research-article

Consensus halving is PPA-complete

Authors:

Aris Filos-Ratsikas,

Paul W. GoldbergAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 51 - 64

https://doi.org/10.1145/3188745.3188880

Published: 20 June 2018 Publication History

Abstract

We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

Supplementary Material

MP4 File (1b-2.mp4)

Download
40.63 MB

References

[1]

J. Aisenberg, M.L. Bonet, and S. Buss. 2-D Tucker is PPA complete. preprint, available for download (2015).

[2]

N. Alon. Splitting Necklaces. Advances in Mathematics, 63(3), pp. 247–253 (1987).

[3]

N. Alon and D.B. West. The Borsuk-Ulam theorem and bisection of necklaces. Proceedings of the American Mathematical Society, 98(4), pp. 623–628 (1986).

[4]

P. Beame, S. Cook, J. Edmonds, R. Impagliazzo and T. Pitassi. The relative complexity of NP search problems. Journal of Computer and System Sciences 57, pp. 3–19 (1998).

Digital Library

[5]

A. Belovs, G. Ivanyos, Y. Qiao, M. Santha, and S. Yang. On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz. Procs. of the 32nd Computational Complexity Conference, Article No. 30 (2017).

Digital Library

[6]

N. Bitansky, O. Paneth, and A. Rosen. On the cryptographic hardness of finding a Nash equilibrium. Procs. of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1480–1498 (2015).

Digital Library

[7]

X. Chen, D. Dai, Y. Du, and S.-H. Teng. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. Procs. of FOCS, Atlanta, USA, pp. 273–282 (2009).

Digital Library

[8]

X. Chen and X. Deng. On the complexity of 2D discrete fixed point problem. Theoretical Computer Science, 410 (44) pp. 4448–4456 (2009).

Digital Library

[9]

X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing twoplayer Nash equilibria. Journal of the ACM 56(3) pp. 1–57 (2009).

Digital Library

[10]

X. Chen, D. Durfee, and A. Orfanou. On the Complexity of Nash Equilibria in Anonymous Games. Procs. of 47th STOC, Portland, USA, pp. 381–390 (2015).

Digital Library

[11]

X. Chen, D. Paparas, and M. Yannakakis. The complexity of non-monotone markets. Procs. of the 45th STOC, Palo Alto, USA, pp. 181–190 (2013).

Digital Library

[12]

Y. Chen, J.K. Lai, D.C. Parkes, and A.D. Procaccia. Truth, justice, and cake cutting. Games and Economic Behavior, 77(1) pp. 284–297 (2013).

[13]

B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye. The complexity of equilibria: Hardness results for economies via a correspondence with games. Theoretical Computer Science, 408 pp. 188–198 (2008).

Digital Library

[14]

C. Daskalakis, P.W. Goldberg, and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing 39(1) pp. 195–259 (2009).

Digital Library

[15]

X. Deng, J.R. Edmonds, Z. Feng, Z. Liu, Q. Qi, and Z. Xu. Understanding PPAcompleteness. 31st Conference on Computational Complexity, article no. 23, pp. 23:1–23:25 (2016).

Digital Library

[16]

X. Deng, Z. Feng, and R. Kulkarni. Octahedral Tucker is PPA-complete. Electronic Colloquium on Computational Complexity Report TR17-118 (2017).

[17]

X. Deng, Q. Qi, and A. Saberi. On the Complexity of Envy-Free Cake Cutting. CoRR, arXiv:0907.1334 (2009).

[18]

E. Elkind, L.A. Goldberg and P.W. Goldberg. Nash Equilibria in Graphical Games on Trees Revisited. Procs. of the 7th ACM Conference on Electronic Commerce (ACM EC), Ann Arbor, Michigan, USA, pp. 100–109 (2006).

Digital Library

[19]

A. Filos-Ratsikas, S. K. S. Frederiksen, P.W. Goldberg, and J. Zhang. Hardness Results for Consensus-Halving. CoRR: ArXiv:1609.05136 (2016).

[20]

R.M. Freund and M.J. Todd. A Constructive Proof of Tucker’s Combinatorial Lemma. Journal of Combinatorial Theory Series A 30, pp. 321–325 (1981).

[21]

S. Garg, O. Pandey, and A. Srinivasan. On the exact cryptographic hardness of finding a Nash equilibrium. Cryptology ePrint Archive, Report 2015/1078 (2015).

[22]

S. Garg, O. Pandey, and A. Srinivasan. Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium. Procs. of CRYPTO, Part II, LNCS 9815, pp. 579–604 (2016).

Digital Library

[23]

M. Grigni. A Sperner Lemma Complete for PPA. Information Processing Letters 77 (5–6) pp. 255–259 (2001).

Digital Library

[24]

L.A. Hemaspaandra. Computational Social Choice and Computational Complexity: BFFs? CoRR: ArXiv:1710.10753 (2017). (to appear in 32nd AAAI, 2018).

[25]

P. Hubáček, M. Naor, and E. Yogev. The Journey from NP to TFNP Hardness. Electronic Colloquium on Computational Complexity Report TR16-199 (2016).

[26]

E. Jeřábek. Integer factoring and modular square roots. Journal of Computer and System Sciences 82(2) pp. 380–394 (2016).

Digital Library

[27]

D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis. How easy is local search? J. Comput. System Sci. 37 pp. 79–100 (1988).

Digital Library

[28]

S. Kintali, L.J. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng. Reducibility among Fractional Stability Problems. SIAM Journal on Computing, 42(6) pp. 2063– 2113 (2013).

[29]

I. Komargodski, M. Naor, and E. Yogev. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. Electronic Colloquium on Computational Complexity Report TR17-015 (2017).

[30]

J. Matoušek. Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Springer (2008).

[31]

N. Megiddo. A note on the complexity of P -matrix LCP and computing an equilibrium. Res. Rep. RJ6439, IBM Almaden Research Center, San Jose. pp. 1–5 (1988).

[32]

N. Megiddo and C.H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2) pp. 317–324 (1991).

Digital Library

[33]

R. Mehta. Constant rank bimatrix games are PPAD-hard. Procs. of 46th STOC, New York, USA, pp. 545–554 (2014).

Digital Library

[34]

C.H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences 48 pp. 498–532 (1994).

Digital Library

[35]

A.D. Procaccia. Cake Cutting Algorithms. Handbook of Computational Social Choice, Chapter 13, Cambridge University Press (2016).

[36]

P. Pudlák. On the complexity of finding falsifying assignments for Herbrand disjunctions. Arch. Math. Logic, 54, pp. 769–783 (2015).

Digital Library

[37]

A. Rubinstein. Inapproximability of Nash equilibrium. Procs. of the 47th STOC, Portland, USA, pp. 409–418 (2015).

Digital Library

[38]

A. Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. Procs. of the 57th FOCS, New Brunswick, USA, pp. 258–265 (2016).

[39]

S. Schuldenzucker, S. Seuken, and S. Battiston. Finding clearing payments in financial networks with credit default swaps is PPAD-complete. Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) Conference, Berkeley, USA, (2017).

[40]

F.W. Simmons and F.E. Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical Social Sciences 45(1) pp. 15–25, (2003).

[41]

A. Thomason. Hamilton cycles and uniquely edge colourable graphs. Ann. Discrete Math. 3, pp. 259–268 (1978).

[42]

A.W. Tucker. Some topological properties of disk and sphere. Proc. First Canadian Math. Congress, Toronto: University of Toronto Press, pp. 285–309 (1945).

[43]

V.V. Vazirani and M. Yannakakis. Market equilibrium under separable, piecewiselinear, concave utilities. Journal of the ACM, 58 (3), Article 10 (2011).

Digital Library

Cited By

Deligkas AFearnley JHollender AMelissourgos TLeonardi SGupta A(2022)Constant inapproximability for PPAProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520079(1010-1023)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520079
Filos-Ratsikas AGoldberg P(2022)The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham SandwichSIAM Journal on Computing10.1137/20M131267852:2(STOC19-200-STOC19-268)Online publication date: 28-Feb-2022
https://doi.org/10.1137/20M1312678
Ikenmeyer CPak I(2022)What is in #P and what is not?2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00087(860-871)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00087
Show More Cited By

Index Terms

Consensus halving is PPA-complete
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Problems, reductions and completeness
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic game theory

Recommendations

The complexity of splitting necklaces and bisecting ham sandwiches
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We resolve the computational complexity of two problems known as Necklace Splitting and Discrete Ham Sandwich, showing that they are PPA-complete. For Necklace Splitting, this result is specific to the important special case in which two thieves share ...
The consensus string problem for a metric is NP-complete

Given a set S of strings, a consensus string of S based on consensus error is a string w that minimizes the sum of the distances between w and all the strings in S. In this paper, we show that the problem of finding a consensus string based on consensus ...
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ERC

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
331
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)2

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deligkas AFearnley JHollender AMelissourgos TLeonardi SGupta A(2022)Constant inapproximability for PPAProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520079(1010-1023)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520079
Filos-Ratsikas AGoldberg P(2022)The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham SandwichSIAM Journal on Computing10.1137/20M131267852:2(STOC19-200-STOC19-268)Online publication date: 28-Feb-2022
https://doi.org/10.1137/20M1312678
Ikenmeyer CPak I(2022)What is in #P and what is not?2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00087(860-871)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00087
Manurangsi PSuksompong W(2022)Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy TheoryTheoretical Computer Science10.1016/j.tcs.2022.07.022Online publication date: Aug-2022
https://doi.org/10.1016/j.tcs.2022.07.022
Hollender A(2022)The classes PPA-kTheoretical Computer Science10.1016/j.tcs.2021.06.016885:C(15-29)Online publication date: 22-Apr-2022
https://dl.acm.org/doi/10.1016/j.tcs.2021.06.016
Deligkas AFilos-Ratsikas AHollender A(2022)Two's company, three's a crowd: Consensus-halving for a constant number of agentsArtificial Intelligence10.1016/j.artint.2022.103784313(103784)Online publication date: Dec-2022
https://doi.org/10.1016/j.artint.2022.103784
Haviv I(2022)The Complexity of Finding Fair Independent Sets in CyclesComputational Complexity10.1007/s00037-022-00233-631:2Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1007/s00037-022-00233-6
Filos-Ratsikas AHollender ASotiraki KZampetakis MMarx D(2021)A topological characterization of modulo-p arguments and implications for necklace splittingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458219(2615-2634)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458219
Babichenko YRubinstein AKhuller SVassilevska Williams V(2021)Settling the complexity of Nash equilibrium in congestion gamesProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451039(1426-1437)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451039
Göös MKamath PSotiraki KZampetakis MAceto L(2020)On the complexity of modulo-q arguments and the chevalley-warning theoremProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.19(1-42)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.19
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents