Greedy-Based Online Fair Allocation with Adversarial Input: (aaai24-28858)

Given finitely many complete agent valuation/budget types with rational masses, finitely encoded recurring item-value vectors, epsilon, and K, consider N-clone realizations with one indivisible item assigned to one clone per micro-round and item arrival rate proportional to N. Under the greedy ratio rule and a specified population-invariant measurable tie-breaking rule, decide whether every admissible adversarial stream in the N-to-infinity, per-capita-horizon limit has limiting essential-supremum multiplicative envy at most K.

A society is given by its support: an ordered list of \(\tau\) types with positive binary-rational masses \(p_a\), summing to \(1\). The support size \(\tau\) counts listed types, not possible types. Type \(a\) has positive rational budget \(B_a\) and additive valuations \(v_{aj}\) for \(m\geq1\) reusable item categories. All input numbers are binary rationals, with total encoding length \(L\).
Given \(\varepsilon\in(0,1]\) and \(K\geq0\), require \(v_{aj}\in\{0\}\cup[\varepsilon,1]\), every category to be valued positively by some type, and every type to value some category positively.
For each \(N\geq2\) making every \(Np_a\) integral, create \(Np_a\) clones of type \(a\), labelled \((a,c/(Np_a))\) for \(1\leq c\leq Np_a\). Each clone retains its type's budget and valuations. One unit indivisible item arrives per micro-round; per-capita time \(h\) contains \(\lfloor Nh\rfloor\) rounds.
An adversary chooses an infinite category sequence \(s_N\) for each such \(N\), possibly using previous allocations. Admissibility requires every type's monopolistic utility to diverge for each fixed \(N\), and \(\lim_{h\to\infty}\liminf_{N\to\infty}N^{-1}\sum_{t\leq\lfloor Nh\rfloor}v_{a,s_N(t)}=\infty\) for every \(a\).
Initialize clone utilities at zero. Allocate each arriving category \(j\) irrevocably to a clone maximizing \(B_a v_{aj}/U\), then add \(v_{aj}\) to that clone's utility. A positive numerator over zero scores \(+\infty\); a zero numerator scores zero. Break ties by the lexicographically smallest clone label, using the same ordering at every population size.
At time \(h\), let \(A_i\) be clone \(i\)'s bundle and define \(E_{ij}^{N,h}=B_iU_i(A_j)/(B_jU_i(A_i))\), with positive-over-zero equal to \(+\infty\) and zero-over-zero equal to \(1\). Let \(Q_{1-\delta}^{N,h}\) be its \((1-\delta)\)-quantile over uniformly sampled ordered distinct clone pairs.
Define the limiting essential-supremum envy of a stream family by \(\mathcal E=\limsup_{h\to\infty}\lim_{\delta\downarrow0}\limsup_{N\to\infty}Q_{1-\delta}^{N,h}\); population limits run through the integral realizations above.

Is deciding whether \(\mathcal E\leq K\) for every admissible adversarial stream family solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finitely many agents, greedy allocation has asymptotic budget-adjusted multiplicative envy at most \(1+2\log(1/\varepsilon)\) under non-extreme values and divergent monopolistic utilities, with a matching unrestricted worst-case lower bound. [Yang–Liao–Kroer](https://arxiv.org/pdf/2308.09277).
A later finite-agent treatment gives the bound \(1+2\log(1/\varepsilon)+O(n/W_i)\), where \(W_i\) is agent \(i\)'s monopolistic utility; this is a performance guarantee, not a complexity classification of the universal threshold problem. [Yang–Liao–Gao–Kroer](https://arxiv.org/html/2408.02403v1#S7).
No result settling this specific population-limit threshold problem was located.

Result

The decision problem is polynomial-time solvable. In fact, its exact threshold has a finite rational formula.

For each ordered pair of types $a,b$, define
$$ R_{ab}=\left\{\frac{v_{aj}}{v_{bj}}:v_{aj}>0,\ v_{bj}>0\right\}. $$
If $R_{ab}$ is empty, set $C_{ab}=0$. Otherwise, list its distinct elements in decreasing order:
$$ \rho_1>\rho_2>\cdots>\rho_q>0, $$
and set
$$ C_{ab}=1+\sum_{\ell=2}^{q} \left(1-\frac{\rho_\ell}{\rho_{\ell-1}}\right). $$
Define
$$ C_*=\max_{a,b}C_{ab}. $$

I prove that
$$ \sup_{\text{admissible stream families}}\mathcal E=C_*, $$
and that the supremum is attained by an admissible stream family. Consequently, the answer to the universal threshold question is yes exactly when
$$ K\geq C_*. $$

The positive masses and budgets affect the dynamics, but they do not affect this exact worst-case threshold.

1. Two elementary allocation properties

Write $U_i(t)$ for clone $i$’s utility after $t$ rounds, and put
$$ M_a=\max_j v_{aj}\leq 1. $$

Every allocated item goes to a clone that values it positively: some clone has a positive score, whereas all clones assigning value zero have score zero.

Moreover, whenever an item is allocated to a clone of type $a$, that clone has minimum utility among clones of type $a$. Indeed, all those clones have the same budget and valuation for the arriving category, so maximizing their scores is equivalent to minimizing their utilities.

It follows inductively that, at every time,
$$ \max_{i:\,\operatorname{type}(i)=a}U_i - \min_{i:\,\operatorname{type}(i)=a}U_i \leq M_a\leq1. $$
To check the induction, allocating to a minimum-utility clone raises its utility by at most $M_a$; all other utilities remain unchanged.

Both properties hold under the specified tie-breaking rule.

2. A finite-catalogue pairwise upper bound

Fix a finite population, a finite prefix, and distinct clones $i,k$ of types $a,b$. Let $U_i$ denote clone $i$’s final utility in that prefix.

If $R_{ab}$ is empty, then
$$ U_i(A_k)=0, $$
because every item allocated to $k$ has positive value for type $b$ and hence zero value for type $a$.

Suppose instead that $R_{ab}$ is nonempty, and write
$$ r_{ab}=\max R_{ab}=\rho_1. $$
I will prove
$$ U_i(A_k) \leq \frac{B_b}{B_a}C_{ab}U_i+M_b r_{ab}. $$

Set
$$ X=\frac{U_i}{B_a}. $$
Along clone $k$’s allocations, let $y$ be its utility immediately before an allocation, divided by $B_b$. An allocation of category $j$ increases $y$ by
$$ \Delta y=\frac{v_{bj}}{B_b}\leq d_b, \qquad d_b=\frac{M_b}{B_b}. $$
If $v_{aj}>0$, write $\rho=v_{aj}/v_{bj}$. The greedy comparison against clone $i$ gives
$$ \rho y\leq \frac{U_i(t-1)}{B_a}\leq X. $$
This remains valid when a utility is zero: if clone $i$ has zero utility and positive value for the category, clone $k$ can win only if its utility is also zero.

Define the nonincreasing function
$$ f_X(y)= \max\left(\{\,\rho\in R_{ab}:\rho y\leq X\,\}\cup\{0\}\right). $$
For every allocation to $k$, its contribution to $U_i(A_k)/B_b$ is at most
$$ f_X(y)\Delta y. $$
This also covers categories with $v_{aj}=0$.

Let $y_0=0<y_1<\cdots<y_s$ be clone $k$’s successive normalized utilities. Since $f_X$ is nonincreasing and every increment is at most $d_b$,
$$ \begin{aligned} \sum_{\nu=1}^{s}f_X(y_{\nu-1})(y_\nu-y_{\nu-1}) -\int_0^{y_s}f_X(y)\,dy &\leq \sum_{\nu=1}^{s}(y_\nu-y_{\nu-1}) \bigl(f_X(y_{\nu-1})-f_X(y_\nu)\bigr)\\ &\leq d_b\bigl(f_X(0)-f_X(y_s)\bigr)\\ &\leq d_b r_{ab}. \end{aligned} $$

For $X>0$, direct integration gives
$$ \begin{aligned} \int_0^\infty f_X(y)\,dy &= \rho_1\frac{X}{\rho_1} +\sum_{\ell=2}^{q} \rho_\ell\left(\frac{X}{\rho_\ell} -\frac{X}{\rho_{\ell-1}}\right)\\ &=XC_{ab}. \end{aligned} $$
For $X=0$, the integral is zero, so the same identity holds.

Combining these facts proves the claimed inequality. In particular, whenever $U_i>0$,
$$ E_{ik} \leq C_{ab}+ \frac{B_aM_b r_{ab}}{B_bU_i}. $$

Thus $C_{ab}$ is a catalogue-specific asymptotic upper bound, with an error depending on the envious clone’s utility.

3. Admissibility makes the error vanish in the required order of limits

For empty $R_{ab}$, also set $r_{ab}=0$. Define
$$ D_a=\sum_b p_b\frac{B_b}{B_a}C_{ab}, \qquad G_a=\sum_b p_bM_b r_{ab}. $$
Since $R_{aa}=\{1\}$, we have $C_{aa}=1$, and therefore
$$ D_a\geq p_a>0. $$

Let $W_a^{N,h}$ be type $a$’s monopolistic utility through time $h$. For any clone $i$ of type $a$, decomposition over the allocated bundles gives
$$ W_a^{N,h} = U_i+\sum_{k\ne i}U_i(A_k). $$
Applying the preceding pairwise inequality and using the $Np_b$ clones of each type yields
$$ W_a^{N,h} \leq ND_aU_i+NG_a. $$
Here the coefficient of $U_i$ is exactly $ND_a$: the own-bundle coefficient $1$ replaces the omitted same-type coefficient $C_{aa}=1$.

Consequently, every clone of type $a$ satisfies
$$ U_i\geq \frac{W_a^{N,h}/N-G_a}{D_a}. $$

The population admissibility hypothesis now implies
$$ \lim_{h\to\infty}\liminf_{N\to\infty} \min_i U_i^{N,h}=\infty. $$
Indeed, the displayed lower bound applies to every clone, and there are only finitely many types.

Let
$$ A_*=\max_{a,b}\frac{B_aM_b r_{ab}}{B_b}. $$
At times and populations where all utilities are positive, every distinct pair therefore satisfies
$$ E_{ik}^{N,h}\leq C_*+\frac{A_*}{\min_iU_i^{N,h}}. $$
For every positive error tolerance, the preceding utility-divergence statement bounds this error eventually in $N$, for every sufficiently large $h$. The same bound then applies to every quantile, and hence to the specified iterated limits.

Thus, for every admissible family,
$$ \mathcal E\leq C_*. $$

This argument respects the given order of limits; it does not interchange population and time limits.

4. A uniform rounding lemma for homogeneous blocks

To prove attainability, we need a precise description of a block consisting of one repeated category.

Fix category $j$. Its participating clones are those whose types satisfy $v_{cj}>0$. Define their loads by
$$ z_i=\frac{U_i}{B_cv_{cj}}. $$
During this block, greedy allocation always chooses a minimum-load participating clone. Receiving one item increases that clone’s load by $1/B_c$.

For a prescribed level $z\geq0$, the exact number of allocations needed to make every participating load at least $z$ is
$$ T(z)= \sum_{i:\,v_{\operatorname{type}(i),j}>0} \left\lceil \left(B_{\operatorname{type}(i)}z -\frac{U_i}{v_{\operatorname{type}(i),j}}\right)_+ \right\rceil, $$
where $x_+=\max\{x,0\}$.

To justify this identity, while any participating clone is below $z$, a minimum-load clone is below $z$. Once a clone reaches $z$, it receives no further item until all participating clones reach $z$. Thus each clone receives exactly the number of items appearing in its summand.

At that hitting time, a participating clone’s utility differs from
$$ \max\{U_i,B_cv_{cj}z\} $$
by less than or equal to $v_{cj}\leq1$.

The following consequence controls scheduled block lengths uniformly in population size. Put
$$ p_{\min}=\min_c p_c>0. $$
Suppose the initial utilities satisfy, for every clone of type $c$,
$$ |U_i-Ru_c|\leq D, $$
where $R>0$ and $u_c\geq0$. For a fixed $z_0\geq0$, define
$$ u'_c= \begin{cases} \max\{u_c,B_cv_{cj}z_0\},&v_{cj}>0,\\ u_c,&v_{cj}=0, \end{cases} $$
and
$$ S=\sum_{c:\,v_{cj}>0} p_c\frac{u'_c-u_c}{v_{cj}}. $$

Run a block of $n$ items with
$$ |n-NRS|\leq1. $$
Then every resulting clone utility satisfies
$$ |U_i^{\mathrm{end}}-Ru'_c| \leq D+3+\frac{D/\varepsilon+2}{p_{\min}}. $$

Here is the error calculation. Apply the hitting-time identity at level $Rz_0$. Each clone’s required item count differs from its ideal count by at most
$$ D/v_{cj}+1\leq D/\varepsilon+1. $$
Therefore
$$ |T(Rz_0)-NRS|\leq N(D/\varepsilon+1), $$
and
$$ |n-T(Rz_0)|\leq N(D/\varepsilon+1)+1. $$
At the hitting time, the utility error is at most $D+1$.

Between that hitting time and the scheduled endpoint, the average utility change within type $c$ is at most
$$ \frac{|n-T(Rz_0)|}{Np_c}. $$
At both endpoints, utilities within that type have spread at most $1$, so an individual utility change exceeds the average change by at most $2$. These inequalities give the stated bound. Types not participating in the category retain their utilities.

In particular, a fixed finite sequence of such blocks transforms an initial error $D$ into an error at most
$$ A(D+1), $$
for some constant $A$ depending only on the fixed society and the block sequence, uniformly in $N$ and $R$.

5. A finite template attaining a pair value

Choose types $a,b$ with $R_{ab}$ nonempty. Order its ratios as before, and choose categories $j_\ell$ realizing them:
$$ \frac{v_{a,j_\ell}}{v_{b,j_\ell}}=\rho_\ell. $$

Define ideal per-clone utilities recursively, starting from $u_c^0=0$:
$$ u_c^\ell= \begin{cases} \displaystyle \max\left\{u_c^{\ell-1}, \frac{B_cv_{c,j_\ell}}{v_{a,j_\ell}}\right\}, &v_{c,j_\ell}>0,\\ u_c^{\ell-1},&v_{c,j_\ell}=0. \end{cases} $$
Define the per-capita length of phase $\ell$ by
$$ S_\ell= \sum_{c:\,v_{c,j_\ell}>0} p_c\frac{u_c^\ell-u_c^{\ell-1}}{v_{c,j_\ell}}. $$
All these quantities are rational. Furthermore,
$$ u_a^\ell=B_a, \qquad u_b^\ell=\frac{B_b}{\rho_\ell} \qquad (1\leq\ell\leq q). $$
The first identity holds because every phase’s threshold for type $a$ is $B_a$. The second holds because the ratios decrease, so the thresholds for type $b$ increase.

In particular, every $S_\ell$ is positive: type $b$ gains utility in every phase.

At scale $R$, run category $j_\ell$ for approximately $NRS_\ell$ rounds. The rounding lemma applies with threshold
$$ z_0=\frac{1}{v_{a,j_\ell}}. $$
It shows that actual utilities track $Ru_c^\ell$, up to a uniformly bounded multiple of the initial error plus one.

The ideal value that type $a$ assigns to a type $b$ clone’s template bundle is
$$ \begin{aligned} \sum_{\ell=1}^{q} \rho_\ell(u_b^\ell-u_b^{\ell-1}) &= B_b+ \sum_{\ell=2}^{q} \rho_\ell \left(\frac{B_b}{\rho_\ell} -\frac{B_b}{\rho_{\ell-1}}\right)\\ &=B_bC_{ab}. \end{aligned} $$
Its ideal budget-adjusted envy is therefore
$$ \frac{B_a(B_bC_{ab})}{B_bB_a}=C_{ab}. $$

The other types have been included in every phase length $S_\ell$. Their allocations are therefore fully accounted for.

6. Repeating the template gives an admissible attaining family

Choose a pair $a,b$ attaining $C_*$. Such a pair has nonempty $R_{ab}$ because $C_{aa}=1$.

Let
$$ S=\sum_{\ell=1}^{q}S_\ell>0. $$
We construct a stream for every integral population realization using the same per-capita schedule.

Set $h_0=0$. Stage $r$ consists of:

• A cycle through all $m$ categories, with per-capita length $1$ for each category.
• The template from Section 5, at an integer scale $R_r$ chosen so that

$$ R_r\geq r(h_{r-1}+m+1)^2. $$

Thus
$$ h_r=h_{r-1}+m+R_rS. $$
A scheduled block between per-capita times $x$ and $y$ occupies exactly the rounds after $\lfloor Nx\rfloor$ through $\lfloor Ny\rfloor$. Its length differs from $N(y-x)$ by less than $1$, as required by the rounding lemma. Checkpoint $h_r$ therefore coincides exactly with the specified observation time.

Before stage $r$’s template, every clone of type $c$ has utility at most
$$ \frac{h_{r-1}+m}{p_c}+1. $$
Indeed, total allocated utility is at most the number of elapsed rounds, and the within-type utility spread is at most $1$.

Applying the rounding lemma through the fixed template gives, uniformly over all integral populations and all clones of the relevant types,
$$ U_i^{N,h_r} = R_rB_a+O(h_{r-1}+m+1) \qquad (\operatorname{type}(i)=a), $$
and, at the end of template phase $\ell$,
$$ U_k^\ell = R_r\frac{B_b}{\rho_\ell} +O(h_{r-1}+m+1) \qquad (\operatorname{type}(k)=b). $$
The constants here depend only on the society and template.

Every item previously allocated to a type $b$ clone has type $b$ value at least $\varepsilon$. Its previous bundle therefore has type $a$ value at most its previous own utility divided by $\varepsilon$, which is also $O(h_{r-1}+m+1)$.

During phase $\ell$, the type $a$ value of clone $k$’s new items is exactly $\rho_\ell$ times its utility increase. The calculation in Section 5 consequently gives
$$ U_i(A_k) = R_rB_bC_*+O(h_{r-1}+m+1). $$
It follows that, for all distinct pairs of the chosen types,
$$ E_{ik}^{N,h_r} = C_*+ O\left(\frac{h_{r-1}+m+1}{R_r}\right). $$
The error tends to zero with $r$, uniformly in $N$.

These pairs have limiting positive probability under uniform sampling of ordered distinct clones. Their probability tends to $p_ap_b$ if $a\ne b$, and to $p_a^2$ if $a=b$. Therefore, for every sufficiently small fixed $\delta>0$,
$$ \limsup_{N\to\infty}Q_{1-\delta}^{N,h_r} \geq C_*-o_r(1). $$
Taking the remaining limits proves
$$ \mathcal E\geq C_*. $$

Finally, the family is admissible. Each stage’s initial cycle contains exactly $N$ copies of every category. Thus every completed cycle contributes
$$ N\sum_jv_{cj}>0 $$
to type $c$’s monopolistic utility. Infinitely many cycles occur, giving divergence for every fixed $N$. After any prescribed number of cycles, their per-capita contribution is also uniform in $N$, proving the required population-limit divergence.

Combined with Section 3, this establishes
$$ \mathcal E=C_* $$
for the constructed admissible family.

7. Polynomial-time computation

For each pair of types, form at most $m$ positive rational ratios, sort them, remove duplicates, and calculate $C_{ab}$. Then compare their maximum with $K$.

These are polynomially many rational arithmetic operations and comparisons. Each ratio has bit length polynomial in $L$; summing at most $m$ rational terms still produces a rational of bit length polynomial in $m$ and $L$. Thus the entire computation takes polynomial time in $m,\tau,L$.

As a consistency check, for nonempty $R_{ab}$,
$$ \begin{aligned} C_{ab} &\leq 1+\sum_{\ell=2}^{q} \log\frac{\rho_{\ell-1}}{\rho_\ell}\\ &= 1+\log\frac{\rho_1}{\rho_q}\\ &\leq 1+2\log\frac1\varepsilon. \end{aligned} $$
The first inequality uses $1-x\leq-\log x$, and the last uses
$$ \varepsilon\leq\rho_\ell\leq1/\varepsilon. $$
This agrees with the unrestricted logarithmic performance bound in [Yang–Liao–Gao–Kroer, Theorem 7.1](https://arxiv.org/html/2408.02403v1#S7). The finite rational formula above supplies the exact threshold for the fixed reusable catalogue.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output establishes the exact worst-case threshold and a polynomial-time algorithm for the stated problem. I found no major or minor mathematical issues requiring repair.

• Allocation properties — correct.

Every category has a positive valuation somewhere, so its maximum score is positive or infinite. A clone assigning zero value cannot win.

Within a type, all participating clones have the same positive numerator. Consequently, a winning clone has minimum utility within its type, including when utilities are zero. The induction establishing utility spread at most $M_a\leq1$ is valid. The specified tie-breaking rule preserves both properties.

• Finite-prefix pairwise bound — correct, including zero utilities.

When $R_{ab}$ is empty, every item allocated to a type $b$ clone has zero value for type $a$, as claimed.

Otherwise, the greedy comparison gives
$$ \rho y\leq \frac{U_i(t-1)}{B_a}\leq X. $$
For positive utilities this follows by cross-multiplication. If the envious clone has zero utility, its score is infinite, so a winning clone with positive value must also have zero utility. Thus the comparison remains valid in the exceptional case.

The function $f_X$ is nonincreasing. The displayed left-sum error estimate is valid, and its telescoping bound is exactly $d_b r_{ab}$. The integral calculation correctly gives
$$ \int_0^\infty f_X(y)\,dy=XC_{ab}. $$
For $X=0$, the possibly nonzero value at $y=0$ does not affect the integral.

Multiplying by $B_b$ produces the stated additive error $M_b r_{ab}$. Dividing by the positive final utility gives the claimed budget-adjusted envy bound.

• Uniform utility divergence — correct.

Decomposing monopolistic utility over all allocated bundles is valid because every arriving item is allocated exactly once.

In the coefficient of $U_i$, the own-bundle term replaces the omitted same-type term exactly: $C_{aa}=1$ and $B_a/B_a=1$. The additive constant $NG_a$ may overcount the excluded clone’s contribution, which is harmless for an upper bound.

Thus the displayed lower bound
$$ U_i\geq\frac{W_a^{N,h}/N-G_a}{D_a} $$
holds for every clone, with $D_a\geq p_a>0$.

Population admissibility and the finiteness of the type list imply the stated divergence of the minimum utility. In particular, utilities are positive for all sufficiently large populations at sufficiently large times. This handles the zero-denominator conventions before the envy bound is applied.

The error bound is uniform over clone pairs and therefore over quantiles. The argument respects the population, quantile, and time limits in their prescribed order.

• Homogeneous-block hitting time and rounding — correct.

The load definition converts greedy allocation into minimum-load allocation, and one item increases the winning load by exactly $1/B_c$.

The formula for $T(z)$ correctly counts the items needed by each clone. Until every participating clone reaches $z$, a clone already at or above $z$ cannot receive another item. The ceiling formula also handles zero deficits and exact integer deficits correctly.

The scheduled-length estimate follows from the stated ceiling and initial-utility errors. The use of utility spread at most $1$ is justified by Section 1: all applications concern actual greedy trajectories.

Rechecking the final constant, the preceding estimates give an individual endpoint error bounded by
$$ D+3+\frac{D/\varepsilon+1+1/N}{p_c}, $$
which is at most the claimed
$$ D+3+\frac{D/\varepsilon+2}{p_{\min}}. $$
Iterating this bound through a fixed finite template gives the stated population- and scale-uniform error estimate.

• Finite template — correct.

Every selected category is positively valued by both chosen types, so all threshold divisions are defined.

The recursive maxima correctly give $u_a^\ell=B_a$ and $u_b^\ell=B_b/\rho_\ell$. Strictly decreasing ratios make the type $b$ increment positive in every phase, including the initial increment from zero. Hence every $S_\ell$ is positive.

The phase lengths include all participating types. They therefore account for competition from the rest of the society.

The cross-valuation calculation is correct: within phase $\ell$, type $a$ values every item received by a type $b$ clone at exactly $\rho_\ell$ times its own value. The displayed sum consequently equals $B_bC_{ab}$, giving ideal envy $C_{ab}$.

• Repeated construction and accumulated errors — correct.

A maximizing pair with nonempty $R_{ab}$ exists because every diagonal pair has $C_{aa}=1$.

The block-boundary convention introduces an error strictly smaller than one round. A category block of per-capita length $1$ contains exactly $N$ rounds, even when its starting time is nonintegral.

The pre-template utility bound correctly follows from total allocated utility being at most the elapsed number of rounds and the within-type spread bound. It supplies the required initial error for the rounding lemma.

Previous type $b$ bundles have type $a$ value at most their own utility divided by $\varepsilon$, because their allocated items have type $b$ value at least $\varepsilon$ and type $a$ value at most $1$. Thus previous bundles and phase errors have the claimed order.

The scale condition makes their ratio to $R_r$ vanish. The envy estimate is therefore valid for sufficiently large stages, uniformly in population size.

• Quantiles and attainability — correct.

The chosen ordered distinct pairs have limiting probability $p_ap_b$ for different types and $p_a^2$ for identical types. Both are positive.

For sufficiently small fixed $\delta$, this positive fraction of pairs forces the corresponding upper quantile to satisfy the stated lower bound. Uniformity in population size permits the population limit first; the subsequent quantile limit preserves the bound. The unbounded checkpoint sequence then supplies the required time limsup.

The case $a=b$ is covered: the construction uses distinct clones, and their limiting pair probability remains positive.

• Admissibility — correct in both required senses.

Every completed cycle supplies exactly $N$ copies of every category. Each type’s total valuation across categories is positive.

Infinitely many cycles therefore give divergent monopolistic utility for every fixed population. Their per-capita contributions are uniform in population size, establishing the separate population-limit divergence condition as well.

• Complexity and consistency check — correct.

There are polynomially many ratios, sorting operations, and rational arithmetic operations. The ratios and the sums defining $C_{ab}$ have polynomial bit length. Exact comparison with $K$ consequently takes polynomial time in $m,\tau,L$.

The logarithmic consistency inequality has the correct direction and range: every positive shared-category ratio lies in $[\varepsilon,1/\varepsilon]$. The cited finite-agent theorem gives the stated logarithmic bound with an additional finite-horizon error; it is used only as a consistency check, not as a premise for the complexity classification. [Theorem 7.1](https://arxiv.org/html/2408.02403v1#S7).

The proof resolves both directions of the threshold equivalence and establishes attainment by an admissible family. No additional lemma, clarification, or repair is needed.

⟨structured verdict parsed — rendered above⟩