Answer: Polynomial-time solvable in the binary bit model.
Theorem 8 — class: algorithmic
Given rational type masses \(\mu_t>0\) summing to \(1\), per-capita budgets \(b_t\), and normalized nonnegative piecewise-linear valuations \(v_t\) on \([0,1]\) with \(K\) shared segments, define \(B_t=\mu_t b_t\) and let \(U_t^*\) be type \(t\)'s aggregate utility at the Fisher equilibrium. Compute a feasible pure aggregate allocation \(y_t=\mathbf{1}_{A_t}\), where each \(A_t\) is a union of at most \(K\) intervals and \(\sum_t y_t\leq 1\), such that \(\int_0^1 v_t(\theta)y_t(\theta)\,d\theta\geq U_t^*-\epsilon\) for every type \(t\).
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.
Each type has a positive binary-rational per-capita budget \(b_t\) and a nonnegative valuation density \(v_t\) on \([0,1]\), normalized by \(\int_0^1v_t(\theta)\,d\theta=1\). The input specifies rational breakpoints \(0=a_0<\cdots<a_K=1\) and rational coefficients such that \(v_t(\theta)=c_{tk}\theta+d_{tk}\) on each segment; discontinuities and identically zero segments are allowed.
The item interval has Lebesgue measure and unit supply at every point. Set \(B_t=\mu_tb_t\). Aggregate utility is \(U_t(x_t)=\int_0^1v_t(\theta)x_t(\theta)\,d\theta\), without an additional mass factor. Define \(U^*\) as the unique utility vector maximizing \(\sum_tB_t\log U_t(x_t)\) over nonnegative essentially bounded measurable allocations satisfying \(\sum_tx_t\leq1\) almost everywhere; these are the aggregate Fisher equilibrium utilities.
Given a binary-rational tolerance \(0<\epsilon<1\), compute sets \(A_t\subseteq[0,1]\), each a union of at most \(K\) intervals with rational endpoints, such that \(y_t=\mathbf{1}_{A_t}\), \(\sum_ty_t\leq1\) almost everywhere, and \(\int_0^1v_t(\theta)y_t(\theta)\,d\theta\geq U_t^*-\epsilon\) for every type. Empty sets and leftover supply are allowed. Let \(L\) be the total binary input length; there is no finite item-count parameter \(m\) in this model.
Is this allocation problem solvable in time polynomial in \(\tau,K,L,\log(1/\epsilon)\), or is it NP-hard?
For finitely many buyers, Gao and Kroer establish polynomial-time computation of the same additive utility guarantee with at most \(K\) intervals per buyer; their analysis counts arithmetic operations. [Primary source](https://arxiv.org/pdf/2010.03025).
The stated aggregate-type formulation is also a finite-buyer Fisher market with arbitrary positive budgets, so the verified result already covers its mathematical allocation problem; a distinct open continuous analogue has not been established.
Result. The problem is solvable in time polynomial in \(\tau,K,L,\log(1/\epsilon)\), in the binary bit model.
Gao and Kroer’s Theorem 8 establishes the finite-buyer utility guarantee and the bound of \(K\) intervals per buyer, with arithmetic-operation complexity. The proof below separately handles bit complexity and rational endpoints. [Gao–Kroer](https://arxiv.org/pdf/2010.03025)
1. Normalize the budgets and bound equilibrium utilities.
Set
\[
\]
\(S=\sum_t B_t\), \(w_t=B_t/S\), and \(w_{\min}=\min_t w_t\). Multiplying the objective by \(1/S\) leaves its maximizer unchanged. Thus we maximize \(\sum_t w_t\log U_t\), where \(\sum_t w_t=1\).
These rational numbers have bit lengths polynomial in \(L\). In particular, \(\log(1/w_{\min})\) is polynomially bounded in \(L\).
Every feasible utility satisfies \(0\leq U_t\leq1\). The feasible utility set is convex and compact: the allocation set is weak-star compact in the product of the spaces \(L^\infty([0,1])\), and integration against each \(v_t\in L^1([0,1])\) is weak-star continuous. Allocating the constant share \(1/\tau\) to every type gives strictly positive utilities. Consequently, the logarithmic objective attains its maximum at positive utilities, and strict concavity makes its maximizing utility vector unique.
We will use the bound \(U_t^*\geq w_t\). To prove it, consider the feasible utility vector \(e_t\), obtained by giving the whole interval to type \(t\). The directional derivative at the optimum toward \(e_t\) is nonpositive, so
\(\displaystyle 0\geq \sum_j\frac{w_j}{U_j^*}\bigl((e_t)_j-U_j^*\bigr) =\frac{w_t}{U_t^*}-1. \)
This proves the bound.
For \(\tau=1\), simply output \(A_1=[0,1]\). Henceforth assume \(\tau\geq2\).
2. Construct a well-bounded finite-dimensional utility body.
Write \(I_k=[a_{k-1},a_k]\) and define the rational number
\(\displaystyle \Lambda_{tk}=\int_{I_k}v_t(\theta)\,d\theta.\)
Call \((t,k)\) active when \(\Lambda_{tk}>0\). If \(\Lambda_{tk}=0\), nonnegativity implies that the affine density on that segment is identically zero. Such pairs can be omitted.
For an active pair, put \(\widehat v_{tk}=v_t/\Lambda_{tk}\) on \(I_k\); its integral is one. Let \(C_k\) be the set of utility vectors attainable on \(I_k\) under these normalized densities, with one coordinate for each active type. Omit segments with no active types, and set
\(\displaystyle C=\prod_k C_k,\qquad D=\sum_k\#\{t:\Lambda_{tk}>0\}\leq\tau K.\)
Each \(C_k\) is compact and convex by the same weak-star argument used above. It is also downward closed: decreasing a buyer’s desired utility can be implemented by multiplying that buyer’s allocation by a constant in \([0,1]\).
Moreover,
\(\displaystyle \{z\geq0:\sum_t z_t\leq1\}\subseteq C_k\subseteq[0,1]^{\dim C_k}. \)
The first inclusion follows by giving each type the constant allocation \(z_t\).
Let \(c\in\mathbb Q^D\) have every coordinate equal to \(1/(2\tau)\), and set \(r=1/(4\tau)\). The Euclidean ball of radius \(r\) around \(c\) lies in \(C\): every coordinate in that ball is positive, and the coordinate sum in any segment is at most \(3/4\). Also \(C\subseteq B_2(c,D)\). Thus we have explicit rational inner and outer ball bounds.
For \(z\in C\), define aggregate utilities by
\(\displaystyle U_t(z)=\sum_{k:\Lambda_{tk}>0}\Lambda_{tk}z_{tk}.\)
The image \(U(C)\) is exactly the original feasible utility set. Indeed, feasible allocations can be restricted to the segments, and independently feasible segment allocations can be concatenated.
3. Give an exact rational linear optimization oracle.
For a rational objective vector \(q\), linear optimization over \(C\) separates over segments. On a segment, assign each point to a type maximizing
\(\displaystyle q_{tk}\widehat v_{tk}(\theta),\)
including the additional option of leaving it unallocated, with objective value zero.
These functions are affine with rational coefficients. Compute all pairwise intersection points lying in the segment, partition at those points, and determine a maximizing function at a rational midpoint of each resulting open interval. Identical functions can be resolved by a fixed index order.
This allocation maximizes the objective pointwise, hence maximizes its integral. Its utility coordinates are rational, because each integral has the form
\(\displaystyle \int_\ell^h(c\theta+d)\,d\theta =\frac c2(h^2-\ell^2)+d(h-\ell). \)
There are at most polynomially many intersections and integrals. Every intermediate rational has bit length polynomial in \(L\) and the query length. Therefore this is an exact linear optimization oracle with polynomial bit complexity.
We use the standard Grötschel–Lovász–Schrijver oracle theorem: for a compact convex body with supplied rational inner and outer ball bounds, weak linear optimization and weak separation are polynomially interconvertible in the binary model. Weak optimization, with tolerance \(\delta\), returns a rational point within distance \(\delta\) of the body whose objective is within \(\delta\) of the optimum. Weak separation can be expressed as either a distance certificate or a rational normal \(q\), normalized by \(\|q\|_\infty=1\), satisfying \(q\cdot x\leq q\cdot y+\delta\) throughout the body. The norm conventions are polynomially equivalent. [Grötschel–Lovász–Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf)
The compactness, dimension, ball bounds, and oracle bit complexity required by this theorem have all been verified for \(C\).
4. Optimize a smooth extension of the logarithmic objective.
Set \(a=w_{\min}/2\). Define a convex function on the whole real line by
\(\displaystyle \phi_a(s)=-\log s\quad\text{when }s\geq a,\)
and
\(\displaystyle \phi_a(s)=-\log a-\frac{s-a}{a}+\frac{(s-a)^2}{2a^2} \quad\text{when }s<a. \)
The derivatives match at \(a\). On \([0,1]\), its second derivative is at least one: it equals \(1/a^2\) below \(a\) and \(1/s^2\) above \(a\).
Define
\(\displaystyle G(u)=\sum_t w_t\phi_a(u_t),\qquad f(z)=G(U(z)).\)
Because \(U_t^*\geq w_t\geq2a\), the gradient of \(G\) at \(U^*\) equals the gradient of the original negative logarithmic objective there. Its first-order optimality inequality therefore holds on the entire feasible utility set. Convexity implies that \(U^*\) also minimizes \(G\). Furthermore, for every feasible \(u\),
\(\displaystyle G(u)-G(U^*)\geq \frac{w_{\min}}2\|u-U^*\|_2^2. \)
Here the linear term in the strong-convexity inequality is nonnegative by first-order optimality.
At rational arguments, \(\nabla f\) is exactly rational. Function values can be approximated to any prescribed accuracy in polynomial bit time. For completeness, logarithms can be computed by scaling their arguments into \([1,2]\) and using
\(\displaystyle \log x=2\sum_{j=0}^{\infty} \frac{\bigl((x-1)/(x+1)\bigr)^{2j+1}}{2j+1}, \)
whose ratio parameter has absolute value at most \(1/3\) on that interval.
On \([-1,2]^D\), each aggregate utility lies in \([-1,2]\), since \(\sum_k\Lambda_{tk}=1\). The derivative formula gives the valid Lipschitz bound
\(\displaystyle H=\frac{4D}{a^2}\)
for \(f\) on that box.
To make the convex optimization application explicit, consider the compact epigraph body
\(\displaystyle E=\{(z,s):z\in C,\ f(z)\leq s\leq8/a\}. \)
For \(z\in C\), we have \(0\leq f(z)\leq3/a\). Thus \(E\) contains the ball of radius \(r\) centered at \((c,4/a)\), and it lies in the ball of radius \(D+8/a\) with that center.
It also has a polynomial-time weak separation oracle. Given \((z,s)\) and tolerance \(0<\delta\leq1\):
In the last two cases, the proximity certificate places \(z\) inside \([-1,2]^D\), so the stated Lipschitz bound applies. All cuts and value approximations have polynomial bit complexity.
Apply weak linear optimization to minimize \(s\) over \(E\), with tolerance
\(\displaystyle \eta=\frac{w_{\min}\epsilon^2}{8}, \qquad \xi=\frac{\eta}{2(1+HD)}. \)
It returns rational \((z,s)\) within distance \(\xi\) of \(E\), with \(s\leq G(U^*)+\xi\).
Recover an exactly feasible rational vector by setting
\(\displaystyle q_{tk}=\max\{0,\min\{1,z_{tk}\}-\xi\}. \)
Indeed, for some \((z_0,s_0)\in E\) within distance \(\xi\), each coordinate satisfies \(0\leq q_{tk}\leq(z_0)_{tk}\). Downward closure gives \(q\in C\). Also \(\|q-z_0\|_2\leq2D\xi\), whence
\(\displaystyle f(q)\leq f(z_0)+2HD\xi \leq G(U^*)+2\xi+2HD\xi =G(U^*)+\eta. \)
The strong-convexity inequality now gives
\(\displaystyle \|U(q)-U^*\|_2 \leq\sqrt{\frac{2\eta}{w_{\min}}} =\epsilon/2. \)
Thus \(U_t(q)\geq U_t^*-\epsilon/2\) for every type. Every numerical parameter used above has encoding length polynomial in \(\tau,K,L,\log(1/\epsilon)\).
5. Prove that feasible segment utilities admit ordered interval allocations.
Fix a segment \(I=[\ell,h]\) and its active types. Transform its normalized densities to \([0,1]\):
\(\displaystyle g_i(s)=(h-\ell)\widehat v_i(\ell+(h-\ell)s) =\alpha_i s+\beta_i. \)
Their integrals are one, so \(\alpha_i=2(1-\beta_i)\), and nonnegativity gives \(0\leq\beta_i\leq2\). Sort types by decreasing \(\beta_i\), allowing ties.
Every \(g_i\) is strictly positive in the open interval. For an earlier type \(i\) and a later type \(j\),
\(\displaystyle \frac{d}{ds}\frac{g_j(s)}{g_i(s)} =\frac{2(\beta_i-\beta_j)}{g_i(s)^2}\geq0. \)
We prove that any feasible target utilities can be attained or exceeded by giving types consecutive intervals in this order.
Start with a feasible allocation attaining at least the targets. Scale the first type’s allocation down to attain its target exactly. Write its allocation as \(x_1\), and let \(r\) satisfy
\(\displaystyle \int_0^r g_1(s)\,ds=\int_0^1g_1(s)x_1(s)\,ds.\)
For each later type \(j\), let \(m_j=\int_0^r g_1x_j\), and put \(T=\int_r^1g_1x_1\). Supply feasibility implies
\(\displaystyle \sum_{j>1}m_j \leq\int_0^r g_1(1-x_1) =\int_r^1g_1x_1=T. \)
Give the first type the whole prefix \([0,r]\). If \(0<r<1\) and \(T>0\), remove later types from that prefix and, outside it, replace their allocations by
\(\displaystyle y_j=x_j+(m_j/T)x_1.\)
This remains supply feasible because \(\sum_{j>1}m_j/T\leq1\). Monotonicity of \(g_j/g_1\) implies that the added utility is at least \((g_j(r)/g_1(r))m_j\), while the removed utility is at most that quantity. Thus no later type loses utility.
If \(T=0\), all \(m_j\) vanish and no transfer is needed. The cases \(r=0\) and \(r=1\) are immediate; in the latter case all later feasible utilities are zero.
Repeat on the suffix with the remaining types. Their ratio inequalities continue to hold on every suffix. Induction proves the claim. The last type can receive the entire remaining suffix.
Hence every \(q_{\cdot k}\in C_k\) can be implemented with one interval per active type on segment \(k\). This proof includes repeated normalized densities.
6. Compute rational cuts with controlled loss.
Let
\(\displaystyle M=1+\max_{t,k}\max\{ c_{tk}a_{k-1}+d_{tk},\ c_{tk}a_k+d_{tk}\}. \)
Endpoint values here are evaluated using the affine formula for that segment. Thus \(M\) bounds all densities almost everywhere and has polynomial bit length.
Use the rational cut tolerance \(\rho=\epsilon/(2KM)\). On each segment, process types in the order from Section 5. For each type except the last, use its original-density target \(\Lambda_{tk}q_{tk}\).
Starting at the current rational left endpoint, find the cut by bisection, returning a lower endpoint within \(\rho\) of the exact cut. Every comparison uses the exact rational integral formula from Section 3. Zero targets receive empty intervals.
These cuts always exist. To see this rigorously, compare with the exact ordered construction from Section 5. Inductively, the current rational left endpoint is no later than its exact counterpart. Nonnegativity implies that the exact cut from this earlier starting point is no later than the corresponding ideal cut. Rounding it downward preserves this invariant.
Each computed interval attains its target minus at most \(M\rho\). The last type receives the remaining suffix and attains at least its target. Consequently, for every type,
\(\displaystyle \int_{A_t}v_t \geq \sum_k\Lambda_{tk}q_{tk}-KM\rho \geq U_t^*-\epsilon. \)
Each \(A_t\) is a union of at most one interval from each original segment, hence at most \(K\) intervals. The intervals are disjoint almost everywhere and have rational endpoints.
There are at most \(\tau K\) cuts. Each requires \(O(\log(1/\rho))\) bisections, with polynomially bounded rational bit lengths throughout. Together with the oracle optimization, this proves the claimed polynomial running time.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem. It establishes a polynomial-time algorithm in the binary bit model, with the required additive utility guarantee, rational endpoints, and at most \(K\) intervals per type. I found no major or minor mathematical issues.
The oracle theorem used in Sections 3–4 does provide the guarantees stated in the proof. In particular, the cited 1981 formulation compares objectives and separating inequalities against the entire convex body, so the proof does not silently substitute those guarantees for guarantees concerning an eroded body.
Correct.
The aggregate budgets are \(B_t=\mu_tb_t\), and dividing all budgets by their positive sum preserves the maximizing utility vector. This matches the task’s aggregate utility convention; no additional mass factor is introduced.
The rational arithmetic defining \(S\), \(w_t\), and \(w_{\min}\) has polynomial encoding length. Positivity and binary encoding imply that \(\log(1/w_{\min})\) is polynomially bounded in \(L\).
The feasible allocation set is bounded and weak-star closed, hence weak-star compact. Integration against the integrable densities is weak-star continuous, giving a compact, convex feasible utility set. The constant-share allocation supplies positive utilities to every type. The logarithmic objective therefore has a positive maximizing utility vector, and strict concavity gives uniqueness.
The directional-derivative computation is valid: the optimum has positive coordinates, and the segment toward \(e_t\) remains positive sufficiently near the optimum. The displayed derivative simplifies correctly to
\[
\frac{w_t}{U_t^*}-1.
\]
Thus \(U_t^*\geq w_t\).
The case \(\tau=1\) is correctly handled.
Correct.
Because every segment has positive length and its affine density is nonnegative, zero integral implies that the affine formula vanishes identically. Omitting inactive pairs therefore loses no attainable utility.
Normalization of an active density gives integral one on its segment. Constant allocations prove the simplex inclusion, and unit supply proves the coordinate upper bounds. Coordinatewise scaling establishes downward closure.
The inner-ball claim is valid. A perturbation of Euclidean norm at most \(r\) changes each coordinate by at most \(r\), so coordinates remain positive. With at most \(\tau\) active coordinates on a segment, its coordinate sum is at most
\[
\tau\left(\frac{1}{2\tau}+\frac{1}{4\tau}\right)=\frac34.
\]
The stated outer radius \(D\) is also sufficient.
The map \(U\) correctly reconstructs original utilities. Restriction and concatenation of allocations show that \(U(C)\) is exactly the original feasible utility set. Segment endpoints cause no difficulty because feasibility and utilities are defined almost everywhere.
Correct.
Pointwise maximization of the weighted affine densities, with zero as an additional option, maximizes the integral objective. The zero option correctly handles negative objective coefficients and leftover supply.
Pairwise intersections partition each segment into intervals on which the ordering of nonidentical affine functions cannot change. Identical functions can be consistently resolved by index. All intersection points, midpoints, and integrated utility coordinates are rational.
There are polynomially many intersections. Each computation uses polynomially many rational arithmetic operations on numbers of polynomial encoding length. Thus the claimed exact oracle has polynomial bit complexity.
The cited oracle result is applicable. The original paper defines weak optimization by proximity to the body and additive objective accuracy against every point of the body; its weak separation definition likewise permits proximity certification or an approximate separating inequality against the entire body. Theorem 3.1 establishes polynomial-time equivalence under supplied inner and outer ball bounds. These are the contracts used here. The normalization of separating normals requires only the stated polynomial changes between norm conventions. [Grötschel–Lovász–Schrijver, Section 1 and Theorem 3.1](https://ir.cwi.nl/pub/10046/10046D.pdf)
All required geometric and encoding hypotheses have been checked for \(C\). Moreover, \(D\geq\tau\geq2\), so the source’s dimension restriction presents no omitted case.
Correct.
The two definitions of \(\phi_a\) agree in value and derivative at \(a\), and the function is convex on the whole real line. Its second derivative on \([0,1]\) is at least one.
Since \(U_t^*\geq w_t\geq2a\), the extended objective has the original negative-logarithmic gradient at \(U^*\). Its first-order optimality inequality therefore proves that \(U^*\) also minimizes \(G\). The stated strong-convexity estimate follows with the correct constant \(w_{\min}/2\).
The gradient at rational arguments is rational. The logarithm series and scaling procedure give polynomial-time value approximation: the series converges geometrically on the stated interval, and the scaling exponent has polynomial size.
The aggregate utility range on \([-1,2]^D\) is correct because each type’s segment weights sum to one. The derivative bounds validate the conservative Lipschitz constant \(H=4D/a^2\).
The epigraph body \(E\) is compact, convex, and has the stated ball bounds. On \(C\), the objective satisfies \(0\leq f\leq3/a\), leaving sufficient vertical clearance around the proposed inner-ball center.
All four branches of the weak separation procedure are valid:
The proximity certificate also ensures that evaluations requiring the Lipschitz bound occur inside its stated box.
The recovery formula yields \(0\leq q\leq z_0\) coordinatewise for a nearby feasible \(z_0\). Downward closure therefore establishes exact feasibility, despite the optimizer returning only approximate feasibility.
The objective-error calculation is correct:
\[
2\xi+2HD\xi=\eta.
\]
The subsequent strong-convexity calculation gives utility distance at most \(\epsilon/2\), as claimed.
All numerical parameters have polynomial encoding length. Their potentially large numerical magnitudes do not produce a polynomial dependence on \(1/\epsilon\) or \(1/w_{\min}\).
Correct.
The transformed affine densities satisfy the stated normalization relation and intercept bounds. Each is positive in the open interval, including the endpoint-zero cases.
The ratio derivative is correctly computed:
\[
\frac{d}{ds}\frac{g_j(s)}{g_i(s)}
=\frac{2(\beta_i-\beta_j)}{g_i(s)^2}.
\]
Its sign matches the prescribed decreasing-intercept order.
The transfer argument correctly preserves later types’ utilities. Supply feasibility bounds the total transfer coefficient by one. Ratio monotonicity bounds removed utility from above and added utility from below by the same threshold expression.
The exceptional cases are covered:
Repeating the argument on suffixes is legitimate because the ratio monotonicity persists there. This establishes one interval per active type per segment for every feasible target vector.
Correct.
An affine function’s maximum on a segment occurs at an endpoint, so \(M\) bounds all original densities almost everywhere. Using each segment’s own affine formula correctly accommodates discontinuities.
The comparison with the exact ordered construction establishes existence of every requested cut. Starting earlier cannot move the exact target-attaining cut later, and downward rounding preserves the induction invariant.
Each rounded cut loses at most \(M\rho\) utility. The last type receives a suffix containing its ideal suffix, so it incurs no loss. Summing over segments gives
\[
KM\rho=\epsilon/2,
\]
which combines with the optimization error to deliver the required \(\epsilon\) guarantee.
Zero targets, inactive pairs, and entirely valueless segments are handled correctly. The produced allocations are disjoint almost everywhere, and each type receives at most one interval from each original segment.
Bisection uses exact rational comparisons and polynomially many iterations. Rational endpoint encoding lengths remain polynomial throughout the sequential construction. The algorithm depends on the listed support and segments; it introduces no finite item-count parameter.
The preliminary attribution to Gao–Kroer is also accurate: Theorem 8 gives the finite-buyer additive guarantee and interval bound, while this proof separately supplies the bit-complexity and rational-endpoint analysis. [Gao–Kroer, Theorem 8](https://arxiv.org/pdf/2010.03025)
No repair is required. The claimed polynomial-time classification follows from the argument as written.
⟨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.