Improved Regret Bounds for Online Fair Division with Bandit Learning
This addresses fair resource allocation in dynamic settings for applications like ad auctions or task assignments, representing a strong specific gain.
The paper tackles online fair division with unknown player value distributions, achieving an expected social welfare with proportionality constraints and showing a regret bound of $ ilde{O}(\sqrt{T})$, improving on the previous $ ilde{O}(T^{2/3})$.
We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means. In this setting, a sequence of indivisible items arrives according to a random online process, and each item must be allocated to a single player. The goal is to maximize expected social welfare while maintaining that the allocation satisfies proportionality in expectation. When player values are normalized, we show that it is possible to with high probability guarantee proportionality constraint satisfaction and achieve $\tilde{O}(\sqrt{T})$ regret. To achieve this result, we present an upper confidence bound (UCB) algorithm that uses two rounds of linear optimization. This algorithm highlights fundamental aspects of proportionality constraints that allow for a UCB algorithm despite the presence of many (potentially tight) constraints. This result improves upon the previous best regret rate of $\tilde{O}(T^{2/3})$.