Positive values do not guarantee efficient fair divisions of goods
Pareto Inefficiency of EFX
Computer Science and Game Theory
Summary
Dividing items fairly among people is tricky, especially when trying to be both fair and efficient. The authors show that even if everyone values every item positively, it’s still impossible to divide goods so that no one envies another’s share after removing any one item, while also making sure no one can be made better off without making someone else worse off. They also find that even relaxed versions of fairness may fail to coexist with maximum efficiency. This highlights limits in balancing fairness and efficiency in dividing goods.
What this means in practice
- •For marketplace designers: Understand limitations in creating perfectly fair and efficient item allocations even when all items have positive value to all participants.
- •For resource allocation engineers: Design allocation algorithms that acknowledge the impossibility of combining high fairness with full Pareto efficiency for indivisible items with positive valuations.
A theory result. No direct application yet.
Authors
Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
Abstract
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$.