Campus Event Calendar
Event Entry
What and Who
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
Xinkai Shu
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 6 May 2025
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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/logn 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.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 04/28/2025 14:54
Nidhi Rathi, 04/28/2025 14:54 -- Created document.
Nidhi Rathi, 04/28/2025 14:54 -- Created document.