Hardness results for consensus-halving

Aris Filos-Ratsikas, Stiil Frederiksen Søren Kristoffer, Paul W. Goldberg, Jie Zhang

Research output: Chapter in Book/Report/Conference proceedingChapter in a published conference proceeding

Abstract

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.
Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science
PublisherLeibniz International Proceedings in Informatics (LIPIcs)
Publication statusPublished - 15 Jun 2018

Fingerprint

Dive into the research topics of 'Hardness results for consensus-halving'. Together they form a unique fingerprint.

Cite this