Proportionally Fair Online Allocation of Public Goods with Predictions
Proportionally Fair Online Allocation of Public Goods with Predictions
复制标题
DOI：
10.48550/arxiv.2209.15305
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Siddhartha Banerjee;Vasilis Gkatzelis;Safwan Hossain;Billy Jin;Evi Micha;Nisarg Shah
中科院分区：
文献类型：
--
作者：
Siddhartha Banerjee;Vasilis Gkatzelis;Safwan Hossain;Billy Jin;Evi Micha;Nisarg Shah
我们设计的在线算法，公平分配的公共产品的一组N代理在一个序列的T轮，并专注于提高他们的性能，使用预测。在基本模型中，公共物品在每一轮中到达，每个代理人在到达时揭示其价值。算法必须合理地决定对该商品的投资，而不超过所有回合的总预算B。该算法可以利用（潜在的噪声）预测每个代理的总价值为所有剩余的货物。该算法的性能测量使用比例公平的目标，非正式地要求每一组代理的奖励成比例的大小和凝聚力的喜好。我们表明，没有算法可以达到比Θ（T/B）比例公平没有预测。通过合理准确的预测，情况显著改善，并且实现了Θ（log（T/B））比例公平性。我们还将我们的结果扩展到一个一般的设置，其中一批L公共产品到达在每一轮和O（log（min（N，L）T/B））比例公平性实现。我们的精确边界被参数化为预测误差的函数，随着误差的增加，性能会优雅地下降。
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.