Document Open Access Logo

The Complexity of Sharing a Pizza

Author Patrick Schnider

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.13.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Patrick Schnider
  • Department of Mathematical Sciences, University of Copenhagen, Denmark

Funding

The author has received funding from the European Research Council under the European Unions Seventh Framework Programme ERC Grant agreement ERC StG 716424 - CASe.

Cite AsGet BibTex

Patrick Schnider. The Complexity of Sharing a Pizza. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.13

Abstract

Assume you have a 2-dimensional pizza with 2n ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that n cuts always suffice. In this work, we study the computational complexity of finding such n cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets n cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • pizza sharing
  • Ham-Sandwich theorem
  • PPA
  • computational geometry
  • computational complexity

Metrics

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

Related Versions

References

  1. Oswin Aichholzer, Nieves Atienza, Ruy Fabila-Monroy, Pablo Perez-Lantero, Jose M Dıaz-Báñez, David Flores-Peñaloza, Birgit Vogtenhuber, and Jorge Urrutia. Balanced islands in two colored point sets in the plane. arXiv preprint, 2015. URL: http://arxiv.org/abs/1510.01819.
  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. Imre Bárány, Alfredo Hubard, and Jesús Jerónimo. Slicing convex sets and measures by a hyperplane. Discrete & Computational Geometry, 39(1-3):67-75, 2008. Google Scholar
  5. Luis Barba, Alexander Pilz, and Patrick Schnider. Sharing a pizza: bisecting masses with two cuts. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.02502.
  6. Sergey Bereg. Equipartitions of measures by 2-fans. In International Symposium on Algorithms and Computation, pages 149-158. Springer, 2004. Google Scholar
  7. Sergey Bereg. Computing generalized ham-sandwich cuts. Information Processing Letters, 112(13):532-534, 2012. Google Scholar
  8. Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo I. Silveira, Jorge Urrutia, and Kevin Verbeek. Balanced partitions of 3-colored geometric sets in the plane. Discrete Applied Mathematics, 181:21-32, 2015. Google Scholar
  9. P Bonsma, Th Epping, and Winfried Hochstättler. Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics, 154(9):1335-1343, 2006. Google Scholar
  10. Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng. Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 273-282. IEEE, 2009. Google Scholar
  11. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):1-57, 2009. Google Scholar
  12. Xi Chen, David Durfee, and Anthi Orfanou. On the complexity of nash equilibria in anonymous games. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 381-390, 2015. Google Scholar
  13. Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The complexity of non-monotone markets. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 181-190, 2013. Google Scholar
  14. Man-Kwun Chiu, Aruni Choudhary, and Wolfgang Mulzer. Computational Complexity of the α-Ham-Sandwich Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  15. Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, and Yinyu Ye. The complexity of equilibria: Hardness results for economies via a correspondence with games. Theoretical Computer Science, 408(2-3):188-198, 2008. Google Scholar
  16. 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
  17. Argyrios Deligkas, John Fearnley, and Themistoklis Melissourgos. Pizza sharing is PPA-hard. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.14236.
  18. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G Spirakis. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Journal of Computer and System Sciences, 117:75-98, 2021. Google Scholar
  19. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag New York, Inc., New York, NY, USA, 1987. Google Scholar
  20. Edith Elkind, Leslie Ann Goldberg, and Paul Goldberg. Nash equilibria in graphical games on trees revisited. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 100-109, 2006. Google Scholar
  21. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  22. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. Journal of Computer and System Sciences, 114:1-35, 2020. Google Scholar
  23. 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, pages 51-64, 2018. Google Scholar
  24. Aris Filos-Ratsikas and Paul W Goldberg. The complexity of splitting necklaces and bisecting ham sandwiches. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 638-649, 2019. Google Scholar
  25. Charles R. Hobby and John R. Rice. A moment problem in L₁ approximation. Proceedings of the American Mathematical Society, 16(4):665-670, 1965. URL: http://www.jstor.org/stable/2033900.
  26. Alfredo Hubard and Roman Karasev. Bisecting measures with hyperplane arrangements. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 169, pages 639-647. Cambridge University Press, 2020. Google Scholar
  27. Mikio Kano and Jorge Urrutia. Discrete geometry on colored point sets in the plane—a survey. Graphs and Combinatorics, 37(1):1-53, 2021. Google Scholar
  28. Roman N Karasev, Edgardo Roldán-Pensado, and Pablo Soberón. Measure partitions using hyperplanes with fixed directions. Israel Journal of Mathematics, 212(2):705-728, 2016. Google Scholar
  29. Christian Knauer, Hans Raj Tiwary, and Daniel Werner. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. In Symposium on Theoretical Aspects of Computer Science (STACS2011), volume 9, pages 649-660, 2011. Google Scholar
  30. Stefan Langerman. personal communication, 2017. Google Scholar
  31. Chi-Yuan Lo, Jiří Matoušek, and William Steiger. Algorithms for ham-sandwich cuts. Discrete & Computational Geometry, 11(1):433-452, 1994. Google Scholar
  32. Chi-Yuan Lo and William Steiger. An optimal time algorithm for ham-sandwich cuts in the plane. In Proc. 2superscriptnd Canadian Conference on Computational Geometry (CCCG 1990), pages 5-9, 1990. Google Scholar
  33. Jiri Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer Publishing Company, Inc., 2007. Google Scholar
  34. Ruta Mehta. Constant rank bimatrix games are PPAD-hard. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 545-554, 2014. Google Scholar
  35. Frédéric Meunier. Discrete splittings of the necklace. Mathematics of Operations Research, 33(3):678-688, 2008. Google Scholar
  36. 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
  37. Alexander Pilz and Patrick Schnider. Bisecting three classes of lines. Computational Geometry, 98:101775, 2021. Google Scholar
  38. Edgardo Roldan-Pensado and Pablo Soberon. A survey of mass partitions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.00478.
  39. Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):917-959, 2018. Google Scholar
  40. Patrick Schnider. Equipartitions with Wedges and Cones. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.13352.
  41. Patrick Schnider. Ham-sandwich cuts and center transversals in subspaces. Discrete & Computational Geometry, 64(4):1192-1209, 2020. Google Scholar
  42. Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston. Finding clearing payments in financial networks with credit default swaps is PPAD-complete. LIPIcs: Leibniz International Proceedings in Informatics, 67, 2017. Google Scholar
  43. William Steiger and Jihui Zhao. Generalized ham-sandwich cuts. Discrete & Computational Geometry, 44(3):535-545, 2010. Google Scholar
  44. A. H. Stone and J. W. Tukey. Generalized "sandwich" theorems. Duke Math. J., 9(2):356-359, June 1942. Google Scholar
  45. Vijay V Vazirani and Mihalis Yannakakis. Market equilibrium under separable, piecewise-linear, concave utilities. Journal of the ACM (JACM), 58(3):1-25, 2011. 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