Pizza Sharing Is PPA-Hard
DOI:
https://doi.org/10.1609/aaai.v36i5.20426Keywords:
Game Theory And Economic Paradigms (GTEP)Abstract
We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also prove that decision variants of the square-cut problem are hard: the approximate problem is NP-complete, and the exact problem is ETR-complete.Downloads
Published
2022-06-28
How to Cite
Deligkas, A., Fearnley, J., & Melissourgos, T. (2022). Pizza Sharing Is PPA-Hard. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4957-4965. https://doi.org/10.1609/aaai.v36i5.20426
Issue
Section
AAAI Technical Track on Game Theory and Economic Paradigms