Credit Fairness: Online Fairness In Shared Resource Pools
This addresses fairness issues in online resource allocation for agents with time-varying demands, though it is incremental as it builds on prior max-min mechanisms.
The paper tackles the problem of large disparities in total resources received by agents in shared resource pools, even with equal average demands, by introducing credit fairness to ensure agents lending resources early can recoup them later. The proposed mechanism achieves credit fairness and Pareto efficiency, with performance evaluated in a computational resource-sharing setting.
We consider a setting in which a group of agents share resources that must be allocated among them in each discrete time period. Agents have time-varying demands and derive constant marginal utility from each unit of resource received up to their demand, with zero utility for any additional resources. In this setting, it is known that independently maximizing the minimum utility in each round satisfies sharing incentives (agents weakly prefer participating in the mechanism to not participating), strategyproofness (agents have no incentive to misreport their demands), and Pareto efficiency (Freeman et al. 2018). However, recent work (Vuppalapati et al. 2023) has shown that this max-min mechanism can lead to large disparities in the total resources received by agents, even when they have the same average demand. In this paper, we introduce credit fairness, a strengthening of sharing incentives that ensures agents who lend resources in early rounds are able to recoup them in later rounds. Credit fairness can be achieved in conjunction with either Pareto efficiency or strategyproofness, but not both. We propose a mechanism that is credit fair and Pareto efficient, and we evaluate its performance in a computational resource-sharing setting.