Grainger College of Engineering, All Events

View Full Calendar

Bhaskar Ray Chaudhury "Improving EFX Guarantees Through Extremal Combinatorics"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
3401 Siebel Center for Computer Science
Date
Oct 30, 2023   10:00 am  
Speaker
Bhaskar Ray Chaudhury (UIUC)
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
8
Originating Calendar
Computer Science 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 .

link for robots only