Ensuring fairness is a fundamental aspect of human nature. In times when an increasing amount of decision-making is being handed over to automated systems, it is more important than ever to provide solutions with provable, mathematically rigorous guarantees. The area of fair division provides a formal theoretical framework to reason about such questions in the context of resource allocation.

This talk will focus on the fair allocation of indivisible resources, which arises in real-world settings such as inheritance division and university course allocation. Traditional approaches to this problem involve either randomized allocations that are fair in expectation or deterministic allocations that are approximately fair. I will discuss an algorithmic framework that unifies randomization and approximation. Specifically, I will present an algorithm for finding a randomized allocation of indivisible goods that is ex-ante envy-free and ex-post envy-free up to one good. I will also touch upon some open problems and potential avenues for future research.

Based on joint work with Haris Aziz (UNSW Sydney), Rupert Freeman (University of Virginia), and Nisarg Shah (University of Toronto). https://pubsonline.informs.org/doi/full/10.1287/opre.2022.2432

Short Bio:

Rohit Vaish is an Assistant Professor in the Department of Computer Science and Engineering and an associate faculty member at the Yardi School of Artificial Intelligence, both located at IIT Delhi. Previously, he was a postdoctoral researcher at TIFR and Rensselaer Polytechnic Institute. Before that, he completed his PhD from IISc. Rohit's area of research is computational social choice. This field focuses on studying collective decision-making problems from a computational perspective. More generally, he enjoys working on problems at the intersection of economics and computer science.