# fair_division_of_time_multilayered_cake_cutting__b9ceb08c.pdf

Fair Division of Time: Multi-layered Cake Cutting

Hadi Hosseini1 , Ayumi Igarashi2 and Andrew Searns1

1Rochester Institute of Technology, USA 2National Institute of Informatics, Japan hhvcs@rit.edu, ayumi igarashi@nii.ac.jp, abs2157@rit.edu

We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces, for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envyfree allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We further devise an algorithm for computing proportional allocations for any number of agents when the number of layers is factorable to three and/or some power of two.

1 Introduction

Consider a group of students who wish to use multiple college facilities such as a conference room and an exercise room over different periods of time. Each student has a preference over what facility to use at different time of the day: Alice prefers to set her meetings in the morning and exercise in the afternoon, whereas Bob prefers to start the day with exercising for a couple of hours and meet with his teammates in the conference room for the rest of the day. The fair division literature has extensively studied the problem of dividing a heterogeneous divisible resource (aka a cake) among several agents who may have different preference over the various pieces of the cake [Steinhaus, 1948; Robertson and Webb, 1998; Brams et al., 2006]. These studies have resulted in a plethora of axiomatic and existence results [Barbanel, 2005; Moulin, 2004] as well as computational solutions [Procaccia, 2013; Aziz and Mackenzie, 2016b] under a variety of assumptions, and were successfully implemented in practice (see [Procaccia and Moulin, 2016; Brams and Taylor, 1996] for an overview). In the case of Alice and Bob, each facility represents a layer of the cake in a multi-layered cake cutting problem, and the question is

how to allocate the time intervals (usage right) of the facilities according to their preferences in a fair manner. One naive approach is to treat each cake independently and solve the problem through well-established cake-cutting techniques by performing a fair division on each layer separately. However, this approach has major drawbacks: First, the ﬁnal outcome, although fair on each layer, may not necessarily be fair overall. Second, the allocation may not be feasible, i.e., it may assign two overlapping pieces (time intervals) to a single agent. In our example, Alice cannot simultaneously utilize the exercise room and the conference room at the same time if she receives overlapping intervals. Several other application domains exhibit similar structures over resources: assigning nurses to various wards and shifts, doctors to operation rooms, and research equipment to groups, to name a few. In multi-layared cake cutting, each layer represents a divisible resource. Each agent has additive preferences over every disjoint (non-overlapping) intervals. A division of a multi-layered cake is feasible if no agent s share contain overlapping intervals, and is contiguous if each allocated piece of a layer is contiguous. There has been some recent work on dividing multiple cakes among agents [Cloutier et al., 2010; Lebert et al., 2013]. Yet, none of the previous work considered the division of multiple resources under feasibility and contiguity constraints. Therefore, in this setting we ask the following research question: What fairness guarantees can be achieved under feasibility and contiguity constraints for various number of agents and layers?

1.1 Our Results We initiate the study of the multi-layered cake cutting problem for allocating divisible resources, under contiguity and feasibility requirements. Our focus is on two fairness notions, envy-freeness and proportionality. Envy-freeness (EF) requires that each agent believes no other agent s share is better than its share of the cake. Proportionality (Prop) among n agents requires that each agent receives a share that is valued at least 1

n of the value of the entire cake. For efﬁciency, we consider complete divisions with no leftover pieces. Focusing on envy-free divisions, we show the existence of envy-free and complete allocations that are both feasible and contiguous for two-layered cakes and up to three agents with at most two types of preferences. These cases are particularly

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Agents (n) Layers (m) EF Prop

2 2 Thm. 1 Thm. 7 3 2 Thm. 2 Thm. 7 n m 2a, a Z+ ? Thm. 7 n m 2a3b, a Z+, b {0, 1} ? Thm. 6

Table 1: The overview of our results. assumes two types of agents preferences. indicates that existence holds without contiguity requirement. Note that when m > n, no complete and feasible (non-overlapping) solution exists.

appealing since many applications often deal with dividing a small number of resources among few agents (e.g. assigning meeting rooms). We then show that proportional complete allocations that are feasible exist for three agents and three layers and can be computed efﬁciently. Based on this, we extend this result to a more general case; speciﬁcally, we show that a proportional complete feasible allocation exists when the number of layers is factorable to a product of three and powers of two. We omit some proofs due to space constraints.1

1.2 Related Work In recent years, cake cutting has received signiﬁcant attention in artiﬁcial intelligence and economics as a metaphor for algorithmic approaches in achieving fairness in allocation of resources [Procaccia, 2013; Brˆanzei and Nisan, 2019; Kurokawa et al., 2013; Aziz and Mackenzie, 2016a]. Recent studies have focused on the fair division of resources when agents have requirements over multiple resources that must be simultaneously allocated in order to carry out certain tasks (e.g. CPU and RAM) [Ghodsi et al., 2011; Gutman and Nisan, 2012; Parkes et al., 2015]. The most relevant work to ours is the envy-free multi-cake fair division that considers dividing multiple cakes among agents with linked preferences over the cakes. Here, agents can simultaneously beneﬁt from all allocated pieces with no constraints. They show that envy-free divisions with only few cuts exist for two agents and many cakes, as well as three agents and two cakes [Cloutier et al., 2010; Lebert et al., 2013; Nyman et al., 2020]. In contrast, a multi-layered cake cutting requires non-overlapping pieces. Thus, the generalized envy-freeness notion on multiple cakes [Cloutier et al., 2010] does not immediately imply envy-freeness in our setting and no longer induces a feasible division.

2 Our Model

Our setting includes a set of agents denoted by N = [n], a set of layers denoted by L = [m], where for a natural number s N, [s] = {1, 2, . . . , s}. Given two real numbers x, y R, we write [x, y] = { z R | x z y } to denote an interval. We denote by R+ (respectively Z+) the set of non-negative reals (respectively, integers) including 0. A piece of cake is a ﬁnite set of disjoint subintervals of [0, 1]. We say that a subinterval of [0, 1] is a contiguous piece of cake. An mlayered cake is denoted by C = (Cj)j L where Cj [0, 1] is

1All missing proofs as well as the generalization of Theorem 4 can be found in the extended version [Hosseini et al., 2020].

a contiguous piece for j L. We refer to each j L as j-th layer and Cj as j-th layered cake. Each agent i is endowed with a non-negative integrable density function vij : Cj R+. For a given piece of cake X of j-th layer, Vij(X) denotes the value assigned to it by agent i, i.e., Vij(X) = P I X R

x I vij(x)dx. We assume that the valuations are normalized over layers, i.e., P j L Vij(Cj) = 1. A layered piece is a sequence X = (Xj)j L of pieces of each layer j L; a layered piece is said to be contiguous if each Xj is a contiguous piece of each layer. We assume valuation functions are additive on layers and write Vi(X) = P j L Vij(Xj). A layered contiguous piece is said to be non-overlapping if no two pieces from different layers overlap, i.e, for any pair of distinct layers j, j L and for any I Xj and I Xj , I I = . For two layered pieces X and X , we say that agent i weakly prefers X to X if Vi(X) Vi(X ). A multi-allocation A = (A1, A2, . . . , An) is a partition of the m-layered cake C where each Ai = (Aij)j L is a layered piece of the cake allocated to agent i; we refer to each Ai as a bundle of i. For a multi-allocation A and i N, we write Vi(Ai) = P j L Vij(Aij) to denote the value of agent i for Ai. A multi-allocation A is said to be contiguous if each Ai for i N is contiguous; feasible if each Ai for i N is non-overlapping. We focus on complete multi-allocations where the entire cake must be allocated. Notice that some layers may be disjoint (see Figure 1), and the number of agents must exceed the number of layers, i.e. n m; otherwise the multi-allocation will contain overlapping pieces. We illustrate our model in the following example. Example 1 (Resource sharing). Suppose that there are three meeting rooms r1, r2, and r3 with different capacities, and three researchers Alice, Bob, and Charlie. The ﬁrst room is available all day, the second and the third rooms are only available in the morning and late afternoon, respectively (see Fig. 1). Each researcher has a preference over the access time to the shared rooms. For example, Alice wants to have a group meeting in the larger room in the morning and then have an individual meeting in the smaller one in the afternoon.

Figure 1: Example of a multi-layered cake. There are three meeting rooms r1, r2, and r3 with different capacities, shared among several research groups.

Fairness. A multi-allocation is said to be envy-free if no agent envies the others, i.e., Vi(Ai) Vi(Ai ) for any pair of agents i, i N. A multi-allocation is said to be proportional if each agent gets his proportional fair share, i.e., Vi(Ai) 1

n for any i N. The following implication, which is wellknown for the standard setting, holds in our setting as well.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Lemma 1. An envy-free complete multi-allocation satisﬁes proportionality. The m-layered cuts. In order to cut the layered cake while satisfying the non-overlapping constraint, we deﬁne a particular approach for partitioning the entire cake into diagonal pieces. Consider the m-layered cake C where m is an even number. For each point x of the interval [0, 1], we deﬁne

LR(x, C) = (S m

2 j=1 Cj [0, x]) (Sm j= m

2 +1 Cj [x, 1]);

RL(x, C) = (S m

2 j=1 Cj [x, 1]) (Sm j= m

2 +1 Cj [0, x]).

LR(x, C) consists of the top-half subintervals of points left of x and the lower-half subintervals of points right of x; similarly, RL(x, C) consists of the top-half subintervals of points right of x and the lower-half subintervals of points left of x (Fig. 2). We abuse the notation and write LR(x) = LR(x, C) and RL(x) = RL(x, C) if C is clear from the context.

RL(x) j = 1

Figure 2: Examples of the partitions induced by x = 0 and x = 2

5 for a four-layered cake.

Computational model. Following the standard Robertson Webb Model [Robertson and Webb, 1998], we introduce two types of queries: those for a cake on each layer (called a short knife) and those for the entire cake (called a long knife). Short knife. Short eval query: given an interval [x, y] of the j-th layered cake Cj, evalj(i, x, y) asks agent i for its value [x, y], i.e., Vij([x, y]). Short cut query: given a point x and r [0, 1], cutj(i, x, r) asks agent i for the minimum point y such that Vij([x, y]) = r. Long knife. Long eval query: given a point x, eval(i, x) asks agent i for its value LR(x), i.e., Vi(LR(x)). Long cut query: given r [0, 1], cut(i, r) asks agent i for the minimum point x such that Vi(LR(x)) = r if such point x exists.

3 Existence of a Switching Point We start by showing the existence of a point x that equally divides the entire cake into two pairs of diagonal pieces, both for the individuals and for the majority; these will serve as a fundamental property in our problem. We say that x [0, 1] is a switching point for agent i over a layered cake C if Vi(LR(x)) = Vi(RL(x)). Lemma 2. Suppose that the number m of layers is even. Take any i N. Let r R be such that (i) Vi(LR(0)) r and Vi(RL(0)) r, or (ii) Vi(LR(0)) r and Vi(RL(0)) r. Then, there exists a point x [0, 1] such that i values LR(x) exactly at r, i.e. Vi(LR(x)) = r. In particular, a switching point for i always exists.

Proof. Suppose that Vi(LR(0)) r and Vi(RL(0)) r. Consider the function f(x) = Vi(LR(x)) for x [0, 1]. Recall that f(x) is a continuous function written as the sum

of continuous functions: f(x) = P m

2 j=1 Vij(Cj [0, x]) + Pm j= m

2 +1 Vij(Cj [x, 1]). Since f(0) r and f(1) r, there is a point x [0, 1] with f(x) = r by the intermediate value theorem, which proves the claim. Further, by taking r = 1

2, the point x where Vi(LR(x)) = 1

2 is a switching point for agent i.

We will generalize the notion of a switching point from the individual level to the majority. For layered contiguous pieces I and I , we say that the majority weakly prefer I

to I (denoted by I m I ) if there exists S N such that |S| n

2 and each i S weakly prefers I to I . We say that x [0, 1] is a majority switching point over C if

LR(x) m RL(x) and RL(x) m LR(x). The following lemma guarantees the existence of a majority switching point, for any even number of layers and any number of agents. Lemma 3. Suppose that the number m of layers is even. Then, there exists a majority switching point for any number n m of agents.

4 Envy-free Multi-layered Cake Cutting Now we will look into the problem of obtaining complete envyfree multi-allocations, while satisfying non-overlapping constraints. When there is only one layer, it is known that an envyfree contiguous allocation exists for any number of agents under mild assumptions on agents preferences [Stromquist, 1980; Su, 1999]. Given the contiguity and feasibility constraints, the question is whether it is possible to guarantee an envy-free division in the multi-layered cake-cutting model.

4.1 Two Agents and Two Layers We answer the above question positively for a simple, yet important, case of two agents and two layers. The standard protocol that achieves envy-freeness for two agents is known as the cut-and-choose protocol: Alice divides the entire cake into two pieces of equal value. Bob selects his preferred piece over the two pieces, leaving the remainder for Alice. We extend this protocol to the multi-layered cake cutting using the notion of a switching point. Alice ﬁrst divides the layered cake into two diagonal pieces: one that includes the top left and lower right parts and another that includes the top right and lower left parts of the cake. Our version of the cut-and-choose protocol is speciﬁed as follows:

Cut-and-choose protocol for n = 2 agents over a twolayered cake C: Step 1. Alice selects her switching point x over C. Step 2. Bob chooses a weakly preferred layered contiguous piece among LR(x) and RL(x). Step 3. Alice receives the remaining piece.

LR(x) RL(x)

Figure 3: Cut-and-Choose for two-layered cake

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Theorem 1. The cut-and-choose protocol yields a complete envy-free multi-allocation that is feasible and contiguous for two agents and a two-layered cake using O(1) number of long eval and cut queries.

Proof. It is immediate to see that the protocol returns a complete multi-allocation where each agent is assigned to a nonoverlapping layered contiguous piece. The resulting allocation satisﬁes envy-freeness: Bob does not envy Alice since he chooses a preferred piece among LR(x) and RL(x). Alice does not envy Bob by the deﬁnition of a switching point.

As we noted in Section 2, the existence result for two agents does not extend beyond two layers: if there are at least three layers, there is no feasible multi-allocation that completely allocates the cake to two agents.

4.2 Three Agents and Two Layers We move on to the case of three agents and two layers. We will design a variant of Stromquist s protocol that achieves envy-freeness for one-layered cake [Stromquist, 1980]: The referee moves two knives: a short knife and a long knife. The short knife moves from left to right over the top layer and gradually increases the left-most top piece (denoted by Y ), while the long knife keeps pointing to the point x, which can partition the remaining cake into two diagonal pieces LR(x) and RL(x) in an envy-free manner. Each agent shouts when the left-most top piece Y becomes at least as highly valuable as the preferred piece among LR(x) and RL(x). Some agent, say s, shouts eventually (before the left-most top piece becomes the top layer), assuming that there is at least one agent who weakly prefers the top layer to the bottom layer. We note that x may be positioned left to y; see Figure 4 for some possibilities of the long knife s locations. We will show that the above protocol works, for a special case when there are at most two types of preferences: In such cases, the majority switching points coincide with the switching points of an agent with the majority preference.

Lemma 4. Suppose that m = 2, n = 3, and there are two different agents i, j N with the same valuation V . Then, x is a majority switching point over C if and only if x is a switching point for i. An obvious implication of the above lemma is that when performing Stromquist s protocol, one can point out to a switching point of an individual, instead of a majority one. This allows the value of each piece to change continuously. For a given two-layered cake C, we write C y = (C y 1 , C2) as a two-layered cake obtained from C where the ﬁrst segment [0, y] of the top layer is removed, i.e., C y 1 = C1 \ [0, y]. For each majority switching point x over C y, we select three different agents ℓ(x), m(x), and r(x) as follows: ℓ(x) is an agent who weakly prefers LR(x, C y) to RL(x, C y); m(x) is an agent who is indifferent between LR(x, C y) and RL(x, C y); and r(x) and agent who weakly prefers RL(x, C y) to LR(x, C y).

Theorem 2. Suppose that m = 2 and n = 3. If there are two different agents with the same valuation, an envy-free complete multi-allocation that is feasible and contiguous exists.

RL(x) LR(x)

Figure 4: Moving knife protocol for three agents over a two-layered cake. Note that the position of x may appear before y.

Proof. Assume w.l.o.g. that at least one agent prefers the top layer over the bottom layer. This means that such agent weakly prefers the top layer to any of the pieces LR(z, C y) and RL(z, C y) when y = 1. Suppose that i N is one of the two different agents with the same valuations. We design the following protocol for three agents over a two-layered cake:

Moving-knife protocol for n = 3 agents over a twolayered cake C: w.l.o.g. assume that at least one agent weakly prefers the top layer (j = 1) over the bottom layer (j = 2) Step 1. The referee continuously moves a short knife from the left-most point (y = 0) to the right-most point (y = 1) over the top layer, while continuously moving a long knife pointing to a switching point over C y for i. Let y be the position of the short knife and Y be the top layer piece to its left. Let x be the position of the long knife. Step 2. The referee stops moving the short knife when some agent s shouts, i.e., Y becomes at least as highly valuable as the preferred piece among LR(x, C y) and RL(x, C y). Step 3. We allocate the shouter s to the left-most top piece Y and partitions the rest into LR(x, C y) and RL(x, C y). If s = ℓ(x), then we allocate LR(x, C y) to m(x) and RL(x, C y) to r(x). If s = m(x), then we allocate LR(x, C y) to ℓ(x) and RL(x, C y) to r(x). If s = r(x), then we allocate LR(x, C y) to ℓ(x) and RL(x, C y) to m(x).

By our assumption, some agent eventually shouts and thus the protocol returns an allocation A. Clearly, A is feasible, contiguous, and complete. Also, it is easy to see that the shouter s who receives a bundle Y does not envy the other two agents. The agents i = s do not envy s because the referee continuously moves both a short and a long knife. Finally, the agents i = s do not envy each other by the deﬁnition of a majority switching point and by Lemma 4.

In the general case, the existence question of contiguous and feasible envy-free multi-allocations deems to be challenging due to the non-monotonicity of valuations over diagonal pieces.2 However, when the contiguity requirement is relaxed, one can show the existence of envy-free feasible multi-allocations [Hosseini et al., 2020].

2See Section 6 for an extensive discussion.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

5 Proportional Multi-layered Cake Cutting

Focusing on a less demanding fairness notion, it turns out that a complete proportional multi-allocation that is feasible exists for a wider class of instances, i.e., when the number m of layers is a product of three and some power of two, and the number n of agents is at least m. Notably, we show that the problem can be decomposed into smaller instances when the number of agents is greater than the number of layers, or the number of layers is a power of two. Building up on the base cases of two and three layers, our algorithm recursively calls the same algorithm to decide on how to allocate the cake of the sub-problems. We ﬁrst proceed by showing how to solve the base case: For three layers and three agents, a feasible proportional multi-allocation exists and can be efﬁciently computed.

Theorem 3. A proportional complete multi-allocation that is feasible exists for three layers and three agents and can be computed using O(1) number of short eval queries and long eval and cut queries. Further, each bundle of the resulting multi-allocation includes at most two contiguous pieces within each layer.

We start by showing two auxiliary lemmata. We deﬁne a merge of two disjoint contiguous pieces Ij and Ij of layers j and j as replacing the j-th layered cake with the union Ij Ij and removing j -th layered cake. The merge of a ﬁnite sequence of mutually disjoint contiguous pieces (I1, . . . , Ik) can be deﬁned inductively: merge (I1, . . . , Ik 1) and then apply the merge operation to the resulting outcome and Ik. Now we observe that if there are two disjoint layers, one can safely merge these layers and reduce the problem size.

Lemma 5. Suppose that Cj and Cj are two disjoint layers of a layered cake C, and C is obtained from C by merging Cj and Cj . Then, each non-overlapping contiguous layered piece of C is a non-overlapping contiguous layered piece of the original cake C. The above lemma can be generalized further: Let C be a 2m-layered cake and x [0, 1]. We deﬁne a merge of LR(x) = (Sj)j L by merging the pair (Sj, Sj+m) for each j [m]. A merge of RL(x) can be deﬁned analogously. Such operation still preserves both feasibility and contiguity.

Corollary 1. Let C be a 2m-layered cake and x [0, 1]. Suppose that C is a m-layered cake obtained by merging LR(x, C) or RL(x, C). Then, each non-overlapping contiguous layered piece of C is a non-overlapping contiguous layered piece of the original cake C. Below, we show that each agent can divide the entire cake into n equally valued layered pieces. A multi-allocation A is equitable if for each agent i N, Vi(Ai) = 1

n. We design a recursive algorithm that iteratively ﬁnds two layers for which one has value at most 1

m and at least 1

m and removes a pair of diagonal pieces of value exactly 1

m from the two layers.

Lemma 6. For any number m of layers and any number n = m of agents with the identical valuations, an equitable complete multi-allocation that is feasible and contiguous exists and can be found using O(m2) number of short eval queries and O(m) number of long cut queries.

Proof. We denote by V = Vi the valuation function for each agent i N. Consider the following recursive algorithm D that takes a subset N of agents with |N | 1, a |L |- layered cake C , and a valuation proﬁle (Vi)i N , and returns an equitable complete multi-allocation of the layered cake to the agents. When |L | = |N | = 1, then the algorithm allocates the entire cake to the single agent. Suppose that |L | = |N | 2. The algorithm ﬁrst ﬁnds a layer j whose entire value is at most 1 m and another layer j whose entire value is at least 1

m. The algorithm D then ﬁnds a point x [0, 1] where V (Sj Sj ) = 1 m for Sj = Cj [0, x] and Sj = Cj [x, 1]; such point exists due to Lemma 2. We allocate Sj Sj to one agent and apply D to the remaining cake C with |N | 1 agents where C is obtained from merging the remaining j-th layered cake Cj \ Sj and the j -th layered cake Cj \ Sj . The correctness of the algorithm as well as the bound on the query complexity are immediate.

Equipped with Lemma 6, we will prove Theorem 3.

Figure 5: Protocol for proportionality for three agents and three layers. Alice divides the entire cake into three equally valued layered pieces I1, I2, and I3 (the left picture). Here, Ii = (Iij)j=1,2,3 for each i = 1, 2, 3 where I23 = I31 = . After allocating I1 to either Alice or Charlie, the algorithm merges I2, and I3 and applies the cut-and-choose among the remaining agents (the right picture).

Proof of Thm. 3. Suppose there are three agents: Alice, Bob, and Charlie. Our procedure for achieving proportionality on a three-layered cake works as follows. See Figure 5 for an illustration.

A protocol for proportionality for n = 3 agents over a three-layered cake C: Step 1. Alice partitions the cake into three non-overlapping layered contiguous pieces I1, I2, and I3 which she considers of equal value, using the algorithm in the proof of Lemma 6. Step 2. Assume w.l.o.g. that I1 is the piece for which Bob has value at most 1

3. Step 3. Decide on the agent who is assigned to I1 depending on the preference of Charlie. Step 3-1. If Charlie values I1 at least his proportional fair share 1

3, then allocate it to him. Step 3-2. Otherwise, allocate I1 to Alice. Step 4. Merge all the disjoint contiguous pieces in I2 and I3, respectively, and create a two-layered cake C consisting of each merge of I2 and I3. Apply the cut-and-choose protocol to C among the remaining agents.

We will ﬁrst show that the resulting multi-allocation A is proportional. Clearly, the agent who gets I1 has proportional fair share for his bundle. Further, each i of the remaining agents have value at least 2

3 for the remaining instance; thus, Vi(Ai) is at least Vi(I2)+Vi(I3)

3. Further, each bundle

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

contains at most two contiguous pieces from each layer of C: If Ai = I1, then Ai is contiguous. If Ai = LR(x, C ) for some x R, then each layer of C contains at most one contiguous piece of the original layers in C; since Ai is contiguous with respect to C , it contains at most two contiguous pieces of every distinct layer of C. A similar argument applies to the case when Ai = RL(x, C ) for some x R. Finally, it can be easily veriﬁed that each bundle Ai is non-overlapping. This completes the proof.

We are now ready to prove that a proportional complete multi-allocation exists for any n = m when m is a product of some power of 2 and 3. In essence, the existence of a majority switching point, as proved in Lemma 3, allows us to divide the problem into two instances. We will repeat this procedure until the number of layers of the subproblem becomes either 2 or 3, for which we know the existence of a proportional, feasible multi-allocation by Theorem 1 and Theorem 3.

Theorem 4. A proportional complete multi-allocation that is feasible exists for any number m of layers and any number n = m of agents where m = 2a3b for some a Z+ and b {0, 1}.

Proof Sketch. We assume without loss of generality that each layer Cj is the whole interval [0, 1] by just putting zero valuations on the part outside Cj. We design the following recursive algorithm D that takes a subset N of agents with |N | 2, a |L |-layered cake C , and a valuation proﬁle (Vi)i N , and returns a proportional complete multi-allocation of the cake to the agents which is feasible. Suppose that m = n. If m = n = 1, then we allocate the entire cake to the single agent. If m = n = 2, we run the cut-and-choose algorithm as described in the proof of Theorem 1. If m = n = 3, we run the procedure as described in the proof of Theorem 3. Now consider the case when m = n = 2a3b for some integers a 1 and b {0, 1}. Then the algorithm ﬁnds a majority switching point x over C . We let I1 = LR(x) and I2 = RL(x). By deﬁnition of a majority switching point and the fact that n is even, we can partition the set of agents N into N1 and N2 where N1 is the set of agents who weakly prefer I1 to I2, N2 be the set of agents who weakly prefer I2 to I1, and |Nk| = |N |

2 for each k = 1, 2. We apply D to the merge of Ik with the agent set Nk for each k = 1, 2, respectively. One can prove by induction on m that the complete multi-allocation A returned by D satisﬁes proportionality as well as feasibility.

It remains open whether a proportional contiguous multiallocation exists when the number of layers is three. A part of the reason is that our algorithm for ﬁnding an equitable multiallocation (Lemma 6) may not return a balanced partition: The number of pieces contained in each layered piece may not be the same when the number of layers is odd. For example, one layered piece may contain pieces from three different layers while the other two parts may contain pieces from two different layers, as depicted in Figure 5. However, we are able to avoid this problem when the number of layers is a power of two: Indeed, in such cases, proportionality, contiguity, and feasibility are compatible with each other.

Theorem 5. A proportional complete multi-allocation that is feasible and contiguous exists for any number m of layers and any number n = m of agents where m = 2a for some a Z+.

We will generalize the above theorems to the case when the number of agents is strictly greater than the number of layers. Intuitively, when n > m, then there is at least one layer whose sub-piece can be safely allocated to some agent without violating the non-overlapping constraint.

Theorem 6. A proportional complete multi-allocation that is feasible exists for any number m of layers and any number n m of agents where m = 2a3b for some a Z+ and b {0, 1}.

The proof of the above theorem together with Theorem 5 immediately implies the following.

Theorem 7. A proportional complete multi-allocation that is feasible and contiguous exists for any number m of layers and any number n m of agents where m = 2a for some a Z+.

6 Discussion

We showed that an envy-free complete multi-allocation of a two-layered cake that is both contiguous and feasible exists for two or three agents with at most two types of preferences. An interesting open problem is whether such allocation also exists for any number of agents over a two-layered cake. One might expect that the Simmon-Su s technique [Su, 1999] using Sperner s Lemma can be adopted to our setting by considering all possible diagonal pieces. However, this approach may not work because multi-layered cake-cutting necessarily exhibits non-monotonicity in that the value of a pair of diagonal pieces may decrease when the knife moves from left to right. For the case when the contiguity constraint is relaxed, one can show the existence of an envy-free feasible multiallocation, when each value density function vij is continuous: We can reduce the problem to ﬁnding a perfect allocation of a one-layered cake. The formal proof can be found in the extended version of the paper [Hosseini et al., 2020]. With respect to proportionality, one intriguing future direction is extending our positive results to any m, which requires careful consideration of contiguity and feasibility, which are often at odds with completeness. Lastly, the compatibility of the fairness notions with a more demanding efﬁciency requirement and studying its query complexity remain open in the multi-layered cake-cutting problem.

Acknowledgements

Hadi Hosseini was supported by the National Science Foundation (grant IIS-1850076). Ayumi Igarashi was supported by the KAKENHI Grant-in-Aid for JSPS Fellows no. 18J00997 and JST, ACT-X. The authors would like to thank Yuki Tamura for introducing the problem to us and for the fruitful discussions. The authors also acknowledge the helpful comments by the GAIW and IJCAI reviewers. We are grateful to an anonymous GAIW reviewer for the proof of the existence of an envy-free feasible multi-allocation in the general case.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

[Aziz and Mackenzie, 2016a] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 416 427, 2016.

[Aziz and Mackenzie, 2016b] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS), pages 454 464. ACM, 2016.

[Barbanel, 2005] Julius B Barbanel. The geometry of efﬁcient fair division. Cambridge University Press, 2005.

[Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.

[Brams et al., 2006] Steven J. Brams, Michal A. Jones, and Christian Klamler. Better ways to cut a cake. Notices of the American Mathematical Society, 53(11):1314 1321, 2006.

[Brˆanzei and Nisan, 2019] Simina Brˆanzei and Noam Nisan. Communication complexity of cake cutting. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 525 525. ACM, 2019.

[Cloutier et al., 2010] John Cloutier, Kathryn L Nyman, and Francis Edward Su. Two-player envy-free multi-cake division. Mathematical Social Sciences, 59(1):26 37, 2010.

[Ghodsi et al., 2011] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSD), pages 323 336. USENIX Association, 2011.

[Gutman and Nisan, 2012] Avital Gutman and Noam Nisan. Fair allocation without trade. In Proceedings of the 11th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pages 719 728, 2012.

[Hosseini et al., 2020] Hadi Hosseini, Ayumi Igarashi, and Andrew Searns. Fair division of time: Multi-layered cake cutting. Co RR, abs/2004.13397, 2020.

[Kurokawa et al., 2013] David Kurokawa, John K Lai, and Ariel D Procaccia. How to cut a cake before the party ends. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 555 561. AAAI Press, 2013.

[Lebert et al., 2013] Nicolas Lebert, Fr ed eric Meunier, and Quentin Carbonneaux. Envy-free two-player m-cake and three-player two-cake divisions. Operations Research Letters, 41(6):607 610, 2013.

[Moulin, 2004] Herv e Moulin. Fair division and collective welfare. MIT press, 2004.

[Nyman et al., 2020] Kathryn Nyman, Francis Edward Su, and Shira Zerbib. Fair division with multiple pieces. Discrete Applied Mathematics, 2020.

[Parkes et al., 2015] David C Parkes, Ariel D Procaccia, and Nisarg Shah. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Transactions on Economics and Computation (TEAC), 3:1 22, 2015. [Procaccia and Moulin, 2016] Ariel D. Procaccia and Herv e Moulin. Cake Cutting Algorithms, pages 311 330. Cambridge University Press, 2016. [Procaccia, 2013] Ariel D Procaccia. Cake cutting: not just child s play. Communications of the ACM, 56(7):78 87, 2013. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-cutting Algorithms: Be Fair if You Can. A. K. P.s, Ltd, 1998. [Steinhaus, 1948] Hugo Steinhaus. The problem of fair division. Econometrica, 16(1):101 104, 1948. [Stromquist, 1980] Walter Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640 644, 1980. [Su, 1999] Francis E. Su. Rental harmony: Sperner s lemma in fair division. The American Mathematical Monthly, 106(10):930 942, 1999.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)