📖
Pareto Inefficiency of EFX
Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski

Pareto Inefficiency of EFX

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX) and Pareto optimality. While some of the earliest work on EFX showed that Pareto optimal EFX allocations may not exist if agents can have zero value for some goods, it has remained open whether the same is true when all values are positive. We present a simple instance in which every good has positive value to every agent, but no Pareto optimal EFX allocation exists. We then generalize to a family of instances showing that Pareto optimal $α$-EFX allocations may not exist for any $α> 2/3$.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Pareto Inefficiency of EFX
Author / Organization Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
Subject & Discipline cs.GT
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-268135
Original Source Link Visit Source Page on arxiv.org »