| paper | d4-conf-atal-2016-0106 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 4 is a numbered result, but it proves an incentive-property impossibility for stable mechanisms, not a result about computing a matching or the hardness of doing so. The proposed continuum question makes positive-mass cohorts strategic and allows fractional assignments, changing the individual truncation problem; the paper’s SAT procedures do not provide a numbered computational theorem anchor.
fails bit a — no named computational result to mirror
Theorem 4 excludes mechanisms by a rule property rather than proving a computational result, and the cohort version changes the strategic actor; the proponent acknowledges both changes but does not establish that the theorem transfers.
fatal: True
The proposal targets only Theorem 4’s truncation-resistance claim. It leaves the other mechanism results, the SAT procedures, and the empirical market findings without a qualifying computational anchor.
The strongest positive case is a type-mass version of matching with couples, focused on the paper’s truncation result. It is a credible research direction, though a weaker ChoCo anchor than a theorem about P, NP-hardness, or parameterized complexity.
A plausible regime is a large centralized placement market with repeated preference templates: for example, applicants grouped by specialty, location priorities, and qualification class, with some paired applicants sharing joint placement preferences. Let \(N\) be the number of resident units and \(\tau\) the number of complete resident types, with \(N\gg\tau\). A type must include everything used by the market: its single or couple status, preference list, and the program priority classes of its members. Program categories have rational capacities \(q_p\) that scale with market size.
For a society with rational type masses \(\mu_t\), a mass assignment sends each single type across programs or nil, and each couple type across jointly ranked program pairs. The assignment variables are nonnegative flows \(x_{t,a}\) and \(y_{t,b}\), summing to \(\mu_t\) for each type and respecting program capacities. Stability means there is no positive mass of a type that can move to a strictly preferred listed option while each affected program would accept those members under its responsive priority and quota rule. Fractional assignment gives each type a distribution over outcomes; compare such distributions by first-order stochastic dominance under the type’s true ranking.
The lead question is whether there exists a direct mechanism, defined uniformly over such markets, that returns a stable mass assignment whenever one exists and resists positive-mass cohort truncations. A deviation moves some \(\delta>0\) mass of type \(t\) to a report that truncates its list. The question is whether the deviators’ resulting assignment distribution can strictly improve, in the first-order stochastic dominance sense, on their truthful assignment distribution. A solution would be either a mechanism with this property or an impossibility proof with a finite-support counterexample. The mechanism has no scalar objective: it selects among stable assignments.
The anchor is Theorem 4, proved in this paper: *No stable mechanism for SMP-C is resident strategy-proof against truncations.* Its witness has two couples with opposing preferences over two stable matchings; by truncating at rank 1, each can force a stable mechanism to select the matching it prefers. The fixed-size witness gives a reason to expect a no-go result to survive when each role is replicated into a positive-mass type and program capacities scale proportionally. I would predict an impossibility-transfer result, since the conflict comes from couples’ joint options rather than from a large number of named residents. That prediction needs proof: fractional mass assignments may create stable mixtures that are unavailable in the paper’s finite instance.
This mirror covers the vulnerability of stable selection to truncation. It does not cover the paper’s empirical claims about market size or couples’ prevalence, its SAT solver comparisons, or its general reordering results. Further questions include whether rational mass-stable assignments correspond to limits or averages of stable matchings in cloned discrete markets, whether fractional mixtures remove the truncation obstruction, and whether stable mass assignments can be computed efficiently in \(m,\tau\), and the input bit length.
The weakest point is that the continuous incentive question is not the paper’s individual strategy-proofness question. A single agent has zero mass, so I make manipulation meaningful by allowing a positive-mass cohort to coordinate its report. The paper does not establish that such collective deviations model its residents’ behavior. The continuous matching model also needs type-level priorities and scaled capacities. Those are plausible co-modifications for a bulk placement market, but they leave the exact transfer from Theorem 4 to be established.
Finally, the paper has no numbered theorem giving a complexity-class result. Its NP-completeness claim for SMP-C is stated in prose and cited to Ronn [20], so it does not meet the requested numbered-anchor test. Theorem 4 is a named mechanism-impossibility result, proved here, and is the best positive anchor only if that broader kind of computational social choice result is admissible. If the gate requires an explicit algorithmic or complexity classification, this paper has no qualifying anchor.
Theorem 4 is the wrong kind of anchor for ChoCo’s stated gate. It proves that a desirable incentive property is impossible for stable mechanisms; it says nothing about the complexity of computing a solution, or the existence of an efficient algorithm. The paper’s NP-completeness claim is attributed to Ronn, and its SAT-RPopt procedure is not accompanied by a numbered complexity result. Calling the mechanism an algorithm does not turn Theorem 4 into one. So the proposed mirror starts from a rule-impossibility result, not a computational result of the kind this programme is charting.
The strongest direct version would keep each resident or couple as an atom of mass \(1/N\), so an individual can still truncate their report. That preserves the paper’s strategic actor, but it leaves the theorem about individual manipulation in a finite instance; the mass representation does not make it a result about continuous societies. In a genuinely atomless model, changing one person’s report leaves the type distribution unchanged, so individual strategy-proofness is vacuous.
The proponent’s rescue is a positive-mass cohort deviation. That is a possible research question, but it changes the strategic actor from one resident or couple to a coalition. It also requires a mass-stability notion with scaled capacities and priority rules, and allows fractional assignments or mixtures of couple outcomes. Theorem 4’s witness over named residents and discrete stable matchings does not establish what happens under those semantics. Computing resident-Pareto-optimal mass assignments might also be worthwhile, but that would pose a new computational problem rather than mirror a complexity result proved here.
I would not argue that no plausible high-multiplicity placement market exists; large markets with repeated preference and qualification profiles are credible. That makes the absolute claim “no worthwhile continuous mirror in any scenario” hard to establish. The stronger, narrower conclusion is that this paper supplies no eligible computational anchor for such a mirror. A continuous matching-with-couples study could still be valuable, but it would be an adjacent project, not the computational continuization of a result this paper establishes.
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.