Constant-Factor EFX Exists for ChoresOberseminar Discrete Optimization

by Jugal Garg (University of Illinois Urbana Champaign)

Monday Mar 31, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Fair division is an age-old problem that deals with the allocation of items among agents with diverse preferences in a fair and efficient way. It naturally arises in various real-life situations, from interpersonal to international conflicts. In the discrete setting, envy-freeness up to any item (EFX) has emerged as a compelling fairness criterion, though its existence remains one of the most important open problems in fair division. In this talk, I will present recent advances in the fair allocation of indivisible chores, focusing on the first constant-factor approximation of EFX, achieved through the novel concept of earning-restricted competitive equilibrium.

 

This talk is based on joint work with Aniket Murhekar and John Qin, available  at https://arxiv.org/abs/2407.03318.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.