Seminars

View all Seminars  |  Download ICal for this event

Best of Both Worlds in Fair Division

Series: Bangalore Theory Seminars

Speaker: Rohit Vaish, Indian Institute of Technoloby Delhi,

Date/Time: Feb 02 14:00:00

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract:
Fairness is a fundamental human endeavor. 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.

In this talk, I will focus on fair allocation of indivisible resources, which models real-world settings such as inheritance division and course allocation at universities. Traditional approaches towards this problem focus either on 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 outline some open problems and directions for future work.

Based on joint work with Haris Aziz (UNSW Sydney), Rupert Freeman (University of Virginia), and Nisarg Shah (University of Toronto). Link


Microsoft teams link:

Link

We are grateful to the Kirani family for generously supporting the theory seminar series

Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas