You are not logged in |
New Fairness Concepts for Allocating Indivisible Items
- Speaker(s)
- Nidhi Rathi
- Affiliation
- Max-Planck-Institut für Informatik
- Language of the talk
- English
- Date
- April 3, 2025, 12:15 p.m.
- Room
- room 4050
- Title in Polish
- New Fairness Concepts for Allocating Indivisible Items
- Seminar
- Seminar Games, Mechanisms, and Social Networks
We study the fundamental problem of 'fairly' dividing a set of indivisible items among agents with varied valuations/preferences. But what does “fairly” mean? There is no single answer here and different ways of interpreting “fairly” have been considered in the literature. In this setting, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelling fairness concepts proposed to date. Despite significant efforts, existence of EFX allocations is a major open problem in fair division---let alone their efficient computation. Moreover, it is known that MMS allocations are not guaranteed to exist in all cases. These limitations weaken the practical applicability of both EFX and MMS, despite their appealing conceptual properties. As a result, there has been a growing body of research exploring relaxations and approximations of these fairness notions.
Our recent work (IJCAI-23 and AAAI-25) proposes a new promising notion of fairness, known as 'epistemic EFX (EEFX)', that is inspired by EFX. We investigate its relationship to well-studied fairness notions and, more importantly, prove that EEFX allocations always exist for general monotone valuations and can be computed efficiently for additive valuations. Our results suggest that epistemic EFX offers an excellent alternative to EFX and MMS.
