Hardness Results for Consensus-Halving

Abstract

We study the consensus-halving problem of dividing an object into two portions, such that each of $n$ agents has equal valuation for the two portions. The $\hat{I}\mu$-approximate consensus-halving problem allows each agent to have an $\hat{I}\mu$ discrepancy on the values of the portions. We prove that computing $\hat{I}\mu$-approximate consensus-halving solution using $n$ cuts is in PPA, and is PPAD-hard, where $\hat{I}\mu$ is some positive constant; the problem remains PPAD-hard when we allow a constant number of additional cuts. It is NP-hard to decide whether a solution with $n-1$ cuts exists for the problem. As a corollary of our results, we obtain that the approximate computational version of the Continuous Necklace Splitting Problem is PPAD-hard when the number of portions $t$ is two.

Published in MFCS 2018