Bhaskar Ray Chaudhury "Improving EFX Guarantees Through Extremal Combinatorics"
- Sponsor
- Illinois Computer Science
- Speaker
- Bhaskar Ray Chaudhury (UIUC)
- Contact
- Candice Steidinger
- steidin2@illinois.edu
- Views
- 87
- Originating Calendar
- Siebel School Speakers Calendar
We look forward to seeing you in-person in 3401 Siebel Center for Computer Science.
Abstract: The existence of EFX allocations is a fundamental open problem in fair division. Given an instance comprising of n agents having monotone utilities for a set of indivisible goods, we say that an allocation is envy-free up to any good (EFX) if no agent prefers a strict subset of another agent's bundle to her own. Despite significant effort, the existence of EFX allocations has been illusive. In this talk, we show some recent results that establish the existence of "almost" EFX allocations using concepts from extremal combinatorics.
Based on joint work with Hannaneh Akrami, Noga Alon, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EC 2023. https://dl.acm.org/doi/abs/10.1145/3580507.3597799 .