| paper | Your College Dorm and Dormmates: Fair Resource Sharing with Externalities |
| authors | Jiarui Gan, Bo Li, Yingkai Li |
| venue | JAIR 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4.6
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), two resources with rational capacities \(q_1,q_2\) satisfying \(q_1+q_2=1\), binary type-level externalities \(e_{tu}\), and the valuation pattern \(v_{t1}=1,v_{t2}=0\), decide whether there are assignment masses \(x_{tr}\ge0\) with \(\sum_r x_{tr}=\mu_t\) and \(\sum_t x_{tr}=q_r\) such that every type \(t\) receiving positive mass on resource \(r\) satisfies, for every occupied resource \(s\ne r\), \(v_{tr}\ge v_{ts}\) or \(E_t(r;x)\ge E_t(s;x)\), where \(E_t(r;x)=\sum_{u\in T}e_{tu}x_{ur}\).
A nonatomic high-multiplicity resource-sharing model with complete types \(t\in T\), population mass \(\mu_t\), integral resource bundles, assignment-mass variables \(x_{tr}\), and external utility \(E_t(r;x)=\sum_u e_{tu}x_{ur}\); the decision problem is existence of a mass-PEF assignment.
Type aggregation replaces the paper's arbitrary identity-level externality graph by block-constant population composition, so the Clique reduction and the expected hardness may disappear.
fatal: False
The mirror covers the existence and complexity results in Propositions 4.2 and 4.6 and the capacity-two construction in Theorem 5.6; it leaves the utility guarantees in Propositions 6.1–6.3 and the stronger future notions untreated.
Yes: the paper admits a credible continuous mirror, with Proposition 4.6 as the lead anchor. The mirror is not a fractional-goods reformulation. It makes the population continuous while preserving whole-resource assignments and externalities.
Take a finite set of complete agent types \(T\), with mass distribution \(\mu\), \(\sum_{t\in T}\mu_t=1\). A type specifies its values \(v_{tr}\) for resources and its externality row \(e_{tu}\) toward every other type. An aggregate assignment is \(x_{tr}\ge 0\), where \(\sum_r x_{tr}=\mu_t\) and \(\sum_t x_{tr}=q_r\), with \(q_r\) the resource’s population share. Each individual receives one whole resource; \(x_{tr}\) only records how much mass of type \(t\) receives \(r\). The external utility of type \(t\) in resource \(r\) is
\[ E_t(r;x)=\sum_{u\in T}e_{tu}x_{ur}. \]
This is a natural high-multiplicity regime for dorms or project teams: a large university intake or workforce may contain millions of agents but only hundreds of recurring preference-and-compatibility types. Agents of one type have identical resource values, prices, budgets, and externality responses. This is precisely the high-multiplicity interpretation, not an objection to it.
The lead is Proposition 4.6, proved in this paper. It states that deciding whether a dorm-sharing instance admits a Pareto envy-free assignment is NP-complete when resources may have different capacities, even with only two resources and binary external values. Its reduction is from Clique.
The corresponding problem is Two-Resource Mass-PEF. An instance consists of \(T\), rational masses \(\mu_t\), two resources \(r_1,r_2\) with rational capacities \(q_1,q_2\), binary type-level externalities \(e_{tu}\in\{0,1\}\), and the paper’s valuation pattern \(v_{t1}=1\), \(v_{t2}=0\). Decide whether there is an aggregate assignment \(x\) such that, whenever \(x_{tr}>0\) and resource \(s\) has positive mass, either
\[ v_{tr}\ge v_{ts} \]
or
\[ E_t(r;x)\ge E_t(s;x). \]
This is exactly the infinitesimal version of the paper’s PEF swap test: a type-\(t\) agent must not simultaneously prefer another resource and the externality profile there.
I would expect this problem to be continuum-specifically hard, although a hardness-transfer result is also plausible. The discrete Clique obstruction may dissolve because a type can split its mass between resources, but the condition remains a nonconvex support-selection problem: every type receiving positive mass in the less-valued resource must have sufficiently many compatible agents there. Thus continuization does not simply produce an LP. The open question is whether fractional mass makes the condition tractable or whether the type-level externality graph retains enough combinatorics for hardness.
A second, more direct hardness mirror is Proposition 4.2, also proved here. It states that deciding whether an EF assignment exists is NP-complete, even with only two resources that have value \(0\) for every agent. Again the proof reduces from Clique.
The corresponding problem is Two-Resource Mass-EF. Given \(T,\mu\), two resource capacities \(q_1,q_2\), zero internal values, and a binary type-level externality matrix, decide whether there is \(x\) such that every type assigned positive mass to resource \(r\) weakly prefers its externality there to that in the other resource:
\[ E_t(r;x)\ge E_t(s;x) \]
for every occupied \(r,s\). I expect hardness to transfer here. The reduction’s combinatorics live in the externality graph, not in the sheer number of named agents. Each vertex can be replaced by \(K\) indistinguishable copies of one type, with capacities and masses scaled accordingly; then \(n=K|T|\), while the Clique structure remains in the finite type graph. A formal integrality-forcing construction would still be needed, but this is a particularly credible Class B mirror.
The constructive companion is Theorem 5.6, proved here: with capacity \(2\) for every dorm, a PEF assignment always exists and can be computed in polynomial time. The paper obtains this using a maximum matching, Gallai–Edmonds structure, and Hall’s theorem.
For this result I would preserve capacity \(2\) literally rather than turn each dorm into a positive mass. Consider a continuum of anonymous copies of finitely many dorm kinds. Every room copy has exactly two occupants. Let \(\rho_r\) be the mass of room copies of kind \(r\), and let \(p_{tu,r}\) be the mass of rooms of kind \(r\) occupied by types \(t,u\). These variables satisfy
\[ \sum_{t\le u}p_{tu,r}=\rho_r \]
and
\[ 2\sum_r p_{tt,r} +\sum_{u\ne t}\sum_r p_{\min(t,u),\max(t,u),r} =\mu_t. \]
The question, Pair-Continuum PEF-2, is to find such a pair allocation satisfying the paper’s PEF swap condition for every positive-mass pair type and every possible target room pair. If type \(t\) is paired with \(u\) in dorm kind \(r\), and a target agent of type \(a\) is paired with \(b\) in dorm kind \(s\), then the move must be blocked by either
\[ v_{tr}\ge v_{ts} \]
or
\[ e_{tu}\ge e_{tb}, \]
with the analogous condition when the target agent is \(b\). This keeps every individual’s bundle integral; only the distribution over pairings is continuous.
I would expect Pair-Continuum PEF-2 to be tractable, via fractional matching, transportation, and flow versions of the paper’s matching arguments. It is therefore a useful Class A counterpart to the two hardness mirrors.
The main weakness is that the paper permits arbitrary named-agent externalities, whereas these mirrors require a plausible cohort interpretation in which externalities are type-to-type. That is a real modelling commitment. It is defensible for dorm cohorts, project teams, or repeated workforce roles, and the paper’s mathematical problem is still recognisably the same: assigning agents to capacity-constrained resources while balancing resource values against the composition of one’s mates. The two-resource mirrors are especially strong because they preserve the paper’s exact fairness notions and binary externalities. The capacity-two mirror requires the extra room-copy formulation, but that co-modification is forced by preserving the paper’s central \(c=2\) regime rather than changing the problem into fractional occupancy.
This covers Proposition 4.2, Proposition 4.6, and Theorem 5.6. I would not claim that the utility guarantees in Propositions 6.1–6.3 automatically continuize; those are secondary results, whereas the existence, hardness, and capacity boundary provide a coherent continuous-computational programme.
The strongest negative case begins with Proposition 4.2, because its natural continuous mirror actually collapses. In the reduction, the two resources have equal capacity and all internal values are zero. For any type distribution \(\mu\), assign half of every type to each resource:
\[ x_{t1}=x_{t2}=\frac{\mu_t}{2}. \]
Then, for every type \(t\),
\[ E_t(1)=\sum_u e_{tu}x_{u1} =\sum_u e_{tu}x_{u2} =E_t(2). \]
Thus the assignment is EF, and hence PEF, for every instance. The Clique obstruction disappears before any algorithmic question arises. Preventing this by making type masses indivisible would abandon the genuine continuous-population interpretation; replacing total externality by per-capita externality would change the paper’s utility model. So Proposition 4.2 supplies no worthwhile continuous mirror in its own parameter regime.
Proposition 4.6 is less decisive than the proponent suggests. Its reduction depends on an individual-level externality graph: each \(a_i\) has a carefully selected set of friends in \(N_1\), and the construction uses the exact numbers of named neighbours. Replacing agents by repeated types turns those relations into complete bipartite blocks. Splitting a type across the two resources then produces a weighted fractional community problem, not the paper’s Clique gadget. To retain the original relations, one must give essentially every exceptional agent its own type; then \(\tau\) grows with the population and the claimed high-multiplicity gain disappears.
One can define a new problem with block-constant compatibility—“all members of cohort \(t\) like all members of cohort \(u\)”—but that is a substantive change from friendship externalities to utility for population composition. It may be a respectable model, but it is not evidence that the paper’s Proposition 4.6 has a worthwhile mirror. The same issue makes the dorm interpretation weak: finite type spaces produce dense unions of cliques and complete bipartite friendship blocks, whereas the paper’s computational content is precisely arbitrary individual-level social structure.
Theorem 5.6 is the hardest anchor to defeat. Its capacity-two condition does invite a distribution over integral pairs, and the proposed \(p_{tu,r}\) variables are a coherent high-multiplicity formulation. The negative point is that preserving arbitrary dorm valuations requires agents to carry preference vectors over an expanding set of labelled dorms. That makes types increasingly individual-specific. If dorms are instead collapsed into finitely many room kinds, the result becomes a new configuration or transportation problem; the Gallai–Edmonds theorem on the original externality graph is no longer the relevant object. Moreover, PEF constraints remain support-dependent disjunctions, so “fractional matching” does not by itself establish a tractable continuous theorem.
This is nevertheless where the negative case is weakest. A cohort-based pair-allocation problem is genuinely conceivable and computationally meaningful. Therefore the universal conclusion—no worthwhile continuous mirror in any scenario—cannot honestly be sustained. The strongest defensible verdict is narrower: Proposition 4.2 degenerates, Proposition 4.6 relies on identity-level structure that high multiplicity erases, while Theorem 5.6 remains a credible continuous mirror despite the modelling commitments it requires.
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.