Preprint
Online Nash Social Welfare Maximization with Predictions
arXiv.org
08 Aug 2020
Abstract
We consider the problem of allocating a set of divisible goods to$N$agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of$T$periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial$O(N)$ , unless it is given additional information about the agents' values. Then, in line with the emerging area of "algorithms with predictions", we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the$T$periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of$O(\log N)$and$O(\log T)$if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of$O(\log^{1-\epsilon} N)$or$O(\log^{1-\epsilon} T)$for any constant$\epsilon>0$ .
Metrics
1 Record Views
Details
- Title
- Online Nash Social Welfare Maximization with Predictions
- Creators
- Siddhartha Banerjee - Cornell UniversityVasilis Gkatzelis - Drexel University, Computer ScienceArtur Gorokh - Facebook (United States, New York)Billy Jin - Cornell University
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991022202260204721