Files and links (1)
Published, Version of Record (VoR)Open Access (License Unspecified), Open
Conference proceeding
Proportionally Fair Online Allocation of Public Goods with Predictions
PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, pp 20-28
01 Jan 2023
Abstract
We design online algorithms for the fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent's total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Theta(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Theta(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N, L) center dot T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.
Metrics
Details
- Title
- Proportionally Fair Online Allocation of Public Goods with Predictions
- Creators
- Siddhartha Banerjee - Cornell UniversityVasilis Gkatzelis - Drexel UniversitySafwan Hossain - Harvard UniversityBilly Jin - Cornell UniversityEvi Micha - University of TorontoNisarg Shah - University of Toronto
- Contributors
- E Elkind (Editor)
- Publication Details
- PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, pp 20-28
- Conference
- THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, 32nd
- Publisher
- Ijcai-Int Joint Conf Artif Intell
- Number of pages
- 9
- Grant note
- CCF 2047907 / NSF CAREER award; National Science Foundation (NSF); NSF - Office of the Director (OD) PGSD3-532673-2019 / NSERC fellowship; Natural Sciences and Engineering Research Council of Canada (NSERC) ECCS-1847393 / NSF; National Science Foundation (NSF) Simons Institute for the Theory of Computing FA9550-23-1-0068 / AFOSR; United States Department of Defense; Air Force Office of Scientific Research (AFOSR) NSERC Discovery Grant; Natural Sciences and Engineering Research Council of Canada (NSERC)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:001202344200003
- Scopus ID
- 2-s2.0-85165185675
- Other Identifier
- 991021897307804721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Computer Science, Theory & Methods