| paper | d4-conf-ijcai-2017-0498 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 2 provides a computational anchor, but its repair question depends on removing a particular couple. The proposed mass model cannot represent that event or count the resulting individual partner changes; its type-pair ban is a different robustness question. No continuous mirror the authors would recognize survives these objections.
fails bit b-changes — the continuum limit changes the question
A coupling records type-level flows, not which people are coupled; forbidding \(q\) mass from one type cell therefore models a bulk compatibility ban, while the paper measures repair after particular couples break.
fatal: True
The proposed mirror targets Theorem 2 and the repair subproblem underlying the supermatch check; it does not cover the paper's search formulations, heuristics, or empirical comparison.
The strongest mirror I see is the paper’s nearest stable repair question. It fits the paper’s central object—repairing a stable matching after a match breaks—and has a plausible high-multiplicity setting: a large centralized placement market, such as residency or graduate hiring, with many applicants and positions but relatively few preference classes. Within a class, agents have the same preferences over counterpart classes; masses record the fractions in each class. The paper itself motivates robustness with resident–hospital moves, which helps make this setting recognizable to its authors.
My lead anchor is Theorem 2, proved in this paper. It says that for a stable matching \(M\) and an unwanted nonfixed pair \(\langle m_i,w_j\rangle\), the closest stable matching that removes that pair is one of two particular matchings. In the rotation-poset representation, if \(S\) is the closed set for \(M\), the upward candidate removes the rotation producing the pair and its successors in \(S\): \(S_{\mathrm{UP}}^*=S\setminus(\{\rho_{p_{i,j}}\}\cup(N_t^+(\rho_{p_{i,j}})\cap S))\). The downward candidate adds the rotation eliminating the pair and its predecessors not already in \(S\): \(S_{\mathrm{DOWN}}^*=S\cup\{\rho_{e_{i,j}}\}\cup(N_t^-(\rho_{e_{i,j}})\setminus S)\). Whichever candidates exist, the theorem says the closest repair is one of them.
Theorem 2 is a structural algorithmic result, not a numbered claim that the problem is in P. The paper’s following, unnumbered complexity argument says that checking a \((1,b)\)-supermatch takes \(O(n|V|)\) time after \(O(n^2+|V|^2)\) preprocessing. The paper gives no named hardness result. I would not present the polynomial bound as a second numbered anchor.
Here is the continuous problem I would hand to a prover: \(q\)-Mass Closest Stable Repair. Its instance consists of two finite sets of types, applicant types \(U\) and position types \(W\), with rational masses \(\mu_i\) and \(\nu_j\), each side totaling one. Each type has a strict ranking over the types on the other side; individuals within a counterpart type are interchangeable. The input also includes a stable matching represented by a coupling \(X=(x_{ij})\), whose row and column sums are \(\mu\) and \(\nu\), a used type-pair edge \((i,j)\), and a rational shock size \(q\leq x_{ij}\).
Stability means no positive mass on both sides can mutually improve: for every \(i,j\), either the mass of type \(i\) assigned to types it ranks below \(j\) is zero, or the mass of type \(j\) assigned to types it ranks below \(i\) is zero. The task is to find a stable coupling \(Y\) with \(y_{ij}\leq x_{ij}-q\), minimizing the collateral reassignment mass \(d(X,Y)-q\), where \(d(X,Y)=1-\sum_{i,j}\min(x_{ij},y_{ij})\). If no such \(Y\) exists, report infeasibility. Each individual still receives one whole counterpart; only the type-level flows are fractional.
I would expect this problem to be tractable, as a conjecture rather than a claim. The discrete nearest-repair result suggests a structural characterization, while rational masses and \(q\) could act as weights in a compressed type-level version of the rotation-poset method. The challenge is whether that structure survives when mass can split across counterpart types. If stability’s mutual-improvement condition creates choices that cannot be represented by weighted closures, continuum-specific hardness remains plausible. A natural follow-on is to choose the baseline stable coupling minimizing worst-case repair cost over all type-pair shocks of size \(q\), then study how the answer changes as \(q\) shrinks.
This mirror covers the repair subproblem behind the paper’s supermatch check, not its CP encoding, metaheuristics, or empirical comparison. My weakest point is the scale of the shock: the paper breaks one pair, whereas \(q\) is positive mass. Setting \(q=1/N\) recovers a one-pair shock in a population of size \(N\), but that shock vanishes as \(N\) grows. A fixed \(q\) gives a meaningful continuum repair question, but changes the perturbation regime. The type model also coarsens the paper’s complete rankings of named agents to rankings over counterpart classes. Those are real adaptations; they seem necessary to make a finite-support, high-multiplicity version of the authors’ repair problem well-defined.
The strongest objection is a mismatch between the event in Theorem 2 and the information in the proposed mass model. Theorem 2 identifies the closest stable matching after a *particular man–woman pair* is removed, using the unique rotations that produce and eliminate that pair. The paper does not state a numbered complexity theorem for this task: its polynomial-time supermatch check appears in the prose, while the optimization methods are a CP model and empirical heuristics. Theorem 2 is a real structural anchor, but it gives the proposed continuous problem little computational content once individual pairs are aggregated away.
The proposed \(q\)-Mass Closest Stable Repair exposes the problem. A coupling \(X=(x_{ij})\) records how much mass of type \(i\) is matched to type \(j\); it does not record *which people* form those couples. If \(q\) mass of couples in one type cell breaks, the people can in principle be rematched within that same cell. Their type-level coupling stays \(X\), even though each affected person gets a different partner. The proposed constraint \(y_{ij}\leq x_{ij}-q\) instead forbids that much type-\(i\)-to-type-\(j\) matching. It models a bulk ban on that type pair, not the breakup of particular couples.
There is a corresponding failure in the objective. The proposed \(d(X,Y)\) measures changes in type-level assignments, not changes in individual partners. If the model counts partner identities, a mass \(q\) of broken couples has already incurred the initial \(q\) changes, and re-pairing within their types can leave no collateral changes. If it counts only type flows, those partner changes disappear from the metric. Either way, the input masses alone cannot represent the paper’s repair cost. The discrete rotation argument depends on precisely the pair-level information that the coupling discards.
The best rescue is to keep an identity-level matching map and define a shock affecting a positive mass of its couples. But with preferences only over types, within-type rearrangements leave stability unchanged and can make the collateral cost zero. To prevent that, the model must retain individual preference distinctions—such as rankings over named counterparts—or add restrictions on which within-type re-pairings are allowed. Those distinctions either undermine the finite-support compression or introduce substantive rules absent from the paper. Alternatively, forbidding a positive mass from matching a counterpart type yields a well-posed market-disruption problem, but it is a different robustness question. Optimizing the baseline matching against such shocks does not remove this modeling fork.
This is not a general objection that matching markets lack high multiplicity: the paper itself points to residents and hospitals, and large markets are plausible. Nor is the issue that the continuous answer might be easy or hard. It is that the paper’s unit of disruption and repair is an identity-specific couple, while a population distribution over preference types cannot distinguish that couple from the others in its cell.
The negative case is strongest against the proposed mirror and its nearest repair variants, but it is not airtight as a universal claim. The authors might recognize robustness to mass-level compatibility failures as a worthwhile extension. I would treat that as a new problem requiring its own motivation, rather than a continuous mirror of Theorem 2 or the paper’s supermatch notion.
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.