Universal and Tight Online Algorithms for Generalized-Mean Welfare

The strongest honest case is for a population-continuation of the paper’s online welfare problem. The paper has no NP-hardness or other standard complexity-class theorem, so I cannot offer a conventional hardness anchor. Its best computational anchor is instead an online competitive lower bound.

My lead anchor is Theorem 3, which states that for every \(p<0\), no online algorithm has competitive ratio strictly below \(2^{-(2+2/|p|)}n^{|p|/(2|p|+1)}\). This theorem is stated in the paper but its proof is explicitly deferred to the authors’ full version, Barman, Khan, and Maiti (2021); it is not a result cited from an unrelated paper. The theorem is not NP-hardness, but it is exactly the kind of population-sensitive computational obstruction whose fate a continuous mirror can test.

A plausible regime is a national food-bank network with many local kitchens. The kitchens fall into a moderate number of standardized demand types: for example, meal programmes with the same dietary restrictions, refrigeration requirements, storage capacity, and valuation response to each category of donation. There may be millions of kitchen-equivalents but only \(\tau\) materially distinct valuation types. Donations arrive over time, their values to each type become known only at arrival, and allocation is immediate and irrevocable. This is recognizably the paper’s food-bank model, not a new welfare story invented merely to make the continuation easy.

The continuous problem I would call Type-Continuum Online \(p\)-Mean Welfare is the following. Fix \(p<0\). An instance has a finite type set \(\Theta\), rational masses \(\mu_\theta\ge 0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), a total population mass \(N\), and \(T\) divisible goods. Type \(\theta\) therefore has mass \(M_\theta=N\mu_\theta\). At round \(t\), every member of type \(\theta\) has the same value \(v_t(\theta)\), with \(\sum_{t=1}^T v_t(\theta)=1\); to retain the paper’s small-good normalization, one may also impose \(v_t(\theta)\le 1/N^2\).

When good \(t\) arrives, its vector \(v_t\) is revealed but future vectors remain hidden. The online action is a mass allocation \(y_{t,\theta}\), where \(y_{t,\theta}\) is the amount of good \(t\) assigned to type \(\theta\), subject to \(0\le y_{t,\theta}\le M_\theta\) and \(\sum_\theta y_{t,\theta}\le 1\). The average utility of a member of type \(\theta\) is \(u_\theta=\sum_t v_t(\theta)y_{t,\theta}/M_\theta\). Welfare is the mass-weighted generalized mean \(W_p(y)=\left(\sum_\theta\mu_\theta u_\theta^p\right)^{1/p}\). The offline benchmark \(\operatorname{OPT}_p\) maximizes the same expression with the complete sequence known.

The problem is to compute, without expanding the \(N\) individuals, an online policy \(\mathcal A\) and a competitive guarantee \(\rho\) such that \(W_p(\mathcal A)\ge \operatorname{OPT}_p/\rho\) for every legal valuation sequence, including adaptive adversarial sequences. A solution is the policy together with a proof of its worst-case ratio, with running time polynomial in \(\tau\), \(T\), and the numerical encoding length.

This is a genuine high-multiplicity mirror. If the masses are cleared to integers, \(M_\theta\) identical clone agents recover the discrete model. Conversely, any symmetric allocation to those clones aggregates to the variables \(y_{t,\theta}\). The paper’s information model is preserved: current values are revealed only when goods arrive, while the future remains hidden. The paper’s divisible goods remain divisible, but that is not the source of continuity here; the new continuous object is the population measure and the aggregate allocation to type mass.

I expect this lead problem to be Class A in the high-multiplicity parameter, at least when \(\tau\) is fixed or moderate and the nonzero masses are not vanishingly small. The paper’s lower bound grows with \(n\), but its adversarial combinatorics plausibly rely on steering many individually distinct agents. Once those agents are collapsed into a few type masses, an online algorithm can maintain weighted active and vulnerable type classes, rather than \(n\) individual states. A natural analogue of the paper’s \(ALG(\Phi)\) would allocate greedily among currently under-served types while reserving mass for types whose remaining valuable goods are scarce.

The important prediction is not that all online difficulty disappears. It is that the \(N^{|p|/(2|p|+1)}\) dependence should disappear or be replaced by dependence on \(\tau\) and the mass profile, perhaps through \(\mu_{\min}\). If a fixed-\(\tau\) algorithm with an \(N\)-independent ratio exists, Theorem 3’s obstruction dissolves under continuization. If a comparable lower bound persists even for constant \(\tau\), that would be a genuinely continuum-specific online barrier, Class C rather than transferred discrete hardness.

My secondary anchor is Theorem 1, which states that one online allocation achieves an \(O(\sqrt n\log n)\) approximation simultaneously for every \(p\le 1\). The theorem is a result of this paper: the conference version proves the egalitarian and Nash-welfare portions in Section 4, while the remaining ranges are deferred to the authors’ full version.

Its continuous counterpart is Universal Type-Continuum \(p\)-Mean Welfare. It uses the same instance and action variables, but asks for one online policy \(\mathcal A\), independent of \(p\), that simultaneously guarantees \(W_p(\mathcal A)\ge \operatorname{OPT}_p/R\) for every \(p\in[-\infty,1]\). The question is whether \(R\) can be bounded independently of \(N\), ideally by a function such as \(O(\sqrt{\tau}\log\tau)\) when the type masses are comparable, or more generally by a function of \(\tau\) and \(\mu_{\min}\). The solution is one explicit type-level online policy, together with the simultaneous guarantee for all \(p\).

This is not a weakened version of Theorem 1: the online revelation model, irrevocability, additive valuations, scaling assumption, generalized-mean family, and universal-policy requirement all remain. Only the list of individual agents is replaced by a finite distribution of clone types. I would expect this problem also to be Class A, though the unequal-mass analysis may be substantially harder than simply substituting \(\tau\) for \(n\).

The mirror covers Theorems 1 and 3, not the paper’s future directions on predictions, stochastic arrivals, random order, or indivisible goods. I would not separately anchor Theorem 2: its “competitive ratio strictly greater than one” statement is subsumed by the stronger \(p<0\) lower bound in Theorem 3 and adds little independent evidence.

The weakest point is that Theorem 3’s lower bound is not actually a complexity hardness result, and it may be driven by adversarial online information rather than population multiplicity. Moreover, if the original lower-bound construction requires every agent to have a distinct valuation trajectory, then collapsing agents into types removes its essential structure. The positive case therefore cannot claim that the theorem’s lower bound must dissolve. Its claim is narrower and testable: the paper supplies a faithful, author-recognizable online population mirror in which one can ask whether the \(n\)-dependent barrier survives when \(N\gg\tau\). That is a worthwhile Class A-versus-Class C question, even without an NP-hardness anchor.