Tata Institute of Fundamental Research
Advances and Challenges in Fair Division: Quantiles, Subsidies, and Randomization
STCS Seminar
Speaker:
Vishnu V Narayan (McGill University, Canada)
Organiser:
Umang Bhaskar
Date:
Wednesday, 7 Aug 2024, 11:00 to 12:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
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 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.
Short 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. 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.
| Speaker: | Vishnu V Narayan (McGill University, Canada) |
| Organiser: | Umang Bhaskar |
| Date: | Wednesday, 7 Aug 2024, 11:00 to 12:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
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 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.
Short 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. 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.