On Discrete Fair Division

Abstract: In this talk, we focus on a fundamental problem in discrete fair division, where the goal is to divide indivisible goods among a set of agents  "fairly". Ideally, one would aim to divide the goods such that no agent envies another agent. However, since the goods are indivisible, such allocations may not always exist (a simple scenario involving two agents and a single good). Therefore, relaxations of envy-freeness have been proposed and extensively studied.  We focus on one of the most fundamental and sought out relaxations -- envy-freeness up to any good (EFX), where no agent envies another, following the removal of any single good from the other's bundle. Despite substantial effort from the community, the existence of EFX allocations has not been settled. In this talk, we elaborate the proof of existence of "almost" EFX allocations and the existence of EFX allocations when there are only three agents. In the end, we reduce the problem of finding improved guarantees on EFX allocations to a problem in zero sum extremal combinatorics.

Bio: Bhaskar Ray Chaudhury is a Future Faculty Fellow (postdoc) at University of Illinois at Urbana Champaign (UIUC). Prior joining UIUC, he completed his PhD in 2021, from Max Planck Institute for Informatics, under the supervision of Kurt Mehlhorn and Karl Bringmann. His primary research interests lies in the theoretical foundations of economics and computation, with a particular emphasis on fair division and equilibrium computation. He also pursues fine grained complexity theory as his secondary research interest. One of his works on discrete fair division was the recipient of the Best Paper with Student Lead Author Award and the Exemplary Paper in the Theory Track Award at the ACM conference on Economics and Computation 2020 (EC 2020).

The seminar will be held via Zoom, the details have been circulated via talk-announce@cs.ox.ac.uk