| paper | Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets |
| authors | Niclas Boehmer, Klaus Heeger, Rolf Niedermeier |
| venue | AAAI 2022 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given resident types \Theta_R with rational masses \mu_\theta, hospitals \(H\) with capacities \(q_h\), type-level old and new profiles \(P_1,P_2\), a \(P_1\)-stable initial flow \(x^1\), and rational \kappa, decide whether a feasible \(P_2\)-stable flow \(x\) satisfies \sum_{\theta,h}\lvert x_{\theta h}-x^1_{\theta h}\rvert\le\kappa; stability requires \(r_{\theta h}(x)s_{h\theta}(x)=0\) for every acceptable pair, where \(r_{\theta h}\) is mass preferring \(h\) to its assignment and \(s_{h\theta}\) is capacity not occupied by residents ranked at least as highly as \theta. The new profile may differ by one adjacent swap in one positive-mass resident type.
A high-multiplicity school-choice market with resident cohorts as types \theta, society masses \mu, capacities \(q_h\), assignment-flow variables \(x_{\theta h}\), and an \(L_1\) reassignment objective relative to \(x^1\), subject to type-level stability under \(P_2\).
The condition \lvert P_1\oplus P_2\rvert=1 is atomic in the paper: a positive-mass type change is a cohort-wide shock, whereas a one-agent change vanishes in the limit, so the theorem's exact parameter meaning and reduction do not transfer.
fatal: False
The mirror covers the incremental stable-flow analogue of Theorem 3 and the density-scaled almost-stable question behind Theorem 2; Proposition 5 provides an algorithmic bridge, while Theorem 1, gadget reductions, and finite-agent experiments are not transferred verbatim.
The strongest mirror is a typed, mass-based version of the paper’s incremental hospital-residents problem. I would lead with Theorem 3, while also carrying Theorem 2 as the stronger NP-hardness anchor.
The continuous object is the population of residents, not the matching outcome. Consider a school-choice market with a finite set \(H\) of schools and resident types \(\Theta_R\). A type records everything relevant to the problem: the resident’s old and new preference orders, eligibility, and any priority-relevant attributes. The society is a rational mass vector \(\mu\), where \(\mu_\theta\) is the fraction of residents of type \(\theta\). There may be hundreds of thousands of residents but only hundreds or thousands of types, because many applicants share the same preference profile, geographic situation, eligibility class, and priority category. Schools have capacities \(q_h\) and preference orders over resident types.
A matching is now a flow \(x_{\theta h}\), the mass of type \(\theta\) assigned to school \(h\). Given the old stable flow \(x^1\), the natural adjustment objective is
\[ D(x,x^1)=\sum_{\theta\in\Theta_R}\sum_{h\in H} \left|x_{\theta h}-x^1_{\theta h}\right|. \]
This is the normalized symmetric difference: in a finite blow-up in which every mass is represented by many identical residents, it is exactly the fraction of assignment edges that disappear or appear.
Stability also has a direct type-level definition. Let
\[ r_{\theta h}(x) = \mu_\theta- \sum_{g:\,g\succeq_\theta h}x_{\theta g} \]
be the mass of type \(\theta\) that strictly prefers \(h\) to its current assignment, treating being unmatched as worst. Let
\[ s_{h\theta}(x) = q_h- \sum_{\eta:\,\eta\succeq_h\theta}x_{\eta h} \]
be the amount of capacity at \(h\) not occupied by residents that \(h\) ranks at least as highly as \(\theta\). The flow is stable precisely when, for every acceptable pair \((\theta,h)\), \(r_{\theta h}(x)=0\) or \(s_{h\theta}(x)=0\). Thus the model preserves the paper’s blocking-pair semantics while replacing named residents by masses of indistinguishable residents.
My lead problem is therefore:
Continuous Incremental Hospital Residents with Ties. The input consists of finite resident types \(\Theta_R\), schools \(H\), rational masses \(\mu_\theta\), capacities \(q_h\), old and new preference profiles \(P_1,P_2\), a \(P_1\)-stable initial flow \(x^1\), and a rational adjustment budget \(\kappa\). The new profile may differ from the old one by one adjacent swap in the preference list of one resident cohort, the natural positive-mass analogue of \(|P_1\oplus P_2|=1\). The question is whether there is a \(P_2\)-stable flow \(x\) with \(D(x,x^1)\le\kappa\).
This is a very close mirror of Theorem 3, which states that IHR-T is W[1]-hard parameterized by the number \(m\) of hospitals, even when \(|P_1\oplus P_2|=1\). The theorem is proved in this paper, using the earlier W[1]-hardness result for COM HR-T from Boehmer and Heeger (2021, Proposition 8).
The scenario is particularly convincing here. The paper itself motivates the problem through large school-choice markets and late cancellations. The continuous regime is not merely “there are many residents”: it is a market with \(N\) very large, \(m\ll N\), and \(\tau_R\ll N\), where resident cohorts recur at high multiplicity. A common preference change—say, a policy change moving one school above another for an entire applicant category—is exactly a mass version of the paper’s swap operation.
My prediction is that the high-multiplicity version is a serious Class A candidate, at least when the number of resident types and schools is moderate. The discrete W[1]-hardness may be exploiting the individuality of the residents in the reduction. After aggregation, the decision variable is a transportation flow, and one can hope to enumerate only the finitely many hospital cutoff patterns and solve the resulting flow or linear programs. If that succeeds, the result would be especially informative: the paper’s hardness would have been population-multiplicity hardness that disappears under continuization. If it does not, the question would establish that the obstruction lives in the preference structure or the number of hospitals and therefore transfers to the continuum.
The paper’s strongest NP-hardness result gives a second, slightly more ambitious mirror. Theorem 2, proved by the authors in the full version, states that IASM is NP-hard and W[1]-hard parameterized by
\[ k+b+|P_1\oplus P_2|. \]
The reduction is from LOCAL SEARCH ASM, whose hardness is cited from Gupta et al. (2020, Theorem 3).
For this anchor, take two finite families of cohort types, \(\Theta_U\) and \(\Theta_W\), with masses \(\mu^U_\theta\) and \(\mu^W_\phi\). Each type contains its old and new preference orders. A candidate solution is a nonnegative matching flow \(x_{\theta\phi}\), subject to the obvious mass constraints. Define
\[ r^U_{\theta\phi}(x) = \mu^U_\theta- \sum_{\psi:\,\psi\succeq_\theta^2\phi}x_{\theta\psi} \]
and
\[ r^W_{\phi\theta}(x) = \mu^W_\phi- \sum_{\eta:\,\eta\succeq_\phi^2\theta}x_{\eta\phi}. \]
The normalized mass of blocking pairs is naturally
\[ B(x) = \sum_{\theta,\phi} r^U_{\theta\phi}(x)\, r^W_{\phi\theta}(x). \]
This product is not arbitrary: if a mass \(a\) of \(U\)-agents and a mass \(b\) of \(W\)-agents mutually prefer one another to their current partners, then the corresponding cohort pair contributes \(ab\) blocking pairs in the finite blow-up.
The problem is:
Continuous Incremental Almost-Stable Marriage. Given \(\mu\), \(P_1,P_2\), a \(P_1\)-stable initial flow \(x^1\), and rational thresholds \(\kappa,\beta\), decide whether there is a \(P_2\)-matching flow \(x\) satisfying
\[ D(x,x^1)\le\kappa \qquad\text{and}\qquad B(x)\le\beta. \]
The case \(\beta=0\) is the exact-stability mirror; positive \(\beta\) is the continuous analogue of allowing at most \(b\) blocking pairs.
This is recognizably the authors’ problem, not an easier unrelated optimization problem. It retains the old profile, changed profile, initial stable matching, minimum adjustment objective, and tolerance for blocking pairs. It also matches their empirical observation that allowing a small fraction of blocking pairs can dramatically reduce the required restructuring in a large market.
I would expect the exact case \(B(x)=0\) to be substantially more tractable than discrete IASM, possibly through finite-type stability constraints and flow optimization. The positive-\(\beta\) problem is a plausible Class C candidate: the blocker budget introduces bilinear residual-mass terms, and the difficulty may survive even after individual identities disappear. Alternatively, if the combinatorics of the LOCAL SEARCH ASM reduction can be encoded at the level of cohort types, Theorem 2 could yield a Class B hardness transfer. Determining which of these happens is precisely the useful question.
A supporting algorithmic anchor is Proposition 5, proved by the authors in the full version. It states that ISM-T is solvable in
\[ O\!\left( 2^{(t_U+1)(t_W+1)}\cdot n^{2.5} \right) \]
time, where \(t_U\) and \(t_W\) are the numbers of agent types on the two sides. This is not a novelty collision; it is evidence that the paper already regards type compression as a meaningful structural parameter.
Its continuous counterpart is the exact typed problem above with \(B(x)=0\), asking for a stable updated flow within distance \(\kappa\). The authors’ enumeration of type-compatibility graphs would become an enumeration of compatibility patterns between cohort types, followed by a maximum-weight transportation problem rather than a matching problem on \(n\) named agents. The expected running time should depend exponentially on the number of types but polynomially on the encoding length of the masses. This is a clean Class A target and a direct bridge from the paper’s own parameterized result to continuous optimization.
The paper’s Theorem 1, asserting linear equivalence of Swap, Replace, Delete, and Add changes, strengthens the mirror even though I would not use it as a primary computational anchor. In the continuous model, these become positive-mass versions of the same operations: changing a cohort’s ranking, replacing its preference type, removing mass, or introducing a type with zero old mass and positive new mass.
The weakest point is that the paper’s formal models use identifiable agents with preferences over other identifiable agents. Aggregating them into types necessarily creates indifference among clones and permits a flow to split a type across several partners. That is a genuine modeling choice, not a theorem. The defence is that this is exactly what high multiplicity means: agents identical in every preference- and priority-relevant respect should be quotiented together. The paper itself studies ties, explicitly defines agent types, and treats hospitals as collections of same-type agents. Still, a formal blow-up-and-rounding theorem is needed to show when a rational flow corresponds to a large finite market with only a controlled additive loss. That is the main technical obligation of the proposed mirror, not something to assume away.
The strongest negative case is a fidelity objection, not the claim that fractional matchings are illegitimate. The paper studies how to preserve a particular matching of named agents after an essentially atomic perturbation. Its objective, \(\lvert M_1\triangle M_2\rvert\), counts which named edges survive. The proposed mass model changes all three ingredients: atomic perturbations become cohort shocks, named edges become type–hospital mass, and exceptional blocking pairs become densities. That is enough to defeat the claimed direct mirrors.
For Theorem 3, the problem is especially sharp. The condition \(\lvert P_1\oplus P_2\rvert=1\) means that one named resident changes one adjacent pair in their preference list. If a type of mass \(\mu_\theta>0\) changes its ranking, then in an \(N\)-agent blow-up, \(\mu_\theta N\) residents change—not one. If only one resident changes, its mass is \(1/N\), which disappears in the atomless limit. Choosing a threshold of order \(1/N\) to detect it simply reinstates finite-agent granularity.
This is not a cosmetic difference in the theorem’s reduction. The construction uses a special resident, a one-swap perturbation, and individual penalizing gadgets to force the source instance through the new matching. With a fixed positive-mass type, the perturbation is a collective policy change; with vanishing mass, it has no effect on the aggregate society. One can certainly study a new problem in which an entire applicant cohort changes its preferences, but that is not the paper’s one-change incremental problem. Alternatively, one can give every source resident its own type and blow each one up many times; that preserves the finite instance but removes the population compression that motivates continuization. The theorem therefore does not provide the advertised bridge to a low-type continuous society.
Theorem 2 has a related, even more fundamental scaling problem. If \(x\) is a mass matching and \(B(x)\) is the proponent’s blocking-pair mass, then an \(N\)-agent blow-up has approximately
\[ \#\operatorname{blocks}(M)=N^2B(x). \]
By contrast, the symmetric-difference objective scales as \(ND(x,x^1)\). Thus a fixed finite allowance \(b\) converges to exact stability: \(b/N^2\to 0\). To obtain a nontrivial limit one must replace \(b\) by a density such as \(\beta N^2\), producing the proposed constraint \(B(x)\le\beta\).
That is a coherent research extension, but it is not the continuous form of the theorem’s parameterized problem. In the discrete reduction, “few blocking pairs” means a few exceptional named pairs. In a typed population, a blocking type-pair normally generates a whole rectangle of blocking clone pairs. Preserving sparse exceptions requires splitting off small masses, eventually recreating individual types. Keeping positive masses instead turns the problem into one about the density of mutually dissatisfied cohort pairs, with a different parameter and different feasible-set geometry. The proponent’s model may be interesting, but Theorem 2 does not establish it as a faithful mirror.
There is also a strictness issue. IASM is based on strict named preferences. A genuine clone population normally induces ties among indistinguishable copies. Passing to weak typed preferences is a sensible extension, and I would not reject it merely because the literal notation changes. But it reinforces the point: the proposed problem is a new anonymous matching model, not a high-multiplicity realization of the original strict instance.
Proposition 5 does not repair these gaps. Its “agent types” are a parameter inside an identity-level algorithm. The final maximum-weight matching still runs on the \(n\) named agents and assigns weight according to the particular edges of \(M_1\). The proposition therefore does not say that rational masses, fractional flows, or type-level old matchings preserve the incremental objective. If one assumes enough anonymity that the old matching itself is completely described by type–type edge masses, then the resulting problem is a new capacitated stable-flow problem; if one does not make that assumption, the mass vector has forgotten the information that \(\lvert M_1\triangle M_2\rvert\) measures.
Theorem 1 is no stronger. Its reductions use binding agents, clones, edge gadgets, and additive corrections for individual changed agents. Those constructions do not automatically become measure-preserving transformations when one agent is replaced by a positive-mass cohort. Type-level versions of Add, Delete, Swap, and Replace can be defined, but their equivalence would be a fresh modelling theorem rather than a consequence of the paper’s linear reductions.
The honest limitation is that this does not prove that no worthwhile extension exists. A large school-choice market with repeated resident cohorts, capacities scaled with population, cohort-wide policy changes, and an objective measuring mass reassignment is perfectly sensible. Exact rational blow-ups can even make that anonymous typed model mathematically clean. But it should be classified as an extension or re-modelling, not as a direct continuization of Theorems 2 or 3. I can therefore defeat the proponent’s claimed anchors as faithful mirrors; I cannot honestly sustain the stronger universal claim that every cohort-based continuous matching question inspired by this paper would be worthless.
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.