Answer: Polynomial-time solvable in \(\tau\) and \(L\) for every fixed positive integer \(K\).
Proposition 1 — class: hardness
Given a finite supplier type set \(T\), rational type fractions \(\mu_t>0\) summing to \(1\), supplier-to-customer ratio \(\rho>0\), rational scores \(v_t>0\) and outside-option scores \(q_t\geq0\), a fixed cap \(K\), and accuracy \(\epsilon>0\), customer mass is \(1\) and supplier mass of type \(t\) is \(\rho\mu_t\). A menu pattern is \(a\in\mathbb{Z}_{\geq0}^{|T|}\) with \(\sum_t a_t\leq K\); choose shares \(x_a\geq0\) summing to \(1\). Define \(p_t(a)=a_tv_t/(1+\sum_s a_sv_s)\), \(y_t=\sum_a x_ap_t(a)\), and \(G_q(\lambda)=\mathbb{E}[h_q(X)]\) for \(X\sim\mathrm{Poisson}(\lambda)\), where \(h_q(0)=0\) and \(h_q(r)=r/(r+q)\) for \(r\geq1\). Find an \(x\) whose value is within additive \(\epsilon\) of the maximum of \(\rho\sum_t\mu_tG_{q_t}(y_t/(\rho\mu_t))\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) supplier types with positive binary rational fractions \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. Customer mass is \(1\), and supplier mass of type \(t\) is \(\rho\mu_t\).
Input scores satisfy \(v_t>0\), \(q_t\geq0\), with \(\rho>0\) and \(0<\epsilon<1\), all binary rationals. Fix a positive integer cap \(K\) independently of the input. Let \(L\) be the total input bit length, including accuracy; there is no finite customer-count parameter \(m\).
Menus are patterns \(a\in A_K:=\{a\in\mathbb Z_{\geq0}^{\tau}:\sum_ta_t\leq K\}\); entries count distinct suppliers of each type, and the empty menu is allowed. No aggregate exposure constraint is imposed.
A feasible allocation has real shares \(x_a\geq0\), \(\sum_{a\in A_K}x_a=1\). Customer outside-option score is \(1\); define \(p_t(a)=a_tv_t/(1+\sum_sa_sv_s)\) and \(y_t=\sum_ax_ap_t(a)\).
Define \(h_q(0)=0\), \(h_q(r)=r/(r+q)\) for integers \(r\geq1\), and \(G_q(\lambda)=\mathbb E[h_q(X)]\) for \(X\sim\operatorname{Poisson}(\lambda)\).
Set \(F(x)=\rho\sum_t\mu_tG_{q_t}(y_t/(\rho\mu_t))\). The computational problem is to find rational feasible shares with \(F(x)\geq\max_zF(z)-\epsilon\).
For each fixed \(K\), is this additive-accuracy optimization problem solvable in polynomial time in \(\tau\) and \(L\), or is it NP-hard?
The finite-agent sequential assortment problem with unrestricted menus is strongly NP-hard, even with zero supplier outside-option scores, and admits a polynomial-time constant-factor approximation ([source](https://web.stanford.edu/~iashlagi/papers/assortment.pdf)).
No result settling this precise fixed-cap, Poisson, mass-allocation problem was located in the literature search.
For every fixed positive integer \(K\), the stated additive-accuracy optimization problem is solvable in deterministic polynomial time in \(\tau\) and \(L\).
The algorithm returns exactly feasible rational shares. Its dependence on accuracy is polynomial in \(\log(1/\epsilon)\). The proof requires both concavity and a numerical evaluation procedure whose running time remains polynomial when Poisson means are exponentially large.
Fix \(q\geq0\). Define the forward differences
\(d_q(r)=h_q(r+1)-h_q(r)\), for \(r\geq0\).
From the definition of \(h_q\),
\(d_q(0)=1/(1+q)\),
and, for \(r\geq1\),
\(d_q(r)=q/((r+q)(r+1+q))\).
These differences are nonnegative and nonincreasing. Indeed,
\(d_q(1)/d_q(0)=q/(q+2)\leq1\),
and the denominator in the formula for \(d_q(r)\) increases with \(r\). This also covers \(q=0\): then \(d_0(0)=1\) and \(d_0(r)=0\) for \(r\geq1\).
Because \(0\leq h_q(r)\leq1\), the Poisson series and its differentiated series converge uniformly on bounded intervals. Differentiating gives
\(G_q'(\lambda)=\mathbb E[d_q(X)]\),
\(G_q''(\lambda)=\mathbb E[d_q(X+1)-d_q(X)]\),
where \(X\sim\operatorname{Poisson}(\lambda)\). At zero, these identities hold by the corresponding right derivatives.
Consequently,
\(0\leq G_q'(\lambda)\leq1\), and \(G_q''(\lambda)\leq0\).
Thus \(G_q\) is increasing and concave on \([0,\infty)\). Since \(G_q(0)=0\),
\(0\leq G_q(\lambda)\leq\lambda\),
and
\(\lvert G_q(\lambda)-G_q(\lambda')\rvert\leq\lvert\lambda-\lambda'\rvert\).
Write \(c_t=\rho\mu_t>0\). The function \(y\mapsto c_tG_{q_t}(y/c_t)\) is therefore concave and has Lipschitz constant at most one. It follows that \(F\) is concave in the allocation shares.
Moreover, for every feasible allocation,
\(0\leq F(x)\leq\sum_t y_t\leq1\),
because every menu satisfies
\(\sum_t p_t(a)=\dfrac{\sum_ta_tv_t}{1+\sum_ta_tv_t}\leq1\).
These bounds are independent of the sizes of \(\rho\), \(q_t\), and \(v_t\).
Stars and bars gives
\(N:=\lvert A_K\rvert=\binom{\tau+K}{K}\).
For fixed \(K\), this is polynomial in \(\tau\). All menus can be enumerated, and every \(p_t(a)\) can be computed exactly as a rational of polynomial encoding length.
Enumerate the nonempty menus as \(a^1,\ldots,a^d\), where \(d=N-1\geq1\). Eliminate the empty-menu share by writing
\(x_{a^i}=z_i\), and \(x_{\varnothing}=1-\sum_{i=1}^d z_i\).
The feasible domain becomes the full-dimensional simplex
\(D=\{z\in\mathbb R^d:z_i\geq0,\ \sum_i z_i\leq1\}\).
Let \(f(z)=F(x(z))\). Since the empty menu contributes zero, the demand vector is
\(y_t(z)=\sum_{i=1}^d z_i p_t(a^i)\).
For \(z,z'\in D\),
\(\lvert f(z)-f(z')\rvert\leq\sum_t\lvert y_t(z)-y_t(z')\rvert \leq\sum_i\lvert z_i-z_i'\rvert\sum_t p_t(a^i) \leq\lVert z-z'\rVert_1\).
Thus \(f\) is concave, takes values in \([0,1]\), and has a uniform Lipschitz bound.
It remains to establish polynomial-time numerical evaluation and optimization in the binary model.
Lemma. Given binary rational \(q,\lambda\geq0\) and \(0<\delta\leq1/2\), a rational approximation to \(G_q(\lambda)\) with absolute error at most \(\delta\) can be computed in time polynomial in their encoding lengths. The number of arithmetic operations is polynomial in \(\log(1/\delta)\), rather than in \(\lambda\) or \(q\).
The case \(\lambda=0\) is immediate. For \(\lambda>0\), expanding the Poisson expectation gives
\(G_q(\lambda) =\lambda e^{-\lambda}\sum_{k=0}^{\infty}\dfrac{\lambda^k}{k!(k+1+q)} =\lambda\int_0^1 s^q e^{-\lambda(1-s)}\,ds\).
The interchange of sum and integral is justified by nonnegativity. This formula includes \(q=0\).
Set
\(\alpha=q+1+\lambda,\quad a=(q+1)/\alpha,\quad b=\lambda/\alpha\).
Then \(\alpha\geq1\), \(a+b=1\), and \(0\leq a,b\leq1\). Substituting \(s=e^{-u}\), followed by \(z=\alpha u\), yields
\(G_q(\lambda)=b\int_0^\infty g(z)\,dz\),
where
\(g(z)=\exp\bigl(-az-\lambda(1-e^{-z/\alpha})\bigr)\).
Let
\(E(z)=az+\lambda(1-e^{-z/\alpha})\).
We claim that \(E(z)\geq\sqrt z\) for every \(z\geq4\).
There are three cases.
\(E(z)\geq z/2\geq\sqrt z\).
\(E(z)\geq z/2\geq\sqrt z\).
\(E(z)\geq z/(2\lambda)+\lambda/2\geq\sqrt z\),
where the last inequality is the arithmetic–geometric mean inequality.
Therefore, for \(B\geq4\),
\(b\int_B^\infty g(z)\,dz \leq\int_B^\infty e^{-\sqrt z}\,dz =2(\sqrt B+1)e^{-\sqrt B}\).
Choose
\(n=\lceil\log_2(1/\delta)\rceil,\qquad B=16(n+1)^2\).
Here \(n\geq1\). Since \(e>2\) and \(8n+10\leq2^{3n+3}\),
\(2(\sqrt B+1)e^{-\sqrt B}\leq2^{-n-1}\leq\delta/2\).
Thus the integral can be truncated at an integer \(B\) polynomial in \(\log(1/\delta)\), uniformly in \(q\) and \(\lambda\).
Divide \([0,B]\) into unit intervals, with centers \(z_j=j+1/2\).
The function \(g\) is entire. On the complex disk \(\lvert\zeta-z_j\rvert\leq1\), one has \(\operatorname{Re}\zeta\geq-1\), and therefore
\(\log\lvert g(\zeta)\rvert \leq a+\lambda(e^{1/\alpha}-1) \leq a+(e-1)b<3\).
The second inequality follows from \(e^u-1\leq(e-1)u\) for \(0\leq u\leq1\).
Write the Taylor expansion
\(g(z_j+w)=\sum_{k=0}^\infty c_{j,k}w^k\).
Cauchy’s coefficient bound gives \(\lvert c_{j,k}\rvert\leq e^3<21\). On \(\lvert w\rvert\leq1/2\), truncating after degree \(D\) has error at most \(21\,2^{-D}\). Choose
\(D=\lceil\log_2(84B/\delta)\rceil\).
The total integration error from Taylor truncation is then at most \(\delta/4\).
We next show that the coefficients can be approximated efficiently, with certified error.
Put \(H_j=e^{-z_j/\alpha}\). The exponent expansion is
\(g(z_j+w)=c_{j,0}\exp\bigl(\sum_{k=1}^\infty \beta_{j,k}w^k\bigr)\),
where
\(c_{j,0}=e^{-az_j-\lambda(1-H_j)}\),
\(\beta_{j,1}=-a-bH_j\),
and, for \(k\geq2\),
\(\beta_{j,k}=\lambda H_j(-1/\alpha)^k/k!\).
These satisfy
\(0<c_{j,0}\leq1,\quad \lvert\beta_{j,1}\rvert\leq1,\quad \lvert\beta_{j,k}\rvert\leq1/k!\) for \(k\geq2\).
Let
\(\nu=\delta/(400B(D+1))\).
Compute dyadic approximations to \(c_{j,0}\) and each \(\beta_{j,k}\), \(1\leq k\leq D\), with errors at most \(\nu\). From these approximations, compute Taylor coefficients exactly by the rational recurrence
\(\widehat c_{j,k} =\dfrac1k\sum_{\ell=1}^k \ell\,\widehat\beta_{j,\ell}\widehat c_{j,k-\ell}\).
To bound their errors, define
\(P(w)=\sum_{k=1}^D\beta_{j,k}w^k,\qquad \widehat P(w)=\sum_{k=1}^D\widehat\beta_{j,k}w^k\).
On \(\lvert w\rvert\leq1\),
\(\lvert P(w)\rvert<2,\quad \lvert\widehat P(w)\rvert\leq3,\quad \lvert P(w)-\widehat P(w)\rvert\leq D\nu\).
It follows, using the integral formula for the difference of two exponentials, that
\(\lvert c_{j,0}e^{P(w)} -\widehat c_{j,0}e^{\widehat P(w)}\rvert \leq50(D+1)\nu\).
Cauchy’s bound therefore gives this same bound for the difference of each corresponding coefficient. On \(\lvert w\rvert\leq1/2\), summing the coefficient errors gives at most \(100(D+1)\nu\). Across all intervals, the resulting integration error is at most \(\delta/4\).
Each approximate polynomial integrates exactly, since
\(\int_{-1/2}^{1/2}w^k\,dw=0\) for odd \(k\),
and
\(\int_{-1/2}^{1/2}w^k\,dw=1/(2^k(k+1))\) for even \(k\).
Together with the tail bound, the total error is at most \(\delta\).
All exponentials needed above have arguments in \([0,B]\). In particular,
\(0\leq az_j+\lambda(1-H_j)\leq z_j\leq B\).
To control multiplication by a possibly large \(\lambda\), compute \(H_j\) to error at most
\(\nu/(8(1+\lambda))\).
The required precision has encoding length polynomial in the input length and \(\log(1/\delta)\). Form the rational approximation to the exponent of \(c_{j,0}\), clip it to \([0,z_j]\), and evaluate its exponential to sufficiently small error. Clipping cannot increase its error, and \(e^{-u}\) is one-Lipschitz on \([0,\infty)\).
For completeness, \(e^{-r}\), with rational \(0\leq r\leq B\), can be evaluated by its Taylor series using exact rational arithmetic. The degree-\(M\) remainder is at most
\(B^{M+1}/(M+1)!\).
Using \(m!\geq(m/e)^m\), choosing \(M+1\geq6B\) and \(M+1\geq\log_2(1/\theta)\) makes this error at most \(\theta\). Thus the required degree and all intermediate encoding lengths are polynomial.
Finally, choose a common dyadic denominator \(2^P\) for the coefficient inputs. The recurrence produces coefficients whose denominators divide
\(2^{(k+1)P}k!\).
Their numerators also have polynomial encoding length, by the preceding coefficient bounds. Hence the exact rational recurrence and integration have polynomial bit complexity. This proves the lemma.
Given rational \(z\in D\), compute all \(y_t(z)\), \(c_t\), and
\(\lambda_t=y_t(z)/c_t\)
exactly. Their encoding lengths are polynomial in the original input length, the query length, and the number of menus.
For a requested absolute error \(\zeta>0\), apply the lemma to every \(G_{q_t}(\lambda_t)\) with accuracy
\(\sigma=\min\{1/2,\zeta/\rho\}\).
Since \(\sum_t c_t=\rho\), the rational weighted sum \(\widetilde f(z)\) satisfies
\(\lvert\widetilde f(z)-f(z)\rvert \leq\sum_t c_t\sigma =\rho\sigma\leq\zeta\).
Its computation is polynomial in the input and query encoding lengths, including the requested precision.
We use the following standard theorem: for a compact convex body \(C\), supplied with rational bounds
\(B(u_0,r)\subseteq C\subseteq B(0,R)\),
a polynomial-time weak membership oracle yields polynomial-time weak linear optimization. Specifically, for rational \(\delta>0\), it returns a rational point \(\widehat u\) within distance \(\delta\) of \(C\), whose linear objective is within \(\delta\) of the maximum over
\(C_{-\delta}=\{u:B(u,\delta)\subseteq C\}\),
or reports that this inner set is empty. The running time is polynomial in dimension and binary encoding lengths. This is the Yudin–Nemirovskii reduction, as stated in [Grötschel–Lovász–Schrijver, Corollary 4.3.12](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
Apply it to the truncated hypograph
\(C=\{(z,s):z\in D,\ -1\leq s\leq f(z)\}\).
Concavity and continuity of \(f\) imply that \(C\) is compact and convex.
Its geometric bounds are explicit. Let
\(u_0=((1/(2d),\ldots,1/(2d)),-1/2),\qquad r=1/(4d)\).
Every point in \(B(u_0,r)\) has nonnegative \(z_i\), and
\(\sum_i z_i\leq1/2+\sqrt d\,r\leq3/4\).
Its \(s\)-coordinate lies in \([-3/4,-1/4]\), which is contained in \([-1,f(z)]\), because \(f(z)\geq0\). Thus \(B(u_0,r)\subseteq C\).
Also, \(\lVert z\rVert_2\leq1\) and \(\lvert s\rvert\leq1\) on \(C\), so \(C\subseteq B(0,2)\).
A weak membership oracle follows directly from the value oracle. At a rational query \((z,s)\) and tolerance \(\eta>0\):
An accepted point is within vertical distance \(\eta/2\) of \(C\). A rejected point satisfies \(s>f(z)\), so it is outside \(C\), and hence outside \(C_{-\eta}\). This verifies the oracle requirements.
All hypotheses of the weak optimization theorem are therefore satisfied.
Let
\(f^*=\max_{z\in D}f(z)\), and \(\delta=\epsilon/(16(d+1))\).
Then \(\delta<r\). Apply weak optimization to maximize the \(s\)-coordinate, obtaining rational \((\widehat z,\widehat s)\).
First compare the inner optimum with \(f^*\). Let \(u^*=(z^*,f^*)\in C\) be an optimizer, and set
\(\theta=\delta/r,\qquad u_\theta=(1-\theta)u^*+\theta u_0\).
Convexity implies
\(B(u_\theta,\theta r)\subseteq C\):
each point in that ball is a convex combination of \(u^*\) and a point in \(B(u_0,r)\). Thus \(u_\theta\in C_{-\delta}\). Its \(s\)-coordinate is at least
\(f^*-\theta(f^*+1/2)\geq f^*-3\delta/(2r)\).
The weak optimization guarantee gives
\(\widehat s\geq f^*-3\delta/(2r)-\delta\).
Now repair \(\widehat z\) rationally:
\(w_i=\max\{\widehat z_i,0\},\qquad S=\sum_i w_i,\qquad \overline z_i=w_i/\max\{1,S\}\).
Then \(\overline z\in D\) exactly.
Since \((\widehat z,\widehat s)\) is within distance \(\delta\) of \(C\), there exists \((z',s')\in C\) with
\(\lVert\widehat z-z'\rVert_2\leq\delta,\qquad s'\geq\widehat s-\delta\).
Clipping negative coordinates cannot increase their distance from the nonnegative vector \(z'\), so
\(\lVert w-z'\rVert_1\leq\sqrt d\,\delta\).
If \(S>1\), normalization changes \(w\) by \(\ell_1\)-distance \(S-1\), and
\(S-1\leq\lVert w-z'\rVert_1\),
because \(\sum_i z_i'\leq1\). Consequently,
\(\lVert\overline z-z'\rVert_1\leq2\sqrt d\,\delta\leq2d\delta\).
The Lipschitz bound from Section 2 now yields
\(f(\overline z)\geq f(z')-2d\delta \geq\widehat s-(2d+1)\delta\).
Combining the inequalities and substituting \(r=1/(4d)\),
\(f(\overline z)\geq f^*-(8d+2)\delta>f^*-\epsilon\).
Return
\(x_{a^i}=\overline z_i,\qquad x_{\varnothing}=1-\sum_i\overline z_i\).
These shares are rational, nonnegative, and sum to one exactly. Their encoding lengths remain polynomial.
For fixed \(K\), the number of menus is polynomial in \(\tau\). The geometric parameters, requested optimization tolerance, oracle queries, numerical evaluation precision, and output shares all have polynomial encoding length. The weak optimization theorem and the evaluation lemma therefore give a deterministic algorithm running in polynomial time in \(\tau\) and \(L\).
The cited [finite-agent hardness result](https://web.stanford.edu/~iashlagi/papers/assortment.pdf) concerns a different optimization problem. Here the allowed real allocation shares form a convex domain, the Poisson response is concave, and fixed \(K\) permits polynomial enumeration of every menu. No finite customer-count parameter is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes a deterministic polynomial-time algorithm for every fixed positive integer \(K\), with exactly feasible rational output and the required additive guarantee. I found no major or minor mathematical issues requiring correction.
The forward-difference formulas are correct, including the exceptional value at \(r=0\):
\[ d_q(0)=\frac{1}{1+q},\qquad d_q(r)=\frac{q}{(r+q)(r+1+q)}\quad(r\geq1). \]
The comparison \(d_q(1)/d_q(0)=q/(q+2)\) is valid for every \(q\geq0\). The remaining differences decrease because their denominators increase. The case \(q=0\) is explicitly handled correctly.
The boundedness of \(h_q\) justifies differentiating the Poisson series on bounded intervals. Both derivative identities are correct, with right derivatives at zero. They establish concavity and the derivative bound \(0\leq G_q'\leq1\).
The scaling \(c_tG_{q_t}(y/c_t)\), where \(c_t=\rho\mu_t>0\), preserves concavity and has Lipschitz constant at most one. Thus the claimed concavity of \(F\) follows.
The objective bound \(0\leq F(x)\leq1\) follows correctly from \(G_q(\lambda)\leq\lambda\) and the menu probability sums. No bound on the numerical magnitudes of the input scores is needed.
The count \(\lvert A_K\rvert=\binom{\tau+K}{K}\) includes the empty menu and is correct. It is polynomial in \(\tau\) when \(K\) is fixed independently of the input.
Exact rational computation of the menu probabilities has polynomial encoding length. Eliminating the empty-menu share produces precisely the stated simplex \(D\). Since the support is nonempty and \(K\geq1\), \(d\geq1\), so subsequent divisions by \(d\) are valid.
The displayed Lipschitz calculation is correct: nonnegative menu probabilities and their sums bounded by one give
\[ \lvert f(z)-f(z')\rvert\leq\lVert z-z'\rVert_1. \]
The Poisson index shift, integral identity, and interchange by nonnegativity are valid. The substitutions produce the stated representation with \(a+b=1\) and \(\alpha\geq1\). The cases \(\lambda=0\) and \(q=0\) are covered.
The three cases cover all possibilities. Each inequality is valid:
The tail integral equals \(2(\sqrt B+1)e^{-\sqrt B}\). For the selected \(B=16(n+1)^2\), the stated estimates give a tail error at most \(2^{-n-1}\leq\delta/2\). Crucially, this truncation length is independent of the magnitudes of \(q\) and \(\lambda\).
The integrand is entire. The complex-disk estimate is valid: the real part of the inner exponential is bounded by its modulus, giving the stated uniform bound below \(e^3<21\).
Cauchy’s estimate therefore bounds every Taylor coefficient by \(21\). Summing the omitted terms on \(\lvert w\rvert\leq1/2\) gives the stated error \(21\,2^{-D}\). The selected degree makes the total truncation error at most \(\delta/4\).
The exponent coefficients have the correct signs and satisfy the claimed bounds. The rational recurrence correctly computes coefficients of the exponential of the approximate exponent polynomial. For coefficients through degree \(D\), truncating that exponent polynomial at degree \(D\) does not change the exact coefficients being compared.
The perturbation estimates for \(P\), \(\widehat P\), and their exponentials are valid with the supplied constants. Cauchy’s bound and the geometric sum on the half-radius disk give the claimed integrated coefficient error \(\delta/4\).
The monomial integration formulas are correct. The three error contributions sum to at most \(\delta\).
The bound on the exponent of \(c_{j,0}\) is correct. Computing \(H_j\) to the stated precision controls amplification by \(\lambda\), including when \(\lambda\) is exponentially large. Clipping the approximate exponent cannot increase its error.
The exponential Taylor remainder bound is applicable on the stated nonnegative interval. The two lower bounds on \(M+1\) suffice to make the remainder at most \(\theta\), with polynomial degree and intermediate encoding lengths.
The recurrence denominator bound \(2^{(k+1)P}k!\) is valid. The coefficient magnitude bounds also control numerator lengths. Exact rational integration across polynomially many intervals retains polynomial bit complexity.
The evaluation lemma is established as written.
For rational feasible queries, the demand values and Poisson means can be computed exactly with polynomial encoding length.
The weighted error calculation is correct because \(\sum_t c_t=\rho\). The choice \(\sigma=\min\{1/2,\zeta/\rho\}\) ensures error at most \(\zeta\), and its encoding length remains polynomial even for very large or small \(\rho\).
The stated membership-to-optimization reduction matches [Grötschel–Lovász–Schrijver, Corollary 4.3.12](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf). The prover supplies the required rational geometric bounds and a valid weak membership oracle.
The truncated hypograph is compact and convex. The claimed inner ball satisfies every simplex and hypograph constraint, including when \(d=1\). The outer radius \(2\) is valid.
The membership oracle also meets both permitted guarantees:
Queries with invalid simplex coordinates are rejected before the value oracle is called, so evaluation outside its established domain is unnecessary.
The selected tolerance satisfies \(0<\delta<r\). The convex-combination construction correctly supplies a point in \(C_{-\delta}\), ensuring that the inner set is nonempty and bounding its optimum.
The rational clipping and normalization produce a point exactly in \(D\). The distance estimates are valid: clipping cannot increase coordinatewise distance from a nonnegative feasible vector, and normalization changes the vector by precisely \(S-1\) when \(S>1\).
Combining this bound with the Lipschitz estimate and the weak optimization guarantee gives the stated loss \((8d+2)\delta\). Its substitution is strictly less than \(\epsilon\).
The reconstructed empty-menu share is rational and nonnegative, and all shares sum to one exactly. Their encoding lengths remain polynomial.
The proof resolves the assigned fixed-cap, Poisson, mass-allocation problem. It establishes both the necessary numerical oracle and the conversion from weak optimization output to exactly feasible rational shares.
No additional lemma, 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.