2022/01/24 by Argyrios Deligkas, Deligkas, Argyrios, John Fearnley +5 · 1 citation
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · doi:10.48550/arxiv.2201.10011
openalex publication_date 2022/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.