Greedy-Based Online Fair Allocation with Adversarial Input:

The strongest positive case is real but narrow: this paper has a credible continuous mirror for its first-order greedy algorithm’s asymptotic envy results. I would lead with Theorem 3.4, proved in this paper, and use Theorem 3.5, also proved here, as its sharpness companion. The paper has no named P/NP/W[1]/FPT theorem; its named results are algorithmic performance guarantees and lower bounds.

The natural regime is a large market with millions of exchangeable agents—say bandwidth users, ad-slot consumers, or subscribers—falling into a small number \(\tau\) of complete valuation/budget types. A type specifies an agent’s entire valuation vector over the item stream and its weight. If \(N\) agents are present but only \(\tau\ll N\) distinct valuation columns occur, the high-multiplicity object is the distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) of agent mass across those types. For example, \(N\) may be in the millions while \(\tau\) is 10–100.

The item sequence remains discrete, sequential, and adversarial. Continuization applies to the agent population, not to time or to the social objective. Normalize the population to total mass one, and let each arriving item have aggregate supply \(\delta=1/N\). A feasible allocation at round \(t\) is a measurable set \(S_t\) of agents of mass \(\delta\); every agent in \(S_t\) receives the whole item. Thus the aggregate action is a mass allocation, but individual allocation remains integral. In the finite-\(N\) model, \(S_t\) is exactly one clone; in the fluid limit it is a measurable mass slice.

If \(a(z)\) is agent \(z\)’s type and \(v_a^t\in\{0\}\cup[\varepsilon,1]\) is that type’s value for item \(t\), then the continuous first-order greedy rule selects a mass-\(\delta\) set maximizing

\[ \frac{v_{a(z)}^t}{U_z(t-1)}, \]

with the usual convention for zero utility and a specified measurable tie-breaking rule. The state is the evolving measure of agents, their cumulative utilities, and their assigned item histories. For agents \(z,z'\), define

\[ \operatorname{env}(z,z') = \frac{\sum_{t:z'\in S_t}v_{a(z)}^t} {\sum_{t:z\in S_t}v_{a(z)}^t}, \]

and take the essential supremum over pairs of agents. The objective is the asymptotic worst-case multiplicative envy over all admissible adversarial streams satisfying the paper’s non-extreme-value and unbounded-utility assumptions.

My lead problem would be:

*Continuous Greedy-Envy Guarantee.* Given a finite type system, rational type masses, \(\varepsilon\), and a threshold \(K\), decide whether every admissible adversarial item stream satisfies

\[ \limsup_{T\to\infty}\operatorname{Env}_T \le K \]

under the continuous first-order greedy rule. A solution is either a universal certificate of the guarantee or an admissible stream and pair of agent states violating it.

This is a faithful mirror of Theorem 3.4, “Upper Bound for Multiplicative Envy,” proved here. The expected answer is Class A in the restricted high-multiplicity regime. The proof already reduces the adversary’s problem to the canonical one-dimensional program

\[ \frac1U\int_0^{U/\varepsilon} \min\left\{\frac{U}{u},\frac1\varepsilon\right\}\,du = 1+2\log\frac1\varepsilon. \]

The continuous population makes that integral the native object rather than the limit of a discrete Riemann sum. The expected universal threshold is therefore

\[ K^\star(\varepsilon)=1+2\log(1/\varepsilon), \]

independent of the number of agents and, in the high-multiplicity regime, independent of the mass scale \(N\).

The sharpness problem is worth keeping as a second anchor:

*Continuous Greedy-Envy Witness.* Given \(K<1+2\log(1/\varepsilon)\), construct an admissible continuous type-mass instance and adversarial item stream for which the fluid greedy allocation produces a pair with asymptotic multiplicative envy exceeding \(K\).

This mirrors Theorem 3.5, “Lower Bound for Multiplicative Envy of the Greedy Algorithm,” proved here. It should also be tractable in the restricted model: the paper’s lower-bound construction can be lifted by replacing repeated clones with measurable mass slices. Together, Theorems 3.4 and 3.5 suggest that the continuous problem has an exact solution, not merely an approximation:

\[ \sup_{\text{admissible streams}} \limsup_{T\to\infty}\operatorname{Env}_T = 1+2\log(1/\varepsilon). \]

The authors should recognize this as their problem rather than a softened substitute. It preserves sequential arrivals, adversarial input, additive utilities, integral allocation at the individual level, the same greedy decision rule, the same non-extreme-value assumption, and the same multiplicative envy objective. What changes is precisely the intended high-multiplicity feature: named agents with identical valuation/budget descriptions become a measurable population of interchangeable clones. The paper itself motivates this setting by saying that real markets contain many similar items and that exponentially varying values are unnatural.

The bridge back to the discrete problem is also concrete. An \(N\)-agent instance induces masses \(\mu_a=N_a/N\), and a continuous allocation set of mass \(1/N\) can be rounded to one clone. Conversely, an empirical distribution of clones gives a continuous instance. Under a positive utility floor, rounding errors vanish with \(N\). Thus the mirror could yield high-multiplicity algorithms and finite-\(N\) approximation guarantees rather than being merely an asymptotic restatement.

The weakest point is that this is not a static finite-type LP in the cleanest ChoCo sense. Agents of one initial type acquire different utility and allocation histories, so the dynamic state is a measure over type, current utility, and bundle history. That state can have many strata even when the exogenous type count \(\tau\) is small. Moreover, the aggregate action resembles divisible allocation, although each individual still receives an all-or-nothing item. If the programme insists that the continuous object must be only a static distribution \(\mu\) with no measure-valued online state, this mirror is vulnerable.

I would therefore not claim that the whole PACE/Nash-welfare contribution has already become a clean Class-A continuous problem. The strongest defensible claim is narrower: the paper’s greedy multiplicative-envy results have a natural high-multiplicity population mirror, and its central adversarial optimization already collapses to exactly the sort of integral problem that continuization is meant to expose.