The Relative Value of Prediction & Honor Among Bandits: No-Regret Learning for Online Fair Division

Juan Perdomo's talk:

Title: The Relative Value of Prediction

Abstract: Algorithmic predictions are increasingly used to inform the allocation of goods in the public sphere. In these domains, predictions serve as a means to an end. They provide stakeholders with insights into the likelihood of future events in order to improve decision making quality, and enhance social welfare. However, if maximizing welfare is the question, to what extent is improving prediction the best answer? In this talk, I will present a formal framework to analyze these questions.

Shirley Zhang's talk:

Title: Honor Among Bandits: No-Regret Learning for Online Fair Division

Abstract: 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 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 Ω˜(T^2/3) regret for our setting, showing that our results are tight. Joint work with Ben Schiffer and Ariel Procaccia.