{'fraction_non_alphanumeric': 0.041903548323858064, 'fraction_numerical': 0.015111416062210024, 'mean_word_length': 3.844717055797388, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results strengthening those from prior work.


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 and has received attention from mathematicians, economists, and computer scientists alike (Brams and Taylor, 1996;Robertson and Webb, 1998;. 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). 1 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.

Our Contributions
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 [0, 1] 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 cakecutting 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 envyfree 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.
Finally, 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. 2 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 valuations 3 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 nonbinary valuations. In addition, we prove that when the valuations are binary and every agent values a contiguous block of items, deciding whether a contiguous proportional allocation exists is also NP-hard.

Further Related Work
Since the seminal work of Stromquist (1980Stromquist ( , 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, Qi, and Saberi (2012) showed that contiguous envy-free cake cutting is PPAD-complete; however, the result requires non-standard (e.g., non-additive) valuation functions. Aumann, Dombb, and Hassidim (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á, Doboš, and Pillárová (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, Hassidim, and Aumann (2016) circumvented Stromquist (1980)'s impossibility result by presenting bounded-time contiguous envyfree algorithms that may not allocate the entire cake but guarantee every agent a certain positive fraction of their value. 4 Contiguity has recently been studied in a more general model where the cake can be represented by an arbitrary graph .
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. Like in cake cutting, contiguity has been studied for indivisible items in the more general model where the items lie on an arbitrary graph (Bouveret et al., 2017;Igarashi and Peters, 2019;. 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, Qi, and Saberi, 2012;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, . . . , n}. In our cake cutting setting, we consider the cake as the interval [0, 1]. There are n agents whose preferences over the cake are represented by valuation functions v 1 , . . . , v n . Assume that these valuation functions are non-negative density functions over [0, 1]. We abuse notation and let 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 ∈ [n].
A contiguous allocation of the cake is a partition of [0, 1] 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 ≤ x 1 ≤ x 2 ≤ · · · ≤ x n−1 ≤ 1 and a permutation π : [n] → [n] that assigns the intervals to the agents so that agent i receives the interval [x π(i)−1 , x π(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, π) is envy-free if for all i, j ∈ [n], we have v i (x π(i)−1 , x π(i) ) ≥ v i (x j−1 , x j ). In some cases we will be interested in finding a contiguous allocation that is only approximately envyfree. For ε ∈ [0, 1], the contiguous allocation (x, π) is ε- In other words, any agent has envy that is at most a fraction ε 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, α and asks agent i to return the leftmost point y such that v i (x, y) = α. 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 [0, 1], 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 0.

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. if v i (ℓ, 1) ≥ 1/3 then 8: r i ← leftmost point such that v i (ℓ, r i ) = 1/3 9: else 10:  While Algorithm 1 can be implemented for general val-uations 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. Theorem 3.1. 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.
Proof. Every agent receives a single interval from the algorithm; the only possible exception is agent j in line 19. However, since j is chosen as the last agent removed from N , the interval M j allocated to j earlier is adjacent to [ℓ, 1], meaning that j also receives a single interval. Hence the allocation is contiguous. Moreover, the algorithm only needs to make queries in lines 5, 7 and 8, and the number of necessary queries is clearly polynomial in n. The remaining steps can be implemented in polynomial time.
We now prove that the envy of an agent i towards any other agent is at most 1/3. If i is assigned a piece in the while loop (line 5), i receives value at least 1/3. This means that i's value for any other agent's piece is at most 2/3, so i's envy is no more than 1/3. Alternatively, after the while loop, i still has not received a piece, meaning that N = ∅ in line 14. By our allocation procedure in the while loop, i values any piece assigned in the while loop at most 1/3. Furthermore, when the algorithm enters line 14, i values the interval [ℓ, 1] less than 1/3. Since [ℓ, 1] is assigned to an agent who did not receive an interval earlier, it follows that i does not envy any other agent more than 1/3, as claimed.
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 ε > 0, a contiguous ε-envy-free allocation can be found using O(n/ε) queries, which is polynomial in n for constant ε. Their algorithm works by cutting the cake into pieces of size 1/ε 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 ε). By contrast, in the absence of the contiguity constraint, Procaccia (2016, p. 323) gave a simple polynomialtime algorithm that computes an ε-envy-free allocation for any constant ε. His algorithm also starts by cutting the cake into pieces of size 1/ε 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, 5 we show next that if the agents have piecewise uniform valuations and each agent only values a Algorithm 2 1/4-Envy-Free Algorithm for Uniform Single-Interval Valuations ⊲ R i : the single interval valued by agent i ⊲ mid(i) : the midpoint of R i ⊲ A i : part of R i that is unallocated at the start of agent i's turn ⊲ an interval is restrained if it is adjacent to an interval that has already been allocated 1: procedure APPROXIMATEEFSINGLEINTERVAL 2: Order the agents 1, . . . , n so that |R i | ≤ |R j | for all i < j 3: for i = 1, . . . , n do 4: if there exists a restrained interval I ⊆ A i with v i (I) = 1/4 and mid(i) ∈ I then ⊲ Case 1 5: else if there exists an interval I ⊆ A i with v i (I) = 1/4 and mid(i) ∈ I then ⊲ Case 2 7: Extend M q and all assigned intervals to its left as far as possible to the left.

16:
Extend M r and all assigned intervals to its right as far as possible to the right. 17: else 18: Extend assigned intervals arbitrarily to cover the remaining cake. 19: return (M 1 , . . . , M n ) 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. 6 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. gorithm 2 returns a contiguous 1/4-envy-free allocation and runs in time polynomial in n.
Proof. 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 14). 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 4), Case 2 (line 6), Case 3 (line 10) or Case 4 (line 12). 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 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 ) ≤ 1/4 for all i. Since M i ⊆ R i and because of the way the agents are ordered, it follows that v i (M j ) ≤ 1/4 for all j ≤ i (1) 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 We treat the four different cases that can occur during agent i's turn.
Cases 1 and 2. In both cases, M i contains mid(i) and has i-value 1/4. This also holds for M + i ⊇ 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 3. In this case, we again have v i (M i ) = 1/4. However, this time we have mid(i) ∈ M ℓ , which implies that Thus, we need to show that the extension of M ℓ to M + ℓ increases the i-value by at most 1/4. Since M i was chosen to be adjacent to M ℓ , it suffices to show that there is at most 1/4 i-value available on the other side of M ℓ .
To this end, we prove that at the start of agent i's turn, M ℓ cannot have at least 1/4 of i-value available both on the left side and on the right side. Assume on the contrary that this is the case. Note, in particular, that M ℓ is not restrained. Thus, M ℓ was allocated in agent ℓ's turn by Case 2. We also know that i ∈ S ℓ , because mid(i), mid(ℓ) ∈ M ℓ and v ℓ (M ℓ ) = 1/4. Now there are two cases: • If i = min S ℓ , then mid(i) ∈ ∂M ℓ . But in that case, at the start of agent i's turn, there exists a restrained interval I ⊆ A i with v i (I) = 1/4 and mid(i) ∈ I. Thus, agent i would have been in Case 1 instead of 3. • If i > k = min S ℓ , then in agent k's turn, Case 1 will apply. Indeed, mid(k) ∈ ∂M ℓ and thus there is at least 1/4 of k-value available that contains mid(k) (because there is enough space for 1/4 of i-value and i > k). But if Case 1 applies, then M k will be chosen to be adjacent to M ℓ (since they both contain mid(k)), and M ℓ will not have space available on both sides when agent i's turn comes.
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 (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 < 1/2-otherwise, agent i would have fallen in Case 1 or 2. Consider any j < i: • if mid(i) ∈ 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 (SDE property) and takes over an interval of i-value at least 1/4 that contains mid(i). But then, agent i would be in Case 1 or 2.
This completes the proof.

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.
Theorem 4.1. The following decision problems are NPhard 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 left-most piece? • Does there exist an envy-free allocation in which the pieces are allocated to the n agents in the order 1, 2, . . . , 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 envyfreeness by ε-envy-freeness for any sufficiently small constant ε.
This list is not exhaustive: additional results of the same flavor can be found in the full proof (Appendix A). 7 The following proof sketch conveys the main ideas behind these results.
Proof Sketch. 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.
Let us give some insight into how this instance is constructed. Consider a 3-SAT formula C 1 ∨ · · · ∨ C m , where the C i are clauses containing 3 literals using the variables x 1 , . . . , x n and their negations. The cake-cutting instance is constructed by putting together multiple small cake-cutting instances, so-called gadgets. For every clause C i we introduce a Clause-Gadget with its three corresponding agents C 1 i , C 2 i and C 3 i . The intuition here is that C 1 i is associated to the first literal appearing in C i , C 2 i to the second one, and C 3 i to the third one. For any Clause-Gadget agent A, we let ℓ(A) denote the associated literal. The valuations of these agents inside the gadget are as shown in Figure 1. We say that the gadget operates correctly if it contains exactly two cuts and the three resulting pieces go to the three agents C 1 i , C 2 i and C 3 i . At this point we can already make a first key observation: if the gadget operates correctly, at least one of the three agents must be sad, i.e., obtain at most one out of its three blocks of value in this gadget. For every variable x j we introduce a Variable-Gadget with its two corresponding agents L j and R j . Apart from these two agents, some Clause-Gadget agents will also have a value-block inside this gadget. In more detail, all the Clause-Gadget agents that correspond to x j or x j will have a block of value inside the Variable-Gadget for x j . Figure 2 shows how the value-blocks are arranged inside the gadget. We say that the gadget operates correctly if it contains exactly one cut and the two resulting pieces go to L j and R j . There is a second key observation to be made here. Assume that all gadgets operate correctly. If some agent C k i with ℓ(C k i ) = x j (or x j ) is sad, then the value-block of C k i in the Variable-Gadget for x j has to contain a cut (otherwise C k i would be envious). Since the Variable-Gadget contains exactly one cut, it is impossible to have agents A and B with ℓ(A) = x j and ℓ(B) = x j that are both sad.
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.
Let us now see how a nice envy-free allocation yields a satisfying assignment for the 3-SAT formula. For any agent C k i that is sad, we set the corresponding literal ℓ(C k i ) to be true. This means that if ℓ(C k i ) = x j , then we set x j to be true, and if ℓ(C k i ) = x j , then we set x j to be false. The first key observation above tells us that every Clause-Gadget has at least one sad agent. Thus, this assignment of the variables ensures that every clause is satisfied. However, we have to make sure that this assignment is consistent, i.e., we never set x j to be both true and false. This consistency is enforced by the Variable-Gadget for x j and the second key observation above.
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.

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 0 or 1. In other words, an agent either "wants" an item or not. Even though binary valuations are much more restrictive 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 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. Proof. We prove this result with a single reduction. Let I be an instance of 3-SAT with m clauses C 1 , . . . C m using Figure 3: Variable-Gadget for variable x j . Every item is represented by a rectangle containing the agent(s) who value it.
the variables x 1 , . . . , x n and their negations. We create the following gadgets.
• Clause-Gadget: For every clause C i we introduce three agents: C 1 i , C 2 i , C 3 i . Each of these agents is associated with one of the three literals that appear in the clause C i . We denote by ℓ(C k i ) the literal associated with C k i . For every clause C i we construct a Clause-Gadget. The gadget consists of four contiguous items that are all valued by all three agents C 1 i , C 2 i , C 3 i , and by no one else. • Variable-Gadget: For every variable x j we introduce two agents, X j and X j , and construct a Variable-Gadget as follows (Figure 3). Starting from the left, create two items that are valued by both X j and X j (and no one else). Then, create one item that is valued only by X j . Then, for every C k i such that ℓ(C k i ) = x j , create two items that are valued only by C k i . Then, create an item that is valued by both X j and X j . Then, for every C k i such that ℓ(C k i ) = x j , create two items that are valued only by C k i . Finally, create an item that is valued only by X j .
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.
Claim. The following statements hold: • 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 envyfree allocation in R where every agent gets exactly two items they value.
Proof of Claim. Consider any (possibly partial) contiguous allocation in R where every agents gets at least two valued items. All of the items valued by X j or X j lie in the Variable-Gadget for x j . Let T denote the second item in this gadget. Note that this item must necessarily be allocated to X j or X j (and it cannot remain unallocated, even in a partial allocation). If X j obtains T , then we set a j = 1. If X j obtains T , we set a j = 0. We now claim that a is a satisfying assignment for I. Consider any clause C i and the three associated agents C 1 i , C 2 i , C 3 i . At most two of those agents can obtain their two items from the Clause-Gadget for C i . Thus, there exists k ∈ [3] such that C k i is allocated a valued item outside the Clause-Gadget. But the only other place where C k i values items is inside the Variable-Gadget for the variable of ℓ(C k i ) (the literal in clause C i corresponding to agent C k i ). Since C k i obtains an item in this gadget, one can check that the agent corresponding to the literal ℓ(C k i ) must obtain the second item in the gadget. It follows that the literal ℓ(C k i ) has value 1 in the assignment a, and thus the clause C i is satisfied by a.
Conversely, let a be any satisfying assignment for I. For every clause C i , there exists an agent C k i such that the literal ℓ(C k i ) is true in a. Allocate the four items in the Clause-Gadget for C i to the other two clause agents (two contiguous items for each). Then, C k i has only two valued items remaining, namely the ones in the Variable-Gadget corresponding to ℓ(C k i ). Allocate them to C k i . Once this is done for all clauses, we move on to the Variable-Gadget agents. Assume that a j = 1; the case where a j = 0 can be treated analogously. Then, the first two items of the Variable-Gadget for x j are allocated to X j , while X j obtains the only two remaining items that it values (which are not adjacent). However, no clause agent C k i has been allocated any item in this interval, because items there are only valued by C k i with ℓ(C k i ) = x j and those agents have been allocated items within their respective Clause-Gadget (because a j = 1); therefore we may allocate all items in this interval to X j . At this point, some items in the Variable-Gadget might still be unallocated, namely items that lie in the interval starting from the third item up to the last item not allocated to X j . If all of these items are unallocated, then allocate them all to X j . Note that the items allocated to X j are indeed contiguous. If some of these items are already allocated, then they are allocated to clause agents. Simply extend the intervals allocated to these clause agents until they form a partition of this region. This construction ensures that every agent A obtains exactly two items they value. Moreover, for every other agent B, A obtains at most two items valued by B.
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 ∈ [m] and k ∈ [3], C k i values all new items except the rightmost six. For every j ∈ [n], X j and 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 ′ . Note that in R ′ there are 6m + 4n + 7 agents and every agent values exactly 6m + 4n + 14 items. Now consider any contiguous allocation for R ′ .
• If the allocation is proportional, then every agent gets at least ⌈(6m + 4n + 14)/(6m + 4n + 7)⌉ = 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 ≥ 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 ≥ 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 ′ yields a satisfying assignment for the 3-SAT instance I, for any non-empty X ⊆ {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 ′ , 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).

Theorem 5.2. 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.
Proof. We reduce from the 3-PARTITION problem. An instance of the 3-PARTITION problem consists of 3n positive integers x 1 , . . . , 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 ′ := 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 ≤ i ≤ 3n, the ith normal agent values the leftmost n ′ x i items. Note that this is well-defined because n ′ x i < 2n(k + 1)B < 4nkB = nk 2 < m. Moreover, n ′ 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 a1 , x a2 , x a3 } in the solution to the 3-PARTITION instance, we pick a block of B normal items and give x ai 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 4nk 2 n ′ = 4nk 2 4n(k+1) = 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 3n i=1 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).

Theorem 5.3. Deciding whether an instance with indivisible items on a line admits • a contiguous allocation that is both proportional and eq-
uitable; • 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.
Proof. 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 , . . . , a 3n . For each i ∈ [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) ≥ BK ≥ Kx i items overall. Furthermore, agent a i values all items in the right region, because Kx i ≥ 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.

Conclusion
In this paper, we study the classical cake cutting problem with the contiguity constraint and establish several hardness results and approximation algorithms for this setting. It is worth noting that while our 1/3-envy-free algorithm (Algorithm 1) is simple, lowering the envy to 1/4 for the restricted class of uniform single-interval valuations (Algorithm 2) already requires significantly more work. Pushing the approximation factor down further even for this class or the class of piecewise uniform valuations while maintaining computational efficiency is therefore a challenging direction. Of course, it is possible that there are hardness results for sufficiently small constants-this is not implied by the work of Deng, Qi, and Saberi (2012), as their PPAD-completeness result relies on more complex valuation functions.
On the hardness front, we provide constructions that serve as frameworks for deriving NP-hardness results for both cake cutting and indivisible items. Nevertheless, our frameworks do not cover questions related to the utilities of the agents, for instance whether there exists a contiguous envyfree allocation of the cake in which the first agent receives at least a certain level of utility. Extending or modifying our constructions to deal with such questions is an interesting direction for future research.
A Proof of Theorem 4.1 We provide a full proof of NP-hardness for the following decision problems: 1. Does there exist an envy-free allocation in which agent 1 gets the leftmost piece?
2. Does there exist an envy-free allocation in which agents 1, 2, . . . , k get the k leftmost pieces, in that order? (for any constant k ≥ 1) 3. Does there exist an envy-free allocation in which all the agents 1, 2, . . . , n are assigned pieces in that order from left to right? 4. Does there exist an envy-free allocation such that there is a cut at position x? (x given in the input) 5. Does there exist an envy-free allocation such that the leftmost cut is at position x? (x given in the input) 6. Does there exist an envy-free allocation such that there are cuts at positions x 1 , . . . , x k ? (x 1 , . . . , x k given in the input, k any constant) The problems remain NP-hard if we replace envy-freeness by ε-envy-freeness for any ε ≤ 0.01.
Remark. 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 kth piece from the left (k ≥ 1 constant)" or to "the k leftmost cuts are at positions x 1 , . . . , x k ".
Let I be an instance of 3-SAT with m clauses C 1 , . . . , C m , where each clause is made out of 3 literals using the variables x 1 , . . . , 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 ε ≤ 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 [0, 1]. This is just for convenience as it is easy to obtain a completely equivalent instance on [0, 1] 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 [0, 1]). 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 [0, 1]), 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 1 i , C 2 i and C 3 i . The interpretation is that C 1 i corresponds to the first literal appearing in the clause C i , C 2 i to the second one, and C 3 i to the third one. The valuation of agent C 1 i 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 2 i and C 3 i have the same blocks as C 1 i , 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.
Variable-Gadget. For every variable x j we introduce a Variable-Gadget in the cake cutting instance. The Variable-Gadget for x j requires an interval of length 4, say [b j , b j +4], and introduces two new agents L j and R j . L j has a block of value 1 in the subinterval [b j , b j + 1], and R j has a block of value 1 in the subinterval [b j + 3, b j + 4]. For every clause C i that contains x j (respectively x j ) in the ℓth position (ℓ ∈ {1, 2, 3}), the agent C ℓ i has a block of value 0.28 lying at the center of the subinterval [b j + 1, b j + 2] (respectively [b j + 2, b j + 3]). See the illustration in Figure 2.
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 [0,9], 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 kth Isolating Interval from the left is denoted I k . The Isolating Interval I k = [a, a + 3] is divided into three subintervals: . We also define an agent S m+n−1 that has a block of value 1 in I m+n−1 [2]. Figure 4 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 ε = 0.01. Since an envy-free allocation always exists, the cake-cutting instance we have constructed admits an envy-free allocation (in particular also ε-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 ε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. Lemma A.1. Any ε-envy-free allocation that satisfies the Isolation property yields a satisfying assignment for the 3-SAT formula.
Proof. Consider any ε-envy-free allocation. If there is at most one cut strictly inside the Clause-Gadget of C i , then there is an agent C k i (k ∈ {1, 2, 3}) who does not obtain any of its value from this Clause-Gadget. Thus, agent C k i 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 k i 's valuation, which contradicts ε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 > ε. Thus, every Variable-Gadget strictly contains at least one cut. Now consider an ε-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 > ε. Similarly, since there are exactly two cuts strictly inside the Clause-Gadget of C i , the three resulting parts must go to agents C 1 i , C 2 i and C 3 i . Indeed, if one of these three agents does not get one of the three parts, the agent would have value 0 (as she cannot get any value from the corresponding variable gadget) and therefore have envy at least 0.24 > ε.
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 1 i , C 2 i and C 3 i . 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 1 i 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 k i is sad, this means that we set the literal corresponding to C k i to have the value 1. It remains to check that this is consistent, i.e., that we never set the two literals x j and x j to both be 1. In other words, we have to check that if some agent C k i corresponding to the literal ℓ ∈ {x j , x j } is sad, then all agents corresponding to ℓ are not sad. If agent C k i is sad, then it gets value at most 0.24. Agent C k i has a block of value 0.28 in the Variable-Gadget of x j . This block must contain a cut, otherwise C k i would have envy at least 0.04 > ε. But since there is a single cut inside the Variable-Gadget, the blocks of all agents corresponding to ℓ are not cut. As a result, these agents cannot be sad.
Claim 1. In any ε-envy-free allocation for this instance, every agent obtains a nonzero value.
Proof. Assume on the contrary that some agent X 0 obtains value 0. Note that X 0 (like all agents) has a block of value at least 0.2 somewhere on the cake such that no other agent has any value there. Since the allocation is ε-envy-free, it follows that this block must be cut into slices of value at most ε. Let X 1 be an agent that is assigned one of the slices strictly contained in this block. Agent X 1 also obtains value 0, and it must also have a block of value at least 0.2 somewhere on the cake such that no other agent has any value there. This block must also be cut in slices of value at most ε, and since there are at least two slices that lie strictly inside the block, there exists such a slice that is not assigned to agent X 0 , but rather to some agent X 2 . We continue this procedure, always ensuring that we pick some agent that is not X 0 (which is always possible). Since the number of agents is finite, there exist i < j such that X i = X j . If i > 0, then one can check that we necessarily have X i−1 = X j−1 . Thus, there exists ℓ > 0 such that X 0 = X ℓ . However, this is impossible due to our choice of X ℓ , a contradiction.
Fixing the ordering of agents. Claim. If there exists an ε-envy-free allocation in which agent S 0 gets the leftmost piece, then the 3-SAT formula is satisfiable.
Proof. In any ε-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 [1] ∪ I 0 [2] = [0, 2]. Indeed, if S 0 were allocated all of [0, 2], then agent S ′ 0 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 [1] and I 1 [3] 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 0. 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 A.1, any ε-envy-free allocation in which S 0 gets the left-most 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 . 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 1 i , C 2 i , C 3 i . 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.
Claim. 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.
Proof. 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 ≤ k ≤ m + n − 2. Allocate the left-most piece to S 0 and the next piece to S ′ 0 . 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 , S 0 , S 1 , . . . , S m+n−1 will definitely be envy-free. S ′ 0 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 ≤ k ≤ 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 4 shows the positions of the cuts in I 0 , I 1 and I 2 .
Depending on whether x j = 1 or x j = 1 place a cut in the middle of the region corresponding to x j or 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 k i be the associated agent. We position two cuts inside the gadget such that C k i 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 k i 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 1 i , C 2 i , C 3 i in that order from left to right. C k i 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 k i 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 ε-envy-freeness).
Claim. In any ε-envy-free allocation in which there is a cut at position 1, the left-most piece must be assigned to agent S 0 .
Proof. 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 ε-envy-freeness).