Logo image
Back
Online Nash Social Welfare Maximization with Predictions
Conference paper   Open access

Online Nash Social Welfare Maximization with Predictions

Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh and Billy Jin
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1-19
01 Jan 2022
DOI: https://doi.org/10.1137/1.9781611977073.1
url
https://doi.org/10.48550/arxiv.2008.03564View
Accepted (AM) Open arXiv.org - Non-exclusive license to distribute

Abstract

Computer Science, Theory & Methods Mathematics, Applied Science & Technology Computer Science Mathematics Physical Sciences Technology
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

8 Record Views
36 citations in Web of Science

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Industry collaboration
Domestic collaboration
Web of Science research areas
Computer Science, Theory & Methods
Mathematics, Applied
Logo image