Achieving EF1 and Epistemic EFX Guarantees Simultaneously
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912899419602944 |
|---|---|
| author | Akrami, Hannaneh Mahara, Ryoga Mehlhorn, Kurt Rathi, Nidhi |
| author_facet | Akrami, Hannaneh Mahara, Ryoga Mehlhorn, Kurt Rathi, Nidhi |
| contents | We study the fundamental problem of fairly dividing a set of indivisible goods among agents with additive valuations. Here, envy-freeness up to any good (EFX) is a central fairness notion and resolving its existence is regarded as one of the most important open problems in this area of research. Two prominent relaxations of EFX are envy-freeness up to one good (EF1) and epistemic EFX (EEFX). While allocations satisfying each of these notions individually are known to exist even for general monotone valuations, whether both can be satisfied simultaneously remains open for all instances in which the EFX problem is itself unresolved.
In this work, we show that there always exists an allocation that is both EF1 (in fact, the stronger notion EFL) and EEFX for additive valuations, thereby resolving the primary open question raised by Akrami and Rathi (2025) and bringing us one step closer to resolving the elusive EFX problem. We introduce a new share-based fairness notion, termed strong EEFX share, which may be of independent interest and which implies EEFX feasibility of bundles. We show that this notion is compatible with EF1, leading to the desired existence result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11732 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Achieving EF1 and Epistemic EFX Guarantees Simultaneously Akrami, Hannaneh Mahara, Ryoga Mehlhorn, Kurt Rathi, Nidhi Computer Science and Game Theory We study the fundamental problem of fairly dividing a set of indivisible goods among agents with additive valuations. Here, envy-freeness up to any good (EFX) is a central fairness notion and resolving its existence is regarded as one of the most important open problems in this area of research. Two prominent relaxations of EFX are envy-freeness up to one good (EF1) and epistemic EFX (EEFX). While allocations satisfying each of these notions individually are known to exist even for general monotone valuations, whether both can be satisfied simultaneously remains open for all instances in which the EFX problem is itself unresolved. In this work, we show that there always exists an allocation that is both EF1 (in fact, the stronger notion EFL) and EEFX for additive valuations, thereby resolving the primary open question raised by Akrami and Rathi (2025) and bringing us one step closer to resolving the elusive EFX problem. We introduce a new share-based fairness notion, termed strong EEFX share, which may be of independent interest and which implies EEFX feasibility of bundles. We show that this notion is compatible with EF1, leading to the desired existence result. |
| title | Achieving EF1 and Epistemic EFX Guarantees Simultaneously |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.11732 |