The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917989557731328 |
|---|---|
| author | Huang, Zhiyi Lee, Chui Shan Shu, Xinkai Wang, Zhaozi |
| author_facet | Huang, Zhiyi Lee, Chui Shan Shu, Xinkai Wang, Zhaozi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13430 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization Huang, Zhiyi Lee, Chui Shan Shu, Xinkai Wang, Zhaozi Computer Science and Game Theory Data Structures and Algorithms 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. |
| title | The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.13430 |