| paper | d4-conf-sagt-2021-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite type sets \(I\) and \(J\), rational masses \(p_i\) and \(q_j\) summing to \(1\) on each side, and strict rankings of opposite-side types, decide whether there is a coupling \(x_{ij}\geq 0\) with row sums \(p_i\) and column sums \(q_j\) such that, on the positive cells \((i,j)\), neither side’s directed envy graph has a cycle. In the \(I\)-side graph, an arc from \((i,j)\) to \((i',j')\) means \(j'\succ_i j\); in the \(J\)-side graph, it means \(i'\succ_j i\).
A nonatomic two-sided matching market with type masses \((p_i)_{i\in I}\) and \((q_j)_{j\in J}\), where members of each type share rankings over counterpart types and are tied among members of a counterpart type. The decision variable is a fractional coupling \(x\) with those marginals; the objective is feasibility, and coalitional exchange-stability means the positive-cell envy graph is acyclic for each side.
The mirror covers Theorem 2’s complete-preference marriage hardness result; it does not cover the roommates result, bounded-list algorithms, or the local-search result.
The strongest mirror I see is the paper’s complete-preference Coalitional Exchange-Stable Marriage result, as a question about whether a fractional matching between preference types exists. It is a credible high-multiplicity question: for example, a large student homestay programme might match many students to many hosts, with people grouped by their full preferences over host or student categories. The regime I have in mind has thousands of placements but dozens or perhaps hundreds of distinct types. Each type is a genuine cohort whose members are interchangeable for the problem; if exact preference profiles leave nearly every person in a different type, this mirror is no longer the right one.
My anchor is Theorem 2, proved in this paper: deciding whether a Stable Marriage instance admits a coalitional exchange-stable matching is NP-complete even when preferences are complete and strict; the same is true for the Stable Roommates version. The theorem concerns existence of a matching with no exchange-blocking coalition. I would mirror its marriage result. The paper’s complete-preference case gives the continuous problem a natural perfect-matching requirement: both sides’ total mass is matched.
Here is the continuous problem I would hand to a prover. Call it Coalitional Exchange-Stable Marriage\(_\infty\). An instance consists of finite type sets \(I\) and \(J\) for the two sides, with rational masses \(p_i\geq 0\) and \(q_j\geq 0\), each side’s masses summing to \(1\), and complete rankings of the opposite-side types. Each type is a full description for the problem: its members share the same ranking of counterpart types. A matching is a nonnegative matrix \(x=(x_{ij})\) satisfying
\[
\sum_{j\in J}x_{ij}=p_i
\quad\text{and}\quad
\sum_{i\in I}x_{ij}=q_j.
\]
Thus \(x_{ij}\) is the fraction of each population type paired across that type pair.
To state stability, make a directed graph whose vertices are the occupied pairs \((i,j)\) with \(x_{ij}>0\). For the \(I\)-side, add an arc from \((i,j)\) to \((i',j')\) whenever \(j'\succ_i j\); for the \(J\)-side, add an arc whenever \(i'\succ_j i\). The question is whether there is a coupling \(x\) for which both graphs are acyclic. A directed cycle represents a finite coalition whose members can each obtain a more-preferred partner type by exchanging partners. Since every cell on the cycle has positive mass, the continuum contains enough distinct members of those types to realize the coalition. A solution is the rational coupling matrix \(x\); this is a feasibility problem, so it has no separate optimization objective.
Members of a type are tied over individual members of the same counterpart type, while their ranking across types is strict. That is a real change from Theorem 2’s strict individual rankings, but it preserves the substance of its question: can the population be paired so that no coalition can improve through partner exchanges? The authors say in their conclusion that their results transfer to preferences with ties, which makes this type-based formulation especially plausible as their problem.
My provisional expectation is continuum-specific hardness (Class C), not a claim that Theorem 2’s hardness transfers. The coupling lies in a transportation polytope, but coalitional stability constrains its support: choosing both of two occupied cells may create an envy cycle. Fractional mass could make a stable coupling possible where no discrete matching exists, so the paper’s NP-hardness alone proves nothing about this version. Conversely, the support constraints leave substantial combinatorial structure for a reduction to exploit.
The weakest point is that the paper’s reductions rely on distinct agents and carefully linked gadgets. Collapsing agents into preference types, then allowing fractional couplings, could erase that structure or even make stable couplings routinely available. That is a real risk, not a reason to avoid the question: determining whether fractional mass dissolves the obstruction is exactly the computational question the mirror exposes. The useful next questions are whether this problem has a polynomial-time algorithm in the number of types and mass bit length, whether every instance admits such a coupling, and when a fractional yes-instance can be realized by a discrete matching. This case covers Theorem 2’s complete-preference marriage hardness result; it does not claim to mirror the paper’s local-search result or its bounded-list algorithms.
Theorem 2 is a genuine computational anchor: it proves NP-completeness for CESM, including complete preferences. The strongest case against the mirror is about whether the proposed population types preserve the object that theorem studies.
In the paper, preferences rank named people, and the reductions use particular agents as gadget roles with carefully chosen rankings. A high-multiplicity version that preserves those distinctions needs types that retain those roles; their number then grows with the construction. If instead types rank counterpart categories, members of a category become interchangeable and tied with one another. That is a sensible matching model, and the paper’s conclusion makes ties plausible, but it removes distinctions the strict-preference instance can use. The proponent’s model is therefore a defensible new problem, though its connection to Theorem 2 is less direct than the label “continuous mirror” suggests.
The stronger version—give each gadget role positive mass and test the support of a fractional coupling for envy cycles—still faces this fidelity issue. In the discrete reduction, each agent occupies one matching edge. In a coupling, a role’s mass can be split across several edges. The paper’s gadget argument is about perfect matchings; it does not establish that its constraints survive this splitting. That leaves the mirror’s computational direction open. This does not make the question unworthy: discovering that fractional mass changes the problem is part of the programme. It does mean the theorem supplies little evidence that this particular mirror will illuminate the paper’s hardness result.
There is also a limit-model concern. Under the proposed cycle test, any positive mass in an occupied cell supplies enough distinct agents for a finite blocking coalition, however small that mass is. Thus stability reacts to whether a cell has positive mass, while its magnitude matters only through which couplings are feasible. A fixed lower bound on type masses would reduce that concern, but would narrow the proposed model and would not preserve every high-multiplicity instance.
These objections weaken the case; they do not defeat it. The type-based version is coherent, and large matching markets with shared rankings over categories are plausible. I cannot make an honest universal case that no worthwhile mirror exists. The negative case is strongest on fidelity to the paper’s named-person model, and weakest against the claim that the fractional, type-based question is worth studying in its own right.
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.