Honor Among Bandits: No-Regret Learning for Online Fair Division
This addresses fair resource allocation in dynamic settings like online platforms, offering a novel algorithmic approach with theoretical guarantees, though it is incremental in applying bandit methods to fair division.
The paper tackles the problem of online fair division of indivisible goods with unknown player values, aiming to maximize social welfare under fairness constraints like envy-freeness or proportionality in expectation. It designs an explore-then-commit algorithm achieving $ ilde{O}(T^{2/3})$ regret, matching a proven lower bound, thus providing tight results.
We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space. We also prove a lower bound of $\tildeΩ(T^{2/3})$ regret for our setting, showing that our results are tight.