GPT 6 Astra Ultra attempt on Econ-342

A most-probably popular house allocation: a research attempt

Status: unresolved. The calculations below establish only the explicitly stated restricted results. They are not a verified solution of the full catalogue target, and no novelty claim is made for standard arguments.

Target and deterministic verification

Applicants alone vote between matchings; all acceptable houses are preferred to being unmatched. A matching must be chosen before a random strict preference profile is drawn. Its objective $\pi(M)$ is the probability that no competing matching defeats it by a strict majority. The original target asks for classification under explicit joint support, independent applicant lotteries and independent tie refinements.

First fix a profile $P$ and matching $M$. For every applicant $a$ and acceptable house $h$, let $w_{a,h}$ be $1,0,-1$ according as $h$ is better than, equal to, or worse than $M(a)$. Add an applicant-specific dummy house for being unmatched, with the corresponding vote weight. Maximizing total weight over matchings assigning every applicant a real or its own dummy house computes the largest voting margin against $M$. The matching $M$ itself gives margin zero; it is popular exactly when the maximum is zero. Maximum-weight bipartite matching therefore tests popularity in polynomial time. Dummy choices also count the negative votes of applicants made unmatched; ignoring those votes would give the wrong test.

For explicit profiles $P_1,\ldots,P_K$ with rational probabilities $p_k$, evaluation is consequently polynomial: $\pi(M)=\sum_kp_k\mathbf1\{M\text{ popular at }P_k\}$. Rational addition and comparison have polynomial bit complexity in the input. This establishes NP membership for the explicit-joint threshold problem but does not make optimization polynomial.

A two-applicant component and its exact behavior

Take two applicants $u,v$ and two houses $x,y$, with all four pairs acceptable. There are two complete matchings: $M^0=\{ux,vy\}$ and $M^1=\{uy,vx\}$. Three strict profiles realize the following sets of popular matchings:

1. Both applicants receive their top house in $M^0$: $u:x\succ y$, $v:y\succ x$. Then only $M^0$ is popular.
2. Reverse both lists. Then only $M^1$ is popular.
3. Give both applicants the same list $x\succ y$. Then both complete matchings are popular.

For the first two claims the alternative complete matching loses two votes. No partial matching is popular: an unmatched applicant can receive a free acceptable house without changing anybody else's assignment. In the third profile the two complete matchings tie one vote each; a partial alternative cannot win, since every changed unmatched status is worse and at most one applicant can improve by taking $x$. These observations exhaust the component's possibilities.

For a disjoint union of components, a global matching is popular if and only if every component restriction is popular. A defeating alternative in one component can be joined with the unchanged matching elsewhere. Conversely every alternative has a nonpositive voting margin in each component when all component restrictions are popular, so its total margin is nonpositive. This factorization is a deterministic event statement and does not assume independent uncertainty.

Explicit-joint NP-completeness by a cut reduction

Let $G=(V,E)$ be an instance of unweighted MAX-CUT with $m=|E|>0$. Create one component of the preceding form for every vertex $v$, and interpret its selected complete matching as a bit $z_v\in\{0,1\}$. For every edge $\{u,v\}$ put two profiles into the joint lottery, each with probability $1/(2m)$:

• one profile forces $z_u=0,z_v=1$ using the first two component profiles;
• the other forces $z_u=1,z_v=0$;
• all other components use the third, permissive profile.

The support has $2m$ profiles and description length polynomial in $|V|+m$. Correlation across applicants is explicit and allowed by this encoding. The reduction also preserves multiplicative approximation ratios on these instances, since both objective values differ only by $2m$. No stronger approximation hardness is claimed without an appropriate hardness theorem for MAX-CUT. Notice that each individual support profile here does possess popular matchings, but a single matching cannot generally satisfy all profiles. In these constructed instances the optimum is at most $1/2$.

An independent-uncertainty tractable restriction

For independent applicant lotteries on a disjoint union of $K_{2,2}$ components, each component has at most four strict profile outcomes. Compute its two probabilities $\pi_v(0),\pi_v(1)$ directly. Independence across components and the deterministic factorization imply \[ \pi(M_z)=\prod_{v\in V}\pi_v(z_v). \] Selecting in each component a bit with the larger local probability maximizes the product, including the possibility of zero factors. Products and comparisons of explicitly encoded rationals have polynomial bit length. Independent uniform tie refinements also fall into this restriction because each two-house list has at most two refinements. The explicit-joint reduction therefore crucially uses correlation: it cannot be silently transferred to independent lotteries on this same graph.

For general graphs with independent compact uncertainty, a fixed matching can still be evaluated by sampling profiles and running the deterministic popularity test. Hoeffding's inequality gives additive error at most $\epsilon$ with probability at least $1-\eta$ using at least $\log(2/\eta)/(2\epsilon^2)$ independent samples. Uniform control over a candidate set of $L$ matchings replaces the numerator by $\log(2L/\eta)$. This is a statistical evaluation bound, not an efficient optimization algorithm: maximizing the sampled success count over all matchings retains a combinatorial search. A multiplicative guarantee also becomes problematic near zero success probability.

Completion Estimate

59%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt proves NP completeness for explicit joint popularity thresholds, polynomial evaluation, and an exact independent uncertainty algorithm on disconnected two applicant components. The full classification still lacks general independent lottery and tie refinement hardness or algorithms, together with their optimization approximation guarantees.

Checks, status and sources

The argument gives a complete classification of the explicit-joint threshold subproblem and an exact independent-uncertainty restriction. It leaves the original general independent-lottery and tie-refinement classifications, and their approximation regimes, unresolved. The reduction is presented with proof; no priority or literature-novelty claim is made.

Katarína Cechlárová, Ágnes Cseh and David F. Manlove (2019), Selected Open Problems in Matching Under Preferences, Section 3.1.2 inspected for the uncertainty models and proposed popularity extension: https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. Michael R. Garey, David S. Johnson and Larry Stockmeyer (1976), Some Simplified NP-Complete Graph Problems, Theoretical Computer Science 1, 237--267; primary publisher abstract inspected for NP-completeness of simple unweighted MAX-CUT: https://doi.org/10.1016/0304-3975(76)90059-1.