# Consensus Halving for Sets of Items

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

## Key facts

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

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

- [Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions](https://mlsanity.com/paper/2506.21727/) (2025)

## Abstract (arXiv)

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represented by an interval, a consensus halving with at most n cuts always exists, but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting where the resource consists of a set of items without a linear ordering. When agents have additive utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts, and show that n cuts are almost surely necessary when the agents' utilities are drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, where we wish to divide the resource into k parts in possibly unequal ratios, and provide some consequences of our results on the problem of computing small agreeable sets.