| paper | d4-conf-wine-2020-0039 |
| 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: \(\mathsf{P}\): every valid instance admits a stable assignment. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.8
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), and a strict master order over multisets of two types that induces each type’s ranking, decide whether there are \(\lambda_r\ge 0\), one for each multiset \(r\) of three types, such that \(\sum_r \nu_t(r)\lambda_r=\mu_t\) for every \(t\in T\) and no triple multiset \(q\) has \(B_{t,q}(\lambda)>0\) for every type \(t\) occurring in \(q\). Here \(\nu_t(r)\) is the number of copies of \(t\) in \(r\), and \(B_{t,q}(\lambda)\) is the mass of type-\(t\) residents assigned to pairs of co-resident types ranked below \(q\setminus\{t\}\).
A continuum of residents with finite support \(T\) and rational type masses \(\mu\), assigned to indivisible three-person rooms represented by masses \(\lambda_r\) over multisets of three types. Each type ranks pairs of co-resident types by a common strict master order; a triple blocks when every distinct type in it has positive mass of residents who prefer the proposed co-resident types to their current assignment.
The mirror covers Theorem 3.8’s complete-preference, common-master-list case. It leaves the master-poset parameter results and the incomplete-preference result unmirrored.
The strongest mirror I believe is a clone invariant version of 3-dimensional stable roommates, in a large first-year housing cohort. Suppose thousands of residents are grouped into a modest number \(\tau\) of complete compatibility types: two residents have the same type exactly when they have the same preferences over every possible pair of co-resident types. Their rankings come from a common master list of type-pairs, perhaps based on a shared compatibility score. This is a credible high-multiplicity regime when preferences are driven by a finite questionnaire or set of housing criteria. Each person still gets one whole room with two other people; mass only lets us describe how the cohort is divided among room compositions.
The anchor is Theorem 3.8, proved in this paper: 3-DSR-ML is NP-complete. It decides whether a stable matching exists when \(d=3\), every agent has complete preferences over pairs of other agents, and those preferences are derived by deleting pairs containing that agent from one strict master list of pairs. The paper proves the result by reduction from 1-in-3 Positive 3-Occurrence-SAT, whose NP-completeness it cites from elsewhere.
My lead mirror is Continuous 3-DSR-ML by Types. An instance gives a finite support \(T\) of resident types, rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\), and a strict master ordering of the unordered *multisets* of two types. The master ordering induces each type’s strict ranking over possible pairs of co-resident types. Multisets matter because two residents in a room may share a type; another resident of that type is not the resident whose preferences we are describing.
A proposed solution is a nonnegative real number \(\lambda_r\) for each multiset \(r\) of three types. It means that mass \(\lambda_r\) lives in rooms of composition \(r\). It must use all the population:
\[
\sum_{r\in\mathcal M_3(T)} \nu_t(r)\lambda_r=\mu_t
\qquad\text{for every }t\in T,
\]
where \(\nu_t(r)\) is the number of times type \(t\) occurs in \(r\). For a proposed blocking room composition \(q\), let \(B_{t,q}(\lambda)\) be the mass of type-\(t\) residents currently assigned to pairs of co-resident types they rank below \(q\setminus\{t\}\). The solution is stable precisely when, for every \(q\), at least one type \(t\) in \(q\) has \(B_{t,q}(\lambda)=0\). If all participating types have positive such mass, we can take a small amount from each and form a positive mass of blocking rooms. The question is whether a stable \(\lambda\) exists; if so, the \(\lambda_r\) are the requested witness.
This keeps the paper’s central question and blocking rule intact while making the population the continuous object. It also gives a high-multiplicity dictionary: a stable \(\lambda\) can be realized as an ordinary matching in a sufficiently large integer replication of the type proportions, and a stable matching in such a replication gives a \(\lambda\). It covers Theorem 3.8’s complete-preference, common-master-list case; it does not try to mirror the paper’s poset parameterizations or its incomplete-preference result.
My forecast is Class C, continuum-specific hardness, but only as a working expectation. The theorem’s reduction uses carefully distinguished clause and occurrence agents, so its NP-hardness does not automatically survive when residents of a type are interchangeable. On the other hand, the continuous problem still has a support-sized set of possible room compositions, and stability creates coupled zero-mass conditions across those compositions. I see no immediate reason those conditions collapse to an LP. The concrete questions are whether this existence problem is polynomial in \(\tau\) and the rational input length \(L\), and whether the SAT hardness can be rebuilt using types and mass rather than identity-specific agents.
The weakest point is the change from strict preferences over named individuals to preferences over type-pairs: residents of the same type are indifferent between particular individuals of a given type, even though their type-pair ranking is strict. That is the necessary symmetry for high multiplicity, but a referee could regard it as a tied-preference variant rather than a direct instance of the paper’s strict individual-ranking problem. I think the authors would recognize the mirror because it preserves triple formation, stability, and the master-list structure; I would not claim that Theorem 3.8 itself settles its complexity.
The strongest negative case is about what Theorem 3.8 actually anchors. It is a genuine computational result: deciding whether a stable matching exists is NP-complete. So “no named result to mirror” does not apply.
The difficulty is that the theorem’s agents are named and their preferences rank pairs of named agents. Its master list is an order on those pairs. The reduction uses that addressability: clause agents, occurrence agents, and the six-agent obstruction gadgets each have specific roles. A literal population limit that keeps those preferences does not obviously group many agents into a small set of interchangeable types.
The proponent’s stronger version avoids that problem by making preferences over *type compositions* the model itself. That is coherent: a mass \(\lambda_r\) is assigned to each triple of types, and a blocking composition needs positive mass of every participating type that strictly prefers it. But this changes the preference domain and stability semantics from the paper’s strict rankings over named people to anonymous rankings over types. It is a sensible new problem, yet Theorem 3.8 does not establish that the paper’s computational contribution carries over to it. If instead types retain the gadgets’ distinct roles, the encoding may need support growing with the formula. That still leaves a valid complexity question in \(\tau\); it just weakens the claim that this paper supplies a natural, compressed mirror.
The nearby literature makes the type-based model recognizable, but does not settle this question: there is work on continuum roommate markets with finitely many types, and on computational complexity for fractional pairwise matchings. Those are analytic or pairwise-fractional neighbors, not a computational treatment of stable triple allocations by type masses. [Carmona on continuous roommate markets](https://onlinelibrary.wiley.com/doi/full/10.3982/TE5915), [Chen, Roy, and Sorge on fractional matchings](https://www.ijcai.org/proceedings/2021/13).
So the best case against is that the paper’s theorem and the attractive continuous model do not yet meet at a demonstrated high-multiplicity translation: preserve the paper’s named-agent semantics and type compression is questionable; adopt anonymous type preferences and the result becomes a newly specified stable-core problem. That is a reason to demand a sharper bridge before prioritizing this mirror, not a decisive reason to reject it. The honest negative case is weak: the type-based triple problem is well-posed, and I cannot convincingly argue that the authors would not recognize it as worthwhile.
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.