Answer: \(\mathrm{P}\)
Theorem 3.6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFinding a maximum SW roommate matching is APX-hard under binary Leontief utilities. In particular, the instance creates a setting where all triples have utility at most 1. That is a maximum welfare matching would essentially be a maximal matching of Ls with max- imum size. This is an important difference from the reduc- tion in (Chan et al. 2016) which proves NP-hardness with mixtures of Ls and Ts.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete agent types with masses summing to 2 and finitely many complete room types with masses summing to 1, binary type-to-type compatibility and type-to-room valuations, compute or approximate the maximum utilitarian welfare achievable by assigning room mass to unordered pairs of agent types subject to all mass-balance constraints.
Given finite resident types \(T\) and room types \(R\), rational masses \(\mu_t\ge0\) and supplies \(\lambda_r\ge0\) with \(\sum_{t\in T}\mu_t=1\) and \(\sum_{r\in R}\lambda_r=\tfrac12\), let \(v_t(t')\in\{0,1\}\) be symmetric and let \(\widehat v_t(r)\in\{0,1\}\). Set \(u_t(t',r)=\min\{v_t(t'),\widehat v_t(r)\}\).
An allocation has variables \(x_{\{t,t'\},r}\ge0\). It satisfies \(\sum_r\left(2x_{\{t,t\},r}+\sum_{t'\ne t}x_{\{t,t'\},r}\right)=\mu_t\) for every \(t\), and \(\sum_{\{t,t'\}}x_{\{t,t'\},r}=\lambda_r\) for every \(r\). Its welfare is \(\sum_{r,t}2x_{\{t,t\},r}u_t(t,r)+\sum_{r,\{t,t'\}:t\ne t'}x_{\{t,t'\},r}\bigl(u_t(t',r)+u_{t'}(t,r)\bigr)\).
Is deciding whether an allocation of welfare at least \(K\) exists, equivalently maximizing this welfare, in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard?
For finite individual agents, maximum-welfare roommate-and-room matching under binary symmetric Leontief utilities is APX-hard (and hence NP-hard).
No verified prior result was identified for exactly the mass-allocation formulation above.
Under the standard binary encoding of the rational numbers \(\mu_t\), \(\lambda_r\), and \(K\), the welfare-threshold problem is polynomial-time solvable. Consequently, maximum welfare can also be computed in polynomial time by rational linear programming.
Let \(n=|T|\) and \(m=|R|\). For every unordered pair \(\{t,t'\}\), including the case \(t=t'\), and every \(r\in R\), introduce the variable \(x_{\{t,t'\},r}\).
There are exactly
\[ m\binom{n+1}{2} \]
variables, which is polynomial in the explicit input size.
For each variable, define its welfare coefficient by
\[ c_{\{t,t\},r}=2u_t(t,r) \]
and, when \(t\neq t'\), by
\[ c_{\{t,t'\},r} = u_t(t',r)+u_{t'}(t,r). \]
Because
\[ u_t(t',r)=\min\{v_t(t'),\widehat v_t(r)\}, \]
every coefficient \(c_{\{t,t'\},r}\) belongs to \(\{0,1,2\}\) and is computable directly from the input.
The existence of an allocation of welfare at least \(K\) is therefore exactly the feasibility of the following rational linear system:
\[ x_{\{t,t'\},r}\geq 0 \]
for all \(\{t,t'\}\) and \(r\),
\[ \sum_{r\in R} \left( 2x_{\{t,t\},r} + \sum_{t'\neq t}x_{\{t,t'\},r} \right) = \mu_t \]
for every \(t\in T\),
\[ \sum_{\{t,t'\}}x_{\{t,t'\},r} = \lambda_r \]
for every \(r\in R\), and
\[ \sum_{r\in R}\sum_{\{t,t'\}}c_{\{t,t'\},r}x_{\{t,t'\},r} \geq K. \]
This system has \(n+m\) equality constraints, one welfare inequality, and \(m\binom{n+1}{2}\) nonnegativity constraints. Its coefficients belong to \(\{0,1,2\}\), apart from the rational right-hand sides supplied in the input. Thus its encoding length is polynomial in the encoding length of the original instance.
Feasibility of a rational linear program is decidable in polynomial time in the Turing bit model. Hence the welfare-threshold problem belongs to \(\mathrm{P}\).
Similarly, maximum welfare is the rational linear program
\[ \max \sum_{r\in R}\sum_{\{t,t'\}} c_{\{t,t'\},r}x_{\{t,t'\},r} \]
subject to the resident-mass and room-supply constraints above. Rational linear programming computes an optimal solution and its exact rational objective value in polynomial time.
The feasible region is always nonempty under the stated mass-balance assumptions. Indeed, set
\[ x_{\{t,t\},r}=\mu_t\lambda_r \]
and set all cross-type variables to zero. Then, for every \(t\),
\[ \sum_{r\in R}2x_{\{t,t\},r} = 2\mu_t\sum_{r\in R}\lambda_r = \mu_t, \]
while, for every \(r\),
\[ \sum_{t\in T}x_{\{t,t\},r} = \lambda_r\sum_{t\in T}\mu_t = \lambda_r. \]
Moreover, every variable satisfies \(0\leq x_{\{t,t'\},r}\leq\lambda_r\). Thus the feasible region is compact, and the linear welfare objective attains its maximum.
The finite-agent problem imposes indivisible matching decisions. In the mass formulation, every resident type can be divided among arbitrarily many roommate-type and room-type combinations. The variables are genuinely continuous, and no integrality or support restriction is imposed.
Accordingly, the displayed formulation is a fractional relaxation of the corresponding finite matching problem. APX-hardness of the indivisible problem does not imply hardness of this continuous linear program.
Therefore the stated mass-allocation problem is in \(\mathrm{P}\). It could be NP-hard under polynomial-time reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly identifies the mass-allocation problem as a rational linear program of polynomial size. The argument establishes both polynomial-time threshold feasibility and polynomial-time exact welfare maximization under the standard explicit binary encoding. No substantive gap was found.
The allocation variables are exactly those specified in the task: one nonnegative variable \(x_{\{t,t'\},r}\) for every unordered resident-type pair, including repeated pairs, and every room type.
The count
\[ |R|\binom{|T|+1}{2} \]
is correct. It is polynomial when \(T\), \(R\), and the valuation tables are explicitly represented.
For a same-type pair, the coefficient \(2u_t(t,r)\) matches the welfare definition. For a cross-type pair, the coefficient
\[ u_t(t',r)+u_{t'}(t,r) \]
also matches the stated welfare expression.
Since each utility is the minimum of two binary values, every utility lies in \(\{0,1\}\), so the objective coefficients indeed lie in \(\{0,1,2\}\).
The displayed constraints
\[ \sum_{r\in R}\left(2x_{\{t,t\},r}+\sum_{t'\neq t}x_{\{t,t'\},r}\right)=\mu_t \]
reproduce the task’s resident-mass constraints exactly. There is no double-counting error: a same-type pair consumes two units of type-\(t\) mass, while a cross-type pair consumes one unit of each participating type.
The equations
\[ \sum_{\{t,t'\}}x_{\{t,t'\},r}=\lambda_r \]
agree exactly with the required room-type supplies.
Adding the inequality
\[ \sum_{r\in R}\sum_{\{t,t'\}}c_{\{t,t'\},r}x_{\{t,t'\},r}\geq K \]
is precisely equivalent to requiring welfare at least \(K\). Thus the decision problem is exactly rational linear-program feasibility, not merely a relaxation of the stated mass problem.
The system has polynomially many variables and constraints. Its matrix and objective coefficients have constant bit length, while \(\mu_t\), \(\lambda_r\), and \(K\) retain their input bit lengths. Therefore the resulting rational linear program has polynomial encoding length.
The invocation of polynomial-time rational linear programming is valid. Rational LP feasibility and optimization are polynomial-time solvable in the Turing bit model, so both the threshold problem and exact maximum-welfare computation are in \(\mathrm{P}\).
The proposed allocation
\[ x_{\{t,t\},r}=\mu_t\lambda_r \]
with all cross-type variables zero satisfies the resident constraints because
\[ 2\mu_t\sum_r\lambda_r=\mu_t, \]
and satisfies each room constraint because
\[ \lambda_r\sum_t\mu_t=\lambda_r. \]
This construction remains valid when some masses or supplies are zero.
From nonnegativity and the room equation, every variable associated with room type \(r\) is at most \(\lambda_r\). Hence the feasible set is closed and bounded in finite-dimensional space, so it is compact. The linear objective therefore attains its maximum.
The explanation is correct: the mass model permits arbitrary fractional division and imposes no integrality condition. Hardness of the indivisible finite-agent problem does not establish hardness of this continuous LP.
No major or minor mathematical issues were identified.
⟨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.