Pizza Sharing is PPA-hard

Introduction

Mass partition problems ask to fairly divide measurable objects that are embedded into Euclidean space [RS20]. Perhaps the most popular mass partition problem is the ham sandwich problem, in which three masses are given in three-dimensional Euclidean space, and the goal is to find a single plane that cuts all three masses in half. Recently, there has been interest in pizza sharing problems, which are mass partition problems in the two-dimensional plane, and in this paper we study the computational complexity of such problems.

In the straight-cut pizza sharing problem, we are given $2n$ two-dimensional masses in the plane, and we are asked to find $n$ straight lines that simultaneously bisect all of the masses. See Figure 1(a) for an example. It has been shown that this problem always has a solution: the first result on the topic showed that solutions always exist when $n=2$ [BPS19], and this was subsequently extended to show existence for all $n$ [HK20].

R^{+} and $R^{-}$ (shaded and non-shaded areas respectively). Another related problem is the square-cut pizza sharing. In this problem, there are $n$ masses in the plane, and the task is to simultaneously bisect all masses using cuts, but the method of generating the cuts is different. Specifically, we seek a square-cut, which consists of a single path that is the union of horizontal and vertical line segments. See Figure 1(b) and Figure 1(c) for two examples of square-cuts. Intuitively, we can imagine that a pizza cutter is placed on the plane, and is then moved horizontally and vertically without being lifted in order to produce the cut. Note that the path is allowed to wrap around on the horizontal axis: if it exits the left or right boundary, then it re-appears on the opposite boundary. So the cut in Figure 1(c) is still considered to be a single square-cut.

It has been shown by [KRPS16] that, given $n$ masses, there always exists a square-cut-path (termed SC-path) which makes at most $n-1$ turns and simultaneously bisects all of the masses. This holds even if the SC-path is required to be $y$-monotone, meaning that the path never moves downwards.

Two-dimensional fair division is usually called land division in the literature. Land division is a prominent topic of interest in the Economics and AI communities that studies ways of fairly allocating two-dimensional objects among $n$ agents [Cha05, SHNHA17, SNHA20, ESS21, AD15, IH09, Hüs11]. The first popular appearance of such problems in a mathematical description was done by [Ste48], and since then, the existence of allocations under various fairness criteria have been extensively studied, together with algorithms that achieve them. These problems find applications from division of resources on land itself, to the Law of the Sea [SS03], to redistricting [LRY09, LS14].

Consensus halving is a problem that asks us to split a one-dimensional resource into two parts such that $n$ agents have equal value in both parts. Here, we study the same fairness criterion for $n$ agents, but for a two-dimensional resource. One can see that when we have the same fairness criterion at hand for any $k$-dimensional resource, $k\geq 2$, we can always translate the problem into its one-dimensional version, by integrating each agent’s measure to a single dimension. Then a solution can be given by applying consensus halving. However, the solutions we get by doing so, are not taking into account the dimensionality of the problem, and as a result they might produce very unnatural solutions to a high-dimensional problem. For example, in land division, applying consensus halving would produce two parts, each of which can possibly be a union of $\left\lceil n/2\right\rceil$ disjoint land strips. Can we get better solutions by exploiting all the dimensions of the problem?

In this work we investigate different cutting methods of the two-dimensional objects, and in particular, two pizza sharing methods for which a solution is guaranteed. While based on intuition one might assume that exploiting the two dimensions would allow the complexity of finding a solution to be lower, our results show that this is not the case. We present polynomial time reductions from the one-dimensional problem to the two-dimensional problems showing that the latter are at least as hard as the former, i.e., PPA-hard. Apart from the hardness results themselves, we believe that our reductions are interesting from another aspect too. They show ways to efficiently turn a problem into one of higher dimension, a task that has no standardised methods to be achieved (even for non-efficient reductions), and whose inverse is trivially achievable.

Computational complexity of fair division problems. There has been much interest recently in the computational complexity of fair division problems. In particular, the complexity class PPA has risen to prominence, because it appears to naturally capture the complexity of solving these problems. For example, it has recently been shown by [FRG18, FRG19] that the consensus halving problem, the ham sandwich problem, and the well-known necklace splitting problem are all PPA-complete.

The other class of relevance here is the class BU, which consists of all problems that can be polynomial-time reduced to finding an exact solution to a Borsuk-Ulam function. This class was defined by [DFMS21] and is believed to be substantially harder than the class PPA, because it is possible to construct a Borsuk-Ulam function that only has irrational solutions. Due to this, it is not currently expected that BU will be contained in FNP, whereas the containment of PPA in FNP is immediate.

Unfortunately, it is not currently known whether BU has complete problems. However, in [DFMS21] it was shown that exact consensus halving is in BU and also FIXP-hard, implying that $\textup{{FIXP}}\subseteq\textup{{BU}}$. FIXP, defined by Etessami and Yannakakis [EY10], is the class of problems that can be reduced to finding an exact fixed point of a Brouwer function. It is known by the aforementioned work, that FIXP contains the problem Square Root Sum, which has as input positive integers $a_{1},\dots,a_{n}$ and $k$, and asks whether $\sum_{i=1}^{n}\sqrt{a_{i}}\leq k$. The question of whether Square Root Sum is in NP has been open for more than 40 years ([GGJ76, Pap77, Tiw92]). Furthermore, since there exist Brouwer functions that only have irrational fixed points, it is likewise not expected that FIXP will be contained in FNP.

Our contribution. We study the computational complexity of the straight-cut and square-cut pizza sharing problems, and we specifically study the cases where (i) all mass distributions are unions of weighted polygons, and (ii) we are given unweighted point sets. We show that it is PPA-complete to find approximate solutions of the approximate versions of all the problems, while their decision variants are NP-complete. We also show that the exact square-cut pizza sharing problem with mass distributions is FIXP-hard and in BU, while its decision variant is ETR-complete. All of our hardness results are summarized in Table 1 and Table 2.

These results represent, to the best of our knowledge, the first PPA-hardness results for problems arising from computational geometry. We also note that pizza sharing problems do not need a circuit as part of the input, which makes them in some sense more “natural” than problems that are specified by circuits. Other known “natural” PPA-hard problems are one-dimensional, such as consensus halving [FHSZ20] and necklace splitting [FRG19]. Here we show the first known PPA-hardness result for a “natural” two-dimensional problem. Let us also mention here that shortly after the appearance of our result, Schnider in [Sch21] proved that the discrete version of straight-cut pizza sharing where each mass is represented by unweighted points is PPA-complete, while its continuous version for a more general input representation is FIXP-hard.

Recently, [BHH21] made great improvement towards showing BU-hardness of exact consensus halving. They introduced a class named BBU whose typical problem is an equivalent, alternative definition of the Borsuk-Ulam theorem, and they considered the strong approximation version of the classes BU and BBU, named $\textup{{BU}}_{a}$ and $\textup{{BBU}}_{a}$, respectively. Some of the most notable results of the aforementioned paper is that $\textup{{BU}}_{a}=\textup{{BBU}}_{a}$ and that the strong approximation version of consensus halving is complete for $\textup{{BU}}_{a}$. We believe that some of our reductions will be able to be translated into the framework of strong approximation and yield analogous $\textup{{BU}}_{a}$-hardness results for the strong approximation version of pizza sharing problems. However, we remark that BU-completeness of either exact consensus halving or any of the pizza sharing problems is yet to be proven.

For both the straight-cut and the square-cut pizza sharing problems, we show that it is PPA-complete to find an $\varepsilon$-approximate solution for any constant $\varepsilon\in(0,1/5)$. This holds even when $n+n^{1-\delta}$ lines are permitted in a straight-cut pizza sharing instance with $2n$ mass distributions, and when $n-1+n^{1-\delta}$ turns of the square-cut path are permitted in a square-cut pizza sharing instance with $n$ mass distributions, for constant $\delta>0$. Furthermore, the PPA-hardness holds even when each mass distribution is uniform over polynomially many axis-aligned rectangles, and there is no overlap between any two mass distributions. The inapproximability for such high values of $\varepsilon$ is possible due to a recent advancement in the inapproximability of consensus halving [DFHM22]. The PPA-inclusion holds even for inverse polynomial and inverse exponential $\varepsilon$, and for weighted polygons with holes (that is, the most general type of allowed input). Furthermore, we show that there exists an $\varepsilon>0$ such that deciding whether an $\varepsilon$-approximate solution of straight-cut pizza sharing with at most $n-1$ lines (resp. an $\varepsilon$-approximate solution of square-cut pizza sharing with at most $n-2$ turns) exists or, is NP-complete. All of these results hold also for the discrete version of the problems.

We then turn our attention to the computational complexity of finding an exact solution to the square-cut problem. We show that the problem of finding an SC-path with at most $n-1$ turns that exactly bisects $n$ masses lies in BU, and is FIXP-hard. This hardness result applies even if all mass distributions are unions of weighted axis-aligned squares and right-angled triangles. In order to prove containment in BU, we provide a simpler existence proof for a solution to the square-cut pizza sharing problem that follows the lines of the original proof by [KRPS16], while to prove the FIXP-hardness, we reduce from the problem of finding an exact Consensus-Halving solution [DFMS21]. Regarding the decision version of the square-cut problem, we show that deciding whether there exists an exact solution with at most $n-2$ turns is ETR-complete, where ETR consists of every decision problem that can be formulated in the existential theory of the reals (see Section 2 for its definition).

From a technical viewpoint, our PPA containment result for straight-cut pizza sharing is based on a reduction that transforms mass distributions to point sets in general position and then employs a recent result by [Sch21]. On the contrary, our containment results for square-cut pizza sharing are shown by directly reducing it to the Borsuk-Ulam problem. Our hardness results are obtained by reducing from the consensus halving problem, historically the first fair-division problem shown to be PPA-complete [FRG18]. It is worth mentioning that, if in the future, consensus halving with linear valuation densities (see definitions of $k$-block-triangle valuations in Section 2) is shown to be BU-complete, then our work implies BU-completeness of exact square-cut pizza sharing.

Further related work. Since mass partitions lie in the intersection of topology, discrete geometry, and computer science there are several surveys on the topic; [BFHZ18, DLGMM19, Mat08, Živ17] focus on the topological point of view, while [AE+99, Ede12, KK03, Mat02] focus on computational aspects. Consensus halving [SS03] is the mass partition problem that received the majority of attention in Economics and Computation so far [DFH21, FRFGZ18, FRG19, FHSZ20, FRHSZ21]. Recently, Haviv [Hav22] showed PPA-completeness of finding fair independent sets on cycle graphs, having as a starting point the latter problem.

Preliminaries

Mass distributions. A mass distribution $\mu$ on $^{2}$ is a measure on the plane such that all open subsets of $^{2}$ are measurable, $0<\mu\left(^{2}\right)<\infty$, and $\mu(S)=0$ for every subset of $^{2}$ with dimension lower than 2. A mass distribution $\mu$ is finite-separable, or simply separable, if it can be decomposed into a finite set of non-overlapping areas $a_{1},a_{2},\ldots,a_{d}$ such that $\mu\left(^{2}\right)=\sum_{j=1}^{d}\mu(a_{j})$. In addition, a separable mass distribution $\mu$ is piece-wise uniform, if for every $j$ and every $S\subseteq a_{j}$ it holds that $\mu(a_{j}\cap S)=w_{j}\cdot\text{area}(a_{j}\cap S)$ for some weight $w_{j}>0$ independent of $S$. When additionally $w_{j}=w_{k}$ for all $j,k\in[d]$ then the mass distribution is called uniform. Finally, a mass distribution is normalised if $\mu(^{2})=1$. The support of mass distribution $i$, denoted by $supp(i)$, is the area $A_{i}\subseteq^{2}$ which has the property that for every $S\subseteq A_{i}$ with non-zero Lebesgue measure we have $\mu_{i}(S)>0$. Let $N:=\{I\subseteq[n]:\bigcap_{i\in I}supp(i)\neq\emptyset\}$. A set of mass distributions $\mu_{1},\dots,\mu_{n}$, or colours, has overlap $k$ if $\max_{I\in N}|I|=k$. In order to easily present our results that concern additive approximations, throughout this work we consider all mass distributions to be normalised, which is without loss of generality.

Set of straight-cuts. A set of straight-cuts, or cut-lines, or simply lines defines subdivisions of the plane $R$. Figure 1(a) shows an example of a set of straight-cuts. Each line creates two half-spaces, and arbitrarily assigns number “” to one and “$1$” to the other. A subdivision of $R$ is labeled “$+$” (and belongs to $R^{+}$) if its parity is odd (according to the labels given to the half-spaces) and “$-$” (and belongs to $R^{-}$) otherwise. Observe that by flipping the numbers of two half-spaces defined by a line, we flip all the subdivisions’ labels. Thus, there are only two possible labelings of the subdivisions.

Square-cut-path. A square-cut-path, denoted for brevity SC-path, is a non-crossing directed path that is formed only by horizontal and vertical line segments and in addition it is allowed to “wrap around” in the horizontal dimension. Figure 1(b), Figure 1(c) show two examples of SC-paths. A turn of the path is where a horizontal segment meets with a vertical segment. An SC-path is $y$-monotone if all of its horizontal segments are monotone with respect to the $y$ axis. Any SC-path partitions the plane into two regions, that we call $R^{+}$ and $R^{-}$.

Pizza sharing. A set of lines (resp. a SC-path) $\varepsilon$-bisects a mass distribution $\mu$, if $|\mu(R^{+})-\mu(R^{-})|\leq\varepsilon$. It simultaneously $\varepsilon$-bisects a set of mass distributions $M$ if $|\mu_{i}(R^{+})-\mu_{i}(R^{-})|\leq\varepsilon$ for every $\mu_{i}\in M$.

R^{+} and $R^{-}$ using at most $n$ lines such that for each $i\in[2n]$, it holds that $|\mu_{i}(R^{+})-\mu_{i}(R^{-})|\leq\varepsilon$. Definition 3. For any $n\geq 1$, the problem $\varepsilon$-SC-Pizza-Sharing is defined as follows: • Input: $\varepsilon\geq 0$ and mass distributions $\mu_{1},\mu_{2},\ldots,\mu_{n}$ on $^{2}$. • Output: A partition of $^{2}$ to $R^{+}$ and $R^{-}$ using a SC-path with at most $n-1$ turns such that for each $i\in[n]$, it holds that $|\mu_{i}(R^{+})-\mu_{i}(R^{-})|\leq\varepsilon$. In [KRPS16], it was proved that $\varepsilon$-SC-Pizza-Sharing always admits a solution for arbitrary continuous measures with respect to the Lebesgue measure, and for any $\varepsilon\geq 0$. In this work, we are interested in the computational aspect of the problem, hence we need to specify its input representation. For simplicity, we deal with measures determined by sets of polygons with holes, since even these simply-defined measures suffice to yield PPA-hardness. The precise input representation is described in Appendix A.

Although it is not hard to construct instances of $\varepsilon$-SC-Pizza-Sharing where $n-1$ turns are necessary for any SC-path in order to constitute a solution, there might be cases where a solution can be achieved with an SC-path with fewer turns. Hence, we also study the decision version of the problem, in which we ask whether we can find a solution with $k$ turns, where $k<n-1$.

Consensus halving. The hardness results that we will show in this paper will be shown by a reduction from the consensus halving problem.

In the $\varepsilon$-Consensus-Halving problem, there is a set of $n$ agents with valuation functions $v_{i}$ over the interval $$, and the goal is to find a partition of the interval into subintervals labelled either “$+$” or “$-$”, using at most$n$cuts. This partition should satisfy that for every agent$i$, the total value for the union of subintervals$\mathcal{I}^{+}$labelled “$+$” and the total value for the union of subintervals$\mathcal{I}^{-}$labelled “$-$” is the same up to$\varepsilon$, i.e.,$|v_{i}(\mathcal{I}^{+})-v_{i}(\mathcal{I}^{-})|\leq\varepsilon$. We will consider the following types for a valuation function$v_{i}$; see Figure 2 for a visualization.

$k$-block uniform. $v_{i}$ is $k$-block and the density of every interval is $c_{i}$.

Complexity classes. $\varepsilon$-SC-Pizza-Sharing is an example of a total problem, which is a problem that always has a solution. The complexity class TFNP (Total Function NP) defined in [MP91], contains all total problems whose solutions can be verified in polynomial time.

There are several well-known subclasses of TFNP that we will use in this paper. The class PPA, defined by Papadimitriou [Pap94], captures problems whose totality is guaranteed by the parity argument on undirected graphs. The complexity class $\textup{{PPAD}}\subseteq\textup{{PPA}}$ is the subclass of PPA containing all problems whose totality is guaranteed by the parity argument on directed graphs.

The complexity class ETR consists of all decision problems that can be formulated in the existential theory of the reals [Mat14, Sch09]. It is known that $\textup{{NP}}\subseteq\textup{{ETR}}\subseteq\textup{{FNP}}$ [Can88], and it is generally believed that ETR is distinct from the other two classes. The class FETR (Function ETR) consists of all search problems whose decision version is in ETR. The class TFETR is the subclass of FETR which contains only problems that admit a solution (i.e. all the instances of their decision version are “yes” instances). Both FETR and TFETR were introduced in [DFMS21] as the natural analogues of FNP and TFNP in the real RAM model of computation. For a definition of the real RAM model we refer the reader to the detailed work of Erickson, van der Hoog, and Miltzow [EvM20].

In this paper, our focus regarding computational complexity will be on the following two classes contained in TFETR. As mentioned earlier, the class $\textup{{BU}}\subseteq\textup{{TFETR}}$ was introduced in [DFMS21] and captures problems whose totality is guaranteed by the Borsuk-Ulam theorem. The class $\textup{{FIXP}}\subseteq\textup{{BU}}$ was defined in [EY10] and captures problems whose totality is guaranteed by Brouwer’s fixed point theorem.

Hardness results

Here we show all hardness results regarding the exact and approximate versions of our pizza sharing problems for mass distributions, as well as for point sets.

We start by proving that $\varepsilon$-Straight-Pizza-Sharing is PPA-hard for any $\varepsilon<1/5$, even for very simple mass distributions. We prove our result via a reduction from $\varepsilon$-Consensus-Halving with $k$-block valuations, which for the special case of $3$-block uniform valuations has been shown to be PPA-complete [DFHM22]. In addition, we explain how to combine the machinery of our reduction with that of [FRFGZ18] in order to get NP-hardness for $\varepsilon$-Straight-Pizza-Sharing, where $\varepsilon>0$ is a small constant.

We reduce from Consensus-Halving with $2n$ agents, and for each agent we create a corresponding mass in Straight-Pizza-Sharing. Firstly, we finely discretize the $$interval into blocks and we place the blocks on$y=x^{2}$, where$x\geq 0$. So, the$$interval corresponds to a part of the quadratic equation. This guarantees that every line can cut this “bent” interval at most twice and in addition the part of each mass that is in$R^{+}$is almost the same as value of the corresponding agent for the piece of$$labelled with “$+$”. Next we show how to construct an instance$I_{P}$of$(\varepsilon-\varepsilon^{\prime})$-Straight-Pizza-Sharing with$2n$mass distributions, for any$\varepsilon^{\prime}=\frac{1}{\textup{poly}(n)}<\varepsilon$, given an instance$I_{\textsc{CH}}$of$\varepsilon$-Consensus-Halving with$2n$agents with$k$-block valuations.

Let $c_{\max}:=\max_{i\in[2n],m\in[k]}c_{im}$, where $c_{im}$ is the value density of agent $i$’s $m$-th block in $I_{\textsc{CH}}$, and observe that $c_{\max}\geq 1$ since the total valuation of any agent over $$is$1$. In what follows, it will help us to think of the interval$$in$I_{\textsc{CH}}$as being discretized in increments of$d:=\frac{1}{\left\lceil 4\cdot n^{2}\cdot c_{\max}\right\rceil}$. We refer to the subinterval$\left[(j-1)\cdot d,j\cdot d\right]$as the$j$-th$d$-block of interval$$in$I_{\textsc{CH}}$, for$j\in[1/d]$.

We now describe the instance $I_{P}$. For ease of presentation, the space of the instance is inflated to $\left[0,\left(\frac{6}{d^{2}}\right)^{2}+1\right]^{2}$, but by scaling the construction down, the results are attained. We consider two kinds of square tiles; $1/d$ large square tiles of size $1\times 1$, each of which contains $2n$ smaller square tiles of size $\frac{1}{2n}\times\frac{1}{2n}$ on its diagonal. We will call the former type big-tile and denote it by $t_{j}$ and the latter one small-tile and denote it by $t_{ij}$ for some $i\in[2n]$, $j\in[1/d]$.

The centers of consecutive big-tiles are positioned with $\frac{6}{d}$ distance apart in the $x$-axis. For $j\in[1/d]$ we define $s_{j}=\frac{6}{d}\cdot j$. For every agent $i\in[2n]$ we will create a uniform mass distribution $\mu_{i}$ that consists of at most $1/d$ many axis-aligned small-tiles. Each big-tile $t_{j}$, $j\in[1/d]$, is centered at $\left(s_{j},s_{j}^{2}\right)$ while, in it, each small-tile $t_{ij}$, $i\in[2n]$, belonging to mass distribution $\mu_{i}$ has its bottom left corner at $\left(s_{j}+\frac{i-1}{2n},s_{j}^{2}+\frac{i-1}{2n}\right)$. Each small-tile $t_{ij}$ contains total mass (belonging to $\mu_{i}$) of exactly the same total value $v_{ij}$ as that of agent $i$’s $j$-th $d$-block in $I_{\textsc{CH}}$. Observe that, by definition, the value $v_{ij}$ of the $j$-th $d$-block for agent $i$ is at most $d\cdot c_{\max}\leq\frac{1}{2n\cdot 2n}$, and therefore it fits inside the small tile of size $\frac{1}{2n}\times\frac{1}{2n}$. In particular, the mass inside $t_{ij}$ has width $\frac{1}{2n}$ and height $v_{ij}\cdot 2n$. Figure 3 and Figure 4 depict our construction.

The proof of the following lemma can be found in LABEL:app:_{lem:lines-to-cuts}.

This, together with the fact that $\varepsilon$-Consensus-Halving is PPA -hard for any $\varepsilon<1/5$, due to [DFHM22], implies the main theorem of this section.

$\varepsilon$-Straight-Pizza-Sharing with $2n$ mass distributions is PPA-hard for any constant $\varepsilon<1/5$, even when $n+n^{1-\delta}$ lines are allowed for any given constant $\delta>0$, every mass distribution is uniform over polynomially many rectangles, and there is no overlap between any two mass distributions.

We will now shift our attention to studying the decision version of the problem, where we are asking to find a solution that uses at most $n-1$ straight lines, and notice that there is no guarantee for such a solution. We employ the NP-hard instances of $\varepsilon$-Consensus-Halving for their constant $\varepsilon$ from [FRFGZ18], and reduce them according to the above reduction procedure to $(\varepsilon-\varepsilon^{\prime})$-Straight-Pizza-Sharing instances for some $\varepsilon^{\prime}$ that is inverse polynomial in the input size, e.g., $\varepsilon^{\prime}=1/n^{2}$. This gives the following.

There exists a constant $\varepsilon>0$ for which it is NP-hard to decide if an $\varepsilon$-Straight-Pizza-Sharing instance with $2n$ mass distributions admits a solution with at most $n-1$ lines, even when every mass distribution is uniform over polynomially many rectangles, and there is no overlap between any two mass distributions.

2 Hardness of approximate SC-Pizza-Sharing

In this section we prove hardness results for $\varepsilon$-SC-Pizza-Sharing. We provide a reduction from $\varepsilon$-Consensus-Halving with $k$-block valuations, which was shown to be PPA-complete in [DFHM22] for any constant $\varepsilon<1/5$ even for $3$-block uniform valuations. Our construction shows that $\varepsilon$-SC-Pizza-Sharing remains PPA-hard even when there is no overlap between any two mass distributions. Notice that the case of non-overlapping mass distributions is the most simple type of an instance, since we can easily reduce it to one where an arbitrarily large number of masses overlap: make “dummy” exact copies of an existing mass distribution. Also, the machinery that we present, combined with the reduction by [FRFGZ18] implies NP-hardness for the decision version of $\varepsilon$-SC-Pizza-Sharing when $\varepsilon$ is a small constant.

We reduce from a general $\varepsilon$-Consensus-Halving instance to an $\varepsilon$-SC-Pizza-Sharing instance, and the idea is to create a mass for each agent. For any $\varepsilon^{\prime}=\frac{1}{\textup{poly}(n)}<\varepsilon$, given an instance $I_{\textsc{CH}}$ of $\varepsilon$-Consensus-Halving with $n$ agents and $k$-block valuations we will show a polynomial time construction to an $(\varepsilon-\varepsilon^{\prime})$-SC-Pizza-Sharing instance $I_{\textsc{SC}}$.

For our construction, we will use the same components as those in the proof of Lemma 4. In particular, let $c_{\max}:=\max_{i\in[n],m\in[k]}c_{im}$, where $c_{im}$ is the value density of agent $i$’s $m$-th block in $I_{\textsc{CH}}$ (and again note that $c_{\max}\geq 1$ since the total valuation of the agent over $$is$1$). Similarly to the aforementioned proof, we will discretize the$$interval of$I_{\textsc{CH}}$in increments of$d:=\frac{1}{\left\lceil n^{2}\cdot c_{\max}\right\rceil}$. Also, let us restate that for any given$j\in[1/d]$, the subinterval$\left[(j-1)\cdot d,j\cdot d\right]$is called$j$-th$d$-block of interval$$in$I_{\textsc{CH}}$.

To simplify the presentation, all the analysis of instance $I_{\textsc{SC}}$ will be for the scaled version of it, that is, in $\left[0,\frac{1}{d}\right]^{2}$. It is easy to verify, though, that by proper re-scaling we can put the instance in $^{2}$ as required. We will be using the same gadgets that were constructed for the proof of Lemma 4, namely the big-tiles, which contain small-tiles. In particular, we have $1/d$ square big-tiles of size $1\times 1$, each of which contains $n$ square small-tiles of size $\frac{1}{n}\times\frac{1}{n}$ on its diagonal. For any $i\in[n]$, $j\in[1/d]$, we denote them by $t_{j}$ and $t_{ij}$, respectively.

In this construction, however, the positioning of big-tiles will be different than that of the aforementioned proof. In particular, we will be placing them on the diagonal of $\left[0,\frac{1}{d}\right]^{2}$ as shown in Figure 4(b). For every agent $i$ we will create a uniform mass distribution $\mu_{i}$ that consists of at most $1/d$ many axis-aligned small-tiles. For each $j\in[1/d]$, the bottom-left corner of big-tile $t_{j}$ is at $\left(j-1,j-1\right)$. In it, each small-tile $t_{ij}$, $i\in[n]$, belonging to mass distribution $\mu_{i}$ has its bottom left corner at $\left(j-1+\frac{i-1}{n},j-1+\frac{i-1}{n}\right)$.

Inside a given big-tile $t_{j}$, the total mass of each small-tile $t_{ij}$ contains total mass (belonging to $\mu_{i}$) of exactly the same total value $v_{ij}$ as that of agent $i$’s $j$-th $d$-block in $I_{\textsc{CH}}$. The shape of that mass is rectangular, and has width $1/n$ and height $v_{ij}\cdot n$. Using identical arguments to those of Lemma 4 we conclude that the total value of the $d$-block fits inside the small tile of size $\frac{1}{n}\times\frac{1}{n}$. Figure 4 depicts our construction.

We will now define how a solution to $I_{\textsc{SC}}$, i.e., an SC-path, is mapped back to a solution of $I_{\textsc{CH}}$, i.e., a set of cuts. This is identical to that of the aforementioned lemma’s translation. In particular, we consider again the big-tiles in sequential order and we add one cut at $j\cdot d$ whenever we find two big-tiles $t_{j}$ and $t_{j+2}$ that belong to different regions. Suppose that, following the aforementioned procedure, the next $I_{\textsc{CH}}$ cut falls at $j\cdot d^{\prime}$ for some $d^{\prime}>d$. If $t_{j}$ belongs to region “$+$” (resp. “$-$”) and $t_{j+2}$ belongs to “$-$” (resp. “$+$”), then the interval $[j\cdot d,j\cdot d^{\prime}]$ gets label “$+$” (resp. “$-$”), and vice versa. This translation obviously takes polynomial time.

Fix a constant $\delta>0$, and some $\varepsilon^{\prime}\in[\frac{2}{n^{r}},\varepsilon)$, where $r\geq 1$ and $\frac{2}{n^{r}}<\varepsilon<1$. Let an SC-path with at most $n-1+n^{1-\delta}$ turns be a solution to $(\varepsilon-\varepsilon^{\prime})$-SC-Pizza-Sharing instance $I_{\textsc{SC}}$. Then we can find in polynomial time a solution to $\varepsilon$-Consensus-Halving instance $I_{\textsc{CH}}$ with at most $n+n^{1-\delta}$ cuts.

The above translation of the SC-path to $I_{\textsc{CH}}$ cuts indicates that each cut introduces a discrepancy between the “$+$” and “$-$” regions of $I_{\textsc{CH}}$, of value at most $c_{\max}\cdot d$ for each valuation $v_{i}$, $i\in[n]$. This results in total discrepancy of $(n+n^{1-\delta})\cdot c_{\max}\cdot d$ for each agent $i$. We now denote by $\mathcal{I}^{+}$ and $\mathcal{I}^{-}$ the regions in $I_{\textsc{CH}}$ which correspond to the regions $R^{+}$ and $R^{-}$ of $I_{\textsc{SC}}$ respectively, induced by the SC-path after disregarding the intersected big-tiles. Then for the discrepancy in the valuation of agent $i$ in $I_{\textsc{CH}}$ we get

where the last inequality is due to the fact that in our reduction we can pick $d\leq\frac{\varepsilon^{\prime}}{2n\cdot c_{\max}}$. This is always possible since, by assumption, $\varepsilon^{\prime}\geq 2/n^{r}$ for some $r\geq 1$, and additionally, according to our reduction, $d$ is required to be at most $\frac{1}{n^{2}\cdot c_{\max}}$. ∎

The above, together with the fact that $\varepsilon$-Consensus-Halving is PPA -hard for any $\varepsilon<1/5$ ([DFHM22]) implies the main theorem of this section.

$\varepsilon$-SC-Pizza-Sharing with $n$ mass distributions is PPA-hard for any constant $\varepsilon<1/5$, even when $n-1+n^{1-\delta}$ turns are allowed in the SC-path for any given constant $\delta>0$, every mass distribution is uniform over polynomially many rectangles, and there is no overlap between any two mass distributions.

Similarly to the case of the decision variant of $\varepsilon$-Straight-Pizza-Sharing (Theorem 6), we can get the following result by reducing from the NP-hard instances of $\varepsilon$-Consensus-Halving for constant $\varepsilon$.

There exists a constant $\varepsilon>0$ for which it is NP-hard to decide if an $\varepsilon$-SC-Pizza-Sharing instance with $n$ mass distributions admits a solution consisting of an SC-path with at most $n-2$ turns, even when every mass distribution is uniform over polynomially many rectangles, and there is no overlap between any two mass distributions.

3 Hardness of discrete Straight-Pizza-Sharing and SC-Pizza-Sharing

In this section, we study the discrete versions of Straight-Pizza-Sharing and SC-Pizza-Sharing.

R^{+} and $R^{-}$ using at most $n$ lines such that for each $i\in[2n]$ it holds that $\left||P_{i}\cap R^{+}|-|P_{i}\cap R^{-}|\right|\leq\varepsilon\cdot|P_{i}|$. A point that is intersected by a line does not belong to any of $R^{+}$, $R^{-}$. Definition 11. For any $n\geq 1$, the problem $\varepsilon$-Discrete-SC-Pizza-Sharing is defined as follows: • Input: $\varepsilon\geq 0$ and $n$ point sets $P_{1},P_{2},\dots,P_{n}$ on $^{2}$. • Output: One of the following. (a) Two points with the same $x$- or $y$-coordinate. (b) A partition of $^{2}$ to $R^{+}$ and $R^{-}$ using a $y$-monotone SC-path with at most $n-1$ turns such that for each $i\in[n]$ it holds that $\left||P_{i}\cap R^{+}|-|P_{i}\cap R^{-}|\right|\leq\varepsilon\cdot|P_{i}|$. A point that is intersected by a line does not belong to any of $R^{+}$, $R^{-}$. Notice that the first kind of allowed output for both problems (Definition 10(a), Definition 11(a)) is a witness that the input points are not in general position or that their $x$- or $y$-coordinates are not unique, respectively, which can be checked in polynomial time. The second kind of output (Definition 10(b), Definition 11(b)) is the one that is interesting and can encode the hard instances studied here. In case the first kind of output does not exist, the other one is guaranteed to exist due to [Sch21] for $\varepsilon$-Discrete-Straight-Pizza-Sharing, while for $\varepsilon$-Discrete-SC-Pizza-Sharing its existence is guaranteed for every $\varepsilon\in$ due to a reduction we present in Section 4.4 which shows containment in PPA.

The definition of $\varepsilon$-Discrete-Straight-Pizza-Sharing is a slightly modified form of the one that appears in [Sch21], where it is referred to as DiscretePizzaCutting. In our definition, we avoid having to “promise” an input of points that are in general position, by allowing as output a witness of an inappropriate input. Furthermore, the definition we present is more general, since it accommodates an approximation factor $\varepsilon$; in particular, for $\varepsilon<\min_{i}\{1/|P_{i}|\}$ we get the definition of the aforementioned paper. Similarly, we define $\varepsilon$-Discrete-SC-Pizza-Sharing, which to the best of our knowledge, has not been stated in previous work. Note that, if the input consists of points that are in general position, in an $\varepsilon$-Discrete-Straight-Pizza-Sharing solution only up to two points are allowed to be intersected by the same line, while in an $\varepsilon$-Discrete-SC-Pizza-Sharing solution only up to two points are allowed to be intersected by the same line segment.

Recall that in $\varepsilon$-SC-Pizza-Sharing we are given $n$ mass distributions, while in $\varepsilon$-Straight-Pizza-Sharing we are given $2n$ mass distributions as input. In Appendix C, we describe a general construction that takes as an input $q\in\{n,2n\}$ mass distributions $\mu_{1},\dots,\mu_{q}$ normalized on $^{2}$, represented by weighted polygons with holes (see Appendix A for the detailed description), and turns it into $q$ sets of points $P_{1},\dots,P_{q}$ on $^{2}$ whose union is in general position and furthermore, they have unique $x$- and $y$-coordinates. We prove that, given a set of $m\leq 2n$ lines or an SC-path of at most $m^{\prime}\leq 2n-1$ turns, that partition $^{2}$ into $R^{+}$ and $R^{-}$ such that $\left||P_{i}\cap R^{+}|-|P_{i}\cap R^{-}|\right|\leq(\varepsilon-\varepsilon^{\prime})\cdot|P_{i}|$, the same lines and SC-path, respectively, separate the mass distributions such that $\left|\mu_{i}(R^{+})-\mu_{i}(R^{-})\right|\leq\varepsilon$.

Let $N\geq 2n$ be the input size of any of our two pizza sharing problems, and let the smallest area triangle in the mass distributions’ triangulation be $\alpha$. For any $\varepsilon^{\prime}<\varepsilon$, where $\varepsilon$ and $\alpha$ are at least inverse polynomial in $N$, the construction results to a polynomial time reduction from $\varepsilon$-Straight-Pizza-Sharing to $(\varepsilon-\varepsilon^{\prime})$-Discrete-Straight-Pizza-Sharing and from $\varepsilon$-SC-Pizza-Sharing to $(\varepsilon-\varepsilon^{\prime})$-Discrete-SC-Pizza-Sharing. The reduction can be performed in time polynomial in the input size and in $1/\alpha$. It consists of two parts: (i) First we “pixelate” the mass distributions finely enough so that they are represented by a sufficiently large number of pixels. This will ensure a high enough “resolution” of the pixelated distributions. (ii) The pixels will then be turned into points, which we have to perturb in order to guarantee they are in general position and with unique coordinates, as required. In particular, in Appendix C, we prove the following.

Let $N$ be the input size of an approximate pizza sharing problem (either $\varepsilon$-Straight-Pizza-Sharing or $\varepsilon$-SC-Pizza-Sharing) whose triangulation has no triangle with area less than $\alpha>0$. Also, let $\varepsilon^{\prime}\in\left[\frac{6}{N^{c}},\varepsilon\right)$, where $c>0$ is a fixed constant, and $\frac{6}{N^{c}}<\varepsilon<1$. Then, the instance can be reduced in time $\textup{poly}(N,1/\alpha)$ to its approximate discrete version, that is, $(\varepsilon-\varepsilon^{\prime})$-Discrete-Straight-Pizza-Sharing or $(\varepsilon-\varepsilon^{\prime})$-Discrete-SC-Pizza-Sharing.

Given Theorem 5 and Theorem 8, and since their instances are constructed such that $\alpha$ is an at least inverse polynomial function of the input size, the above lemma implies the following hardness results.

$\varepsilon$-Discrete-Straight-Pizza-Sharing with $2n$ point sets is PPA-hard for any constant $\varepsilon<1/5$, even when $n+n^{1-\delta}$ lines are allowed for any given constant $\delta>0$.

$\varepsilon$-Discrete-SC-Pizza-Sharing with $n$ point sets is PPA-hard for any constant $\varepsilon<1/5$, even when $n-1+n^{1-\delta}$ turns are allowed in the SC-path for any given constant $\delta>0$.

We note that PPA-hardness for $\varepsilon$-Discrete-Straight-Pizza-Sharing was so far known only for any $\varepsilon\in\left[0,\min_{i}\{1/|P_{i}|\}\right)$ (which is equivalent to $\varepsilon=0$), due to [Sch21]. Since, in the aforementioned paper’s constructions, $\min_{i}\{1/|P_{i}|\}\in O(1/\textup{poly}(N))$, our result strengthens the hardness of the problem significantly.

Lemma 12 is general enough that allows us to derive NP-hardness results for the decision variants of the two discrete versions of the pizza sharing problems. If we ask for a solution with at most $n-1$ straight lines or $n-2$ turns in $(\varepsilon-\varepsilon^{\prime})$-Discrete-Straight-Pizza-Sharing and $(\varepsilon-\varepsilon^{\prime})$-Discrete-SC-Pizza-Sharing, respectively, then we can easily reduce to them from the instances of Theorem 6 and Theorem 9, picking $\varepsilon^{\prime}$ to be some inverse polynomial function of $N$, e.g., $\varepsilon^{\prime}=1/N$. In particular, we get the following.

There exists a constant $\varepsilon>0$ for which it is NP-hard to decide whether a solution of $\varepsilon$-Discrete-Straight-Pizza-Sharing with $2n$ point sets and at most $n-1$ lines exists.

There exists a constant $\varepsilon>0$ for which it is NP-hard to decide whether a solution of $\varepsilon$-Discrete-SC-Pizza-Sharing with $n$ point sets and an SC-path with at most $n-2$ turns exists.

4 Hardness of exact SC-Pizza-Sharing

In this section, we show hardness results for exact SC-Pizza-Sharing. We prove that solving SC-Pizza-Sharing is FIXP-hard and that deciding whether there exists a solution for SC-Pizza-Sharing with fewer than $n-1$ turns is ETR-hard.

As mentioned earlier, computing an exact solution of a FIXP-hard problem may require computing an irrational number. To showcase this for SC-Pizza-Sharing, consider the following simple instance. Let us have a single mass distribution in the shape of a right-angled triangle, whose corners are on $(0,1)$, $(1,1)$, and $(1,0)$. It is normalised, i.e., its total mass is $1$, therefore its weight is $2$. An exact solution of SC-Pizza-Sharing is either a horizontal or a vertical straight line (with turns), which cuts the triangle such that each half-space has half of the mass, that is, $1/2$. One can easily check that the solution is either the horizontal line $y=\sqrt{2}/2$, or the vertical line $x=\sqrt{2}/2$.

We provide a main reduction from (exact) Consensus-Halving to (exact) SC-Pizza-Sharing, whose gadgets are then employed to show the ETR-hardness of the decision version. This time, as a starting point, we will use the instances of Consensus-Halving produced in [DFMS21], which we will denote by $I_{\textsc{CH}}^{\textsc{DFMS}}$. When clear from context, by $I_{\textsc{CH}}^{\textsc{DFMS}}$ we will denote a particular instance of the aforementioned family. We note that here the input consists of sets of points, i.e., we describe polygons by their vertices. For a detailed description of the input representation, see Appendix A. In [DFMS21], the FIXP-hard family of instances we reduce from has as input $n$ arithmetic circuits capturing the cumulative valuation of $n$ agents on $$, which were piece-wise polynomials of maximum degree 2. However, since their (density) valuation functions are piece-wise linear, the input of SC-Pizza-Sharing suffices to consist of only rectangles and triangles, and no other shape. Therefore, there is no need for extra translation of the input of Consensus-Halving to the input of SC-Pizza-Sharing.

The reduction. Here we show the main reduction, which will conclude with the proof that finding an exact solution to SC-Pizza-Sharing is FIXP-hard, and then will be used to show that its decision version is ETR-hard. We reduce from a Consensus-Halving instance $I_{\textsc{CH}}^{\textsc{DFMS}}$ with $n$ agents and $k$-block-triangle valuations to an SC-Pizza-Sharing instance $I_{\textsc{SC}}$ with $n$ mass distributions. When requesting a solution in $I_{\textsc{SC}}$ with at most $n-1$ turns in the SC-path, then we get FIXP-hardness, while when requesting to decide if $I_{\textsc{SC}}$ is solvable with $n-2$ turns, then we get ETR-hardness. Both of these results are due to [DFMS21], and hold even for $6$-block-triangle valuations.

As in our previous proofs, for ease of presentation, the space of the instance is inflated to $\left[0,2n(k+1)\right]^{2}$, and by scaling the construction down to $^{2}$ the correctness is attained. The key difference between this reduction and the previous reductions on the approximate versions is that the starting point of the reduction, i.e., instance $I_{\textsc{CH}}^{\textsc{DFMS}}$, besides rectangular, also contains triangular-shaped valuations for agents. More specifically, all of the following hold:

the valuation function of every agent is 4-block-triangle, or 6-block;

every triangle has height 2 and belongs to exactly one interval of interest of the form $[a,a+1]$;

for every agent $i\in[n]$ there exists an interval $[a_{i},b_{i}]$ that contains more than half of their total valuation, and in addition, for every $i^{\prime}\neq i$ we have $(a_{i},b_{i})\cap(a_{i^{\prime}},b_{i^{\prime}})=\emptyset$.

Also, in this reduction, the resulting SC-Pizza-Sharing instances will contain weighted mass distributions (see definition in Section 2).

For each subinterval $j\in[m]$ of $I_{\textsc{CH}}$, we will construct a tile $t_{j}$ of size $1\times 1$. Let the total value of agent $i$ in the $j$-th interval of $I_{\textsc{CH}}$ be $v_{ij}$. If for agent $i$ the valuation in the $j$-th interval has constant density (i.e., the total valuation has a rectangular shape), then we create a square mass that belongs to $\mu_{i}$, of size $1\times 1$ inside $t_{j}$, with weight $w_{ij}=v_{ij}$. If her valuation has linear density (i.e., the total valuation has a triangular shape), then we create a mass of right-triangular shape that belongs to $\mu_{i}$, with two of its sides being of length $1$ and touching the top and right sides of $t_{j}$, while its right angle touches the top-right corner of $t_{j}$, and its weight is $w_{ij}=2$. Observe that, for any given $i\in[n]$, the total value of a subinterval in $I_{\textsc{CH}}$ is equal to its total mass in the corresponding tile. Finally, we place the tiles sequentially in a diagonal manner, i.e., each tile $t_{j}$ is axis-aligned and placed with its bottom-left corner at point $(j,j)$. See Figure 5 and Figure 6 for a depiction.

Now we need to show how an exact solution of $I_{\textsc{SC}}$, that is, an SC-path with $n-1$ many turns is mapped back to a solution of $I_{\textsc{CH}}$ with $n$ cuts. Consider the first tile $t_{j}$ that is intersected by the SC-path, resulting in a part of it belonging to $R^{+}$ and the rest of it to $R^{-}$. Let $a_{j}^{+}:=\mu_{i}(t_{j}\cap R^{+})$, and by our definition above, it is implied that $\mu_{i}(t_{j}\cap R^{-})=v_{ij}-a_{j}^{+}$. We then place a cut in the $j$-th subinterval of $I_{\textsc{CH}}$ at point $x^{\prime}_{j}=x_{j}+(x_{j+1}-x_{j})\cdot\frac{a_{j}^{+}}{v_{ij}}$, and label the interval $[0,x^{\prime}_{j}]$ with “$+$”, and the interval $[x^{\prime}_{j},x_{j+1}]$ with “$-$”. Next, consider the second tile $t_{j^{\prime}}$ that is intersected by the SC-path, resulting in a part of it belonging to $R^{+}$ and the rest of it to $R^{-}$. For this tile, we will place a cut in the $j^{\prime}$-th subinterval of $I_{\textsc{CH}}$ at point $x^{\prime}_{j^{\prime}}=x_{j^{\prime}}+(x_{j^{\prime}+1}-x_{j^{\prime}})\cdot\frac{v_{ij^{\prime}}-a_{j^{\prime}}^{+}}{v_{ij^{\prime}}}$, and label the interval $[x_{j+1},x^{\prime}_{j^{\prime}}]$ with “$-$”, and the interval $[x^{\prime}_{j^{\prime}},x_{j^{\prime}+1}]$ with “$+$”. We continue in this fashion with the translation of the SC-path into cuts and labels of $I_{\textsc{CH}}$, where, the $r$-th in order intersected tile will be of the kind $t_{j}$ if $r$ is odd, and of the kind $t_{j^{\prime}}$ if $r$ is even. This will result in a set of cuts that define regions with alternating signs.

It remains to prove that this is a solution to $I_{\textsc{CH}}$. To do this, we will use the following crucial observation.

In any solution of $I_{\textsc{SC}}$ created by $I_{\textsc{CH}}^{\textsc{DFMS}}$, there can be no turn inside a tile.

The truth of the statement can become apparent if one considers Item 3 of the above facts on $I_{\textsc{CH}}^{\textsc{DFMS}}$, together with the fact that the endpoints of each $[a_{i},b_{i}]$ are points of interest. It is implied then, that in any of the $I_{\textsc{CH}}^{\textsc{DFMS}}$ solutions, there needs to be at least one cut in each interval $[a_{i},b_{i}]$ for each $i\in[n]$. And since we are allowed to draw at most $n$ cuts, there will be a single cut in each of those intervals. Also, due to the fact that $a_{i},b_{i}$ are points of interest, each cut in $[a_{i},b_{i}]$ belongs to a different subinterval, and therefore, there will be exactly $n$ cuts in $n$ distinct subintervals. Focusing now on our $I_{\textsc{SC}}$ construction, the SC-path with $n-1$ turns consists of a total of $n$ horizontal and vertical line segments. If any of those does not intersect any tile, then this SC-path will correspond to a set of at most $n-1$ cuts in $I_{\textsc{CH}}$, which cannot be a solution. Therefore, every line segment intersects some tile.

Notice that, due to the diagonal placement of tiles, any SC-path that is a solution has to be $x$-monotone and $y$-monotone, i.e., to have a “staircase” form. Also, this diagonal placement of tiles dictates that, if there was a turn of the SC inside a tile, then two line segments are used to intersect it instead of one. This means that at most $n-1$ tiles will be intersected, and therefore this translates to a set of at most $n-1$ cuts in $I_{\textsc{CH}}$, which cannot be a solution. ∎

Put differently, having a turn inside a tile would be a “waste”, and in our instances, all turns are needed in order for a solution to exist.

Let us now focus on a tile $t_{r}$. We consider two cases that can appear in $I_{\textsc{CH}}^{\textsc{DFMS}}$:

For all $i\in[n]$, $v_{i}$ is nonnegative constant in the $r$-th subinterval. Let $t_{r}$ be a tile as the aforementioned $t_{j}$. Now notice that the “$+$” part of the $j$-th subinterval equals $v_{ij}\cdot\frac{x^{\prime}_{j}-x_{j}}{x_{j+1}-x_{j}}=a_{j}^{+}=\mu_{i}(t_{j}\cap R^{+})$, and the “$-$” part equals $v_{ij}\cdot\frac{x_{j+1}-x^{\prime}_{j}}{x_{j+1}-x_{j}}=v_{ij}-a_{j}^{+}=\mu_{i}(t_{j}\cap R^{-})$. If on the other hand, $t_{r}$ is a tile as the aforementioned $t_{j^{\prime}}$, it is again easy to see that, for every $i\in[n]$, the total “$+$” and “$-$” parts of $t_{j^{\prime}}$ have mass equal to the corresponding “$+$” and “$-$” parts of the $j^{\prime}$-th subinterval.

There is an $i\in[n]$ such that $v_{i}$ is linear in the $r$-th subinterval. Due to the previous case, for all $i^{\prime}\neq i$, the total “$+$” and “$-$” parts of the tile have mass equal to the corresponding “$+$” and “$-$” parts of the corresponding subinterval in $I_{\textsc{CH}}$. For $i$, due to the structure of $I_{\textsc{CH}}^{\textsc{DFMS}}$, the slope of $v_{i}$ is $2$, and the length of the subinterval is $1$, therefore we have $v_{ij}=1$. Let $t_{r}$ be a tile as the aforementioned $t_{j}$, and without loss of generality, let the SC-path intersect it horizontally at $j+s$ (y-coordinate), and its bottom part is labelled “$+$”, while the top part is labelled “$-$”. According to the previous case, a cut should be placed at point $x^{\prime}_{j}=x_{j}+s$ in the $j$-th subinterval, and its part to the left should be labelled “$+$” while the one to its right should be labelled “$-$”. Now notice that for agent $i$ the “$+$” part of the $j$-th subinterval equals $\frac{s\cdot 2s}{2}=s^{2}$, while her “$+$” mass in $t_{j}$ is $\frac{s\cdot s}{2}\cdot w_{ij}=s^{2}$, since $w_{ij}=2$. Similarly, both the “$-$” parts of $I_{\textsc{CH}}$ and $I_{\textsc{SC}}$ are equal in the subinterval and the tile, respectively. Finally, if, $t_{r}$ is a tile as the aforementioned $t_{j^{\prime}}$, it is again easy to see that the total “$+$” and “$-$” parts of $t_{j^{\prime}}$ have mass equal to the corresponding “$+$” and “$-$” parts of the $j^{\prime}$-th subinterval.

The above analysis shows that, for any $i\in[n]$, in each individual tile the total “$+$” mass is equal to the total “$+$” value of the corresponding subinterval. Therefore, given a solution to $I_{\textsc{SC}}$ where the total mass of $R^{+}$ will equal that of $R^{-}$ for every $i\in[n]$, the induced cuts on $I_{\textsc{CH}}$ constitute a solution. Finally, due to the FIXP-hardness of exact Consensus-Halving shown in [DFMS21], we get the following.

SC-Pizza-Sharing is FIXP-hard even when every mass distribution is uniform, consists of at most six pieces that can be unit-squares or right-angled triangles, and have overlap at most 3.

We can also show that deciding whether there exists an exact SC-Pizza-Sharing solution with $n-2$ turns is ETR-hard. To show this, we will use a result of [DFMS21], where it was shown that deciding whether there exists an exact Consensus-Halving solution with $n$ agents and $n-1$ cuts is ETR-hard. We give a reduction from this version of Consensus-Halving to the decision problem for SC-Pizza-Sharing. The reduction uses the same ideas that we presented for the FIXP-hardness reduction. The full details are in Appendix D, where the following theorem is shown.

It is ETR-hard to decide if an exact SC-Pizza-Sharing instance admits a solution with a SC-path with at most $n-2$ turns, even when every mass distribution consists of at most six pieces that can be unit-squares or right-angled triangles, and have overlap at most 3.