Answer: Exact welfare maximization is polynomial-time solvable in \(m,\tau,L\); the welfare-threshold decision problem belongs to \(\mathrm{P}\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that there are n agents with piecewise constant valuation functions. Then Algorithm 1 computes an optimal EF allocation in polynomial time. Interestingly, setting the variables xiI to 1/n for every i ∈N and I ∈J —allocating to each agent a 1/n- fraction of each interval in J —produces an allocation where Vi(Xj) = 1/n for every i, j ∈N; this is what Chen et al. (2010) call a perfect allocation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t>0\) summing to \(1\), piecewise-constant valuation types \(t\in T\), their common breakpoint partition \(J\), and a per-capita supply \(\beta\) of each interval, choose type bundles \(x_{tI}\in[0,1]\). With \(U_t(x_t)=\sum_{I\in J}x_{tI}V_t(I)\), maximize \(\sum_{t\in T}\mu_t U_t(x_t)\), subject to \(\sum_{t\in T}\mu_t x_{tI}\le\beta\) for every \(I\in J\) and \(U_t(x_t)\ge U_t(x_s)\) for every pair \(t,s\). What is the exact computational complexity in the support size, partition size, and input bit length?
A society is given by its support: the list of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The cake is \([0,1]\). Its common partition \(J\) consists of \(m\ge1\) intervals with rational endpoints; each type has a nonnegative rational constant density \(v_{tI}\) on each interval, normalized by \(\sum_{I\in J}|I|v_{tI}=1\). Write \(V_t(I)=|I|v_{tI}\).
The input also contains a positive binary rational per-capita supply \(\beta\), common to all intervals. A bundle matrix has real entries \(x_{tI}\in[0,1]\), interpreted as fractions of intervals, and utility \(U_t(x_s)=\sum_{I\in J}x_{sI}V_t(I)\).
Feasibility requires \(\sum_t\mu_t x_{tI}\le\beta\) for every interval and weak envy-freeness \(U_t(x_t)\ge U_t(x_s)\) for every ordered pair of types. Unused supply is permitted. Maximize welfare \(\sum_t\mu_t U_t(x_t)\).
Let \(L\) be the total binary input length; the welfare-threshold decision problem additionally receives a binary rational \(q\) and asks whether feasible welfare at least \(q\) exists.
Is computing an exact welfare-maximizing feasible bundle matrix polynomial-time in \(m,\tau,L\), or is its welfare-threshold decision problem NP-hard?
For finitely many equally weighted agents with normalized piecewise-constant valuations, Cohler, Lai, Parkes, and Procaccia establish polynomial-time computation of an optimal envy-free allocation. That result concerns finite-agent allocations and does not explicitly address the rational-mass society with per-capita supply defined here.
An exact welfare-maximizing feasible bundle matrix can be computed in time polynomial in \(m,\tau,L\). The welfare-threshold decision problem belongs to \(\mathrm{P}\).
The proof applies directly to the rational-mass society in the question.
Index the supported types by \(t\in\{1,\ldots,\tau\}\). For each interval \(I\), compute the rational number \(a_{tI}=|I|v_{tI}=V_t(I)\).
Introduce one real variable \(x_{tI}\) for each type–interval pair. Consider the following linear program:
This formulation is exact. The supply constraints and bounds reproduce the corresponding requirements verbatim. For each ordered pair \(t,s\), the envy constraint is precisely \(U_t(x_t)\ge U_t(x_s)\). The omitted constraints with \(t=s\) are identities. Finally, the objective is precisely the stated welfare.
Consequently, feasible bundle matrices and feasible points of this linear program coincide, with identical objective values.
The program has \(n=\tau m\) variables and
\(\displaystyle r=m+\tau(\tau-1)+2\tau m\)
inequalities.
Each derived coefficient is one of the original rational numbers, an interval value \(a_{tI}\), an objective coefficient \(\mu_t a_{tI}\), or a signed version of these numbers.
To verify their encoding lengths, write an interval as \(I=[\ell_I,r_I]\). Computing \(a_{tI}=(r_I-\ell_I)v_{tI}\) uses one subtraction and one multiplication of input rationals. Computing \(\mu_t a_{tI}\) uses one further multiplication. Under numerator–denominator binary encoding, these operations increase encoding length by at most a constant factor of the total length of their operands. Hence every derived coefficient has encoding length \(O(L)\) and can be computed in polynomial time.
Even a dense representation of the program therefore has total length
\(\displaystyle O\bigl((r+1)(n+1)(L+1)\bigr),\)
which is polynomial in \(m,\tau,L\).
In particular, the algorithm uses the masses as rational coefficients. It does not expand a type into a number of agents determined by its mass denominator.
We use the standard exact rational linear programming theorem: a linear program with binary-encoded rational coefficients can be solved in polynomial bit time; when its feasible region is nonempty and its optimum is finite, the algorithm returns an exact rational optimal solution of polynomial encoding length. This is an exact optimization result, rather than merely an approximation guarantee; see the discussion following Theorem 1 in [Vishnoi’s linear programming notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf).
All relevant hypotheses hold here:
Applying the theorem returns an exact rational matrix \(x^\star\) in polynomial time. By the equivalence proved in Section 1, this matrix maximizes welfare among all feasible real bundle matrices.
For a rational threshold \(q\), append the single linear inequality
\(\displaystyle \sum_{t=1}^{\tau}\sum_{I\in J}\mu_t a_{tI}x_{tI}\ge q.\)
The resulting rational linear system is feasible exactly when the answer to the threshold question is yes. Its encoding length remains polynomial in the original input length and the encoding length of \(q\). Polynomial-time rational linear programming feasibility therefore decides the threshold problem.
Thus the target is completely resolved: exact optimization is polynomial-time solvable, and the threshold problem is in \(\mathrm{P}\). An NP-hardness claim under polynomial-time reductions would consequently imply \(\mathrm{P}=\mathrm{NP}\). The finite-agent result mentioned in the question is unnecessary for this direct proof.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed polynomial-time result. The linear program exactly matches the task, its encoding size is polynomial, and the stated exact rational linear programming theorem applies. No major or minor issues require repair.
The definition \(a_{tI}=|I|v_{tI}\) agrees with \(V_t(I)\). Consequently, every utility is a linear function of the bundle entries.
Each part of the formulation is correct:
The asserted equivalence holds in both directions and for real bundle entries. No discrete allocation interpretation or expansion into individual agents is assumed.
The variable count \(n=\tau m\) is correct. The inequality count
\[ r=m+\tau(\tau-1)+2\tau m \]
correctly includes supply, ordered envy, and bound inequalities.
The coefficient calculations are valid. Subtracting rational endpoints and multiplying by a rational density require only a fixed number of rational arithmetic operations. Multiplication by \(\mu_t\) adds one further operation. Numerator and denominator bit lengths therefore remain \(O(L)\); these calculations take polynomial bit time. The additional bound coefficients and right-hand sides are fixed constants or input rationals.
The dense encoding bound \(O((r+1)(n+1)(L+1))\) is a valid polynomial upper bound. Large mass denominators affect coefficient bit lengths, rather than creating additional variables or constraints.
The prover states the needed theorem precisely enough: binary-encoded rational linear programs admit polynomial-bit-time exact optimization, with an exact rational optimal solution of polynomial encoding length when feasibility and a finite optimum hold.
The cited discussion following Theorem 1 explicitly supports conversion to exact optimization and a polynomial bound on the rational output length. [Vishnoi’s linear programming notes, page 2](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf).
All hypotheses are verified:
Thus the exact theorem yields an optimal rational matrix for the original optimization over real matrices. Neither uniqueness nor full dimensionality is required by the general theorem invoked.
Appending the inequality \(W(x)\ge q\) is exactly equivalent to the threshold question. It adds one rational constraint with polynomial encoding length, including the encoding length of \(q\). Exact rational LP feasibility therefore decides the question in polynomial time.
This covers arbitrary rational thresholds, including negative thresholds and thresholds exceeding one.
The argument remains valid when \(m=1\), when \(\tau=1\), when some interval values vanish, when types have identical valuations, and when supply constraints are redundant. These cases introduce no missing hypothesis.
The proof directly handles the society representation specified in the task. Its conclusion does not depend on the finite-agent theorem mentioned there. The final observation about NP-hardness implying \(\mathrm{P}=\mathrm{NP}\) is correct for standard polynomial-time reductions.
Required clarification or repair: None.
⟨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.