2026-07-22T17:01:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9606 2024-03-06T10:44:31Z ddc:004 open_access

Hardness Results for Consensus-Halving Filos-Ratsikas, Aris Frederiksen, Søren Kristoffer Stiil Goldberg, Paul W. Zhang, Jie PPAD PPA consensus halving generalized-circuit reduction The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n-1 cuts exists for the problem is NP-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aris Filos-Ratsikas and Søren Kristoffer Stiil Frederiksen and Paul W. Goldberg and Jie Zhang 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.24 urn:nbn:de:0030-drops-96069 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode