Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve
Abstract
Optimizing the operations of complex systems often involves making tradeoffs between objectives such as efficiency, revenue, and fairness. How these criteria interact is often not well understood, and current approaches focus on maximizing a convex combination which provides little operational insights. In this talk we investigate the tradeoff between fairness and efficiency in online resource allocation motivated by a partnership with the Food Bank of the Southern Tier. We start by establishing an uncertainty principle: a lower bound exactly characterizing the envy and efficiency Pareto frontier. We complement this by showing how to leverage the principle of algorithmic guardrails, artificial constraints imposed on the set of actions, which allows algorithms to exactly match the uncertainty principle. These techniques extend to a variety of settings including perishable resources, evolving budgets, and a wide range of individual preference models.
This work falls under a broader range of questions in designing practical sequential decision making algorithms for uncertain environments. Such questions include optimizing multiple objectives, as discussed above, but also in designing algorithms which computationally and statistically scale to real-world systems. Time permitting, I will highlight this by briefly discussing my work designing algorithms which leverage information relaxation in problems with exogenous dynamics. The algorithm appeals to existing computational solutions for business problems for solving large-scale deterministic optimization problems. This algorithm design is currently in deployment for the Microsoft Azure platform.
Biography
Sean Sinclair is a fifth-year Ph.D. candidate in Operations Research and Information Engineering at Cornell University, co advised by Siddhartha Banerjee and Christina Yu. He received his undergraduate degree in Honours Mathematics and Computer Science from McGill University and afterwards served as a teacher in Ghana with the Peace Corps. His research focuses on developing algorithms for data-driven sequential decision making in societal systems.
Sean was selected for the 2022 Future Leaders Summit at the Michigan Institute for Data Science. In 2020 and 2022 respectively he was a visitor at the Simons Institute for the programs on the Theory of Reinforcement Learning and Data-Driven Decision Processes. During the Summer of 2021 he was a research intern at Microsoft Research in the Reinforcement Learning group working on virtual machine scheduling in Microsoft Azure.
Optimizing the operations of complex systems often involves making tradeoffs between objectives such as efficiency, revenue, and fairness. How these criteria interact is often not well understood, and current approaches focus on maximizing a convex combination which provides little operational insights. In this talk we investigate the tradeoff between fairness and efficiency in online resource allocation motivated by a partnership with the Food Bank of the Southern Tier. We start by establishing an uncertainty principle: a lower bound exactly characterizing the envy and efficiency Pareto frontier. We complement this by showing how to leverage the principle of algorithmic guardrails, artificial constraints imposed on the set of actions, which allows algorithms to exactly match the uncertainty principle. These techniques extend to a variety of settings including perishable resources, evolving budgets, and a wide range of individual preference models.
This work falls under a broader range of questions in designing practical sequential decision making algorithms for uncertain environments. Such questions include optimizing multiple objectives, as discussed above, but also in designing algorithms which computationally and statistically scale to real-world systems. Time permitting, I will highlight this by briefly discussing my work designing algorithms which leverage information relaxation in problems with exogenous dynamics. The algorithm appeals to existing computational solutions for business problems for solving large-scale deterministic optimization problems. This algorithm design is currently in deployment for the Microsoft Azure platform.
Biography
Sean Sinclair is a fifth-year Ph.D. candidate in Operations Research and Information Engineering at Cornell University, co advised by Siddhartha Banerjee and Christina Yu. He received his undergraduate degree in Honours Mathematics and Computer Science from McGill University and afterwards served as a teacher in Ghana with the Peace Corps. His research focuses on developing algorithms for data-driven sequential decision making in societal systems.
Sean was selected for the 2022 Future Leaders Summit at the Michigan Institute for Data Science. In 2020 and 2022 respectively he was a visitor at the Simons Institute for the programs on the Theory of Reinforcement Learning and Data-Driven Decision Processes. During the Summer of 2021 he was a research intern at Microsoft Research in the Reinforcement Learning group working on virtual machine scheduling in Microsoft Azure.
Practical information
- General public
- Free
Organizer
- Prof. Daniel Kuhn
Contact
- Amandine Weissbrodt RAO Assistant administrative