New Fairness Concepts for Allocating Indivisible Items
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913646783758336 |
|---|---|
| author | Caragiannis, Ioannis Garg, Jugal Rathi, Nidhi Sharma, Eklavya Varricchio, Giovanna |
| author_facet | Caragiannis, Ioannis Garg, Jugal Rathi, Nidhi Sharma, Eklavya Varricchio, Giovanna |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_01710 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | New Fairness Concepts for Allocating Indivisible Items Caragiannis, Ioannis Garg, Jugal Rathi, Nidhi Sharma, Eklavya Varricchio, Giovanna Computer Science and Game Theory 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. |
| title | New Fairness Concepts for Allocating Indivisible Items |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2206.01710 |