Efficient Splitting of Measures and Necklaces

Abstract

We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $\epsilon$-CONSENSUS SPLITTING. In the problem $\epsilon$-CONSENSUS SPLITTING, there are $n$ measures, represented by valuation functions over the interval $[0, 1]$ and $k$ agents. The goal is to divide the interval, via at most $n (k-1)$ cuts, into pieces and distribute them to the $k$ agents in an approximately equitable way, so that each agent receives $1/k$ of each type of measure, with an error up to $\epsilon / 2$. It is known that this is possible even for $\epsilon = 0$. NECKLACE SPLITTING is a discrete version of $\epsilon$-CONSENSUS SPLITTING. For $k = 2$ and some absolute positive constant $\epsilon$, both of these problems are PPAD-hard.

We consider two types of approximation. The first one has the aim of providing every agent with a positive amount of measure of each type under the constraint of making at most $n (k - 1)$ cuts. The second one has the aim of providing an approximately equitable split with as few cuts as possible. Apart from the offline model, we consider the Online model as well, where the interval (or necklace) is presented as a stream, and decisions about cutting and distributing must be made on the spot.

For the first type of approximation, we provide an efficient algorithm that gives every agent at least $\frac{1}{nk}$ of each type of measure and works for the Online model as well. For the second type of approximation, we provide an efficient online algorithm that makes $\text{poly}(n, k, \epsilon)$ cuts and an offline algorithm making $O(nk \log \frac{1}{\epsilon})$ cuts. We also provide unconditional hardness results in the Online model for both problems even in the case of $k=2$ agents. Our lower bounds show that our online algorithm for the second type of approximation is optimal up to a factor of $\Theta(\log n)$ in terms of the number of cuts made.