| paper | Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem |
| authors | Sulian Le Bozec-Chiffoleau, Charles Prud'homme, Gilles Simonin |
| venue | IJCAI 2024 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper offers a plausible type-mass extension of robust stable matching. However, neither Theorem 1 nor Theorem 4 asserts a qualifying computational result; the NP-hardness and polynomial-runtime claims occur only in prose or prior work. Therefore bit (a) fails under the explicit anchor rule.
fails bit a — no named computational result to mirror
The finite strict-preference rotation lattice does not canonically compress to type masses, so the proposed continuous problem would require new stable-flow or fractional-stability theory.
fatal: False
The proposed mirror covers the robust stable-matching objective for SM, HR, and MM markets, but not the paper's exact finite-agent rotation theorems, CP formulation, or experiments.
The strongest positive case is narrow but credible: the paper’s robustness question has a natural high-multiplicity version for matching markets with many exchangeable agents.
The lead anchor is Theorem 1. It is proved in this paper, although the authors explicitly say that it restates a result from Genc et al. (2017). For a stable matching \(M\), Theorem 1 identifies the nearest stable matching that excludes a given pair \((m,w)\): it is characterized by either \(S_{\rho_p}\cap S_M\) or \(S_{\rho_e}\cup S_M\). This is not itself a complexity-class theorem, but it is the paper’s clearest named algorithmic result: a seemingly global robustness repair is reduced to two closure projections in the rotation poset.
The natural mirror is the following.
Consider a large national or regional matching platform assigning applicants to employers, hospitals, or positions. There are \(N\) agents but only \(\tau\ll N\) complete types. A type includes the side of the market, its ranking over the opposite-side types, its capacity or priority parameters, and any other information used by stability. Let \(A\) and \(B\) be the finite sets of types, with rational masses \(\mu_a\) and \(\nu_b\). A matching is a mass-transportation matrix \(x\), where \(x_{ab}\) is the mass of type \(a\) assigned to type \(b\). Agents of the same type are interchangeable; this is exactly the high-multiplicity assumption.
Use the standard nonatomic stability condition: for no pair \((a,b)\) may there be positive mass on both sides assigned to partners ranked below \(b\) by \(a\) and below \(a\) by \(b\), so that a positive amount could move into \(x_{ab}\). Unmatched mass may be represented by an outside-option type. Define the changed mass between two matchings by
\[ D(x,y)=\frac12\sum_{a,b}|x_{ab}-y_{ab}|. \]
For every non-fixed type edge \(e=(a,b)\) used by \(x\), imagine that the whole contract class \(a\)-to-\(b\) becomes forbidden. Let
\[ r_x(e)=\min\{D(x,y):y\text{ is stable and }y_{ab}=0\}-x_{ab}, \]
where the subtraction removes the mass that had to leave the forbidden edge itself, just as the paper subtracts \(1\) from its discrete distance. The continuous problem, which I would call Robust Stable Matching\(_\infty\), is
\[ \min_{x\text{ stable}}\ \max_{e:x_e>0} r_x(e). \]
A solution is a stable mass matching \(x\) and its minimum worst-case collateral mass change.
This is recognizably the authors’ problem: the objects remain stable matchings, the perturbation remains a forbidden pair, the response remains the nearest stable matching, and the objective remains worst-case repair distance. Only the unit of failure changes from one named individual pair to a contract class between two exchangeable types. That is not an arbitrary relaxation in a setting such as hospital admissions or employer matching, where an accreditation rule, eligibility rule, or institutional outage can indeed remove an entire type-to-type channel.
I would expect the intended high-multiplicity version to be Class A, provided the type-level stable allocations admit a weighted rotation-poset representation. Theorem 1 suggests that each type-edge outage should correspond to an upward or downward closure projection. The paper’s Lemma 1 supplies the required monotonicity of distance. With rational type masses, those projections should become weighted mass transfers, and the outer minimax problem is a plausible linear or convex optimization problem. The main technical questions are whether a compressed rotation structure can be constructed from \(\tau\) types, whether fractional stable allocations are exactly described by an order-polytope or stable-flow formulation, and whether the nearest-repair subproblem has an efficient separation oracle.
The paper’s Theorem 4, proved here, reinforces this case: once the upward and downward rotation sets are known, the median stable matching used for an upper bound can be found in \(O(|V|)\) time. Its continuous analogue would replace the finite multiset of candidate matchings by rationally weighted type-level response states and compute the weighted median closed state. I would treat this as supporting evidence rather than a second anchor, since it concerns presolve rather than the main optimization problem.
The weakest point is unavoidable: a literal individual pair has zero mass in a nonatomic society, so forbidding one such pair would be vacuous. The mirror must therefore make the perturbation type-level or specify a positive shock mass. That changes the granularity of the robustness event, though not the underlying stable-matching question. A second risk is that the discrete rotation lattice may not survive fractionalization in the simple form required by Theorem 1. If it does not, the mirror could become continuum-specifically hard rather than tractable.
One bibliographic qualification matters. The paper has no numbered theorem explicitly stating that RSM is NP-hard, in P, or otherwise belonging to a complexity class. The NP-hard and NP-complete claims occur in prose and are attributed to Genc et al. (2017, 2019); the polynomial runtime claims for Algorithms 1 and 2 likewise appear outside numbered complexity theorems. Thus, under a strictly literal anchor rule, there is no qualifying named complexity-class anchor. Theorem 1 is the strongest named algorithmic anchor available, and it supports a serious continuous mirror, but the paper itself does not supply the kind of numbered complexity result your programme normally requires.
The negative case starts with the point the proponent concedes: this paper has no qualifying named complexity result. The claim that RSM is NP-hard appears in prose and is attributed to Genc et al.; the polynomial bounds for Algorithms 1 and 2 are also not stated as numbered complexity theorems. Theorem 1 and Theorem 4 are structural facts about a finite rotation representation, not complexity classifications of a computational problem. Thus the paper does not actually supply the sort of anchor the ChoCo programme is designed to continuize.
Theorem 1 is nevertheless the strongest possible attempted anchor, and it fails to survive faithfully. It concerns a particular *named* pair \((m,w)\) becoming forbidden. In a market with \(N\) copies of finitely many types, forbidding one named pair changes normalized mass by \(1/N\), which tends to zero. With the paper’s unnormalized distance, the limit is not a mass problem at all: the effect remains an integer tied to an omitted identity.
The obvious repair is to forbid an entire type-to-type contract class, say all \(a\)-to-\(b\) matches. That is a plausible institutional outage, but it is not the paper’s perturbation with a continuous unit. It changes the adversarial object from one individual edge to a positive-measure collection of edges. More importantly, the theorem’s proof depends on the strict one-to-one rotation structure:
\[ S_M\cap S^U_{\rho_p} \qquad\text{or}\qquad S_M\cup S^D_{\rho_e}. \]
Those are projections in a lattice of closed subsets of rotations, where each named pair is generated and eliminated at most once and \(H(\rho)\) is a set of named agents. A type-mass matching has no corresponding object supplied by the paper. If preferences are retained as strict rankings over individuals, the finite rotation digraph still contains the individual agents and does not compress to \(\tau\) types. If preferences are quotiented to rankings over types, one has introduced ties or divisible preferences, and the rotation-lattice representation is no longer the paper’s representation. If the within-type tie-breaking is omitted, the same mass vector can correspond to different strict refinements with different stable lattices and robustness values.
There is therefore a genuine trilemma:
\[ \text{exact strict stable marriage} \;+\; \text{finite type description} \;+\; \text{positive-mass failure} \]
cannot all be retained without adding a new model-specific theory. The natural type-level replacement may be interesting, but it is a robust stable-flow or stable-allocation problem, not a continuous version of Theorem 1. Calling the perturbation a type-class outage does not solve that structural problem; it merely defines a different problem for which the paper provides no theorem.
Theorem 4 is weaker still. Its “median” is the median of a specially manufactured multiset containing \(S^U_\rho\) and \(S^D_\rho\) for every rotation. The population distribution supplies masses to agent types, not a measure on rotations or on stable matchings. Replacing the cardinality condition
\[ |S^U_\rho|+|S^D_\rho|<|R(I)| \]
by weighted masses is not canonical: rotations overlap in their affected agents, and no weighting of rotations is induced by \(\mu\). A weighted median can certainly be invented, but it would be an additional construction rather than a mirror of the paper’s result.
The paper’s many-to-many extension does not repair this. Its meta-rotations still operate on named agents with individual capacities; it is not a high-multiplicity or nonatomic model.
This is not an objection to high-multiplicity matching generally. Large hospital or employer markets can plainly contain exchangeable cohorts. Nor is it an objection that the eventual continuous problem might be easy or hard. The narrower point is that the paper’s actual robustness primitive is identity-sensitive, while its named results are consequences of an individual rotation lattice. Replacing the primitive by type-edge failure and replacing the lattice by fractional stability may yield worthwhile new research, but the paper itself gives no computational anchor for it.
The case is therefore strong as a priority objection: there is no named complexity result to mirror, and the best attempted mirrors require changing both the perturbation and the mathematical representation. It is not an airtight universal impossibility claim. If ChoCo is willing to treat type-level contract outages in large matching markets as sufficient continuity, then a sensible new problem can be written. But that would be a new robust matching programme, not a faithful continuous mirror 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.