Pizza Sharing is PPA-hard
This work addresses fundamental complexity questions in computational geometry and fair division, providing hardness results that are incremental but rigorous for specific pizza sharing variants.
The paper tackles the computational complexity of finding solutions for straight-cut and square-cut pizza sharing problems, showing that computing an ε-approximate solution is PPA-complete for both, with hardness applying for ε < 1/5, and that finding an exact solution for square-cut is FIXP-hard.
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an $\varepsilon$-approximate solution is PPA-complete for both problems, while finding an exact solution for the square-cut problem is FIXP-hard. Our PPA-hardness results apply for any $\varepsilon < 1/5$, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP-hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP-complete, while the decision variant for the exact version of square-cut pizza sharing is $\exists\mathbb{R}$-complete.