| paper | d4-conf-ijcai-2015-0508 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): every valid instance admits a rational stable assignment. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set of programs \(P\), supported single-doctor types \(S\), couple types \(K\), rational type masses \(\alpha_s,\beta_k\), and rational per-capita quotas \(q_p\), decide whether there are rational assignment flows \(x_{s,p}\) and \(y_{k,(p_1,p_2)}\) that exhaust each type’s mass, respect quotas and individual acceptability, and admit no blocking deviation. Each type specifies its complete relevant preferences; programs rank doctor types, with members of a type sharing a priority. A blocking deviation is a positive mass of a type moving to a preferred option that the destination programs can accept under responsive choice, with both members accepted together when a couple chooses the same program. If such flows exist, produce one. Measure complexity in the number of programs \(m\), supported types \(\tau=|S|+|K|\), input bit length \(L\), and preference-list lengths.
A rational-mass stable matching market with single and couple types, complete type-level preferences, program priority classes, per-capita quotas, and flows assigning single mass to programs and couple mass to program pairs. Stability rules out preferred deviations that the programs can jointly accept under responsive choice.
The paper assumes strict individual program rankings, while the mirror groups repeated agents into equal-priority types and needs a mass-level blocking definition for couples; Theorem 1 establishes neither change.
fatal: False
The mirror covers existence and construction of stable SMP-C assignments; it leaves the DA, SAT, and IP runtime comparisons, empirical satisfiability rates, and resident-outcome comparisons unmirrored.
The strongest mirror I see is Continuous Stable Matching with Couples over Masses. It keeps the paper’s central question—whether a stable assignment exists when couples have joint preferences over program pairs—and changes the unit of the market from named applicants to masses of applicants with identical relevant data.
The paper’s numbered anchor is Theorem 1, proved here. It says that for an SMP-C instance, if a matching \(\mu\) and a SAT-E assignment \(\pi\) correspond via \(m_d[p]\) being true exactly when \(\mu(d)=p\), then \(\mu\) is stable if and only if \(\pi\) satisfies SAT-E. The proof also shows that each fixed setting of the doctor-matching variables uniquely determines the auxiliary variables, so satisfying assignments correspond one-to-one with stable matchings. The theorem is about the underlying stable-matching problem, not just an encoding: SAT-E is computed with to find or rule out stable matchings.
The mirror’s instance has a finite set of programs \(P\), single-doctor types \(S\), and couple types \(K\). A type records all the data the problem uses: a single type’s program ranking and each program’s priority for that doctor type; a couple type’s two members’ program-priority types and their joint ranking over program pairs. Give each type a rational mass, \(\alpha_s\) for \(s\in S\) and \(\beta_k\) for \(k\in K\), normalized so that \(\sum_s \alpha_s+2\sum_k\beta_k=1\). Each program \(p\) has a rational per-capita quota \(q_p\). A solution consists of rational flows \(x_{s,p}\) of single-doctor mass to programs and \(y_{k,(p_1,p_2)}\) of couple mass to program pairs, including unmatched options. They must exhaust each type’s mass, respect program quotas, and use only individually acceptable assignments.
Call such a flow stable when there is no positive mass of a single type or couple type that prefers another assignment and can be accepted under the programs’ responsive choice rules. For a couple, the two proposed program assignments must be accepted together; if both members would go to the same program, that program must be able to accept both. The question for a prover is: given this instance, does a stable mass assignment exist? If so, produce one. Complexity should be measured in the number of programs \(m\), the positive type support \(\tau=|S|+|K|\), the binary input length \(L\), and the encoded preference-list lengths.
A plausible regime is a large residency or fellowship placement market assembled from repeated applicant cohorts: many applicants share complete preference lists and program-priority classes, while couples share joint program-pair rankings. Such a market could have tens of thousands of doctors but only hundreds or thousands of distinct types. I am not claiming that current NRMP data has this structure; it is a plausible standardized placement regime. Mass-valued quotas and fractional type-level flows are co-modifications needed to express that market as a continuum. Each infinitesimal applicant still receives one program, and each infinitesimal couple one program pair.
I expect hardness to transfer provisionally. Couple pair options and program priorities still carry combinatorial structure in the program agenda and type support, not just in the number of copies. The paper’s introduction says SMP-C is NP-complete, citing Ronn (1990), but that is background rather than a numbered result of this paper and therefore is not a separate anchor here. Nor does the citation establish transfer: mass splitting might create stable flows where no discrete stable matching exists. A central follow-up is whether the continuum blocking conditions admit an efficient LP or separation formulation, or retain enough disjunctive structure to be hard; another is whether the discrete-to-continuous identity holds under specific restrictions.
The weakest point is the type regime. To be complete, types must include joint couple rankings and all program-relevant priorities; real applicants may have highly individual rank lists, making \(\tau\) close to the population size. That would weaken the high-multiplicity motivation. Still, where repeated complete profiles are credible, this mirror preserves the paper’s defining question and should be recognizable to its authors. The mirror covers the existence and construction of stable SMP-C matchings; it does not claim to mirror the paper’s solver-performance comparisons.
I would vote against the proposed anchor, but the negative case is weaker than the universal claim asks for.
The only named result the proponent relies on is Theorem 1. It proves that SAT-E correctly encodes stable matchings for a fixed finite instance with named doctors. That is an algorithmic-correctness result, but it gives no complexity bound. The NP-completeness claim appears in the introduction as prior work by Ronn, and the paper’s own solver comparisons are empirical. So Theorem 1 does not anchor a continuous complexity result in the sense ChoCo is meant to chart.
The strongest version of the proposed mirror is a rational-mass market with repeated doctor and couple types, type-level program priorities, and quotas scaled with population. That is coherent. But the paper’s programs strictly rank individual doctors. A doctor’s positions on those lists are part of the information that determines whether a deviation blocks; in the full type definition, those priorities generally distinguish one doctor from another. Keeping them leaves little type compression. Replacing them with priority classes makes a different, tie-based mass model. That could be a sensible new matching problem, but it is not what Theorem 1 establishes.
Nor does Theorem 1 supply the bridge to that model. Its one-to-one correspondence uses Boolean assignment variables for named doctors and exact-one constraints. A mass flow can split a type across program pairs, while a couple’s blocking condition depends on simultaneous acceptance by two programs. The paper proves no discrete-to-mass correspondence for those conditions. Establishing one—or defining and analyzing the mass version without one—would require new results.
That is the best objection to the anchor, not a proof that no worthwhile mirror exists. A standardized placement market with repeated preferences and type-level priorities is plausible, and the resulting stable-mass problem could be interesting. If an encoding-correctness theorem counts as sufficient computational anchoring, the proponent’s case may survive. I can make a credible case against green under the programme’s narrower complexity-result standard; I cannot honestly claim to have ruled out every worthwhile continuous mirror in every scenario.
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.