Answer: The decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any arbitrary small constant ϵ > 0, there is no streaming algorithm which uses o(l) space and ϵ- approximates all the item prices of the social welfare maxi- mizing price vector.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) goods, \(\tau\) rational utility vectors \(v_t\), type masses \(\mu_t\), and per-capita supply \(q\) of each good, find prices \(p_i \ge 0\) and allocations \(x_{ti} \ge 0\) maximizing \(\sum_{t,i} v_{ti}x_{ti}\), subject to \(\sum_i x_{ti} \le \mu_t\), \(\sum_t x_{ti} \le q\), and the envy-free condition that whenever \(x_{ti}>0\), good \(i\) maximizes the type's utility \(v_{ti}-p_i\) among the goods and the outside option of utility \(0\).
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. There are \(m:=k\ge2\) goods, nonnegative binary-rational unit-demand values \(v_{ti}\), and a common binary-rational per-capita supply \(q>0\). Let \(L\) be the total input bit length.
An allocation \(x_{ti}\ge0\) is the mass of type \(t\) receiving good \(i\), with \(\sum_i x_{ti}\le\mu_t\) and \(\sum_t x_{ti}\le q\). Prices \(p_i\ge0\) are common to all types; the outside option has utility \(0\).
Write \(U_t=\max\{0,\max_i(v_{ti}-p_i)\}\). Envy-freeness requires \(x_{ti}>0\Rightarrow v_{ti}-p_i=U_t\), and \(\sum_i x_{ti}<\mu_t\Rightarrow U_t=0\). Tied maximizing choices may receive arbitrary shares of a type's mass; supply may remain unsold.
The objective is to maximize \(\sum_{t,i}v_{ti}x_{ti}\). For the decision version, the input also includes a nonnegative binary-rational welfare threshold \(W\).
Is deciding whether an envy-free allocation and prices achieve welfare at least \(W\) in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Discrete unit-demand welfare-optimal envy-free pricing is polynomial-time solvable offline; a published streaming result asserts that approximating every coordinate of a welfare-optimal price vector requires \(\Omega(\ell)\) space, even with two goods and \(\ell\) copies per good. [Source](https://api.drum.lib.umd.edu/server/api/core/bitstreams/a5a3004e-fb03-47f5-86b3-c9fe8fea3146/content)
No result settling the exact finite-support rational-mass decision problem above was verified.
The decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
In fact, the maximum welfare over envy-free outcomes equals the maximum welfare over all feasible allocations. Prices supporting an optimal allocation are obtained from the dual of the welfare linear program.
Consider the linear program \((P)\):
\[ \begin{aligned} \text{maximize}\quad & \sum_{t=1}^{\tau}\sum_{i=1}^{m}v_{ti}x_{ti}\\ \text{subject to}\quad & \sum_{i=1}^{m}x_{ti}\le\mu_t &&(t=1,\ldots,\tau),\\ & \sum_{t=1}^{\tau}x_{ti}\le q &&(i=1,\ldots,m),\\ & x_{ti}\ge0 &&(t=1,\ldots,\tau,\ i=1,\ldots,m). \end{aligned} \]
Its feasible solutions are exactly the feasible allocations, without imposing envy-freeness. The zero allocation is feasible, and every variable satisfies \(0\le x_{ti}\le\mu_t\). Consequently, the feasible region is compact and the optimum is finite and attained.
Associate nonnegative dual variables \(u_t\) with the type constraints and \(p_i\) with the supply constraints. The dual program \((D)\) is:
\[ \begin{aligned} \text{minimize}\quad & \sum_{t=1}^{\tau}\mu_tu_t+q\sum_{i=1}^{m}p_i\\ \text{subject to}\quad & u_t+p_i\ge v_{ti} &&(t=1,\ldots,\tau,\ i=1,\ldots,m),\\ & u_t\ge0,\quad p_i\ge0. \end{aligned} \]
The dual is feasible: take \(p_i=0\) and \(u_t=\max_i v_{ti}\). By linear-programming strong duality, there are optimal solutions \(x^*\) and \((u^*,p^*)\) with equal objective values.
We prove that \(x^*\), together with the common prices \(p^*\), satisfies every envy-freeness requirement in the question.
For any primal and dual feasible solutions, the objective difference is
\[ \begin{aligned} &\sum_t\mu_tu_t+q\sum_i p_i-\sum_{t,i}v_{ti}x_{ti}\\ &\qquad= \sum_tu_t\left(\mu_t-\sum_i x_{ti}\right) +\sum_i p_i\left(q-\sum_t x_{ti}\right) +\sum_{t,i}(u_t+p_i-v_{ti})x_{ti}. \end{aligned} \]
Every summand on the right is nonnegative by feasibility. For the optimal solutions, the difference is zero by strong duality. Therefore,
\(x^*_{ti}>0\ \Longrightarrow\ u^*_t+p^*_i=v_{ti}\),
and
\(\sum_i x^*_{ti}<\mu_t\ \Longrightarrow\ u^*_t=0\).
Define the actual maximum utility at these prices by
\(U_t=\max\{0,\max_i(v_{ti}-p^*_i)\}\).
Dual feasibility and \(u^*_t\ge0\) imply \(U_t\le u^*_t\). We now prove equality for every type.
It follows that
\(x^*_{ti}>0\ \Longrightarrow\ v_{ti}-p^*_i=U_t\),
and
\(\sum_i x^*_{ti}<\mu_t\ \Longrightarrow\ U_t=0\).
These are exactly the required envy-freeness conditions. They also cover types split among tied goods or between a good and the outside option.
For completeness, the same objective identity gives
\(\sum_t x^*_{ti}<q\ \Longrightarrow\ p^*_i=0\).
This additional property is permitted by the problem, which allows unsold supply.
Let \(F\) be the optimal value of \((P)\).
Every envy-free allocation is primal feasible, so its welfare is at most \(F\). Conversely, Section 2 constructs an envy-free allocation and prices whose welfare is exactly \(F\).
Therefore, the maximum envy-free welfare equals \(F\). In particular, the decision answer is yes if and only if \(F\ge W\).
Use the standard polynomial-time theorem for rational linear programming: a linear program with rational coefficients can be solved exactly in time polynomial in its binary description length, including recovery of a rational optimal solution when a finite optimum exists.
The hypotheses hold here:
Thus we can compute \(F\) exactly and compare it with the rational threshold \(W\) in polynomial time. If an explicit envy-free outcome is desired, solve \((D)\) as well and output \(x^*,p^*\); the preceding proof verifies that outcome.
No expansion of a mass into discrete copies is needed. Binary-encoded masses and supply appear directly as linear-program coefficients.
The streaming setting studied in the [cited dissertation, Chapter 5](https://api.drum.lib.umd.edu/server/api/core/bitstreams/a5a3004e-fb03-47f5-86b3-c9fe8fea3146/content) imposes memory restrictions. Such restrictions do not preclude this offline polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes that the maximum envy-free welfare equals the unrestricted allocation LP optimum, and that the decision problem is solvable exactly in time polynomial in \(m,\tau,L\). No mathematical gaps or false steps were found.
Its variables represent allocated mass, with precisely the type capacity, good capacity, and nonnegativity constraints in USER_TASK. It introduces no indivisibility restriction, minimum allocation, or requirement to sell all supply.
The compactness argument is valid: the feasible region is closed, nonempty because it contains zero, and bounded because each variable satisfies \(0\le x_{ti}\le\mu_t\). The linear objective therefore has a finite attained maximum.
For this maximization LP with upper-bound constraints and nonnegative variables, the displayed dual correctly has nonnegative variables \(u_t,p_i\), objective
\[
\sum_t\mu_tu_t+q\sum_i p_i,
\]
and constraints \(u_t+p_i\ge v_{ti}\).
The proposed dual feasible point is valid: \(p_i=0\) and \(u_t=\max_i v_{ti}\) satisfy both nonnegativity and every dual constraint, using the stipulated nonnegative values.
The applicable strong-duality statement is that a feasible finite-dimensional LP with finite optimum has an attained dual optimum with the same objective value. The prover establishes the required feasibility and finiteness before invoking it. Consequently, the optimal solutions used subsequently exist.
Expanding the displayed identity cancels the terms containing \(u_tx_{ti}\) and \(p_ix_{ti}\), leaving exactly the dual objective minus the primal objective.
Every term on its right-hand side is nonnegative: primal feasibility gives nonnegative capacity slacks, dual feasibility gives nonnegative reduced-cost slacks, and all multiplying variables are nonnegative. Since there are finitely many terms, zero total gap forces each term to vanish.
Thus both implications follow:
\[
x^*_{ti}>0\ \Longrightarrow\ u^*_t+p^*_i=v_{ti},
\]
and
\[
\sum_i x^*_{ti}<\mu_t\ \Longrightarrow\ u^*_t=0.
\]
These conclusions hold for any chosen optimal primal and dual solutions; the proof does not require a special pairing of optima.
Dual feasibility gives \(v_{ti}-p^*_i\le u^*_t\) for every good, and nonnegativity gives \(0\le u^*_t\). Therefore \(U_t\le u^*_t\).
When \(u^*_t=0\), the outside option supplies the opposite inequality \(U_t\ge0\), establishing equality.
When \(u^*_t>0\), the preceding slack implication, together with primal feasibility, forces full allocation of that type. The strict positivity assumption \(\mu_t>0\) then guarantees a positive allocation to some good. Equality on that allocated edge gives \(U_t\ge u^*_t\), completing the argument.
The proof explicitly uses the correct domain assumption at the point where it is needed.
Substituting \(U_t=u^*_t\) into the two established implications gives exactly the two conditions in USER_TASK. Nonnegative common prices follow from dual feasibility.
Ties and partial allocation cause no gap: every positively allocated good attains the same maximum utility, and any unallocated portion requires that maximum utility to equal the outside-option utility zero.
The additional conclusion that unsold goods have zero price follows from the same gap identity. It is compatible with the task and imposes no obstruction to the constructed outcome.
Every envy-free allocation is feasible for the primal LP, so its welfare cannot exceed \(F\). Conversely, the constructed primal optimum with supporting dual prices is envy-free and has welfare \(F\).
Hence the envy-free maximum is attained and equals \(F\), making the decision answer affirmative exactly when \(F\ge W\). This covers equality at the threshold, \(W=0\), zero valuations, and supplies exceeding total population mass.
The prover states the needed rational-LP theorem precisely enough: exact optimization and recovery of a rational optimum take time polynomial in the binary description length when a finite optimum exists.
The LP has \(m\tau\) variables and \(\tau+m\) capacity constraints, with rational input coefficients and constants zero and one. Its explicit encoding has polynomial length in \(m,\tau,L\), including repeated capacity coefficients and any explicitly represented zeros.
Exact rational optimization permits exact comparison with \(W\); no numerical tolerance is substituted for the decision condition. The same theorem applies to the feasible dual, whose finite attained optimum was established by strong duality. No expansion into discrete copies is used.
The cited dissertation describes Chapter 5 as studying pricing under streaming memory restrictions. That context is accurately characterized in the prover’s closing paragraph. A streaming space lower bound does not invalidate the offline LP algorithm. [Cited dissertation](https://api.drum.lib.umd.edu/server/api/core/bitstreams/a5a3004e-fb03-47f5-86b3-c9fe8fea3146/content)
No repair or 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.