Constant Inapproximability for PPA

Abstract

In the $\epsilon$-Consensus-Halving problem, we are given $n$ probability measures $v_1,\dots ,v_n$ on the interval $R=[0,1]$, and the goal is to partition $R$ into two parts $R^{+}$ and $R^{-}$ using at most $n$ cuts, so that $|v_i(R^{+})-v_i(R^{-})|\le \epsilon$ for all $i$. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA, and all subsequent PPA-completeness results for other natural problems have been obtained by reducing from it. We show that $\epsilon$-Consensus-Halving is PPA-complete even when the parameter $\epsilon$ is a constant. In fact, we prove that this holds for any constant $\epsilon <1/5$. As a result, we obtain constant inapproximability results for all known natural PPA-complete problems, including Necklace-Splitting, the Discrete-Ham-Sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.

Journal version