# keep_your_distance_land_division_with_separation__32ec3d2c.pdf

Keep Your Distance: Land Division With Separation

Edith Elkind1 , Erel Segal-Halevi2 and Warut Suksompong3

1Department of Computer Science, University of Oxford 2Department of Computer Science, Ariel University 3School of Computing, National University of Singapore elkind@cs.ox.ac.uk, erelsgl@gmail.com, warut@comp.nus.edu.sg

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of proportionality is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the ordinal maximin share approximation, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axes-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting.

1 Introduction

The problem of fairly allocating a divisible resource has a long history, dating back to the seminal article of Polish mathematician Hugo Steinhaus [1948]. In its basic formulation, the resource, which is metaphorically viewed as a cake, comes in the form of an interval. The aim is to find a division satisfying some fairness criteria, e.g., proportionality, which means that if there are n agents, the value that each of them receives should be at least 1/n of the entire cake. Not only does a proportional allocation always exist, but it can also be found efficiently [Dubins and Spanier, 1961]. While the interval cake is simple and consequently useful as a starting point, it is often insufficient for modeling real-world applications, especially when combined with the common requirement that each agent should receive a connected piece of the cake.1 In particular, when allocating real estate, geometric considerations play a crucial role: it is hard to build a house or raise cattle on a thin or highly zigzagged

1As Stromquist [1980] memorably wrote, without such connectivity requirements, there is a danger that agents will receive a countable union of crumbs .

piece of land even if its total area is large. Such considerations have motivated researchers to study fairness in land division, which also serves to model the allocation of other twodimensional objects such as advertising spaces [Berliant et al., 1992; Ichiishi and Idzik, 1999; Berliant and Dunz, 2004; Dall Aglio and Maccheroni, 2009; Iyer and Huhns, 2009; Devulapalli, 2014; Segal-Halevi et al., 2017; Segal-Halevi et al., 2020]. These studies have uncovered important differences between land division and interval division: for instance, when agents must be allocated square pieces, Segal Halevi et al. [2017] show that we cannot guarantee the agents more than 1/(2n) of their entire value in the worst case, even when the agents have identical valuations over the land. A related issue, which frequently arises in practice, is that agents pieces may have to be separated from one another: we may need to leave a space between adjacent pieces of land, e.g., to prevent dispute between owners, provide access to the plots, avoid cross-fertilization of different crops, or ensure safe social distancing among vendors in a market. The formal study of fair division with separation constraints was initiated by Elkind et al. [2021c], who focus on the one-dimensional setting. The goal of our work is to extend this analysis to two dimensions, i.e., to analyze fair division of land under separation constraints.

1.1 Our Contribution

We assume that each agent must obtain a contiguous piece of land, and the shares that any two agents receive must be separated by a distance of at least s, where s is a given parameter that is independent of the land value. In the presence of separation constraints, no multiplicative approximation of proportionality can be guaranteed, even in one dimension: when all of the agents values are concentrated within distance s, only one agent can receive a positive utility. Elkind et al. [2021c] therefore consider the wellknown criterion of maximin share fairness [Budish, 2011; Kurokawa et al., 2018] the value that each agent receives must be at least her 1-out-of-n maximin share, i.e., the best share that she can guarantee for herself by dividing the resource into n bundles and accepting the worst one. Elkind et al. [2021c] show that this criterion can be satisfied for an interval cake, while an ordinal approximation of it can be attained for a one-dimensional circular cake. We establish that maximin share fairness and relaxations

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

thereof can also provide worst-case guarantees in land allocation with separation. Moreover, since full proportionality cannot always be attained in this setting even in the case of no separation (s = 0), our results have interesting implications for that case as well. Our first result is negative: we prove that, when s > 0, it is impossible to guarantee to each agent a positive fraction of her 1-out-of-n maximin share. Therefore, in the rest of the paper, we focus on an ordinal notion of approximation. Specifically, we ask for the smallest value of k n such that we can guarantee each agent her 1-out-of-k maximin share. We assume that both the land to be divided and each agent s piece are axes-aligned rectangles. If we additionally require that all rectangles (both in agents maximin partitions and in the final allocation) are r-fat, i.e., the ratio of the length of the longer side to the length of the shorter side is bounded by a constant r 1, then it suffices to set k = (2 r + 2)n (3 r + 2); in particular, if all land pieces are required to be squares (r = 1), we obtain k = 4n 5. Without the fatness assumption, the problem is more difficult, and the technique we use for fat rectangles no longer works. However, we still obtain a finite approximation: we show that it suffices to set k = 2n+2, and provide stronger bounds for small values of n. In particular, for n = 2 we can set k = 3, which is optimal. Our positive results are constructive, in the sense that, given each agent s 1-out-of-k maximin partition (i.e., a partition into k pieces where the value of each piece is at least the agent s maximin share), we can divide the land among the agents so that each agent gets her 1-out-of-k share, using a natural adaptation of the standard Robertson Webb model [Robertson and Webb, 1998]. However, it is not clear how a 1-out-of-k maximin partition can be efficiently computed or even approximated. To circumvent this difficulty, we focus on a special class of land partitions known as guillotine partitions; intuitively, these are partitions that can be obtained by a sequence of edge-to-edge cuts. We show that we can efficiently compute an approximately optimal guillotine partition, and that the loss caused by using guillotine partitions can be bounded. Combining these results with our ordinal approximation algorithms, we obtain approximation algorithms for computing a maximin allocation.

1.2 Related Work In considering fair division with separation, we build on the work of Elkind et al. [2021c], who investigate the onedimensional variant of this problem. Fair land division with constraints on the shape of usable pieces has been previously studied [Segal-Halevi et al., 2017; Segal-Halevi et al., 2020]. We follow these works in considering fat rectangles and guillotine cuts; however, the fairness notions considered in these papers are (partial) proportionality and envyfreeness, whereas our work concerns maximin fairness. Our analysis is also somewhat similar in spirit to several recent works on dividing a cake represented by a general graph, which generalizes both the interval and the cycle (a.k.a. pie) setting. Several fairness notions have been studied in this setting: partial proportionality [Bei and Suksompong, 2021], envy-freeness [Igarashi and Zwicker, 2021], and maximin share fairness [Elkind et al., 2021a]. In all of these works, the

cake is still one-dimensional it is a union of a finite number of intervals. As we show in this work, a two-dimensional cake is fundamentally different.

2 Preliminaries

The land is given by a closed, bounded, and connected subset L of the two-dimensional Euclidean plane R2. The land is to be divided among a set of agents N = [n], where [k] := {1, 2, . . . , k} for any positive integer k. There is a prespecified family U of usable pieces. Each agent has an integrable density function fi : L R 0; agent i s value for a piece of land Z is given by vi(Z) := RR

Z fi(x, y)dxdy. Let s 0 be the separation parameter. An allocation of the land is given by a vector A = (A1, . . . , An), where each Ai is a single (connected) piece of land allocated to agent i. We require allocations to be s-separated, i.e., any two pieces Ai and Aj are separated by distance at least s, where distance is measured according to the ℓ norm:

d(Ai, Aj) = inf (x,y) Ai,(x ,y ) Aj max{|x x |, |y y |}.

Partitions and s-separated partitions are defined similarly, except that instead of a vector A = (A1, . . . , An), we have a set P = {P1, . . . , Pn}. Denote by Γn(s) the set of all sseparated partitions. An instance consists of the land, agents, density functions, and the separation parameter.

Definition 2.1. The 1-out-of-k maximin share of agent i is defined as MMSk,s i := sup P Γk(s) minj [k] vi(Pj). We omit s if it is clear from the context, and write MMSk i instead of MMSk,s i . We refer to MMSn i as i s maximin share.

As with cake cutting [Elkind et al., 2021c], the supremum in Definition 2.1 can be replaced by a maximum. This requires defining a metric on the usable pieces and showing that U is compact in that metric space see Appendix C in the work of Segal-Halevi et al. [2017]. An s-separated partition for which this maximum is attained is called a maximin partition of agent i. All omitted proofs can be found in the full version of our paper [Elkind et al., 2021b].

3 A General Impossibility Result

We first show that, in contrast to one-dimensional cake cutting with separation [Elkind et al., 2021c], for land division there may be no allocation that guarantees to all agents their maximin share or even any multiplicative approximation of it. This negative result does not depend on the geometric shape of the land or the pieces.2

Proposition 3.1. For every family U of usable pieces, integer n 2, separation parameter s > 0, and real number r > 0, there exists a land division instance with n agents in which no s-separated allocation gives every agent i a value of at least r MMSn,s i .

Proof sketch. We construct n sets S1, . . . , Sn consisting of n points each such that the distance between any two points in

2We are grateful to Alex Ravsky for the proof idea.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

the same set is greater than 1, but if we pick one representative point from each set, then some two representatives are at distance less than 1 apart. We then construct agents density functions so that each agent only values a small pool of land around each of the points in their set, assigning a value of 1 to each such pool. By scaling this construction by approximately a factor of s, we can ensure that each agent s maximin share is 1, but there are at most n 1 agents who can obtain a positive utility in an s-separated partition.

4 Ordinal Approximation

Since no multiplicative approximation of the maximin share can be guaranteed, we instead consider an ordinal notion of approximation. That is, we ask if each agent can be guaranteed her 1-out-of-k maximin share for some k > n. While the negative result of Section 3 does not depend on geometric assumptions, our positive results concern pieces that have a nice geometric shape. Specifically, we first consider the scenario where U consists of fat axes-aligned rectangles, i.e., rectangles whose length-to-width ratio is bounded by a constant (e.g., if this constant is 1, the set U consists of axes-aligned squares). We then consider the more general setting where U consists of all axes-aligned rectangles. Placing such constraints on the shape of each piece is useful in land allocation settings, particularly in urban regions. Note that when we restrict the shape of the usable pieces to be a (fat) rectangle, in our definition of the maximin share we also only consider s-separated partitions in which each piece is a (fat) rectangle.

4.1 Squares and Fat Rectangles

For a real number r 1, a rectangle is called r-fat if the ratio of its longer side to its shorter side is at most r [Agarwal et al., 1995; Katz, 1997]. In particular, a 1-fat rectangle is a square. Given a rectangle R, we denote the lengths of its long and short side by long(R) and short(R), respectively; we refer to short(R) as the width of R. In what follows, we say that two pieces of land overlap if their intersection has a positive area, and that they are disjoint if their intersection has a zero area. In order to obtain maximin share guarantees, the high-level idea is to find a sufficiently large k such that if we consider the agents 1-out-of-k maximin partitions, then it is possible to select a representative piece from each partition in such a way that these representatives are s-separated. This will ensure that, by allocating to each agent her representative, we obtain an allocation that is s-separated and in which agent i receives value at least MMSk,s i . The following theorem shows that k = (2 r + 2)n (3 r + 2) suffices; for a square (r = 1), this yields k = 4n 5. Note that our result does not place any assumptions on the shape of the land.

Theorem 4.1. Let r 1 be a real number. For every land division instance with n agents and separation parameter s where U is the set of axes-aligned r-fat rectangles, there exists an allocation in which every agent i receives value at least MMSk,s i , where k := (2 r + 2)n (3 r + 2).

Proof. We first consider the following geometric problem:

There are n 2 sets, each of which contains N n axes-aligned r-fat rectangles. The rectangles in each set are pairwise disjoint. We want to choose a single representative rectangle from each set so that the representatives are pairwise disjoint. What is the smallest integer N = NFAT(r, n) for which this is always possible?

We first prove that NFAT(r, 2) r + 2. 3 Given r + 2 red and r + 2 blue r-fat rectangles, we have to show that at least one red and one blue rectangle do not overlap each other. The proof of this statement is left to the full version of our paper [Elkind et al., 2021b]. Next, we prove that NFAT(r, n + 1) NFAT(r, n) + 2 r + 2. We claim that in any arrangement of axes-aligned r-fat rectangles, there exists a rectangle that overlaps at most 2 r + 2 pairwise disjoint rectangles. To prove this claim, let Qmin be a minimum-width rectangle, and denote its width by w. Mark all four corners of Qmin. Moreover, on both of its longer sides, mark r 1 additional points so that the distance between any two consecutive marks is at most w. The total number of marks is 2 r + 2. Any rectangle Q that overlaps Qmin must contain at least one of its marks. Hence, if there are more than 2 r + 2 rectangles overlapping Qmin, some two of them will overlap. This establishes the claim. Combining this with the base case n = 2, we conclude that, for all n 2 and r 1:

NFAT(r, n) (2 r + 2)(n 2) + ( r + 2) = (2 r + 2)n (3 r + 2).

For the special case of a square we get N(1, n) 4n 5.

Figure 1: The dark rectangles are s-separated if and only if the light rectangles wrapping them with a rectangle ring of width s/2 are disjoint.

We can now return to our original problem. Given the separation parameter s, for every rectangle Q with side lengths u and v, define WRAP(Q, s) to be the rectangle with side lengths u+s and v+s and the same center as Q (i.e., wrap Q with a rectangle ring of width s/2); note that WRAP(Q, s)

3 This inequality is tight, that is, NFAT(r, 2) = r + 2 for any r 1. This can proved by exhibiting two sets of r-fat rectangles, each of which contains r + 1 pairwise-disjoint rectangles, such that no two representatives are disjoint. Consider the following two sets of rectangles. The vertical set contains the rectangles [i, i+1] [1 ε, r + ε] for i {0, . . . , r }. The horizontal set contains the rectangles [1 ε, r + ε] [i, i + 1] for i {0, . . . , r }. For all rectangles, the ratio between the two side lengths is r +2ε 1; for sufficiently small ε, it is less than r, so all rectangles are r-fat. It can be verified that each horizontal rectangle overlaps all vertical rectangles.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

is r-fat whenever Q is. Then, two rectangles Q1 and Q2 are s-separated if and only if WRAP(Q1, s) and WRAP(Q2, s) do not overlap (see Figure 1). Now, given an n-agent instance, we ask each agent to produce a 1-out-of-k maximin partition: this is a set of k axesaligned rectangles that are s-separated. Then, we replace each rectangle Q with WRAP(Q, s), so each agent now has a set of k non-overlapping rectangles. Since k NFAT(r, n), there is a set of representative rectangles, one per agent, that are pairwise disjoint. Suppose that these rectangles are WRAP(Q1, s), WRAP(Q2, s), . . . , WRAP(Qn, s), where WRAP(Qi, s) belongs to agent i s set. We allocate the rectangle Qi to agent i. The rectangles Qi are s-separated, and every agent i receives value at least MMSk,s i , as desired.

Constructions similar to those in Proposition 3.1 show that NFAT(r, n) n + 1 for all r. Thus the bound 4n 5 for squares is optimal for n = 2, but may be suboptimal for n 3. Closing the gap between the lower bound n + 1 and the upper bound 4n 5 seems to require new geometric insights.

4.2 Arbitrary Rectangles Next, we allow the pieces to be arbitrary axes-aligned rectangles, and assume that the land itself is also an axes-aligned rectangle. Without loss of generality, we suppose further that the land is a square (otherwise, for positive results, a rectangular land can be completed to a square by attaching to it a rectangle that all agents value at 0). We scale the axes so that the land is the unit square [0, 1] [0, 1]. The arbitrary rectangle case differs from the fat rectangle case in two respects. First, without the separation requirement, the arbitrary rectangle case is much easier: the land can be projected onto a one-dimensional interval, for which full proportionality, and hence MMSn i , can be achieved [Dubins and Spanier, 1961]. In contrast, with the separation requirement, the arbitrary rectangle case is much harder: the representative-selection technique of Theorem 4.1 (which has also been used implicitly, in a simpler form, for cake and pie division by Elkind et al. [2021c]), does not yield a meaningful bound for arbitrary rectangles. An example similar to the one in Footnote 3 shows that, even for an arbitrarily large k, there exist two size-k sets of pairwise-disjoint rectangles such that no two representatives are disjoint. A priori, for n 2, it is not clear that there is a finite NRECT(n) such that an MMSNRECT(n) allocation among n agents always exists. Below we prove that NRECT(n) is indeed finite for any n 2, and derive improved upper bounds on NRECT(n) for small values of n. Towards this goal, we develop some new tools. In what follows, for each agent we fix a 1-out-of-k maximin partition see Figure 2 for some examples of such partitions. For all i N, we assume without loss of generality that MMSk i = 1, and that i s value is 0 outside the k rectangles in her maximin partition (the latter value being positive can only make it easier to satisfy the agent). Hence each agent has a value of k for the land and should get an axes-aligned rectangle worth at least 1. We refer to the k rectangles in the agent s fixed maximin partition as MMS-rectangles; every rectangular piece of land

that is worth at least 1 to the agent is called a value-1 rectangle. Due to our normalization, every MMS-rectangle is a value-1 rectangle, but the converse is not necessarily true. Definition 4.2. Consider an agent with a fixed 1-out-of-k maximin partition, and integers p, q 1. A vertical p:qrectangle cut is a rectangular strip of height 1 and width s that has at least p whole MMS-rectangles on its left and at least q whole MMS-rectangles on its right. A vertical prectangle stack is a sequence of p rectangles of value 1 such that each consecutive pair is separated by a vertical distance of at least s. Horizontal rectangle cuts and stacks are defined similarly. In Figure 2(a), the left vertical cut (the thick red line) is a 1:2-rectangle cut and the right one is a 2:1-rectangle cut. In Figure 2(c), there is a vertical 3-rectangle stack. In Figure 2(d), the vertical cut is a 2:1-rectangle cut, and there is a vertical 2-rectangle stack. The following lemma shows the existence of either a rectangle cut or a rectangle stack with appropriate parameters. Lemma 4.3. Fix an agent and a 1-out-of-k maximin partition of this agent. For any integers 1 p, q k with p + q k + 1, the agent has a vertical p:q-rectangle cut or a vertical (k p q + 2)-rectangle stack.

Proof. Starting from the left end of the cake, move a vertical knife of width s to the right. Stop the knife at the first point where there are at least p whole MMS-rectangles to its left the knife may need to move outside the cake in order for this to happen, as in Figure 2(c) for any p. Consider two cases. Case 1: There are at least q whole MMS-rectangles to the right of the knife. Then, the knife indicates a vertical p:qrectangle cut. This is the case when p = q = 1 in Figures 2(a), (b), and (d). Case 2: There are at most q 1 whole MMS-rectangles to the right of the knife. Then, by moving the knife slightly to the left, we obtain a cut for which there are at most p 1 MMS-rectangles entirely to its left, and at most q 1 MMSrectangles entirely to its right. Therefore, at least k p q+2 MMS-rectangles must intersect the knife itself. Since the knife width is s, these rectangles must lie in order vertically, with a vertical distance of at least s between consecutive rectangles. Hence, they form a vertical (k p q + 2)-rectangle stack. This is the case when p = q = 1 in Figure 2(c).

In the remainder of this section, given y, y [0, 1] with y y , we write R(y, y ) := [0, 1] [y, y ]. We now prove a positive result for two agents matching the lower bound implied by Proposition 3.1. Theorem 4.4. For any land division instance with a rectangular land and n = 2 agents, there exists an allocation in which each agent i receives an axes-aligned rectangle of value at least MMS3 i .

Proof. Call the agents Alice and Bob. Take a 1-out-of-3 maximin partition of each agent, and consider two cases. Case 1: Both agents have a vertical 1:1-rectangle cut. Assume without loss of generality that Alice s cut lies further to the left; give the rectangle to its left to Alice and the one to its right to Bob. Then each agent receives an MMS-rectangle.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

(a) (b) (c) (d)

Figure 2: Four partitions of a rectangular land into three axes-aligned rectangles. Each of these partitions can be a 1-out-of-3 maximin partition of an agent. The partition lines (the thick red lines) have thickness s.

Case 2: At least one agent, say Alice, has no vertical 1:1rectangle cut. By Lemma 4.3, she has a vertical 3-rectangle stack, as in Figure 2(c). For the i-th rectangle in this stack (counting from the bottom), denote the y-coordinates of its top and bottom sides by ti and bi, respectively. Note that t1 + s b2 and t2 + s b3. If Bob s value for R(0, t2) is at least 1, then give R(0, t2) to Bob and R(b3, 1) to Alice. Otherwise, Bob values R(0, t2) less than 1, so his value for R(b2, 1) is more than 2. Give R(b2, 1) to Bob and R(0, t1) to Alice. In both cases Alice s value is 1 and the pieces are s-separated.

For n 3 agents, the analysis becomes more complicated. As in classic cake-cutting algorithms (e.g., [Dubins and Spanier, 1961]), we would like to proceed recursively: give one agent a rectangle worth at least 1, and divide the rest of the land among the remaining n 1 agents. In particular, for n = 3, after allocating a piece to one agent, we would need to show that, for each of the remaining two agents, the rest of the land is worth at least 3, so that we can apply Theorem 4.4. In fact, to apply Theorem 4.4, we need an even stronger condition: each agent should have three s-separated rectangles of value 1. However, the recursion step might yield a remainder land made of many pieces of such rectangles, each of which is worth less than 1. We therefore need to adapt our definitions and lemmas accordingly.

Definition 4.5. A vertical p:q-value cut of an agent is a rectangular strip of width s such that the agent values the land on its left at least p and the land on its right at least q.

For any integers p, q, every p:q-rectangle cut is also a p:qvalue cut, but the converse is not necessarily true. For the following lemma, it is important that the agent s value function is normalized as explained earlier, i.e., the value of each MMS-rectangle is 1 and the value outside the MMS-rectangles is 0. A land-subset is a subset of the land after some pieces have possibly been allocated to other agents.

Lemma 4.6. Consider an agent with a fixed 1-out-of-k maximin partition of the land, who takes part in a division of a rectangular land-subset. Let V k be the agent s value for the land-subset. For any integers p, q 1 with p + q V , the agent has either a vertical p:q-value cut or a vertical ( V p q)/2 -rectangle stack.

The following lemma establishes a weaker bound than Theorem 4.4 does; however, it applies to an arbitrary landsubset, and hence (unlike Theorem 4.4) can be used as part

of a recursive argument. Its proof is essentially identical to the proof of Theorem 4.4: the only difference is that we first look for a vertical 1:1-value cut, and if we fail to find one, we invoke Lemma 4.6 to establish the existence of a vertical 3-rectangle stack. Lemma 4.7. Consider a rectangular land-subset and n = 2 agents who value it at least 7 each. There is an allocation in which each agent receives an axes-aligned rectangle of value at least 1.

Proof. We consider two cases. Case 1: Both agents have a vertical 1:1-value cut. Take the cut to the left, give the rectangle to its left to the cutter, and the rectangle to its right to the other agent. Case 2: At least one agent, say Alice, has no vertical 1:1value cut. By Lemma 4.6, she has a vertical 3-rectangle stack, so we can proceed as in Case 2 of Theorem 4.4.

Let Vreq(n) be the smallest value of V such that if each of n agents values the land-subset at V or higher, then there is an allocation of this land-subset in which each agent s value for her share is at least 1. Obviously Vreq(1) = 1, and by Lemma 4.7 we know that Vreq(2) 7. We can now provide a finite (exponential) MMS approximation for every positive n. Theorem 4.8. For any n 1, given any land division instance with a rectangular land and n agents, there exists an allocation in which each agent i receives an axes-aligned rectangle with value at least MMSk i , where k = 2n+2. By adjusting the argument in the proof of Theorem 4.8, we can obtain stronger bounds for n = 3 and n = 4; in particular, we can guarantee each agent i a piece of value at least MMS14 i and MMS24 i , respectively. The details can be found in the full version of our paper [Elkind et al., 2021b].

5 Computing Maximin Allocations The results in Section 4 are stated in terms of approximation guarantees. To convert them into algorithms, we need to formally define our computational model. To do so, we propose a natural modification of the classic Robertson Webb model [Robertson and Webb, 1998] for the two-dimensional setting. Consider an axes-aligned rectangle L = [a0, a1] [b0, b1], which may be part of a larger land-subset. We adapt the CUT and EVAL queries of the Robertson Webb model to allow for horizontal and vertical cuts as follows. The CUTi(|, L, δ) query returns a value a such that agent i values the rectangle

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

[a0, a] [b0, b1] at δ, and the CUTi( , L, δ) query returns a value b such that agent i values the rectangle [a0, a1] [b0, b] at δ; we assume that this query returns a1 (respectively, b1) if the agent values the entire rectangle less than δ. Similarly, the EVALi(|, L, a) query with a0 a a1 returns the value that i assigns to the rectangle [a0, a] [b0, b1], whereas EVALi( , L, b) query with b0 b b1 returns the value that i assigns to the rectangle [a0, a1] [b0, b]. We can now revisit the proofs of Theorems 4.4 and 4.8 and check if they can be converted into algorithms that use CUT and EVAL queries. One can see that these proofs are constructive and their basic steps can be expressed in terms of these queries: a p:q-value cut can be implemented by two CUT queries, and agents values for rectangles of the form R(x, y) can be determined using EVAL queries. However, these algorithms use the agents 1-out-of-k maximin partitions as their starting points, and it is not clear if such partitions are efficiently computable. Indeed, even in the 1-dimensional case, there is no algorithm that always computes a maximin partition of an agent using finitely many queries, and the best known solution is a (1 ε) approximation in time O(n log(1/ε)) [Elkind et al., 2021c]. For the 2-dimensional case, even a (1 ε) approximation seems challenging. To circumvent this difficulty, we focus on maximin partitions with a special structure, namely, guillotine partitions [Gonzalez et al., 1994; Ackerman et al., 2006; Messaoud et al., 2008; Horev et al., 2009; Asinowski et al., 2014; Russo et al., 2020]. This class of partitions is defined recursively, as follows.

Definition 5.1. Consider a land-subset L = [a0, a1] [b0, b1], a set of rectangles P = {P1, . . . , Pt}, where Pi L for each i [t], and a separation parameter s. We say that P forms an s-separated guillotine partition of L if one of the following three conditions holds:

t = 1 and P1 L;

there exists an a with a0 < a < a1 s and a partition of P into two disjoint collections of rectangles P1 and P2 such that P1 forms an s-separated guillotine partition of [a0, a] [b0, b1] and P2 forms an s-separated guillotine partition of [a + s, a1] [b0, b1];

there exists a b with b0 < b < b1 s and a partition of P into two disjoint collections of rectangles P1 and P2 such that P1 forms an s-separated guillotine partition of [a0, a1] [b0, b] and P2 forms an s-separated guillotine partition of [a0, a1] [b + s, b1].

Intuitively, an s-separated guillotine partition is obtained by a sequence of cuts, where each cut splits a rectangle into two s-separated rectangles. All partitions in Figure 2 are guillotine partitions, while Figure 3 provides an example of an s-separated partition that is not a guillotine partition. The following theorem shows that we can compute a nearly optimal s-separated guillotine maximin partition efficiently. Our algorithm proceeds by discretizing the land and finding an optimal s-separated guillotine partition that is consistent with this discretization; such a partition can be computed by dynamic programming.

Figure 3: Example of an s-separated partition that is not a guillotine partition. The small space between each pair of adjacent rectangles has length s.

Theorem 5.2. Consider a rectangular land-subset L, an agent i who values L at 1, and a separation parameter s > 0. Suppose that there exists an s-separated guillotine partition of L into k parts such that i s value for each part is at least V . Then, given ε > 0, s, and k, we can compute an s-separated guillotine partition of L into k parts such that i s value for each part is at least V ε, in time polynomial in k and 1/ε. How much value do we lose by considering guillotine partitions instead of general ones? Figure 3 illustrates that this loss is non-trivial. The following theorem provides a crude (but positive) lower bound on the approximation ratio.

Theorem 5.3. Let Ξ-MMSk,s i denote the maximin share of agent i with respect to s-separated guillotine partitions into k parts. Then, it holds that Ξ-MMSk,s i MMS4k2,s i . Combining Theorems 5.2 and 5.3 with 4.8 gives Corollary 5.4. For each ε > 0, we can compute in time polynomial in k and 1/ε an allocation in which each agent i receives a rectangular piece of land with value at least MMSk,s i ε, where k 4 (22n+2)2 = 24n+6.

6 Conclusion and Future Work This paper continues the quest of bringing the theory of fair division closer to practice by investigating fair land allocation under separation constraints. Even though the classic fairness notion of proportionality is unsuitable for this setting, we establish meaningful bounds on achievable maximin share guarantees for a variety of shapes and develop a number of new techniques in the process. In particular, for rfat rectangles we derive a polynomial bound on the achievable approximation for any number of agents, while for arbitrary rectangular pieces we obtain a finite but exponential bound. Improving the latter bound to polynomial is a challenging question which likely requires novel geometric insights. Other avenues for future work include testing our algorithms on real land division data [Shtechman et al., 2020] and exploring the possibilities of efficient computation with non-guillotine or other types of cuts.

Acknowledgments This work was partially supported by the European Research Council (ERC) under grant number 639945 (ACCORD), by the Israel Science Foundation under grant number 712/20, and by an NUS Start-up Grant. We would like to thank Kshitij Gajjar for his insights regarding guillotine partitions and the anonymous reviewers for their valuable comments.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

[Ackerman et al., 2006] Eyal Ackerman, Gill Barequet, Ron Y. Pinter, and Dan Romik. The number of guillotine partitions in d dimensions. Information Processing Letters, 98(4):162 167, 2006. [Agarwal et al., 1995] Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Computing depth orders for fat objects and related problems. Computational Geometry, 5(4):187 206, 1995. [Asinowski et al., 2014] Andrei Asinowski, Gill Barequet, Toufik Mansour, and Ron Y. Pinter. Cut equivalence of ddimensional guillotine partitions. Discrete Mathematics, 331:165 174, 2014. [Bei and Suksompong, 2021] Xiaohui Bei and Warut Suksompong. Dividing a graphical cake. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021. [Berliant and Dunz, 2004] Marcus Berliant and Karl Dunz. A foundation of location theory: Existence of equilibrium, the welfare theorems, and core. Journal of Mathematical Economics, 40(5):593 618, 2004. [Berliant et al., 1992] Marcus Berliant, William Thomson, and Karl Dunz. On the fair division of a heterogeneous commodity. Journal of Mathematical Economics, 21(3):201 216, 1992. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Dall Aglio and Maccheroni, 2009] Marco Dall Aglio and Fabio Maccheroni. Disputed lands. Games and Economic Behavior, 66(1):57 77, 2009. [Devulapalli, 2014] Raghuveer Devulapalli. Geometric partitioning algorithms for fair division of geographic resources. Ph D thesis, University of Minnesota, 2014. [Dubins and Spanier, 1961] Lester E. Dubins and Edwin H. Spanier. How to cut a cake fairly. American Mathematical Monthly, 68(1):1 17, 1961. [Elkind et al., 2021a] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Graphical cake cutting via maximin share. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021. [Elkind et al., 2021b] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Keep your distance: Land division with separation. ar Xiv preprint ar Xiv:2105.06669, 2021. [Elkind et al., 2021c] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Mind the gap: Cake cutting with separation. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021. [Gonzalez et al., 1994] Teofilo F. Gonzalez, Mohammadreza Razzazi, Man-Tak Shing, and Si-Qing Zheng. On optimal guillotine partitions approximating optimal d-box partitions. Computational Geometry, 4(1):1 11, 1994.

[Horev et al., 2009] Elad Horev, Matthew J. Katz, Roi Krakovski, and Maarten L offler. Polychromatic 4-coloring of guillotine subdivisions. Information Processing Letters, 109(13):690 694, 2009. [Ichiishi and Idzik, 1999] Tatsuro Ichiishi and Adam Idzik. Equitable allocation of divisible goods. Journal of Mathematical Economics, 32(4):389 400, 1999. [Igarashi and Zwicker, 2021] Ayumi Igarashi and William S. Zwicker. Fair division of graphs and of tangled cakes. ar Xiv preprint ar Xiv:2102.08560, 2021. [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(3 4):1 34, 2009. [Katz, 1997] Matthew J. Katz. 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects. Computational Geometry, 8(6):299 316, 1997. [Kurokawa et al., 2018] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM, 64(2):8:1 8:27, 2018. [Messaoud et al., 2008] Said Ben Messaoud, Chengbin Chu, and Marie-Laure Espinouse. Characterization and modelling of guillotine constraints. European Journal of Operational Research, 191(1):112 126, 2008. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press, 1998. [Russo et al., 2020] Mauro Russo, Maurizio Boccia, Antonio Sforza, and Claudio Sterle. Constrained twodimensional guillotine cutting problem: Upper-bound review and categorization. International Transactions in Operational Research, 27(2):794 834, 2020. [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(8):1 28, 2017. [Segal-Halevi et al., 2020] Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. Envy-free division of land. Mathematics of Operations Research, 45(3):896 922, 2020. [Shtechman et al., 2020] Itay Shtechman, Rica Gonen, and Erel Segal-Halevi. Fair cake-cutting algorithms with real land-value data. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2005 2007, 2020. [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. American Mathematical Monthly, 87(8):640 644, 1980.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)