Answer: polynomial-time solvable
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to find a maximum social welfare assignment, even when all happiness and evaluations take {0,1} values.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support \(A\): the list of its \(\tau\) complete person types with positive binary-rational masses \(\mu_a\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Let \(Q\) contain \(m\) room classes with binary-rational supplies \(\rho_q\geq 0\), summing to \(\tfrac12\). Let \(L\) be the total input bit length.
For every \(a,b\in A\) and \(q\in Q\), the input specifies directed happiness \(h_{ab}\in\{0,1\}\) and room value \(v_{aq}\in\{0,1\}\). The value \(h_{aa}\) concerns two distinct people of the same type; happiness need not be symmetric.
Fix any ordering of \(A\). An allocation consists of divisible, nonnegative rational room masses \(x_{abq}\) for \(a\leq b\): each such room houses one person of each indicated type, or two distinct people of type \(a\) when \(a=b\).
Require \(\sum_{a\leq b}x_{abq}=\rho_q\) for every \(q\), and \(2\sum_qx_{aaq}+\sum_{b<a}\sum_qx_{baq}+\sum_{b>a}\sum_qx_{abq}=\mu_a\) for every \(a\).
Maximize welfare \(W(x)=\sum_{q\in Q}\sum_{a\leq b}x_{abq}(h_{ab}+h_{ba}+v_{aq}+v_{bq})\). No stability or envy-freeness condition is imposed; rents do not enter welfare.
Is exact welfare maximization for this mass allocation problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite societies with two distinct people per room, exact welfare maximization is NP-hard even when all happiness and room values belong to \(\{0,1\}\). This discrete result does not classify the mass problem stated above.
Claim. Exact welfare maximization is solvable in polynomial time in \(m,\tau,L\). Both an optimal rational allocation and its exact welfare can be computed.
Linear-program formulation. Let \(I=\{(a,b,q):a,b\in A,\ a\leq b,\ q\in Q\}\). There are \(N=m\tau(\tau+1)/2\) variables. For each index, define \(c_{abq}=h_{ab}+h_{ba}+v_{aq}+v_{bq}\), so \(c_{abq}\in\{0,1,2,3,4\}\).
Write the allocation constraints as \(Mx=d\), where the rows consist of the \(m\) room-supply equations and the \(\tau\) person-mass equations. The column for \(x_{abq}\) has:
Thus the optimization problem is precisely \(\max\{c^\mathsf{T}x:Mx=d,\ x\geq0\}\), with the additional requirement that its output be rational. All matrix coefficients belong to \(\{0,1,2\}\), and \(d\) consists of the input supplies and masses. Even a dense encoding of this linear program has length polynomial in \(m,\tau,L\).
Feasibility and existence of an optimum. Initially allow real coordinates and denote the resulting feasible set by \(P\). Define \(x^0_{aaq}=\mu_a\rho_q\) and \(x^0_{abq}=0\) for \(a<b\). For every room class, \(\sum_a x^0_{aaq}=\rho_q\sum_a\mu_a=\rho_q\). For every person type, \(2\sum_qx^0_{aaq}=2\mu_a\sum_q\rho_q=\mu_a\). Hence \(P\) is nonempty, and this particular allocation is rational.
Every feasible coordinate satisfies \(0\leq x_{abq}\leq\rho_q\leq\tfrac12\). Consequently, \(P\) is closed and bounded, hence compact. The linear objective therefore attains a maximum over \(P\). Moreover, \(0\leq W(x)\leq4\sum_q\rho_q=2\).
Exactness and output size. We next show that some maximizer is rational with polynomial encoding length.
Choose a maximizer \(x^*\) with the smallest possible number \(k\) of positive coordinates, and let \(S\) be its support. The columns of \(M\) indexed by \(S\) are linearly independent. Indeed, otherwise there would be a nonzero vector \(z\), supported on \(S\), satisfying \(Mz=0\). Both \(x^*+\varepsilon z\) and \(x^*-\varepsilon z\) are feasible for sufficiently small positive \(\varepsilon\), because all coordinates of \(x^*\) in \(S\) are positive. Optimality forces \(c^\mathsf{T}z=0\); otherwise one of these perturbations would improve welfare.
Change the sign of \(z\), if necessary, so that some coordinate is positive. Set \(t=\min_{j\in S:z_j>0}x^*_j/z_j\). Then \(x^*-tz\) is feasible, has the same welfare, and has strictly fewer positive coordinates. This contradicts the choice of \(x^*\), proving column independence.
In particular, \(k\leq m+\tau\). Select \(k\) rows on which these columns form a nonsingular integer matrix \(B\). The positive coordinates satisfy \(Bx^*_S=d'\), where \(d'\) is the selected portion of \(d\).
Let \(D\) be the product of the denominators of the input masses and supplies. Its binary length is \(O(L)\), and \(Dd'\) is integral. Cramer’s rule gives \(x^*_j=\det(B_j)/(D\det B)\), where \(B_j\) replaces the corresponding column of \(B\) by \(Dd'\).
Every entry of \(B\) has absolute value at most \(2\), and every entry of \(Dd'\) has absolute value at most \(D\). Expanding determinants therefore gives \(|\det B|\leq k!2^k\) and \(|\det B_j|\leq k!2^{k-1}D\). Each coordinate consequently has encoding length \(O(L+k\log(k+1))\). Thus \(x^*\) is a legal rational allocation of polynomial total encoding length, and the maximum over real allocations equals the maximum over the required rational allocations.
Polynomial-time computation. The exact rational linear-programming theorem states that an explicitly specified rational linear program can be solved in time polynomial in its encoding length, returning an exact rational optimum when the feasible set is nonempty and the optimum is finite. This is the standard ellipsoid-method guarantee; see [Theorem 1 in Yang Cai’s thesis](https://www.cs.yale.edu/homes/cai/publication/thesis/thesis.pdf#page=38).
All its hypotheses hold here: the program is explicitly specified, has rational coefficients, has polynomial encoding length, is feasible, and is bounded. Applying that theorem returns an optimal rational allocation in polynomial time in \(m,\tau,L\). Evaluating \(c^\mathsf{T}x^*\) by exact rational arithmetic also takes polynomial time.
The stated discrete NP-hardness result concerns additional indivisibility requirements. Those requirements are absent from this mass problem, whose feasible allocations are exactly the rational points of the linear program above.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the argument establishes polynomial-time computation of both an optimal rational allocation and its exact welfare. No major or minor mathematical issues were found.
There is one variable for every unordered pair of supported types and every room class, giving \(N=m\tau(\tau+1)/2\) variables. This uses the supplied support size \(\tau\), without enumerating types outside the support.
The matrix coefficients correctly count people: an off-diagonal room contributes one person to each of two type equations, while a diagonal room contributes two people to one type equation. Every room contributes one unit to its room-supply equation.
The objective also matches the task, including directed happiness. For diagonal variables, its coefficient is \(2h_{aa}+2v_{aq}\), correctly counting the contributions of both occupants. No symmetry assumption or integrality restriction is introduced.
With \(m+\tau\) equality rows and \(N\) nonnegativity constraints, even a dense representation has polynomial encoding length in \(m,\tau,L\).
The proposed coordinates \(x^0_{aaq}=\mu_a\rho_q\), with all off-diagonal coordinates zero, are nonnegative and rational. The displayed calculations verify every room-supply equation and every person-mass equation using the two prescribed normalization conditions.
Zero-supply classes cause no difficulty: all their constructed coordinates are zero. Allocations within a single type are expressly allowed by the task, so the diagonal construction does not introduce an unauthorized allocation.
Nonnegativity and the room-supply equation imply \(x_{abq}\leq\rho_q\). Since supplies are nonnegative and sum to \(1/2\), each supply is at most \(1/2\).
The real feasible set is closed, bounded, and nonempty. Compactness and continuity therefore justify attainment of the maximum. The welfare bound \(0\leq W(x)\leq2\) follows from coefficients between zero and four and total room mass \(1/2\).
A maximizer with minimum support size exists because maximizers exist and support sizes belong to the finite set of integers from zero to \(N\).
If its supported columns were dependent, the stated nonzero kernel vector would permit both sufficiently small perturbations: supported coordinates are strictly positive, and unsupported coordinates remain zero. The equality constraints are preserved.
Optimality then forces \(c^\mathsf{T}z=0\). After the permitted sign change, the minimum defining \(t\) exists and is strictly positive. Subtracting \(tz\) preserves nonnegativity, makes at least one positive coordinate zero, creates no positive coordinate outside the support, and preserves welfare. The contradiction correctly proves column independence and hence \(k\leq m+\tau\).
Column independence permits selection of a nonsingular \(k\)-by-\(k\) row submatrix. The resulting system determines the supported coordinates uniquely.
The product \(D\) of input denominators has binary length \(O(L)\) and clears the selected right-hand side. The stated Cramer’s-rule formula has the correct factor \(D\) in its denominator.
Each selected right-hand-side entry lies between zero and one, so entries of \(Dd'\) have absolute value at most \(D\). The determinant bounds
\[
|\det B|\leq k!2^k,\qquad
|\det B_j|\leq k!2^{k-1}D
\]
correctly follow by bounding the terms in the determinant expansions. Since \(\det B\) is a nonzero integer, these bounds yield the asserted coordinate encoding length.
The case \(k=0\) cannot occur: positive total room supply forces every feasible allocation to have a positive coordinate. Thus the determinant argument has no missing empty-support case.
Including zero coordinates, the allocation still has polynomial total encoding length because \(N\) is polynomial. A rational real maximizer establishes equality between the real and rational optimum values.
The prover states the standard exact rational linear-programming guarantee with sufficient hypotheses. Its cited Theorem 1 gives polynomial-time optimization over a rational polytope through a separation oracle, with an optimal corner returned. The explicitly listed rational constraints provide the required oracle with polynomial running time and coefficient bit lengths. The source imposes no full-dimensionality requirement, so the equality constraints and possible zero supplies do not invalidate the application. [Yang Cai’s thesis, Theorem 1](https://www.cs.yale.edu/homes/cai/publication/thesis/thesis.pdf#page=38)
Feasibility, boundedness, and polynomial encoding length have all been established. Exact evaluation of the objective also takes polynomial time: there are polynomially many rational coordinates of polynomial bit length and bounded integer objective coefficients.
The argument proves exact optimization for the divisible rational masses specified in the task. Its observation that discrete indivisibility changes the feasible set is correct; the supplied discrete hardness result does not contradict this conclusion.
No additional clarification is required.
⟨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.