Answer: The continuous minimum envy-ratio problem admits a \(\mathrm{PTAS}\).
Theorem 8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a PTAS for the envy-ratio problem when all players have the same utility for each good. Furthermore, when the number of players is constant, there is an FPTAS.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(r\) good types with utilities \(w_j\in\mathbb{Q}_{>0}\) and per-capita supplies \(q_j\in\mathbb{Q}_{\ge0}\), consider a unit-mass population of identical agents with additive utility \(u(b)=\sum_{j=1}^r w_jb_j\) for integral bundles \(b\in\mathbb{Z}_{\ge0}^r\). Choose masses \(x_b\ge0\) satisfying \(\sum_bx_b=1\) and \(\sum_b b_jx_b=q_j\) for every \(j\), minimizing \(\rho(x)=\max_{x_b>0}u(b)/\min_{x_b>0}u(b)\), with value \(+\infty\) if a used bundle has zero utility.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported agent types, not possible types. Here agents are identical, with total mass \(1\), so \(\tau=1\).
There are \(r\ge1\) good types with utilities \(w_j\in\mathbb Q_{>0}\) and per-capita supplies \(q_j\in\mathbb Q_{\ge0}\), all encoded in binary. Write \(m=r\) and let \(L\) be the total input bit length.
Each agent receives an integral bundle \(b\in\mathbb Z_{\ge0}^r\), with utility \(u(b)=\sum_{j=1}^r w_jb_j\). An allocation consists of real masses \(x_b\ge0\) satisfying \(\sum_bx_b=1\) and \(\sum_b b_jx_b=q_j\) for every \(j\).
Minimize \(\rho(x)=\sup_{x_b>0}u(b)/\inf_{x_b>0}u(b)\), assigning value \(+\infty\) if a used bundle has zero utility or used utilities are unbounded. Let \(\mathrm{OPT}=\inf_x\rho(x)\). Algorithmic allocations are represented by lists of integral bundles and binary rational masses.
Does this continuous minimum envy-ratio problem admit a PTAS: for every fixed rational \(\varepsilon>0\), can a feasible allocation satisfying \(\rho(x)\le(1+\varepsilon)\mathrm{OPT}\) be computed in time polynomial in \(m,\tau,L\), or is achieving this guarantee NP-hard for some fixed \(\varepsilon>0\)?
For finitely many identical agents and explicitly listed indivisible goods with positive additive utilities, a PTAS exists, and an FPTAS exists when the number of agents is fixed. [Lipton–Markakis–Mossel–Saberi](https://procaccia.info/courses/15896s16/docs/paper12a.pdf)
A later result improves the discrete FPTAS for a fixed number of agents. [Kanellopoulos et al.](https://arxiv.org/abs/2503.18241) No result addressing exactly the continuous model above was located in the search.
The problem admits a PTAS. For every fixed rational \(\varepsilon>0\), a feasible allocation with binary encoded rational masses and ratio at most \((1+\varepsilon)\mathrm{OPT}\) can be computed in time polynomial in \(m\) and \(L\).
The proof uses a configuration LP and a rounding procedure that preserves every type’s supply exactly. Finite populations appear only in structural existence proofs; the algorithm never expands the binary supplies into individual goods or agents.
For context, the discrete PTAS is stated in [Lipton–Markakis–Mossel–Saberi, Theorem 3.3](https://procaccia.info/courses/15896s16/docs/paper12a.pdf). The argument below establishes the guarantee directly for the continuous model.
Discard types with \(q_j=0\). Every feasible allocation assigns zero copies of such types to every used bundle, because its corresponding supply equation has nonnegative summands.
Write
\(\displaystyle Q=\sum_j q_j,\qquad \mu=\sum_j w_jq_j.\)
If \(Q<1\), every feasible allocation uses the zero bundle. Indeed,
\(\displaystyle 1-x_0=\sum_{b\ne0}x_b\le\sum_b\Bigl(\sum_jb_j\Bigr)x_b=Q.\)
Thus \(\mathrm{OPT}=+\infty\). A polynomial-size feasible allocation assigns mass \(q_j\) to the unit bundle \(e_j\) and mass \(1-Q\) to the zero bundle. This settles that case.
Henceforth assume \(Q\ge1\), so at least one type remains.
We first show that a finite-ratio allocation exists. Put \(q_j=k_j+f_j\), where \(k_j=\lfloor q_j\rfloor\) and \(0\le f_j<1\), and let \(F_j=\sum_{i\le j}f_i\), with \(F_0=0\). For uniform \(\theta\in[0,1)\), define
\(\displaystyle b_j(\theta)=k_j+\lfloor F_j+\theta\rfloor-\lfloor F_{j-1}+\theta\rfloor.\)
The floor difference is either zero or one, its expectation is \(f_j\), and
\(\displaystyle \sum_jb_j(\theta)=\sum_jk_j+\lfloor F_r+\theta\rfloor\in\{\lfloor Q\rfloor,\lceil Q\rceil\}.\)
Consequently, every bundle is nonempty and \(\mathbb E b_j=q_j\). The finitely many breakpoints of this construction are rational, so it gives a rational allocation.
Let
\(\displaystyle w_{\min}=\min_jw_j,\qquad H=\sum_jw_j\lceil q_j\rceil,\qquad R_0=H/w_{\min}.\)
The allocation just constructed has ratio at most \(R_0\).
Every allocation of ratio at most \(R_0\) has maximum utility at most \(R_0\mu\): its minimum utility is at most its mean \(\mu\). Since all weights are positive, there are only finitely many integral bundles of utility at most \(R_0\mu\). Therefore only finitely many objective values can occur among allocations of ratio at most \(R_0\), each determined by two bundle utilities. The minimum is attained.
For an optimal support, the equations defining its masses form a feasible rational linear system with nonnegativity constraints. It has a rational solution; dropping zero masses cannot worsen the ratio. Thus an optimal allocation exists with finite support and rational masses.
We now describe a preprocessing operation determined entirely by the input.
Maintain remaining agent mass \(t\) and remaining type set \(J\), initially \(t=1\) and \(J\) equal to all retained types. Whenever \(t>0\), define the remaining average
\(\displaystyle T_J=\frac{\sum_{j\in J}w_jq_j}{t}.\)
If the set
\(\displaystyle A=\{j\in J:w_j\ge T_J\}\)
is nonempty, prescribe mass \(q_j\) of singleton bundle \(e_j\) for each \(j\in A\), remove these types, and replace \(t\) by \(t-\sum_{j\in A}q_j\). Repeat until either \(t=0\) or no such type remains.
This operation is well defined. If \(h=\sum_{j\in A}q_j\), then
\(\displaystyle T_Jh\le\sum_{j\in A}w_jq_j\le T_Jt,\)
so \(h\le t\). If \(h=t\), no supply remains outside \(A\). If \(h<t\), the new average is at most \(T_J\), since the removed utility is at least \(T_Jh\). Hence the successive averages are nonincreasing.
At most \(m\) iterations occur.
There exists an optimal allocation in which every peeled good is assigned as its prescribed singleton.
Proof. Take a rational optimal allocation from Section 1. Multiply all masses by a common denominator \(N\). This realizes the allocation as a finite allocation to \(N\) agents with \(Nq_j\) goods of each type.
Consider one preprocessing stage, whose active agents have average utility \(T_J\). Process individual goods of the types in \(A\), marking their recipients inactive once the good has been isolated.
The active average remains at most \(T_J\): each previously isolated good has value at least \(T_J\). Let a designated good of value \(w\ge T_J\) lie in a bundle with additional goods. There is another active agent of utility at most the active average, hence at most \(w\).
Move one additional good of value \(p\) to such an agent. If the recipient’s old utility is \(s\le w\) and the donor’s old utility is \(d\), then
\(\displaystyle s+p\le w+p\le d,\qquad d-p\ge w\ge s.\)
Both new utilities lie between the two old utilities. Thus neither the global minimum decreases nor the global maximum increases.
Repeat until the designated good is alone, then mark its recipient inactive. Its value is at least the current active average, so removing it cannot increase that average. The argument therefore continues through the entire stage and then through subsequent stages.
The resulting allocation has the prescribed singleton masses and ratio no larger than the optimum. It is consequently optimal. \(\square\)
If preprocessing ends with \(t=0\), these singleton masses form an exact optimal allocation, completing that case.
Otherwise, let \(J\) be the remaining types and define
\(\displaystyle T=\frac{\sum_{j\in J}w_jq_j}{t}>0.\)
Every remaining weight satisfies \(w_j<T\). Every peeled singleton has value at least \(T\). Let \(W\) be the largest peeled weight, taking \(W=0\) if no type was peeled.
There is an optimal allocation respecting the prescribed singletons in which every residual bundle has utility in \([T/2,2T]\).
Proof. Again use a finite realization of the rational allocation supplied by Lemma 1. Transfers below involve only residual agents and goods.
Suppose a residual agent has minimum utility \(s<T/2\). Some residual agent has utility \(d\ge T\). Since each residual good has value less than \(T\), this donor has at least two goods. Its smallest good has value \(p\le d/2\). Transfer this good to the minimum agent. Then
\(\displaystyle s+p<s+d/2<T/2+d/2\le d,\)
and
\(\displaystyle d-p\ge d/2\ge T/2>s.\)
Thus both new utilities lie between \(s\) and \(d\). Moreover, the sum of squared utilities decreases by
\(\displaystyle d^2+s^2-(d-p)^2-(s+p)^2=2p(d-s-p)>0.\)
There are finitely many allocations of these fixed finite inventories. Repeating this operation therefore terminates, and termination gives minimum residual utility at least \(T/2\).
Next, if some residual utility is \(d>2T\), select a residual agent of minimum utility \(s\le T\), and transfer any good of value \(p<T\) from the former to the latter. Then
\(\displaystyle d-p>T\ge s,\qquad s+p<2T<d.\)
The minimum remains at least \(T/2\), the global utility interval does not expand, and the same squared-utility calculation is strictly positive because \(d-s-p>0\). Finiteness again implies termination, now with maximum residual utility at most \(2T\).
Neither phase increases the global ratio, so the resulting allocation is optimal. \(\square\)
Fix this optimal allocation, and denote its minimum and maximum residual utilities by \(a\) and \(b\). Then
\(\displaystyle T/2\le a\le T\le b\le2T.\)
Because peeled singletons have value at least \(T\),
\(\displaystyle \mathrm{OPT}=\frac{\max\{W,b\}}{a}.\)
This bounded residual scale is the key to the approximation.
We need two constructive rounding facts.
Let \(v\in\mathbb Q_{\ge0}^d\).
\(\displaystyle \mathbb E B=v,\qquad |p\cdot B-p\cdot v|\le\max_i p_i\)
for every supported vector.
\(\displaystyle \mathbb E B=v,\qquad \sum_{i\in G}B_i=\sum_{i\in G}v_i\)
for every supported vector and every group.
Both procedures take polynomial time in their rational input length. Their support sizes can be bounded by \(2(d+1)\) and \(d+1\), respectively.
Proof. Subtract the coordinatewise floor of \(v\), leaving a vector \(f\in[0,1)^d\).
For the first assertion, maintain a distribution on vectors in \([0,1]^d\), each satisfying \(p\cdot z=p\cdot f\). Initially it consists only of \(f\).
Whenever a supported vector has two fractional coordinates \(i,j\), move in the direction
\(\displaystyle e_i/p_i-e_j/p_j.\)
Move in both directions until reaching the boundary of the cube. The original vector is a rational convex combination of the two endpoints. Replacing it by these endpoints preserves its expectation and weighted sum, and each endpoint has fewer fractional coordinates.
After each generation, reduce support to at most \(d+1\) while preserving its expectation. Explicitly, if there are too many points \(z_s\), find a nonzero rational affine dependence
\(\displaystyle \sum_s\beta_s=0,\qquad \sum_s\beta_sz_s=0.\)
For current probabilities \(\pi_s\), subtract \(\lambda\beta_s\), where
\(\displaystyle \lambda=\min_{\beta_s>0}\pi_s/\beta_s.\)
The probabilities remain nonnegative, preserve their sum and expectation, and at least one becomes zero. Repeat as necessary.
After at most \(d\) generations, each supported vector has at most one fractional coordinate. Round that coordinate to zero or one with probabilities preserving its expectation. This changes the weighted sum by at most its weight. Restoring the floors proves the first assertion, with at most \(2(d+1)\) points.
For the second assertion, make the same pairwise moves with unit weights, choosing both coordinates inside a single group. Each group’s sum stays integer. A group with exactly one fractional coordinate would have a noninteger sum, so whenever any fractional coordinate remains, some group contains a pair available for rounding. The procedure therefore ends with integral vectors, retaining every group sum. Support compression gives at most \(d+1\) points.
For completeness, these operations have polynomial bit complexity. During pairwise rounding, each remaining fractional coordinate’s weighted value is a sum of original weighted fractional coordinates minus weights of coordinates already fixed to one. There are at most \(d\) terms, so all point coordinates have polynomial encoding length. Splitting probabilities therefore have polynomial encoding length. Integer affine dependencies of polynomial encoding length are obtainable by rational Gaussian elimination. Using a common denominator for the probabilities, each split or elimination increases its bit length by a polynomial amount. There are polynomially many such operations. \(\square\)
Choose
\(\displaystyle k=\left\lceil\max\{32,32/\varepsilon\}\right\rceil,\qquad \delta=1/k,\qquad \Delta=T/k.\)
Call a residual type small if \(w_j<T/k\), and large otherwise.
For a large type, round its weight upward to
\(\displaystyle \widehat w_j=\frac{T}{k^2}\left\lceil\frac{k^2w_j}{T}\right\rceil.\)
Then
\(\displaystyle w_j\le\widehat w_j\le(1+\delta)w_j,\)
because \(w_j\ge T/k\). Each rounded weight is \(\nu T/k^2\) for some integer \(\nu\in\{k,\ldots,k^2\}\).
Define the aggregate supplies and small-good utility by
\(\displaystyle Q_\nu=\sum_{\widehat w_j=\nu T/k^2}q_j,\qquad S=\sum_{\text{small }j}w_jq_j.\)
A configuration is an integral vector \(c=(c_\nu)_{\nu=k}^{k^2}\) with rounded utility
\(\displaystyle V_c=\frac{T}{k^2}\sum_{\nu=k}^{k^2}\nu c_\nu\le3T.\)
Every configuration contains at most \(3k\) large goods. Thus the number of configurations depends only on \(k\), and hence only on \(\varepsilon\).
Enumerate all grid pairs \((\ell,h)\) satisfying
\(\displaystyle \ell,h\in\Delta\mathbb Z,\qquad T/3\le\ell\le T,\qquad \ell\le h\le3T.\)
For each pair, retain configurations with \(V_c\le h\) and solve the following rational LP. Here \(z_c\) is the mass of configuration \(c\), and \(y_c\) is the total small-good utility assigned to that mass:
\(\displaystyle z_c,y_c\ge0,\)
\(\displaystyle \sum_cz_c=t,\qquad \sum_cc_\nu z_c=Q_\nu\quad\text{for every }\nu,\)
\(\displaystyle \sum_cy_c=S,\)
\(\displaystyle \max\{0,\ell-V_c\}z_c\le y_c\le(h-V_c)z_c.\)
For each feasible pair, record
\(\displaystyle R(\ell,h)=\frac{\max\{W,h\}}{\ell}.\)
Select a feasible pair minimizing this quantity.
Use the optimal allocation from Lemma 2, and set
\(\displaystyle \ell_*=\Delta\left\lfloor a/\Delta\right\rfloor,\qquad h_*=\Delta\left\lceil(1+\delta)b/\Delta\right\rceil.\)
The bounds on \(a,b\), together with \(\delta\le1/32\), imply that this pair is enumerated:
\(\displaystyle T/3\le\ell_*\le T,\qquad \ell_*\le h_*\le3T.\)
Round each bundle’s large-good weights upward while retaining its actual small-good utility. Its resulting utility lies between its original utility and \((1+\delta)\) times that utility, hence between \(\ell_*\) and \(h_*\). Grouping bundles by their large-good configurations gives a feasible LP solution.
Furthermore,
\(\displaystyle \ell_*\ge a-\delta T\ge(1-2\delta)a,\)
and
\(\displaystyle h_*\le(1+\delta)b+\delta T\le(1+2\delta)b.\)
Therefore the selected pair satisfies
\(\displaystyle R(\ell,h)\le R(\ell_*,h_*)\le\frac{1+2\delta}{1-2\delta}\mathrm{OPT}.\)
Take a rational solution of the selected LP. For each configuration with \(z_c>0\), put
\(\displaystyle s_c=y_c/z_c.\)
The LP guarantees
\(\displaystyle \ell\le V_c+s_c\le h.\)
We construct a distribution of original bundles for this configuration population.
For each original large type \(j\) in rounded class \(\nu\), prescribe the expected number
\(\displaystyle A_j=c_\nu q_j/Q_\nu.\)
If \(Q_\nu=0\), its supply equation forces \(c_\nu=0\) in every configuration of positive mass, so that class can be omitted.
For each class,
\(\displaystyle \sum_{j\text{ in class }\nu}A_j=c_\nu\in\mathbb Z_{\ge0}.\)
Apply Lemma 3(2), grouping coordinates by rounded class. Every resulting integral bundle contains exactly \(c_\nu\) goods of class \(\nu\), while its expected original counts are \(A_j\). Its actual large-good utility therefore lies in
\(\displaystyle [V_c/(1+\delta),V_c].\)
Across all configuration populations, each original large type has precisely its required supply, since
\(\displaystyle \sum_cz_cA_j=\frac{q_j}{Q_\nu}\sum_cz_cc_\nu=q_j.\)
If \(S=0\), there are no supported small types and every \(y_c=0\).
If \(S>0\), prescribe, for each small type,
\(\displaystyle D_j=q_js_c/S.\)
These expectations have weighted utility exactly \(s_c\):
\(\displaystyle \sum_{\text{small }j}w_jD_j=s_c.\)
Apply Lemma 3(1). Every resulting small-good bundle has utility in
\(\displaystyle [s_c-\delta T,s_c+\delta T],\)
and the aggregate supply of every small type is exactly correct:
\(\displaystyle \sum_cz_cD_j=\frac{q_j}{S}\sum_cz_cs_c=\frac{q_j}{S}\sum_cy_c=q_j.\)
For each configuration, take the product of its large-good and small-good distributions and multiply their probabilities by \(z_c\). Finally add the prescribed peeled singletons.
The resulting allocation has total mass one, integral bundles, rational masses, and exactly the original supply of every type.
Every residual bundle’s utility lies between
\(\displaystyle \frac{V_c}{1+\delta}+s_c-\delta T \ge\frac{\ell}{1+\delta}-\delta T\)
and
\(\displaystyle V_c+s_c+\delta T\le h+\delta T.\)
Because \(\ell\ge T/3\),
\(\displaystyle \frac{\ell}{1+\delta}-\delta T \ge\left(\frac1{1+\delta}-3\delta\right)\ell \ge(1-4\delta)\ell>0.\)
Every peeled singleton has value at least \(T\), so this lower bound also holds for the complete allocation.
Also, \(h\ge\ell\ge T/3\), giving
\(\displaystyle h+\delta T\le(1+3\delta)h.\)
Consequently, the output allocation satisfies
\(\displaystyle \rho(x)\le \frac{1+3\delta}{1-4\delta}R(\ell,h) \le \frac{(1+3\delta)(1+2\delta)} {(1-4\delta)(1-2\delta)} \,\mathrm{OPT}.\)
For \(0<\delta\le1/32\), the excess of this factor over one equals
\(\displaystyle \frac{11\delta-2\delta^2}{1-6\delta+8\delta^2} \le\frac{176}{13}\delta<14\delta.\)
Since \(k\ge32/\varepsilon\), we have \(\delta\le\varepsilon/32\). Thus
\(\displaystyle \rho(x)\le(1+14\delta)\mathrm{OPT}\le(1+\varepsilon)\mathrm{OPT}.\)
For fixed \(\varepsilon\), the integer \(k\), the number of configurations, and the number of grid pairs are constants.
Preprocessing takes at most \(m\) iterations. Its quantities can be computed directly from sums of the original rational supplies and utilities, so they have polynomial encoding length.
Each configuration LP is explicitly listed, has rational coefficients of polynomial encoding length, and has bounded variables: \(0\le z_c\le t\) and \(0\le y_c\le3Tt\). Standard polynomial-time rational linear programming therefore decides feasibility and produces a rational solution of polynomial encoding length.
Lemma 3 constructs the original-type distributions in polynomial time. Each configuration contributes at most \(2(m+1)^2\) bundles through the product construction. Thus the final allocation has \(O_\varepsilon(m^2)\) listed bundles, all with polynomial-length integral coordinates and rational masses.
The finite realizations used in Lemmas 1 and 2 establish existence only. None is constructed by the algorithm. Its running time is polynomial in \(m\) and \(L\) for every fixed rational \(\varepsilon>0\), as required with \(\tau=1\).
⟨structured verdict parsed — rendered above⟩
The prover’s PTAS claim is established. I found no major or minor issues requiring repair. The argument handles zero supplies and infinite optimum, proves the structural properties it uses, preserves supplies exactly, and accounts for binary encoding and output size.
This establishes polynomial-time approximation for every fixed positive rational \(\varepsilon\). It does not establish polynomial-time exact optimization.
Correct.
Removing types with zero supply is justified by nonnegativity: every positive-mass bundle must have zero count in those coordinates.
For \(Q<1\), the displayed inequality gives \(x_0\ge1-Q>0\), so every feasible allocation has infinite ratio. The proposed allocation has nonnegative rational masses summing to one and satisfies every supply equation. This includes the case where all supplies vanish.
For \(Q\ge1\), the floor construction is valid:
Every constructed bundle has utility between \(w_{\min}\) and \(H\), establishing the finite bound \(R_0\).
The attainment argument also works. Every feasible allocation has mean utility \(\mu\), by the supply equations and nonnegativity. For an allocation with ratio at most \(R_0\), its minimum used utility is at most \(\mu\), so its maximum used utility is at most \(R_0\mu\). Positivity of all retained weights makes the set of bundles under this bound finite. Consequently, only finitely many ratios can occur in this restricted class, and an attained minimum exists.
The assertion about rational masses is justified: the finite support gives a nonempty rational polyhedron of feasible masses. A rational feasible point exists, and discarding zero masses cannot increase the ratio.
Correct.
At every stage with remaining supply, the average \(T_J\) is positive. The inequality \(T_Jh\le T_Jt\) establishes that the prescribed singleton masses never exceed the available agent mass.
If \(h=t\), equality forces the utility outside \(A\) to vanish. Since retained weights and supplies are positive, no supply remains outside \(A\). If \(h<t\), the displayed comparison correctly shows that the new average cannot increase.
Lemma 1’s finite realization is legitimate. Multiplying rational support masses by a common denominator produces integer agent counts, and the supply equations then imply integer inventories.
The transfer argument checks out:
Each designated good becomes isolated after finitely many transfers. Previously isolated recipients remain inactive, so later transfers preserve their singleton bundles. The final allocation therefore has exactly the prescribed singleton masses without increasing the ratio.
The case \(t=0\) is consequently resolved exactly.
Correct.
Both transfer phases preserve the residual inventory and average.
In the first phase, \(s<T/2\) and \(d\ge T\). Since every residual good has value less than \(T\), the donor has at least two goods, and its smallest good satisfies \(p\le d/2\). The stated inequalities ensure that both resulting utilities lie inside \([s,d]\).
The decrease in squared utilities is correctly computed as \(2p(d-s-p)\), and it is strictly positive because \(d-s-p\ge d/2-s>0\).
In the second phase, \(d>2T\), \(s\le T\), and \(p<T\). Thus \(d-p>T\ge s\) and \(s+p<2T<d\). These inequalities preserve the first phase’s lower bound, prevent expansion of the global utility interval, and again make the squared-utility decrease strictly positive.
There are finitely many assignments of the fixed finite inventory to the fixed finite population. Strict decrease therefore guarantees termination in both phases.
The resulting bounds \(T/2\le a\le T\le b\le2T\) follow from the residual utility interval and its mean. Since every peeled singleton has utility at least \(T\), the expression \(\mathrm{OPT}=\max\{W,b\}/a\) is valid, including when no goods were peeled.
Correct.
For the weighted procedure, the direction \(e_i/p_i-e_j/p_j\) preserves the weighted sum. The two boundary endpoints express the original point as a rational convex combination, preserve its expectation, and each reduce the number of fractional coordinates.
Support compression is valid. A nonzero affine dependence has both positive and negative coefficients. The specified choice of \(\lambda\) preserves nonnegative probabilities, total probability, and expectation, while eliminating at least one point.
After at most \(d\) generations, every supported point has at most one fractional coordinate. Its final unbiased rounding changes weighted utility by at most that coordinate’s weight. The support bound \(2(d+1)\) follows.
For grouped rounding, moves within a group preserve its integer sum. A group cannot have exactly one fractional coordinate, so the procedure cannot stop with a fractional coordinate remaining. Compression preserves the group constraints because every retained point already satisfies them.
The bit-complexity argument is sufficient. Endpoint coordinates have polynomial encoding length; splitting probabilities and integer affine dependencies therefore do as well. There are polynomially many splits and eliminations, and a common probability denominator grows by only a polynomial number of bits per operation. Thus neither support size nor rational encoding length grows exponentially.
Correct.
The upward weight rounding satisfies \(w_j\le\widehat w_j\le(1+\delta)w_j\). The upper bound follows from the additive rounding increment \(T/k^2\) and the large-good threshold \(w_j\ge T/k\).
A configuration with rounded utility at most \(3T\) contains at most \(3k\) large goods. Both the number of classes and the maximum configuration size depend only on \(k\), so the configuration family is constant for fixed \(\varepsilon\).
The LP correctly imposes residual mass, rounded-class supplies, total small-good utility, and the prescribed utility interval.
The comparison pair is enumerated. In particular, \(\ell_*\ge T/2-\delta T>T/3\) and \(h_*\le2(1+\delta)T+\delta T<3T\).
Rounding the optimum’s large-good utilities upward puts every rounded bundle between \(\ell_*\) and \(h_*\). Grouping these bundles supplies a feasible LP solution, including the constraints on small-good utility.
The comparisons \(\ell_*\ge(1-2\delta)a\) and \(h_*\le(1+2\delta)b\) are correct. Accounting for the fixed singleton maximum \(W\) gives the stated bound on the selected value \(R(\ell,h)\).
Correct.
For large goods, the prescribed expectations sum to the integer class count \(c_\nu\). Lemma 3(2) therefore applies. Every resulting bundle has exactly the required rounded-class counts, so its actual large-good utility lies in \([V_c/(1+\delta),V_c]\).
The calculation of each original large type’s aggregate supply is exact. A zero-supply rounded class cannot occur in a positive-mass configuration.
For small goods, the expectations \(D_j\) have weighted utility \(s_c\), and Lemma 3(1) applies with error at most \(\delta T\). The displayed aggregate-supply calculation is again exact.
The \(S=0\) branch is handled correctly: positivity of retained weights and supplies implies that no retained small types exist.
Taking product distributions preserves both sets of expectations. Multiplying by \(z_c\) and adding peeled singletons yields total mass one and every original supply exactly.
The final residual utility bounds follow from these constructions and the LP constraints.
Correct.
The lower bound is positive because \(\delta\le1/32\), and
\(\ell/(1+\delta)-\delta T\ge(1-4\delta)\ell\).
Peeled singleton utilities also satisfy this bound, since they are at least \(T\) and \(\ell\le T\).
The upper bound \(h+\delta T\le(1+3\delta)h\) follows from \(h\ge T/3\). Combining the two bounds gives the claimed multiplicative factor.
The excess-factor computation is correct:
\((11\delta-2\delta^2)/(1-6\delta+8\delta^2)\).
On the stated range, the denominator is at least \(13/16\), yielding the bound \((176/13)\delta<14\delta\).
Finally, \(\delta\le\varepsilon/32\) establishes the requested approximation guarantee.
Correct.
For fixed \(\varepsilon\), configuration enumeration and grid enumeration have constant size. Preprocessing uses at most \(m\) iterations and polynomial-length rational arithmetic.
The rational LP claim applies to an explicitly listed system with polynomial-length coefficients. Its stated variable bounds are valid, and polynomial-time rational linear programming supplies polynomial-length rational solutions.
The rounding inputs are obtained through polynomially many rational operations. Each configuration contributes at most \(2(m+1)^2\) product bundles. Adding at most \(m\) peeled singletons preserves the claimed polynomial output size. Bundle coordinates and masses have polynomial encoding length.
The potentially enormous finite populations occur only in existence proofs; the algorithm does not construct them.
The contextual citation is accurate: [Lipton–Markakis–Mossel–Saberi, Theorem 3.3](https://procaccia.info/courses/15896s16/docs/paper12a.pdf) states the discrete PTAS for identical utilities and the FPTAS for a fixed number of players. The continuous argument does not depend on extending that theorem.
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.