Fairly Allocating Contiguous Blocks of Indivisible Items
arXiv:1707.00345 · doi:10.1016/j.dam.2019.01.036
Abstract
In this paper, we study the classic problem of fairly allocating indivisible items with the extra feature that the items lie on a line. Our goal is to find a fair allocation that is contiguous, meaning that the bundle of each agent forms a contiguous block on the line. While allocations satisfying the classical fairness notions of proportionality, envy-freeness, and equitability are not guaranteed to exist even without the contiguity requirement, we show the existence of contiguous allocations satisfying approximate versions of these notions that do not degrade as the number of agents or items increases. We also study the efficiency loss of contiguous allocations due to fairness constraints.
Appears in the 10th International Symposium on Algorithmic Game Theory (SAGT), 2017
References in corpus (3)
Cited by in corpus (17)
- Weighted Envy-Freeness in Indivisible Item Allocation
- Almost Envy-Freeness in Group Resource Allocation
- The Price of Fairness for Indivisible Goods
- Almost Envy-Free Allocations with Connected Bundles
- Democratic Fair Allocation of Indivisible Goods
- The Price of Connectivity in Fair Division
- Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
- Redividing the Cake
- Fairly Allocating Many Goods with Few Queries
- On the Number of Almost Envy-Free Allocations
- Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints
- Equitable Allocations of Indivisible Goods
- Approximate Envy-Freeness in Graphical Cake Cutting
- Dividing a Graphical Cake
- Price of Fairness in Budget Division for Egalitarian Social Welfare
- Welfare Loss in Connected Resource Allocation
- Differentially Private Fair Division