The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
Published in ICALP 2025, 2025
Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang
Venue: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), LIPIcs 334, Article 98
| Links: Proceedings | arXiv | DOI |
We characterize the optimal competitive ratios for online p-mean welfare maximization over the full spectrum from egalitarian to utilitarian welfare. For a broad range of p, the result builds on greedy Nash-welfare allocation together with auxiliary components that protect agents with low utility.