Document Open Access Logo

Hardness Results for Consensus-Halving

Authors Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.24.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Aris Filos-Ratsikas
  • École Polytechnique Fédérale de Lausanne, Switzerland
Søren Kristoffer Stiil Frederiksen
  • Aarhus University, Denmark
Paul W. Goldberg
  • University of Oxford, United Kingdom
Jie Zhang
  • University of Southampton, United Kingdom

Funding

  • Filos-Ratsikas, Aris: The author was supported by the ERC Advanced Grant 321171 (ALGAME).
  • Zhang, Jie: The author was supported by the ERC Advanced Grant 321171 (ALGAME).

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.24

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • PPAD
  • PPA
  • consensus halving
  • generalized-circuit
  • reduction

Metrics

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

Related Versions

References

  1. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. ECCC TR15, 163, 2015. Google Scholar
  2. Noga Alon. Splitting necklaces. Advances in Mathematics, 63(3):247-253, 1987. Google Scholar
  3. 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
  4. Julius B Barbanel. Super envy-free cake division and independence of measures. Journal of Mathematical Analysis and Applications, 197(1):54-60, 1996. Google Scholar
  5. Kim C Border. Fixed point theorems with applications to economics and game theory. Cambridge University Press, 1989. Google Scholar
  6. Karol Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae, 1(20):177-190, 1933. Google Scholar
  7. Steven J. Brams and D. Marc Kilgour. Competitive fair division. Journal of Political Economy, 109(2):418-443, 2001. Google Scholar
  8. Steven J. Brams and Alan D. Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. Google Scholar
  9. 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
  10. Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The complexity of non-monotone markets. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 181-190. ACM, 2013. Google Scholar
  11. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  12. Ky Fan. Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation. Journal of Combinatorial Theory, 2(4):588-602, 1967. Google Scholar
  13. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus Halving is PPA-Complete. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 51-64. ACM, 2018. Google Scholar
  14. Aris Filos-Ratsikas and Paul W. Goldberg. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. arXiv preprint arXiv:1805.12559, 2018. Google Scholar
  15. Martin Gardner. Aha! Aha! insight, volume 1. Scientific American, 1978. Google Scholar
  16. Charles H. Goldberg and Douglas B. West. Bisection of circle colorings. SIAM Journal on Algebraic Discrete Methods, 6(1):93-106, 1985. Google Scholar
  17. 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
  18. Charles R. Hobby and John R. Rice. A moment problem in L1 approximation. Proceedings of the American Mathematical Society, 16(4):665-670, 1965. Google Scholar
  19. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  20. Jerzy Neyman. Un theoreme d'existence. C. R. Acad. Sci. Paris Ser. A-B 222, pages 843-845, 1946. Google Scholar
  21. Abraham Othman, Christos H. Papadimitriou, and Aviad Rubinstein. The complexity of fairness through equilibrium. In Proceedings of the 15th ACM conference on Economics and Computation (EC), pages 209-226. ACM, 2014. Google Scholar
  22. 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
  23. Elisha Peterson and Francis Edward Su. Four-person envy-free chore division. Mathematics Magazine, 75(2):117-122, 2002. Google Scholar
  24. Timothy Prescott and Francis Edward Su. A constructive proof of Ky Fan’s generalization of Tucker’s lemma. Journal of Combinatorial Theory, Series A, 111(2):257-265, 2005. Google Scholar
  25. Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. Natick: AK Peters, 1998. Google Scholar
  26. Aviad Rubinstein. Inapproximability of Nash equilibrium. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 409-418. ACM, 2015. Google Scholar
  27. 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
  28. Emanuel Sperner. Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 6 (1), pages 265-272. Springer, 1928. Google Scholar
  29. Hugo Steinhaus. The problem of fair division. Econometrica, 16(1), 1948. Google Scholar
  30. Francis Edward Su. Rental harmony: Sperner’s lemma in fair division. The American mathematical monthly, 106(10):930-942, 1999. Google Scholar
  31. Albert William Tucker. Some Topological Properties of Disk and Sphere. Proc. First Canadian Math. Congress, Montreal, pages 285–-309, 1945. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact