Fair allocation of indivisible chores via earning-restricted equilibria

Abstract: 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 allocation of indivisible chores, focusing on the first constant-factor approximation of EFX, achieved through the novel concept of earning-restricted competitive equilibrium. This is based on joint work with Jugal Garg and John Qin (https://arxiv.org/abs/2407.03318).