




















We study the online allocation of divisible items to $n$ agents with additive valuations for $p$-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti~(2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of $-\infty \le p \le 1$. Surprisingly, our improved algorithms for all $p \le \frac{1}{\log n}$ are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。