| paper | d4-journals-mss-2022-0037 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: No polynomial total-time algorithm exists for the requested explicit output: some instances require at least \(2^{m/7}=2^{\tau/6}\) polyhedra. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite sets of worker types \(A\) and employer types \(B\), rational masses \(\mu_a,\nu_b\), and strict rankings of acceptable opposite-side types, compute an exact finite union of rational polyhedra describing all stable mass matrices \(x\). Each matrix must satisfy \(x_{ab}\ge 0\), \(\sum_b x_{ab}\le\mu_a\), and \(\sum_a x_{ab}\le\nu_b\); for every mutually acceptable pair, stability requires \(r_{ab}(x)s_{ab}(x)=0\), where \(r_{ab}(x)\) and \(s_{ab}(x)\) are the masses on each side unmatched or matched to a less-preferred type.
A one-to-one mass matching between worker types \(a\in A\) and employer types \(b\in B\), with rational type masses, shared strict rankings, and a mass matrix \(x_{ab}\). Individuals still receive at most one match, while each type’s mass can split across counterpart types; a pair blocks when both types have positive mass unmatched or matched below one another.
Aggregating cloned markets may not yield the residual-mass blocking notion, because tie-breaking among clones can affect finite stable outcomes; the case flags this bridge but does not settle it.
fatal: False
The mirror covers Theorem 2’s full-stable-set computation for one-to-one markets with finitely many worker and employer types. It leaves aside the broader many-to-many preference model and does not transfer the paper’s cycle algorithm or establish a complexity bound for the mass problem.
My lead mirror is a type-based, one-to-one labor market. It is a deliberate restriction to a subcase the paper includes; I would not claim it captures the paper’s full many-to-many model.
The anchor is Theorem 2, proved in this paper. Under substitutable preferences satisfying the law of aggregate demand, it says the authors’ algorithm computes the entire stable set \(S(P)\): deferred acceptance finds the firm-optimal and worker-optimal stable matchings; the algorithm then repeatedly reduces preferences, finds cycles, and adds their cyclic matchings until it reaches the worker-optimal matching. The theorem asserts that the firm-optimal matching and all cyclic matchings found this way are exactly the stable matchings. This is an algorithmic correctness result, not a complexity classification. The paper’s polynomial-time claim with a choice oracle appears in an unnumbered concluding remark, so it is not my anchor.
Full Stable Mass Matching (FSMM) is the continuous problem I would give a prover. An instance has finite sets \(A\) and \(B\) of worker and employer-slot types, rational masses \(\mu_a,\nu_b\), and each type’s strict ranking of acceptable opposite-side types. A type is complete for this model: its members share the same ranking. A solution is a mass matrix \(x_{ab}\), where each unit of mass receives at most one match:
\[ x_{ab}\ge 0,\qquad \sum_b x_{ab}\le \mu_a,\qquad \sum_a x_{ab}\le \nu_b. \]
Unmatched mass is allowed. For a mutually acceptable pair \((a,b)\), define
\[ r_{ab}(x)=\mu_a-\sum_{b':\,b'\succeq_a b}x_{ab'}, \qquad s_{ab}(x)=\nu_b-\sum_{a':\,a'\succeq_b a}x_{a'b}. \]
These are the masses of type \(a\) workers and type \(b\) employers who are unmatched or currently matched below the other type. The mass matching is stable exactly when
\[ r_{ab}(x)s_{ab}(x)=0 \]
for every mutually acceptable pair: a positive mass on both sides would contain agents who could form a blocking pair.
The computational question is to return an exact finite union of rational polyhedra whose union is the set of all such stable mass matrices. A valid output must describe the whole set, not just one stable allocation. The instance is measured by \(|A|,|B|\), the preference-list size, and the mass bit length \(L\); the output size also matters. This is genuinely about a continuous population: each person still gets an integral one-to-one match, while a type’s aggregate mass can split across outcomes. It is not a lottery over one finite market.
The regime is a large centralized placement market: many applicants and slots, but relatively few complete preference types, perhaps grouped by qualification, geography, and shared ranking. Then population size \(N\) can greatly exceed the number of types \(\tau\). The paper itself discusses medical-intern markets and returns to the one-to-one case in Example 2, so the underlying stability question should be recognizable to its authors. The type-based preference lists are a co-modification needed to make that regime a finite-input problem.
I expect this restricted FSMM problem to be Class A, if its full stable set has a compact polyhedral description. The lattice and cycle structure in Theorem 2 make that a credible direction: a mass-level representation might describe a continuum of stable allocations without enumerating each allocation separately. That is a conjecture for the mirror, not a tractability result established by Theorem 2. Natural follow-up questions are whether \(\mathcal S_\infty\) is always convex, whether it has a polynomial-size exact description, and whether a cycle-based characterization extends to responsive many-to-many types. A bridge question is whether rational type masses correspond to normalized aggregates of stable matchings in finite clone markets.
My weakest point is that Theorem 2 computes a set of matchings between named agents, while FSMM compresses identities into preference types. Even though that is the intended high-multiplicity move, strict preferences over named counterparts may carry structure that type-level rankings erase. And the anchor proves correctness of an enumeration algorithm; it does not show that a compact continuous description exists. That limits the strength of the tractability case, but the continuous full-set question remains a plausible analogue of what the paper computes.
The strongest objection is that Theorem 2’s computational object does not carry over as directly as the proposed case suggests. The theorem computes the full set of matchings among named agents with strict preferences over partners. FSMM instead gives each preference type a mass that can split across matches and declares a pair blocking when both sides have positive residual mass. That is a coherent continuum stability notion, but it is not simply the paper’s stable set with names erased: cloning types into finite markets requires handling indifference among same-type agents, and tie-breaking can affect which finite stable matchings aggregate to which mass assignments. So the cycle algorithm does not itself give a route to FSMM.
There is also a problem with FSMM’s proposed computational target. For each acceptable type pair, \(r_{ab}(x)s_{ab}(x)=0\) is the disjunction \(r_{ab}(x)=0\) or \(s_{ab}(x)=0\). With \(q\) such pairs, one can mechanically expand the constraints into at most \(2^q\) rational polyhedra. That gives an exact representation, but says little about whether the representation can be made compact or whether the paper’s cycle structure survives. The proponent’s stronger follow-up—find a polynomial-size description—would be a more substantive problem, but it needs a precise target and cannot be inferred from Theorem 2.
The one-to-one subcase is also close to established polyhedral work. Vande Vate described the convex hull of stable marriages and showed how to optimize over it by linear programming; later work studies fractional points in that polytope as lotteries or time-sharing arrangements ([Vande Vate, “Linear programming brings marital bliss”](https://www.sciencedirect.com/science/article/pii/0167637789900412), [Roth, Rothblum and Vande Vate](https://pubsonline.informs.org/doi/10.1287/moor.18.4.803)). That does not settle FSMM: a lottery over finite stable matchings is not the same as simultaneous positive masses in an atomless market, and the polytope’s points need not satisfy the proposed residual-mass blocking condition. It does mean that a one-to-one mirror would need to say exactly what its population formulation adds. Meanwhile, existing continuum matching work often models a finite set of schools and a continuum of students, characterizing stable outcomes through supply and demand; that is useful context, but it does not compute the full stable set for two type-based mass populations ([Azevedo and Leshno](https://www.journals.uchicago.edu/doi/pdf/10.1086/687476?download=true)).
The paper does provide a named computational result: Theorem 2 proves that its algorithm returns the full stable set. But the paper’s ordinary-input complexity contribution is limited: it says choice-function evaluation can be exponential, and gives polynomial time only under an artificial choice oracle. That makes the bridge to the programme’s complexity questions less ready-made than the proponent suggests.
I would argue against treating this as an established Class A opportunity: the full-set mass problem is a real change of stability model, and the stated polyhedral output has an immediate exponential construction. But I cannot honestly make the universal case that no worthwhile mirror exists. A high-multiplicity placement market with a small number of complete preference types is plausible, and FSMM asks a well-posed computational question about it. The objections weaken the claimed connection to the paper’s cycle algorithm; they do not defeat that mirror.
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.