# pizza_sharing_is_ppahard__ede7a806.pdf Pizza Sharing Is PPA-Hard Argyrios Deligkas*1, John Fearnley*2, Themistoklis Melissourgos3 1Royal Holloway University of London, UK, 2University of Liverpool, UK, 3University of Essex, UK argyrios.deligkas@rhul.ac.uk, john.fearnley@liverpool.ac.uk, themistoklis.melissourgos@essex.ac.uk 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 PPAhard 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 PPAhardness 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. Introduction Mass partition problems ask us to fairly divide measurable objects that are embedded into Euclidean space (Rold an Pensado and Sober on 2020). 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 2𝑛two-dimensional masses in the plane, and we are asked to find 𝑛straight lines that simultaneously bisect all of the masses. See Figure 1(π‘Ž) 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 𝑛= 2 (Barba, Pilz, and Schnider 2019), and this was subsequently extended to show existence for all 𝑛(Hubard and Karasev 2020). Another related problem is the square-cut pizza sharing. In this problem, there are 𝑛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 *These authors contributed equally. Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Figure 1: Partitions of the plane to 𝑅+ and 𝑅 (shaded and non-shaded areas respectively). Subfigure (a): a straight-line partition with four lines. Subfigure (b): a square-cut-path with six turns. Observe that the path is not 𝑦-monotone. Subfigure (c): a 𝑦-monotone square-cut-path with four turns. Figure 1(𝑏) and 1(𝑐) 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(𝑐) is still considered to be a single square-cut. It has been shown by (Karasev, Rold an-Pensado, and Sober on 2016) that, given 𝑛masses, there always exists a square-cut-path (termed SC-path) which makes at most 𝑛 1 turns and simultaneously bisects all of the masses. This holds even if the SC-path is required to be 𝑦-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 𝑛agents (Chambers 2005; Segal-Halevi et al. 2017; Segal Halevi et al. 2020; Elkind, Segal-Halevi, and Suksompong 2021; Aumann and Dombb 2015; Iyer and Huhns 2009; Husseinov 2011). The first popular appearance of such problems in a mathematical description was done by (Steinhaus 1948), 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 (Simmons and Su 2003), to redistricting (Landau, Reid, and Yershov 2009; Landau and Su 2014). The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) Consensus halving is a problem that asks us to split a onedimensional resource into two parts such that 𝑛agents have equal value in both parts. Here, we study the same fairness criterion for 𝑛agents, but for a two-dimensional resource. One can see that when we have the same fairness criterion at hand for any π‘˜-dimensional resource, π‘˜ 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 𝑛/2 disjoint stripes of land. 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. Due to space restrictions, we omit full proofs of our results and illustratory figures that are provided in the full version of the paper (Deligkas, Fearnley, and Melissourgos 2020). 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 (Filos Ratsikas and Goldberg 2018, 2019) that the consensus halving problem, the ham sandwich problem, and the wellknown necklace splitting problem are all PPA-complete. More generally, PPA captures all problems whose solution is verifiable in polynomial time and is guaranteed by the Borsuk-Ulam theorem. Finding an approximate solution to a Borsuk-Ulam function, or finding an exact solution to a linear Borsuk-Ulam function are both known to be PPA-complete problems (Papadimitriou 1994; Deligkas et al. 2021). The existence of solutions to the ham sandwich problem, the necklace splitting problem, and indeed the square-cut pizza sharing problem can all be proved via the Borsuk-Ulam theorem1. 1It has also been shown that the Borsuk-Ulam theorem is equivalent to the ham sandwich theorem which states that the volumes of any 𝑛compact sets in R𝑛can always be simultaneously bisected by an (𝑛 1)-dimensional hyperplane (S. and Saha 2017). Theorem 1 (Borsuk-Ulam). Let 𝑓: 𝑆𝑑 R𝑑be a continuous function, where 𝑆𝑑is a 𝑑-dimensional sphere. Then, there exists an π‘₯ 𝑆𝑑such that 𝑓(π‘₯) = 𝑓( π‘₯). 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 (Deligkas et al. 2021) 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. 2 Our contribution. We study the computational complexity of the straight-cut and square-cut pizza sharing problems, and we specifically study the case where all masses are unions of weighted polygons. We show that it is PPAhard to find approximate solutions of either problem. All of our hardness results are summarized in Tables 1 and 2. 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 (Filos-Ratsikas et al. 2020) and necklace splitting (Filos-Ratsikas and Goldberg 2019). Here we show the first known PPA-hardness result for a natural two-dimensional problem. 3 For the straight-cut problem, we show that it is PPA-hard to find an 1/poly(𝑛)-approximate solution to the problem and PPAD-hard to find a 𝑐-approximate solution for some constant 𝑐. Both hardness results hold even when 𝑛+ 𝑛1 𝛿 lines are permitted, for constant 𝛿> 0, and even when each mass distribution is a union of polynomially-many nonoverlapping squares. For the square-cut problem, we show that finding a square cut with 𝑛 1 turns that πœ€-approximately bisects 𝑛mass distributions is a PPA-complete problem. In fact, we show three different hardness results for the approximate problem. Our main hardness result shows hardness for πœ€ = 1/poly(𝑛), and we are able to show that it is PPA-hard even to find an SC-path with 𝑛+𝑛1 𝛿turns, where 𝛿> 0 is a constant. By making adjustments to the result above, we are able to extend the hardness to the case where all of the polygons are axis-aligned unweighted non-overlapping squares. Finally, we are able to show a hardness result for constant πœ€, but in this case the hardness is PPAD-hardness. We remark that our reductions from consensus halving to the pizza sharing problems are such that the additive error in the solution quality is only weakened by at most an additional inverse polynomial. This is fact automatically implies an improvement of the PPA-hardness for the pizza sharing 2For a recent improvement towards showing BU-hardness of exact consensus halving see (Batziou, Hansen, and HΓΈgh 2021). 3Shortly after the appearance of our result, (Schnider 2021) proved that the discrete version of straight-cut pizza sharing where each mass is represented by equal-weight points is PPA-complete. Hardness πœ€ Lines Pieces Overlap Theorem PPA 1 poly(𝑛) 𝑛+ 𝑛1 𝛿 poly(𝑛) 1 5 PPAD 𝑐 𝑛+ 𝑛1 𝛿 poly(𝑛) 1 6 Table 1: A summary of our hardness results for πœ€STRAIGHT-PIZZA-SHARING. Here, 𝑐and 𝛿> 0 are absolute constants. Lines refers to the number of lines we allow. Pieces refers to the maximum number of distinct polygons that define every mass distribution. Overlap denotes the number of different mass distributions that can contain any point of [0, 1]2. problems to πœ€< 1/5 due to a recent result on the hardness of consensus halving (Deligkas et al. 2022). 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 𝑛 1 turns that exactly bisects 𝑛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 this result, 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 (Karasev, Rold an-Pensado, and Sober on 2016). Finally, we study the decision version of the square-cut problem. While a solution to the problem is guaranteed to exist for cuts that make 𝑛 1 turns, this is not the case if only 𝑛 2 turns are allowed. We show that deciding whether there exists an approximate solution that makes at most 𝑛 2 turns is NP-complete, and deciding whether there is an exact solution that makes at most 𝑛 2 turns is ETR-complete. From a technical point of view, our containment results are shown by directly reducing the square-cut pizza sharing problem to the BORSUK-ULAM problem. Our hardness results are obtained by reducing from the consensus halving problem, which was one of the first fair-division problems shown to be PPA-complete by (Filos-Ratsikas and Goldberg 2018). We remark that, if in the future, consensus halving is shown to be BU-complete under block and triangle valuations for the agents, then our work implies that exact squarecut pizza sharing is BU-complete. Further related work. Since mass partitions lie in the intersection of topology, discrete geometry, and computer science there are several surveys on the topic; (Blagojevi c et al. 2018; De Loera et al. 2019; MatouΛ‡sek 2008; Λ‡Zivaljevi c 2017) focus on the topological point of view, while (Agarwal, Erickson et al. 1999; Edelsbrunner 2012; Kaneko and Kano 2003; Kano and Urrutia 2020; Matousek 2013) focus on computational aspects. Consensus halving (Simmons and Su 2003) is the mass partition problem that received the majority of attention in Economics and Computation so far (Deligkas, Filos-Ratsikas, and Hollender 2020; Filos Ratsikas et al. 2018; Filos-Ratsikas and Goldberg 2019; Filos-Ratsikas et al. 2020, 2021). Hardness πœ€ Turns Pieces Overlap Theorem PPA 1 poly(𝑛) 𝑛+ 𝑛1 𝛿 poly(𝑛) 𝑂(𝑛) 8 PPAD 𝑐 𝑛+ 𝑛1 𝛿 6 3 9 NP 1 poly(𝑛) 𝑛 2 6 3 10 PPA 1 poly(𝑛) 𝑛+ 𝑛1 𝛿 poly(𝑛) 1 11 FIXP 0 𝑛 1 6 3 13 ETR 0 𝑛 2 6 3 14 Table 2: A summary of our hardness results for πœ€-SCPIZZA-SHARING. Here, 𝑐and 𝛿> 0 are absolute constants. Turns denotes the maximum number of turns the path can have. Pieces refers to the maximum number of distinct polygons that define every mass distribution. Overlap denotes the number of different mass distributions that can contain any point of [0, 1]2. Preliminaries Mass distributions. A mass distribution πœ‡on [0, 1]2 is a measure on the plane such that all open subsets of [0, 1]2 are measurable, 0 < πœ‡ ( [0, 1]2) < , and πœ‡(𝑆) = 0 for every subset of [0, 1]2 with dimension lower than 2. A mass distribution πœ‡is finite-separable, or simply separable, if it can be decomposed into a finite set of non-overlapping areas π‘Ž1, π‘Ž2, . . . , π‘Žπ‘‘such that πœ‡([0, 1]2) = 𝑑 𝑗=1 πœ‡(π‘Žπ‘—). In addition, a separable mass distribution πœ‡is piece-wise uniform, if for every 𝑗and every 𝑆 π‘Žπ‘—it holds that πœ‡(π‘Žπ‘— 𝑆) = 𝑐𝑗 area(π‘Žπ‘— 𝑆) for some 𝑐𝑗> 0 independent of 𝑆. When additionally 𝑐𝑗= 1 for all 𝑗 [𝑑] then the mass distribution is called uniform. Finally, a mass distribution is normalised if πœ‡([0, 1]2) = 1. The support of mass distribution 𝑖, denoted by 𝑠𝑒𝑝𝑝(𝑖), is the area 𝐴𝑖 [0, 1]2 which has the property that for every 𝑆 𝐴𝑖with non-zero Lebesgue measure we have πœ‡π‘–(𝑆) > 0. Let 𝑁:= {𝐼 [𝑛] : 𝑖 𝐼𝑠𝑒𝑝𝑝(𝑖) = }. A set of mass distributions πœ‡1, . . . , πœ‡π‘›has overlap π‘˜if max𝐼 𝑁|𝐼| = π‘˜. Mass distributions can be categorized according to their shape as well. So, a separable mass distribution is a: 𝑑-polygon, if it can be decomposed into 𝑑nonoverlapping polygons 𝑝1, 𝑝2, . . . , 𝑝𝑑; 𝑑-β„“-square, if it can be decomposed into 𝑑squares 𝑠1, 𝑠2, . . . , 𝑠𝑑each of edge-length β„“, when β„“= 1 we say that it is a unit-square. Set of straight-cuts. A set of straight cuts (or lines) defines subdivisions of the plane 𝑅. Figure 1(a) shows an example of a set of straight-cuts. Each line creates two half-spaces, and arbitrarily assigns number 0 to one and 1 to the other. A subdivision of 𝑅is labeled + (and belongs to 𝑅+) if its parity is odd (according to the labels given to the halfspaces) and (and belongs to 𝑅 ) 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,c) shows two examples of SC-paths. A turn of the path is where a horizontal segment meets with a vertical segment. An SC-path is 𝑦-monotone if all of its horizontal segments are monotone with respect to the 𝑦axis. Any SCpath partitions the plane into two regions, that we call 𝑅+ and 𝑅 . Pizza sharing. A set of lines (resp. a SC path) πœ€-bisects a mass distribution πœ‡, if |πœ‡(𝑅+) πœ‡(𝑅 )| πœ€. It simultaneously πœ€-bisects a set of mass distributions 𝑀if |πœ‡π‘–(𝑅+) πœ‡π‘–(𝑅 )| πœ€for every πœ‡π‘– 𝑀. Definition 2. For any 𝑛 1, the problem πœ€-STRAIGHTPIZZA-SHARING is defined as follows: Input: πœ€ 0 and mass distributions πœ‡1, πœ‡2, . . . , πœ‡2𝑛 on [0, 1]2. Output: A partition of [0, 1]2 to 𝑅+ and 𝑅 using at most 𝑛lines such that for each mass distribution 𝑖it holds that |πœ‡π‘–(𝑅+) πœ‡π‘–(𝑅 )| πœ€. In particular, the mass distributions are weighted polygons with holes. Definition 3. For any 𝑛 1, the problem πœ€-SC-PIZZASHARING is defined as follows: Input: πœ€ 0 and mass distributions πœ‡1, πœ‡2, . . . , πœ‡π‘› on [0, 1]2. Output: A partition of [0, 1]2 to 𝑅+ and 𝑅 using a 𝑦-monotone SC-path with at most 𝑛 1 turns such that for each mass distribution 𝑖it holds that |πœ‡π‘–(𝑅+) πœ‡π‘–(𝑅 )| πœ€. In particular, the mass distributions are weighted polygons with holes. (Karasev, Rold an-Pensado, and Sober on 2016) proved that πœ€-SC-PIZZA-SHARING always admits a solution for arbitrary continuous measures with respect to the Lebesgue measure, and for any πœ€ 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. We also study the decision version of the problem, in which we ask whether we can find a solution with π‘˜turns, where π‘˜< 𝑛 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 πœ€-CONSENSUS-HALVING problem, there is a set of 𝑛agents with valuation functions 𝑣𝑖over the interval [0, 1], and the goal is to find a partition of the interval into subintervals labelled either + or , using at most 𝑛cuts. This partition should satisfy that for every agent 𝑖, the total value for the union of subintervals ℐ+ labelled + and the total value for the union of subintervals ℐ labelled is the same up to πœ€, i.e., |𝑣𝑖(ℐ+) 𝑣𝑖(ℐ )| πœ€. We will consider the following types for a valuation function 𝑣𝑖: π‘˜-block. 𝑣𝑖 can be decomposed into at most π‘˜ non-overlapping (but possibly adjacent) intervals [π‘Žβ„“ 𝑖1, π‘Žπ‘Ÿ 𝑖1], . . . , [π‘Žβ„“ π‘–π‘˜, π‘Žπ‘Ÿ π‘–π‘˜] where interval [π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗] has density 𝑐𝑖𝑗 and 0 otherwise. So, 𝑣𝑖([π‘Žβ„“ 𝑖𝑗, π‘₯]) = (π‘₯ π‘Žβ„“ 𝑖𝑗) 𝑐𝑖𝑗for every π‘₯ [π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗] and 𝑣𝑖([0, 1]) = 𝑗𝑣𝑖([π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗]) = 1. 2-block uniform. 𝑣𝑖is two-block and the density of every interval is 𝑐𝑖. π‘˜-block-triangle. 𝑣𝑖is the union of a π‘˜-block valuation function and an extra interval [π‘Žβ„“ 𝑖1, π‘Žπ‘Ÿ 𝑖1], where 𝑣𝑖([π‘Žβ„“ 𝑖1, π‘₯]) = (π‘Žβ„“ 𝑖1 π‘₯)2 for every π‘₯ [π‘Žβ„“ 𝑖1, π‘Žπ‘Ÿ 𝑖1] and (π‘Žβ„“ 𝑖1, π‘Žπ‘Ÿ 𝑖1) [π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗] = 0 for every 𝑗 [π‘˜]. Complexity classes. πœ€-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 by (Megiddo and Papadimitriou 1991), 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 1994), captures problems whose totality is guaranteed by the parity argument on undirected graphs. The complexity class PPAD PPA is the subclass of PPA containing all problems whose totality is guaranteed by the parity argument on directed graphs. We will show hardness and completeness results for these classes by reducing from the consensus halving problem, which is discussed below. The complexity class ETR consists of all decision problems that can be formulated in the existential theory of the reals (MatouΛ‡sek 2014; Schaefer 2009). It is known that NP ETR PSPACE (Canny 1988), 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. Hardness Results for PIZZA-SHARING Here we show all hardness results regarding the exact and approximate versions of our pizza sharing problems. We first provide sketches of the hardness reductions for πœ€STRAIGHT-PIZZA-SHARING, and consequently, for πœ€-SCPIZZA-SHARING and exact SC-PIZZA-SHARING. Hardness of πœ€-STRAIGHT-PIZZA-SHARING In this section we sketch the proof of the PPA-hardness for πœ€-STRAIGHT-PIZZA-SHARING when πœ€= 1 poly(𝑛). We prove our result via a reduction from πœ€-CONSENSUS-HALVING with 2-block uniform valuations. In addition, we explain how to modify our reduction so we can get PPAD-hardness for πœ€-STRAIGHT-PIZZA-SHARING for a constant πœ€> 0. Reduction. We reduce from CONSENSUS-HALVING, where for every agent we create a mass. Firstly, we finely discretize the [0, 1] interval into blocks and we place the blocks on 𝑦= π‘₯2, where π‘₯ 0. This guarantees that every line can cut this bended interval at most twice and in addition the part of each mass that is in 𝑅+ is almost the same as value of the corresponding agent for the piece of [0, 1] labelled with + . Next we show how to construct an instance 𝐼𝑃of (πœ€ πœ€ )-STRAIGHT-PIZZA-SHARING, for any πœ€ = 1 poly(𝑛) < πœ€, given an instance 𝐼𝐢𝐻of πœ€-CONSENSUSHALVING with 2𝑛agents with 2-block uniform valuations. Let 𝑐max := max𝑖 [2𝑛] 𝑐𝑖, where 𝑐𝑖is the value density of agent 𝑖 [2𝑛] in 𝐼𝐢𝐻. In what follows, it will help us to think of the interval [0, 1] in 𝐼𝐢𝐻as being discretized in increments of some 𝑑 1 4 𝑛2 𝑐max . For every agent 𝑖 [2𝑛] the starting or finishing position of the two blocks of positive density in the valuation function of each, namely numbers {π‘Žβ„“ 𝑖1, π‘Žπ‘Ÿ 𝑖1, π‘Žβ„“ 𝑖2, π‘Žπ‘Ÿ 𝑖2} are rational since they are part of the problem s input. We refer to the subinterval [(𝑗 1) 𝑑, 𝑗 𝑑] as the 𝑗-th 𝑑-block of interval [0, 1] in 𝐼𝐢𝐻. We now describe the instance 𝐼𝑃. For ease of presentation the space of the instance is inflated to [ 0, ( 6 𝑑2 ) 2 + 1 ] 2 , but by scaling the construction down, the results are attained. We consider two kinds of square tiles; 1/𝑑large tiles of size 1 1, each of which contains 2𝑛smaller square tiles of size 1 2𝑛 1 2𝑛on its diagonal. We will call the former type big-tile and denote it by 𝑑𝑗and the latter one small-tile and denote it by 𝑑𝑖,𝑗for some 𝑖 [2𝑛], 𝑗 [1/𝑑]. The centers of consecutive big-tiles are positioned with 6 𝑑2 distance apart in the π‘₯-axis. For 𝑗 [1/𝑑] we define 𝑠𝑗= 6 𝑑2 𝑗. For every agent 𝑖 [2𝑛] we will create a uniform mass distribution πœ‡π‘–that consists of at most 1/𝑑many axisaligned small-tiles. Each big-tile 𝑑𝑗is centered at ( 𝑠𝑗, 𝑠2 𝑗 ) while, in it, each small-tile 𝑑𝑖𝑗belonging to mass distribution πœ‡π‘–has its bottom left corner at ( 𝑠𝑗+ 𝑖 1 2𝑛, 𝑠2 𝑗+ 𝑖 1 2𝑛 ) . Each small-tile 𝑑𝑖𝑗contains a rectangle mass (that belongs to πœ‡π‘–) of size 1 2𝑛 (𝑑 2𝑛 𝑐𝑖 𝑇𝑖𝑗), where 𝑇𝑖𝑗= 0 if the density is zero in the 𝑗-th 𝑑-block of agent 𝑖in 𝐼𝐢𝐻, and 𝑇𝑖𝑗= 1 otherwise. Lemma 4. Let β„’= {β„“1, . . . , ℓ𝑛+𝑛1 𝛿} be a set of lines. If β„’is a solution for (πœ€ πœ€ )-STRAIGHT-PIZZA-SHARING instance 𝐼𝑃for some πœ€ [ 1 π‘›π‘Ÿ, πœ€), where π‘Ÿ 1, then we can find in polynomial time a solution for πœ€-CONSENSUSHALVING instance 𝐼𝐢𝐻with 2(𝑛+ 𝑛1 𝛿) cuts for any constant 𝛿> 0. Theorem 5. πœ€-STRAIGHT-PIZZA-SHARING is PPA-hard for πœ€= 1 poly(𝑛) even when 𝑛+ 𝑛1 𝛿lines are allowed for any given constant 𝛿> 0, every mass distribution is uniform over polynomially many squares, and there is no overlap between any two mass distributions. In addition to the result above, we can derive PPAD hardness if we reduce from the instances of CONSENSUSHALVING from (Filos-Ratsikas et al. 2018) for constant πœ€. The construction and the proof follow exactly the same lines as the one above. The only difference is that this time the square associated to mass πœ‡π‘–in tile 𝑑𝑗will be weighted by the density of the value of the agent for the 𝑗th 𝑑-block. Then, the proof of correctness of the following theorem is verbatim as the proof of Lemma 4. Theorem 6. πœ€-STRAIGHT-PIZZA-SHARING is PPAD-hard for a constant πœ€> 0 even when every mass distribution is piece-wise uniform over polynomially many squares and there is no overlap between any two mass distributions. Hardness of Approximate SC-PIZZA-SHARING In this section we prove several hardness results for πœ€-SCPIZZA-SHARING. We give two different reductions that allow us to prove a variety of results. The first one, which we call the overlapping reduction, is conceptually simpler, and it reduces from πœ€-CONSENSUS-HALVING with π‘˜-block valuations. It produces SC-PIZZA-SHARING instances where every mass distribution is a union of piecewise uniform unit-squares. We use this to prove PPAhardness, PPAD-hardness, and NP-hardness for the problem when we have overlapping mass distributions. The second reduction, which we call the checkerboard reduction is more technical and reduces from πœ€CONSENSUS-HALVING with 2-block uniform valuations. It allows us to prove PPA-hardness even when every mass distribution is 𝑑𝑖-ℓ𝑖-unit-square uniform. While the overlapping reduction produces mass distributions that can overlap each other, the checkerboard reduction produces an instance in which the mass distributions do not touch each other. Since both reductions are from πœ€-CONSENSUS-HALVING with block valuations, we will begin by introducing some notation. For both reductions, we will reduce from an instance 𝐼𝐢𝐻of πœ€-CONSENSUS-HALVING with k-block valuations for the agents. Thus, the valuation function of agent 𝑖 is defined by the subintervals [π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗] for 𝑗 [π‘˜]. The first step of both reductions is to partition [0, 1] to subintervals that are defined by points of interest. We say that a point π‘₯ [0, 1] is a point of interest if it coincides with the beginning or the end of a valuation block of an agent; formally, π‘₯is a point of interest if π‘₯ {π‘Žβ„“ 𝑖𝑗, π‘Žπ‘Ÿ 𝑖𝑗} for some 𝑖 [𝑛] and 𝑗 [π‘˜]. These points conceptually split [0, 1] into blocks, since in between any pair of consecutive points of interest, all agents have a non-changing valuation. Let 0 π‘₯1 π‘₯2 . . . π‘₯π‘š 1 denote the points of interest and [π‘₯𝑗, π‘₯𝑗+1] denote the intervals of interest. Observe that π‘š 2 𝑛 π‘˜. Also, observe that for every 𝑗, π‘₯𝑗+1 π‘₯𝑗is polynomially bounded with respect to the input size. Overview of the overlapping reduction. The key idea behind the reduction is to encode any CONSENSUS-HALVING instance where agents have π‘˜-block uniform valuations as a sequence of diagonal squares in the SC-PIZZA-SHARING instance. The instance consists of a sequence of squares, which are lined up diagonally, and each square corresponds to the corresponding block from the CONSENSUS-HALVING instance. Square 𝑠1 corresponds to the region between π‘₯1 and π‘₯2, square 𝑠2 corresponds to the region between π‘₯2 and π‘₯3, and so on. The weight of each square for each agent equals the block of interest s length times the valuation density of the agent in the CONSENSUS-HALVING instance. The key observation is that if an SC-path cuts two distinct squares, then it must make at least one turn in between due to the diagonal arrangement of the squares. This will allow us to transform an SC-path with 𝑛 1 turns into a sequence of 𝑛cuts for the CONSENSUS-HALVING instance: every time the path passes through a square, we transform it into a cut in the corresponding block in the CONSENSUS-HALVING instance. The weighting of the squares ensures that, if the SCpath cuts each of the mass distributions in half, then the cuts will be a solution to the CONSENSUS-HALVING instance. The construction. We are ready to formally define the reduction. Starting from an instance 𝐼𝐢𝐻of CONSENSUSHALVING, we will construct an πœ€-SC-PIZZA-SHARING instance 𝐼SC. For every agent 𝑖we will create a mass distribution πœ‡π‘–. We will create π‘š 1 unit-squares 𝑠1, 𝑠2, . . . , π‘ π‘š 1 which will be the locations where the mass distributions are placed. Unit-square 𝑠𝑗is defined by the points (𝑗, 𝑗), (𝑗+ 1, 𝑗), (𝑗, 𝑗+ 1), and (𝑗+ 1, 𝑗+ 1), meaning that squares 𝑠𝑗 and 𝑠𝑗+1 are diagonally adjacent. If agent 𝑖has positive value 𝑐𝑖𝑗over the interval of interest [π‘₯𝑗, π‘₯𝑗+1], then mass distribution πœ‡π‘–has density 𝑐𝑖𝑗 (π‘₯𝑗+1 π‘₯𝑗) over the 𝑗-th unit-square. This means that for any mass distribution that appears in square 𝑠𝑗and any area 𝑆 𝑠𝑗of size |𝑆|, we have πœ‡π‘–(𝑆) = |𝑆| 𝑐𝑖𝑗 (π‘₯𝑗+1 π‘₯𝑗). Observe that by the way the instance 𝐼SC is constructed, any SC-path with π‘˜turns can traverse at most π‘˜+1 squares. We must now show how the SC-path can be mapped to a solution for 𝐼𝐢𝐻. Let us now translate an SC-path into a sequence of cuts for 𝐼𝐢𝐻. If the SC-path passes through a square without turning then this line segment is mapped back to a single cut in 𝐼𝐢𝐻that cuts the same proportion of mass from the block. If the SC-path turns inside a square 𝑠𝑗, then we must be more careful. If the path turns inside 𝑠𝑗, and the square right before and the squares right before and after 𝑠𝑗are both on the same side of the cut, then we cannot use a single cut in 𝐼𝐢𝐻, and instead we have to use two cuts. This is not a problem, because the extra turn inside the square means that we can afford to use an extra cut inside the corresponding block in 𝐼𝐢𝐻. Even if the path passes through the square multiple times, we never need to use more than two cuts in 𝐼𝐢𝐻. In general, if the lower left corner of the square and the upper right corner of the square are on the same side of the SC-path, then we use two cuts in 𝐼𝐢𝐻. Formally, the translation between SC-paths and cuts in 𝐼𝐢𝐻is given in the following lemma. Lemma 7. Every solution of the πœ€-SC-PIZZA-SHARING instance 𝐼SC with an SC-path with π‘˜turns corresponds to a solution of the πœ€-CONSENSUS-HALVING instance 𝐼𝐢𝐻with π‘˜+ 1 cuts. Hardness results. So far we have reduced CONSENSUSHALVING to πœ€-SC-PIZZA-SHARING, but the hardness result that we obtain depends on the instance of CONSENSUSHALVING that we start with. We will show that, by varying this instance, we can obtain a variety of hardness results. We begin by showing PPA-hardness. By combining the PPA-hardness result of (Filos-Ratsikas et al. 2020) with Lemma 7 we get the following. Theorem 8. πœ€-SC-PIZZA-SHARING is PPA-hard for πœ€= 1/poly(𝑛), even when an SC-path with 𝑛+𝑛1 𝛿turns is allowed for some constant 𝛿> 0, and every mass distribution is piece-wise uniform over polynomially many unit-squares. Next we show PPAD-hardness. In (Filos-Ratsikas et al. 2018) it was proven that πœ€-CONSENSUS-HALVING is PPAD-hard for a constant πœ€, 6-block valuation functions, and even when we are allowed to use 𝑛+ π‘˜cuts, for some constant π‘˜. In addition, every agent has positive value for at most six intervals of interest and for every interval of interest at most three agents have positive value. By combining the PPAD-hardness result of the aforementioned paper with Lemma 7 we get the following. Theorem 9. πœ€-SC-PIZZA-SHARING is PPAD-hard for some absolute constant πœ€, even when an SC-path with 𝑛+ 𝑛1 𝛿 turns is allowed, for some constant 𝛿> 0, every mass distribution is piece-wise uniform over six unit-squares, and at any point of the plane at most three mass-distributions overlap. Finally, Lemma 7 is general enough to imply yet another result when combined with the NP-hardness result of the aforementioned paper. Theorem 10. It is NP-hard to decide if an πœ€-SC-PIZZASHARING instance admits a solution with an SC-path with 𝑛 2 turns, even when every mass distribution is piece-wise uniform over six unit-squares, and at any point of the plane at most three mass-distributions overlap. The checkerboard reduction. Finally, we show that the problem remains PPA-hard even for unweighted nonoverlapping squares. More formally, this means that the 𝑖-th mass distribution consists of 𝑑𝑖squares of size ℓ𝑖 ℓ𝑖each and πœ‡π‘–is uniformly distributed over the 𝑑𝑖squares. In addition, there is no overlap between the mass distributions. To do this, we use the same ideas as the overlapping reduction, but rather than producing overlapping squares, we create blocks that are filled with a checkerboard pattern to ensure that none of the mass distributions overlap. Now each block is filled by a tiling that contains squares from the mass distributions that appear in the corresponding interval of interest. This ensures that no two mass distributions overlap. The size of the squares associated with a specific mass distribution that appear in a tile are in proportion to the agent s valuations in the CONSENSUS-HALVING instance. However, we show that with a sufficiently dense tiling, the difference in proportions is bounded, and so we can still recover an πœ€-solution for CONSENSUS-HALVING from an πœ€ - solution for SC-PIZZA-SHARING. Theorem 11. πœ€-SC-PIZZA-SHARING is PPA-hard even when πœ€is inverse-polynomial with respect to 𝑛, one is allowed to use 𝑛+ 𝑛1 𝛿turns for some constant 𝛿> 0, every mass distribution πœ‡π‘–is uniform 𝑑-ℓ𝑖-square with 𝑑= 𝑂(𝑛), and there is no overlap between any two mass distributions. 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 𝑛 1 turns is ETR-hard. We prove these results using a reduction from the exact version of CONSENSUS-HALVING. This time however we will use the instances of CONSENSUSHALVING produced in (Deligkas et al. 2021), which we will denote by 𝐼DFMS 𝐢𝐻. We note that here the input consists of sets of points, i.e., we describe polygons by chains of vertices. In (Deligkas et al. 2021) the FIXP-hard family of instances we reduce from had as input 𝑛arithmetic circuits capturing the cumulative valuation of 𝑛agents on [0, 1], which were piece-wise polynomials of maximum degree 2. However, since their (density) valuation functions consist of only rectangles and triangles, the input can also be sets of points that define the aforementioned shapes. So, there is no need for extra translation of the input of CONSENSUS-HALVING to that of SC-PIZZA-SHARING. FIXP-hardness. Here we show that finding an exact solution to SC-PIZZA-SHARING is FIXP-hard. The key difference between this reduction and the previous reductions on the approximate versions is that the instance 𝐼DFMS 𝐢𝐻 contains triangular shaped valuations for agents. More specifically, all of the following hold: 1. the valuation function of every agent is 4-block-triangle, or 6-block; 2. every triangle has height 2 and belongs to exactly one interval of interest of the form [π‘Ž, π‘Ž+ 1]; 3. for every agent 𝑖 [𝑛] there exists an interval [π‘Ž, 𝑏] that contains more than half of their total valuation and in addition for every 𝑖 = 𝑖 we have (π‘Ž, 𝑏) (π‘Ž , 𝑏 ) = . We will follow the same approach as in the overlapping reduction. Namely, every interval of interest will correspond to a unit-square located on the diagonal of the instance. Blockshaped valuations will be translated as before. For the triangular valuations, Point 2 guarantees that no triangle is split over two different intervals of interest. Hence, we can create an axis-aligned triangle inside the unit-square. Formally, if there exists a triangle in the interval of interest [π‘₯𝑗, π‘₯𝑗+1], then we create a triangle with vertices (𝑗, 𝑗+ 1), (𝑗+ 1, 𝑗), (𝑗+ 1, 𝑗+ 1) with density 1; this is because all triangles in the CONSENSUS-HALVING instance have the same value. One complication is that, if the SC-path turns inside a square, then it may not be possible to map this back to cuts in the SC-PIZZA-SHARING instance. One example of this would be when the path cuts a portion of the square without cutting the triangle at all. Fortunately, we are able to use point 3 above to show that all exact solutions to the SC-PIZZA-SHARING instance must pass through 𝑛distinct squares. Therefore, if a SC-path wastes a turn by turning inside a square, then it can pass through at most 𝑛 1 distinct squares, and so it cannot be an exact solution to the SC-PIZZA-SHARING instance. Hence we can restrict ourselves to SC-paths that do not turn inside a square. The mapping from SC-paths to CONSENSUS-HALVING cuts is the same as the overlapping reduction. Here, in particular, we rely on the fact that if the SC-path does not turn inside a square, then it must pass through the triangular mass either horizontally or vertically, and so we can map this back to a single cut in the CONSENSUS-HALVING instance. Lemma 12. Any SC-path that is a solution for the produced SC-PIZZA-SHARING instance, does not turn inside any unit-square. Combining Lemma 12 and the FIXP-hardness proven for 𝐼DFMS 𝐢𝐻 in (Deligkas et al. 2021) gives us the following result. 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. ETR-hardness. We can also show that deciding whether there is an exact SC-PIZZA-SHARING solution with 𝑛 2 turns exists is ETR-hard. To show this, we will use a result of (Deligkas et al. 2021), where it was shown that deciding whether there exists an exact CONSENSUS-HALVING solution with 𝑛agents and 𝑛 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 BU-hardness reduction. Theorem 14. It is ETR-hard to decide if an exact SCPIZZA-SHARING instance admits a solution with a SC-path with 𝑛 2 turns. Containment Results In this section we present containment results for the exact and approximate versions of SC-PIZZA-SHARING that we study in this paper. All of our containment results revolve around a proof that solutions exist for SC-PIZZA-SHARING which utilizes the Borsuk-Ulam theorem. A proof of this kind was already presented in (Karasev, Rold an-Pensado, and Sober on 2016), but we present our own proof which is conceptually simpler, as it does not use any involved topological techniques. An advantage of our proof is that it can be made algorithmic, and so it can be used to show that SCPIZZA-SHARING is contained in BU. Then, by making simple modifications to the BU containment proof, we show the other containment results hold. Theorem 15. Exact SC-PIZZA-SHARING for weighted polygons with holes is in BU. Theorem 16. Deciding whether there exists an SC-path with π‘˜turns that is an exact solution for SC-PIZZASHARING with 𝑛mass distributions is in ETR. Theorem 17. πœ€-SC-PIZZA-SHARING for weighted polygons with holes is in PPA. Theorem 18. Deciding whether there exists an SC-path with π‘˜turns that is a solution for πœ€-SC-PIZZA-SHARING with 𝑛mass distributions is in NP. Open Problems One of the most interesting open problems is to settle the complexity of the more general pizza sharing problems where, instead of two, we ask to fairly split the plane into 𝑑 3 equal parts. Acknowledgements The paper was completed while the third author was affiliated with the group of Operations Research at the Technical University of Munich. His work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). References Agarwal, P. K.; Erickson, J.; et al. 1999. Geometric range searching and its relatives. Contemporary Mathematics, 223: 1 56. Aumann, Y.; and Dombb, Y. 2015. The Efficiency of Fair Division with Connected Pieces. ACM Trans. Econ. Comput., 3(4). Barba, L.; Pilz, A.; and Schnider, P. 2019. Sharing a pizza: bisecting masses with two cuts. ar Xiv preprint ar Xiv:1904.02502. Batziou, E.; Hansen, K. A.; and HΓΈgh, K. 2021. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In Bansal, N.; Merelli, E.; and Worrell, J., eds., 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, 24:1 24:20. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Blagojevi c, P.; Frick, F.; Haase, A.; and Ziegler, G. 2018. Topology of the Gr unbaum Hadwiger Ramos hyperplane mass partition problem. Transactions of the American Mathematical Society, 370(10): 6795 6824. Canny, J. 1988. Some Algebraic and Geometric Computations in PSPACE. In Proc. of STOC, 460 467. New York, NY, USA: ACM. ISBN 0-89791-264-0. Chambers, C. P. 2005. Allocation rules for land division. Journal of Economic Theory, 121(2): 236 258. De Loera, J.; Goaoc, X.; Meunier, F.; and Mustafa, N. 2019. The discrete yet ubiquitous theorems of Carath eodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, 56(3): 415 511. Deligkas, A.; Fearnley, J.; Hollender, A.; and Melissourgos, T. 2022. Constant Inapproximability for PPA. Co RR, abs/2201.10011. Deligkas, A.; Fearnley, J.; and Melissourgos, T. 2020. Square-Cut Pizza Sharing is PPA-complete. Co RR, abs/2012.14236. Deligkas, A.; Fearnley, J.; Melissourgos, T.; and Spirakis, P. G. 2021. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Journal of Computer and System Sciences, 117: 75 98. Deligkas, A.; Filos-Ratsikas, A.; and Hollender, A. 2020. Two s Company, Three s a Crowd: Consensus-Halving for a Constant Number of Agents. Co RR, abs/2007.15125. Edelsbrunner, H. 2012. Algorithms in combinatorial geometry, volume 10. Springer Science & Business Media. Elkind, E.; Segal-Halevi, E.; and Suksompong, W. 2021. Keep Your Distance: Land Division With Separation. In Zhou, Z., ed., Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, 168 174. ijcai.org. Filos-Ratsikas, A.; Frederiksen, S. K. S.; Goldberg, P. W.; and Zhang, J. 2018. Hardness Results for Consensus Halving. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 24:1 24:16. Schloss Dagstuhl Leibniz-Zentrum f ur Informatik. Filos-Ratsikas, A.; and Goldberg, P. W. 2018. Consensus Halving is PPA-complete. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 51 64. ACM. Filos-Ratsikas, A.; and Goldberg, P. W. 2019. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 638 649. ACM. Filos-Ratsikas, A.; Hollender, A.; Sotiraki, K.; and Zampetakis, M. 2020. Consensus-Halving: Does it Ever Get Easier? In Proceedings of the 21st ACM Conference on Economics and Computation (EC), 381 399. Filos-Ratsikas, A.; Hollender, A.; Sotiraki, K.; and Zampetakis, M. 2021. A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2615 2634. SIAM. Hubard, A.; and Karasev, R. 2020. Bisecting measures with hyperplane arrangements. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 169, 639 647. Cambridge University Press. Husseinov, F. 2011. A theory of a heterogeneous divisible commodity exchange economy. Journal of Mathematical Economics, 47(1): 54 59. Iyer, K.; and Huhns, M. N. 2009. A procedure for the allocation of two-dimensional resources in a multiagent system. International Journal of Cooperative Information Systems, 18(03n04): 381 422. Kaneko, A.; and Kano, M. 2003. Discrete geometry on red and blue points in the plane a survey . In Discrete and computational geometry, 551 570. Springer. Kano, M.; and Urrutia, J. 2020. Discrete Geometry on Red and Blue Points in the Plane-A survey. Graphs and Combinatorics. Karasev, R. N.; Rold an-Pensado, E.; and Sober on, P. 2016. Measure partitions using hyperplanes with fixed directions. Israel Journal of Mathematics, 212(2): 705 728. Landau, Z.; Reid, O.; and Yershov, I. 2009. A fair division solution to the problem of redistricting. Social Choice and Welfare, 32(3): 479 492. Landau, Z.; and Su, F. E. 2014. Fair division and redistricting. The Mathematics of Decisions, Elections, and Games. American Mathematical Society, 17 36. Matousek, J. 2013. Lectures on discrete geometry, volume 212. Springer Science & Business Media. MatouΛ‡sek, J. 2014. Intersection graphs of segments and R. Co RR, abs/1406.2636. MatouΛ‡sek, J. 2008. Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry. Springer Science & Business Media. Megiddo, N.; and Papadimitriou, C. H. 1991. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2): 317 324. Papadimitriou, C. H. 1994. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3): 498 532. Rold an-Pensado, E.; and Sober on, P. 2020. A Survey of mass partitions. Co RR, abs/2010.00478. S., K. C.; and Saha, A. 2017. Ham sandwich is equivalent to Borsuk-Ulam. In Aronov, B.; and Katz, M. J., eds., 33rd International Symposium on Computational Geometry (So CG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), 24:1 24:15. Dagstuhl, Germany: Schloss Dagstuhl Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-038-5. Schaefer, M. 2009. Complexity of some geometric and topological problems. In International Symposium on Graph Drawing, 334 344. Springer. Schnider, P. 2021. The Complexity of Sharing a Pizza. In Ahn, H.; and Sadakane, K., eds., 32nd International Symposium on Algorithms and Computation, ISAAC, volume 212 of LIPIcs, 13:1 13:15. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik. Segal-Halevi, E.; Nitzan, S.; Hassidim, A.; and Aumann, Y. 2017. Fair and square: Cake-cutting in two dimensions. Journal of Mathematical Economics, 70: 1 28. Segal-Halevi, E.; Nitzan, S.; Hassidim, A.; and Aumann, Y. 2020. Envy-Free Division of Land. Math. Oper. Res., 45(3): 896 922. Simmons, F. W.; and Su, F. E. 2003. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical social sciences, 45(1): 15 25. Steinhaus, H. 1948. The problem of fair division. Econometrica, 16: 101 104. Λ‡Zivaljevi c, R. 2017. Topological methods in discrete geometry. In Handbook of Discrete and Computational Geometry, Third Edition. Taylor & Francis.