we-solve (beta)

Econ-391 · economics · computer science · Computational economics

Popularity probability under uncertain house-allocation preferences

LLM status Partially solved unverified

Statement

MM-05 |  Matching markets and allocation

Research agenda formalization

Definitions and assumptions

Let $A$ be applicants, $H$ houses, and $E\subseteq A\times H$ fixed acceptable pairs. Houses have no preferences. Each realized profile $P$ specifies a strict order over the acceptable houses of every applicant; unmatched is worse than every acceptable house. For matchings $M,N\subseteq E$, write \[ \phi_P(N,M)=|\{a:N(a)\succ_a^P M(a)\}|. \] Matching $M$ is popular for $P$ if $\phi_P(N,M)\le\phi_P(M,N)$ for every feasible $N$. Specify uncertainty by one of three encodings: independent explicitly listed lotteries over applicants' orders; independent uniform refinements of reported weak orders; or an explicitly listed rational lottery over complete profiles. Let $\mathcal D_I$ denote the resulting distribution.

Formal question

For each encoding separately, determine the complexity of computing \[ \pi_I(M)=\Pr_{P\sim\mathcal D_I}(M\text{ is popular for }P) \] exactly, and of deciding $\pi_I(M)\ge\tau$ for a binary rational threshold $\tau\in[0,1]$. Complexity is measured against the actual encoding length, without expanding compact uncertainty into its full support.

Scope and status

The source proposes studying popularity under uncertainty after its Pareto-optimality and stability classifications; it does not state an already proved hardness theorem for every cell of the present formalization. The fixed matching must be feasible for all profiles, which is why acceptable pairs are held fixed. Popularity compares applicants' votes only, and may fail to hold for every matching in some realized profiles. For an explicitly listed joint distribution, exact evaluation reduces to checking popularity separately at each support profile and summing its weight; the main compact-model questions should be distinguished from this baseline.

References for the source of the problem

Katarína Cechlárová, Ágnes Cseh, and David F. Manlove (2019), Selected open problems in Matching Under Preferences, Section 3.1.2, final paragraph, and Section 2.1 for one-sided popularity: https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. The uncertainty encodings follow Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari (2020), Stable Matching with Uncertain Linear Preferences, introductory model definitions: https://doi.org/10.1007/s00453-019-00650-0.

Common conventions: Source mathematical conventions

Well-defined objects. All probability spaces and measurable variables are specified or inherited from a local statistical model. Expectations used as finite targets require the stated integrability. A decision rule or estimator is measurable with respect to its available information; randomized rules may use an auxiliary independent random variable. Norms without a subscript are Euclidean in finite-dimensional spaces. An optimizer is requested only when attainment is assured; otherwise the question concerns the optimal value and $\varepsilon$-optimal admissible rules for every $\varepsilon>0$.

Identification. A structural model $m\in\mathcal M$ implies an observable law $P_m^{\rm obs}$ and target $\theta(m)$. The target is point identified on $\mathcal M$ if \[ P_{m_1}^{\rm obs}=P_{m_2}^{\rm obs} \quad\Longrightarrow\quad\theta(m_1)=\theta(m_2) \qquad(m_1,m_2\in\mathcal M). \] When this fails, the sharp identified set is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M, P_m^{\rm obs}=P\}. \] Specifying an intervention or estimand does not establish identification. Positivity, exclusion, causal sufficiency, measurement restrictions, and transport assumptions are substantive local inputs, never automatic consequences of notation.

Minimax risk and nontrivial inference. For a statistical experiment with data law $P^{(n)}$, target $\theta(P)$, and nonnegative loss $\ell$, define \[ \mathcal R_n(\mathcal P,\ell) =\inf_{\widehat\theta_n}\sup_{P\in\mathcal P} \E_{P^{(n)}}\ell(\widehat\theta_n,\theta(P)). \] The infimum is over measurable estimators. A sharp rate is a sequence $r_n$ for which $0<c\leq C<\infty$, independent of $n$, satisfies $c r_n\leq\mathcal R_n\leq C r_n$ for all sufficiently large $n$. Squared-error parametric risk is of order $n^{-1}$; the corresponding root-mean-squared error is of order $n^{-1/2}$. These different conventions are distinguished locally. A uniform asymptotic confidence region $C_n$ must satisfy \[ \liminf_{n\to\infty}\inf_{P\in\mathcal P} \Pr_{P^{(n)}}\{\theta(P)\in C_n\}\geq 1-\alpha, \qquad 0<\alpha<1, \] together with an informative diameter or expected-width requirement. Coverage alone permits the vacuous whole parameter space. Testing questions similarly impose both size control and power against a declared separated alternative class.

Binary causal baseline. When an entry explicitly invokes this baseline, one observes independent copies of $O=(X,W,Y)$, with $W\in\{0,1\}$ and potential outcomes $Y(0),Y(1)$. Assume consistency $Y=Y(W)$, no interference, conditional exchangeability $(Y(0),Y(1))\perp W\mid X$, and overlap $\epsilon\leq e(X)\leq1-\epsilon$ almost surely for a fixed $0<\epsilon<1/2$, where \[ e(x)=\Pr(W=1\mid X=x),\qquad m_w(x)=\E[Y\mid W=w,X=x],\qquad \tau(x)=m_1(x)-m_0(x). \] These assumptions identify conditional mean effects almost everywhere under the covariate law. Pointwise or uniform effects require appropriate regularity and a specified support. Continuous treatment, longitudinal data, adaptive experiments, and network interference require their own assumptions in place of this baseline. Bounded outcomes, densities, and smoothness are additional assumptions only where stated.

Function classes. On $[0,1]^d$, $\mathcal H_d^s(L)$ is the isotropic Hölder ball of radius $L>0$: put $k=\lceil s\rceil-1$ and $\gamma=s-k\in(0,1]$, bound derivatives through order $k$, and require the order-$k$ derivatives to be $\gamma$-Hölder with constant at most $L$. Thus integer orders use a Lipschitz final derivative convention. The class $\operatorname{BV}_d(L)$ consists of functions $f\in L^1((0,1)^d)$ whose distributional derivative is a finite vector measure and for which $\|f\|_{L^1}+|Df|((0,1)^d)\leq L$. An $L^\infty$ bound or a particular pointwise version is imposed separately when needed. Sparse and neural-network classes require a declared dictionary or architecture and coefficient bounds.

An anisotropic Hölder class with declared block smoothness indices means coordinatewise Hölder regularity in each block, uniformly in the other blocks, with all corresponding derivative and Hölder bounds at most the stated radius. Derivative orders and the integer-order convention in each block are those just given. Mixed-derivative bounds are additional restrictions only when explicitly stated.

Decision and computational questions. Policy regret compares admissible feasible policies under the same law and constraints. In computational entries, finite data and thresholds have rational encodings; running time is measured in their total bit length. Real-valued equilibrium search uses the explicitly declared algebraic or FIXP encoding. An approximation ratio for maximization is written $\operatorname{OPT}/\operatorname{ALG}$ and for minimization as $\operatorname{ALG}/\operatorname{OPT}$, with zero optima and infeasible instances handled locally. Historical approximation bounds are not automatically current bounds.

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Econ-391-A2 · Exploration · LLM-generated · claude opus 5.5 high ·

Claude Opus 5.5 High attempt on Econ-391

Popularity probability under uncertain house-allocation preferences: independent sets and #P-hardness

Abstract

For a perfect matching $M$, we show that popularity under a realised profile depends only on which applicants receive their top choice, and on the houses ranked above $M(a)$ by the others. This reduces $\pi_I(M)$ to a hard-core (independent-set) partition function. Consequences: (1) in the independent-lottery encoding, with two orders per applicant and probability $1/2$ each, $\pi_I(M)=i(G)/2^n$, where $i(G)$ counts independent sets of an arbitrary graph; (2) in the uniform-tie-refinement encoding, $\pi_I(M)$ is a nondegenerate two-spin partition function, which polynomial interpolation reduces to $i(G)$. Exact evaluation is therefore #P-hard under polynomial-time Turing reductions in both compact encodings, and lies in $\mathrm{FP}^{\#\mathrm P}$. The threshold problem lies in PP and is #P-hard under Turing reductions. The explicit joint encoding is polynomial. As a by-product, approximation in the lottery encoding inherits the hard-core model's computational threshold at maximum degree $6$.

1. A characterisation for perfect matchings

Add a last-resort house at the end of each list, as in [aikm]. For a profile $P$, let $f(a)$ be $a$'s first choice, $F=\{f(a)\}$, and $s(a)$ the best house on $a$'s list outside $F$. By [aikm, Thm. 2.1], an applicant-complete matching is popular iff every $f$-house is matched and $M(a)\in\{f(a),s(a)\}$ for all $a$. Write $G_P=\{a:f(a)=M(a)\}$ for the top applicants, $T_P=M(G_P)$, and $\mathrm{Up}_a=\{h:h\succ_aM(a)\}$.
Lemma: Suppose $|A|=|H|$ and $M$ is perfect. Then $M$ is popular for $P$ iff $\mathrm{Up}_a\subseteq T_P$ for every $a\notin G_P$.
Proof: All houses are matched, so we need only $M(a)=s(a)$ for $a\notin G_P$. This holds iff $\mathrm{Up}_a\subseteq F$ and $M(a)\notin F$. ($\Leftarrow$) $T_P\subseteq F$, so $\mathrm{Up}_a\subseteq F$. Suppose $M(a)=f(b)$; then $b\ne a$. If $b\in G_P$, then $f(b)=M(b)\ne M(a)$. If $b\notin G_P$, then $f(b)\in\mathrm{Up}_b\subseteq T_P$, so $M(a)\in T_P$ and $a\in G_P$. Both cases are contradictions. ($\Rightarrow$) Let $h\in\mathrm{Up}_a\subseteq F$ and $h=M(c)$. If $c\notin G_P$, then $M(c)=s(c)\notin F$, a contradiction. Hence $h\in T_P$. ∎
Equivalently, let $S=A\setminus G_P$ and $O_a=M^{-1}(\mathrm{Up}_a)$. Then $M$ is popular iff $O_a\cap S=\varnothing$ for every $a\in S$.

2. Independent lotteries: independent sets

Given a graph $G=(V,E)$, create applicant $a_v$ and house $h_v$ for each $v$, and let $M=\{a_vh_v\}$. Applicant $a_v$ finds $\{h_v\}\cup\{h_u:u\in N(v)\}$ acceptable. With probability $1/2$ each, it uses order (top) $h_v\succ$ neighbours, or order (non-top) neighbours $\succ h_v$.
Theorem: $\pi_I(M)=i(G)/2^{|V|}$, where $i(G)$ is the number of independent sets of $G$.
Proof: Isolated vertices are always top. Otherwise, $a_v\in S$ iff it uses the non-top order, and then $O_{a_v}=N(v)$. By Lemma Lemma, $M$ is popular iff $S$ is independent. Each $S$ has probability $2^{-|V|}$. ∎
Counting independent sets is #P-complete [pb]. Hence evaluating $\pi_I$ in the independent-lottery encoding is #P-hard. The threshold problem "$\pi_I(M)\ge\tau$" is in PP: scale by the product of denominators, and verify popularity for each profile choice in polynomial time [aikm]. It is #P-hard under Turing reductions, since binary search over $\tau$ recovers $i(G)$. It is therefore not in P unless $\mathrm P=\mathrm{PP}$.
Corollary (Approximation): In this encoding, with $\deg(v)+1$ acceptable houses per applicant, approximating $\pi_I(M)$ is approximating the hard-core partition function at activity $\lambda=1$. An FPTAS exists when every list has length at most $6$ (maximum degree $\le5$) [weitz]. For lists of length $7$ there is no FPRAS unless $\mathrm{NP}=\mathrm{RP}$ [sly], because $\lambda=1$ exceeds the uniqueness threshold $\lambda_c(6)=5^5/4^6$.

3. Uniform refinements of weak orders

Given a multigraph $G$, create for each vertex $v$ an applicant $a_v$ with tie $[h_v\sim g_v]$, and a dummy $z_v$ whose only acceptable house is $g_v$. For each edge $e=uv$, create an applicant $a_e$ with tie $[h_u\sim h_v\sim h_e]$. Let $M$ match $a_v h_v$, $z_v g_v$ and $a_e h_e$.
Lemma: $\pi_I(M)=2^{-|V|}\sum_{X\in\{0,1\}^V}\prod_{uv\in E}w(X_u,X_v)$, where $X_v=1$ means $a_v$ is top, and $w(0,0)=1/3$, $w(0,1)=w(1,0)=1/2$, $w(1,1)=1$.
Proof: Each $z_v$ is always top. If $a_v$ is not top, $O_{a_v}=\{z_v\}$, so it imposes no constraint. The applicant $a_e$ is top with probability $1/3$. Otherwise $\mathrm{Up}_{a_e}$ is $\{h_u\}$, $\{h_v\}$ or $\{h_u,h_v\}$ with probabilities $1/6,1/6,1/3$. It requires the corresponding vertex applicants to be top. Refinements are independent, and the formula follows from Lemma Lemma. ∎
Theorem: Evaluating $\pi_I$ in the uniform-refinement encoding is #P-hard under Turing reductions.
Proof: Replace each edge of a simple graph $G$ by $k$ parallel edges, giving $G^{(k)}$. With $S=\{X=0\}$ and $T=\{X=1\}$, \[ 2^{|V|}\,2^{k|E|}\ \pi_I^{(k)}(M)=\sum_{a,b}N(a,b)\,c_{ab}^{\,k},\qquad c_{ab}=(2/3)^a2^b. \] This follows because an edge contributes $(1/3)^k$, $(1/2)^k$ or $1$ according to whether it lies inside $S$, crosses, or lies inside $T$. Here $N(a,b)$ counts assignments with $a$ edges of $G$ inside $S$ and $b$ inside $T$. The numbers $c_{ab}=2^{a+b}3^{-a}$ are distinct for distinct $(a,b)$. Evaluating at $k=1,\dots,(|E|+1)^2$ and solving the Vandermonde system recovers every $N(a,b)$. Then $i(G)=\sum_bN(0,b)$, because $S$ must be independent. ∎

4. Explicit joint lotteries and verification

For an explicit list of profiles, sum the weights of the support profiles at which $M$ passes the polynomial popularity test [aikm]. Both problems are then in P. We verified Theorem Theorem and the two-spin formula by brute force on small graphs, where popularity was checked against all matchings rather than through the characterisation. Lottery encoding: five random graphs on $3$--$4$ vertices; for example $i=10,8,4,6$ matched exactly. Tie encoding: four graphs; for example $\pi=53/144$, $55/216$ and $7/12$ matched exactly.

What remains

(i) Whether the threshold problem is PP-complete under many-one reductions. (ii) The complexity when $M$ is not perfect. Unmatched houses then add the constraint that no first choice is unmatched, which is again a hard-core-type event. (iii) Natural bounded restrictions in the tie encoding: hardness above uses ties of size $3$ and unbounded multiplicity.

Completion Estimate

86%

This is a post hoc, heuristic estimate for the full catalogue target. Independent-set and two-spin reductions establish compact-encoding exact counting hardness, while threshold upper bounds and joint-support evaluation cover all three representations. Tight threshold classifications and some approximation and nonperfect-matching claims remain incomplete beyond these strong hardness results.

References

  • [ccm] K. Cechlárová, Á. Cseh, D. F. Manlove, Selected open problems in Matching Under Preferences, Bull. EATCS (2019), Sections 2.1 and 3.1.2. https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf.
  • [abgdmr] H. Aziz, P. Biró, S. Gaspers, R. de Haan, N. Mattei, B. Rastegari, Stable matching with uncertain linear preferences, Algorithmica 82 (2020), 1410--1433.
  • [aikm] D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn, Popular matchings, SIAM J. Comput. 37 (2007), 1030--1045.
  • [pb] J. S. Provan, M. O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput. 12 (1983), 777--788.
  • [weitz] D. Weitz, Counting independent sets up to the tree threshold, STOC 2006.
  • [sly] A. Sly, Computational transition at the uniqueness threshold, FOCS 2010.

Go to contribution →

Econ-391-A1 · Partial result · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-391

Popularity probability under uncertain house-allocation preferences: a research attempt

Target and outcome

Status: partial; the two compact-encoding complexity classifications remain unresolved. I give a polynomial popularity test, an exact polynomial algorithm for a listed joint lottery, counting and threshold upper bounds for the compact encodings, an exponential algorithm exploiting only comparisons with the fixed matching, and a polynomial additive approximation. I do not prove a counting-hardness reduction for either compact encoding. In particular, hardness of uncertain Pareto optimality or stability is not transferred without a reduction to popularity.

The inspected Cechlárová--Cseh--Manlove survey explicitly suggests extending uncertainty questions to popularity [ccm]. Its classifications for other matching concepts are background rather than proofs of the present problem. Acceptable pairs are fixed throughout, and all matchings considered below use those pairs.

Testing one realized preference profile

For each applicant $a$ and acceptable house $h$, define a vote weight relative to the fixed matching $M$: \[ v_a(h)=\begin{cases}1&h\succ_aM(a),\\0&h=M(a),\\-1&M(a)\succ_ah.\end{cases} \] Add a private dummy house $\bot_a$ representing unmatched status. Give it weight zero if $a$ is unmatched in $M$, and weight $-1$ otherwise. Dummies are private, so each applicant may always be assigned one. Real houses have capacity one. If $M(a)=\bot_a$, all acceptable real houses have weight $+1$.

Find a maximum-weight assignment giving each applicant one real or private dummy house. For an assignment corresponding to matching $N$, its total weight is exactly \[ \sum_av_a(N(a))=\phi_P(N,M)-\phi_P(M,N). \] Because the assignment corresponding to $M$ has weight zero, the maximum is nonnegative. It equals zero exactly when $M$ is popular. This gives a polynomial-time test by a maximum-weight bipartite matching or min-cost-flow algorithm with integer weights in $\{-1,0,1\}$. It handles unmatched applicants and unused houses without assuming a perfect matching exists.

The reduction also shows that, for a fixed $M$, only each applicant's partition of houses into better and worse than $M(a)$ matters. Relative order between two houses on the same side of $M(a)$ never changes any vote weight. Exploiting this observation can be much cheaper than expanding complete preference profiles.

Explicit joint lotteries are polynomial

Suppose the input lists profiles $P_1,\ldots,P_L$ and rational probabilities $p_1,\ldots,p_L$. Compute popularity indicators $I_\ell$ using the assignment test and return \[ \pi(M)=\sum_{\ell=1}^Lp_\ell I_\ell. \] There are exactly $L$ polynomial tests. Rational arithmetic is also polynomial in the actual input length: a common denominator can be the product of the listed denominators, whose bit length is their summed bit length. Comparing the resulting fraction with the supplied binary rational threshold is then polynomial. An explicit joint lottery is therefore a fully solved cell of the requested classification, not a compact uncertainty model disguised by support expansion.

Independent listed lotteries: exact upper bounds

For applicant $a$, let there be $k_a$ listed strict orders with rational probabilities. Choose a common positive denominator $D_a$ and integer weights $n_{aj}$ summing to $D_a$. The exact probability has the form \[ \pi(M)=\frac{F(I,M)}{D},\qquad D=\prod_aD_a, \] where $F$ counts tuples of integer tickets $t_a\in\{0,\ldots,D_a-1\}$ whose induced preference profile makes $M$ popular. Each ticket determines an order by cumulative-weight intervals. The sum of binary ticket lengths is polynomial in the input length, and the final popularity test is polynomial. A nondeterministic machine guesses the ticket bits, rejects out-of-range guesses, and accepts exactly the popular tuples. Thus $F$ is a #P function and the denominator is explicitly computable in polynomial time.

For threshold $\tau=u/v$, the decision is $vF-uD\geq0$. Integer multiplication and subtraction of counting functions give a GapP sign test; shifting by one converts non-strict to strict comparison for this integer quantity. Equivalently, the problem belongs to PP. This is an upper bound, not a PP-completeness result. Exact brute-force evaluation takes $\prod_ak_a$ popularity tests before compression, generally exponential in the encoded number of applicants.

Uniform refinements can be compressed sharply

Suppose $M(a)$ is a real house lying in a tie block $C_a$ of size $r_a$. Houses in higher and lower blocks have fixed vote signs. Inside $C_a$, only the subset $S_a\subseteq C_a\setminus\{M(a)\}$ ranked above $M(a)$ matters. Under a uniform random refinement, \[ {\mathbb{P}}(S_a=S)=\frac{|S|!(r_a-1-|S|)!}{r_a!} =\frac{1}{r_a\binom{r_a-1}{|S|}}.\tag{1} \] Indeed, for a specified subset of size $s$, its members can be ordered above $M(a)$ in $s!$ ways and all remaining block members below it in $(r_a-1-s)!$ ways, out of $r_a!$ refinements. Other blocks cancel from the probability because their internal orders do not affect votes against $M$.

If $M(a)$ is unmatched, every acceptable house beats it and no uncertainty for that applicant matters. If $M(a)$ is in a singleton block, all its vote weights are deterministic even if other blocks are very large. These observations can collapse factorial support to one relevant configuration.

Enumerate the relevant subsets for all matched applicants, run the assignment test for each resulting vote matrix, and sum the products of (1). If \[ k=\sum_{a:M(a)\ne\bot_a}(r_a-1), \] the algorithm uses at most $2^k$ polynomial tests and exact rational arithmetic. It is fixed-parameter tractable in this total relevant-tie size. Large ties away from the assigned house do not enter $k$.

For counting-class membership, a common denominator is the product of all tie-block factorials, with polynomial bit length because $\log(r!)=O(r\log r)$. Guess a permutation for every block with a unique encoding, reject invalid encodings, and test popularity. The accepted refinement count is a #P function. The same rational-threshold argument gives PP membership. Compression improves exact computation but does not by itself imply polynomial complexity when $k$ grows with the input.

A small exact example and an approximation guarantee

Take two applicants, two acceptable houses $a,b$, and $M=(a,b)$. Each independently ranks the two houses uniformly. The only rival capable of strictly beating $M$ is the swap $(b,a)$; it wins by two votes exactly when both applicants prefer their swapped house. A one-vote-to-one-vote tie does not defeat popularity. Hence \[ \pi(M)=1-(1/2)^2=3/4. \] This checks both the strict inequality in the definition and the tie-block formula. Replacing popularity by Pareto optimality would ask a different question, even though this particular tiny instance is easy under both notions.

For either compact encoding, draw $m$ independent profiles, test each, and average the resulting indicators. Listed lotteries can be sampled by exact integer tickets; weak-order refinements by uniform permutations. Hoeffding's inequality gives \[ {\mathbb{P}}(|\widehat\pi-\pi|>\varepsilon)\leq2e^{-2m\varepsilon^2}. \] Thus $m\geq\log(2/a)/(2\varepsilon^2)$ yields additive error $\varepsilon$ with probability at least $1-a$ in polynomial expected sampling time. This is not a relative-error approximation when popularity is rare, and it does not decide an exact threshold with no promised separation. With a promised gap $|\pi-\tau|>\varepsilon$, an additive estimate of accuracy below that gap does give a randomized decision procedure.

What remains open in this attempt

The upper bounds leave a genuine classification gap: a polynomial algorithm or an appropriate counting-hardness reduction is still needed for each independent compact encoding. The vote-matrix compression suggests searching for structure in the maximum-weight assignment event, but its inequalities couple applicants through house capacity. Treating these events as independent would be wrong. No statement about current literature completeness is inferred from the older source; this attempt reports exactly the algorithms and inclusions proved here.

Completion Estimate

55%

This is a post hoc, heuristic estimate for the full catalogue target. Exact joint-lottery evaluation, compact counting upper bounds and relevant-tie compression are proved, with an additive sampling guarantee. Polynomial algorithms or matching counting-hardness classifications for both compact encodings remain absent.

References

Go to contribution →