| paper | d4-journals-mss-2023-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1 (Paths to stability result)
statement extracted from the paper’s text layer
Given couple types \(C\) with rational masses \(b_c\), hospital-slot types \(G\) with rational capacities \(q_g\), restricted-complementarity preferences, and an initial rational allocation \(x^0\), can one compute in time polynomial in the type support \(\tau\), input bit length \(L\), and explicit preference-list size a finite sequence of exact rational allocations from \(x^0\) to stability? Each allocation assigns mass of each couple type to ordered pairs of slot types or the outside option \(u\); each step moves positive mass from an assigned pair to a strictly preferred pair that the receiving slots can accept, displacing lower-priority incumbents as in the paper. Stability means there is no such positive-mass blocking move.
Represent each couple type by its two doctor profiles and strict ranking over feasible ordered pairs of hospital-slot types and \(u\); represent each hospital-slot type by a common strict priority ranking over doctor profiles and a rational mass of one-position slots. An allocation is a rational flow \(x_{c,p}\) over couple types and assigned pairs, with \(\sum_p x_{c,p}=b_c\) and slot-type occupancy at most \(q_g\). A blocking move transfers a positive rational mass of a couple type from a pair to a strictly preferred pair; the receiving slots use vacancies or displace lower-priority incumbents, whose doctors become unmatched as in the paper.
It mirrors Theorem 1’s path guarantee and stable endpoint, including the stable-existence implication of Proposition 1; it leaves the preference-equivalence result in Lemma 1 and the almost-sure random-path claim in Corollary 1 open.
The strongest anchor is Theorem 1 (Paths to stability result), proved in this paper. It says that for any finite matching-with-couples problem in which every couple’s preferences satisfy restricted complementarity, and from any initial matching, there is a finite sequence of matchings ending in a stable matching, where every step satisfies a blocking coalition from the previous matching. The authors prove it here using their PS-algorithm; they adapt an earlier algorithm of Klaus and Klijn. The paper does not give a named NP-hardness or complexity-class result, and Theorem 1 gives no polynomial running-time bound. It is a constructive algorithmic anchor, not an established P-versus-hardness result.
A plausible high-multiplicity regime is a large centralized residency match with many physician couples. A couple’s type records both spouses’ doctor profiles and their complete ranking over feasible hospital pairs. A hospital-slot type records its priority ordering over doctor profiles. Many couples could share rank-list templates, and many positions could share priority orderings: for example, tens of thousands of couples and positions but hundreds of distinct types. This is a constructed cohort scenario, not a claim that the NRMP already has only a few types. As in the paper’s Remark 2, single doctors could be represented by fictitious partners.
Here is the mirror I would hand to a prover: Mass Paths to Stability under Restricted Complementarity (MPtS-RC). An instance has finitely many couple types \(c\), each with rational mass \(b_c\), and finitely many hospital-slot types \(g\), each with rational capacity \(q_g\). A slot has one position; multiple slots may share a type. Couple types have strict rankings over feasible ordered pairs of slot types and the outside option \(u\), and hospital types rank doctor profiles and vacancy. Preferences satisfy the paper’s restricted-complementarity condition on these type-level options. Types are complete for the model: agents in a couple type share the same doctor profiles and full pair ranking, while slots in a hospital type share the same priorities. Slots may be indifferent among indistinguishable doctors of the same profile.
A feasible mass allocation is a nonnegative flow \(x_{c,p}\), where \(p\) is the ordered pair assigned to type \(c\), including pairs with \(u\). It satisfies \(\sum_p x_{c,p}=b_c\) for each couple type, and the total mass assigned to each slot type does not exceed its capacity. A pair using the same slot type twice consumes two distinct slots. Given an initial rational allocation \(x^0\), the task is to output a finite sequence \(x^0,x^1,\ldots,x^k\). Each step must move some positive rational mass of a couple type to a strictly preferred pair through a blocking coalition: the receiving slots accept those spouses relative to their incumbents, any displaced doctors become unmatched as in the paper’s definition, and all capacity constraints remain satisfied. The sequence must end at an allocation with no positive-mass blocking coalition. Fractional type-level flows are allowed, while each individual couple still receives an integral pair of jobs. The solution is the path itself, not a welfare-maximizing allocation.
I would tentatively expect an A-style tractability result for finding a stable mass allocation when the type support is finite: after aggregation, there are finitely many couple and slot types, and acceptance depends on finite priority orderings. But the stronger finite-path claim is the real test. The paper’s finiteness argument uses progress among discrete agents; in a mass model, a sequence could conceivably keep making smaller positive moves. So the key question is whether an aggregate PS-style procedure can guarantee a finite path, not merely convergence to a stable allocation. The natural follow-ups are a running-time bound in the number of types and input bit length, whether an asynchronous random blocking process converges almost surely, and how stable mass allocations relate to stable matchings in large replicated finite markets.
The weakest point is the type regime: complete couple rankings over hospital pairs may be highly diverse, so the number of distinct types could grow nearly as fast as the population in real markets. And the paper’s theorem establishes finite convergence, not a complexity bound. Those are real limits, but they do not make the mirror a change of subject: population mass is the object being continuized, hospitals still have capacity, couples still choose pairs, and the endpoint is stability under the same blocking-coalition idea.
The strongest argument against is that Theorem 1 is a finite-path result, not a complexity result. Its proof gives no running-time bound, and its termination argument counts individual couples and hospitals. That does not support the proponent’s tentative A-style claim for an algorithm polynomial in the number of types and input bit length.
There is a useful way to expose the gap. For rational masses and capacities, clear denominators and represent the instance as a finite replicated market. The paper’s algorithm then gives a finite path, which can be projected back to mass allocations. But the replication factor can be exponential in the input bit length. In a genuinely aggregate proof, the paper’s potential would become weighted by mass moved; a step could improve it by an arbitrarily small amount, so the existing finiteness argument would no longer establish a finite path. A worthwhile computational question would need to ask whether one can find a stable allocation, or a compressed finite path, in time polynomial in the type support and bit length. The proposed mirror has not yet specified that target or fully formalized how a blocking move selects and displaces submass.
That is a real weakness in the case *for* a tractability result, but it does not defeat the anchor. A large market with repeated couple preference templates and hospital priority types is a sensible high-multiplicity regime; capacities can scale with the population, and an aggregate assignment can retain couples’ paired outcomes. The resulting algorithmic question is not answered by the paper’s finite-agent theorem or by analytic continuum work. So I can argue against treating Theorem 1 as evidence that the mirror will be tractable, but I cannot honestly argue that no worthwhile continuous mirror exists. The sole anchor survives as a credible computational question, though its strongest version still needs to be stated.
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.