New Fairness Concepts for Allocating Indivisible Items

TY - GEN

T1 - New Fairness Concepts for Allocating Indivisible Items

AU - Caragiannis, Ioannis

AU - Garg, Jugal

AU - Rathi, Nidhi

AU - Sharma, Eklavya

AU - Varricchio, Giovanna

PY - 2023/8

Y1 - 2023/8

N2 - For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed until now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts-called epistemic EFX (EEFX) and minimum EFX share fairness (MXS)-inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts can be excellent alternatives to EFX and MMS.

AB - For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed until now. Unfortunately, despite significant efforts over the past few years, whether EFX allocations always exist is still an enigmatic open problem, let alone their efficient computation. Furthermore, today we know that MMS allocations are not always guaranteed to exist. These facts weaken the usefulness of both EFX and MMS, albeit their appealing conceptual characteristics. We propose two alternative fairness concepts-called epistemic EFX (EEFX) and minimum EFX share fairness (MXS)-inspired by EFX and MMS. For both, we explore their relationships to well-studied fairness notions and, more importantly, prove that EEFX and MXS allocations always exist and can be computed efficiently for additive valuations. Our results justify that the new fairness concepts can be excellent alternatives to EFX and MMS.

UR - https://www.scopus.com/pages/publications/85170370416

M3 - Article in proceedings

SP - 2554

EP - 2562

BT - IJCAI '23

A2 - Elkind, Edith

PB - Association for Computing Machinery

ER -