Hardness Results for Consensus-Halving

Aris Filos-Ratsikas; Soren Kristoffer Stiil Frederiksen; Paul W. Goldberg; Jie Zhang

doi:10.4230/LIPIcs.MFCS.2018.24

Hardness Results for Consensus-Halving

Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon 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.

Original language	English
Title of host publication	43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Editors	Igor Potapov, Paul Spirakis, James Worrell
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	24:1-24:16
Number of pages	16
Volume	117
ISBN (Print)	978-3-95977-086-6
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2018.24
Publication status	Published - 27 Aug 2018
Event	43rd International Symposium on Mathematical Foundations of Computer Science, 2018 - Liverpool, United Kingdom Duration: 27 Aug 2018 → 31 Aug 2018 Conference number: 43 https://mfcs2018.csc.liv.ac.uk/index.html

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume	117
ISSN (Electronic)	1868-8969

Symposium

Symposium	43rd International Symposium on Mathematical Foundations of Computer Science, 2018
Abbreviated title	MFCS 2018
Country/Territory	United Kingdom
City	Liverpool
Period	27/08/18 → 31/08/18
Internet address	https://mfcs2018.csc.liv.ac.uk/index.html

Keywords / Materials (for Non-textual outputs)

PPAD
PPA
consensus halving
generalized-circuit
reduction

Access to Document

10.4230/LIPIcs.MFCS.2018.24Licence: Creative Commons: Attribution (CC-BY)

Hardness Results_FILOS-RATSIKAS_DOA12062018_VOR_CC-BYFinal published version, 572 KBLicence: Creative Commons: Attribution (CC-BY)

http://drops.dagstuhl.de/opus/volltexte/2018/9606Licence: Creative Commons: Attribution (CC-BY)

Cite this

Filos-Ratsikas, A., Frederiksen, S. K. S., Goldberg, P. W., & Zhang, J. (2018). Hardness Results for Consensus-Halving. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (Vol. 117, pp. 24:1-24:16). Article 24 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 117). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.MFCS.2018.24

Filos-Ratsikas, Aris ; Frederiksen, Soren Kristoffer Stiil ; Goldberg, Paul W. et al. / Hardness Results for Consensus-Halving. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). editor / Igor Potapov ; Paul Spirakis ; James Worrell. Vol. 117 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2018. pp. 24:1-24:16 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{ef4bab44c3a147199ea054d89e8e4816,

title = "Hardness Results for Consensus-Halving",

abstract = "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 epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon 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.",

keywords = "PPAD, PPA, consensus halving, generalized-circuit, reduction",

author = "Aris Filos-Ratsikas and Frederiksen, {Soren Kristoffer Stiil} and Goldberg, {Paul W.} and Jie Zhang",

year = "2018",

month = aug,

day = "27",

doi = "10.4230/LIPIcs.MFCS.2018.24",

language = "English",

isbn = "978-3-95977-086-6",

volume = "117",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",

pages = "24:1--24:16",

editor = "Igor Potapov and Paul Spirakis and James Worrell",

booktitle = "43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)",

note = "43rd International Symposium on Mathematical Foundations of Computer Science, 2018, MFCS 2018 ; Conference date: 27-08-2018 Through 31-08-2018",

url = "https://mfcs2018.csc.liv.ac.uk/index.html",

}

Filos-Ratsikas, A, Frederiksen, SKS, Goldberg, PW & Zhang, J 2018, Hardness Results for Consensus-Halving. in I Potapov, P Spirakis & J Worrell (eds), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). vol. 117, 24, Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany, pp. 24:1-24:16, 43rd International Symposium on Mathematical Foundations of Computer Science, 2018, Liverpool, United Kingdom, 27/08/18. https://doi.org/10.4230/LIPIcs.MFCS.2018.24

Hardness Results for Consensus-Halving. / Filos-Ratsikas, Aris; Frederiksen, Soren Kristoffer Stiil; Goldberg, Paul W. et al.
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). ed. / Igor Potapov; Paul Spirakis; James Worrell. Vol. 117 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2018. p. 24:1-24:16 24 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 117).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Hardness Results for Consensus-Halving

AU - Filos-Ratsikas, Aris

AU - Frederiksen, Soren Kristoffer Stiil

AU - Goldberg, Paul W.

AU - Zhang, Jie

N1 - Conference code: 43

PY - 2018/8/27

Y1 - 2018/8/27

N2 - 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 epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon 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.

AB - 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 epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in [Filos-Ratsikas and Goldberg, 2018] that the problem of computing an epsilon-approximate Consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon 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.

KW - PPAD

KW - PPA

KW - consensus halving

KW - generalized-circuit

KW - reduction

U2 - 10.4230/LIPIcs.MFCS.2018.24

DO - 10.4230/LIPIcs.MFCS.2018.24

M3 - Conference contribution

SN - 978-3-95977-086-6

VL - 117

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 24:1-24:16

BT - 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

A2 - Potapov, Igor

A2 - Spirakis, Paul

A2 - Worrell, James

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

CY - Dagstuhl, Germany

T2 - 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Y2 - 27 August 2018 through 31 August 2018

ER -

Filos-Ratsikas A, Frederiksen SKS, Goldberg PW, Zhang J. Hardness Results for Consensus-Halving. In Potapov I, Spirakis P, Worrell J, editors, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Vol. 117. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2018. p. 24:1-24:16. 24. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.MFCS.2018.24

Hardness Results for Consensus-Halving

Abstract

Publication series

Symposium

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this