# Fairly Allocating Contiguous Blocks of Indivisible Items

arXiv: https://arxiv.org/abs/1707.00345 · HTML: https://mlsanity.com/paper/1707.00345/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2017.

## Built on by (most cited first, 3 of 3)

- [The Complexity of Envy-Free Graph Cutting](https://mlsanity.com/paper/2312.07043/) (2023)
- [On Approximate MMS Allocations on Restricted Graph Classes](https://mlsanity.com/paper/2508.06343/) (2025)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

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.