Answer: Polynomial-time solvable for every fixed $\gamma\in(0,1]$, in $\operatorname{poly}_\gamma(m,\tau,S,L)$ bit operations, where $S=\tau\sum_jK_j$ is the number of listed marginal values. A polynomial-size rounded-utility flow formulation yields a feasible rational finite-support allocation satisfying all three guarantees.
Theorem 1 — class: algorithmic
Given finite \(T\) and goods \(M\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational per-capita supplies \(q_j\), rational caps \(c_t\), and finitely encoded nonincreasing marginal sequences \(u_{t,j,\ell}\), find a finite-support distribution \(x_{t,B}\ge0\) over integral bundles \(B\in\mathbb{Z}_{\ge0}^{|M|}\) satisfying \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B}b_jx_{t,B}=q_j\), where \(\bar u_t(B)=\min\!\left(c_t,\sum_j\sum_{\ell\le b_j}u_{t,j,\ell}\right)\), such that \(\operatorname{NSW}_\infty(x)=\exp\!\left(\sum_{t,B}x_{t,B}\log\bar u_t(B)\right)\) is within factor \((1+\gamma/4)e^{e^{-1/(1+\gamma)}}\) of optimum and the allocation satisfies continuous EF1 and uncapped approximate Pareto optimality.
A society is given by its support: the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts represented types, not possible types. There are \(m=|M|\ge1\) goods with positive rational per-capita supplies \(q_j\). Each type has a positive rational cap \(c_t\), or the explicit uncapped flag \(c_t=+\infty\), and explicitly listed nonnegative rational marginal values \(u_{t,j,1}\ge\cdots\ge u_{t,j,K_j}\), extended by zero thereafter. Let \(L\) be the total input bit length.
For an integral bundle \(B=(b_j)\in\mathbb Z_{\ge0}^{m}\), define \(u_t(B)=\sum_j\sum_{\ell=1}^{b_j}u_{t,j,\ell}\) and \(\bar u_t(B)=\min\{c_t,u_t(B)\}\). A feasible allocation is a finite-support mass distribution satisfying \(x_{t,B}\ge0\), \(\sum_Bx_{t,B}=\mu_t\), and \(\sum_{t,B}b_jx_{t,B}=q_j\) for every good.
Define \(\operatorname{NSW}_\infty(x)=\exp(\sum_{t,B:x_{t,B}>0}x_{t,B}\log\bar u_t(B))\), with value zero if any positive-mass bundle has zero capped utility; let \(\mathrm{OPT}\) be its supremum over feasible allocations, without fairness constraints.
Fix a constant \(\gamma\in(0,1]\), and write \(r=1+\gamma/4\) and \(A_\gamma=r\exp(\exp(-1/(1+\gamma)))\). Continuous approximate EF1 means that for every \(x_{t,B}>0\) and \(x_{s,C}>0\) with \(C\ne0\), some \(j\) with \(C_j>0\) satisfies \(\bar u_t(B)\ge\bar u_t(C-e_j)/(2+\gamma)\), where \(e_j\) is a unit vector; comparison with an empty bundle is automatic.
When all types are uncapped, require continuous \(r\)-approximate Pareto optimality: there is no finite-support nonnegative reassignment \(z_{t,B,C}\) with \(\sum_Cz_{t,B,C}=x_{t,B}\) and \(\sum_{t,B,C}C_jz_{t,B,C}=q_j\), such that \(u_t(C)\ge r u_t(B)\) whenever \(z_{t,B,C}>0\), with strict inequality on positive mass.
Can a feasible rational finite-support allocation satisfying \(A_\gamma\operatorname{NSW}_\infty(x)\ge\mathrm{OPT}\), continuous approximate EF1, and the stated uncapped Pareto guarantee be computed in polynomial time, or is achieving these joint guarantees NP-hard? State running times in \(m,\tau,L\) and the listed sequence lengths, for each fixed \(\gamma\).
For finite societies, a polynomial-time algorithm achieves this same NSW factor and approximate EF1 guarantee, with approximate Pareto optimality when all valuations are uncapped. [Verified discrete result](https://www.jair.org/index.php/jair/article/download/12911/26798/30539).
No result settling these joint guarantees for this precise mass-allocation problem was identified in the literature search.
The joint guarantees are computable in polynomial time for every fixed $\gamma\in(0,1]$.
The construction below obtains a stronger welfare guarantee: its approximation factor is $\exp(\varepsilon)$, where $\varepsilon$ can be chosen inverse-polynomially small. It optimizes a rational surrogate for logarithmic utility over a polynomial-size flow formulation. Exact optimization of this surrogate supplies the local inequalities needed for fairness and the global inequality needed for the uncapped Pareto guarantee.
Write
$$
f_t(B)=\bar u_t(B),\qquad
K=\sum_{j=1}^m K_j,\qquad
S=\tau K.
$$
Here $S$ is the total number of listed marginal values.
For the fixed constant $\gamma$, choose a fixed positive rational $\kappa\le\gamma$, and set
$$
\varepsilon=\frac{\kappa}{64(K+1)}.
$$
The algorithm uses $\kappa$, so its arithmetic remains rational even if $\gamma$ itself is not rational.
For any finite-support allocation $x$, define
$$
P(x)=\sum_{t,B:f_t(B)>0}x_{t,B},
\qquad
F(x)=\sum_{t,B:f_t(B)>0}x_{t,B}\log f_t(B).
$$
The first objective records positive-utility mass. When $P(x)=1$,
$$
F(x)=\log\operatorname{NSW}_\infty(x).
$$
We will construct rational scores $s_t(B)$ satisfying the following properties:
$$ \log f_t(B)-\varepsilon\le s_t(B)\le\log f_t(B). $$
Define
$$
G(x)=\sum_{t,B}x_{t,B}s_t(B).
$$
We will compute an allocation maximizing $(P,G)$ lexicographically: first maximize $P$, then maximize $G$ while preserving the optimal value of $P$.
For every allocation,
$$
F(x)-\varepsilon P(x)\le G(x)\le F(x).
$$
Let
$$
\mathcal B=\prod_{j=1}^m\{0,\ldots,K_j\},
\qquad
\widehat B_j=\min\{B_j,K_j\}.
$$
Since all later marginal values are zero,
$$
f_t(\widehat B)=f_t(B).
$$
Initially we optimize over distributions on $\mathcal B$, with supply inequalities:
$$
\sum_{B\in\mathcal B}x_{t,B}=\mu_t,
\qquad
\sum_{t,B\in\mathcal B}B_jx_{t,B}\le q_j.
$$
Section 3 restores supply equalities.
If every listed marginal value is zero, every utility is zero. Any rational feasible allocation then satisfies all requested guarantees, including the uncapped Pareto guarantee because strict utility improvement is impossible. Such an allocation is obtained by the supply-completion construction in Section 3, starting from empty bundles. Hence assume some marginal value is positive.
Let
$$
\lambda=\min\{u_{t,j,\ell}:u_{t,j,\ell}>0\},
\qquad
W=\max_t\sum_j\sum_{\ell=1}^{K_j}u_{t,j,\ell}.
$$
Both are positive rationals of polynomial encoding length. Every positive raw bundle utility is at least $\lambda$, and every truncated bundle has raw utility at most $W$.
Set
$$
\delta=\frac{\varepsilon}{2m},
\qquad
\beta=1+\delta.
$$
Use the positive utility grid
$$
\lambda,\lambda\beta,\ldots,\lambda\beta^R,
$$
where $R$ is the largest nonnegative integer satisfying $\lambda\beta^R\le W$.
For $z\in[\lambda,W]$, let $\rho(z)$ be the largest grid value at most $z$, and put $\rho(0)=0$. Then
$$
\frac z\beta\le\rho(z)\le z.
$$
For a truncated bundle $B$, define its rounded accumulated raw utility recursively:
$$
a_{t,0}(B)=0,
$$
$$
a_{t,j}(B)=
\rho\left(
a_{t,j-1}(B)+
\sum_{\ell=1}^{B_j}u_{t,j,\ell}
\right).
$$
Whenever the argument is positive, it is at least $\lambda$: either the previous state is positive, or the added prefix contains a positive marginal value.
Let
$$
U_{t,j}(B)=\sum_{i=1}^j\sum_{\ell=1}^{B_i}u_{t,i,\ell}.
$$
Induction on $j$ gives
$$
\beta^{-j}U_{t,j}(B)\le a_{t,j}(B)\le U_{t,j}(B).
$$
Indeed, assuming the lower bound at stage $j-1$ and writing the next prefix value as $v\ge0$,
$$
a_{t,j}(B)
\ge
\frac{a_{t,j-1}(B)+v}{\beta}
\ge
\beta^{-j}\bigl(U_{t,j-1}(B)+v\bigr).
$$
The upper bound follows from rounding downward.
Consequently,
$$
a_{t,m}(B)=0\quad\Longleftrightarrow\quad u_t(B)=0.
$$
Define the rounded capped utility
$$
\widetilde f_t(B)=
\begin{cases}
\min\{c_t,a_{t,m}(B)\},&c_t<+\infty,\\
a_{t,m}(B),&c_t=+\infty.
\end{cases}
$$
Taking a positive cap preserves the multiplicative bound:
$$
\beta^{-m}f_t(B)\le\widetilde f_t(B)\le f_t(B).
$$
For positive utility,
$$
0\le\log f_t(B)-\log\widetilde f_t(B)
\le m\log\beta
\le m\delta
=\frac{\varepsilon}{2}.
$$
For every type and positive terminal grid state $a$, compute a rational lower approximation $\ell_{t,a}$ satisfying
$$
\log\min\{c_t,a\}-\frac{\varepsilon}{2}
\le\ell_{t,a}
\le\log\min\{c_t,a\},
$$
with the cap omitted when uncapped.
These approximations are computable in polynomial time. To make this explicit, for a positive rational $z$, choose an integer $h$ such that
$$
z=2^h y,\qquad 1\le y<2.
$$
For $v=(y-1)/(y+1)$, we have $0\le v<1/3$, and
$$
\log y=2\sum_{i=0}^{\infty}\frac{v^{2i+1}}{2i+1}.
$$
The same series with $v=1/3$ computes $\log 2$. After $n$ terms, the remainder is at most
$$
3\cdot 3^{-(2n+1)}.
$$
Thus rational upper and lower bounds for
$$
\log z=h\log 2+\log y
$$
of prescribed inverse-polynomial accuracy require only polynomially many bit operations. For negative $h$, the upper bound for $\log 2$ is used when forming a lower bound for $h\log 2$. Rounding the resulting lower bound downward to a sufficiently fine dyadic rational preserves the required error bound.
Order the positive grid states increasingly and replace each $\ell_{t,a}$ by the maximum of the lower approximations up to that state. This makes the scores nondecreasing without invalidating either bound: logarithmic capped utility is itself nondecreasing.
Set
$$
s_t(B)=
\begin{cases}
0,&a_{t,m}(B)=0,\\
\ell_{t,a_{t,m}(B)},&a_{t,m}(B)>0.
\end{cases}
$$
Combining the two approximation errors gives
$$
\log f_t(B)-\varepsilon\le s_t(B)\le\log f_t(B)
$$
whenever $f_t(B)>0$.
The rounded accumulation is coordinatewise nondecreasing, because prefix values and $\rho$ are nondecreasing. Therefore $s_t$ is nondecreasing between positive-utility bundles.
For an unrestricted bundle, define
$$
s_t(B)=s_t(\widehat B).
$$
All the preceding properties continue to hold.
For each type $t$, construct a directed layered graph.
At layer zero, the sole reachable state is $0$. At layer $j$, states are rounded accumulated utilities after considering goods $1,\ldots,j$.
From a reachable state $a$ at layer $j-1$, include an edge for every choice $k\in\{0,\ldots,K_j\}$, leading to
$$
\rho\left(a+\sum_{\ell=1}^k u_{t,j,\ell}\right).
$$
This edge consumes $k$ copies of good $j$. Every reachable transition has argument at most $W$, because rounded accumulated utility never exceeds actual prefix utility.
Join each final state to a sink. Give this terminal edge:
Send flow $\mu_t$ through the graph of type $t$. Impose flow conservation and the $m$ aggregate supply inequalities.
Every truncated bundle determines exactly one path. Conversely, every source-to-sink path determines a truncated bundle, because its edges specify each coordinate. Thus:
The two optimization problems are therefore equivalent.
Solve two rational linear programs: first maximize the primary objective, obtaining $p^*$; then impose primary objective $p^*$ and maximize the secondary objective.
The feasible flow polytope is nonempty, since empty-bundle paths are available. It is bounded, since every edge flow is at most the corresponding type mass. All coefficients are rational. Hence exact rational optimization and polynomial-size rational output follow from the polynomial-time theorem for rational linear programming. [Polynomial-time linear programming](https://lucatrevisan.github.io/cs261/lecture05.pdf)
Decompose the resulting flows into paths. Repeatedly subtract the minimum positive edge flow along a positive-flow path. Each iteration eliminates an edge, so the total number of supported paths is at most the number of graph edges.
Let $y$ be the truncated allocation just computed, and let
$$
a_j=\sum_{t,B}B_jy_{t,B}\le q_j.
$$
Choose a supported pair $(t_0,B^0)$ of rational mass $\alpha>0$. Its required mean increment is
$$
v_j=\frac{q_j-a_j}{\alpha}.
$$
Write
$$
v_j=d_j+\theta_j,\qquad
d_j\in\mathbb Z_{\ge0},\quad 0\le\theta_j<1.
$$
Replace that supported pair by the distribution of bundles
$$
B^0+d+\bigl(\mathbf 1[h<\theta_j]\bigr)_{j=1}^m,
$$
where $h$ is uniform on $[0,1]$. The distribution changes only at the $m$ rational thresholds $\theta_j$, so it has at most $m+1$ bundles with rational masses. Its expected increment is exactly $v$.
The resulting allocation $x$ satisfies every supply equality.
Adding goods cannot decrease the pair $(P,G)$ lexicographically. Positive-utility mass cannot decrease; if it stays unchanged, the scores of positive-utility bundles cannot decrease.
On the other hand, truncating any unrestricted feasible allocation produces a feasible truncated allocation for the supply inequalities, preserving $P$ and $G$. Therefore no unrestricted feasible allocation has a lexicographic objective above the flow optimum. It follows that the completed allocation $x$ is itself a lexicographic maximizer of $(P,G)$ over all feasible finite-support allocations.
This fact will be used throughout the remaining proof.
If $P(x)<1$, lexicographic optimality implies that no feasible allocation has positive utility throughout its support. Every feasible allocation consequently has NSW zero, and
$$
\mathrm{OPT}=0.
$$
Suppose instead that $P(x)=1$. Let $y$ be any feasible allocation with positive NSW. Then $P(y)=1$, and secondary optimality gives
$$
G(x)\ge G(y).
$$
The uniform score bounds imply
$$
F(x)\ge G(x)\ge G(y)\ge F(y)-\varepsilon.
$$
Exponentiating and taking the supremum over feasible $y$ yields
$$
\exp(\varepsilon)\operatorname{NSW}_\infty(x)\ge\mathrm{OPT}.
$$
Moreover,
$$
\log r
=\log(1+\gamma/4)
\ge\frac{\gamma}{4+\gamma}
\ge\frac{\gamma}{5}
>\varepsilon.
$$
The first inequality follows by integrating $1/(1+z)$ over $[0,\gamma/4]$ and bounding the integrand below by its endpoint value.
Thus
$$
\exp(\varepsilon)<r<A_\gamma,
$$
so the requested welfare guarantee holds.
We prove that every supported comparison satisfies the factor $2+\gamma$.
For a type $t$ and bundle $B$, define
$$
a_{t,j}(B)=f_t(B+e_j)-f_t(B).
$$
These gains are nonnegative and nonincreasing under coordinatewise increases of $B$. Explicitly, the gain is the next raw marginal value, limited by the remaining room below the cap. Both quantities can only decrease as coordinates increase.
Consequently, for every integral $D\ge0$,
$$
f_t(D)\le f_t(B+D)
\le f_t(B)+\sum_jD_j a_{t,j}(B).
$$
Next, fix a type $s$ and bundle $C$ with $V=f_s(C)>0$. For $C_j>0$, put
$$
d_j=V-f_s(C-e_j).
$$
Then
$$
\sum_{j:C_j>0}C_jd_j\le V.
$$
To prove this, write
$$
W_C=u_s(C),\qquad w_j=u_{s,j,C_j}.
$$
Diminishing marginals give
$$
\sum_jC_jw_j\le W_C.
$$
If uncapped, or $W_C\le c_s$, then $d_j=w_j$, proving the inequality.
Otherwise let $h=W_C-c_s>0$. Then
$$
d_j=\max\{w_j-h,0\}.
$$
For $J=\{j:d_j>0\}$, the claim is immediate if $J$ is empty. If $J$ is nonempty,
$$
\sum_jC_jd_j
=\sum_{j\in J}C_jw_j-h\sum_{j\in J}C_j
\le W_C-h
=c_s
=V,
$$
because $\sum_{j\in J}C_j\ge1$.
Fix supported pairs $(t,B)$ and $(s,C)$, with $C\ne0$, and write
$$
U=f_t(B),\qquad V=f_s(C).
$$
One copy of good $j$ can be transferred from $C$ to $B$ on equal sufficiently small positive masses. This preserves type masses and supplies. If the supported pairs coincide, use two disjoint portions of that mass.
Whenever the transfer preserves positive-utility mass, secondary optimality says that the sum of the two new scores is at most the sum of the two old scores.
If all four involved utilities are positive, the score errors therefore give
$$
\log\frac{f_t(B+e_j)}{U}
+
\log\frac{f_s(C-e_j)}{V}
\le2\varepsilon.
$$
Set
$$
\eta=\exp(2\varepsilon)-1.
$$
Since $\varepsilon\le1/64$,
$$
\eta\le4\varepsilon.
$$
Indeed, for $0\le z\le1/2$, the power series gives
$$
\exp(z)\le\frac1{1-z},
\qquad
\exp(z)-1\le2z.
$$
We now consider all possibilities for $U$ and $V$.
Suppose $U=0$. If some present good $j$ satisfies $f_t(C-e_j)=0$, the desired fairness inequality holds.
Otherwise every deletion leaves positive utility for $t$. Hence $C$ contains at least two copies, counted with multiplicity, of goods whose first marginal value to $t$ is positive. If there were at most one such copy, deleting it would leave zero utility.
Since $f_t(B)=0$ and the cap is positive, $B$ contains no copy of any such good. Transferring any one of them to $B$ creates positive utility.
If $V=0$, removing a copy leaves the donor at zero utility, so this transfer increases $P$, a contradiction.
If $V>0$, a deletion destroys donor positivity only if it removes the donor’s unique copy of a good with positive first marginal value and there are no other valuable goods in $C$. Among the at least two copies valuable to $t$, choose one other than that unique copy, if it exists. Its transfer preserves donor positivity and again increases $P$, a contradiction.
Thus some deletion gives $f_t(C-e_j)=0$.
Suppose $U>0$ and $V=0$. Removing any copy leaves donor utility zero. The score comparison, with only the recipient having positive utility, gives
$$
\log\frac{U+a_{t,j}(B)}{U}\le\varepsilon.
$$
Thus, for every present good,
$$
\frac{a_{t,j}(B)}{U}\le\exp(\varepsilon)-1\le\eta.
$$
Choose any present good $g$, and put
$$
D_j=\min\{C_j-\mathbf1[j=g],K_j\}.
$$
Truncation preserves utility, so
$$
f_t(C-e_g)=f_t(D)
\le U+\sum_jD_ja_{t,j}(B)
\le U(1+K\eta).
$$
Since $K\eta\le4K\varepsilon\le\kappa/16$, this is smaller than $(2+\gamma)U$.
Suppose $U>0$ and $V>0$. Define
$$
h_j=\frac{d_j}{V}
$$
for present goods. The removal-loss inequality gives
$$
\sum_jC_jh_j\le1.
$$
Whenever $h_j<1$, donor positivity survives deletion. The exchange inequality implies
$$
\left(1+\frac{a_{t,j}(B)}U\right)(1-h_j)
\le1+\eta,
$$
and therefore
$$
\frac{a_{t,j}(B)}U
\le\frac{h_j+\eta}{1-h_j}.
$$
Choose a present good $g$ maximizing $h_j$, and put
$$
n_j=\min\{C_j-\mathbf1[j=g],K_j\}.
$$
For every $j$ with $n_j>0$, we have $h_j\le1/2$. To see this, a value exceeding $1/2$ can occur on at most one copy, because $\sum_jC_jh_j\le1$. That copy must maximize $h_j$ and is precisely the copy removed.
We also have
$$
\sum_{j:n_j>0}\frac{n_jh_j}{1-h_j}\le1.
$$
If $h_g<1$, maximality of $h_g$ gives
$$
\sum_j\frac{n_jh_j}{1-h_j}
\le
\frac{\sum_j(C_j-\mathbf1[j=g])h_j}{1-h_g}
\le
\frac{1-h_g}{1-h_g}
=1.
$$
If $h_g=1$, the loss bound forces $C_g=1$ and all other $h_j=0$, so the sum is zero.
Applying the diminishing-gain inequality to the truncated bundle after deletion,
$$
\frac{f_t(C-e_g)}U
\le
1+\sum_{j:n_j>0}n_j\frac{a_{t,j}(B)}U
$$
$$
\le
1+\sum_j\frac{n_jh_j}{1-h_j}
+\eta\sum_j\frac{n_j}{1-h_j}
\le
2+2K\eta
\le
2+8K\varepsilon
\le
2+\frac{\kappa}{8}
\le
2+\gamma.
$$
All supported comparisons have now been covered. Therefore $x$ satisfies continuous approximate EF1.
The use of $K$ rather than the possibly enormous size of $C$ is essential: truncation removes every utility-irrelevant surplus copy from the gain calculation.
Assume every type is uncapped. Suppose, toward a contradiction, that a reassignment $z$ as in the question satisfies
$$
u_t(C)\ge r\,u_t(B)
$$
on every positive reassigned mass, with strict inequality on positive mass.
Aggregate it into the feasible finite-support allocation
$$
y_{t,C}=\sum_Bz_{t,B,C}.
$$
Positive baseline utility remains positive. If any positive mass moves from zero to positive utility, then
$$
P(y)>P(x),
$$
contradicting primary optimality. Thus zero-utility mass remains at zero, and
$$
P(y)=P(x)=p.
$$
If $p=0$, all baseline and final utilities are zero, contradicting the required strict improvement.
If $p>0$, the multiplicative improvement on positive baseline mass gives
$$
F(y)\ge F(x)+p\log r.
$$
The uniform surrogate bounds then imply
$$
G(y)
\ge F(y)-p\varepsilon
\ge F(x)+p(\log r-\varepsilon)
>F(x)
\ge G(x).
$$
This contradicts secondary optimality because $\varepsilon<\log r$.
Hence the stated continuous $r$-approximate Pareto guarantee holds.
Every positive input marginal lies between $2^{-L}$ and $2^L$, so
$$
\log(W/\lambda)\le2L+\log(K+1).
$$
Since $\log(1+\delta)\ge\delta/2$ for our choice of $\delta$,
$$
R+1
=
O\left(
1+\frac{m(L+\log(K+1))}{\varepsilon}
\right)
=
O_\gamma\left(
m(K+1)(L+\log(K+1)+1)
\right).
$$
Each type graph has at most $O(m(R+1))$ nodes and
$$
O\bigl((R+1)(K+m+1)\bigr)
$$
edges. Thus the two linear programs have
$$
D=
O\bigl(\tau(R+1)(K+m+1)\bigr)
$$
variables and $O(\tau m(R+1)+m)$ constraints.
Grid numbers have bit length
$$
O\left(L+R\log(m/\varepsilon+2)\right).
$$
Transitions, rational logarithmic approximations, and all LP coefficients are computable with polynomial bit length and polynomial work in these parameters. The two exact rational LP optimizations therefore take
$$
\operatorname{poly}_\gamma(m,\tau,K,L)
$$
bit operations, equivalently
$$
\operatorname{poly}_\gamma(m,\tau,S,L).
$$
This bound depends on the explicitly listed sequence lengths, not on the numerical supplies or reciprocals of type masses.
Path decomposition uses at most $D$ paths. Supply completion increases support by at most $m$, giving at most $D+m$ supported type–bundle pairs.
The LP output has polynomial encoding length. Path decomposition preserves polynomial bit length: a common denominator of all rational edge flows has polynomial bit length, and every extracted path mass is an integer multiple of its reciprocal. In supply completion, division by a positive rational path mass, taking integer parts, and computing threshold differences also preserve polynomial bit length. Thus even very large surplus bundle coordinates have polynomial binary encodings.
Consequently, the algorithm outputs a feasible rational finite-support allocation in polynomial time, with all three requested guarantees. No equal-weight expansion into a finite society is required.
⟨structured verdict parsed — rendered above⟩
The construction establishes the requested polynomial-time result in substance. I found no major mathematical gap or false central step. There is one minor notation defect in the final EF1 calculation: some displayed sums include undefined fractions in a boundary case already handled correctly by the preceding argument.
The choices of rational $\kappa$ and $\varepsilon$ are valid for each fixed $\gamma$. No computation with an irrational $\gamma$ is required.
The distinction between $P$ and $F$ correctly handles zero utilities. In particular, $F$ represents logarithmic NSW only when $P=1$; the proof does not incorrectly use that identity when zero-utility mass is present.
Assigning score zero to zero-utility bundles is consistent with lexicographic optimization, even though positive-utility scores can be negative. The construction only requires score monotonicity between positive-utility bundles, which is exactly what its supply-completion argument uses.
Truncation preserves both raw and capped utilities because every marginal after the listed sequence is zero. Truncating an allocation satisfying supply equalities produces an allocation satisfying the truncated supply inequalities.
The rounding operation is applied within its stated domain. A positive transition argument is at least $\lambda$, and every reachable transition argument is at most $W$.
The induction establishing
$$
\beta^{-j}U_{t,j}(B)\le a_{t,j}(B)\le U_{t,j}(B)
$$
is correct, including stages with zero accumulated utility. Positive raw utility is therefore equivalent to a positive terminal state.
Taking the minimum with a positive cap preserves the claimed multiplicative bound. Consequently, the logarithmic rounding error is at most $\varepsilon/2$. Caps smaller than $\lambda$ cause no difficulty, since the grid approximates raw utility before applying the cap.
The logarithm series and its stated remainder bound are valid for the arguments used. The normalization of a positive rational into $2^h y$ correctly accommodates negative $h$, and the explanation specifies the correct bound direction when multiplying an approximation to $\log 2$ by a negative integer.
The required precision is inverse-polynomial, and all terminal rationals have polynomial encoding length. Thus the proposed rational score computation has polynomial bit complexity.
Replacing each lower approximation by the maximum of earlier lower approximations preserves both approximation bounds: the current approximation supplies the lower bound, while monotonicity of capped logarithmic utility supplies the upper bound.
Combining rounding and logarithm approximation gives the claimed uniform score error. The coordinatewise monotonicity argument is also valid.
The layered graph correctly represents truncated bundles. Choices of bundle coordinates determine a unique path, and every path determines those coordinates. Merging paths with the same rounded state does not invalidate later transitions: subsequent rounding depends only on that state and the next coordinate choice.
Aggregate resource consumption and both objectives are linear functions of edge flows. Therefore the stated correspondence between bundle distributions and graph flows preserves all constraints and objectives.
The cited rational-LP result applies: the programs have rational data, the first feasible region is nonempty and bounded, and the second is the nonempty optimal face obtained by imposing the first optimal value. Exact optimization with polynomial-size rational output is supported by the cited source’s discussion of polynomial-time LP algorithms and rational encoding. [Trevisan’s linear-programming lecture](https://lucatrevisan.github.io/cs261/lecture05.pdf)
The path-decomposition argument is valid because the graphs are acyclic. Subtracting the minimum positive edge flow on a path eliminates at least one positive edge and creates none, giving the claimed polynomial support bound.
The threshold construction has the stated expected increments. Its interval lengths are rational, its coordinates are nonnegative integers, and it uses at most $m+1$ replacement bundles. It preserves type masses and restores every supply equality.
Its lexicographic monotonicity argument is correct. Adding goods cannot reduce positive-utility mass. If that mass remains unchanged, monotonicity on positive-utility bundles prevents a decrease in the secondary objective.
Conversely, truncating any unrestricted feasible allocation preserves both objectives and yields a feasible point of the truncated optimization problem. These two comparisons justify the assertion that the completed allocation is a lexicographic maximizer over unrestricted feasible finite-support allocations.
The all-zero valuation case is correctly treated separately. The completion construction remains applicable, fairness is automatic, and strict utility improvement is impossible.
If the maximum positive-utility mass is less than one, no feasible allocation has positive NSW. Thus the conclusion $\mathrm{OPT}=0$ is valid, including the supremum formulation.
If $P(x)=1$, the score bounds and secondary optimality give
$$
F(x)\ge F(y)-\varepsilon
$$
for every feasible allocation $y$ with positive NSW. Exponentiation and taking the supremum are legitimate; the argument does not require attainment of the original NSW optimum.
The comparison of constants is correct:
$$
\varepsilon\le\frac{\gamma}{64(K+1)}
<\frac{\gamma}{5}\le\log r.
$$
Therefore the stronger welfare factor $\exp(\varepsilon)$ implies the requested factor $A_\gamma$.
Both valuation inequalities in Section 5.1 check out. Capped addition gains decrease under coordinatewise increases, and the removal-loss bound correctly handles uncapped bundles, bundles below their cap, and bundles strictly above their cap. Zero-valued surplus copies do not invalidate either inequality.
The exchange operation preserves supplies and type masses. When the two supported pairs coincide, taking two disjoint portions of sufficiently small positive mass is permissible. The score comparison yields the claimed error $2\varepsilon$ when all four utilities are positive, and error $\varepsilon$ when only the recipient contributes to the secondary objective.
The three utility cases are covered correctly:
The numerical estimates also hold:
$$
\eta\le4\varepsilon,\qquad
2K\eta\le8K\varepsilon\le\frac{\kappa}{8}\le\gamma.
$$
Minor issue: the final displayed calculation changes from sums restricted to $n_j>0$ to unrestricted sums containing
$$
\frac{n_jh_j}{1-h_j}
\quad\text{and}\quad
\frac{n_j}{1-h_j}.
$$
In the explicitly handled case $h_g=1$, one has $n_g=0$, so these unrestricted expressions contain $0/0$. Also, $h_j$ was defined only for present goods. The preceding restricted calculation supplies the intended meaning, so this is an expositional defect rather than a missing mathematical argument.
Minimum clarification: retain the restriction $n_j>0$ in every fractional sum in the concluding EF1 calculation.
Aggregating a finite-support reassignment produces a feasible finite-support allocation. Positive baseline utility remains positive under the required multiplicative improvement.
Any movement from zero utility to positive utility would increase $P$, contradicting primary optimality. Otherwise, $P$ remains unchanged. The case $p=0$ correctly rules out the required strict improvement.
For $p>0$, summing the multiplicative improvement over positive baseline mass gives the stated increase in $F$. The uniform score bounds then imply a strict increase in $G$, since $\log r>\varepsilon$. This contradicts secondary optimality and proves exactly the Pareto guarantee requested in the task.
The bounds on the utility range, grid size, graph size, and rational coefficient lengths are polynomial in the stated parameters for fixed $\gamma$. The grid-size estimate also covers $W=\lambda$, when the grid has only one positive state.
The running-time statement
$$
\operatorname{poly}_\gamma(m,\tau,K,L)
$$
addresses the explicitly listed sequence lengths. The alternative statement using $S=\tau K$ is valid because the support is nonempty, so $\tau\ge1$.
The rational-output argument is sound. Path decomposition preserves polynomial encoding length through the common-denominator bound. Supply completion introduces only polynomial-length rational arithmetic and integer coordinates with polynomial binary encodings. Large supplies and small positive type masses therefore do not require expansion into individual agents.
The output resolves all three requested guarantees, subject only to correcting the fractional-sum notation identified above.
⟨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.