Document Open Access Logo

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Authors Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos , Paul G. Spirakis

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.138.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • PPA
  • FIXP
  • ETR
  • consensus halving
  • circuit
  • reduction
  • complexity class

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete [Filos-Ratsikas and Goldberg, 2018; Filos-Ratsikas and Goldberg, 2018], we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP-hard, and deciding whether there exists a solution with fewer than n cuts is ETR-complete. We also give a QPTAS for the case where each agent’s valuation is a polynomial.
Along the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP subseteq BU subseteq TFETR and that LinearBU = PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.

Cite As Get BibTex

Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.138

Author Details

Argyrios Deligkas
  • Department of Computer Science, University of Liverpool, Liverpool, UK
  • Leverhulme Research Centre for Functional Materials Design, Liverpool, UK
John Fearnley
  • Department of Computer Science, University of Liverpool, Liverpool, UK
Themistoklis Melissourgos
  • Department of Computer Science, University of Liverpool, Liverpool, UK
Paul G. Spirakis
  • Department of Computer Science, University of Liverpool, Liverpool, UK
  • Computer Engineering and Informatics Department, University of Patras, Patras, Greece

Funding

  • Fearnley, John: The work of this author was supported by the EPSRC grant EP/P020909/1.
  • Spirakis, Paul G.: The work of this author was supported by the EPSRC grant EP/P02002X/1.

References

  1. Zachary Abel, Erik D Demaine, Martin L Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B Schardl. Who needs crossings? Hardness of plane graph rigidity. In LIPIcs-Leibniz International Proceedings in Informatics, volume 51. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  2. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ETR-complete. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 65-73. ACM, 2018. Google Scholar
  3. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. Electronic Colloquium on Computational Complexity (ECCC), 22:163, 2015. Google Scholar
  4. Noga Alon. Splitting necklaces. Advances in Mathematics, 63(3):247-253, 1987. Google Scholar
  5. Noga Alon and Douglas B West. The Borsuk-Ulam theorem and bisection of necklaces. Proceedings of the American Mathematical Society, 98(4):623-628, 1986. Google Scholar
  6. Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, and Eftychia Vakaliou. An improved envy-free cake cutting protocol for four agents. In International Symposium on Algorithmic Game Theory, pages 87-99. Springer, 2018. Google Scholar
  7. Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 416-427. IEEE, 2016. Google Scholar
  8. Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 454-464. ACM, 2016. Google Scholar
  9. Daniel Bienstock. Some provably hard crossing number problems. Discrete &Computational Geometry, 6(3):443-459, 1991. Google Scholar
  10. Vittorio Bilò and Marios Mavronicolas. The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games. In Proc. of SAGT, pages 37-48, 2012. Google Scholar
  11. Vittorio Bilò and Marios Mavronicolas. Complexity of rational and irrational Nash equilibria. Theory of Computing Systems, 54(3):491-527, 2014. Google Scholar
  12. Vittorio Bilò and Marios Mavronicolas. A catalog of EXISTS-R-complete decision problems about Nash equilibria in multi-player games. In LIPIcs-Leibniz International Proceedings in Informatics, volume 47, 2016. Google Scholar
  13. Vittorio Bilò and Marios Mavronicolas. Existential-R-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In LIPIcs-Leibniz International Proceedings in Informatics, volume 66, 2017. Google Scholar
  14. Steven J Brams and D Marc Kilgour. Competitive fair division. Journal of Political Economy, 109(2):418-443, 2001. Google Scholar
  15. Steven J Brams and Alan D Taylor. An envy-free cake division protocol. The American Mathematical Monthly, 102(1):9-18, 1995. Google Scholar
  16. Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. Google Scholar
  17. John Canny. Some Algebraic and Geometric Computations in PSPACE. In Proc. of STOC, pages 460-467, New York, NY, USA, 1988. ACM. URL: http://dx.doi.org/10.1145/62212.62257.
  18. Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete &Computational Geometry, 57(1):164-178, 2017. Google Scholar
  19. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):14, 2009. Google Scholar
  20. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Approximating the Existential Theory of the Reals. In George Christodoulou and Tobias Harks, editors, Web and Internet Economics, pages 126-139, Cham, 2018. Springer International Publishing. Google Scholar
  21. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Approximating the Existential Theory of the Reals. CoRR, abs/1810.01393, 2018. URL: http://arxiv.org/abs/1810.01393.
  22. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. CoRR, abs/1903.03101, 2019. URL: http://arxiv.org/abs/1903.03101.
  23. Xiaotie Deng, Jack R Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu. Understanding PPA-completeness. In Proceedings of the 31st Conference on Computational Complexity, page 23. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  24. Xiaotie Deng, Zhe Feng, and Rucha Kulkarni. Octahedral Tucker is PPA-complete. In Electronic Colloquium on Computational Complexity Report TR17-118, 2017. Google Scholar
  25. Francis Edward Su. Rental harmony: Sperner’s lemma in fair division. The American mathematical monthly, 106(10):930-942, 1999. Google Scholar
  26. K. Etessami and M. Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing, 39(6):2531-2597, 2010. URL: http://dx.doi.org/10.1137/080720826.
  27. Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness Results for Consensus-Halving. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 24:1-24:16, 2018. Google Scholar
  28. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus halving is PPA-complete. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 51-64, 2018. Google Scholar
  29. Aris Filos-Ratsikas and Paul W Goldberg. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.12559.
  30. Katalin Friedl, Gábor Ivanyos, Miklos Santha, and Yves F Verhoeven. Locally 2-dimensional Sperner problems complete for the Polynomial Parity Argument classes. In Italian Conference on Algorithms and Complexity, pages 380-391. Springer, 2006. Google Scholar
  31. Jugal Garg, Ruta Mehta, Vijay V Vazirani, and Sadra Yazdanbod. ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Transactions on Economics and Computation (TEAC), 6(1):1, 2018. Google Scholar
  32. Michelangelo Grigni. A Sperner lemma complete for PPA. Information Processing Letters, 77(5-6):255-259, 2001. Google Scholar
  33. Claus-Jochen Haake, Matthias G Raith, and Francis Edward Su. Bidding for envy-freeness: A procedural approach to n-player fair-division problems. Social Choice and Welfare, 19(4):723-749, 2002. Google Scholar
  34. Jiri Matousek. Intersection graphs of segments and EXISTS-R. arXiv preprint, 2014. URL: http://arxiv.org/abs/1406.2636.
  35. Ruta Mehta. Constant rank bimatrix games are PPAD-hard. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 545-554, 2014. URL: http://dx.doi.org/10.1145/2591796.2591835.
  36. Sergei Ovchinnikov. Max-min representation of piecewise linear functions. Beiträge zur Algebra und Geometrie, 43(1):297-302, 2002. URL: http://eudml.org/doc/225460.
  37. Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  38. Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):917-959, 2018. Google Scholar
  39. Marcus Schaefer. Complexity of some geometric and topological problems. In International Symposium on Graph Drawing, pages 334-344. Springer, 2009. Google Scholar
  40. Marcus Schaefer. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory, pages 461-482. Springer, 2013. Google Scholar
  41. Marcus Schaefer and Daniel Stefankovic. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Theory Comput. Syst., 60(2):172-193, 2017. URL: http://dx.doi.org/10.1007/s00224-015-9662-0.
  42. Yaroslav Shitov. A universality theorem for nonnegative matrix factorizations. arXiv preprint, 2016. URL: http://arxiv.org/abs/1606.09068.
  43. Yaroslav Shitov. The complexity of positive semidefinite matrix factorization. SIAM Journal on Optimization, 27(3):1898-1909, 2017. Google Scholar
  44. Forest W. Simmons and Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical Social Sciences, 45(1):15-25, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact