ISyE Seminar Series: Christian Kroer
“Best-of-Many-Worlds Guarantees for Online Fair Allocation”
Christian Kroer
Assistant Professor of Industrial Engineering and Operations Research
Columbia University
About the seminar:
We consider the problem of fairly allocating a set of goods to a set of individuals when the goods are arriving sequentially over time. In the offline setting, it is well-known that the competitive equilibrium from equal incomes (CEEI) solution concept leads to strong fairness and efficiency properties. Our goal will be to develop algorithms that can, asymptotically, compete with the hindsight CEEI allocation. We will study two allocation methods: greedy Nash welfare maximization and an online learning procedure called PACE, which is based on first-price auctions and adaptive learning of a price-per-utility multiplier for each individual. For the learning algorithm, we will show that it achieves mean-square convergence to the hindsight-optimal CEEI utilities under stochastic inputs, as well as approximate convergence under nonstationary inputs with bounded nonstationarity. For both algorithms, we show that they achieve asymptotic competitive-ratio guarantees with respect to hindsight CEEI utilities in an adversarial setting with mild assumptions on the inputs. Combining these results, we show that PACE achieves the first best-of-many-worlds guarantee for online fair allocation, by yielding guarantees under stochastic, nonstationary, and adversarial inputs.
Bio:
Christian Kroer is an Assistant Professor of Industrial Engineering and Operations Research at Columbia University, as well as a member of the Data Science Institute at Columbia. His research interests are at the intersection of operations research, economics, and computation, with a focus on how optimization and AI methods enable large-scale economic solution concepts. He obtained his Ph.D. in computer science from Carnegie Mellon University, and spent a year as a postdoc with the Economics and Computation team at Facebook Research. He is the recipient of an Office of Naval Research Young Investigator Program award and an NSF CAREER award.