Answer: \(\mathrm{NP}\text{-complete}\)
Proposition 4.6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf resources are allowed to have different capacities, then deciding whether a given dorm sharing instance admits a PEF assignment is NP-complete, even when there are only two resources with binary external values.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is atomless and given by its support: a nonempty list \(T\) of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=2\) resources with positive binary-rational capacities \(q_1,q_2\), possibly different, satisfying \(q_1+q_2=1\). Every type has internal values \(v_{t1}=1\) and \(v_{t2}=0\).
Externalities satisfy \(e_{tu}=e_{ut}\in\{0,1\}\). A diagonal entry describes externalities between distinct individuals of the same type; an individual's own contribution has zero mass.
An assignment consists of real masses \(x_{tr}\geq0\) satisfying \(\sum_{r=1}^{2}x_{tr}=\mu_t\) and \(\sum_{t\in T}x_{tr}=q_r\). Types may be split between resources. Define \(E_t(r;x)=\sum_{u\in T}e_{tu}x_{ur}\).
Call an assignment Pareto envy-free if, whenever \(x_{tr}>0\), every occupied resource \(s\neq r\) satisfies \(v_{tr}\geq v_{ts}\) or \(E_t(r;x)\geq E_t(s;x)\). Comparisons are weak; exchanging two individual positions leaves aggregate masses unchanged.
Is deciding whether such a Pareto envy-free assignment exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m=2\), \(\tau\), and the total input bit length \(L\).
For indivisible agents, existence is \(\mathrm{NP}\)-complete with two positive-capacity resources, symmetric binary externalities, and these common internal values; envy is evaluated after exchanging individual positions ([Gan, Li, and Li, 2023](https://arxiv.org/pdf/2012.04522)).
No result settling this exact atomless decision problem was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when every mass and capacity is a dyadic rational. Thus a polynomial-time algorithm in \(\tau\) and \(L\) exists only if \(\mathrm{P}=\mathrm{NP}\).
For \(m=2\), an exact algorithm runs in \(2^\tau\operatorname{poly}(\tau,L)\) time.
Write \(y_t=x_{t2}\), so \(x_{t1}=\mu_t-y_t\). Define the total externality mass of type \(t\) by
\(d_t=\sum_{u\in T}e_{tu}\mu_u.\)
Assignment feasibility is equivalent to
\(0\leq y_t\leq\mu_t\quad(t\in T),\qquad \sum_{t\in T}y_t=q_2.\)
Individuals assigned to resource \(1\) satisfy the internal-value comparison because \(v_{t1}=1>0=v_{t2}\). For individuals assigned to resource \(2\), that comparison fails. Their externality comparison becomes
\(\sum_u e_{tu}y_u\geq\sum_u e_{tu}(\mu_u-y_u).\)
Consequently, the assignment is Pareto envy-free exactly when
\[y_t>0\quad\Longrightarrow\quad \sum_u e_{tu}y_u\geq d_t/2.\tag{1}\]
We will also use the following bound, which holds because externalities are binary:
\[\sum_u e_{tu}y_u\leq\sum_u y_u=q_2.\tag{2}\]
In particular, if \(d_t>2q_2\), equations (1) and (2) force \(y_t=0\).
There is an easy positive case: when \(q_2\geq 1/2\), the proportional assignment \(y_t=q_2\mu_t\) satisfies (1). The hardness construction below has \(q_2<1/2\).
For each subset \(S\subseteq T\), consider the rational linear system
\(0\leq y_t\leq\mu_t\quad(t\in T),\qquad \sum_t y_t=q_2,\)
\[y_t=0\quad(t\notin S),\qquad \sum_u e_{tu}y_u\geq d_t/2\quad(t\in S).\tag{3}\]
An envy-free assignment yields a feasible system by choosing \(S=\{t:y_t>0\}\). Conversely, any solution of (3) satisfies (1): every type with positive \(y_t\) belongs to \(S\) and satisfies its externality inequality. It does not matter if some types in \(S\) receive zero mass on resource \(2\).
Each system has \(\tau\) variables and \(O(\tau)\) constraints, with encoding length polynomial in \(\tau\) and \(L\). Polynomial-time rational linear programming therefore gives an exact decision algorithm with running time
\(2^\tau\operatorname{poly}(\tau,L)\qquad\text{for }m=2.\)
For completeness, real-valued assignments do not prevent membership in \(\mathrm{NP}\). Every nonempty system (3) defines a bounded rational polytope and hence has a vertex. Clearing denominators produces integer coefficients with \(O(L)\) bits: the product of the input denominators, multiplied by \(2\), is a sufficient common denominator. At a vertex, \(\tau\) independent tight constraints determine the coordinates. Cramer’s rule and determinant bounds give \(O(\tau(L+\log\tau))\) bits per coordinate.
Thus a polynomial-length certificate consists of \(S\) and a rational feasible vector \(y\). All constraints can be verified by exact rational arithmetic in polynomial time. The problem belongs to \(\mathrm{NP}\).
We use the classical \(\mathrm{NP}\)-complete CLIQUE problem: given a simple undirected graph and an integer threshold, decide whether the graph contains a clique of at least that size. [Karp, *Reducibility among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may restrict to instances \(G=(V,F)\), with \(n=|V|\), satisfying
\[n/2<k\leq n.\tag{4}\]
Here is the justification for that restriction. Given any instance on \(n_0\) vertices with \(1\leq k_0\leq n_0\), add \(n_0\) vertices forming a clique and adjacent to every original vertex. The new graph has \(2n_0\) vertices and threshold \(n_0+k_0>n_0\). It contains a clique of that size exactly when the original graph contains a clique of size at least \(k_0\): a new clique contains at most \(n_0\) added vertices, while any original clique can be extended by all added vertices.
We now construct a society from an instance satisfying (4).
For every vertex \(i\in V\), introduce a candidate type \(c_i\) and an auxiliary type \(a_i\). Introduce one additional type \(z\). Thus
\(\tau=2n+1.\)
Let \(\deg_G(i)\) denote the degree of vertex \(i\), and define
\(r_i=2k-\deg_G(i)-1.\)
Since \(\deg_G(i)+1\leq n<2k\), every \(r_i\) is a positive integer.
Set
\(C=n+\sum_{i\in V}r_i,\)
and let \(B\) be the smallest power of \(2\) strictly larger than \(C+2k\). Define
\[\mu_{c_i}=1/B,\qquad \mu_{a_i}=r_i/B,\qquad \mu_z=(B-C)/B.\tag{5}\]
All masses are positive, and
\(\sum_{t\in T}\mu_t=(n+\sum_i r_i+B-C)/B=1.\)
The capacities are
\[q_2=k/B,\qquad q_1=1-k/B.\tag{6}\]
They are positive and sum to \(1\). Moreover,
\[\mu_z=(B-C)/B>2k/B=2q_2.\tag{7}\]
In particular, \(q_2<1/2\).
Set the following entries equal to \(1\), together with their symmetric counterparts:
Every other entry is \(0\). This is a symmetric binary matrix. Its diagonal entries use exactly the same-type externality interpretation specified in the question.
Every type receives the required internal values \(v_{t1}=1\) and \(v_{t2}=0\).
The total externality mass of \(z\) is
\(d_z=\mu_z+\sum_i\mu_{a_i}\geq\mu_z>2q_2.\)
For each auxiliary type,
\(d_{a_i}=\mu_{c_i}+\mu_z>2q_2.\)
The consequence of equations (1) and (2) therefore gives
\[y_z=0,\qquad y_{a_i}=0\quad(i\in V)\tag{8}\]
in every envy-free assignment. This conclusion permits arbitrary real splitting; even a positive fragment of one of these types on resource \(2\) would violate (1).
For a candidate type \(c_i\), its neighbors are itself, the candidate types corresponding to its graph neighbors, and its auxiliary type. Therefore
\[d_{c_i}=\frac{1+\deg_G(i)+r_i}{B}=\frac{2k}{B}=2q_2.\tag{9}\]
If \(y_{c_i}>0\), equations (1), (2), and (9) imply
\[\sum_t e_{c_i t}y_t=q_2.\tag{10}\]
Let
\(S=\{i\in V:y_{c_i}>0\}.\)
By (8), all resource-\(2\) mass belongs to candidate types, so
\[\sum_{i\in S}y_{c_i}=q_2.\tag{11}\]
For any \(i\in S\), subtracting (10) from (11) yields
\(0=\sum_{j\in S}(1-e_{c_i c_j})y_{c_j}.\)
Each summand is nonnegative, and every \(y_{c_j}\) appearing here is positive. Hence \(e_{c_i c_j}=1\) for all \(i,j\in S\). For distinct vertices, this means that \(S\) is a clique in \(G\).
Finally, each candidate has mass \(1/B\), so
\(\frac{k}{B}=q_2=\sum_{i\in S}y_{c_i}\leq\frac{|S|}{B}.\)
Thus \(|S|\geq k\). We have proved that existence of an envy-free assignment implies existence of the required clique.
Conversely, suppose \(G\) contains a clique of size at least \(k\), and choose exactly \(k\) vertices from it. Assign their candidate types entirely to resource \(2\); assign all remaining types entirely to resource \(1\).
The mass on resource \(2\) is \(k/B=q_2\), so the assignment satisfies both capacities.
Each candidate assigned to resource \(2\) has externality \(1\) toward every type assigned there, including its own type. Its externality on resource \(2\) is consequently \(q_2\). By (9), its externality on resource \(1\) is also \(q_2\). The weak comparison in (1) holds with equality.
Every type assigned to resource \(1\) satisfies the internal-value comparison. Hence the assignment is Pareto envy-free.
The constructed instance is therefore a yes-instance exactly when \(G\) has a clique of size at least \(k\).
The reduction has \(\tau=2n+1\). Since \(r_i\leq 2k-1\),
\(C=n+\sum_i r_i\leq 2kn\leq 2n^2.\)
The choice of \(B\) gives
\(B\leq 2(C+2k)=O(n^2).\)
Thus every mass and capacity in (5)–(6) is a dyadic rational with \(O(\log n)\) bits. The externality matrix has \(O(n^2)\) binary entries. Under the explicit matrix encoding, the total output length is
\(L=O(n^2+n\log n),\)
and the reduction can be implemented in \(O(n^2\log n)\) bit operations. It is therefore a polynomial-time many-one reduction.
Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness for the stated atomless problem. For \(m=2\), support enumeration gives \(2^\tau\operatorname{poly}(\tau,L)\) time; polynomial dependence on both \(\tau\) and \(L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction establishes \(\mathrm{NP}\)-hardness for the exact atomless model, including arbitrary real splitting. The rational-certificate argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
Setting \(y_t=x_{t2}\) gives exactly the stated feasibility conditions. Because both capacities are positive, both resources are occupied, so the comparison with the other resource is always applicable.
Individuals on resource \(1\) satisfy the internal-value comparison. For individuals on resource \(2\), that comparison fails, and the externality comparison is equivalent to
\[
\sum_u e_{tu}y_u\geq d_t/2.
\]
Thus equation (1), including its strict antecedent \(y_t>0\) and weak consequent, is correct.
The diagonal terms require no correction: under the task’s atomless interpretation, excluding an individual’s own contribution removes zero mass.
Equation (2) follows from \(e_{tu}\in\{0,1\}\) and \(y_u\geq0\). Consequently, a type with \(d_t>2q_2\) cannot have any positive mass on resource \(2\). The strict inequality is used correctly.
For \(q_2\geq1/2\), the proportional assignment is feasible and gives externality \(q_2d_t\) on resource \(2\), which is at least \(d_t/2\). This also covers \(d_t=0\) and \(q_2=1/2\).
An envy-free assignment satisfies system (3) for its positive support. Conversely, a feasible solution of (3) satisfies every externality inequality required by its actual positive support.
Allowing a type in the guessed set \(S\) to receive zero mass creates no false positives: it merely imposes an unnecessary inequality on that type. No strict positivity constraints need to be solved.
Each system is a finite rational linear feasibility problem with \(\tau\) variables and \(O(\tau)\) constraints. Its encoded size is polynomial in \(\tau\) and \(L\). The standard polynomial-time theorem for rational linear programming therefore applies, giving the claimed running time \(2^\tau\operatorname{poly}(\tau,L)\) for \(m=2\).
Every system (3) defines a closed, bounded rational polytope. If nonempty, it has a vertex; boundedness follows directly from the coordinate bounds.
The proposed common denominator clears the masses, capacities, and the factors \(1/2\). Its bit length is \(O(L)\), and the resulting integer coefficients also have \(O(L)\) bits.
At a vertex, \(\tau\) linearly independent active constraints determine the coordinates. This remains valid when the polytope has dimension smaller than \(\tau\). The stated Cramer’s-rule and determinant estimate, \(O(\tau(L+\log\tau))\) bits per coordinate, is sufficient and correct.
Consequently, the guessed set \(S\) and a rational feasible vector form a polynomial-length certificate. Exact rational verification takes polynomial time. The argument does not assume that every real feasible assignment already has a short encoding.
The source problem—existence of a clique of at least the given threshold—is the classical \(\mathrm{NP}\)-complete CLIQUE problem cited in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The padding construction correctly transforms instances with \(1\leq k_0\leq n_0\) into instances with \(n=2n_0\) and \(k=n_0+k_0\), so \(n/2<k\leq n\).
Both directions of the padding equivalence hold. An original qualifying clique extends using all added vertices. A qualifying clique in the padded graph contains at least \(k_0\) original vertices, which themselves form a clique. The restriction therefore preserves hardness.
From \(\deg_G(i)+1\leq n<2k\), every \(r_i\) is a positive integer. The masses in (5) are therefore positive, and their displayed sum is exactly \(1\).
The strict choice \(B>C+2k\) gives \(\mu_z>2q_2\). It also ensures positive capacities and \(q_2<1/2\). All masses and capacities are dyadic rationals.
The externality matrix is symmetric and binary. Its specified diagonal entries are permitted by the task. All types have exactly the required common internal values. The construction uses precisely \(\tau=2n+1\) listed types.
The calculations of \(d_z\) and \(d_{a_i}\) are correct. Both exceed \(2q_2\), so equation (8) follows even if only an arbitrarily small positive fragment were placed on resource \(2\).
For each candidate, equation (9) correctly gives \(d_{c_i}=2q_2\). A positive candidate must therefore attain equality in the universal bound, yielding equation (10).
Since all resource-\(2\) mass belongs to candidates, subtracting equations (10) and (11) gives the stated sum of nonnegative terms. Every candidate in \(S\) has strictly positive mass, so every corresponding coefficient must vanish. The diagonal coefficients already vanish because \(e_{c_ic_i}=1\); the off-diagonal coefficients force \(S\) to be a clique.
The bound \(y_{c_i}\leq1/B\) then correctly yields \(|S|\geq k\). This is the crucial step showing that fractional assignments cannot bypass the clique requirement.
Conversely, assigning exactly \(k\) clique candidates entirely to resource \(2\) satisfies both capacities. Each selected candidate has externality \(q_2\) on each resource, so the required weak comparison holds with equality. Every other type satisfies the internal-value comparison on resource \(1\).
The estimates \(C\leq2kn\leq2n^2\) and \(B\leq2(C+2k)\) hold, including when \(C+2k\) is itself a power of two: the next strictly larger power is exactly twice that value.
Thus each numerical entry has \(O(\log n)\) bits. With an explicit externality matrix, the stated output length \(O(n^2+n\log n)\) and construction time \(O(n^2\log n)\) bit operations are valid upper bounds.
The polynomial many-one reduction and membership argument establish \(\mathrm{NP}\)-completeness. The answer also supplies the requested exact running time in the fixed two-resource setting. No additional clarification is needed to verify the mathematical conclusion.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.