Filos-Ratsikas, Aris 
ORCID: 0000-0001-7868-8114, Frederiksen, Soren Kristoffer Stiil, Goldberg, Paul W and Zhang, Jie
(2016)
Hardness Results for Consensus-Halving.
.
|
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 Nov 2023 07:21 |
| DOI: | 10.4230/LIPIcs.MFCS.2018.24 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127557 |
Dimensions
Dimensions
