Answer: Yes. A multiplicative approximation factor \(e^\varepsilon(1+1/\omega)^\omega/(e\,\omega\ln(1+1/\omega))\) is achievable in time polynomial in \(m,\tau,L,1/\varepsilon\), with an exactly feasible finite allocation of polynomial encoding length.
Theorem 3 — class: algorithmic
Type-Smooth-ANW-infinity: given rational masses \(p_a\) of complete agent types, rational supplies \(q_b\) of item types, utilities \(u_{ab}\), weights \(\eta_a\), smoothing parameter \(\omega\), and integral bundle configurations \(k\) in the nonnegative integer lattice, choose configuration masses \(y_{a,k}\) satisfying \(\sum_k y_{a,k} = p_a\) and \(\sum_{a,k} k_b y_{a,k} = q_b\), maximizing \(\exp\left(\left(\sum_{a,k} y_{a,k} \eta_a \ln\left(\sum_b u_{ab} k_b + \omega\right)\right) / \left(\sum_a p_a \eta_a\right)\right)\).
A society is given by its support: a list of \(\tau\geq1\) complete agent types with positive binary-rational masses \(p_a\), where \(\sum_a p_a=1\). Here \(\tau\) is the support size, not the number of possible types. Each type specifies its utility row and weight.
There are \(m\geq1\) item types with positive binary-rational supplies \(q_b\), measured per unit society mass; supplies need not sum to one. Utilities and weights are binary rationals satisfying \(u_{ab}\geq0\), \(\max_b u_{ab}=1\) for every \(a\), and \(\eta_a>0\). The binary-rational smoothing parameter satisfies \(0<\omega\leq1\); \(L\) is the total input bit length.
A configuration is any \(k\in\mathbb Z_{\geq0}^m\), including the empty bundle, with no imposed upper bound. An allocation consists of real masses \(y_{a,k}\geq0\) satisfying \(\sum_k y_{a,k}=p_a\) and \(\sum_{a,k}k_b y_{a,k}=q_b\) for every \(b\). Thus each individual receives an integral bundle, while each type's mass may be split among configurations.
Define \(W(y)=\exp\!\left(\frac{\sum_{a,k}y_{a,k}\eta_a\ln(\omega+\sum_bu_{ab}k_b)}{\sum_a p_a\eta_a}\right)\), and let \(\mathrm{OPT}\) be its supremum over feasible allocations. Algorithmic allocations are represented by finite lists of configurations and binary-rational masses.
Does this problem admit a multiplicative approximation factor \(O\!\left(\frac{e^{\varepsilon}}{\omega\ln(1+1/\omega)}\right)\), for every binary-rational \(0<\varepsilon\leq1\), in time polynomial in \(m,\tau,L,1/\varepsilon,1/\omega\)?
For finite societies with \(n\) agents and \(M\) indivisible items, smooth asymmetric Nash welfare admits the same approximation factor in time \(O(nM^2/(\varepsilon\omega))\). [Kell–Sun](https://arxiv.org/pdf/2109.00081)
For finite societies without smoothing, weighted additive Nash welfare admits an \((e^{1/e}+\delta)\)-approximation for every \(\delta>0\). [Feng–Li](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.63)
No result settling this approximation question for the specified unbounded-configuration mass model was located.
The answer is yes. In fact, there is an algorithm with approximation factor
\( R(\omega,\varepsilon) = e^\varepsilon \frac{(1+1/\omega)^\omega} {e\,\omega\ln(1+1/\omega)} \leq \frac{e^\varepsilon}{\omega\ln(1+1/\omega)}. \)
Its running time and output length are polynomial in \(m,\tau,L,1/\varepsilon\). Thus it satisfies the requested running-time bound.
The proof optimizes a relaxation over mean bundles, then implements each mean bundle by a small distribution over integral bundles. Exact supply preservation follows because the model permits splitting each type’s mass. The logarithmic rounding loss is the same one-item curvature underlying the finite-society guarantee of [Kell–Sun](https://arxiv.org/pdf/2109.00081), but the construction below works directly with the support encoding.
Initially, “binary-rational” is interpreted as a rational represented by binary-encoded numerator and denominator. Section 5 also supplies a conversion for the stricter interpretation in which algorithmic masses must be dyadic.
Define
\( A=\sum_a p_a\eta_a, \qquad c_a=\frac{p_a\eta_a}{A}. \)
Then \(c_a>0\) and \(\sum_a c_a=1\). Write the normalized logarithmic welfare as
\( F(y)=\ln W(y) = \frac1A\sum_{a,k}y_{a,k}\eta_a \ln(\omega+u_a\cdot k). \)
For a feasible allocation, let
\( z_{ab}=\sum_k k_b y_{a,k}, \qquad x_{ab}=\frac{z_{ab}}{p_a}. \)
Here \(z_{ab}\) is the aggregate amount of item type \(b\) assigned to type \(a\), and \(x_a\) is that type’s mean bundle. These quantities satisfy
\( z_{ab}\geq0, \qquad \sum_a z_{ab}=q_b. \)
Conditional on type \(a\), the configuration distribution is \(y_{a,k}/p_a\). Its expected utility is \(u_a\cdot x_a\). This expectation is finite, since \(u_{ab}\leq1\) and all supplies are finite.
Moreover, the logarithm is bounded below by \(\ln\omega\), and its positive part is integrable: for \(s\geq0\),
\( \ln(\omega+s) = \ln\omega+\ln(1+s/\omega) \leq \ln\omega+s/\omega. \)
Thus Jensen’s inequality applies, including to allocations with countably infinite support, and gives
\( F(y) \leq \Phi(z) := \sum_a c_a \ln\!\left( \omega+\frac1{p_a}\sum_b u_{ab}z_{ab} \right). \)
Let \(\Phi^*\) be the maximum of \(\Phi\) subject to the displayed aggregate constraints. Their feasible set is a nonempty compact product of simplices, and \(\Phi\) is continuous because \(\omega>0\). Consequently, the maximum exists and
\( \ln\mathrm{OPT}\leq\Phi^*. \)
This upper bound does not assume that the configuration problem attains its supremum.
We first construct, in polynomial time, a rational feasible \(z\) satisfying
\( \Phi(z)\geq\Phi^*-\varepsilon/2. \)
This step uses a rational piecewise-linear approximation to the logarithm, so no exact transcendental optimization oracle is needed.
Set
\( Q=\sum_b q_b, \qquad p_{\min}=\min_a p_a, \qquad S=\omega+Q/p_{\min}. \)
Every shifted utility in the relaxation lies in \([\omega,S]\). Choose an integer \(H\geq1\) such that
\( S/\omega\leq2^H. \)
Such an \(H\) is computable from rational comparisons and is polynomially bounded in the input bit length. In particular,
\( \ln(S/\omega)\leq H. \)
Put \(h=\varepsilon/(4H)\), and define rational knots
\( s_i=\omega(1+h)^i, \qquad i=0,\ldots,N, \)
where \(N\) is the first index with \(s_N\geq S\). Since \(h\leq1/4\) and \(\ln(1+h)\geq h/2\),
\( N\leq 8H^2/\varepsilon+1. \)
Choose a rational \(\ell\) satisfying
\( \ln\omega-\varepsilon/4 \leq \ell \leq \ln\omega. \)
Define \(g(\omega)=\ell\), with constant slope \(1/s_{i+1}\) on each interval \([s_i,s_{i+1}]\). The slopes decrease, so \(g\) is concave and piecewise linear, with rational coefficients.
For \(s\in[s_i,s_{i+1}]\),
\( \frac1{(1+h)s} \leq g'(s)=\frac1{s_{i+1}} \leq \frac1s. \)
Integrating these inequalities yields, throughout \([\omega,S]\),
\( 0\leq\ln s-g(s) \leq \varepsilon/4+h\ln(S/\omega) \leq \varepsilon/2. \)
Let \(L_i\) be the affine extension of the \(i\)-th segment of \(g\). Decreasing slopes imply that every such extension lies above \(g\), and the extension of the segment containing \(s\) equals \(g(s)\). Hence
\( g(s)=\min_{0\leq i<N}L_i(s) \)
on the relevant interval.
We therefore solve the rational linear program
\( \max \sum_a c_a v_a \)
subject to
\( z_{ab}\geq0,\qquad \sum_a z_{ab}=q_b, \)
and, for every \(a,i\),
\( v_a \leq L_i\!\left( \omega+\frac1{p_a}\sum_b u_{ab}z_{ab} \right). \)
The LP is feasible and has a finite optimum. Because all \(c_a\) are positive, its objective is exactly the maximum of the surrogate objective
\( G(z)= \sum_a c_a g\!\left( \omega+\frac1{p_a}\sum_b u_{ab}z_{ab} \right). \)
The pointwise approximation gives
\( \Phi(z)-\varepsilon/2\leq G(z)\leq\Phi(z). \)
If \(z^*\) maximizes \(\Phi\) and \(\widehat z\) maximizes \(G\), then
\( \Phi(\widehat z) \geq G(\widehat z) \geq G(z^*) \geq \Phi^*-\varepsilon/2. \)
The LP has polynomially many variables and constraints. Each knot is obtained by at most \(N\) rational multiplications, so all coefficients have polynomial bit length. Exact rational linear programming consequently returns a rational optimum of polynomial encoding length in polynomial time; this is the standard rational LP theorem originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319).
For completeness, \(\ell\) is also computable with polynomially many rational operations. Write \(\omega=2^{-r}v\), where \(1\leq v<2\) and \(r\) is polynomially bounded. For \(1\leq v\leq2\),
\( \ln v = 2\sum_{j=0}^{\infty} \frac{t^{2j+1}}{2j+1}, \qquad t=\frac{v-1}{v+1}\leq\frac13. \)
After \(J\) terms, the tail is at most \(3\cdot9^{-J}\). Applying this formula to \(v\) and to \(2\), and combining their rational lower and upper bounds in \(\ln\omega=\ln v-r\ln2\), produces the required lower approximation \(\ell\). Only polynomially many bits are needed.
We next prove the implementation property needed for each type.
Lemma. Let \(x\in\mathbb Q_{\geq0}^m\) and \(u\in\mathbb Q_{\geq0}^m\), with \(u_b\leq1\). There is a polynomial-time construction of a rational distribution over at most \(2(m+1)\) integral configurations \(K\) such that
\( \mathbb E K=x \)
and
\( \mathbb E\ln(\omega+u\cdot K) \geq \ln(\omega+u\cdot x)-\alpha(\omega), \)
where
\( \alpha(\omega) = -\ln\!\left(\omega\ln(1+1/\omega)\right) -1+\omega\ln(1+1/\omega). \)
Every output configuration satisfies \(K_b\leq\lceil x_b\rceil\).
Write \(x=d+f\), where \(d_b=\lfloor x_b\rfloor\) and \(f\in[0,1]^m\). Consider the rational polytope
\( P= \{v\in[0,1]^m:u\cdot v=u\cdot f\}. \)
Every vertex of \(P\) has at most one fractional coordinate. Indeed:
Either situation contradicts extremality.
We now give a constructive decomposition
\( f=\sum_{j=1}^{s}\lambda_jv^{(j)}, \qquad s\leq m+1, \qquad \lambda_j\geq0, \qquad \sum_j\lambda_j=1, \)
into vertices of \(P\).
Start with \(w=f\). Keep every coordinate already equal to zero or one fixed. Obtain a vertex \(v\) in this face by setting fractional zero-utility coordinates to endpoints, then repeatedly moving along a direction \(u_j e_i-u_i e_j\) until another coordinate reaches an endpoint. This terminates with at most one fractional coordinate.
If \(w=v\), stop. Otherwise choose
\( \lambda= \min\left( \left\{\frac{w_i}{v_i}:v_i>w_i\right\} \cup \left\{\frac{1-w_i}{1-v_i}:v_i<w_i\right\} \right). \)
Because \(v\) respects all already fixed coordinates and differs from \(w\), this minimum satisfies \(0<\lambda<1\). Define
\( w'=\frac{w-\lambda v}{1-\lambda}. \)
The choice of \(\lambda\) ensures that \(w'\in[0,1]^m\), preserves \(u\cdot w'=u\cdot f\), and makes at least one additional coordinate integral. The identity
\( w=\lambda v+(1-\lambda)w' \)
therefore peels off a vertex while reducing the number of free coordinates. Repeating gives at most \(m+1\) vertices.
This is a polynomial-time rational construction. To check bit growth, put the utilities over a common denominator, \(u_i=A_i/D\), and write \(u\cdot f=C/E\). Any fractional coordinate of any generated vertex has the form
\( v_j= \frac{DC-E\sum_{i\neq j}A_i v_i}{EA_j}, \qquad v_i\in\{0,1\}\ \text{for }i\neq j. \)
Thus all vertex coordinates have uniformly polynomial bit length. In unnormalized residual coordinates, each peeling step uses linear operations and division by a nonzero \(v_i\) or \(1-v_i\). Each step adds only polynomially many denominator bits, and there are at most \(m\) peeling steps.
For a vertex \(v\), all coordinates are integral except possibly \(v_j=\theta\in(0,1)\). Round this coordinate to one with probability \(\theta\), and to zero with probability \(1-\theta\).
The resulting configuration has expectation \(d+v\). Mixing these two-point distributions with weights \(\lambda_j\) therefore gives \(\mathbb E K=x\), with at most \(2(m+1)\) configurations.
Before this final rounding, every vertex has the same utility:
\( u\cdot(d+v)=u\cdot x. \)
It remains to bound the loss from its single Bernoulli rounding.
For a vertex with fractional coordinate \(\theta\), let \(C\geq\omega\) be the shifted utility when that coordinate is rounded down, and let \(D=u_j\leq1\). The loss is
\( \Delta(C,D,\theta) = \ln(C+\theta D) -(1-\theta)\ln C -\theta\ln(C+D). \)
With \(\rho=D/C\), this becomes
\( \Delta(C,D,\theta) = \ln(1+\theta\rho)-\theta\ln(1+\rho). \)
For fixed \(\theta\in[0,1]\),
\( \frac{\partial\Delta}{\partial\rho} = \frac{\theta(1-\theta)\rho} {(1+\theta\rho)(1+\rho)} \geq0. \)
Since \(D/C\leq1/\omega\),
\( \Delta(C,D,\theta) \leq \ln(\omega+\theta) -(1-\theta)\ln\omega -\theta\ln(\omega+1). \)
Set \(r=\ln(1+1/\omega)\). The expression on the right equals
\( \ln(\omega+\theta)-\ln\omega-\theta r. \)
It is strictly concave in \(\theta\). Its maximizer is
\( \theta^*=\frac1r-\omega. \)
The integral identity \(r=\int_\omega^{\omega+1}dt/t\) gives
\( \frac1{\omega+1}<r<\frac1\omega, \)
so \(0<\theta^*<1\). Substitution yields the maximum
\( \alpha(\omega) = -\ln(\omega r)-1+\omega r. \)
This proves the rounding lemma.
Apply the lemma separately to
\( x_a=\widehat z_a/p_a. \)
If the resulting conditional distribution for type \(a\) assigns probability \(\pi_{a,k}\) to configuration \(k\), output the masses \(y_{a,k}=p_a\pi_{a,k}\). Then
\( \sum_k y_{a,k}=p_a \)
and, for every item type \(b\),
\( \sum_{a,k}k_b y_{a,k} = \sum_a p_a x_{ab} = \sum_a\widehat z_{ab} = q_b. \)
Thus the output is exactly feasible. The lemma and \(\sum_a c_a=1\) give
\( F(y) \geq \Phi(\widehat z)-\alpha(\omega) \geq \Phi^*-\varepsilon/2-\alpha(\omega). \)
Under the ordinary binary encoding of rationals, this already proves a factor \(e^{\varepsilon/2+\alpha(\omega)}\), using at most \(2\tau(m+1)\) configurations.
Allowing an additional logarithmic loss of \(\varepsilon/2\), as in the dyadic conversion below, gives
\( W(y)\geq \mathrm{OPT}\,e^{-\varepsilon-\alpha(\omega)}. \)
Finally,
\( e^{\alpha(\omega)} = \frac{e^{\omega r-1}}{\omega r} = \frac{(1+1/\omega)^\omega} {e\,\omega\ln(1+1/\omega)}. \)
Because \(\omega r<1\), this is at most \(1/(\omega r)\), establishing the stated factor.
If “binary-rational” means dyadic, the inputs \(p_a,q_b\) are dyadic, but intermediate rational LP and rounding computations may produce other denominators. We now convert the output masses to dyadic masses with logarithmic loss at most \(\varepsilon/2\).
Let \(N_0=2(m+1)\). Every configuration produced above satisfies
\( k_b\leq\lceil q_b/p_a\rceil, \)
and therefore
\( \omega+u_a\cdot k \leq B_0:=\omega+Q/p_{\min}+m. \)
Choose an integer \(H'\geq1\), polynomially bounded in the input length, such that \(B_0/\omega\leq2^{H'}\). Consequently, all current configurations satisfy
\( \ln(\omega+u_a\cdot k)\leq\ln\omega+H'. \)
Choose a grid size \(d=2^{-B}\) satisfying
\( d\leq\frac{\varepsilon p_{\min}}{2N_0H'}, \)
with \(B\) also large enough that every input mass and supply is an integer multiple of \(d\). Round each current mass downward to this grid. If \(R_a\) is the removed mass of type \(a\), then
\( 0\leq R_a\leq N_0d. \)
Let \(D_b\) be the leftover supply of item type \(b\). Every \(R_a,D_b\) is dyadic and nonnegative.
If all \(R_a=0\), the retained allocation is already feasible. Otherwise, select a type \(a_0\) with \(R_{a_0}>0\), and choose a power of two \(h_0\leq R_{a_0}\).
Assign empty bundles to residual masses \(R_a\) for \(a\neq a_0\), and to mass \(R_{a_0}-h_0\) of type \(a_0\). On the remaining mass \(h_0\), implement the mean bundle
\( d_b'=D_b/h_0. \)
These coordinates are dyadic. Write \(d_b'=\lfloor d_b'\rfloor+f_b'\), and, for a common uniform parameter \(U\in[0,1]\), use
\( K_b=\lfloor d_b'\rfloor+\mathbf1_{\{U<f_b'\}}. \)
Partitioning \([0,1]\) at the distinct thresholds \(f_b'\) gives at most \(m+1\) configurations. All interval lengths, and hence all configuration masses, are dyadic. Also,
\( h_0\mathbb E K_b=D_b. \)
This repairs every supply equality and every type-mass equality exactly.
All replacement configurations have shifted utility at least \(\omega\). Compared with the original allocation, the logarithmic loss is therefore at most
\( \frac{H'}A\sum_a\eta_a R_a = H'\sum_a c_a\frac{R_a}{p_a} \leq H'\frac{N_0d}{p_{\min}} \leq \varepsilon/2. \)
The required \(B\) is polynomially bounded. We may choose \(h_0\geq2^{-B}\), so even the repair configurations have polynomial bit length. The conversion adds at most \(\tau+m+1\) configurations.
The construction preserves the stated individual-level objective: it evaluates logarithmic welfare on integral bundles, and uses mean utilities only to obtain an upper bound and guide rounding.
The algorithm outputs an exactly feasible finite allocation with polynomial encoding length and satisfies
\( W(y)\geq \frac{\mathrm{OPT}} {e^\varepsilon(1+1/\omega)^\omega/ \bigl(e\,\omega\ln(1+1/\omega)\bigr)}. \)
All steps run in time polynomial in \(m,\tau,L,1/\varepsilon\), which is stronger than the requested dependence on \(1/\omega\). The argument covers the unbounded-configuration model and its supremum benchmark directly.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested approximation guarantee, including exact feasibility and polynomial output length. I found no major or minor mathematical issues. It proves a polynomial-time approximation result; it does not establish polynomial-time exact optimization.
The normalization \(A=\sum_a p_a\eta_a\) is positive, and the coefficients \(c_a=p_a\eta_a/A\) are positive and sum to one.
For every feasible allocation, each aggregate quantity \(z_{ab}\) is finite: it is nonnegative and bounded by the corresponding total supply \(q_b\). Thus the conditional mean bundle \(x_a=z_a/p_a\) is well-defined.
The application of Jensen’s inequality is justified even for countably supported allocations. The logarithm is bounded below by \(\ln\omega\), and the displayed bound controls its positive part by an integrable function of utility. Consequently, the expected logarithm exists and is finite.
The relaxation’s feasible set is a nonempty compact product of simplices. Its objective is continuous because every logarithm has argument at least \(\omega>0\). Therefore its maximum exists, and the conclusion \(\ln\mathrm{OPT}\leq\Phi^*\) is valid. Attainment of the original supremum is unnecessary.
Finding: This section supplies a valid upper bound for the specified configuration model.
The interval \([\omega,S]\) contains every shifted mean utility: \(u_{ab}\leq1\), \(z_{ab}\leq q_b\), and \(p_a\geq p_{\min}>0\).
The knot-count estimate is correct. From \(s_N\geq S\), \(\ln(S/\omega)\leq H\), and \(\ln(1+h)\geq h/2\), the stated bound \(N\leq8H^2/\varepsilon+1\) follows.
The derivative comparison is also correct. On a segment, \(s_i\leq s\leq s_{i+1}=(1+h)s_i\), so
\[
\frac{1}{(1+h)s}\leq\frac{1}{s_{i+1}}\leq\frac1s.
\]
Together with the initial lower approximation \(\ell\), this gives the claimed uniform error \(0\leq\ln s-g(s)\leq\varepsilon/2\).
Because the segment slopes decrease, the affine segment extensions describe the concave function through their pointwise minimum. The LP therefore represents the surrogate objective exactly. Positivity of every \(c_a\) ensures that the variables \(v_a\) reach their allowed upper values at an optimum.
The optimization comparison establishing
\[
\Phi(\widehat z)\geq\Phi^*-\varepsilon/2
\]
uses the inequalities in the correct directions.
The rational LP theorem invoked here applies: the LP has rational coefficients, polynomial encoding length, a nonempty feasible set, and a finite attained optimum. The cited polynomial-time linear-programming result is an appropriate foundation. [Khachiyan, *A polynomial algorithm in linear programming*](https://www.mathnet.ru/eng/dan42319).
The logarithm approximation is computationally adequate. The series has geometric convergence because \(t\leq1/3\); its stated tail bound is valid. Combining lower and upper bounds accounts correctly for the subtraction in \(\ln\omega=\ln v-r\ln2\). Polynomially many terms and polynomial-size rational arithmetic suffice.
Finding: The relaxation can be approximated to the stated additive accuracy with the claimed bit complexity.
The vertex argument is valid:
After eliminating these possibilities, the constructed point is a vertex: all coordinates are fixed at endpoints except possibly one coordinate with positive utility, which the equality constraint fixes.
The peeling construction is correct. Coordinates on which \(v\) differs from \(w\) are fractional in \(w\), since already integral coordinates remain fixed. Thus the displayed ratios are positive and less than one, giving \(0<\lambda<1\).
The formula for \(w'\) preserves the utility equality and the box constraints. At least one coordinate reaches an endpoint, and previously fixed coordinates remain fixed. Hence the procedure terminates and yields at most \(m+1\) vertices.
The bit-complexity justification is sufficient. The displayed formula bounds every vertex coordinate’s encoding length independently of the sequence of moves. In unnormalized residual coordinates, subsequent divisions use these bounded-size coordinates or their complements. There are only polynomially many peeling steps.
The final Bernoulli rounding preserves the expectation of each coordinate. Mixing the vertex distributions therefore gives \(\mathbb E K=x\). The support bound \(2(m+1)\) is correct.
The coordinate bound \(K_b\leq\lceil x_b\rceil\) also holds. In particular, if \(x_b\) is integral, then \(f_b=0\), and that coordinate stays fixed throughout the construction.
The argument covers zero utilities, integral mean bundles, and vertices without a fractional coordinate.
Finding: The rounding construction is valid, finite, and polynomial-time.
The expression for the Bernoulli rounding loss is correct. Differentiating with respect to \(\rho\) gives exactly
\[
\frac{\theta(1-\theta)\rho}
{(1+\theta\rho)(1+\rho)}\geq0.
\]
Since \(C\geq\omega\) and \(D\leq1\), substituting the upper bound \(\rho\leq1/\omega\) is justified.
The maximization over \(\theta\) is correct. For \(r=\ln(1+1/\omega)\), the strict integral bounds
\[
\frac1{\omega+1}<r<\frac1\omega
\]
place \(\theta^*=1/r-\omega\) strictly inside \((0,1)\). Substitution gives the claimed value
\[
\alpha(\omega)=-\ln(\omega r)-1+\omega r.
\]
Applying the lemma independently to each type preserves every type mass and every supply exactly. The normalization \(\sum_a c_a=1\) correctly makes the aggregate rounding loss at most \(\alpha(\omega)\), irrespective of the weight magnitudes.
Combining relaxation error and rounding loss gives the stated welfare comparison against the supremum benchmark. The exponentiation and simplification of the factor are correct:
\[
e^{\alpha(\omega)}
=\frac{(1+1/\omega)^\omega}
{e\,\omega\ln(1+1/\omega)}.
\]
The inequality \(\omega r<1\) establishes the advertised upper bound.
Finding: The constants and parameter ranges in the approximation guarantee check out.
The conversion handles the stricter interpretation of binary rationals.
Rounding masses downward removes nonnegative amounts of both society mass and supplies. Because the original inputs and retained masses are multiples of the chosen dyadic grid, every residual mass \(R_a\) and residual supply \(D_b\) is dyadic.
When some residual mass is positive, a power of two \(h_0\) can be chosen with \(2^{-B}\leq h_0\leq R_{a_0}\). Division by \(h_0\) preserves dyadic rationality.
The common-threshold construction gives at most \(m+1\) configurations, dyadic interval lengths, and the required coordinate expectations. Consequently, the repair restores all equalities exactly.
The welfare-loss estimate is valid. Every removed configuration has logarithm at most \(\ln\omega+H'\), while every replacement configuration has logarithm at least \(\ln\omega\). The displayed bound therefore accounts for all removed weighted mass, including potentially large weights.
The chosen grid ensures this additional loss is at most \(\varepsilon/2\). The lower bound on \(h_0\) ensures that repair bundle sizes have polynomial encoding length, even if their numerical values are large.
Finding: Exact dyadic feasibility and the remaining approximation budget are both established.
The algorithm operates on the support representation without enumerating individuals or expanding supplies into individual items. Its configuration counts and rational encoding lengths are polynomial in the stated parameters. The proof accounts for empty bundles, unbounded configuration sizes, zero utilities, arbitrary positive weights, and the supremum benchmark.
No repair or additional clarification is needed to verify the approximation claim. The result should be distinguished from a classification of exact optimization complexity, which this output does not establish.
⟨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.