Constant inapproximability for PPA

Journal article

In the ε-Consensus-Halving problem, we are given n probability measures v1, . . . , vn 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 |vi(R+) − vi(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: Deligkas, A; Fearnley, J; Hollender, A; Melissourgos, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Computing
• Volume: 54
• Issue: 1
• Pages: 163-192
• Publication date: 2025-02-11
• Acceptance date: 2024-10-15
• DOI: 10.1137/22m1536613
• EISSN: 1095-7111
• ISSN: 0097-5397
• Language: English
• Keywords: consensus halving; ham sandwich theorem; fair division; TFNP; PPA