The Price of Fairness for Indivisible Goods

The Price of Fairness for Indivisible Goods

Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.
Keywords:
Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory