| paper | d4-conf-sagt-2021-0020 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(\tau\) and \(L\); every welfare-maximizing feasible allocation is stable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given finite types \(T\), rational masses \(\mu_t>0\) summing to \(1\), and symmetric binary compatibilities \(a_{ts}=a_{st}\), choose \(y_S\geq 0\) for every multiset \(S\) of three types, with \(\sum_S m_t(S)y_S=\mu_t\) for each \(t\). Define \(u_t(S)=\sum_s (m_s(S)-\mathbf{1}[s=t])a_{ts}\) and \(D_t(S;y)=\sum_{R\ni t}m_t(R)y_R\mathbf{1}[u_t(S)>u_t(R)]\). Require that no \(S\) has \(D_t(S;y)>0\) for every distinct type \(t\) in \(S\). Find a stable \(y\) maximizing \(W(y)=\sum_S y_S\sum_t m_t(S)u_t(S)\), or report that no stable \(y\) exists.
A continuum roommate market with complete compatibility types, rational population masses, and mass assignments to triple compositions. A composition blocks when every type represented has positive mass of residents who strictly prefer it; the objective is total per-capita utilitarian welfare.
The paper guarantees a stable matching in every finite symmetric-binary instance, but gives no such guarantee for the proposed mass-stability rule, so its welfare optimum may not exist.
fatal: False
The mirror covers Theorem 3’s NP-hard maximum-welfare stable matching problem. It leaves the paper’s stable-matching existence results and its 2-approximation result for maximum welfare unaddressed.
The strongest mirror is the paper’s maximum-welfare problem in a large shared-housing market. Imagine an authority assigning a very large applicant population—say, 100,000 people—to three-person flats, where applicants fall into a modest number \(\tau\) of complete roommate-compatibility types. Two people of types \(t\) and \(s\) have the same binary compatibility value \(a_{ts}\), with \(a_{ts}=a_{st}\). A type includes everything relevant to this matching problem, so members of a type are interchangeable. The mass \(\mu_t\) is the fraction of applicants of type \(t\), not a count of named people.
My anchor is Theorem 3, proved in this paper: 3D-SR-SAS-BIN-MAXUW is NP-hard. The problem is to find a stable matching maximizing utilitarian welfare—the sum of agents’ utilities—when every agent’s values are binary and symmetric. The paper proves the result by reduction from Partition Into Triangles. [Theorem 3 in the paper](https://eprints.gla.ac.uk/245422/2/245422.pdf)
Here is the continuous problem I would ask: Maximum-Welfare Stable Roommate Massing. An instance consists of a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), and a symmetric binary compatibility matrix \(a_{ts}\). Let \(\mathcal M_3(T)\) be the multisets of three types. For each \(S\in\mathcal M_3(T)\), choose \(y_S\geq0\), the mass of flats with type composition \(S\). If \(m_t(S)\) counts occurrences of \(t\) in \(S\), require
\[
\sum_{S\in\mathcal M_3(T)}m_t(S)y_S=\mu_t
\quad\text{for every }t\in T.
\]
A type-\(t\) resident in a flat of composition \(S\) gets utility
\[
u_t(S)=\sum_{s\in T}\bigl(m_s(S)-\mathbf 1[s=t]\bigr)a_{ts}.
\]
The objective is to return a stable assignment \(y\) maximizing per-capita welfare
\[
W(y)=\sum_{S\in\mathcal M_3(T)}y_S
\sum_{t\in T}m_t(S)u_t(S).
\]
Stability means that no type composition can form a blocking coalition of positive mass. Precisely, for a candidate composition \(S\) and each distinct type \(t\) appearing in it, let
\[
D_t(S;y)=
\sum_{\substack{R\in\mathcal M_3(T)\\t\in R}}
m_t(R)y_R\,\mathbf 1[u_t(S)>u_t(R)].
\]
Composition \(S\) blocks if \(D_t(S;y)>0\) for every type appearing in \(S\): then a sufficiently small positive mass of strictly improving residents can be assembled into flats of composition \(S\). A solution is an exact rational vector \(y\) satisfying the covering and stability conditions and attaining maximum \(W(y)\).
This is a credible analogue of the authors’ problem: it retains triples, additive binary preferences, strict blocking, symmetry, and the same welfare objective, while making the population itself divisible. The paper’s discussion of symmetric “friendship” valuations and type-based roommate models makes this kind of market legible to its authors; existing type-based work supports the regime’s plausibility, rather than making this mirror redundant. The mirror covers Theorem 3 only, not the paper’s existence or approximation results.
My tentative expectation is Class C: continuum-specific hardness, because the stability conditions choose among many type-level assignment patterns and form a nonconvex union of linear faces. That is a conjectural direction, not something Theorem 3 proves. In fact, its PIT reduction is also the mirror’s weakest point: arbitrary graph neighborhoods may require \(\tau\) to grow with the number of agents, and divisible mass can turn the reduction’s full-welfare threshold into a fractional triangle-cover LP. So the discrete hardness may dissolve. The useful next questions are whether stability’s support choices admit a polynomial algorithm or create hardness when \(\tau\) varies, and whether optimal mass assignments can be rounded to stable discrete matchings with a welfare guarantee.
The strongest skeptical case is a gap between the paper’s stability notion and the proposed mass version. In the continuum, \(D_t(S;y)>0\) means that any positive pool of type-\(t\) residents can be split to fill all the type-\(t\) places in a blocking triple. In a finite matching, one resident cannot fill two places. So a discrete stable matching can become blocked after its type counts are converted to masses. Theorem 3’s hardness result therefore does not automatically transfer to this version, and the proposed model may optimize over a strictly smaller set of matchings—or have no stable mass assignment even though the finite symmetric-binary theorem guarantees a stable matching.
There is also a mismatch between the reduction and the most persuasive large-market scenario. The Partition Into Triangles construction builds agents with graph-specific neighborhoods; representing those neighborhoods as complete types can require \(\tau\) to grow with the instance. A housing market with a modest number of repeated compatibility profiles is plausible, but it is not what that reduction establishes. The authors would need a bridge from their named-agent theorem to that repeated-type regime, or an independent reason to study the mass problem.
Those concerns make the proposed question less securely anchored than the case for suggests. They do not defeat it. Positive-mass blocking is a coherent continuum stability concept, the welfare objective aggregates over types without losing needed identities, and the nonconvex stability conditions leave a genuine computational problem. The paper itself points toward symmetric friendship valuations and cites type-based roommate work, which makes the housing scenario recognizable to its authors. Nor does the earlier type-based literature settle maximum-welfare stable matching in a continuous population.
So I cannot honestly make a convincing universal case that no worthwhile mirror exists. Theorem 3 survives: the mass version is well posed and worth asking about, even though its discrete-to-continuous relationship needs careful study. The honest negative finding is that the proponent has not yet shown that this mirror explains or inherits the paper’s NP-hardness.
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.