| paper | d4-journals-geb-2024-0083 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Constrained stable-mass feasibility is in \(\mathrm P\). A complete description by distinct nonempty rational polyhedra can be computed in total time \((s+1)\operatorname{poly}(m,\tau,L)\), where \(s\) is the number output; the description may include contained faces. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite worker types \(W\) and position types \(F\), rational type masses and capacities, shared strict rankings over mutually acceptable types, and type-level assignment constraints, compute a finite union of rational polyhedra describing all stable mass assignments. Each assignment is a matrix \(x\ge 0\) with row and column sums bounded by the corresponding masses and capacities; forbidden pairs require \(x_{ij}=0\), while an in-constraint requires the whole specified type mass to be assigned within its permitted set. For each acceptable pair \((i,j)\), stability requires that either \(a_i-\sum_k x_{ik}+\sum_{k:\,j\succ_i k}x_{ik}=0\) or \(b_j-\sum_h x_{hj}+\sum_{h:\,i\succ_j h}x_{hj}=0\). Can this description be computed in time polynomial in the input encoding size plus polynomial work per output polyhedron?
Use a continuum of worker types and position types with rational masses and capacities. A nonnegative flow \(x_{ij}\) assigns mass between types; unmatched worker mass and vacant capacity remain possible. Shared type rankings define stability: for every acceptable pair, at least one side has zero mass that would prefer that pair. Cohort-level in/out constraints restrict the flow, and the requested output is a polyhedral description of all qualifying stable flows.
The stable-flow set may require exponentially many disjunctive polyhedra, and no output-sensitive algorithm is established; the proponent frames this as an open conjecture, so it limits the expected tractability rather than the mirror’s plausibility.
fatal: False
Mirrors Theorem 1’s feasibility and enumeration of constrained stable matchings; leaves the IDUA normal-form lemmas and other structural results untouched.
The strongest anchor is Theorem 1, proved in this paper (with some structural lemmas drawn from earlier work). It says that, given a one-to-one matching market and disjoint sets \(C^{in}\) and \(C^{out}\) of worker–firm pairs, Algorithm 1 correctly finds every stable matching containing all pairs in \(C^{in}\) and none in \(C^{out}\). If \(N\) is the larger side of the market and \(s\) is the number of qualifying stable matchings, its running time is \(O(N^3+N^3s)\), with \(O(N^3)\) time between consecutive outputs. The paper has no comparable named hardness result for this problem, so this is the appropriate algorithmic anchor.
A plausible high-multiplicity setting is a large, centralized residency or graduate-placement market. Workers can share a type defined by specialty, credentials, location, and their ranking of program categories; positions can share a type defined by program category, capacity, and priority ranking over worker types. A single annual cohort might contain tens of thousands of applicants and positions but only hundreds of such types. The market designer’s restrictions can then concern cohorts: for example, all members of a specialty group must be placed within a designated set of regions, or no members may be placed in a particular program category. That is a natural population-scale version of the paper’s “in” and “out” assignment constraints.
Here is the mirror I would put to a prover: Constrained Stable Mass Matching, \(\mathrm{CSMM}_{\infty}\). An instance has finite worker-type and position-type sets \(W\) and \(F\), with rational masses \(a_i\) and \(b_j\); each type has a strict ranking of acceptable opposite-side types, and an acceptable pair must be acceptable on both sides. A matching is a nonnegative matrix \(x=(x_{ij})\), where \(x_{ij}\) is the mass of type \(i\) assigned to type \(j\), subject to \(\sum_jx_{ij}\le a_i\) and \(\sum_ix_{ij}\le b_j\). Any unmatched mass remains unmatched.
For each worker type \(i\), an “in” restriction may specify a set \(A_i\subseteq F\) and require \(\sum_{j\in A_i}x_{ij}=a_i\): the whole cohort must be assigned within that set. A firm-side “in” restriction for position type \(j\) similarly specifies \(B_j\subseteq W\) and requires \(\sum_{i\in B_j}x_{ij}=b_j\). An “out” restriction on a type pair requires \(x_{ij}=0\). These are exactly cohort-level versions of the paper’s assignment restrictions.
Stability has a direct mass interpretation. Let \(U_i=a_i-\sum_jx_{ij}\) be unmatched worker mass and \(V_j=b_j-\sum_ix_{ij}\) be vacant position mass. For an acceptable pair \((i,j)\), the mass of type \(i\) that wants \(j\) is \(U_i+\sum_{j':\,j\succ_i j'}x_{ij'}\); the mass of type \(j\) that wants \(i\) is \(V_j+\sum_{i':\,i\succ_j i'}x_{i'j}\). The allocation is stable exactly when, for every acceptable pair, at least one of these two quantities is zero. Otherwise positive masses on both sides would prefer to form that pair, so it blocks. A solution is a stable matrix satisfying the assignment restrictions. There is no welfare objective in this problem: like the paper, it asks whether compatible stable assignments exist and, if so, what they are.
Because the set of stable matrices can contain continua, “find all” needs a continuous output format. For each acceptable pair, stability is the disjunction that one of the two quantities above is zero. Choosing a side of that disjunction for each pair yields a rational polyhedron; the union of the nonempty polyhedra, intersected with the assignment restrictions, describes exactly all qualifying stable mass assignments. The computational question is whether this set can be computed in time polynomial in the number of types, the number of acceptable type pairs, and the input bit length, plus polynomial work per output polyhedron. This is the continuous counterpart of Theorem 1’s output-sensitive enumeration bound. I would expect a Class A result for this direct analogue, though that expectation is a research conjecture, not a consequence of Theorem 1.
This mirror keeps the population as the continuous object: each unit of mass still receives an integral assignment, while \(x_{ij}\) can be fractional because it records the aggregate share assigned across a type pair. It also admits a clear high-multiplicity bridge. Replicate each type according to integer masses obtained by clearing denominators. A stable matching of the replicated finite market gives a grid-valued stable matrix, and such a grid-valued matrix can be expanded into a matching of the replicas. The continuous problem additionally admits non-grid mass allocations. So the mirror asks whether the paper’s structural method extends from enumerating individual stable matchings to describing the full set of stable type-level allocations.
My weakest point is the change from strict rankings of named individuals to rankings of types, with agents within a type treated as interchangeable. That requires type-level preferences or priorities, and cohort-wide constraints; it does not represent a designer who targets one named applicant. If real tie-breaking or individual exceptions are essential, the types may need to be split until their preferences agree, potentially eliminating the small-support regime. The proposed market avoids that problem only where categories and priorities are genuinely shared. In such a regime, the paper’s central question—whether assignment requirements can coexist with stability—remains recognizable, and the mass version is a substantive extension rather than a change of topic.
The strongest objection is that Theorem 1’s output is a set of assignments between named people. Its constraints specify particular worker–firm pairs, and its bound is polynomial time per qualifying matching. Aggregating workers and positions into types changes both objects: a solution becomes a mass-flow matrix, and one flow may stand for many named matchings. So the theorem’s \(O(N^3)\)-delay result does not carry over just by replacing counts with masses. The proposed “enumerate all stable flows” version also needs a chosen representation: stability is a disjunction for each type pair, and expanding those disjunctions gives a union of polyhedra, potentially with exponentially many pieces. That is a substantial new computational problem, not an extension already delivered by the paper.
This objection does not defeat the better mirror. In a large placement market, workers can share specialty, credentials, and rankings over program categories; positions can share capacities and priorities over those worker types. Cohort-level requirements such as “all of this type must be placed within these regions” or “none may go to this program category” are recognizable versions of the paper’s assignment constraints. With rational masses and capacities that scale with the market, the proposed stability condition—no acceptable type pair has positive mass on both sides wanting to match—is a coherent population-level question. It continuizes the population, and the authors could reasonably recognize it as their problem.
The type model does require care. If real firms rank members of a cohort differently, those distinctions belong in the type description; otherwise the model needs shared priorities, possibly with ties. That can weaken the small-support regime in some applications. It does not rule out markets where priorities genuinely operate by category. Nor does the shift from individual constraints to cohort constraints settle the issue: the paper’s own framework already allows constraints on sets of workers and positions, and cohort restrictions are a plausible mass version.
So the negative case can show that Theorem 1’s algorithmic guarantee is not itself the continuous result. It cannot honestly show that no worthwhile mirror exists. The paper has a named computational anchor, and the proposed mass-matching question remains well posed in a plausible high-multiplicity regime. My case against the mirror is weak at that universal claim; the sound caution is to present it as a new aggregate stability problem, not as a direct continuization of the paper’s enumeration algorithm.
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.