| paper | Unique stable matchings |
| authors | G. Gutin, Philip R. Neary, Anders Yeo |
| venue | GEB 2023 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 is a structural characterization, while the paper's polynomial-time deferred-acceptance observation is not a numbered computational result. The proposed continuous type-flow question is intelligible and close in subject, but its capacity-aware stability and normal-form theory are new, and the opponent's example shows that the theorem's singleton characterization does not transfer. Thus no result of this paper has both required properties.
fails bit a — no named computational result to mirror
The opponent's procedural objection is decisive: the only plausible anchor is not computational under the stated rule; independently, the proposed mass-flow model changes the structural theorem.
fatal: True
The proposed mirror covers uniqueness, IDUA normal-form pruning, and stable matching flows, but leaves the preservation lemmas, digraph exposition, and reverse-construction appendix without a qualifying computational analogue.
Strictly under the programme’s anchor rule, this paper has no qualifying computational anchor. It contains no numbered theorem asserting NP-hardness, membership in \( \mathrm{P} \), fixed-parameter tractability, or similar. The statement in the introduction that deferred acceptance gives a polynomial-time test is not itself a numbered result. So the positive case below is substantive but conditional on accepting a named structural theorem as an anchor.
The best anchor is Theorem 1, proved in this paper. It states that for a finite one-to-one matching market \(P\), with normal form \(P^\ast\) obtained by iterated deletion of unattractive alternatives, the following are equivalent:
Lemma 1, attributed to Balinski and Ratier (1997) but reproved here, supports the construction: IDUA does not change the set of stable matchings. I would use Lemma 1 as supporting evidence, not as a second computational anchor.
My mirror would be Continuous Unique Stable Type-Flow. Consider a large centralized labour market, such as annual resident placement or apprenticeship allocation. There are many individual workers and many one-position firms, but workers are grouped by training, region, eligibility, and preference template, while firms are grouped by specialty, location, and ranking template. A type contains every feature relevant to preferences and eligibility. A plausible regime has \(N\) agents but only \( |I|+|J|=\tau \) worker and firm types, with \(N\gg\tau\).
Let \(I\) be worker types and \(J\) firm types. The input gives rational masses \(\mu_i\) and \(\nu_j\), with \( \sum_{i\in I}\mu_i=\sum_{j\in J}\nu_j=1 \), together with strict preferences \( \succ_i^W \) of each worker type over firm types and \( \succ_j^F \) of each firm type over worker types. The mass \(x_{ij}\) assigned between \(i\) and \(j\) is the decision variable, subject to
\(x_{ij}\ge 0\), \( \sum_j x_{ij}=\mu_i \), and \( \sum_i x_{ij}=\nu_j \).
This is not fractionalizing an individual’s outcome: every unit of population mass receives one integral match in the underlying market. The matrix \(x\) records only the aggregate flow between indistinguishable types.
For a candidate flow \(x\), define
\(B_W(i,j;x)=\sum_{j':\,j\succ_i^W j'}x_{ij'}\),
the mass of type-\(i\) workers assigned below firm type \(j\), and
\(B_F(j,i;x)=\sum_{i':\,i\succ_j^F i'}x_{i'j}\),
the mass of type-\(j\) firms assigned below worker type \(i\). The flow is stable if, for every \(i,j\), at least one of \(B_W(i,j;x)\) and \(B_F(j,i;x)\) is zero. Otherwise positive mass on both sides could leave worse assignments and form a blocking match.
The computational problem is:
Given \(I,J,\mu,\nu\) and the two collections of type preferences, determine whether there is exactly one stable type-flow \(x\). If yes, output it; if no, output two distinct stable flows \(x\neq y\).
Uniqueness is understood up to measure-preserving relabelling of agents within a type. That is the appropriate high-multiplicity notion: distinguishing two residents who have identical preferences and all other relevant attributes would manufacture artificial non-uniqueness.
I would expect this problem to be Class A. A mass-deferred-acceptance algorithm can let worker-type mass propose down its preference lists, while each firm type retains up to capacity \(\nu_j\) from the most preferred arriving worker mass. Running the process from both sides should produce worker-optimal and firm-optimal stable type-flows. The continuous market has a unique stable flow exactly when these two extreme flows coincide. The number of proposal events depends on the number of type pairs, not on \(N\), so this is precisely where a high-multiplicity relaxation could replace an enormous discrete market by a polynomial-size computation.
The deeper structural question directly mirrors Theorem 1: define a capacity-aware version of IDUA on the type-pair graph, repeatedly deleting type pairs that cannot occur in any stable flow under the current residual capacities. Does the resulting continuous normal form have a unique stable flow exactly when its preference digraph is acyclic, equivalently when every surviving type has a singleton list? The finite theorem makes this a sharply motivated conjecture rather than an arbitrary new problem.
The mirror is plausible because it preserves the paper’s actual subject: two-sided preferences, blocking pairs, stable matchings, uniqueness, and normal-form pruning. The paper itself discusses extensions to unbalanced and many-to-one markets, so replacing many identical one-position firms by a firm-type mass is a natural high-multiplicity extension. It is not merely a divisible-outcome problem.
The weakest point is substantial. Theorem 1 assumes named agents, strict preferences over named counterparts, and unit capacities. Type aggregation introduces exchangeability within types, capacities, and possibly ties between counterpart identities. The acyclicity/singleton characterization may therefore require a new mass-sensitive theorem and may even fail for arbitrary masses. Also, if the grader insists that only numbered complexity results count as anchors, this paper cannot support a compliant positive case: its computational discussion is informal, while Theorem 1 is structural. Nevertheless, the continuous unique-stable-flow problem itself is a credible high-multiplicity mirror, with a clear expected tractability route and several nontrivial questions about when the paper’s normal-form theorem survives continuization.
The decisive objection is procedural: this paper has no qualifying computational anchor. Theorem 1 is a structural characterization, not a complexity, algorithmic, approximation, or parameterized result. Lemma 1 is a preservation lemma, attributed to Balinski and Ratier, and likewise says nothing computational. The only claim that deferred acceptance tests uniqueness in polynomial time appears as informal discussion, not as a named result proved here. Under the programme’s anchor rule, the proposed mirror therefore fails before its modelling merits are considered.
Even if Theorem 1 is admitted as a conditional anchor, its content does not continuize in the form proposed. The finite theorem relies on named agents, unit capacities, and the fact that every surviving pair in an acyclic normal form is part of one perfect matching. A population flow has capacities and can split one type across several counterpart types. Consequently, the paper’s decisive equivalence—uniqueness if and only if every surviving list is a singleton—fails at the type level.
For example, take worker types \(a,b\) of masses \(0.9,0.1\), and firm types \(A,B\) of masses \(0.9,0.1\), with preferences
\[ B\succ_a A,\qquad A\succ_b B, \]
\[ a\succ_A b,\qquad b\succ_B a. \]
The type preference graph contains the usual four-cycle. Writing \(x=x_{aA}\), feasibility gives
\[ x_{aB}=0.9-x,\qquad x_{bA}=0.9-x,\qquad x_{bB}=x-0.8, \]
with \(0.8\le x\le0.9\). Stability forces \(x_{bB}=0\), hence \(x=0.8\): the stable type-flow is unique. Yet that unique flow assigns type \(a\) partly to both \(A\) and \(B\), and type \(A\) partly to both \(a\) and \(b\). Its support is not a collection of singleton type lists. Thus cycles no longer characterize non-uniqueness, even in a tiny rational high-multiplicity instance.
One can certainly invent a capacity-sensitive normal form that handles this example. But then the result is a new theory of capacitated stable flows, not a continuization of the paper’s normal-form theorem. The proposed mass-deferred-acceptance algorithm is also only a conjectural route until one fixes the treatment of within-type ties, fractional blocking, and the relation between stable flows and strict individual matchings.
The strict-preference issue reinforces this divide. Retaining the paper’s preferences over named counterparts requires types to encode identity-level tie-breaking, undermining a small type space. Quotienting counterpart identities produces ties over types and changes the solution concept to a stable-allocation or stable-flow model. That may be a sensible research problem, but it is a co-designed new model rather than the paper’s computational result in continuous form.
I would not claim that no worthwhile continuous matching problem exists here. Large repeated-type labour markets are plausible, and a stable-flow study could be valuable. But the strongest honest negative verdict is that this paper supplies no eligible computational anchor, while its central structural theorem does not survive the proposed continuization. The resulting project would be new continuous matching theory, not a ChoCo mirror of this paper.
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.