| paper | Probabilistic Analysis of Stable Matching in Large Markets with Siblings |
| authors | Zhaohong Sun, Tomohiko Yokoyama, Makoto Yokoo |
| venue | IJCAI 2025 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finitely many daycare centers \(D\) with mass capacities \(q_d\), finitely many complete family types \(F\), rational type masses \(\mu_f\), joint preferences over daycare tuples, child acceptability, daycare priority types, and an order \(\pi\) over sibling types, run Mass-ESDA: output either a mass assignment \(x_{f,a}\ge0\) satisfying \(\sum_a x_{f,a}=\mu_f\), \(\sum_{f,a}|\{i:a_i=d\}|x_{f,a}\le q_d\), individual rationality, and absence of any positive mass-blocking move, or output \(\mathrm{Unsuccess}\) with its rejection-cycle or order-history certificate.
A finite-type high-multiplicity daycare market: \(\mu_f\) is mass of complete family type \(f\); \(x_{f,a}\) assigns that mass to daycare tuple \(a\); capacities constrain aggregate child mass; greedy priority choice operates on priority-ranked mass; and stability forbids any positive mass sibling coalition improving its tuple.
The proposed type-level ESDA has not been shown to preserve the original rejection-chain invariants when family mass splits across tuples, so conditional soundness and termination require new proofs.
fatal: False
The mirror covers Theorem 2’s conditional soundness and finite termination for a mass version of ESDA, and can reproduce Theorem 1’s qualitative failure example. It does not directly cover Theorem 3’s specific growing-\(m\), Mallows-random asymptotic or the experimental results.
The strongest positive case is that this paper already has the right population-scale object, even though it does not yet formulate it as a continuous computational problem. Its families are naturally repeatable agents, its central parameter is the sibling fraction \(\alpha\), its daycare priorities are generated from a distribution, and its main theorem is explicitly an \(n\to\infty\) statement.
A qualification comes first. The paper contains no named theorem classifying a problem as NP-hard, polynomial-time, FPT, or similar. The NP-hardness statements in the introduction are cited from Rönn, McDermid–Manlove, and Biró et al.; they are not results proved in this paper. The two usable anchors are therefore algorithmic and probabilistic rather than complexity-class theorems.
The lead anchor is Theorem 3, proved in this paper: for the random market \(\widetilde I\) with \(\phi=O(\log n/n)\), the probability that a stable matching exists converges to \(1\). This is unusually mirrorable because the theorem is already about a large population whose relevant structure is distributional.
The continuous problem I would propose is Continuous Mallows-Daycare Stability. A type \(f\) is a complete family type: its ordered number of children \(k_f\le K\); every child’s acceptability and priority score at every daycare; and the family’s strict preference ordering over daycare tuples. Thus two families of type \(f\) are interchangeable for the entire problem. Let \(\mu_f\) be the fraction of families of type \(f\). The sibling proportion is, for example,
\[ \frac{\sum_{f:k_f\ge 2} k_f\mu_f}{\sum_f k_f\mu_f}=\alpha. \]
Daycares \(d\in D\) have capacities \(q_d\), priority orderings over child types, and the usual greedy choice functions.
A solution is a mass assignment \(x_{f,a}\), where \(a\) is an acceptable tuple of daycares for type \(f\). It must satisfy
\[ \sum_{a}x_{f,a}=\mu_f \]
for every family type and
\[ \sum_f\sum_a \left|\{i:a_i=d\}\right|x_{f,a}\le q_d \]
for every daycare. Mass is not a fractional child or a fractional family in the underlying interpretation: it is the fraction of a large cohort of identical families assigned to each configuration.
Stability is defined at mass level. A positive mass \(\varepsilon\) of type \(f\), currently assigned to tuple \(b\), may move to a preferred tuple \(a\) if \(\varepsilon\le x_{f,b}\) and, after removing that slice from \(b\) and inserting it into \(a\), every daycare in \(a\) accepts all proposed sibling mass under its priority choice function. A mass matching is stable if no such \((f,a,b,\varepsilon)\) exists.
For the probabilistic version, daycare priority orders are drawn from the Mallows distribution around a common reference order, with \(\phi_N=O(\log N/N)\). The computational question is:
Given the finite type masses, capacities, family preferences, reference priority order, and a realized priority profile, output a mass-stable matching or report that none exists; under the Mallows distribution, determine whether the algorithm succeeds with probability at least \(1-\delta\).
The expected direction is Class A in the intended regime: bounded \(K\), bounded preference-list length \(L\), moderate type support, and near-common priorities. The allocation layer has finitely many configuration variables, and Theorem 3 suggests that the problematic rejection patterns become vanishingly rare. Exact worst-case existence for arbitrary sibling preferences may remain hard, but that is a boundary question rather than a reason to reject the mirror.
The regime is plausible. Consider a large municipality or recurring intake system with many households sharing the same sibling structure, age profile, priority-score vector, acceptable-centre set, and joint daycare preferences. Fifteen to twenty percent sibling children is exactly the paper’s empirical regime. Daycares can either remain a fixed set of aggregate facilities or be grouped into finitely many centre types with repeated capacity and priority policies. The number of families grows while the number of complete family types remains moderate.
The second anchor is Theorem 2, also proved in this paper: if ESDA returns a matching, that matching is stable, and ESDA always terminates in finite time. Its continuous counterpart is Mass-ESDA. The input is the same mass market together with an initial order \(\pi\) over sibling family types. ESDA processes type mass rather than named families: proposals send remaining mass to the next preferred tuple, daycares accept the highest-priority mass up to capacity, rejected mass generates rejection chains, and the improvement check tests the mass-blocking condition above.
The output is either:
Unsuccess, together with the type-level rejection cycle or previously attempted order that caused termination.Unsuccess is not a certificate that no stable matching exists, exactly as in the paper. Aggregating identical families removes dependence on the number of cloned households. If \(s\) is the number of sibling types, the adaptive order exploration suggests an \(s!\operatorname{poly}(\lvert\operatorname{supp}\mu\rvert,m,L)\) procedure: plausibly FPT in \(s\), and polynomial when \(s\) is fixed. I would not claim unrestricted polynomial time without proving that the type-level aggregation preserves every ESDA invariant.
The authors should recognize these as their questions rather than as unrelated fractional matching. The mirror retains family-level complementarities, tuple preferences, daycare choice functions, sibling seat transfers, and the stronger blocking-coalition definition. It changes only the representation of a large repeated cohort from an explicit list of families to a mass vector.
A useful sanity check is Theorem 1, which says that original SDA may return an unstable matching. Its finite counterexample can be lifted directly to positive masses of the same family types, so continuization does not artificially make every algorithm correct. I would not use it as a third anchor, but it supports the fidelity of the proposed model.
The weakest point is the interaction between mass splitting and sibling complementarities. A continuous solution may distribute one family type across several daycare tuples, whereas each finite family is indivisible. Without a rounding theorem, or a proof that rational mass solutions correspond to large finite markets with controlled stability error, this is a genuine high-multiplicity relaxation rather than an exact restatement. A second concern is that the paper assumes \(m=\Omega(n)\); if every named daycare has a unique location and priority structure, the number of complete types may grow with \(n\), destroying the intended gain. The positive case therefore depends on a credible repeated-cohort or repeated-centre regime.
The natural follow-up questions are whether mass stability can be rounded to finite stable matchings, whether exact continuous existence is tractable for unrestricted sibling preferences, whether the threshold \(\phi=O(\log N/N)\) is sharp, and whether exact probability computation over Mallows priority profiles becomes a continuum-specific counting problem. Those are precisely the kinds of computational questions the paper’s large-market analysis makes available but does not itself ask.
The negative case is stronger than the proponent admits, and it starts before modelling: this paper has no qualifying computational anchor. Theorem 3 is an asymptotic existence-probability statement, not a complexity, approximation, query, or parameterized result. Theorem 2 proves conditional correctness and finite termination, but gives no running-time bound or computational classification. Theorem 1 is only a counterexample to an algorithm. The NP-hardness results belong to cited papers, not to this one. Thus a continuous optimization problem can certainly be invented from the paper, but it is not a continuization of a computational result proved here.
Theorem 3 is also a poor population-continuum anchor. Its asymptotic regime is sparse, not high-multiplicity. The paper assumes \(m=\Omega(n)\), preference lists have bounded length, and each child selects only a few named daycares. Consequently, a daycare receives only \(O(1)\) expected applications when \(m\) grows linearly with \(n\); in the synthetic experiments, capacities are fixed small numbers. The limit is therefore a growing random matching graph in which resources and relevant identities proliferate, not a fixed finite collection of voter-like types carrying positive mass.
A complete family type must preserve the family’s joint tuple preferences, child-level acceptability, and priority position at every daycare. With \(m=\Omega(n)\), random preference lists over named daycares already produce a type space growing roughly like \(m^{O(LK)}\), while the realized family types will generally be almost all distinct. Encoding exact priority positions makes the support larger still. The resulting mass vector has essentially one atom of size \(1/n\) per family, so it gives no continuous compression.
The Mallows parameter does not repair this. The condition \(\phi=O(\log n/n)\) makes the priority perturbation vanish in normalized inversion distance: the theorem studies a sequence of increasingly common priority orders with a small number of finite exceptional inversions. That randomness is over a changing discrete profile, not over a fixed population distribution. A probability question about those permutations is a probabilistic analysis of sparse finite markets, not a computational problem whose society has been continuized.
The strongest possible repair would fix a finite set of daycares or daycare types, scale their capacities with population size, and posit finitely many repeated family types. That is a coherent high-multiplicity matching model, and high-multiplicity matching literature would support its plausibility. But it no longer instantiates Theorem 3: the paper’s growing-\(m\), random-list, sparse-capacity model has been replaced. It may deserve an independent paper on continuous daycare matching, but it cannot be presented as the computational mirror of this theorem.
Theorem 2 fares no better. ESDA’s substantive object is the history of rejection chains among named sibling families and the permutations \(\pi\) explored after one family displaces another. If exact strict priorities and tie-breaking are retained, those identities must remain in the type description, destroying the intended multiplicity. If they are collapsed, daycare choice becomes a threshold rule over priority masses, and ESDA becomes a different algorithm with different rejection chains. Allowing a family type’s mass to split among several tuples also changes the indivisibility that the original stability definition acts on. Clearing denominators does not guarantee that a mass-stable assignment rounds to a stable finite assignment, or even that the same blocking coalitions survive rounding.
Moreover, Unsuccess is not a nonexistence certificate in the original algorithm. A type-level version would therefore offer neither a decision procedure nor a meaningful complexity theorem without substantial new work. Conditional soundness of a newly designed mass algorithm is not distinctive evidence from this paper; the same statement could be manufactured for almost any matching heuristic.
Theorem 1’s counterexample can indeed be replicated with positive mass, but that only shows that duplication does not automatically remove instability. It contributes no computational question and cannot rescue the two proposed anchors.
So the honest verdict is not that continuous daycare matching is impossible or intrinsically uninteresting. A separately motivated cohort model could be worthwhile. The stronger conclusion is that this paper supplies no named computational result to continuize, while its central asymptotic theorem relies on growing resources, vanishing Mallows noise, and increasingly individualized preference data rather than on a finite high-multiplicity population. The proponent’s constructions are therefore extensions or re-modellings, not worthwhile continuous mirrors 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.