| paper | Stable Marriage with Covering Constraints-A Complete Computational Trichotomy |
| authors | Matthias Mnich, Ildikó Schlotter |
| venue | SAGT 2017 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 9
statement extracted from the paper’s text layer
Given rational masses μ_i and ν_j on male and female types, with each type specifying acceptable counterpart types, a strict order over them, and whether it is distinguished, find a mass matching x covering all distinguished female mass and minimizing \(\operatorname{BP}(x)=\sum_{(i,j)\in E}u^M_{ij}(x)u^W_{ji}(x)\), where every female type has at most two acceptable male types and every male type has at most three acceptable female types; equivalently, decide whether \(\operatorname{BP}(x)\le B\).
A nonatomic typed stable-marriage-with-covering model: type masses \(\mu_i,\nu_j\), matching variables \(x_{ij}\), capacity constraints, full coverage of distinguished female types, and a normalized cross-type blocking density as the objective.
The paper's strict named-agent blocking-pair count does not uniquely determine the proposed continuum objective: the product density requires exchangeable type-level preferences and an explicit normalization convention.
fatal: False
The mirror covers Theorem 9's NP-hardness result for SMC-1 with Δ_W=2 and Δ_M=3. It leaves the paper's other hardness, FPT, polynomial-time, approximation, and full parameterized-trichotomy results untouched.
My strongest mirror is a high-multiplicity version of SMC-1, the one-sided Stable Marriage with Covering Constraints problem. I would call it Continuous Typed SMC-1, and this is my lead.
The population consists of male types \(i\in\mathcal M\) and female types \(j\in\mathcal W\), with rational masses \(\mu_i,\nu_j\), normalized so that \(\sum_i\mu_i=\sum_j\nu_j=1\). A type records the complete information relevant to the market: acceptable counterpart types, their preference order, and whether the type is distinguished. Thus agents of the same type have the same preferences, acceptability constraints, and covering status.
Each man type \(i\) has a strict order over acceptable woman types, and each woman type \(j\) has a strict order over acceptable man types. Let \(E\subseteq\mathcal M\times\mathcal W\) be the symmetric acceptability relation. The decision variable is a mass matching \(x=(x_{ij})_{(i,j)\in E}\), where \(x_{ij}\) is the mass of type-\(i\) men matched to type-\(j\) women. It must satisfy \(x_{ij}\ge 0\), \(\sum_jx_{ij}\le\mu_i\), and \(\sum_ix_{ij}\le\nu_j\). If \(\mathcal W^\star\) is the set of distinguished woman types, every such type must be fully covered: \(\sum_i x_{ij}=\nu_j\) for every \(j\in\mathcal W^\star\).
For an acceptable pair \((i,j)\), let \(u^M_{ij}(x)\) be the mass of type-\(i\) men who are unmatched or matched below \(j\), and let \(u^W_{ji}(x)\) be the analogous mass of type-\(j\) women who are unmatched or matched below \(i\). Explicitly, \(u^M_{ij}(x)=\mu_i-\sum_{j'\succeq_i j}x_{ij'}\), and \(u^W_{ji}(x)=\nu_j-\sum_{i'\succeq_j i}x_{i'j}\). The normalized mass of blocking pairs is then \(\operatorname{BP}(x)=\sum_{(i,j)\in E}u^M_{ij}(x)u^W_{ji}(x)\). The problem is to minimize \(\operatorname{BP}(x)\), or equivalently to decide whether some feasible \(x\) has \(\operatorname{BP}(x)\le B\).
The product is not an arbitrary relaxation. If each type is cloned \(N\) times, with \(\mu_i=a_i/N\) and \(\nu_j=b_j/N\), then \(x_{ij}=z_{ij}/N\) represents \(z_{ij}\) matched clone pairs, and \(N^2\operatorname{BP}(x)\) is exactly the number of blocking clone pairs in the complete type-level blow-up. Thus the continuous objective is the normalized high-multiplicity version of the paper’s blocking-pair count. The only forced co-modification is that members of one type are exchangeable, so preferences are ordered over counterpart types rather than named individuals.
The relevant regime is a large school-admission or hospital-recruitment market with recurring cohorts. Applicants may share a type defined by qualification band, specialty, geography, and preference policy; hospital slots may share a type defined by specialty, location, and service requirement. Rural or otherwise essential slot types are distinguished and must receive their entire mass. A plausible instance might have hundreds of thousands of applicants and slots but only dozens of applicant and slot types. This is precisely the sort of setting the paper itself discusses when motivating lower quotas, school-choice categories, and cloning hospitals to unit upper quotas.
The anchor is Theorem 9, proved in this paper: “SMC-1 is NP-hard even if \(\Delta_W=2\) and \(\Delta_M=3\).” Here \(\Delta_W\) is the maximum preference-list length of a woman and \(\Delta_M\) that of a man. The proof reduces from Vertex Cover. Given a graph \(G\) and integer \(k\), the authors construct an SMC-1 instance with only distinguished women, every woman finding at most two men acceptable, and every man finding at most three women acceptable. The instance admits a feasible matching with at most \(|V(G)|+k\) blocking pairs if and only if \(G\) has a vertex cover of size at most \(k\).
My continuous problem \( \mathrm{C\text{-}SMC\text{-}1}(2,3) \) is exactly the typed mass problem above under the restrictions that every woman type has at most two acceptable man types and every man type has at most three acceptable woman types. It asks for the minimum normalized mass of blocking relationships while covering all distinguished woman mass.
I expect this problem to be hard for continuum-specific reasons, i.e. a likely Class C problem, although Class A and Class B remain live alternatives. Theorem 9’s reduction uses binary local choices inside vertex gadgets. A mass matching can split a type across several counterpart types, so the discrete Vertex Cover argument does not automatically transfer. On the other hand, \(\operatorname{BP}(x)\) is a quadratic function of the matching masses, so the continuum formulation does not automatically collapse to the LP or min-cost-flow machinery used for ordinary matching. The first substantive questions are therefore whether the blocking-mass objective admits an extended convex formulation, whether a support-preserving rounding theorem restores the discrete hardness, and whether bounded preference lists suffice for either result.
This mirror deliberately covers only Theorem 9, not the paper’s entire trichotomy. It preserves the authors’ two-sided preferences, incomplete acceptability, covering constraints, and blocking-pair objective; it does not replace stable matching by a generic fractional allocation problem.
The weakest point is the loss of named-agent identity. Theorem 9’s gadgets rely on sparse, identity-specific connections, whereas the typed blow-up turns every acceptable type pair into a mass of interchangeable relationships. Also, type-level exchangeability naturally introduces ties among clones, while the paper’s base model uses strict individual rankings. I would therefore present this as a genuine, author-recognisable high-multiplicity extension—not as a claim that Theorem 9 already proves NP-hardness of the continuous problem. That limitation does not undermine the mirror itself: it identifies exactly the computational question created when the paper’s stable-marriage-with-covering problem is placed in a realistic repeated-cohort market.
The strongest case against this anchor is that Theorem 9’s objective is inherently identity-level. A blocking pair is a pair of named agents under strict preferences. Once agents are collapsed into types, one must choose between two incompatible repairs.
If clone identities and strict rankings are retained, then the proposed types are not complete types: behaviour can depend on the within-type ordering of counterpart clones. Preserving the gadget’s sparse, identity-specific acceptability structure therefore requires making essentially every gadget role its own type. Repeating the entire constructed graph \(N\) times is mathematically possible, but it is a homogeneous blow-up of an instance, not a convincing population model in which many interchangeable agents share a small number of meaningful market types.
If instead one uses weak preferences over counterpart types, then the proponent’s quantity
\[
\operatorname{BP}(x)=\sum_{(i,j)\in E}u^M_{ij}(x)u^W_{ji}(x)
\]
is not the paper’s number of blocking pairs. It is a density of potentially blocking cross-type pairs, obtained after choosing an \(N^2\) normalization. The paper’s threshold \(b=|V(G)|+k\) does not survive that limit: its meaning depends on counting individual exceptions. Other equally natural continuizations would minimize the fraction of agents involved in at least one blocking pair, or require the absence of any blocking type pair. These objectives are genuinely different, and the paper gives no reason to privilege the product density.
That is a real weakness in the stated mirror: its claim that \(N^2\operatorname{BP}(x)\) is “exactly” the clone blocking-pair count is false under the paper’s strict preference model, except after imposing additional tie-breaking or type-level conventions. The conventions are not cosmetic; they change what stability and a blocking pair mean.
However, this does not defeat the stronger mirror. One can explicitly define a high-multiplicity stable-marriage model with weak preferences over types, type-level covering constraints, and normalized blocking-pair density. A repeated hospital or school-choice market with many agents sharing qualification, geography, and preference-policy types is plausible, and the paper itself supplies the application setting. The type graph may encode the input instance while the population supplies the multiplicity.
Thus the negative case cannot honestly establish that no worthwhile mirror exists. It can show that the proponent’s formulation is not a literal continuization of Theorem 9 and that the bridge from individual blocking counts to block density needs to be made explicit. But after that repair, Theorem 9 remains a legitimate computational mirror. The universal negative therefore fails; at most, this is a caution that the continuous problem is a new, carefully defined high-multiplicity variant rather than the theorem transplanted unchanged.
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.