| paper | Stable matching mechanisms are not obviously strategy-proof |
| authors | I. Ashlagi, Yannai A. Gonczarowski |
| venue | JET 2018 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper's numbered results concern mechanism existence, incentive properties, and impossibility, without an algorithmic, complexity, approximation, or parameterized claim. The proposed continuous formulation also changes individual OSP into a cohort-level notion, so it is not a faithful computational mirror of the anchored results. No anchor therefore satisfies both required gates.
fails bit a — no named computational result to mirror
The proposed mass formulation makes OSP a cohort-level condition, whereas the paper's OSP compares outcomes for a named individual whose aggregate deviation has zero effect in an atomless population.
fatal: True
The proposal addresses Theorems \(2\) and \(3\) through a new cohort-level stable-matching synthesis model, but the paper contains no qualifying computational result for that mirror.
The honest caveat is important: this paper contains no numbered theorem asserting NP-hardness, polynomial-time solvability, FPT, approximation, or another standard computational classification. Its numbered results are mechanism-existence and incentive-theoretic results. Thus, under the ChoCo anchor rule strictly understood, it has no qualifying computational anchor. Theorem 1 is explicitly cited from elsewhere; Theorems 2 and 3 are proved here but are not complexity results.
If mechanism synthesis is admitted as a computational problem, the strongest positive case is nevertheless a genuine one. Consider large residency or school-admission markets in which many applicants share complete preference rankings, and many positions share complete priority rankings, eligibility constraints, and capacities. The number of applicants and positions may be \(N\gg\tau\), where \(\tau\) is the number of applicant and position types.
A type is a complete ranking over counterpart types and the outside option, together with every relevant eligibility or priority parameter. Let \(P\) be applicant types and \(Q\) position types, with rational masses \(\mu_p\) and \(\nu_q\). A matching is a nonnegative matrix \(\pi\) satisfying
\[ \sum_q \pi_{p,q}=\mu_p,\qquad \sum_p \pi_{p,q}=\nu_q. \]
The entry \(\pi_{p,q}\) is mass of distinct agents of type \(p\) matched to positions of type \(q\); no individual receives a fractional position or lottery. Stability means that there is no pair \((p,q)\) for which positive mass of type \(p\) prefers \(q\) to its assigned position and positive mass of type \(q\) prefers \(p\) to its assigned applicant.
For the one-sided model, position priorities \(\bar q\) are public and applicant rankings are reported. A type-level extensive-form mechanism queries applicant-type rankings and returns a stable mass matching. At a divergence between reports \(r\) and \(r'\), type-level OSP requires every position in the support of the truthful outcome to be weakly preferred under \(r\) to every position in the support of the deviating outcome. This is the direct worst-truthful-versus-best-deviation analogue of the paper’s Definition 3.
The first substantive anchor is Theorem 2, proved in this paper: “\(C^{\bar q}\) is OSP-implementable for every acyclical preference profile \(\bar q\).” Here \(C^{\bar q}\) is the applicant-optimal stable matching rule for a fixed public priority profile. Acyclicality means that there are no \(a,b,c\in P\) and \(x,y\in Q\) with
\[ a\succ_x b\succ_x c\succ_y a. \]
The corresponding continuous problem is Acyclic Stable-Mass OSP Synthesis. Given \((P,Q,\mu,\nu,\bar q)\), with \(\bar q\) acyclic, construct a finite type-query mechanism that, for every applicant-report profile, outputs the applicant-optimal stable mass matching and satisfies the type-level OSP condition above. A solution consists of the mechanism and its matching rule, not merely a feasible matrix.
This is a plausible Class A problem. The induction in Theorem 2 has a natural mass version: when one applicant type is universally highest priority, allocate its mass to its most preferred available position mass and recurse; when two types are relevant, process their priority regions and recurse on the residual masses. The resulting computation should depend on \(|P|+|Q|\) and the encoding length of the masses, rather than on the expanded population \(N\). Clearing denominators gives a finite repeated-type market, while the mass formulation avoids explicitly expanding it.
The second substantive anchor is Theorem 3, also proved here: if \(|M|\ge 3\) and \(|W|\ge 3\), then there exists a public preference profile \(\bar q\) such that no \(\bar q\)-stable one-side-querying matching rule is OSP-implementable. Importantly, this applies to every stable rule, not only the applicant-optimal rule. Lemma 1 gives the explicit \(3\times3\) obstruction used in the proof.
Its continuous counterpart is Cyclic Stable-Mass OSP Existence. Given finite type sets, masses, and public priorities \(\bar q\), decide whether there exists any finite type-query mechanism that is stable for every applicant-report profile and OSP-implementable. If the public priorities contain the paper’s three-by-three cyclic witness on positive-mass types, the expected answer is “no”: the pruning argument is local, and should survive aggregation whenever the six witness types have positive mass. This would be a structural hardness transfer in ChoCo’s sense—not an NP-hardness theorem, but evidence that population continuization does not dissolve the obstruction. For acyclic profiles, Theorem 2 supplies the positive boundary.
The authors would recognise these as their problem: the matching objective remains stability, the strategic question remains obvious strategy-proof implementation, and only the population representation changes from named agents to masses of indistinguishable agents. The scenario is not every matching market; a seven-person committee is not a meaningful limit object. It is the large-cohort regime of admissions, residency, or labour markets with relatively few preference and priority signatures.
The weakest point is serious: OSP is originally an individual extensive-form property, whereas an atomless individual has zero effect on aggregate mass. My proposed type-query version therefore makes OSP a cohort-level property. A literal individual-level continuum mechanism would require a measure-theoretic protocol or a finite-expansion definition, and the paper’s impossibility proof would not automatically transfer through that change. The mass matching itself is a faithful population continuization; the incentive layer is the unresolved part.
So I would present this as a credible continuous research programme around Theorems 2 and 3, with a likely tractable acyclic regime and a likely persistent cyclic obstruction. I would not present it as a formally compliant ChoCo case under the strict computational-anchor requirement, because the paper proves no standard complexity result.
The decisive objection is that this paper has no qualifying computational anchor. Theorem 1 is imported from earlier work, while Theorems 2 and 3 concern existence or impossibility of obviously strategy-proof implementations. None asserts NP-hardness, polynomial-time solvability, approximation, parameterized complexity, or an algorithmic classification. Thus a ChoCo mirror would have to invent a computational problem—mechanism synthesis—not continuize one of the paper’s computational results.
Even granting that enlargement, the proposed Theorem 2 mirror changes the object in a fundamental way. OSP is not a property of an aggregate matching matrix; it is a pointwise property of an extensive-form mechanism, comparing one named agent’s truthful and deviating outcomes at a particular node. In an atomless population, one agent’s report changes zero mass, so aggregate OSP is vacuous. If a whole positive-mass type is allowed to report jointly, OSP becomes a coalition- or cohort-incentive notion, not the paper’s individual OSP. If agents remain individually queried, the mechanism must retain their identities and cannot be represented by the mass vector alone. Those are not alternative technical formulations of the same mirror: they are three different models.
The proposed mass induction also hides this discontinuity. Serial dictatorship works because it assigns a named man one woman at a time. “Allocate a type’s mass to its preferred available position mass” instead assigns a cohort and therefore requires a new collective incentive definition. Clearing denominators merely recreates a finite market in which the original individual mechanism has \(N\) participants; it does not justify quotienting that mechanism by types.
Theorem 3 does not rescue the case. A cyclic \(3\times3\) witness may be replicated with positive-mass types, but the paper’s pruning proof relies on one named man changing reports while the other named agents’ reports remain independently selectable. In a mass model, an individual deviation has zero aggregate effect, whereas a type-wide deviation is a collective deviation. Hence the claimed persistence of the obstruction is not a consequence of the paper; it would require a new theorem about a newly defined cohort-level mechanism. Moreover, once all witness types have positive mass, the masses themselves play no role in OSP-existence: only the finite support and preference domain matter. The “continuous” input is therefore bookkeeping, not the population object driving a computational question.
So the proponent has identified a potentially interesting programme on stable matching with anonymous cohorts, but not a worthwhile continuous mirror of this paper under ChoCo’s remit. The negative case is strong on the strict anchor rule and on the mismatch between individual extensive-form incentives and population continuization; it is weaker only in the broad modelling sense that one could deliberately create a new, cohort-level mechanism-synthesis literature around these ideas.
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.