Themistoklis Melissourgos

Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

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.

Argyrios Deligkas, John Fearnley, Alexandros Hollender et al.

We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD$=$P. In fact, we prove that computing any approximation better than $1/11$ is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions.

Argyrios Deligkas, John Fearnley, Alexandros Hollender et al.

We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, meaning that every buyer receives a $(1-δ)$-optimal bundle, instead of a perfectly optimal one. We establish the first intractability result for the problem by showing that it is PPAD-hard for some constant $δ> 0$, assuming the PCP-for-PPAD conjecture. This hardness result holds even if all buyers have identical budgets (competitive equilibrium with equal incomes), linear capped utilities, and even if we also allow $\varepsilon$-approximate clearing instead of perfect clearing, for any constant $\varepsilon < 1/9$. Importantly, we show that the PCP-for-PPAD conjecture is in fact required to show hardness for constant $δ$: showing PPAD-hardness for finding such approximate market equilibria in a broad class of markets encompassing those generated by our hardness result would prove the conjecture. This is the first natural problem where the conjecture is provably required to establish hardness for it.