Hardness Results for Consensus-Halving
Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang · 2018
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 -approximate version, which allows each agent to have an discrepancy on the values of the portions. It was recently proven in [13] that the problem of computing an -approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when is inverse-exponential. In this paper, we prove that when 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.