Nisarg Shah* “Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation” (Hosted by Jobst Heitzig)
* University of Toronto
Date: 10 August 2021.
Time: 4PM GMT: 9AM San Francisco, 12PM(noon) New York and Toronto, 1PM Rio de Janeiro, 6PM Paris, 7PM Moscow, 4AM (next day) Auckland
Abstract. We study the problem of allocating indivisible goods among agents with additive valuations. Prior work achieves exact fairness in expectation when randomization is allowed or approximate fairness when a deterministic allocation must be chosen. We set out to achieve both simultaneously, by constructing randomized allocations that are exactly fair ex ante and approximately fair ex post. Our main result is that a randomized allocation that is both envy-free ex ante and envy-free up to one good ex post always exists and can be computed efficiently. We also consider efficiency guarantees, provide other possibility and impossibility results, and extend our results to the allocation of indivisible chores. This is a joint work with Rupert Freeman and Rohit Vaish.
Link to paper: https://www.cs.toronto.edu/~nisarg/papers/best_of_both.pdf
The talks are also announced and the slides/recordings posted on the seminar website https://sites.google.com/view/2021onlinescwseminars/home.