Conference proceeding
Online Nash Social Welfare Maximization with Predictions
PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, pp.1-19
01 Jan 2022
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(logN) 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
5 Record Views
Details
- Title
- Online Nash Social Welfare Maximization with Predictions
- Creators
- Siddhartha Banerjee - Cornell UniversityVasilis Gkatzelis - Drexel UniversityArtur Gorokh - Facebook, New York, NY 10003 USABilly Jin - Cornell University
- Contributors
- J Naor (Editor)N Buchbinder (Editor)
- Publication Details
- PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, pp.1-19
- Conference
- 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA
- Publisher
- Siam
- Number of pages
- 19
- Grant note
- PGSD3-532673-2019 / NSERC fellowship; Natural Sciences and Engineering Research Council of Canada (NSERC) Cornell University, Ithaca, NY CCF-1755955 / NSF; National Science Foundation (NSF) Department of Computer Science, Drexel University CCF-2047907 / NSF CAREER award; National Science Foundation (NSF); NSF - Office of the Director (OD)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021903401604721
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Industry collaboration
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied