| paper | Stable Matchings in Practice: A Constraint Programming Approach |
| authors | — |
| venue | AAAI 2024 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
Given finitely many family types with rational masses, at most two children per type, complete grade and initial-enrollment data, preference lists of length at most two, daycare transferable quotas normalized as masses, and threshold δ>0, does there exist a mass assignment of each type to integral preference-list tuples satisfying all quota and individual-rationality constraints in which at least δ total family mass receives an assignment different from its initial tuple?
A high-multiplicity daycare market with complete family types, rational population masses, integral tuple assignments per family, mass variables y(type, tuple), normalized transferable-quota constraints, individual-rationality constraints, and changed-mass objective.
The fixed positive threshold replaces the paper's existential one-family witness with an aggregate welfare threshold, and the case does not supply a formal finite-to-continuous rounding theorem preserving the original predicate.
fatal: False
The mirror directly covers Theorems 1 and 2; it does not cover the stability characterization in Theorem 3, the CP algorithm, or the empirical comparisons.
There is a credible continuous mirror here. My strongest anchor is Theorem 1.
The paper’s Theorem 1, proved in this paper by a reduction from the cited NP-complete SUBSET SUM problem, says that it is NP-complete to decide whether there is a feasible, individually rational outcome different from the initial matching, even when every family has at most two children and every family preference list has length at most two.
The natural high-multiplicity regime is a large annual daycare or school-choice clearinghouse: perhaps \(10^5\)–\(10^6\) families, but only \(10^2\)–\(10^4\) recurring family profiles. A profile records the complete information relevant to this problem: number and grades of the children, initial daycare tuple, joint preference list over daycare tuples, and any other attribute used by feasibility or individual rationality. Families with the same profile are genuinely interchangeable. This is plausible in a large metropolitan or pooled municipal market where applications are generated from standardized priority categories and geographically repeated preference patterns. The paper’s 550–1589-child experiments are not themselves a continuum regime, but the same model naturally applies to a much larger repeated-profile market.
The continuous problem I would call \(\mathrm{HM\mbox{-}IR\mbox{-}Change}_\infty(\delta)\), and this is my lead mirror.
An instance contains:
The decision variable is \(y_{a,r}\), the mass of type-\(a\) families assigned to tuple \(r\in R_a\). It must satisfy
\[ \sum_{r\in R_a}y_{a,r}=\mu_a, \]
the transferable-quota inequalities, and individual rationality:
\[ y_{a,r}=0\quad\text{whenever }r\prec_a\omega_a. \]
The question is whether there is such a \(y\) with
\[ \sum_{a}\sum_{r\ne\omega_a}y_{a,r}\ge\delta. \]
A solution is the mass assignment \(y\). The unthresholded version asks whether the maximum changed mass is positive; \(\delta\) is the scale-correct analogue of “at least one family” in a finite market.
This is a genuine population continuization. An individual family is still assigned an integral tuple such as \((d_1,d_2)\); \(y_{a,r}=0.37\) means that 37% of the indistinguishable families of type \(a\) receive that tuple. It is not a fractional daycare slot or a lottery over outcomes for one named family.
I expect \(\mathrm{HM\mbox{-}IR\mbox{-}Change}_\infty(\delta)\) to be in Class A. It is a rational linear program with one variable per type–assignment pair and linear quota constraints. The SUBSET SUM reduction behind Theorem 1 relies on selecting indivisible families. Once mass can be split, the subset choice becomes a continuous variable and the obstruction disappears. The restriction to two children and preference lists of length two also ensures that the assignment domain is explicitly polynomial-sized.
The second worthwhile anchor is Theorem 2, also proved in this paper. It says that checking whether a feasible and individually rational matching is Pareto optimal is co-NP-complete, under exactly the same restrictions. The proof derives this from Theorem 1; it is not merely a cited result.
Its continuous counterpart is \(\mathrm{HM\mbox{-}Pareto\mbox{-}Optimality}_\infty(\delta)\). The instance additionally gives a feasible, individually rational baseline mass assignment \(b_{a,r}\). We ask whether there is another feasible assignment \(z\) and a coupling \(\pi_{a,r,r'}\) such that:
\[ \sum_{r'}\pi_{a,r,r'}=b_{a,r},\qquad \sum_r\pi_{a,r,r'}=z_{a,r'}, \]
every moved unit is weakly preferred to its baseline assignment,
\[ \pi_{a,r,r'}>0\implies r'\succeq_a r, \]
and at least \(\delta\) mass is strictly improved:
\[ \sum_{a,r,r':\,r'\succ_a r}\pi_{a,r,r'}\ge\delta. \]
The baseline is \(\delta\)-Pareto optimal if no such witness exists. For ordinary continuum Pareto optimality, replace the threshold by the condition that the maximum strictly improved mass is positive.
This problem also appears to be Class A: maximize strictly improved mass subject to the feasibility and coupling constraints. It is again a rational LP, with polynomially many variables under the theorem’s two-assignment restriction. The co-NP-hardness in Theorem 2 is therefore expected to dissolve for the same reason as Theorem 1: the reduction encodes indivisible subset selection, not combinatorics intrinsic to the daycare alternatives or joint assignments.
The authors should recognize both mirrors as their problem. They retain families, siblings, joint preferences over tuples, initial enrollments, individual rationality, and transferable grade-group quotas. The only substantive change is exactly the high-multiplicity change: repeated families of one complete type are represented by mass. I am deliberately not claiming that the paper’s full stability problem becomes easy. Theorem 1 and Theorem 2 do not use daycare priorities or blocking coalitions, so those features need not be weakened or reinterpreted for these anchors.
The further questions are interesting: can maximum matched mass be optimized simultaneously with Pareto improvement? Can a stable or almost-stable continuous matching be solved by an aggregate choice-function oracle? Can rational continuous solutions be rounded to large finite markets with controlled loss? Those would test where the tractability boundary lies.
The weakest point is that “differs from the initial matching” becomes dangerously weak in an atomless model: an arbitrarily small positive mass may move. That is why the threshold \(\delta\) is important. A referee who insists on the literal one-family predicate may reasonably say that the continuum has changed the question. My answer is that a fixed positive mass threshold is the honest high-multiplicity analogue, while preserving the paper’s exact feasibility and preference structure. I would not extend this positive claim to the paper’s stability result without separately resolving the identity-sensitive priority and blocking-coalition issues.
The strongest case against is that both anchors lose the computational object that made them results in the paper. I would not argue that repeated daycare profiles are impossible: a large pooled municipal market could plausibly have many families sharing a complete profile. Nor can I object merely because the continuous relaxation becomes an LP; that would be exactly the kind of Class A result ChoCo seeks.
The problem is more basic. Theorem 1 asks whether there is a matching differing from the initial one by at least one indivisible family. Its reduction works through the integral choice of which family-level assignment blocks are selected. In the proposed model, a type’s mass can be split between its two assignments. That does not represent the same witness at higher resolution: it permits a fraction of every candidate family block to move, thereby removing the all-or-nothing structure of the theorem.
The threshold \(\delta\) does not repair this. A fixed \(\delta\) asks a new policy question—whether at least a specified fraction of the population can be improved. That may be sensible, but it is not the continuous form of “some family can move.” Setting \(\delta=1/n\), the finite-market scale, still permits fractions of a type’s mass to be rearranged and can therefore produce a positive witness where no integral family assignment exists. Requiring an entire type mass to move together would restore the subset-selection semantics, but that is precisely an integrality or block-indivisibility constraint, not an atomless population model.
The natural replacement, maximizing changed mass, is mathematically legitimate but becomes a generic capacitated assignment problem. It no longer mirrors the named NP-complete predicate; it replaces an atomic existence question with a cardinal aggregate objective. That distinction matters especially for the programme’s discrete–continuous bridge: the finite signal in Theorem 1 is only \(1/n\) mass, so any ordinary additive rounding guarantee can swamp the very phenomenon being decided. A constant-mass version may be useful, but it is a new optimization problem rather than a faithful continuization of the theorem.
Theorem 2 does not provide an independent escape. In the paper’s proof, the baseline is the initial matching. By individual rationality, any feasible matching different from that baseline makes every family weakly better and at least one family strictly better. Thus the co-NP result is simply Theorem 1 restated as Pareto optimality. Its proposed continuous counterpart inherits exactly the same atomicity problem.
The coupling formulation for an arbitrary baseline is a sound aggregate Pareto model, but it moves further away from the paper’s result. It asks whether a positive mass can be weakly improved, which is a standard monotone-flow or transportation question. The coupling correctly preserves sibling assignments and joint preferences, but it does not preserve the finite predicate “there exists one strictly improved family.” Again, a positive threshold produces a reasonable new welfare problem, not a continuous version of the co-NP-complete theorem.
A more ambitious rescue would continuize the paper’s actual stable-matching objective: maximize matched-child mass while minimizing blocking coalitions. That is more interesting, but it is no longer a repair of either anchor. Stability in the paper depends on each daycare’s strict priority ordering over named children. In an atomless model, one family has measure zero, so whether it can form a blocking coalition requires an additional convention about positive-mass deviations and about how priority rankings become a score or priority distribution. Those choices may lead to a worthwhile large-market matching theory, but they define a new model rather than a mirror of Theorems 1 or 2. If priorities are omitted, one is left with the deliberately stripped feasibility problem used only inside the reductions.
So the negative case is not that the proponent’s LP is invalid. It is that the only credible LPs cease to ask the paper’s computational questions, while preserving those questions requires indivisible family blocks and destroys the continuous population interpretation. The honest weakness is that the proposed mass-improvement problem is still a coherent high-multiplicity matching problem. If ChoCo is willing to count such a newly introduced aggregate objective as a worthwhile mirror, the negative case fails; under a stricter requirement of preserving the paper’s named results, however, neither anchor survives.
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.