| paper | d4-conf-aaai-2016-0702 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set \(A\) of complete person types and room classes \(Q\), with binary happiness values \(h_{ab}\) and room values \(v_{aq}\), rational type masses \(\mu_a \ge 0\) summing to \(1\), and rational room supplies \(\rho_q \ge 0\) summing to \(\tfrac12\), choose nonnegative rational masses \(x_{abq}\) for \(a \le b\) and \(q \in Q\) to maximize \(\sum_{q \in Q}\sum_{a \le b} x_{abq}(h_{ab}+h_{ba}+v_{aq}+v_{bq})\), subject to \(\sum_{a \le b}x_{abq}=\rho_q\) for each \(q\) and \(2\sum_q x_{aaq}+\sum_{b<a,q}x_{baq}+\sum_{b>a,q}x_{abq}=\mu_a\) for each \(a\).
A nonatomic population with rational masses of complete person types and rational supplies of room classes. The decision is how much mass to assign to each type-pair and room-class bundle; each individual receives a whole room and roommate, while cohort mass can be split. The objective and constraints form a linear program with \(O(|Q||A|^2)\) variables and polynomially many constraints.
The mirror covers Theorem 1’s maximum-social-welfare objective. It leaves the stability and envy-freeness results, including the 2-person and 4-person stability results, unaddressed.
I would lead with maximum social welfare, anchored by Theorem 1, proved in this paper. It says that finding a maximum-social-welfare roommate assignment is NP-hard even when every happiness value and room valuation is in \(\{0,1\}\). The proof reduces from Tripartite Triangle Partition: it encodes graph edges as happiness and room values so a triple contributes the maximum welfare exactly when its three vertices form a triangle. This is the paper’s clearest hardness result, and its objective transfers directly to a continuous population.
Call the mirror Roommate Welfare\(_\infty\). Let \(A\) be a finite set of complete person types and \(Q\) a finite set of room classes. A type includes everything relevant to utility: its happiness \(h_{ab}\) toward a person of type \(b\), for every \(b\in A\), and its valuation \(v_{aq}\) for every room class \(q\in Q\). The input gives rational agent masses \(\mu_a\), with \(\sum_{a\in A}\mu_a=1\), and rational room supplies \(\rho_q\), with \(\sum_{q\in Q}\rho_q=\tfrac12\). Keep the anchor’s restriction \(h_{ab},v_{aq}\in\{0,1\}\).
For each unordered pair of types \(a\le b\) and room class \(q\), let \(x_{abq}\) be the mass of rooms occupied by an \(a,b\) pair in class \(q\). The question is to choose nonnegative rational \(x_{abq}\) maximizing
\[ \sum_{q\in Q}\sum_{a\le b}x_{abq} \bigl(h_{ab}+h_{ba}+v_{aq}+v_{bq}\bigr), \]
subject to room supply and agent-mass constraints
\[ \sum_{a\le b}x_{abq}=\rho_q \quad(q\in Q), \]
\[ 2\sum_q x_{aaq} +\sum_{b<a,q}x_{baq} +\sum_{b>a,q}x_{abq} =\mu_a \quad(a\in A). \]
A solution is this mass allocation over complete roommate-and-room bundles. The factor of \(2\) for \(x_{aaq}\) counts the two residents of the same type. Although \(x\) can split a type across bundles, each individual in the nonatomic population still receives one whole room and one whole roommate; it is the cohort mass that is divisible.
A plausible regime is a large university housing system, with tens of thousands of residents but a much smaller set of complete types—for example, types defined by cohort, accessibility needs, and broad compatibility and room-preference profiles. Room classes might represent a few buildings or amenity levels. Residents of one type are interchangeable for every feature this model uses. This is a genuine high-multiplicity setting: the population grows while the number of distinct types and room classes remains modest. Room supply scales with population, as it must when every two residents need a room. The paper itself says rent does not affect social welfare, so omitting rent from this welfare question preserves its objective.
The authors could recognize this as their problem: it assigns people in pairs to rooms, uses the same happiness and room-value terms, and maximizes the same social-welfare quantity. For this mirror, the expected result is Class A, tractable. The formulation is a linear program with \(O(|Q||A|^2)\) variables and polynomially many constraints, so exact rational optimization is polynomial in the type and room-class counts and input bit length. Theorem 1’s hardness can then be understood as tied to integral assignments and graph-specific, individual-level interactions that the high-multiplicity regime does not retain. This is a prediction about the mirror, not a claim that the discrete theorem is invalidated.
The scope here is the paper’s welfare-maximization problem. It does not mirror the 2-person or 4-person stability results, or the envy-freeness results. The natural follow-up questions are how closely finite markets with many copies of each type approach the LP optimum, what additive rounding bounds can be proved in terms of the number of types, and which restrictions on type multiplicity or repeated preferences recover the discrete hardness.
My weakest point is that the paper permits arbitrary person-to-person happiness values and room valuations, while this mirror assumes those values are determined by a comparatively small set of types and room classes. In the paper’s triangle-partition reduction, the graph’s bespoke incidence pattern is central; a market with thousands of residents but only a few compatibility types may not exhibit that structure. Under the programme’s definition of high multiplicity, this is an honest limitation of the regime, rather than a change to the welfare question. The case is strongest when repeated, type-based compatibility is a plausible description of the housing market.
The only proposed anchor is Theorem 1. The strongest objection is that its hardness comes from arbitrary person-to-person values \(h_{ij}\): the Tripartite Triangle Partition reduction encodes a bespoke graph of who values whom. In that construction, a type that preserves every interaction may need to identify each person, so \(\tau\) grows with the instance and the repeated-type housing scenario loses its force. Keeping a small set of types instead imposes block-structured compatibility and leaves out the theorem’s arbitrary incidence pattern. That makes the proposed scenario a restricted variant of the paper’s model.
This does not defeat the better mirror. Roommate markets with recurring compatibility and room-preference profiles are plausible, and the type-level model preserves the paper’s welfare objective: pair happiness plus room valuations, with room supplies scaling to serve the population. The allocation variables divide mass among complete roommate-and-room bundles; in an atomless population, each resident can still receive one whole bundle. The change in interaction structure is the high-multiplicity assumption, not a change of the question that makes the mirror unrecognizable.
So the negative case is weak. Theorem 1’s particular hardness construction may not survive in a fixed, small type space, but that says what its reduction represents, not that a worthwhile continuous welfare question is unavailable. I can’t honestly argue that no plausible scenario produces one.
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.