Title | : | Advances and Challenges in Fair Division: Quantiles, Subsidies, and Randomization |
Speaker | : | Vishnu V. Narayan (Tel Aviv University) |
Details | : | Mon, 29 Jul, 2024 3:00 PM @ Turing Hall (SSB 334 |
Abstract: | : | The question of how to fairly divide a collection of indivisible items amongst a set of agents has remained of central importance to humanity since antiquity. In this fundamental problem, the agents have varied preferences, and an allocator seeks to find a single allocation such that every agent perceives its bundle as fair. This problem arises in various applications, ranging from classical examples like the division of inherited estates and international borders to modern applications such as assigning seats in college courses and allocating computational resources fairly.
Recent decades have witnessed significant progress, transforming this problem into a fascinating mathematical landscape with surprising results and intriguing new challenges. The broad goal of the community is to devise definitions of fairness that mirror our intuitive understanding of what it means to be fair, and then study questions such as: does a fair allocation always exist?; can one be (efficiently) computed?; what are the precise limits to the degree of fairness one can guarantee? Fair division is emerging as a major research area, with an increasing number of publications at the top CS Theory and AI conferences each year. In this talk, I will focus on selected recent papers of mine, highlighting three techniques (Quantiles, Subsidies, and Randomization) we use to extend the study of fair allocations to general valuation classes and resolve some conjectures and open problems. This talk will also provide an overview of my research trajectory and plans for future work. Bio: Vishnu V. Narayan is a postdoctoral fellow hosted by Michal Feldman at Tel Aviv University. His main research focus is on the fair division of indivisible items. He is also broadly interested in the many intersections of combinatorics, algorithms, and game theory, has published in a range of top CS conferences and journals. He has a best paper award from SAGT 2019 and a Highlights Session selection at EC 2024. Earlier, he completed his Ph.D. in Computer Science at McGill University under the supervision of Adrian Vetta, and his M.Math. in Combinatorics and Optimization at the University of Waterloo with Joseph Cheriyan. |