Date: Wednesday, November 3rd, 2021
9:00 am – 10:00 am Pacific Time
12:00 pm – 1:00 pm Eastern Time
Location: Weekly Seminar, Zoom
Title: Sequential Fair Allocation – Achieving the Optimal Envy-Efficiency Tradeoff Curve
Abstract:
We consider the problem of dividing limited resources to individuals arriving over T rounds with a goal of achieving fairness across individuals. In general there may be multiple resources and multiple types of individuals with different utilities. A standard definition of `fairness’ requires an allocation to simultaneously satisfy envy-freeness and pareto efficiency. However, in the online sequential setting, the social planner must decide on a current allocation before the downstream demand is realized, such that no policy can guarantee these desiderata simultaneously with probability 1, requiring a modified metric of measuring fairness for online policies. We show that in the online setting, the two desired properties (envy-freeness and efficiency) are in direct contention, in that any algorithm achieving additive counterfactual envy-freeness up to a factor of L_T necessarily suffers an efficiency loss of at least 1 / L_T. We complement this uncertainty principle with a simple algorithm, HopeGuardrail, which allocates resources based on an adaptive threshold policy and is able to achieve any fairness-efficiency point on this frontier. Our result is the first to provide guarantees for fair online resource allocation with high probability for multiple resource and multiple type settings. In simulation results, our algorithm provides allocations close to the optimal fair solution in hindsight, motivating its use in practical applications as the algorithm is able to adapt to any desired fairness efficiency trade-off. This is joint work with Sean Sinclair and Siddhartha Banerjee.
Bio:
Christina Lee Yu is an Assistant Professor at Cornell University in the School of Operations Research and Information Engineering. Prior to Cornell, she was a postdoc at Microsoft Research New England. She received her PhD and MS in EECS from MIT, and her BS in CS from Caltech. Her PhD thesis was awarded an honorable mention for the 2018 INFORMS Dantzig Dissertation Award. She is a 2021 recipient of the Intel Rising Stars Award and a JPMorgan Faculty Research Award. Her research interests include algorithm design and analysis, high dimensional statistics, inference over networks, sequential decision making under uncertainty, online learning, and network causal inference.