Constant inapproximability for PPA

In the ε-Consensus-Halving problem, we are given n probability measures v 1 , …, 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 − )| ≤ ε 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 ε-Consensus-Halving is PPA-complete even when the parameter ε is a constant. In fact, we prove that this holds for any constant ε < 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.

Authors

• Argyrios Deligkas
• John Fearnley
• Alexandros Hollender
• Themistoklis Melissourgos

Keywords

• PPA
• TFNP
• consensus halving
• fair division
• ham sandwich theorem