Hardness Results for Consensus-Halving



Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Frederiksen, Soren Kristoffer Stiil, Goldberg, Paul W and Zhang, Jie
Hardness Results for Consensus-Halving. .

[img] Text
1609.05136v2.pdf - Submitted Version

Download (319kB) | Preview

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 $\epsilon$-approximate consensus-halving problem allows each agent to have an $\epsilon$ discrepancy on the values of the portions. We prove that computing $\epsilon$-approximate consensus-halving solution using $n$ cuts is in PPA, and is PPAD-hard, where $\epsilon$ 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.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: Published in MFCS 2018
Uncontrolled Keywords: cs.GT, cs.GT, cs.CC
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 24 Jun 2021 10:29
Last Modified: 24 Jun 2021 11:10
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3127557