# redividing_the_cake__9e9d80fa.pdf

Redividing the Cake

Erel Segal-Halevi Ariel University, Ariel 40700, Israel erelsgl@gmail.com

A heterogeneous resource, such as a land-estate, is already divided among several agents in an unfair way. It should be re-divided among the agents in a way that balances fairness with ownership rights. We present re-division protocols that attain various trade-off points between fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity the cake is a two-dimensional rectangle and the pieces should be rectangles; (d) convexity the cake is a two-dimensional convex polygon and the pieces should be convex.

1 Introduction

Fair division of land and other resources among agents with different preferences has been an important issue since Biblical times (see Genesis 13). Today it is an active area of research in the interface of computer science [Robertson and Webb, 1998; Procaccia, 2015] and economics [Moulin, 2004]. Its applications range from politics [Brams, 2007] to multi-agent systems [Chevaleyre et al., 2006]. The classic setting assumes a one-shot division: the resource is divided once and for all, like a cake that is divided and eaten soon after it comes out of the oven. But in practice, it is often required to re-divide an already-divided resource. One example is a cloud-computing environment, where new agents come and require resources held by other agents. A second example is fair allocation of radio spectrum among several broadcasting agencies: it may be required to re-divide the frequencies to accommodate new broadcasters. A third example is land-reform: large land-estates are held by a small number of landlords, and the government may want to redivide them to landless citizens. In the classic one-shot division setting, there are n agents with equal rights, and the goal is to give each agent a fair share of the cake. A common deﬁnition of a fair share is a piece worth at least 1/n of the total cake value, according to the agent s personal valuation function. This fairness

requirement is usually termed proportionality. When proportionality cannot be attained, it is often (see Section 6) relaxed to r-proportionality, which means that each agent receives at least a fraction r/n of the total, where r (0, 1) is constant independent of n. In contrast, in the re-division setting, there is an existing division of the cake among the n agents. This division is not necessarily fair; in particular, there may be some agents whose allocation is empty. When the cake is re-divided, it may be required to give extra rights to current holders. In particular, it may be required to give each agent the opportunity to keep a substantial fraction of its current value. This may be due either to efﬁciency reasons (in the cloud computing scenario) or economic reasons (in the radio spectrum scenario) or political reasons (in the land-reform scenario). We call this requirement ownership. Given a constant w (0, 1), wownership means that each agent receives at least w times its old value. What levels of proportionality and ownership can be attained simultaneously? Our ﬁrst two results (in Section 3) provide an almost complete answer to this question.

Proposition 1. For every constants r, w [0, 1] where r + w > 1, it may be impossible to simultaneously guarantee rproportionality and w-ownership.

Theorem 2. For every rational constants r, w [0, 1] where r+w 1, and for every existing division of the cake, there exists a division that simultaneously satisﬁes r-proportionality and w-ownership. It can be found with O(n2) queries.

As an example, taking r = w = 1/2, it is possible to re-divide the cake, giving each agent at least half its previous value, while simultaneously giving each agent at least 1/(2n) of the total cake value. The parameters r, w represent the level of balance between two principles: large r means more emphasis on fairness while large w means more emphasis on ownership rights. The above theorems imply that the re-dividers (e.g. the government) may choose any level of fairness and ownership-rights that ﬁt their ideological, political or economic goals, as long as the sum of these fractions is at most 1. The balance parameters can also be given probabilistic interpretation. Suppose the government wants to do a land reform and needs the agreement of the current landowners. Naturally, the current landowners do not want to give away their lands. However, they may fear that, without land-reform, the

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

landless citizens might revolt and they might lose all their lands. If the landowners believe that the probability of a successful revolt is 1 w, then they will agree to a land-reform that guarantees w-ownership. Theorem 2 implies that, in this case, it is possible to carry out a land-reform that guarantees (1 w)-proportionality. While Theorem 2 is encouraging, it ignores an important aspect of practical division problems: geometry. The division it guarantees may be highly fractioned, giving each agent a large number of disconnected pieces. In many practical division problems, the agents may want to receive a single connected piece. For example, when the divided resource is a time-interval, each agent may need a single contiguous interval rather than a large number of disconnected ones. Can partial-proportionality and partial-ownership be attained simultaneously with a connectivity constraint? The following proposition (proved in Section 4) answers this negatively. Proposition 3. When the cake is a 1-dimensional interval and each piece must be an interval, for every positive constants r, w (0, 1), it may be impossible to simultaneously satisfy r-proportionality and w-ownership. Moreover, for every r > 0 and every integer k {1, . . . , n}, there might be k agents who, in any rproportional division, receive at most a fraction 1/ n

k of their old value. The latter part of the proposition involves a property much weaker than proportionality: all we want is to guarantee each agent a positive value. With the connectivity constraint, even this weak positivity requirement is incompatible with wownership for every constant w > 0: a positive division might require us to give one agent at most 1/n of its previous value, give two agents at most 2/n of their previous value, give n/3 agents at most 1/3 of their previous value, etc. Proposition 3 motivates the following weaker ownership requirement: for every k, at least n k agents receive at least a fraction 1/ n

k of their old value. For example (taking k = n/3 and assuming all quotients are integers), at least 2n/3 agents should receive at least 1/3 of their old value. This criterion is inspired by the 90th percentile criterion common in Service-Level-Agreements and Quality-of-Service analysis, e.g. [Zhang et al., 2014; Delimitrou and Kozyrakis, 2014]. It can also be justiﬁed by political reasoning: in a democratic country, it may be sufﬁcient to win the support of a sufﬁciently large majority. Our following results almost match this relaxed ownership criterion. Formally, the democratic ownership property means that, for every integer k {1, . . . , n}, at least n k agents receive at least a fraction 1/ n

k of their previous value. Democratic-ownership is almost the same as the upper bound implied by Proposition 3; the only difference is that in the upper bound the fraction is rounded down (1/ n

k ) while in democratic-ownership the fraction is rounded up. Theorem 4. When the cake is a 1-dimensional interval and each piece must be an interval, it is possible to ﬁnd in time O(n2 log n) a division simultaneously satisfying democraticownership and 1/3-proportionality. It is an open question whether democratic-ownership is compatible with r-proportionality for some r > 1/3.

Theorem 4, like most cake-cutting papers, assumes that the cake is 1-dimensional. In realistic division scenarios, the cake is often 2-dimensional and the pieces should have a pre-speciﬁed geometric shape, such as a rectangle or a convex polygon. Rectangularity and convexity requirements are sensible when dividing land, exhibition space in museums, advertisement space in newspapers and even virtual space in web-pages. Moreover, in the frequency-range allocation problem, it is possible to allocate frequency ranges for a limited time-period; the frequency-time space is twodimensional and it makes sense to require that the pieces are rectangles in this space [Iyer and Huhns, 2009]. 2-dimensional cake-cutting introduces new challenges over the traditional 1-dimensional setting. As an example, in one dimension, it can be assumed that the initial allocation is a partition of the entire cake; this is without loss of generality, since any blank (unallocated part) can be attached to a neighboring allocated interval without harming its shape or value. However, in two dimensions, the initial allocation might contain blanks that cannot be attached to any allocated piece due to the rectangularity or convexity constraints. For example, suppose the cake is as the rectangle illustrated to the right.

Figure 1: Geometric constraints require us to dispose some cake.

There are 4 agents and each agent i has positive valuedensity only inside the rectangle Zi. The most reasonable division (e.g. the only Pareto-efﬁcient division) is to give each Zi entirely to agent i. But, this allocation leaves a blank in the center of the cake, and this blank cannot be attached to any allocated piece due to the rectangularity constraint. This counter-intuitive scenario cannot happen in a one-dimensional cake. Handling such cases requires new geometry-based tools. Using such tools we can handle two common 2-dimensional settings (Sec. 5):

Theorem 5. When the cake is a rectangle and each piece must be a parallel rectangle, it is possible to ﬁnd in time O(n2 log n) a division simultaneously satisfying democraticownership and 1/4-proportionality.

Theorem 6. When the cake is a 2-dimensional convex polygon and each piece must be convex, there exists a division simultaneously satisfying democratic-ownership and 1/5proportionality.

Remark 7. In the interval, rectangle and convex settings, the geometric constraints are mostly harmless without the ownership requirement: when the cake is an interval/rectangle/convex, classic algorithms for proportional cake-cutting, such as Even and Paz [1984], can be easily made to return interval/rectangle/convex pieces by ensuring that the cuts are parallel. Similarly, the ownership requirement is easy to satisfy without the geometric constraints, as shown by Theorem 2. It is the combination of these two requirements that leads to interesting challenges.

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

2 Model 2.1 Cake Division The cake C is a polytope in the d-dimensional Euclidean plane Rd. In this paper we focus on the common cases in which d = 1 and C is an interval, or d = 2 and C is a polygon. A piece is a Borel subset of C. C has to be divided among n 1 agents. Each agent i {1, . . . , n} has a value-density function vi, which is an integrable, non-negative and bounded function on C. The value of a piece Xi to agent i is marked by Vi(Xi) and it is the integral of its value-density: Vi(Xi) = R

x Xi vi(x)dx. The deﬁnition implies that the Vi are ﬁnite measures and are absolutely-continuous with respect to the Lebesgue measure, i.e., any piece with zero area has zero value to all agents. Therefore, we do not need to worry about who gets the boundary of a piece, since its value is 0. The division protocols access the value measures via queries [Robertson and Webb, 1998; Woeginger and Sgall, 2007]: an eval query asks an agent to reveal its value for a speciﬁed piece of cake; a mark query asks an agent to mark a piece of cake with a speciﬁed value. The present paper ignores strategic considerations and assumes that agents answer truthfully. Indeed, in general it may be impossible to build a cake-cutting protocol that is both fair and strategy-proof [Brˆanzei and Miltersen, 2015]. The geometric constraints, if any, are represented by a prespeciﬁed family S of usable pieces. In this paper, S will either be the set of all pieces (which means that there are no geometric constraints), or the set of all intervals, or the set of all rectangles, or the set of all convex pieces. We assume that each agent can use only a single piece from the family S. An allocation is a vector of n pieces, X = (X1, . . . , Xn), one piece per agent, such that the Xi are pairwise-disjoint and n i=1Xi C. Note that some cake may remain unallocated, i.e, free disposal is assumed. We explained in the introduction why this may be important. An S-allocation is an allocation in which all pieces are usable, i.e, i : Xi S. For every constant r (0, 1), an allocation X is called rproportional if every agent receives at least r/n of the total cake value:

i {1, . . . , n} : Vi(Xi) (r/n) Vi(C)

A 1-proportional division is also known as proportional .

2.2 Cake Redivision There is an existing S-allocation of the cake: Z1, . . . , Zn. It is assumed that the old pieces Zj are pairwise-disjoint and j : Zj S, but nothing else is assumed on the division. In particular, the initial division is not necessarily proportional, and some of C may be undivided. It is required to create a new S-allocation of C to all agents: X1, . . . , Xn. For every constant w (0, 1), the re-allocation satisﬁes the w-ownership property if every agent receives at least a fraction w of its old value:

j {1, . . . , n} : Vj(Xj) w Vj(Zj)

Since w-ownership is not always compatible with rproportionality for any r > 0, we deﬁne the following weaker

property. A re-allocation satisﬁes the democratic-ownership property if, for every k {1, . . . , n}, there are at least n k agents j {1, . . . , n} for whom:

Vj(Xj) 1 n/k Vj(Zj).

3 Arbitrary Cake and Arbitrary Pieces

In this section there are no geometric constraints on the cake or its pieces. We start with the negative result.

Proof of Proposition 1. We are given a pair r, w where r + w > 1. We show a scenario where no r-proportional division satisﬁes w-ownership. In the initial allocation, a single agent owns the entire cake. All n agents have the same value-density and they value the entire cake as 1. In any rproportional division, the n 1 landless citizens must receive a total value of (n 1)r/n = r r/n. Therefore the old landlord receives at most 1 r +r/n. By assumption, 1 r < w. Hence, if n is sufﬁciently large, the old landlord receives less than w of his previous value, contradicting w-ownership.

To prove the matching positive result we need a lemma.

Lemma 8. Given cake-allocations Z and Y and a rational constant r [0, 1], there exists an allocation X such that, for every agent i: Vi(Xi) r Vi(Yi)+(1 r)Vi(Zi). Moreover, it can be found using O(n2) queries.

Proof. Let r = p/q with p < q some positive integers. For every pair of agents i, j (including i = j), the protocol does:

Step 1. Agent i divides Zi Yj to q equal-value pieces. Step 2. Agent j takes the p best pieces in its eyes. Step 3. Agent i takes the remaining q p pieces. (Note, when i = j agent i gets the entire piece Zi Yi).

The pairs i, j can be processed in any order, even in parallel. Each agent i is allocated a piece Xi which is a union of nq pieces: np pieces that agent i took from other agents (including itself) in piece Yi and n(q p) pieces that were left for agent i from other agents in piece Zi. From every piece Yi Zj (for j {1, . . . , n}), agent i picks the best p out of q pieces, which give it a value of at least p

q Vi(Yi Zj). Its total value in these np pieces is thus at least r Vi(Yi). In addition, from every piece Zi Yj (for j {1, . . . , n}), agent i receives q p out of q equal pieces, which give it a value of exactly q p

q Vi(Zi Yj). Its total value of these n(q p) pieces is thus exactly (1 r)Vi(Zi). The three steps are done once for each pair of agents, so the number of queries is O(n2).

Proof of Theorem 2. Given a pair r, w where r + w 1, apply Lemma 8, with the initial allocation as Z, and any proportional allocation as Y (a proportional allocation can be found efﬁciently by classic protocols such as Steinhaus [1948], Even and Paz [1984]). By Lemma 8, the new division satisﬁes r-proportionality and (1 r)-ownership, and 1 r w.

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

Remark 9. The O(n2) complexity assumes the integers p, q are constant (not part of the input). If they are considered part of the input, then the complexity becomes linear in q which is exponential in the number of input bits. The number of queries can be reduced using concepts from number theory, but this is beyond the scope of this paper. See Mc Avaney et al. [1992], Robertson and Webb [1998]. Remark 10. Our redivision protocol gives each agent a piece that is not only worth at least (1 r)Vi(Zi), but also a subset of Zi (in addition to a subset of Yi). This may be desirable in some cases. E.g. in land division, old landlords may want not only a high value but also a subset of their old plot.

4 Interval Cake and Interval Pieces In this section the cake is an interval and each piece must be an interval. Again we start with the negative result.

Proof of Proposition 3. We are given an initial allocation Z, a positive constant r (0, 1), and an integer k n. We show a scenario in which, in every r-proportional allocation, the value of every agent j {1, . . . , k} is at most Vj(Zj)/ n

k . Assume that the valuations are as follows. Each agent j {1, . . . , k} values his original piece Zj as n

k and the rest of the cake as 0. The value-density of j in Zj is piecewiseuniform: It has n

k regions with a value of 1 and n

k 1 gaps regions with a value of 0. The other n k agents are divided to k groups of roughly equal size: the size of each group is either n k

k 1. Each agent in group j assigns a positive value only to a unique gap in the piece Zj (so when the group size is n

k 1, each gap is wanted by exactly one agent; otherwise, there is one gap wanted by two agents). The following ﬁgure illustrates the value-densities that are positive in piece Z1.

Figure 2: Solid boxes represent the value-density of agent #1; each dotted box represents a value-density of a single agent in group #1.

In any r-proportional division, each gap in Zj must be at least partially allocated to an agent in group j. Hence, the interval allocated to agent j must contain at most a single positive region in Zj it is not allowed to overlap any gap. Therefore the value of agent j is at most Vj(Zj)/ n

To prove the matching positive result (Theorem 4), we use a protocol for fair division of an archipelago a cake made of one or more interval islands . Lemma 11. Let C be a cake made of m 1 pairwisedisjoint intervals: C = Z1 Zm. There exists a division X of C among n agents, in which (a) Each agent i receives an interval entirely contained in one of the islands: i : j : Xi Zj, and (b) Each agent receives a value of at least Vi(C)/(n + m 1). Moreover, X can be found using O(mn log n) queries.

Proof. We normalize the valuations of all agents such that i : Vi(C) = n + m 1. We aim to give each agent a piece worth at least 1. The proof is by induction on m. When m =

1, divide the single island among all agents using the Even Paz protocol [Even and Paz, 1984]. It ﬁnds, using O(n log n) queries, a connected division in which each agent receives value at least Vi(C)/n = 1. When m > 1, pick an arbitrary island, say Z1. Pick the n agents whose valuations of Z1 are the highest, where n is chosen such that all these agents value Z1 as at least n . Divide Z1 among them using Even Paz, giving each of them value at least 1. It can be shown that the remaining n n agents value the remaining m 1 islands as at least (n n )+(m 1) 1; divide the islands recursively among them. There are m steps, so the runtime is O(mn log n).

Proof of Theorem 4. We re-divide the interval as follows.

Step 1. Given the original partial allocation Z1 Zn C, extend it to a complete allocation Z 1 Z n = C, by attaching each blank (unallocated interval in C) arbitrarily to one of the two adjacent allocated intervals. This, of course, does not harm the old values: j {1, . . . , n} : Vj(Z j) Vj(Zj). Step 2. For each agent j {1, . . . , n}, add a helper agent j and assign it a value-density function v j :

v j (x) = vj(x) if x Z j v j (x) = 0 if x / Z j

Use the protocol of Lemma 11 with n + n agents, regarding the cake C as an archipelago and the pieces Z 1, . . . , Z n as the islands. Step 3. Give each agent j {1, . . . , n} either the interval allocated to its normal agent j or the interval allocated to its helper agent j , whichever is more valuable.

We now prove that the resulting allocation is 1/3proportional and satisﬁes the democratic-ownership property. (a) Proof of 1/3-proportionality. We apply Lemma 11 with 2n agents and m = n islands. Each of the 2n agents receives an interval contained in one of the pieces Z 1, . . . , Z n, with a value of at least 1/((2n) + n 1) its total cake value. This value is larger than 1/(3n). (b) Proof of democratic-ownership. We focus on the n helper agents. First, by Lemma 11, every helper agent j must receive an interval contained in Z j, since its value is positive only in the island Zj. Moreover, by the pigeonhole principle, for every integer k n, at most k islands are populated by at least n

k normal agents. Hence, at least n k islands are populated by at most n

k 1 normal agents. Adding the helper agent, these islands are populated by at most n

k agents. Hence, the proportional allocation in Lemma 11 gives these helper agents an interval subset of Z j, which is worth for agent j at least Vj(Z j)/ n

Note that the above protocol, like the protocol of the Section 3 (see Remark 10) gives each agent an option to take a subset of his old plot the one allocated to his helper agent.

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

5 Polygonal Cake and Polygonal Pieces

Rectangle Cake and Pieces We assume that C is a rectangle in R2. Each piece Zj in the initial division is a rectangle parallel to C and each piece Xi in the new division must be a rectangle parallel to C. The Even Paz protocol can easily be adapted to this setting, by instructing each agent to make vertical cuts parallel to the rectangle s sides. Thus Lemma 11 and steps #2 and #3 in the protocol of Theorem 4 work in this setting too. The problem is that Step #1, the allocation-completion step, is no longer trivial. We cannot just attach each unallocated part of C to an allocated rectangle, since the result might not be a rectangle. We still need to extend the initial partial allocation Z1 Zn C to a complete allocation, but the number of rectangles in the complete allocation might be larger than n, since we might have unattached blanks. Our goal, then, is to ﬁnd a partition of C to rectangles, Z 1 Z n+b = C, with b 0, such that every input rectangle is contained in a unique output rectangle: j {1, . . . , n} : Zj Z j. The additional b rectangles are called blanks. In Step 3, we will have m = n + b islands and 2n agents, so the value guarantee per agent will be 1/((2n) + (n + b) 1) = 1/(3n+b 1); therefore, we would like the number of blanks b to be as small as possible. An example of the input and output of the allocation-completion step is shown below.

Figure 3: Allocation completion with b = 1 blank, denoted Z 5.

We replace step #1 with the following: Step 1 . Let i loop over the agents in an arbitrary order, e.g, i = 1, . . . , n. extend Zi in all four directions to the maximum extent without intersecting the other Zi s. By construction, the resulting arrangement is maximal no rectangle can be extended any further without overlapping other rectangles. Akopyan and Segal-Halevi [2018] show that, in any maximal arrangement, the number of rectangular blanks b is at most n 2 n O(1). Plugging this into the protocol of Theorem 4 gives a value per agent of at least 1/(4n 2 n) > 1/(4n), satisfying 1/4-proportionality and proving Theorem 5.

Convex Cake and Pieces The situation is similar when C is convex and the pieces should be convex. The Even Paz protocol can operate on a convex cake, requiring the agents to make cuts parallel to the each other. This guarantees that the pieces will be convex. In Step #1, a similar challenge arises. We have an initial partial allocation Z1 Zn C, where each Zj is convex. We need a complete allocation Z 1 Z n+b = C, where each Z j is convex, every input piece is contained in a unique output piece, and the number of blanks b is minimal.

Akopyan and Segal-Halevi [2018] prove that, for every initial allocation Z, there exist a maximal extension where the number of convex blanks b is at most 2n 5. Plugging this into the protocol of Theorem 4 gives a value per agent of at least 1/(5n 6) 1/(5n) in the convex case satisfying 1/5-proportionality and proving Theorem 6. However, we do not know how to ﬁnd this maximal extension efﬁciently; this computational-geometric question is left for future work.

6 Related Work

Dynamic Fair Division Our cake redivision problem differs from several division problems studied recently. 1. In dynamic resource allocation [Kash et al., 2013; Friedman et al., 2015], the resources are homogeneous, which means that the only thing that matters is what quantity of each resource is given to each agent. In contrast, our cake is heterogeneous and different agents may have different valuations on it, so our protocol must decide which parts of the cake should be given to which agent. 2. Population monotonicity [Thomson, 1983; Moulin, 2004; Segal-Halevi and Sziklai , 2018] is a property of a fair division rule. It requires that, when new agents arrive and the same division rule is re-activated, the value of all old agents is weakly smaller all agents should participate in supporting the newcomers. We, too, assume that old agents support new ones, but add the ownership requirement, which guarantees the old agents a fraction of their previous value. 3. Private endowment means that each agent is endowed with an initial part of cake. Then, agents exchange resources using a market mechanism [Aziz and Ye, 2014, and others]. A basic requirement in these works is individual rationality, which means that the ﬁnal value allocated to each agent must be weakly larger than the value of the initial endowment. We cannot make this assumption as it is incompatible with fairness: since some agents may initially own no land, they have nothing to give in the exchange and might remain landless. 4. Online division is a setting in which either the agents or the divided resources are not all available at the time of the division, but rather arrive in different times [Walsh, 2011; Aleksandrov et al., 2015]. It is required to give some cake to agents who come early while keeping a fair share to those who come late. In contrast to our model, there allocated resources are consumed so it it is impossible to re-divide them. 5. Land reform is the re-division of land among citizens. It has been attempted in numerous countries around the globe and in many periods throughout history [Powelson, 1988], since ancient Egypt in the times of King Bakenranef (8th century BC) to the Scotland land-reform act (2016 AD). Balancing fairness and ownership rights is a major concern in such reforms [Lipton, 2009; Sellar, 2006].

Partial Proportionality While proportionality is the most common criterion of fair cake-cutting, it is often relaxed to partial-proportionality in order to achieve additional goals: 1. Speed: ﬁnding a proportional division takes Θ(n log n) queries, but ﬁnding an r-proportional division takes only

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

Θ(n) queries, for some sufﬁciently small r 0.1 [Edmonds and Pruhs, 2006, and others]. 2. Improving social welfare: proportional allocations may be socially inefﬁcient; efﬁciency can be improved by decreasing the value-guarantee per agent [Zivan, 2011; Arzi, 2012]. 3. Minimum-size constraint: In some 1-dimensional settings, each agent may get several intervals but the length of each interval should be above a threshold. It is impossible to guarantee an r-proportional allocation for any r > 0, but additive approximations exist [Caragiannis et al., 2011]. 4. Geometric constraints: For example, when the cake is square and the pieces must be square, it is impossible to guarantee an r-proportional allocation for any r 1/2, but there is an algorithm that guarantees a 1/4-proportional allocation [Segal-Halevi et al., 2017] .

Geometric Cake Models The most prominent cake-model is a one-dimensional interval, in which case the pieces are often required to be contiguous sub-intervals. Some exceptions are: 1. The cake is a 1-dimensional circle and the pieces are contiguous arcs [Thomson, 2007, and others]. 2. The cake is a 2-dimensional territory that lies among several countries. Each country should receive a piece adjacent to its border [Hill, 1983; Beck, 1987]. 3. The cake is 2-dimensional and the pieces are rectangles determined by the agents [Iyer and Huhns, 2009]. 4. The cake is 2-dimensional and the pieces must be squares or fat polygons [Segal-Halevi et al., 2017]. 5. The cake is 2-dimensional; the geometric constraints are connectivity or convexity [Devulapalli, 2014]. 6. The cake is multi-dimensional and the pieces are simplexes or polytopes [Berliant et al., 1992; Dall Aglio and Maccheroni, 2009].

7 Future Work

7.1 Handling Other Geometric Constraints

Two steps in our redivision algorithm are sensitive to the geometric constraints: the allocation-completion (Step #1 in Theorem 4), and the Even Paz protocol (Lemma 11). We describe how these steps are affected by alternative constraints. 1. Convexity in three or more dimensions. The Even Paz protocol can easily operate on multi-dimensional boxes or other convex objects, requiring the agents to cut using hyperplanes parallel to each other. However, we currently do not have an allocation-completion algorithm for convex objects, or even for boxes, in three or more dimensions. 2. Connectivity in two dimensions. If the pieces have to be polygons that are connected but not necessarily convex, then the allocation-completion step is much easier and no blanks are created [Akopyan and Segal-Halevi, 2018]. However, it is not clear how to use the Even Paz protocol in this case: when the cake is not convex, making parallel cuts might create disconnected pieces. 3. Two pieces per agent. Theorem 2 allows an unlimited number of pieces per agent, while the other theorems allow only a single piece per agent. We do not know what happens

between these extremes. For example, if the cake is a onedimensional interval and each agent can get two intervals, what ownership-proportionality combinations are attainable?

7.2 Handling Other Fairness Requirements 1. Envy-freeness. In this paper we took proportionality as a benchmark of fairness. An alternative benchmark is envyfreeness. Envy-freeness means that each agent values its piece at least as much as each of the other pieces. Similarly, r-envy-freeness means that each agent values its piece as at least r times the value of each of the other pieces. For what pairs r, w is r-envy-freeness compatible with w-ownership? With democratic-ownership? 2. Pareto-efﬁciency. From an existential point of view, Pareto-efﬁciency does not add much difﬁculty. Both rproportionality and w-ownership are preserved by Paretoimprovements. Therefore, if there exists a division satisfying r-proportionality and w-ownership (or democraticownership), then there also exists a Pareto-optimal division satisfying these properties. However, it may not be easy to ﬁnd such a division algorithmically.

7.3 Improving the Constants Our redivision protocol is 1/3 or 1/4 or 1/5-proportional (depending on the geometric constraint). We see two potential ways to improve these numbers. 1. In Step #2 of our redivision protocol, we add n helper agents, so the total number of agents is 2n. But in the Step #3, each agent chooses either its helper or its normal agent, while the other agent is wasted . If we could know the n choices of the agents in advance, we could employ only n agents overall, subtracting 1 from the denominator of the constant (the constants would become 1/2 or 1/3 or 1/4). We may view this as a strategic game in which each agent has two possible strategies: normal vs. helper . We conjecture that a purestrategy Nash equilibrium exists in this game, and it corresponds to an allocation satisfying the partial-proportionality and democratic-ownership requirements. While ﬁnding a Nash equilibrium is usually a computationally-hard problem, it may be useful as an existential result. 2. In Lemma 11, we treat each existing piece Zj as an island and insist that each new piece be entirely contained in an existing piece, i.e, we do not cross the existing division lines. This may be desirable in the context of land division, since it respects the Uti Possidetis principle [Lalonde, 2002]. However, it may be possible to improve the proportionality guarantees by devising a different redivision procedure that crosses the existing division lines. These possibilities invoke the following open question: what is the highest level of proportionality that is compatible with democratic-ownership?

Acknowledgements

I started this work during my Ph.D. studies in Bar-Ilan university guided by Yonatan Aumann and Avinatan Hassidim [Segal-Halevi, 2017]. I beneﬁted a lot from discussions with Reuven Cohen, Panagiotis Kanellopoulos, Laszlo Csato, Herve Moulin, Yehuda Levy, Chris Culter, Varun

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

Dubey, Alex Ravsky, Swami Sarvattomananda, participants in BIU game-theory seminar, Glasgow university microeconomics seminar, Corvinus university game-theory seminar, the anonymous reviewers of AAMAS 2016, EC 2016, SODA 2017, ESA 2017 and IJCAI 2018, and above all, Galya Segal-Halevi. Thanks for all the cakes!

References [Akopyan and Segal-Halevi, 2018] Arseniy Akopyan and Erel Segal-Halevi. Counting Blanks in Polygonal Arrangements, 2018 (forthcoming). SIAM Journal on Discrete Mathematics. ar Xiv preprint 1604.00960. [Aleksandrov et al., 2015] Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online Fair Division: analysing a Food Bank problem. In Proc. IJCAI 15. [Arzi, 2012] Orit Arzi. Cake Cutting: Achieving Efﬁciency While Maintaining Fairness. Master s thesis, Bar-Ilan University, October 2012. [Aziz and Ye, 2014] Haris Aziz and Chun Ye. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations. In Proc. WINE 14, pages 1 14. [Beck, 1987] Anatole Beck. Constructing a Fair Border. American Mathematical Monthly, 94(2):157 162. [Berliant et al., 1992] Marcus Berliant, William Thomson, and Karl Dunz. On the fair division of a heterogeneous commodity. J. Math. Econ., 21(3):201 216, 1992. [Brams et al., 2008] Steven J. Brams, Michael Jones, and Christian Klamler. Proportional pie-cutting. International Journal of Game Theory, 36(3-4):353 367, March 2008. [Brams, 2007] Steven J. Brams. Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton University Press, 1st edition, 2007. [Brˆanzei and Miltersen, 2015] Simina Brˆanzei and Peter B. Miltersen. A Dictatorship Theorem for Cake Cutting. In Proc. IJCAI 15, pages 482 488. [Caragiannis et al., 2011] Ioannis Caragiannis, John K. Lai, and Ariel D. Procaccia. Towards more expressive cake cutting. In Proc. IJCAI 11, pages 127 132. [Chevaleyre et al., 2006] Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, M. Lemaˆıtre, N. Maudet, J. Padget, S. Phelps, J. A. Rodriguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30(1):3 31. [Dall Aglio and Maccheroni, 2009] Marco Dall Aglio and Fabio Maccheroni. Disputed lands. Games and Economic Behavior, 66(1):57 77, May 2009. [Delimitrou and Kozyrakis, 2014] Christina Delimitrou and Christos Kozyrakis. Quasar: Resource-efﬁcient and Qo Saware Cluster Management. Proc. ASPLOS 14, 127 144. [Devulapalli, 2014] Raghuveer Devulapalli. Geometric partitioning algorithms for fair division of geographic resources. Ph D thesis, University of Minnesota, July 2014. [Edmonds and Pruhs, 2006] Jeff Edmonds and Kirk Pruhs. Balanced Allocations of Cake. In FOCS, volume 47, pages 623 634. IEEE Computer Society, October 2006. [Even and Paz, 1984] Shimon Even and Azaria Paz. A note on cake cutting. Discrete Applied Math., 7(3):285 296. [Friedman et al., 2015] Eric Friedman, Christos A. Psomas, and Shai Vardi. Dynamic Fair Division with Minimal Disruptions. In Proc. EC 15, pages 697 713.

[Hill, 1983] Theodore P. Hill. Determining a Fair Border. American Mathematical Monthly, 90(7):438 442. [Iyer and Huhns, 2009] Karthik Iyer and Michael N. Huhns. A Procedure for the Allocation of Two-Dimensional Resources in a Multiagent System. International Journal of Cooperative Information Systems, 18:1 34, 2009. [Kash et al., 2013] Ian Kash, Ariel D. Procaccia, and Nisarg Shah. No agent left behind: dynamic fair division of multiple resources. In Proc. AAMAS 13, pages 351 358. [Lalonde, 2002] Suzanne N. Lalonde. Determining boundaries in a conﬂicted world: the role of Uti Possidetis. Mc Gill-Queen s Press-MQUP, 2002. [Lipton, 2009] Michael Lipton. Land Reform in Developing Countries: Property Rights and Property Wrongs. Routledge, August 2009. [Mc Avaney et al., 1992] Kevin Mc Avaney, Jack M. Robertson, and William A. Webb. Ramsey partitions of integers and fair divisions. Combinatorica, 12(2):193 201, 1992. [Moulin, 2004] Herv e Moulin. Fair Division and Collective Welfare. The MIT Press, August 2004. [Powelson, 1988] John P. Powelson. The Story of Land: A World History of Land Tenure and Agrarian Reform. Lincoln Institute of Land Policy, May 1988. [Procaccia, 2015] Ariel D. Procaccia. Cake Cutting Algorithms. In Handbook of Computational Social Choice, chapter 13, pages 261 283. Cambridge University Press. [Robertson and Webb, 1998] Jack M. Robertson and William A. Webb. Cake-Cutting Algorithms: Be Fair if You Can. A K Peters/CRC Press, ﬁrst edition, July 1998. [Segal-Halevi et al., 2017] Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, and Yonatan Aumann. Fair and square: Cake-cutting in two dimensions. Journal of Mathematical Economics, 70:1 28, February 2017. [Segal-Halevi and Sziklai , 2018] Erel Segal-Halevi and Bal azs Sziklai. Monotonicity and Competitive Equilibrium in Cake-Cutting. Economic Theory, 2018 (forthcoming). ar Xiv preprint 1510.05229. [Segal-Halevi, 2017] Erel Segal-Halevi. 2017. Fair Division of Land. Ph.D. Dissertation. Bar Ilan University, Computer Science Department. [Sellar, 2006] Sellar. The great land debate and the Land Reform (Scotland) Act 2003. Norsk Geograﬁsk Tidsskrift - Norwegian Journal of Geography, 60(1):100 109. [Steinhaus, 1948] Hugo Steinhaus. The problem of fair division. Econometrica, 16(1):101 104, January 1948. [Thomson, 1983] William Thomson. The Fair Division of a Fixed Supply Among a Growing Population. Mathematics of Operations Research, 8(3):319 326, August 1983. [Thomson, 2007] William Thomson. Children Crying at Birthday Parties. Why? Economic Theory, 31(3):501 521. [Walsh, 2011] Toby Walsh. Online Cake Cutting. Algorithmic Decision Theory, 6992:292 305, 2011. [Woeginger and Sgall, 2007] Gerhard J. Woeginger and Jiˇr ı Sgall. On the complexity of cake cutting. Discrete Optimization, 4(2):213 220, June 2007. [Zhang et al., 2014] Y. Zhang, M.A. Laurenzano, J. Mars and L. Tang. SMi Te: Precise Qo S Prediction on Real-System SMT Processors. In Proc. IEEE/ACM MICRO 14. [Zivan, 2011] Roie Zivan. Can trust increase the efﬁciency of cake cutting algorithms? In Proc. AAMAS 11.

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