Pizza Sharing Is PPA-Hard

The cleanest positive mirror is to treat the paper’s spatial mass distributions as valuation types of a population, while keeping the pizza itself as the divisible geometric resource. The continuity is therefore in the population, not in the land or in the cut.

Let \(Q=[0,1]^2\). A type \(t\) is a complete valuation measure \(v_t\) over \(Q\): its polygonal support, densities, normalization, and any other parameter used by the problem. A society is a rational distribution \(\boldsymbol{\mu}\) over \(T=\{1,\ldots,\tau\}\), where \(\mu_t\) is the fraction of residents having valuation type \(t\). In a finite realization, there may be \(N\gg\tau\) residents, with \(N\mu_t\) copies of type \(t\).

For a cut \(P\), let \(R^+(P)\) and \(R^-(P)\) be its two regions and define \(\Delta_t(P)=|v_t(R^+(P))-v_t(R^-(P))|\). A faithful typewise fairness requirement is \(\Delta_t(P)\le\varepsilon\) for every \(t\) with \(\mu_t>0\). This is not an aggregate shortcut: if \(M\) residents share type \(t\), one condition fairly treats all \(M\) of them. The optimization objective is to minimize the number of lines or turns subject to these constraints, or, with a fixed geometric budget, minimize the maximum \(\Delta_t(P)\).

A plausible regime is a large municipality or regional land division problem. Millions of residents may fall into a few hundred recurring spatial valuation profiles: residents of the same planning zone, workers in the same industrial cohort, or households with the same accessibility and amenity valuation. The paper’s squares and triangles can represent these profiles. This is a genuine high-multiplicity regime: the named individual is irrelevant, while the complete valuation type is not.

My strongest anchor is Theorem 13: “SC-PIZZA-SHARING is FIXP-hard even when every mass distribution consists of at most six pieces that can be unit-squares or right-angled triangles, and they have overlap 3.” This theorem is proved in the paper, using the FIXP-hardness of exact consensus halving from Deligkas et al. (2021).

The corresponding problem is \(\mathrm{Exact\text{-}Type\text{-}SC\text{-}Pizza}_\infty\):

Input: a finite type catalogue \(T\), a rational population vector \(\boldsymbol{\mu}\), and for each type \(t\) a normalized valuation \(v_t\) consisting of at most six unit squares or right-angled triangles, with overlap at most \(3\).

Question: does there exist a \(y\)-monotone square-cut path \(P\) with at most \(\tau-1\) turns such that \(\Delta_t(P)=0\) for every type in \(\operatorname{supp}(\boldsymbol{\mu})\)?

A solution is the path itself, including its horizontal and vertical segment coordinates, satisfying the paper’s non-crossing and wraparound conventions.

This is recognisably the authors’ problem, not a weakened aggregate version. The geometry, exact bisection condition, and restricted valuation shapes are unchanged; only repeated agents are represented by one type and a mass \(\mu_t\). I expect this problem to lie in Class B: the finite-agent problem embeds directly by taking one type per input mass distribution and \(\mu_t=1/\tau\). Moreover, every such hard instance can be lifted to a high-multiplicity society by making \(M\) identical copies of every type. Thus \(N=M\tau\) can be arbitrarily larger than \(\tau\), without changing the continuous instance. The hardness is not dissolved because it lives in the distinct valuation types and the geometry, rather than in the names of individual residents.

The second anchor is Theorem 14: “It is ETR-hard to decide if an exact SC-PIZZA-SHARING instance admits a solution with a SC-path with \(n-2\) turns.” This is also proved in the paper, by reducing from the cited ETR-hard exact consensus-halving problem of Deligkas et al. (2021).

Its continuous counterpart is \(\mathrm{MinTurns\text{-}Type\text{-}SC\text{-}Pizza}_\infty\):

Input: \(T\), \(\boldsymbol{\mu}\), and rationally represented weighted polygonal valuation types \(v_t\), with \(\tau\ge2\).

Question: does there exist a \(y\)-monotone square-cut path with at most \(\tau-2\) turns that exactly bisects every populated type?

Equivalently, this asks whether the minimum turn complexity \(k^\star(\boldsymbol{\mu})\) is at most \(\tau-2\), where \(k^\star\) is the least number of turns required for exact typewise fairness. The threshold is meaningful because the general existence theorem gives \(\tau-1\) turns; the question asks whether one turn can be saved.

This is a natural robustness or design problem: how simple can a public land partition be while remaining exactly fair to every resident class? I again expect hardness to transfer, probably retaining ETR-hardness. The continuous population representation removes redundant copies but does not remove the real-algebraic structure of the cut coordinates. Further questions include whether \(k^\star\) admits parameterized algorithms for small \(\tau\), and whether population weights can support a meaningful “fair to all but an \(\eta\)-fraction of society” relaxation without abandoning the paper’s typewise problem.

A useful approximate anchor is Theorem 11: “\(\varepsilon\)-SC-PIZZA-SHARING is PPA-hard even when \(\varepsilon\) is inverse-polynomial with respect to \(n\), one is allowed to use \(n+n^{1-\delta}\) turns, every mass distribution \(\mu_i\) is uniform \(d\)-\(\ell_i\)-square with \(d=O(n)\), and there is no overlap between any two mass distributions.” This theorem is proved in the paper through the checkerboard reduction from consensus halving.

The matching problem is \(\varepsilon\)-\(\mathrm{Type\text{-}SC\text{-}Pizza}_\infty\):

Input: a type distribution \(\boldsymbol{\mu}\) with \(\tau\) populated types, inverse-polynomial \(\varepsilon\), and valuation type \(v_t\) for each \(t\), where each \(v_t\) is uniform over \(d_t=O(\tau)\) equal-sized squares and the supports of distinct types do not overlap.

Output: a \(y\)-monotone square-cut path with at most \(\tau+\tau^{1-\delta}\) turns such that \(\Delta_t(P)\le\varepsilon\) for every populated type.

The expected classification is again Class B. Setting every \(\mu_t=1/\tau\) recovers the paper’s finite instance, while duplicating each type gives a society with arbitrarily many agents per type. The non-overlap restriction makes the mirror especially plausible: it does not depend on an artificial interpretation in which many groups compete over exactly the same spatial mass.

This mirror deliberately covers Theorems 11, 13, and 14. It does not claim that every result in the paper—especially the straight-cut theorems, containment results, or the \(d\)-way open problem—has already been continuized. The three selected anchors all concern the same square-cut decision object but expose different computational questions: approximate search, exact search, and minimum geometric complexity.

The weakest point is that the basic typewise feasibility problem depends on \(\boldsymbol{\mu}\) mainly through its support. Changing \(\mu_t\) from \(1\%\) to \(20\%\) does not matter if every populated type must be treated fairly. An opponent can therefore say that this is merely quotienting duplicate agents, not a powerful fractional relaxation like the programme’s LP-based bribery models. That criticism is fair, and the paper’s reductions themselves use many distinct valuation types, so they do not demonstrate that multiplicity-driven hardness disappears.

But quotienting duplicate agents is precisely what high multiplicity means here. It is not a defect that the problem becomes a function of the type catalogue rather than of the headcount. The resulting questions are still the authors’ geometric fairness problems, remain meaningful when \(N\gg\tau\), and reveal an informative boundary: for pizza sharing, continuization may compress the population without making the computational core easy. That is a legitimate and useful continuous mirror, even if its honest prediction is that these anchors belong to the hardness-transfer side rather than to Class A.