2026-07-26T03:57:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23475 2025-10-02T12:56:13Z ddc:004 open_access

The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization Huang, Zhiyi Lee, Chui Shan Shu, Xinkai Wang, Zhaozi Online Algorithms Fair Division Nash Welfare 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 -∞ ≤ p ≤ 1. Surprisingly, our improved algorithms for all p ≤ (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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhiyi Huang and Chui Shan Lee and Xinkai Shu and Zhaozi Wang 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.98 urn:nbn:de:0030-drops-234754 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.98 eng https://creativecommons.org/licenses/by/4.0/legalcode