Redividing the Cake

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 definition 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 efficiency 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 first 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 satisfies 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 fit 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 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/⌊ nk ⌋ 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/⌊ nk ⌋ 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 justified by political reasoning: in a democratic country, it may be sufficient to win the support of a sufficiently 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/⌈ nk ⌉ 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/⌊ nk ⌋) 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 find 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-specified 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.

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-efficient 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 con-

straint. 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 find 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.

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) = ∫x∈Xi vi(x)dx. The definition implies that the Vi are finite 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 specified piece of cake; a mark query asks an agent to mark a piece of cake with a specified 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 prespecified 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 ∪ni=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:

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 satisfies the w-ownership property if every agent receives at least a fraction w of its old value:

Since w-ownership is not always compatible with rproportionality for any r > 0, we define the following weaker property. A re-allocation satisfies the democratic-ownership property if, for every k ∈ {1, . . . , n}, there are at least n - k agents j ∈ {1, . . . , n} for whom:

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 satisfies 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 sufficiently 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) ≥ rVi(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 pq Vi(Yi ∩Zj). Its total value in these np pieces is thus at least rVi(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 efficiently by classic protocols such as Steinhaus [1948], Even and Paz [1984]). By Lemma 8, the new division satisfies r-proportionality and (1-r)-ownership, and 1-r ≥ w.

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 McAvaney 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)/⌊ nk ⌋. Assume that the valuations are as follows. Each agent j ∈ {1, . . . , k} values his original piece Zj as ⌊ nk ⌋ and the rest of the cake as 0. The value-density of j in Zj is piecewiseuniform: It has ⌊ nk ⌋ regions with a value of 1 and ⌊ nk ⌋ - 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 ⌋ = ⌊ nk ⌋-1 or ⌈ n-k k ⌉ = ⌈ nk ⌉-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 ⌊ nk ⌋ - 1, each gap is wanted by exactly one agent; otherwise, there is one gap wanted by two agents). The following figure illustrates the value-densities that are positive in piece Z1.

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)/⌊ nk ⌋.

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 EvenPaz protocol [Even and Paz, 1984]. It finds, 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 :

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 satisfies 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 ⌈ nk ⌉ normal agents. Hence, at least n-k islands are populated by at most ⌈ nk ⌉-1 normal agents. Adding the helper agent, these islands are populated by at most ⌈ nk ⌉ 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 )/⌈ nk ⌉.

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.

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 find 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.

⇒

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 find this maximal extension efficiently; this computational-geometric question is left for future work.

6 RelatedWork

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 final 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: finding a proportional division takes Θ(n log n) queries, but finding an r-proportional division takes only

• Θ(n) queries, for some sufficiently small r ≤ 0.1 [Edmonds and Pruhs, 2006, and others].
• Improving social welfare: proportional allocations may be socially inefficient; efficiency can be improved by decreasing the value-guarantee per agent [Zivan, 2011; Arzi, 2012].
• 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].
• 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 FutureWork

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-efficiency. From an existential point of view, Pareto-efficiency does not add much difficulty. 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 find 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 finding 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 benefited a lot from discussions with Reuven Cohen, Panagiotis Kanellopoulos, Laszlo Csato, Herve Moulin, Yehuda Levy, Chris Culter, Varun 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!