| paper | On the Gale-Shapley Algorithm for Stable Matchings with a Partial Honesty Nash Refinement |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper has no qualifying named computational result under the required gate. Theorem 1 characterizes equilibrium outcomes, while Theorem 2 bounds response iterations without bounding the cost of finding each response. The proposed typed model is a coherent coordinated-cohort extension, but it cannot supply the missing computational anchor.
fails bit a — no named computational result to mirror
The proposed mirror covers the deferred-acceptance prediction in Theorem 1 and the response-iteration idea in Theorem 2, but not the paper's individual-level lemmas, Proposition 1, or named-agent proof structure.
There is a credible, but deliberately narrow, continuous mirror here. Its strongest anchor is Theorem 1, proved in this paper: every minimally dishonest Nash equilibrium of man-proposing Gale–Shapley yields the woman-optimal stable matching. The paper has no named NP-hardness, P, FPT, or W[1]-hardness theorem; this is therefore an algorithmic-outcome anchor, not a standard complexity anchor.
The mirror I would put forward is Typed Continuum Partial-Honesty Deferred Acceptance.
Let \(P\) and \(Q\) be finite sets of resident and position types. A resident type \(p\in P\) has mass \(\mu_p\), and a position type \(q\in Q\) has mass \(\nu_q\), with rational masses summing to the same total. A type includes the complete information relevant to the problem: its sincere ranking, eligibility, capacity or priority parameters, and its dishonesty metric. Its sincere ranking is a strict order over opposite-side types and being unmatched.
A matching is a nonnegative mass flow \(z=(z_{pq})\), where \(z_{pq}\) is the mass of type-\(p\) residents assigned to type-\(q\) positions. Unmatched mass is allowed. The flow is stable if there is no pair \((p,q)\) such that positive mass of type \(p\) prefers \(q\) to its current assignments and positive mass of type \(q\) prefers \(p\) to its current assignments. Equivalently, writing
\[ A_{pq}(z)=\text{mass of type p that prefers q to its current assignment} \]
and \(B_{pq}(z)\) symmetrically for \(q\), stability requires \(A_{pq}(z)=0\) or \(B_{pq}(z)=0\) for every \((p,q)\).
A symmetric strategic profile assigns one reported ranking \(\bar\pi_i\) to each type. Deferred acceptance then operates on mass: a proposer type sends mass down its reported ranking, while a receiving type keeps the most preferred mass up to its available mass. Each type maximizes its average sincere partner quality, with Kendall–Tau dishonesty as a lexicographic tie-break. A typewise minimally dishonest Nash equilibrium is a report profile in which no typewise deviation improves its average sincere outcome, and no more honest report preserves that outcome.
The continuous problem is:
CPH-DA\(_\infty\). Given \((P,Q,\mu,\nu,\pi)\), compute the aggregate matching flow produced by man-proposing deferred acceptance at a typewise minimally dishonest equilibrium; determine whether all such equilibria produce the same flow; and, if so, output that flow together with a report profile certifying it.
The conjectured answer is that the output is exactly \(z^W\), the woman-optimal stable flow for the sincere typed instance. This is a recognizable analogue of Theorem 1: the object being predicted is still the deferred-acceptance outcome under strategic preference reports and a minimal-dishonesty refinement. Only the population has been continuized. The fractional matching flow is not an unrelated outcome-space relaxation; it is the aggregate assignment of a population whose members are exchangeable within type.
This has a natural regime. Consider a national residency or school-assignment market with millions of residents and seats but comparatively few preference types: for example, cohorts sharing specialty, location, credential, and acceptable-program rankings, and program-seat types sharing priority rules. The paper itself discusses exactly these applications. Rational masses correspond to clone expansions: multiplying all masses by a common denominator produces a finite typed market whose aggregate matching is the continuous flow. Named individuals disappear because they are genuinely interchangeable for the problem, not because the model arbitrarily erases relevant prices or preferences.
I would expect the outcome version of CPH-DA\(_\infty\) to be Class A. Typed deferred acceptance has only finitely many type-to-type proposal events, and \(z^W\) can be computed directly by the woman-proposing mass algorithm without enumerating all reported rankings or all equilibria. The real theorem to prove is that the paper’s partial-honesty argument survives mass splitting and type-level ties.
The paper’s Theorem 2, also proved here, suggests a second question but is a weaker anchor. One can define Typed Continuum Honestification: starting from a canonical typed report profile, repeatedly choose one type and replace its report by a minimally dishonest best response, asking for a finite sequence ending at equilibrium and the minimum number of response rounds. Under whole-type symmetric updates, the natural analogue of the paper’s bound is \( |Q|\binom{|P|+1}{2} \), because each female type’s Kendall dishonesty can decrease only finitely many times. I would treat this as a follow-up problem rather than rely on it for the headline claim: the paper’s bound is on named-agent responses, and converting it to type-block responses changes the strategic granularity.
The weakest point is fundamental. In a genuinely atomless population, one individual has zero mass, so an ordinary unilateral deviation cannot change the matching. The continuous model therefore needs either symmetric typewise deviations, positive-mass deviations, or organized cohorts that submit reports collectively. That is not literally the paper’s individual-agent Nash game. A second issue is that identical types induce ties among named partners, whereas the paper assumes strict individual rankings. These are real departures.
The positive case survives if the intended regime is a centralized matching market in which homogeneous cohorts, schools, or professional groups submit common strategic rankings. Then typewise strategic behavior is an economically meaningful high-multiplicity analogue, and CPH-DA\(_\infty\) preserves the paper’s central question and its unique-outcome conclusion. I would not claim that the paper already establishes this continuous theorem; I would claim that it defines a precise, recognizable computational problem whose natural first prediction is tractability and whose main open issue is whether partial-honesty uniqueness survives continuization.
The decisive objection is that this paper offers no qualifying computational anchor. Theorem 1 is an equilibrium-characterisation result, not a complexity, algorithmic, approximation, or parameterized-complexity theorem. Theorem 2 gives a finite improvement bound, but not an algorithm: it says nothing about the complexity of finding a minimally dishonest best response. Thus any proposed continuous problem would be a new strategic matching model, rather than the continuization of a computational result in the paper.
Theorem 1 also depends essentially on finite, named agents. A unilateral deviation changes one preference list and can change the deferred-acceptance matching. In an atomless society, changing one agent’s report changes a zero-mass set, so the aggregate flow is unchanged:
\[ \Delta z=0. \]
Every report therefore gives the same material outcome, and minimal dishonesty selects the sincere report. The strategic force that produces the woman-optimal outcome disappears; truthful man-proposing deferred acceptance remains. This is a genuine degeneration of the paper’s central game, not a technical issue about strict inequalities.
The proposed repair—letting an entire type submit one report—is not the same game. It turns a type into a coalition or a single bloc player. The paper’s Nash equilibrium permits each named agent to deviate independently, whereas typewise CPH-DA permits only coordinated mass deviations. If identical clones are allowed to submit different strategic reports, then the continuous state must record the distribution of reports within each sincere type; the mass vector \(\mu\) is insufficient. If they are forced to submit the same report, that is an additional symmetry or coordination assumption.
The purported flow analogue also loses the objects used in the proof. A type may be split across several partner types, so there is no individual “\(k\)th choice” to which Lemmas 2, 3, and 5 can apply. Kendall distance is defined for an individual report, not for an aggregate flow. Likewise, the lattice and uniqueness arguments rely on strict rankings of named partners; type aggregation introduces capacities, ties, and potentially multiple stable flows. Defining a woman-optimal flow and a typewise honesty cost can certainly produce a coherent new model, but neither is forced by the paper.
A clone-limit formulation does not repair this cleanly. With \(N\) clones, preserving strict rankings over named partners makes the relevant type space grow with \(N\), so there is no fixed finite-type high-multiplicity limit. Collapsing partners into types instead replaces the paper’s strict one-to-one game by a capacitated or tied matching model. Matching markets certainly do have sensible high-multiplicity regimes; that is not the objection. The objection is that the paper’s strategic object does not survive that compression.
Theorem 2 fails for the same reason. Its bound
\[ |W|\binom{|M|+1}{2} \]
counts individual inversion corrections. With many clones, the corresponding individual potential scales with the number of clones. If one updates an entire type at once, the proposed bound
\[ |Q|\binom{|P|+1}{2} \]
is merely the bound for a newly defined block-coordinate game; its independence from population mass comes from changing the move, not from a continuum phenomenon. If arbitrary submasses may deviate, the inversion potential is no longer integer-valued and the finite-descent proof disappears. And again, the theorem gives no complexity bound for computing the required best responses.
A centralized cohort model for residency or school assignment could be worthwhile in its own right. But it would study strategic blocs submitting common rankings, with a newly chosen aggregate utility and honesty convention. That is a new matching programme, not a continuous mirror of this paper’s individual partial-honesty Nash game. Under ChoCo’s computational-anchor standard, both proposed anchors therefore fail; the universal claim that no conceivable related model could be valuable is necessarily stronger than one can prove, but no qualifying mirror of the paper’s actual results survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.