Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
arXiv:2105.01609 · doi:10.1016/j.tcs.2022.07.022
Abstract
We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
arXiv commentAppears in the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021
References in corpus (12)
- Almost Envy-Freeness in Group Resource Allocation
- Fair Division of Mixed Divisible and Indivisible Goods
- Asymptotic Existence of Fair Divisions for Groups
- Democratic Fair Allocation of Indivisible Goods
- Approximate Maximin Shares for Groups of Agents
- Picking Sequences and Monotonicity in Weighted Fair Division
- On Maximum Weighted Nash Welfare for Binary Valuations
- Fair Cake-Cutting among Families
- How to Cut a Cake Fairly: A Generalization to Groups
- Maximin Fairness with Mixed Divisible and Indivisible Goods
- Cutting a Cake Fairly for Groups Revisited
- Envy-Free Cake-Cutting among Families