THEORY SEMINAR: Please join us on March 24th at 11am in Siebel 3401, where Vishwa Prakash HV from Chennai Mathematical Institute will give a talk titled "EFX Exists for Three Types of Agents”. Please see the abstract below:
Given a set of n agents and m goods, each agent with a value for each good, we aim to allocate all the goods fairly among the agents. A natural notion of fairness is Envy-Freeness, where each agent believes they've gotten a better deal compared to others. However, there are instances where no allocation is envy-free. In light of this non-existence, Caragiannis et al introduced a natural weakening of Envy-Freeness called "Envy Free up to any good" (EFX). In an EFX allocation, the envy any agent a feels towards another agent b vanishes if we remove any one good from b's bundle.
Does every instance admit an EFX allocation? This seemingly simple question turns out to be one of the most challenging problems in Fair Division. Many researchers consider it "fair division's biggest problem" [Procaccia, Communications of the ACM: March 2020]. In a breakthrough paper, Chaudhury et al proved that EFX always exists for three agents [Best paper - EC 2020, Journal of ACM 2024]. Mahara [Discret. Appl. Math 2023] showed that EFX exists for any number of agents when there are at most two distinct valuations. That is, there are two types of agents, where agents of the same type have identical valuation on the goods.
In this talk, I'll present our recent work that generalizes both these results and shows that EFX always exists for any number of agents when there are at most three distinct valuations.