Proportionally Fair Online Allocation of Public Goods with Predictions
Proportionally Fair Online Allocation of Public Goods with Predictions
Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, Nisarg Shah
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 20-28.
https://doi.org/10.24963/ijcai.2023/3
We design online algorithms for 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 Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(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)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.
Keywords:
Agent-based and Multi-agent Systems: MAS: Resource allocation
Game Theory and Economic Paradigms: GTEP: Fair division