Answer: Polynomial-time solvable under the promised verifier, using at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls.
Theorem 1 — class: algorithmic
Given a finite item set \([m]\), a distribution \(\mu\) over buyer types with support size \(\tau\), per-capita item supplies \(b_j\), and a population scale \(N\) with \(N\mu_t,Nb_j\in\mathbb Z\), let \(x^*_{t,S}\) be a feasible per-capita fractional allocation of bundle \(S\) to type \(t\). Given an efficient \(\alpha\)-integrality-gap verifier for the aggregate count-allocation polytope, find a finite lottery over feasible integer count allocations \(y_{t,S}\) such that \(\mathbb E[y_{t,S}/N]=\frac{\alpha}{1+4\varepsilon}x^*_{t,S}\) for every type and bundle. The decomposition should use at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls, where \(s\) is the number of nonzero coordinates of \(Nx^*\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Let \(\sum_t\mu_t=1\), \(m\ge1\), \(b_j\in\mathbb Q_{\ge0}\), and \(N\in\mathbb Z_{>0}\), encoded in binary, with \(N\mu_t,Nb_j\in\mathbb Z\).
Coordinates are pairs \((t,S)\) with \(S\subseteq[m]\), including the empty bundle. Define the count-allocation polytope \(Q=\{z\ge0:\sum_Sz_{t,S}\le N\mu_t\ \forall t,\ \sum_t\sum_{S\ni j}z_{t,S}\le Nb_j\ \forall j\}\); feasible integer allocations are \(Q\cap\mathbb Z^{\tau2^m}\). Buyers may remain unassigned and supplies unused.
The input includes a sparsely encoded rational allocation \(x^*\) with \(Nx^*\in Q\), rational parameters \(0<\alpha\le1\) and \(0<\varepsilon\le1/2\), and \(s=|\operatorname{supp}(Nx^*)|\ge2\). Let \(L\) be the total binary input length.
An available verifier, on sparsely encoded rational inputs \(w\) of either sign and \(z\in Q\), returns a sparsely encoded \(y\in Q\cap\mathbb Z^{\tau2^m}\) satisfying \(w^Ty\ge\alpha w^Tz\), in time polynomial in \(m,\tau\) and its input bit length.
The required output is a finite lottery with binary rational probabilities \(\lambda_k\ge0\), \(\sum_k\lambda_k=1\), and sparsely encoded feasible integer allocations \(y^k\), satisfying \(\sum_k\lambda_k y^k_{t,S}/N=\alpha x^*_{t,S}/(1+4\varepsilon)\) for every coordinate, using at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls.
Is this lottery construction solvable in time polynomial in \(m,\tau,s,L,\varepsilon^{-1}\), with the stated verifier-call bound, or is it NP-hard even with the promised efficient verifier?
Elbassioni, Mehlhorn, and Ramezani establish the corresponding decomposition for arbitrary packing polytopes, with the stated call bound and at most \(s(1+\lceil\varepsilon^{-2}\ln s\rceil)\) lottery outcomes. Their result does not separately establish bit complexity for a society compressed into binary population counts. [Source](https://arxiv.org/pdf/1408.1577v4).
The construction is polynomial-time solvable under the promised verifier, with at most \(s\lceil\varepsilon^{-2}\ln s\rceil\) verifier calls. It can also achieve the cited bound of \(s(1+\lceil\varepsilon^{-2}\ln s\rceil)\) outcomes.
Here, “binary rational” means a rational encoded by its numerator and denominator in binary. If probabilities were required to be dyadic, exact equality could fail even in elementary examples.
The [cited paper](https://arxiv.org/pdf/1408.1577v4) supplies the corresponding decomposition theorem. The proof below gives a rational implementation and explicitly bounds its bit complexity, without expanding the population.
Put \(q=Nx^*\), and enumerate its support as \(I=\{1,\ldots,s\}\). Thus \(q_i>0\) for every \(i\in I\). Define the required expectation in count units by
\(d_i=\alpha q_i/(1+4\varepsilon)\).
All coordinates outside \(I\) must have expectation zero.
The polytope \(Q\) is downward closed: if \(0\le u\le v\) coordinatewise and \(v\in Q\), then \(u\in Q\), because every constraint has nonnegative coefficients. Consequently, we can replace every verifier output by its restriction to \(I\). This preserves feasibility, integrality, and its scalar product with any weight vector supported on \(I\).
Also, every coordinate of every feasible allocation is at most \(N\mu_t\le N\). Hence every integer count has \(O(\log N)\) bits.
We first construct a rational threshold \(H\) satisfying
\(\displaystyle \frac{19}{20}\frac{\ln s}{\varepsilon^2}\le H\le\frac{\ln s}{\varepsilon^2}.\)
Let \(M=\lceil20/\varepsilon\rceil\), and set
\(\displaystyle \ell=\sum_{k=M+1}^{sM}\frac1k,\qquad H=\frac{\ell}{\varepsilon^2}.\)
The right and left Riemann sums for the decreasing function \(1/x\) on \([1,s]\), with mesh \(1/M\), show that
\(\displaystyle \ell\le\ln s\le\ell+\frac1M-\frac1{sM}\le\ell+\frac{\varepsilon}{20}.\)
Since \(s\ge2\), we have \(\ln s\ge\ln2\ge1/2\). Therefore
\(\displaystyle \ell\ge\left(1-\frac{\varepsilon}{10}\right)\ln s\ge\frac{19}{20}\ln s,\)
which proves the threshold bounds.
There are \(O(s\varepsilon^{-1})\) summands. Using the product of their denominators as a common denominator shows that \(\ell\), and hence \(H\), can be computed exactly with polynomially many bits and operations.
For each coordinate \(i\in I\), initialize a load \(h_i=0\) and a weight \(p_i=1\). A coordinate is *active* when \(h_i<H\); inactive coordinates have weight zero.
While an active coordinate remains, perform the following iteration.
\(\displaystyle w_i=\frac{p_i}{\alpha q_i}\)
on active coordinates, with all other weights zero.
\(\displaystyle a_i=\frac{y_i}{\alpha q_i}.\)
\(\displaystyle \delta=\frac1{\max_{i\text{ active}}a_i}.\)
Record the pair \((\delta,y)\).
\(\displaystyle p_i\leftarrow p_i(1-\varepsilon\delta a_i).\)
Then set the weights of newly inactive coordinates to zero.
Every arithmetic operation is rational.
To verify that an iteration is well defined, let \(A\) denote its active set and \(P=\sum_{i\in A}p_i\). The verifier guarantee gives
\(\displaystyle \sum_{i\in A}p_i a_i=w^Ty\ge\alpha w^Tq=\sum_{i\in A}p_i=P.\)
Thus \(\max_{i\in A}a_i\ge1\), so \(0<\delta\le1\). Moreover,
\(\displaystyle 0\le\delta a_i\le1\quad(i\in A).\)
Every updated active weight therefore stays positive, since \(1-\varepsilon\delta a_i\ge1-\varepsilon\ge1/2\).
Charge each iteration to an active coordinate attaining the maximum in the definition of \(\delta\). Its load increases by exactly one.
Loads never decrease. Immediately before a coordinate receives its \(r\)-th charge, its load is at least \(r-1\), and it must still be below \(H\). Hence it receives at most \(\lceil H\rceil\) charges. This also proves termination.
If \(K\) is the number of iterations, then
\(\displaystyle K\le s\lceil H\rceil\le s\left\lceil\varepsilon^{-2}\ln s\right\rceil.\)
There is exactly one verifier call per iteration.
Write the recorded pairs as \((\delta_r,y^r)\), and let
\(\displaystyle D=\sum_{r=1}^K\delta_r.\)
We prove \(D/H\le1+4\varepsilon\).
In any iteration, before removing newly inactive coordinates, the sum of updated active weights is
\(\displaystyle \widetilde P=P-\varepsilon\delta\sum_{i\in A}p_i a_i \le P(1-\varepsilon\delta)\le P e^{-\varepsilon\delta}.\)
Removing coordinates only decreases this sum. Starting from total weight \(s\), the updated weight sum in the final iteration is consequently at most \(s e^{-\varepsilon D}\).
Choose a coordinate \(i_0\) active immediately before the final iteration. Monotonicity of loads implies that it was active in every preceding iteration. Its final load satisfies \(h_{i_0}\le H+1\).
For \(0\le u\le1\), concavity of the logarithm gives
\(\displaystyle \ln(1-\varepsilon u)\ge u\ln(1-\varepsilon).\)
Applying this inequality to every weight update of \(i_0\), its final weight before removal satisfies
\(\displaystyle \widetilde p_{i_0}\ge(1-\varepsilon)^{h_{i_0}}\ge(1-\varepsilon)^{H+1}.\)
Combining the lower and upper bounds and taking logarithms yields
\(\displaystyle \frac DH\le\frac{\ln s}{\varepsilon H} +\left(1+\frac1H\right)\frac{-\ln(1-\varepsilon)}{\varepsilon}.\)
For \(0<\varepsilon\le1/2\), the convergent logarithm series gives
\(\displaystyle \frac{-\ln(1-\varepsilon)}{\varepsilon} =1+\sum_{k\ge1}\frac{\varepsilon^k}{k+1} \le1+\frac{\varepsilon}{2(1-\varepsilon)} \le1+\varepsilon.\)
The threshold bounds now imply
\(\displaystyle \frac{\ln s}{\varepsilon H}\le\frac{20}{19}\varepsilon\)
and, using \(\ln s\ge1/2\) and \((1+\varepsilon)\varepsilon\le3/4\),
\(\displaystyle \frac{1+\varepsilon}{H} \le\frac{40}{19}(1+\varepsilon)\varepsilon^2 \le\frac{30}{19}\varepsilon.\)
Therefore
\(\displaystyle \frac DH\le1+\frac{69}{19}\varepsilon<1+4\varepsilon.\)
Assign probability \(\lambda_r=\delta_r/D\) to \(y^r\). These are positive rational probabilities summing to one. At termination every load is at least \(H\), so
\(\displaystyle \sum_{r=1}^K\lambda_r y_i^r =\frac{\alpha q_i h_i}{D} \ge\frac{\alpha q_i H}{D} \ge d_i\qquad(i\in I).\)
Thus the resulting lottery dominates the target.
We now correct each coordinate in turn, preserving the expectations of all other coordinates.
For the current coordinate \(i\), let its surplus be
\(\displaystyle \Delta=\sum_k\lambda_k y_i^k-d_i\ge0.\)
Ignore outcomes with zero probability or zero \(i\)-th count. For an outcome \((\lambda,y)\) with \(\lambda>0\) and \(y_i>0\):
If \(r>0\), replace the resulting outcome by two outcomes: \(y\) with probability \(\lambda-r\), and \(y-e_i\) with probability \(r\).
In the second case, \(a<y_i\), so the additional deletion is permissible. The split decreases the expectation in coordinate \(i\) by exactly \(r\), and preserves every other coordinate’s expectation and the total probability.
All modified allocations are nonnegative integer vectors dominated by their original allocations. Downward closure therefore guarantees feasibility.
There is sufficient count to remove: the required decrease is the current expectation minus the nonnegative target. Consequently, this procedure reaches \(\Delta=0\). Each coordinate requires at most one split, because a split completes its correction.
After all \(s\) corrections, the expectation is exactly \(d\), and the number of outcomes is at most
\(\displaystyle K+s\le s\left(1+\left\lceil\varepsilon^{-2}\ln s\right\rceil\right).\)
Outside \(I\), every outcome is zero. Dividing the count expectations by \(N\) proves every required coordinate equality.
It remains to check that the algorithms above are polynomial in the specified parameters.
Covering arithmetic. Each \(q_i\), \(\alpha q_i\), and verifier-output count has \(O(L)\) bits. Every coefficient \(a_i=y_i/(\alpha q_i)\), increment \(\delta\), and update factor \(1-\varepsilon\delta a_i\) therefore has \(O(L)\) bits.
Each load is a sum of at most \(K\) such rational increments, and each weight is a product of at most \(K\) such rational factors. Taking products of denominators bounds their bit lengths by \(O(KL+\log K)\). The sparse verifier inputs consequently have polynomial length.
The verifier’s promised running time bounds its output length polynomially. Reading that output and restricting it to \(I\) is therefore polynomial-time. Every retained outcome has at most \(s\) coordinates, each with count at most \(N\).
Initial probabilities. The sum \(D\) and all probabilities \(\delta_r/D\) have polynomial bit length by the same denominator-product bound.
Correction arithmetic. Choose a common denominator \(B\) for all initial probabilities and all target coordinates \(d_i\). Its bit length is polynomial, since there are polynomially many rationals of polynomial bit length.
Throughout correction, every probability remains an integer multiple of \(1/B\): surpluses are integer linear combinations of probabilities minus a target coordinate, and splitting uses only those surpluses and subtraction. Since probabilities remain between zero and one, their numerators require at most \(O(\log B)\) bits. Integer deletions and the divisions used to compute floors are also polynomial-time.
There are at most \(K+s\) outcomes and \(O(s(K+s))\) correction operations. None of these operations loops over \(N\) buyers or deletes counts one unit at a time.
Thus the complete construction runs in time polynomial in \(m,\tau,s,L,\varepsilon^{-1}\), with the stated verifier-call bound.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time construction under the promised verifier, with the required verifier-call bound and exact rational probabilities. No major or minor mathematical gaps were found.
The encoding convention is appropriate: “binary rational” means a numerator and denominator encoded in binary. The proof explicitly states this interpretation and does not assume that probabilities must be dyadic.
This step is correct.
The restriction also ensures that every final outcome has zero counts outside \(I\), as required by the zero target expectations there.
The threshold construction and its estimates are correct.
The sum defining \(\ell\) is the right Riemann sum for \(1/x\) on \([1,s]\) with mesh \(1/M\). The corresponding left sum differs by exactly \(1/M-1/(sM)\). Hence the stated inequalities follow.
The deductions using \(M\ge20/\varepsilon\), \(\ln s\ge1/2\), and \(\varepsilon\le1/2\) correctly establish
\[
\frac{19}{20}\frac{\ln s}{\varepsilon^2}\le H\le\frac{\ln s}{\varepsilon^2}.
\]
There are polynomially many summands in the permitted parameters. Their denominator-product representation has polynomial bit length, so exact computation of \(H\) is justified. No numerical evaluation of \(\ln s\) is needed by the algorithm.
Every verifier call satisfies the promised input conditions: \(q\) is feasible, and \(w\) is a sparsely encoded rational vector.
The normalization in the verifier inequality is correct:
\[
w^Ty=\sum_{i\in A}p_i a_i\ge\alpha w^Tq=\sum_{i\in A}p_i=P.
\]
Before termination, \(A\) is nonempty and all its weights are positive. Therefore \(P>0\), and the inequality implies \(\max_{i\in A}a_i\ge1\). Consequently, \(\delta\) is defined, satisfies \(0<\delta\le1\), and gives \(0\le\delta a_i\le1\) on active coordinates.
The weight factors are at least \(1-\varepsilon\ge1/2\). Thus an active coordinate cannot acquire zero weight through an update.
The charging argument is valid even when a coordinate receives additional load in iterations charged elsewhere. Those additional increases only strengthen the lower bound on its load before subsequent charges. The condition \(r-1<H\) limits each coordinate to at most \(\lceil H\rceil\) charges, including when \(H\) is an integer.
This proves both termination and
\[
K\le s\lceil H\rceil\le s\left\lceil\varepsilon^{-2}\ln s\right\rceil.
\]
Exactly one verifier call occurs per iteration.
The potential argument is correct, including its treatment of coordinate removal.
The contraction bound applies to the updated active weights before newly inactive coordinates are removed. Earlier removals only reduce the starting potential for subsequent iterations. Thus the pre-removal weight sum in the final iteration is indeed at most \(s e^{-\varepsilon D}\).
A coordinate active immediately before the final iteration was active throughout all earlier iterations, because loads never decrease. Its final load is at most \(H+1\), since its last increment is at most one.
The logarithmic inequality follows from concavity on the specified interval. Its application to this coordinate’s complete update history yields the stated lower bound on its final pre-removal weight.
Combining the bounds gives the displayed estimate for \(D/H\). The subsequent constants check out:
Therefore \(D/H<1+4\varepsilon\). Since \(D>0\), the probabilities \(\delta_r/D\) are well defined and sum to one. Every terminal load is at least \(H\), giving the required coordinatewise domination of \(d\).
Loads on coordinates already inactive may exceed \(H+1\); the proof does not use that bound for them.
The correction procedure is valid.
For a complete deletion, the decrease in expectation is exactly \(\lambda y_i\), matching the amount subtracted from the surplus.
For a partial deletion, \(\Delta<\lambda y_i\) implies
\[
a=\lfloor\Delta/\lambda\rfloor<y_i.
\]
The remaining count is therefore at least one if an additional deletion is needed.
When \(r>0\), the replacement probabilities \(\lambda-r\) and \(r\) are positive and sum to \(\lambda\). The two allocations differ only by one unit in coordinate \(i\), so this split decreases that coordinate’s expectation by exactly \(r\) and preserves every other expectation.
All deletions preserve nonnegativity, integrality, and feasibility by downward closure. The total removable expectation is sufficient because the target is nonnegative. A partial-deletion step completes the correction, so each coordinate creates at most one additional outcome.
Consequently, the corrected lottery has exact expectation \(d\), has at most \(K+s\) outcomes, and satisfies all required equalities after division by \(N\).
The bit-complexity argument addresses the compressed population representation successfully.
The counts are bounded by \(N\), and the quantities \(q_i\), \(\alpha q_i\), and \(\varepsilon\) have bit lengths bounded by the original input length up to constant factors. Each individual coefficient, step size, load increment, and weight-update factor therefore has \(O(L)\) bits.
Loads are sums and weights are products of at most \(K\) such rationals. Denominator-product bounds consequently give polynomial bit lengths. In particular, repeated verifier calls do not cause an uncontrolled recursive increase in input length: retained counts remain bounded by \(N\), while weights have the explicit accumulated-factor bound.
The initial probabilities also have polynomial bit length. During correction, the common-denominator argument is valid: targets and probabilities are multiples of \(1/B\), integer deletions preserve this property, and the residual \(r=\Delta-\lambda a\) is another multiple of \(1/B\).
The number of outcomes and correction operations is polynomial. Floors and batched deletions operate on binary integers and rationals, without iterating over the population.
The claimed call and outcome bounds match Theorem 1 of the [cited paper](https://arxiv.org/pdf/1408.1577v4). The submitted proof supplies its own covering analysis and correction procedure, so its compressed-input bit-complexity conclusion does not depend on an unstated bit-complexity assertion from that theorem.
The output resolves the requested polynomial-time alternative under the verifier promise. No additional clarification or repair is needed.
⟨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.