We study the consensus-halving problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. The ϵ-approximate consensus-halving problem allows each agent to have an ϵ discrepancy on the values of the portions. We prove that computing ϵ-approximate consensus-halving solution using n cuts is in PPA, and is PPAD-hard, where ϵ is some positive constant; the problem remains PPAD-hard when we allow a constant number of additional cuts. It is NP-hard to decide whether a solution with n−1 cuts exists for the problem. As a corollary of our results, we obtain that the approximate computational version of the Continuous Necklace Splitting Problem is PPAD-hard when the number of portions t is two.
|Title of host publication
|43rd International Symposium on Mathematical Foundations of Computer Science
|Leibniz International Proceedings in Informatics (LIPIcs)
|Published - 15 Jun 2018