Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Introduction

We consider the classical cake cutting problem, where we wish to divide a cake among a set of agents with different preferences over different parts of the cake. The cake serves as a metaphor for any divisible resource such as time or land, and our aim is to perform the division in a fair manner. This problem has a long and storied history that dates back over 70 years (Brams and Taylor, 1996; Robertson and Webb, 1998; Procaccia, 2016) and has received considerable attention in the past decade (Caragiannis et al., 2011; Bei et al., 2012; Aumann et al., 2013; Balkanski et al., 2014; Brânzei and Miltersen, 2015; Alijani et al., 2017; Menon and Larson, 2017; Bei et al., 2018; Segal-Halevi, 2018).

In order to reason about fairness, we need to specify when a division is considered to be fair. One of the most commonly used definitions is envy-freeness, which means that no agent envies another with respect to the division. In other words, among the pieces in the division, every agent receives their first choice. An early result by Dubins and Spanier (1961) shows that an envy-free allocation always exists for arbitrary valuations of the agents. However, as Stromquist (1980) noted, this result depends on a liberal definition of what constitutes a piece of cake, and an agent “who hopes only for a modest interval of cake may be presented instead with a countable union of crumbs.”

In light of this concern, Stromquist (1980) strengthened the result of Dubins and Spanier by showing that it is possible to guarantee an envy-free allocation in which every agent receives a contiguous piece of the cake. Stromquist’s result, together with its topological proof, is widely regarded as a cornerstone of the cake-cutting literature. Nevertheless, since the result focuses only on the existence of a contiguous envy-free allocation, it leaves open the question of how to compute such an allocation. Almost 30 years later, Stromquist himself addressed this question and showed that under the Robertson-Webb model, where an algorithm is allowed to discover the agents’ valuations through cut and evaluate queries, no finite algorithm can compute a contiguous envy-free allocation when there are at least three agents (Stromquist, 2008).For two agents, the well-known cut-and-choose protocol, which lets the first agent cut the cake into two equal pieces and lets the second agent choose the piece that she prefers, computes a contiguous envy-free allocation.

Although Stromquist’s later result rules out the possibility of computing contiguous envy-free allocations in general, several important questions still remain. For instance, can we compute a contiguous allocation with low envy between the agents, and if so, how efficiently? How does the answer change if we know that the agents’ valuations belong to a restricted class? What happens if we add extra requirements on the allocation, such as fixing a desired ordering of the agents or constraining the positions of certain cuts? The goal of this paper is to shed light on the complexity of contiguous cake cutting by addressing these questions.

First, in Section 3 we present two algorithms that compute an allocation with low envy in polynomial time. As is standard in the cake-cutting literature, we represent the cake by the interval $$and normalize the agents’ valuations so that each agent has value$1$for the entire interval. Our first algorithm works for general valuations under the Robertson-Webb model and produces a contiguous allocation in which any agent has envy no more than$1/3$towards any other agent. On the other hand, our second algorithm is specific to valuations where each agent only desires a single subinterval and has a uniform value over that interval—for such valuations, the algorithm produces a contiguous allocation with a lower envy of at most$1/4$.

Next, in Section 4 we consider variants of the cake-cutting problem where we impose constraints on the desired allocation. We show that for several natural variants, the decision problem of whether there exists a contiguous envy-free allocation satisfying the corresponding constraints is NP-hard. In particular, this holds for the variants where (i) a certain agent must be allocated the leftmost piece; (ii) the ordering of the agents is fixed; and (iii) one of the cuts must fall at a given position. Fixing the ordering of the agents is relevant when there is a temporal ordering in which the agents must be served, e.g., due to notions of seniority or the ease of switching from one agent to another in the service. Likewise, fixing a cut point is applicable when we divide a parcel of land and there is a road crossing the parcel, so we cannot allocate a piece that lies on both sides of the road. Moreover, our construction serves as a general framework that can be used to obtain hardness results for other related variants.

In Section 5 we investigate a discrete analog of cake cutting, where there are indivisible items on a line and each agent is to be allocated a contiguous block of items. The discrete setting can be viewed as a type of restriction for the continuous setting, where cuts must be placed between discrete items. In addition to envy-freeness, we work with two other well-studied fairness notions: proportionality and equitability.See the definitions in Section 5. Using a single reduction, we show that deciding whether there exists a contiguous fair allocation is NP-hard for each of the three fairness notions as well as any combination of them; our result holds even when all agents have binary valuationsThat is, the valuations are additive and each agent values each item either or $1$. and moreover value the same number of items. This significantly strengthens a result of Bouveret et al. (2017), who established the hardness for proportionality and envy-freeness using additive but non-binary valuations. Moreover, we show that even if we consider approximate envy-freeness instead of exact, the decision problem remains NP-hard for binary valuations. We also prove that when the valuations are binary and every agent values a contiguous block of items, deciding whether a contiguous proportional allocation exists is NP-hard.

Finally, in Section 6 we present a number of connections between approximate and exact envy-freeness, as well as between the continuous and discrete settings. First, we prove that for piecewise constant valuations, finding an approximately envy-free allocation is as hard as finding an exactly envy-free allocation. Then, we reveal some relationships between continuous and discrete cake cutting—among other things, we show that a special case of the continuous problem for piecewise constant valuations is computationally equivalent to a discrete cake-cutting problem where every item is positively valued by at most one agent. This means that any algorithm or hardness result for one problem will immediately transfer over to the other.

2 Further Related Work

Since the seminal work of Stromquist (1980, 2008), a number of researchers have studied cake cutting in view of the contiguity condition. Su (1999) proved the existence of contiguous envy-free allocations using Sperner’s lemma arguments. Deng et al. (2012) showed that contiguous envy-free cake cutting is PPAD-complete; however, the result requires non-standard (e.g., non-additive, non-monotone) preference functions. Aumann et al. (2013) considered the problem of maximizing social welfare with contiguous pieces, while Bei et al. (2012) tackled the same problem with the added requirement of proportionality. Cechlárová and Pillárová (2012) and Cechlárová et al. (2013) examined the existence and computation of contiguous equitable allocations—among other things, they showed that such an allocation is guaranteed to exist even if we fix the ordering of the agents. Aumann and Dombb (2015) analyzed the trade-off between fairness and social welfare in contiguous cake cutting. Segal-Halevi et al. (2016) circumvented Stromquist (1980)’s impossibility result by presenting bounded-time contiguous envy-free algorithms that may not allocate the entire cake but guarantee every agent a certain positive fraction of their value.Without this guarantee, it would be much easier to find a contiguous envy-free allocation—just don’t allocate any of the cake!

The contiguity requirement has also been considered in the context of indivisible items. Marenco and Tetzlaff (2014) proved that if the items lie on a line and every item is positively valued by at most one agent, a contiguous envy-free allocation is guaranteed to exist. When each item can yield positive value to any number of agents, Barrera et al. (2015), Bilò et al. (2019), and Suksompong (2019) showed that various relaxations of envy-freeness can be fulfilled. In addition, contiguity has been studied in the more general model where the items lie on an arbitrary graph (Bouveret et al., 2017; Igarashi and Peters, 2019; Bei et al., 2019). Like us, Igarashi and Peters (2019) also showed hardness results for binary valuations.

Recently, Arunachaleswaran et al. (2019) developed an efficient algorithm that computes a contiguous cake division with multiplicatively bounded envy—in particular, each agent’s envy is bounded by a multiplicative factor of $3$. We remark that our approximation algorithms are incomparable to their result. On the one hand, their algorithm may return an allocation wherein an agent has value $1/4$ for her own piece and $3/4$ for another agent’s piece—this corresponds to an additive envy of $1/2$. On the other hand, our algorithms may leave some agents empty-handed, leading to unbounded multiplicative envy. We also note that additive envy is the more commonly considered form of approximation, both for cake cutting (Deng et al., 2012; Brânzei and Nisan, 2017, 2019) and for indivisible items (Lipton et al., 2004; Caragiannis et al., 2016).

Preliminaries

For any positive integer $n$, let $[n]=\{1,2,\dots,n\}$. In our cake cutting setting, we consider the cake as the interval $$. There are$n$agents whose preferences over the cake are represented by valuation functions$v_{1},\dots,v_{n}$. Assume that these valuation functions are non-negative density functions over$$. We abuse notation and let$v_{i}(a,b)=v_{i}([a,b])=\int_{a}^{b}v_{i}(x)dx$for$0\leq a\leq b\leq 1$. It follows that the valuations are non-negative, additive, and non-atomic (i.e.,$v_{i}(a,a)=0$). We assume further that the valuations are normalized so that$v_{i}(0,1)=1$for every$i\in[n]$.

A contiguous allocation of the cake is a partition of $$into$n$(possibly empty) intervals, along with an assignment of each interval to an agent, so that every agent gets exactly one interval. Note that this means that we cut the cake using$n-1$cuts. Formally, a contiguous allocation is represented by the cut positions$0\leq x_{1}\leq x_{2}\leq\dots\leq x_{n-1}\leq 1$and a permutation$\pi:[n]\to[n]$that assigns the intervals to the agents so that agent$i$receives the interval$[x_{\pi(i)-1},x_{\pi(i)}]$, where we define$x_{0}=0$and$x_{n}=1$ for convenience.

We are interested in finding a contiguous allocation that is envy-free, i.e., no agent thinks that another agent gets a better interval. Formally, the contiguous allocation $(x,\pi)$ is envy-free if for all $i,j\in[n]$, we have $v_{i}(x_{\pi(i)-1},x_{\pi(i)})\geq v_{i}(x_{j-1},x_{j})$. In some cases we will be interested in finding a contiguous allocation that is only approximately envy-free. For $\varepsilon\in$, the contiguous allocation $(x,\pi)$ is $\varepsilon$-envy-free if for all $i,j\in[n]$, we have $v_{i}(x_{\pi(i)-1},x_{\pi(i)})\geq v_{i}(x_{j-1},x_{j})-\varepsilon$. In other words, any agent has envy that is at most a fraction $\varepsilon$ of her value for the whole cake.

A typical way for an algorithm to access the valuation functions is through queries in the Robertson-Webb model: the algorithm can make evaluate queries—where it specifies $x,y$ and asks agent $i$ to return the value $v_{i}(x,y)$—and cut queries—where it specifies $x,\alpha$ and asks agent $i$ to return the leftmost point $y$ such that $v_{i}(x,y)=\alpha$ (or say that no such $y$ exists). A more restrictive class of valuations is that of piecewise constant valuations. A piecewise constant valuation function is defined by a piecewise constant density function on $$, i.e., a step function. This class of valuations can be explicitly represented as part of the input. A subclass of piecewise constant valuations is the class of piecewise uniform valuations, where the density function of agent$i$is either some fixed rational constant$c_{i}$ or .

Approximation Algorithms

In this section, we present two algorithms for approximate envy-free cake cutting. Algorithm 1 works for arbitrary valuations and returns a $1/3$-envy-free allocation. On the other hand, Algorithm 2 can be used for piecewise uniform valuations with a single value-block and outputs a $1/4$-envy-free allocation. Note that such valuations are relevant, for example, when the agents are dividing machine processing time: each agent has a release date and a deadline for her job, so she would like to maximize the processing time she obtains after the release date and before the deadline.

While Algorithm 1 can be implemented for general valuations under the Robertson-Webb model, it also allows a simple interpretation as a moving-knife algorithm. In this interpretation, the algorithm works by moving a knife over the cake from left to right. Whenever the current piece has value $1/3$ to at least one remaining agent, the piece is allocated to one such agent. If the knife reaches the right end of the cake, then the piece is allocated to an arbitrary remaining agent if there is at least one remaining agent, and to the agent who received the last piece otherwise.

For $n$ agents with arbitrary valuations, Algorithm 1 returns a contiguous $1/3$-envy-free allocation and runs in time polynomial in $n$ assuming that it makes queries in the Robertson-Webb model.

Note that if we are only interested in having an algorithm that makes a polynomial number of queries, Brânzei and Nisan (2017) showed that for any $\varepsilon>0$, a contiguous $\varepsilon$-envy-free allocation can be found using $O(n/\varepsilon)$ queries, which is polynomial in $n$ for constant $\varepsilon$. Their algorithm works by cutting the cake into pieces of size $1/\varepsilon$ and performing a brute-force search over the space of all contiguous allocations with respect to these cuts; this algorithm therefore has exponential computational complexity (even for constant $\varepsilon$). By contrast, in the absence of the contiguity constraint, Procaccia (2016, p. 323) gave a simple polynomial-time algorithm that computes an $\varepsilon$-envy-free allocation for any constant $\varepsilon$. His algorithm also starts by cutting the cake into pieces of size $1/\varepsilon$ and then lets agents choose their favorite pieces in a round-robin manner; consequently, the resulting allocation can be highly non-contiguous.

While we do not know whether the bound $1/3$ in our approximation can be improved under the computational efficiency requirement,For the case $n=3$, Deng et al. (2012) gave a fully polynomial-time approximation scheme that computes a contiguous $\varepsilon$-envy-free allocation for any $\varepsilon>0$. we show next that if the agents have piecewise uniform valuations and each agent only values a single interval, the envy can be reduced to $1/4$. Alijani et al. (2017) showed that if the valuations are as described and moreover the $n$ valued intervals satisfy an “ordering property”, meaning that no interval is a strict subinterval of another interval, then a contiguous envy-free allocation can be computed efficiently. Nevertheless, the ordering property is a very strong assumption, and indeed reducing the envy to $1/4$ without this assumption already requires significant care in assigning the pieces.Alijani et al. (2017) also showed that for piecewise uniform valuations where each agent only values a single interval (without the ordering property assumption), one can efficiently compute an envy-free allocation with at most $2n-1$ intervals in total. Moreover, they showed that for a constant number of agents with piecewise constant valuations, a contiguous envy-free allocation can be computed efficiently.

At a high level, Algorithm 2 first orders the agents from shortest to longest desired interval, breaking ties arbitrarily. For each agent in the ordering, if an interval of value $1/4$ containing the midpoint of her valued interval (perhaps at the edge of the former interval) has not been taken, the agent takes one such interval. Else, if an interval of value $1/4$ is available somewhere, the agent takes one such interval; here, if there are choices on both sides of the midpoint, the agent may need to be careful to pick the “correct” one. Otherwise, if no interval of value $1/4$ is available, the agent takes a largest available interval. At the end of this process, part of the cake may remain unallocated. If some pair of assigned intervals are adjacent, pick one such pair, and allocate the remaining cake by extending pieces away from the border between this pair. Else, extend the pieces arbitrarily to cover the remaining cake.

For $n$ agents with piecewise uniform valuations such that each agent only values a single interval, Algorithm 2 returns a contiguous $1/4$-envy-free allocation and runs in time polynomial in $n$.

One can check that Algorithm 2 assigns a single interval to every agent and can be implemented in polynomial time. It remains to show that the algorithm returns an allocation such that for any two agents $i,j$, agent $i$ has envy at most $1/4$ towards agent $j$. For the purpose of this proof, when we refer to an interval $M_{i}$, we mean the interval before it is extended in the final phase of the algorithm (the extension phase starting at line 18). We denote by $M_{i}^{+}$ the corresponding extended interval that is returned by the algorithm. For any agent $i$ and any interval $I$, the $i$-value of $I$ is the value of $I$ for agent $i$, i.e., $v_{i}(I)$.

When agent $i$’s turn comes in the for-loop, it falls into exactly one of four possible cases: Case 1 (line 8), Case 2 (line 10), Case 3 (line 14) or Case 4 (line 16). Depending on which case applies, $M_{i}$ is chosen accordingly. We say that the single-direction extension (SDE) property holds if at least one agent does not fall into Case 2. It is easy to check that if the SDE property holds, then there are at least two allocated intervals $M_{q}$ and $M_{r}$ that are adjacent before the extension phase begins, and thus every interval $M_{i}$ will be extended in a single direction.

It is clear that $v_{i}(M_{j}^{+})\geq v_{i}(M_{j})$ for all $i,j$. Furthermore, in all four cases it holds that agent $i$ is allocated an interval of value at most $1/4$, i.e., $v_{i}(M_{i})\leq 1/4$ for all $i$. Since $M_{i}\subseteq R_{i}$ and because of the way the agents are ordered, it follows that

We now show that any agent $i$ has envy at most $1/4$ at the end of the algorithm. Namely, we prove that for any agents $i,j$ we have $v_{i}(M_{j}^{+})\leq v_{i}(M_{i}^{+})+1/4$. We treat the four different cases that can occur during agent $i$’s turn.

Cases $1$ and $2$. In both cases, $M_{i}$ contains $\text{mid}(i)$ and has $i$-value $1/4$. This also holds for $M_{i}^{+}\supseteq M_{i}$. Since the midpoint of $R_{i}$ is contained in $M_{i}^{+}$, any other interval $M_{j}^{+}$ has $i$-value at most $1/2$. Thus, agent $i$ has envy at most $1/4$.

Case $4$. First, suppose that $v_{i}(M_{i})<1/4$. This means that $M_{i}$ was a largest available interval in $R_{i}$. It follows that any agent $j>i$ can obtain an interval of $i$-value at most $v_{i}(M_{i})$, since it is processed after $i$. For $j<i$, since agent $i$ is in Case 4, the SDE property holds. Thus, $M_{j}$ can be extended by at most $v_{i}(M_{i})$, i.e., $v_{i}(M_{j}^{+})\leq v_{i}(M_{j})+v_{i}(M_{i})$ for all $j$. With (1) it follows that the envy is at most $1/4$.

Now, consider the case where $v_{i}(M_{i})=1/4$. Any agent $j>i$ can obtain $i$-value no more than $1/2$—otherwise, agent $i$ would have fallen in Case 1 or 2. Consider any $j<i$:

if $\text{mid}(i)\in M_{j}$, then both on the left and right side of $M_{j}$ the space available has $i$-value $<1/4$ (otherwise agent $i$ would be in Case 1 or 3). Since the SDE property holds, it follows that $v_{i}(M_{j}^{+})\leq v_{i}(M_{j})+1/4\leq 1/2$ with (1).

if $\text{mid}(i)\notin M_{j}$, then $v_{i}(M_{j}^{+})<1/2$. Otherwise, it means that $M_{j}$ is extended in a single direction (SDE property) and takes over an interval of $i$-value at least $1/4$ that contains $\text{mid}(i)$. But then, agent $i$ would be in Case 1 or 2.

Hardness for Cake-Cutting Variants

In this section, we establish hardness results for a number of decision problems on the existence of contiguous envy-free allocations.

The following decision problems are NP-hard for contiguous cake cutting, even if we restrict the valuations to be piecewise uniform:

Does there exist an envy-free allocation in which agent $1$ obtains the leftmost piece?

Does there exist an envy-free allocation in which the pieces are allocated to the $n$ agents in the order $1,2,\dots,n$?

Does there exist an envy-free allocation such that there is a cut at position $x$, for $x$ given in the input?

These problems remain NP-hard if we replace envy-freeness by $\varepsilon$-envy-freeness for any sufficiently small constant $\varepsilon$.

This list is not exhaustive: additional results of the same flavor can be found in the full proof (Section 4.1).However, if we fix all $n-1$ cuts, the problem becomes solvable in polynomial time. Indeed, with all the cuts fixed, the resulting pieces are also all fixed. We can therefore construct a bipartite graph with the agents on one side and the pieces on the other side, where there is an edge between an agent and a piece exactly when receiving the piece would make the agent envy-free. The problem of determining whether an envy-free allocation exists therefore reduces to deciding the existence of a perfect matching, which can be done in polynomial time. The following proof sketch conveys the main ideas behind these results.

In order to prove that these decision problems are NP-hard, we reduce from 3-sat. Namely, given a 3-sat formula, we construct a cake-cutting instance such that the answer to the decision problem is “Yes” if and only if the 3-sat formula is satisfiable. A bonus of our proof is that we construct a single cake-cutting instance that works for all of the decision problems mentioned in the theorem statement and even a few more.

The instance is constructed by positioning the gadgets one after the other on the cake. Starting from the left and moving to the right, we first put the Clause-Gadget for $C_{1}$, then $C_{2}$, and so on until $C_{m}$, and then the Variable-Gadget for $x_{1}$, then $x_{2}$, and so on until $x_{n}$. Between adjacent gadgets we introduce a small interval without any value-blocks. We say that an envy-free allocation is nice if all the gadgets operate correctly.

Conversely, given a satisfying assignment for the 3-sat formula, it is not too hard to construct a nice envy-free allocation. This proves NP-hardness for the decision problem “Does there exist a nice envy-free allocation?”. In order to prove the result for the more natural decision problems stated in Theorem 4.1, the construction has to be extended with some additional work. ∎

We provide a full proof of NP-hardness for the following decision problems:

Does there exist an envy-free allocation in which agent $1$ gets the leftmost piece?

Does there exist an envy-free allocation in which agents $1,2,\dots,k$ get the $k$ leftmost pieces, in that order? (for any constant $k\geq 1$)

Does there exist an envy-free allocation in which all the agents $1,2,\dots,n$ are assigned pieces in that order from left to right?

Does there exist an envy-free allocation such that there is a cut at position $x$? ($x$ given in the input)

Does there exist an envy-free allocation such that the leftmost cut is at position $x$? ($x$ given in the input)

Does there exist an envy-free allocation such that there are cuts at positions $x_{1}$, $\dots$, $x_{k}$? ($x_{1}$, $\dots$, $x_{k}$ given in the input, $k$ any constant)

The problems remain NP-hard if we replace envy-freeness by $\varepsilon$-envy-freeness for any $\varepsilon\leq 0.01$.

The list of NP-hard problems that we have provided is by no means exhaustive. The construction we provide below should be viewed as a framework for obtaining these kinds of results. Indeed, with some simple modifications, one can prove additional results of the same general flavor. In particular, one can change the constraint to “agent $1$ gets the $k$th piece from the left ($k\geq 1$ constant)” or to “the $k$ leftmost cuts are at positions $x_{1}$, $\dots$, $x_{k}$”.

Let $I$ be an instance of $3$-sat with $m$ clauses $C_{1},\dots,C_{m}$, where each clause is made out of $3$ literals using the variables $x_{1},\dots,x_{n}$ and their negations. Note that $m$ is polynomial in $n$ and thus we can use $n$ as the complexity parameter for the instance. Let $\varepsilon\leq 0.01$ be arbitrary.

We will construct an instance where the cake is the interval $[0,p(n)]$ (for some polynomial $p$), instead of the usual $$. This is just for convenience as it is easy to obtain a completely equivalent instance on$$ in polynomial time. Indeed, it suffices to divide the position of every block by $p(n)$ and multiply its height by $p(n)$. Note that our construction also gives NP-hardness if the valuations are given in unary representation, since the positions and heights of blocks will have numerator and denominator bounded by some polynomial (even after we scale down to $$). All the valuations we construct will be piecewise uniform, and in fact all blocks of all agents will have height$1$(before scaling the cake to$$), but variable length. Furthermore, value-blocks of different agents will not overlap.

Clause-Gadget. Consider any clause $C_{i}$ in the instance $I$. $C_{i}$ will be represented by a Clause-Gadget in the cake cutting instance. The Clause-Gadget for $C_{i}$ requires an interval of length $9$ on the cake, say $[a_{i},a_{i}+9]$, where only three specific agents are allowed to have any value. These agents are denoted by $C_{i}^{1}$, $C_{i}^{2}$ and $C_{i}^{3}$. The interpretation is that $C_{i}^{1}$ corresponds to the first literal appearing in the clause $C_{i}$, $C_{i}^{2}$ to the second one, and $C_{i}^{3}$ to the third one. The valuation of agent $C_{i}^{1}$ contains three blocks of value in the interval $[a_{i},a_{i}+9]$: one in each of the subintervals $[a_{i},a_{i}+1]$, $[a_{i}+3,a_{i}+4]$ and $[a_{i}+6,a_{i}+7]$. Each of these blocks has value $0.24$ (i.e., length $0.24$ and height $1$). Agents $C_{i}^{2}$ and $C_{i}^{3}$ have the same blocks as $C_{i}^{1}$, but shifted by $1$ and $2$ to the right respectively. The valuations of the three agents inside the Clause-Gadget are shown in Figure 1.

Note that each of the three agents has value $0.72$ inside the Clause-Gadget. The remaining $0.28$ value will be situated in a different gadget that we introduce next.

Instance. Now consider the cake-cutting instance constructed as follows: starting from the left, position all the Clause-Gadgets one after the other, leaving an interval of length $3$ after every gadget. Then, position all the Variable-Gadgets one after the other, again leaving an interval of length $3$ after every gadget. Thus, the cake is the interval $[0,12m+7n]$, where the first Clause-Gadget occupies the interval $$, and the first Variable-Gadget occupies the interval$[12m,12m+4]$. There are$3m+2n$agents so far. Note that adjacent gadgets are separated by intervals of length$3$that we call Isolating Intervals. There are exactly$m+n-1$ Isolating Intervals.

The $k$th Isolating Interval from the left is denoted $I_{k}$. The Isolating Interval $I_{k}=[a,a+3]$ is divided into three subintervals: $I_{k}=[a,a+1]$, $I_{k}=[a+1,a+2]$ and $I_{k}=[a+2,a+3]$. Furthermore, we also add an interval of length 3 on the left end of the cake: the Initiation Interval. We denote it by $I_{0}$ and it is similarly subdivided into $I_{0}$, $I_{0}$ and $I_{0}$. The cake is now represented by the interval $[0,12m+7n+3]$.

We add two new agents $S_{0}$ and $S_{0}^{\prime}$. Agent $S_{0}$ has a block of value $1/7$ in $I_{0}$, a block of value $2/7$ in each of $I_{0}$, $I_{1}$ and $I_{1}$. Agent $S_{0}^{\prime}$ has a block of value $1$ in $I_{0}$. For $k\in[m+n-2]$ we define an agent $S_{k}$ that has a block of value $0.2$ in $I_{k}$ and a block of value $0.4$ in each of $I_{k+1}$ and $I_{k+1}$. We also define an agent $S_{m+n-1}$ that has a block of value $1$ in $I_{m+n-1}$. Figure 3 shows the valuations of the agents in $I_{0}$, $I_{1}$ and $I_{2}$. The total number of agents is $(3m+2n)+(m+n+1)=4m+3n+1$, so there are $4m+3n$ cuts in any solution.

Let $\varepsilon=0.01$. Since an envy-free allocation always exists, the cake-cutting instance we have constructed admits an envy-free allocation (in particular also $\varepsilon$-envy-free). In order to ensure that a solution only exists if the 3-sat formula is satisfiable, we have to add an additional constraint. An $\varepsilon$-envy-free allocation is said to satisfy the Isolation property if together all the Clause- and Variable-Gadgets contain at most $2m+n$ cuts strictly within them.

Any $\varepsilon$-envy-free allocation that satisfies the Isolation property yields a satisfying assignment for the 3-sat formula.

Consider any $\varepsilon$-envy-free allocation. If there is at most one cut strictly inside the Clause-Gadget of $C_{i}$, then there is an agent $C_{i}^{k}$ ($k\in\{1,2,3\}$) who does not obtain any of its value from this Clause-Gadget. Thus, agent $C_{i}^{k}$ gets value at most $0.28$ (from its corresponding Variable-Gadget). However, since the Clause-Gadget of $C_{i}$ is divided into at most two parts, some agent gets at least $0.72/2=0.36$ according to agent $C_{i}^{k}$’s valuation, which contradicts $\varepsilon$-envy-freeness. Thus, every Clause-Gadget contains at least two cuts strictly within them.

If the Variable-Gadget for $x_{j}$ does not strictly contain any cut, then all of it is allocated to a single agent. Necessarily, agent $L_{j}$ or $R_{j}$ would have envy $1>\varepsilon$. Thus, every Variable-Gadget strictly contains at least one cut.

Now consider an $\varepsilon$-envy-free allocation that also satisfies the Isolation property. Since the property permits at most $2m+n$ cuts strictly inside gadgets, we get that these lower bounds on the number of cuts inside gadgets are actually tight. Thus, there are exactly two cuts strictly inside every Clause-Gadget and exactly one cut strictly inside every Variable-Gadget.

Since there is exactly one cut strictly inside the Variable-Gadget of $x_{j}$, the two resulting parts must go to agents $L_{j}$ and $R_{j}$. Indeed, if one of these two agents does not get one of the two parts, then the agent would have envy at least $1/2>\varepsilon$. Similarly, since there are exactly two cuts strictly inside the Clause-Gadget of $C_{i}$, the three resulting parts must go to agents $C_{i}^{1}$, $C_{i}^{2}$ and $C_{i}^{3}$. Indeed, if one of these three agents does not get one of the three parts, the agent would have value (as she cannot get any value from the corresponding variable gadget) and therefore have envy at least $0.24>\varepsilon$.

We now show how such a solution yields a satisfying assignment to the 3-sat instance. Consider the Clause-Gadget of $C_{i}$. As we showed above, there are exactly two cuts strictly inside the gadget and the three resulting parts go to the agents $C_{i}^{1}$, $C_{i}^{2}$ and $C_{i}^{3}$. Any of these three agents who obtains at most $0.24$ of its own value is called sad. By inspection of the construction of the Clause-Gadget it follows that at least one of the three agents must be sad. Indeed, it is easy to check that if $C_{i}^{1}$ is not sad, then at least one of the other two must be. The fact that any Clause-Gadget must have at least one sad agent will be used to encode the fact that any clause of the 3-sat instance must have at least one literal set to $1$. Thus, if $C_{i}^{k}$ is sad, this means that we set the literal corresponding to $C_{i}^{k}$ to have the value $1$.

In any $\varepsilon$-envy-free allocation for this instance, every agent obtains a nonzero value.

If there exists an $\varepsilon$-envy-free allocation in which agent $S_{0}$ gets the leftmost piece, then the 3-sat formula is satisfiable.

In any $\varepsilon$-envy-free allocation in which agent $S_{0}$ gets the leftmost piece, the piece allocated to $S_{0}$ will be a strict prefix of $I_{0}\cup I_{0}=$. Indeed, if $S_{0}$ were allocated all of $$, then agent$S_{0}^{\prime}$would have envy$1$. It follows that agent$S_{0}$will obtain value at most$1/7$. As a result, the three blocks of value$2/7$of$S_{0}$must each contain at least one cut. Also, note that the Initiation Interval$I_{0}$ contains at least two cuts.

We now know that the two blocks of value of $S_{0}$ in $I_{1}$ and $I_{1}$ must each contain a cut. We show that agent $S_{1}$ must be allocated some interval in $I_{1}$. Suppose for the sake of contradiction that this is not the case. Then, some agent $X_{0}$ must be allocated an interval in $I_{1}$, since there are at least two cuts inside $I_{1}$. But this agent cannot be $S_{0}$ or $S_{1}$, so it will obtain value . However, by Claim 1, this is impossible.

Thus, $S_{1}$ must be allocated some interval in $I_{1}$. It follows that $S_{1}$ obtains value at most $0.2$. This, in turn, implies that the two blocks of value $0.4$ of $S_{1}$ in $I_{2}$ must each contain a cut. This means that we can repeat the argument above to show that $S_{2}$ must be allocated an interval in $I_{2}$. By induction it follows that every Isolating Interval contains at least $2$ cuts. Thus, we have shown that at least $2+2(m+n-1)=2m+2n$ cuts do not lie inside any Clause- or Variable-Gadget. This means that at most $(4m+3n)-(2m+2n)=2m+n$ cuts lie strictly inside a Clause- or Variable-Gadget, and so the Isolation property holds. By Lemma 4.2, any $\varepsilon$-envy-free allocation in which $S_{0}$ gets the leftmost piece will yield a satisfying assignment to the 3-sat instance. ∎

We define the standard ordering of allocation as follows. Starting from the left, the first piece goes to agent $S_{0}$ and the second piece to $S_{0}^{\prime}$. The rest of the agents are ordered according to the order of appearance of their gadget in the instance. For this purpose, we treat every Isolating interval $I_{k}$ as a gadget with corresponding agent $S_{k}$. Within the Clause-Gadget for $C_{i}$, the corresponding agents appear in the order $C_{i}^{1}$, $C_{i}^{2}$, $C_{i}^{3}$. Within the Variable-Gadget for $x_{j}$, the corresponding agents appear in the order $L_{j}$, $R_{j}$. This yields a unique full ordering of all the agents in the instance.

If the 3-sat formula is satisfiable, then there exists an envy-free allocation in which the pieces are allocated to the agents according to the standard ordering.

Given a satisfying assignment, we show how to construct an envy-free allocation such that the pieces are allocated to the agents according to the standard ordering. Place a cut at position $1$ and through the middle of every block of $S_{0}$ of value $2/7$. Also place a cut through the middle of every block of value $0.4$ of $S_{k}$, $1\leq k\leq m+n-2$. Allocate the leftmost piece to $S_{0}$ and the next piece to $S_{0}^{\prime}$. Allocate the piece between the two cuts in the Isolating interval $I_{k}$ to agent $S_{k}$. Note that no matter how we allocate the remaining parts of the cake, the agents $S_{0}^{\prime}$, $S_{0}$, $S_{1}$, $\dots$, $S_{m+n-1}$ will definitely be envy-free. $S_{0}^{\prime}$ and $S_{m+n-1}$ have obtained all of their value. $S_{0}$ has obtained value $1/7$, but its three blocks of value $2/7$ have all been cut in half. Finally, for $1\leq k\leq m+n-2$, $S_{k}$ has obtained value $0.2$, but its two blocks of value $0.4$ have also been cut in half. Figure 3 shows the positions of the cuts in $I_{0}$, $I_{1}$ and $I_{2}$.

Depending on whether $x_{j}=1$ or $\overline{x}_{j}=1$ place a cut in the middle of the region corresponding to $x_{j}$ or $\overline{x}_{j}$ respectively inside the Variable-Gadget of $x_{j}$. Allocate the left piece to $L_{j}$ and the right piece to $R_{j}$. Note that $L_{j}$ and $R_{j}$ obtain all of their value.

Finally, for every clause $C_{i}$ pick one of its literals that is $1$ and let $C_{i}^{k}$ be the associated agent. We position two cuts inside the gadget such that $C_{i}^{k}$ gets one block of its own value, and the other two Clause-Gadget agents each get two blocks of their own value. While doing so, we also ensure that these other two agents each get one of the two remaining blocks of $C_{i}^{k}$ inside the gadget. Note that this is always possible and in fact we can also ensure that the three pieces are allocated to the agents $C_{i}^{1},C_{i}^{2},C_{i}^{3}$ in that order from left to right. $C_{i}^{k}$ has thus obtained value $0.24$ and its two other $0.24$-blocks have been allocated to two distinct agents. The last remaining block, which has value $0.28$ and lies in the corresponding Variable-Gadget, has been cut in half according to the procedure above describing how to place the cut in a Variable-Gadget. Thus, $C_{i}^{k}$ is envy-free. Now consider any of the two other agents of this Clause-Gadget. Such an agent has obtained $0.48$ of its value. $0.24$ of its value has been allocated to other agents in this Clause-Gadget, and $0.28$ of its value has been allocated to Variable-Gadget agents. Thus, this agent is also envy-free. ∎

Using these two claims we immediately obtain that the decision problems 1, 2, and 3 are NP-hard (with envy-freeness or $\varepsilon$-envy-freeness).

Fixing cuts.

In any $\varepsilon$-envy-free allocation in which there is a cut at position $1$, the leftmost piece must be assigned to agent $S_{0}$.

Since there is a cut at position $1$, the leftmost piece can only contain value for agent $S_{0}$. Thus, by Claim 1 it cannot be allocated to any other agent. ∎

On the other hand, given a satisfying assignment for the 3-sat formula, we can always ensure that the corresponding envy-free allocation that we construct has a cut at position $1$. In fact, there are many more cuts that are fixed (and do not depend on what the satisfying assignment is), namely, the two cuts in each Isolating interval.

Using this observation along with the claim above, we get that the decision problems 4, 5, and 6 are NP-hard (with envy-freeness or $\varepsilon$-envy-freeness).

Hardness for Indivisible Items

We now turn to a discrete analog of cake cutting, where we wish to allocate a set of indivisible items that lie on a line subject to the requirement that each agent must receive a contiguous block. As in cake cutting, we assume that the valuations of the agents over the items are additive, and that all items must be allocated. Besides envy-freeness, we consider the classical fairness notions of proportionality and equitability. An allocation is proportional if every agent receives value at least $1/n$ times her value for the whole set of items, and equitable if all agents receive the same value.

Unlike in cake cutting, for indivisible items there may be no allocation satisfying any of the three fairness properties, e.g., when two agents try to divide a single item. Bouveret et al. (2017) showed that deciding whether an envy-free allocation exists is NP-hard for additive valuations, and the same is true for proportionality; they did not consider equitability. In this section, we extend and strengthen their results in several ways. We consider binary valuations, which are additive valuations such that the value of each agent for each item is either or $1$. In other words, an agent either “wants” an item or not. Even though binary valuations are much more restricted than additive valuations, as we will see, several problems still remain hard even for this smaller class.

First, we show that deciding whether a fair allocation exists is NP-hard for each of the three fairness notions mentioned. This hardness result holds for any non-empty combination of the three notions and even if all agents want the same number of items. Moreover, we present a reduction that establishes the hardness for all combinations in one fell swoop. We remark that the techniques of Bouveret et al. (2017) do not extend to the binary domain because each agent can have different values for different items in their construction. One may try to fix this by breaking items into smaller items to obtain a binary valuation, but each agent will require a different way of breaking items, and moreover there will be allocations in the new instance that cannot be mapped back to those in the original instance.

and let $\emptyset\neq X\subseteq F$. Deciding whether an instance with indivisible items on a line admits a contiguous allocation satisfying all properties in $X$ is NP-hard, even if all agents have binary valuations and value the same number of items.

We prove this result with a single reduction. Let $I$ be an instance of 3-SAT with $m$ clauses $C_{1},\dots C_{m}$ using the variables $x_{1},\dots,x_{n}$ and their negations. We create the following gadgets.

We combine these gadgets to create the instance $R$ as follows. Starting from the left, construct the Clause-Gadget for each clause $C_{i}$. Then, construct the Variable-Gadget for each variable $x_{j}$. Thus, we obtain an instance with $3m+2n$ agents and $4m+(5n+6m)=5n+10m$ items.

Any contiguous allocation in $R$ where every agent gets at least two items they value yields a satisfying assignment for $I$. This holds even if the allocation is partial, i.e., some items are not allocated.

Any satisfying assignment for $I$ yields a contiguous envy-free allocation in $R$ where every agent gets exactly two items they value.

The final step of the proof is to introduce one last gadget. The Special-Gadget creates $3m+2n+7$ new agents. We denote the set of these new agents by $N$. The gadget consists of $2(3m+2n)+14=6m+4n+14$ new items. These items are valued by all agents in $N$. For every $i\in[m]$ and $k\in$, $C_{i}^{k}$ values all new items except the rightmost six. For every $j\in[n]$, $X_{j}$ and $\overline{X}_{j}$ value all new items except the rightmost four.

The Special-Gadget is added to the right end of $R$ and yields the final instance $R^{\prime}$. Note that in $R^{\prime}$ there are $6m+4n+7$ agents and every agent values exactly $6m+4n+14$ items. Now consider any contiguous allocation for $R^{\prime}$.

If the allocation is proportional, then every agent gets at least $\lceil(6m+4n+14)/(6m+4n+7)\rceil=2$ items they value. It follows that the agents in $N$ get all the new items, because $2|N|=2(3m+2n+7)=6m+4n+14$. This means that the other agents get at least two items they value in $R$. By the claim above, we obtain a satisfying assignment.

If the allocation is equitable, then all agents get exactly $s$ items they value, for some $s\geq 0$. The Special-Gadget contains an item (in fact, many) that is valued by all agents. Since this item will be allocated to someone, $s=0$ is not possible. Also $s\geq 3$ is not possible, because the $3m+2n+7$ agents in $N$ all like the exact same $2(3m+2n+7)$ items. Now, since all $6m+4n+7$ agents value the first $(6m+4n+14)-6=6m+4n+8$ items in the Special-Gadget, at least one of them will be allocated to two of those (by the pigeonhole principle). It follows that $s=1$ is also impossible. Thus, only $s=2$ remains, and we again obtain a satisfying assignment by the claim.

Since envy-freeness implies proportionality, it follows that any $X$-allocation for $R^{\prime}$ yields a satisfying assignment for the 3-SAT instance $I$, for any non-empty $X\subseteq\{$envy-free, proportional, equitable$\}$. On the other hand, any satisfying assignment for the 3-SAT instance yields an envy-free and equitable allocation for $R^{\prime}$, by assigning two contiguous Special-Gadget items to each agent in $N$ and then using the claim. ∎

In the construction used for our proof of Theorem 5.1, each agent values at most four contiguous block of items. In light of this result, one may naturally wonder whether the hardness continues to hold if, for example, every agent values a single block of items. We show that this is the case for proportionality, provided that we drop the requirement that all agents value the same number of items. Note that if each agent values a contiguous block of items and all agents value the same number of items, deciding whether a proportional allocation exists can in fact be done in polynomial time. Indeed, we can view the problem as a scheduling problem on a single machine, with each agent having a task to be completed by a machine. For a given task, its release time is where the corresponding agent’s valued block starts, its deadline is where the block ends, and its length is the number of items that we need to give the agent in order to satisfy proportionality. When all tasks have the same length, which is true in our setting, polynomial-time algorithms have been proposed by Simons (1978) and Garey et al. (1981).

Deciding whether an instance with indivisible items on a line admits a contiguous proportional allocation is NP-hard, even if the valuations are binary and every agent values a contiguous block of items.

We reduce from the 3-partition problem. An instance of the 3-partition problem consists of $3n$ positive integers $x_{1},\dots,x_{3n}$ with sum $nB$, and the goal is to partition them into $n$ sets of size three each so that the three numbers in each set sum to $B$. The problem is NP-hard, and remains so when $B/4<x_{i}<B/2$ for all $i$ (Garey and Johnson, 1979).

Given an instance of 3-partition, we create an instance of our problem as follows. There are $m:=n(B+1)+4nk^{2}$ items on the line, where $k=4B$. Each item belongs to one of the three types: special, normal, and dummy. From left to right, the last $4nk^{2}$ items are dummy items. The remaining $n(B+1)$ items are partitioned into $n$ blocks of size $B+1$—the leftmost item of each block is a special item (so $n$ special items in total), and the remaining $B$ items of the block are normal items (so $nB$ normal items in total). There are $n^{\prime}:=4n(k+1)$ agents: $n$ special, $3n$ normal, and $4nk$ dummy. Each of the $n$ special agents values a distinct special item and nothing else. Each dummy agent values all dummy items and nothing else. For $1\leq i\leq 3n$, the $i$th normal agent values the leftmost $n^{\prime}x_{i}$ items. Note that this is well-defined because $n^{\prime}x_{i}<2n(k+1)B<4nkB=nk^{2}<m$. Moreover, $n^{\prime}x_{i}>n(k+1)B>2nB>n(B+1)$, so each normal agent values all normal items (along with other items).

First, suppose that there is a valid solution to the 3-partition instance. We construct a proportional allocation. Give each special agent her valued item, and each dummy agent $k$ consecutive dummy items. For each part $\{x_{a_{1}},x_{a_{2}},x_{a_{3}}\}$ in the solution to the 3-partition instance, we pick a block of $B$ normal items and give $x_{a_{i}}$ consecutive items to the $a_{i}$th normal agent. One can check that the resulting allocation is proportional; in particular, each dummy agent needs at least $\left\lceil\frac{4nk^{2}}{n^{\prime}}\right\rceil=\left\lceil\frac{4nk^{2}}{4n(k+1)}\right\rceil=k$ valued items, and that is exactly what they get.

Conversely, suppose that our construction admits a proportional allocation. In this allocation, each special agent must get her valued item and, as above, each dummy agent needs at least $k$ valued items. Since there are $4nk$ dummy agents and they value the same $4nk^{2}$ items, each dummy agent must receive exactly $k$ valued items. This leaves only the $nB$ normal items to be allocated to the $3n$ normal agents. Normal agent $i$ needs to get at least $x_{i}$ items, so given that $\sum_{i=1}^{3n}x_{i}=nB$, all normal items must be allocated to the normal agents, and normal agent $i$ must receive exactly $x_{i}$ items. Finally, since $B/4<x_{i}<B/2$ for all $i$, each block of $B$ normal items is allocated to exactly three agents. Hence the allocation yields a valid solution to the 3-partition instance, as desired. ∎

Next, we show that under the same conditions as Theorem 5.2, deciding whether there exists a proportional and equitable allocation, or an equitable allocation that gives the agents positive value, are both computationally hard. Since agents do not all value the same number of items (unlike in Theorem 5.1), we normalize the valuations so that if agent $i$ values $x_{i}$ items, she has value $1/x_{i}$ of each of them (so her total value is $1$).

Deciding whether an instance with indivisible items on a line admits

a contiguous allocation that is both proportional and equitable;

a contiguous equitable allocation in which the agents receive positive value

are both NP-hard, even if the valuations are binary and every agent values a contiguous block of items.

The reduction is similar to the one in Theorem 5.2. We again reduce from 3-partition, but this time we also assume that $x_{i}>n$ for all $i$. Note that we can ensure that this is the case by multiplying all $x_{i}$ and $B$ by $n$.

Let $K=nB$. The main building block of this reduction is a $K$-block: $K$ consecutive items with $K$ agents who only value these $K$ items. The instance is constructed as follows. Starting from the left end of the line, there are $B$ consecutive $K$-blocks. Note that each $K$-block has its own $K$ agents. We call this the “left region” of the instance. The “right region” of the instance consists of $n$ blocks of $K+B$ items each. The leftmost $K$ items of such a block form a $K$-block, and there are $B$ items to the right of that $K$-block. Finally, we introduce new agents $a_{1},\dots,a_{3n}$. For each $i\in[3n]$, agent $a_{i}$ values the $Kx_{i}$ rightmost items on the line. Note that this is well-defined, since there are $BK+n(K+B)\geq BK\geq Kx_{i}$ items overall. Furthermore, agent $a_{i}$ values all items in the right region, because $Kx_{i}\geq n(K+B)$ (since $K=nB$ and $x_{i}>n$). Note that every agent values a contiguous block of items.

Now consider any equitable allocation in which the agents receive positive value. Every agent must get at least one item that they value. Consider any $K$-block. Since its $K$ agents only value these $K$ items, it follows that they each obtain exactly one. Thus, they each get value exactly $1/K$, and all other agents in the instance must also get value exactly $1/K$. This means that agent $a_{i}$ must obtain exactly $x_{i}$ of its valued items. Since $B/4<x_{i}<B/2$ for all $i$, each block of $B$ items in the right region are allocated to exactly three agents $a_{i}$. Hence, we obtain a solution to the 3-partition instance. Note that a proportional and equitable allocation yields positive value to the agents, so it also gives rise to a solution to the 3-partition instance.

Conversely, given a solution to the 3-partition instance, one can construct an equitable allocation in which the agents receive positive value by following the previous paragraph. Note that this allocation is also proportional, since each agent receives value $1/K$ and there are more than $K$ agents. This completes the proof. ∎

Finally, we consider approximate envy-freeness for the discrete setting as well. We show that for a sufficiently small constant $\varepsilon$, deciding whether there exists an $\varepsilon$-envy-free allocation is NP-hard; this holds even if we restrict the valuation functions as in Theorem 5.1.

For any $\varepsilon<1/13$, deciding whether a contiguous $\varepsilon$-envy-free allocation exists is NP-hard, even if all agents have binary valuations and value the same number of items.

Consider an instance of 3-SAT with $m$ clauses $C_{1},\dots,C_{m}$ using the variables $x_{1},\dots,x_{n}$ and their negations. We will make use of the following gadgets:

Isolation-Gadget: An Isolation-Gadget consists of $13$ items and $5$ agents. The $5$ agents value each of the $13$ items and no other items in the instance.

The instance is then constructed as follows. Starting from the left, we construct the Clause-Gadget for $C_{1}$, then for $C_{2}$, and so on up to $C_{m}$. Then, we construct the Variable-Gadget for $x_{1}$, for $x_{2}$, and so on up to $x_{n}$. Finally, we introduce an Isolation-Gadget between any two adjacent gadgets. Thus, there are $m+n-1$ Isolation-Gadgets, and the instance has $3m+2n+5(m+n-1)=8m+7n-5$ agents.

Note that in this construction every agent values exactly $13$ items. Since all of the valuations are binary, this means that for the normalized valuations, any $\varepsilon$-envy-free allocation with $\varepsilon<1/13$ must actually be (exactly) envy-free.

Finally, any Isolation-Gadget must strictly contain at least $6$ cuts. It is easy to see that it must contain at least $4$ cuts, so that each of the $5$ agents that values all of the $13$ items can obtain something. However, $4$ cuts are not enough, because the $5$ resulting pieces cannot contain exactly the same number of items and thus one of the $5$ agents would not be envy-free. It turns out that $5$ cuts are also not enough. Indeed, in that case there are $6$ pieces and $5$ of those must be given to the $5$ agents of the gadget. However, it is impossible to divide $13$ items into $6$ pieces in such a way that $5$ of the pieces contain the same number of items and the $6$th piece contains at most that many items.

Since the instance has $8m+7n-5$ agents, there are $8m+7n-6$ cuts. With the arguments above we have accounted for exactly $2m+n+6(m+n-1)=8m+7n-6$ cuts. It follows that every Clause-Gadget strictly contains exactly $2$ cuts and every Variable-Gadget strictly contains exactly $1$ cut. Thus, similarly to the divisible case, we have ensured that a certain Isolation property holds. The proof that this allocation yields a satisfying assignment for the 3-SAT instance is analogous to the divisible case (Lemma 4.2).

Conversely, given a satisfying assignment of the 3-SAT instance, it is not hard to construct an envy-free contiguous allocation for the instance. In fact, the only difference from the divisible case is with respect to the Isolation-Gadgets. Here, the $6$ cuts inside every Isolation-Gadget are placed as follows: place a cut after the first item, then a cut every two items, and give the $5$ central pieces of size $2$ to the $5$ agents of the gadget. ∎

Connections Between Various Cake-Cutting Problems

In this section, we uncover several new connections between different cake-cutting settings. In particular, in Section 6.1 we show that for piecewise constant valuations, finding an approximate envy-free allocation is as hard as finding an exact one. Then, in Section 6.2 we exhibit connections between a number of continuous and discrete cake-cutting problems.

We begin by proving the following result, which relates approximate and exact envy-freeness for a restricted yet quite expressive class of valuations.

For piecewise constant valuations, computing a contiguous envy-free allocation reduces to computing a contiguous $\varepsilon$-envy-free allocation for a sufficiently small $\varepsilon$ (which may depend on the number of agents and the valuations).

In particular, this means that for such valuations there always exists a contiguous envy-free allocation in which all cut points are rational.This is not the case for more general valuations (Stromquist, 2008). Theorem 6.1 is implied by the following result:

Let $v_{1},\dots,v_{n}$ be (explicit, normalized) piecewise constant valuations, and $M\geq 3$ and $k$ be positive integers such that