Answer: Polynomial-time solvable under the verifier promise, using at most \(\lceil d\epsilon^{-2}\rceil-1\) verifier calls independently of \(N\).
Theorem 1 — class: algorithmic
Given rational masses \(\mu_t=N_t/N\) for \(\tau\) complete valuation types, a type-indexed packing relaxation \(P_\mu\subseteq[0,1]^d\) with \(d\) depending on types and bundle options, an optimal fractional welfare point \(x^\star\), and an efficient \(\alpha\)-integrality-gap verifier returning feasible integral count-allocation patterns, can one output a lottery \((\lambda_j,z^j)\) over those patterns with \(\left\|\sum_j\lambda_j z^j-x^\star/\alpha\right\|_2\le\epsilon\) using \(O(d\epsilon^{-2})\) verifier calls independently of \(N\)? Each pattern records how many members of each type receive each integral bundle.
A society is given by its support: the list of \(\tau\) complete valuation types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) goods; each type has explicitly supplied nonnegative rational bundle valuations, with empty-bundle value \(0\), and an explicit list \(B_t\) of permitted nonempty bundles. Put \(d=\sum_t|B_t|\ge1\).
A binary integer \(N\ge1\) is supplied with \(N_t=N\mu_t\in\mathbb Z_{>0}\). Coordinates \(x_{t,b}\) represent allocated mass. Unallocated mass is permitted.
The input includes a nonempty rational polytope \(P_\mu\subseteq[0,1]^d\), given by linear inequalities, satisfying \(\sum_{b\in B_t}x_{t,b}\le\mu_t\) and the packing property: \(0\le y\le x\in P_\mu\Rightarrow y\in P_\mu\).
Feasible integral count patterns are exactly \(c\in\mathbb Z_{\ge0}^d\) with \(c/N\in P_\mu\); write \(S_N=\{c/N:c\text{ is feasible}\}\). Counts specify how many type members receive each bundle, without listing individual members.
Given also are rational \(\alpha\ge1\), \(0<\epsilon<1\), a rational welfare maximizer \(x^\star\in\operatorname*{arg\,max}_{x\in P_\mu}\sum_{t,b}v_t(b)x_{t,b}\), and a verifier \(\mathcal A\) returning \(z\in S_N\) for every nonnegative rational \(w\), with \(\alpha w\cdot\mathcal A(w)\ge\max_{x\in P_\mu}w\cdot x\). The verifier runs in polynomial time in the input and query bit lengths.
The requested output is a finite lottery with rational \(\lambda_j\ge0\), \(\sum_j\lambda_j=1\), and normalized feasible count patterns \(z^j\in S_N\), satisfying \(\left\|\sum_j\lambda_jz^j-x^\star/\alpha\right\|_2\le\epsilon\). Let \(L\) be the total binary input length.
Is this lottery construction polynomial-time solvable in \(m,\tau,d,L,\epsilon^{-1}\), using \(O(d\epsilon^{-2})\) verifier calls independently of \(N\), or is it NP-hard even with the promised efficient verifier?
For binary allocation coordinates in a packing polytope, an \(\epsilon\)-accurate decomposition of \(x^\star/\alpha\) uses at most \(\lceil n\epsilon^{-2}\rceil-1\) verifier calls ([Kraft–Fadaei–Bichler](https://pub.dss.in.tum.de/bichler-research/2014_kraft_convex_decomposition.pdf)).
The checked sources do not explicitly settle the support-encoded normalized count-pattern formulation above.
The lottery construction is polynomial-time solvable under the stated verifier promise. It uses at most \(\lceil d\epsilon^{-2}\rceil-1\) verifier calls, independently of \(N\), and produces rational weights of polynomial bit length.
The proof below applies to any supplied rational feasible point \(x^\star\); its welfare optimality is not needed.
Index the allocation coordinates by \(i\in\{1,\ldots,d\}\), and write \(P=P_\mu\) and \(q=x^\star/\alpha\). Since \(x^\star\in[0,1]^d\) and \(\alpha\ge1\), we have \(q\in[0,1]^d\).
First, \(0\in S_N\): choose any \(x\in P\), which exists by nonemptiness, and apply packing to \(0\le x\).
For any rational vector \(r\in\mathbb Q^d\), define \(r_i^+=\max\{r_i,0\}\). Make one verifier call \(a=\mathcal A(r^+)\), and define
\(\displaystyle T(r)_i=\begin{cases}a_i,&r_i\ge0,\\0,&r_i<0.\end{cases}\)
This modification preserves count integrality. Indeed, writing \(a=c/N\), it merely replaces some integer counts \(c_i\) by zero. Moreover, \(0\le T(r)\le a\), so packing gives \(T(r)\in S_N\).
The verifier guarantee implies
\(\displaystyle r\cdot T(r)=r^+\cdot a \ge\frac1\alpha\max_{x\in P}r^+\cdot x \ge\frac1\alpha r^+\cdot x^\star \ge\frac1\alpha r\cdot x^\star =r\cdot q.\)
The last inequality uses \(x^\star\ge0\). Consequently,
\[\displaystyle r\cdot\bigl(T(r)-q\bigr)\ge0.\tag{1}\]
Thus one nonnegative-weight verifier call supplies a feasible normalized count pattern satisfying the needed inequality in any rational signed direction.
Set
\(\displaystyle K=\left\lceil d\epsilon^{-2}\right\rceil-1.\)
Initialize \(z^0=0\) and \(y_0=0\). For \(k=0,\ldots,K-1\), perform:
Induction on \(k\) gives
\[\displaystyle y_k=\frac1{k+1}\sum_{j=0}^{k}z^j.\tag{2}\]
Return the patterns \(z^0,\ldots,z^K\), each with weight
\(\displaystyle \lambda_j=\frac1{K+1}.\)
Every pattern belongs to \(S_N\), every weight is rational and positive, and the weights sum to one. Repeated patterns may be combined by adding their weights.
Define \(E_k=\|y_k-q\|_2^2\). Applying (1) with \(r_k=q-y_k\) yields
\[\displaystyle (y_k-q)\cdot(z^{k+1}-q)\le0.\tag{3}\]
Also, since \(z^{k+1},q\in[0,1]^d\),
\[\displaystyle \|z^{k+1}-q\|_2^2\le d.\tag{4}\]
Subtracting \(q\) from the update gives
\(\displaystyle y_{k+1}-q =\frac{k+1}{k+2}(y_k-q)+\frac1{k+2}(z^{k+1}-q).\)
Expanding the squared norm and using (3) and (4), we obtain
\[\displaystyle E_{k+1} \le\frac{(k+1)^2E_k+d}{(k+2)^2}.\tag{5}\]
We claim that
\[\displaystyle E_k\le\frac d{k+1}\qquad\text{for every }k\ge0.\tag{6}\]
For \(k=0\), this follows from \(y_0=0\) and \(q\in[0,1]^d\). If (6) holds at \(k\), then (5) gives
\(\displaystyle E_{k+1} \le\frac{(k+1)^2\,d/(k+1)+d}{(k+2)^2} =\frac{d(k+2)}{(k+2)^2} =\frac d{k+2}.\)
This proves (6) by induction. Since \(K+1=\lceil d\epsilon^{-2}\rceil\),
\(\displaystyle \left\|\sum_{j=0}^{K}\lambda_jz^j-\frac{x^\star}{\alpha}\right\|_2^2 =E_K \le\frac d{K+1} \le\epsilon^2.\)
The returned lottery therefore satisfies the requested error bound.
The averaging rule keeps all arithmetic polynomially bounded.
Write \(z^j=c^j/N\). Each \(c_i^j\) is an integer between zero and \(N\). Maintaining the integer sums
\(\displaystyle C_i^{(k)}=\sum_{j=1}^{k}c_i^j\)
gives the exact representation
\(\displaystyle (y_k)_i=\frac{C_i^{(k)}}{N(k+1)},\qquad 0\le C_i^{(k)}\le kN.\)
Thus each coordinate of \(y_k\) has bit length \(O(\log N+\log(k+1))\). Each coordinate of \(q=x^\star/\alpha\) has bit length \(O(L)\), so the coordinates of the actual nonnegative verifier query \((q-y_k)^+\) have bit length \(O(L+\log(K+1))\).
If the verifier returns rational coordinates rather than integer counts, multiplying them by \(N\) recovers the exact integer counts promised by membership in \(S_N\). These can then be stored in canonical count form. This conversion is polynomial-time because the verifier’s output length is bounded by its promised polynomial running time.
There are \(K=O(d\epsilon^{-2})\) calls. Outside the verifier, each iteration uses polynomially many arithmetic operations on numbers of polynomial bit length. The output has \(K+1\) patterns, each encoded using \(d\) binary counts and the common denominator \(N\), together with weights \(1/(K+1)\).
Hence the total running time and output length are polynomial in \(m,\tau,d,L,\epsilon^{-1}\). The number of verifier calls has no dependence on \(N\); the arithmetic and output depend on its binary encoding through \(\log N\). No individual society members are enumerated.
The supplied type constraints imply, for every \(z\in S_N\),
\(\displaystyle \sum_i z_i =\sum_t\sum_{b\in B_t}z_{t,b} \le\sum_t\mu_t=1.\)
Likewise, \(\sum_iq_i\le1/\alpha\le1\). For nonnegative vectors with coordinate sum at most one, the squared Euclidean norm is at most one. Therefore,
\(\displaystyle \|z-q\|_2^2 =\|z\|_2^2+\|q\|_2^2-2z\cdot q \le2.\)
Together with the cube bound, this gives \(\|z-q\|_2^2\le D\), where \(D=\min\{d,2\}\). Also, \(E_0=\|q\|_2^2\le1\le D\). Replacing \(d\) by \(D\) throughout the same induction proves that only
\(\displaystyle \left\lceil\min\{d,2\}\epsilon^{-2}\right\rceil-1\)
calls are necessary. In particular, the mass-normalized formulation admits an \(O(\epsilon^{-2})\) call bound.
The signed-direction truncation is the same packing argument used in Lemma 1 of [Kraft–Fadaei–Bichler](https://pub.dss.in.tum.de/bichler-research/2014_kraft_convex_decomposition.pdf). Here it preserves the normalized count grid directly, and the explicit averaging proof establishes both convergence and polynomial bit complexity for the support-encoded formulation.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the requested construction. The feasibility argument, convergence bound, and bit-complexity analysis are correct under the stated verifier promise. No major or minor mathematical issues were found.
The proof uses exactly the relevant promises: nonemptiness and packing of \(P_\mu\), feasibility and rationality of \(x^\star\), the normalized count grid, and the verifier guarantee for every nonnegative rational query.
The observation that welfare optimality is unnecessary is correct. The argument uses \(x^\star\in P_\mu\), but never uses its optimality.
The definitions \(P=P_\mu\) and \(q=x^\star/\alpha\) are consistent. Since \(\alpha\ge1\) and \(x^\star\in[0,1]^d\), the claimed inclusion \(q\in[0,1]^d\) follows.
The initialization is feasible: nonemptiness supplies a point \(x\in P\), and packing implies \(0\in P\). The zero integer count vector therefore gives \(0\in S_N\).
For any rational signed direction \(r\), the query \(r^+\) is nonnegative and rational, so it lies in the verifier’s promised domain.
The truncation defining \(T(r)\) preserves both required properties:
Thus \(T(r)\in S_N\), with one verifier call.
Every step in the displayed directional inequality is justified. The identity \(r\cdot T(r)=r^+\cdot a\) holds coordinatewise, including coordinates where \(r_i=0\). The verifier guarantee applies to \(r^+\); feasibility of \(x^\star\) justifies comparison with its value; and \(x^\star\ge0\) justifies \(r^+\cdot x^\star\ge r\cdot x^\star\). Consequently, equation (1) is valid.
The attribution to Lemma 1 of [Kraft–Fadaei–Bichler](https://pub.dss.in.tum.de/bichler-research/2014_kraft_convex_decomposition.pdf) is accurate: that lemma uses the same negative-coordinate truncation. The present proof independently checks its validity for normalized count patterns, so it does not assume that binary-coordinate results automatically cover this formulation.
The iteration count is a valid nonnegative integer. In fact, \(d\ge1\) and \(0<\epsilon<1\) imply \(d\epsilon^{-2}>1\), hence \(K\ge1\).
The averaging identity (2) has the correct indexing. At initialization it gives \(y_0=z^0=0\); substituting it into the update gives equal weights on all \(k+2\) patterns at the next iteration.
There are exactly \(K\) verifier calls and \(K+1\) returned patterns. Each pattern is feasible, and the weights \(1/(K+1)\) are positive rational numbers summing to one. Combining repeated patterns preserves the lottery and its expectation.
The sign in equation (3) is correct: \(r_k=q-y_k\) is the negative of \(y_k-q\), so equation (1) makes the cross term nonpositive.
The cube bound (4) is valid because every coordinate difference between \(z^{k+1}\) and \(q\) has absolute value at most one.
Expanding the update produces precisely the recurrence (5). The cross term has a positive coefficient and a nonpositive inner product, so dropping it gives an upper bound.
The induction establishing \(E_k\le d/(k+1)\) is correct:
Finally, \(K+1=\lceil d\epsilon^{-2}\rceil\) implies \(d/(K+1)\le\epsilon^2\). Taking the nonnegative square root establishes exactly the requested Euclidean error guarantee. There is no off-by-one error in the call bound.
The integer-sum representation of \(y_k\) is correct, with numerator at most \(kN\) and denominator \(N(k+1)\). Its encoding length is therefore bounded by the binary length of \(N\) plus a logarithmic term in the iteration count.
Since \(x^\star\) and \(\alpha\) are supplied rational input, the encoding length of \(q\) is \(O(L)\). Exact subtraction and positive-part truncation consequently produce queries of polynomial bit length.
Recovering counts by multiplying a returned coordinate by \(N\) is valid because membership in \(S_N\) promises that the result is an integer. The verifier’s polynomial running-time promise bounds the length of its explicit output.
The number of iterations and returned patterns is \(O(d\epsilon^{-2})\). Thus total running time and output length are polynomial in the requested parameters. Dependence on \(N\) occurs through its binary encoding, while the verifier-call count is independent of \(N\).
The additional bound is also correct. Summing the type constraints gives coordinate sum at most one for every feasible pattern, and at most \(1/\alpha\) for \(q\).
The squared-distance calculation uses nonnegativity correctly, yielding \(\|z-q\|_2^2\le2\). Combining this with the cube bound gives \(D=\min\{d,2\}\). The initial error satisfies \(E_0\le1\le D\), so the same recurrence and induction apply.
Accordingly, the claimed stronger call bound \(\lceil\min\{d,2\}\epsilon^{-2}\rceil-1\) is established.
No repair or additional clarification 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.