| paper | Adapting Stable Matchings to Forced and Forbidden Pairs |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), strict preferences over acceptable partner types, a stable incumbent census \(y^1\), forbidden type pairs \(P\) with \(y^1_e>0\), and \(\kappa\in\mathbb{Q}_{\ge0}\), decide whether there exists a symmetric mass-pairing matrix \(y\) with \(\sum_u y_{tu}\le\mu_t\), \(y_e=0\) for every \(e\in P\), and \(\delta(y,y^1)=\frac12\sum_{t,u}|y_{tu}-y^1_{tu}|\le\kappa\), such that for every acceptable pair \(\{t,u\}\), it is not the case that both \(R_{t,u}(y)>0\) and \(R_{u,t}(y)>0\), where \(R_{t,u}(y)\) is the mass of type \(t\) assigned to partners ranked below \(u\).
A high-multiplicity Stable Roommates market: types encode complete cohort-level preferences and acceptability, \(\mu\) gives cohort masses, \(y\) is the symmetric mass-pairing decision variable, forbidden type pairs have zero mass, and the objective is \(L_1\) reassignment distance from the incumbent census \(y^1\).
The positive-measure blocking convention is tie-like and has not been proved equivalent to strict clone-level Stable Roommates: different clone tie-breaks could affect feasibility or the reassignment distance.
fatal: False
The mirror covers Theorem 1's \(Q=\varnothing\), \(P\subseteq M_1\) forbidden-pair hardness regime. It leaves Theorem 2's FPT algorithm, the marriage results, and the ties variants unresolved.
There is a credible mirror, and the strongest anchor is Theorem 1.
The natural regime is a large repeated pairing market: a company pairs thousands of developers, a university pairs a large cohort of students, or a reviewer pool assigns papers under recurring conflict-of-interest constraints. A type records everything relevant to matching: role, skills, location, acceptability, preference order over partner classes, and whether a cohort-level pair is permitted. If there are \(N\) agents but only \(\tau\) such classes, with \(N\gg\tau\), then replacing counts by rational masses is a genuine high-multiplicity model rather than a merely fractional reformulation.
For a finite type set \(T\), let \(\mu_t\in\mathbb{Q}_{\ge 0}\) be the mass of type \(t\), with \(\sum_t\mu_t=1\). A mass matching is a symmetric type-pair census \(y\): \(y_{tu}=y_{ut}\) is the mass of type-\(t\) agents paired with type \(u\), and \(\sum_u y_{tu}\le\mu_t\). Unmatched mass is allowed. Let \(y^1\) be the census of the given stable matching.
For strict preferences over partner types, define \(R_{t,u}(y)\) as the mass of type \(t\) agents whose partner is strictly worse than \(u\). The matching is stable when, for every acceptable pair of types \(t,u\), it is not the case that both \(R_{t,u}(y)>0\) and \(R_{u,t}(y)>0\). Thus blocking is a positive-measure event: two type classes block whenever positive mass on both sides would prefer to deviate. The normalized symmetric-difference distance is \(\delta(y,y^1)=\frac12\sum_{t,u}|y_{tu}-y^1_{tu}|\). Clearing denominators gives the corresponding finite cloned instance, and \(\delta\) becomes \(|M_1\triangle M_2|/N\).
My lead problem is:
\(\mathsf{Continuous\text{-}AdaptSR}_{\infty}\). The input is \((T,\mu,\succ,y^1,P,\kappa)\), where \(y^1\) is stable, \(P\) is a set of forbidden type pairs, every pair in \(P\) has positive mass in \(y^1\), and \(\kappa\in\mathbb{Q}_{\ge0}\). The question is whether there exists a stable mass matching \(y\) such that \(y_e=0\) for every \(e\in P\) and \(\delta(y,y^1)\le\kappa\).
This is a continuous, cohort-level version of the paper’s “Adapt SR to Forced and Forbidden Pairs” problem with \(Q=\varnothing\). A solution is the mass matching \(y\), together with a measurable pairing realizing its type-pair census.
The anchor is Theorem 1, proved in this paper: “Adapt SR to Forced and Forbidden Pairs is NP-hard, even if \(Q=\varnothing\) and \(P\subseteq M_1\).” The expected classification of the continuous problem is Class B: hardness transfers.
The reason is that the reduction’s combinatorics live in the preference topology, namely the graph used in the reduction from Independent Set, rather than in the number of named agents. Given \((G,\ell)\), create the same ten role types \(a_i^v,b_i^v\) for each \(v\in V(G)\), assign every role type mass \(1/(10|V(G)|)\), and copy the paper’s preference lists, including the neighbour list of \(a_2^v\). Let \(y^1\) encode \(M_1\), forbid every type pair \(\{a_2^v,b_2^v\}\), and set \(\kappa=(8|V(G)|-4\ell)/(10|V(G)|)\).
The intended selected and unselected gadget matchings have exactly the same normalized distances as in the proof: \(4/(10|V(G)|)\) per selected vertex and \(8/(10|V(G)|)\) per unselected vertex. More importantly, continuization does not obviously create a fractional independent set. If positive mass of gadget \(v\) uses the selected branch and positive mass of adjacent gadget \(w\) does likewise, the corresponding positive masses of \(a_2^v\) and \(a_2^w\) mutually prefer each other to their assigned partners, producing a blocking pair. The forbidden pair \(\{a_2^v,b_2^v\}\) similarly prevents a positive mixture of the two local branches. Thus the support of the selected branches should still be an independent set, preserving the reduction.
This would be hardness caused by the agenda encoded in the type-preference graph, not by population multiplicity. It is exactly the sort of Class B phenomenon the programme predicts: making many agents interchangeable does not destroy combinatorics carried by alternatives, compatibility relations, or preference topology.
A second, more ambitious anchor is Theorem 2, also proved here: “Adapt SR to Forced and Forbidden Pairs can be solved in \(O(2^{|P\cap M_1|}\cdot n\cdot m)\) time.” Its continuous counterpart is:
\(\mathsf{Parameterized\text{-}Continuous\text{-}AdaptSR}_{\infty}\). The input is \((T,\mu,\succ,y^1,Q,P,q,\kappa)\), where \(q_e\) is a required mass for each forced type pair \(e\in Q\). The question is whether there exists a stable mass matching \(y\) satisfying \(y_e\ge q_e\) for \(e\in Q\), \(y_e=0\) for \(e\in P\), and \(\delta(y,y^1)\le\kappa\). The parameter is \(p=|\{e\in P:y^1_e>0\}|\), the number of forbidden cohort relations currently used by the default matching.
I would expect this problem to be Class A, probably fixed-parameter tractable in \(p\) with running time \(f(p)\operatorname{poly}(\tau,L)\), where \(L\) is the encoding length of the rational data. The paper’s algorithm branches only on which endpoint improves across each initially forbidden pair and then exploits the rotation structure. In the mass setting, the natural analogue would branch on the finitely many forbidden type relations and solve the resulting type-level predecessor constraints by a compressed rotation or configuration formulation. The important gain is that the running time should depend on \(\tau\), not on the hidden number \(N\) of cloned agents.
This second claim is less secure than the first. The paper’s rotation poset is defined for named-agent instances, while a mass matching can split one type across several partners. It is an open question whether every stable mass matching has a sufficiently compact rotation representation, or whether fractional support creates a new continuum-specific obstruction. That is precisely a worthwhile question generated by the mirror.
The proposed mirror is author-recognizable. The paper itself motivates the problem through company pair programming, reviewer conflicts, school-choice reallocations, and pairs becoming unavailable over time. Replacing a named developer or reviewer by a large cohort with identical matching-relevant information preserves the paper’s operation: start from a stable assignment, impose forced or forbidden relationships, and minimize reassignment. What changes is only the granularity at which a constraint is imposed: a forbidden type pair means that the whole corresponding cohort relation is unavailable. That is a natural high-multiplicity extension, not an unrelated mean-field model.
The main weakness is that the paper’s original objective counts named edges. In the mirror I count type-pair mass, so two matchings with the same cohort census are equally close even if different clone identities are paired. That is appropriate for an anonymous repeated market, but not for a setting where relationship history matters. A second weakness is that exact continuum stability is support-based and disjunctive rather than automatically linear. If one instead convexifies stability and permits averaged blocking constraints, the Independent Set reduction may disappear; that would be a different, easier problem.
So I would scope the positive claim narrowly: Theorem 1 has a strong continuous mirror with expected Class B hardness transfer, and Theorem 2 gives a natural parameterized Class A research question. I would not claim that Proposition 1, Proposition 2, or the ties variants transfer automatically. The decisive follow-up is to prove rational-clone equivalence for stable mass matchings and determine whether the paper’s rotation machinery survives type compression.
The strongest case against is that the proposed mirror silently changes the problem in two fundamental ways.
The paper’s Stable Roommates model has strict preferences over named agents, and its objective \(\lvert M_1\triangle M_2\rvert\) tracks named relationships. A type census \(y^1\) does not contain that information. Two new matchings can have the same type-pair census while preserving completely different incumbent pairs. If incumbent relationships matter, the type must include the incumbent partner or the identity of the agent, destroying the multiplicity gain. If incumbent history does not matter, then the objective has been replaced by a cohort-level reassignment cost.
There is also a stability mismatch. Clones with the same partner type are indifferent among the individual clones, so the mass model is really a ties model with a positive-measure blocking convention. Adding arbitrary clone-level tie-breaks restores strict preferences only by introducing information that the type abstraction was supposed to remove. Different tie-breaks can affect which individual pairs survive and hence the adaptation distance. Thus the paper’s strict-preference rotation theory does not automatically descend to the continuum.
This is a serious objection to the proposed Theorem 2 mirror. Its algorithm relies on a bijection between individual stable matchings and closed complete sets of rotations. A type may be split across several partners, so there is no longer a single stable partner or a single rotation state for that type. A forbidden type pair may be removed by changing an arbitrarily small mass, whereas the paper’s forbidden edge is all-or-nothing. The parameter \(\lvert P\cap M_1\rvert\) therefore has no canonical continuous counterpart. One can formulate a better model using a mass transport from incumbent type-pairs to new type-pairs, but that is a new optimization problem; Theorem 2 gives no evidence for the claimed \(f(p)\operatorname{poly}(\tau,L)\) algorithm.
Unfortunately, this does not defeat the strongest anchor, Theorem 1. The proponent’s reduction can plausibly be lifted by making \(K\) interchangeable copies of every role type \(a_i^v,b_i^v\). After clearing denominators, a rational mass matching becomes a finite cloned matching. In this particular gadget, mixing the selected and unselected branches creates a positive-measure blocking pair, and positive mass on selected branches for adjacent vertices creates the same blocking pair used in the Independent Set reduction. Thus the type-level support can still encode an independent set. The fact that the reduction has \(10\lvert V(G)\rvert\) distinct types is not fatal under the programme’s definition: one may take \(K\) arbitrarily large, so the population still has high multiplicity.
Nor is “this is only cloning” an available objection. A Class B hardness transfer is explicitly a worthwhile outcome of the programme, even if the continuum does not make the problem easier.
So I would not sign the requested universal negative. The identity and stability objections substantially weaken the proposed Theorem 2 story, but Theorem 1 has a credible author-recognizable high-multiplicity mirror. The honest negative case is therefore weak precisely where it matters: it cannot rule out every worthwhile continuous formulation.
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.