# dividing_a_graphical_cake__bb9a3ce6.pdf

Dividing a Graphical Cake

Xiaohui Bei,1 Warut Suksompong2

1 School of Physical and Mathematical Sciences, Nanyang Technological University 2 School of Computing, National University of Singapore

We consider the classical cake-cutting problem where we wish to fairly divide a heterogeneous resource, often modeled as a cake, among interested agents. Work on the subject typically assumes that the cake is represented by an interval. In this paper, we introduce a generalized setting where the cake can be in the form of the set of edges of an undirected graph, allowing us to model the division of road networks. Unlike in the canonical setting, common fairness criteria such as proportionality cannot always be satisﬁed in our setting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with arbitrary valuations, and exhibit a tight guarantee for each graph in the case of two agents. In addition, when more than one connected piece per agent is allowed, we establish the best egalitarian welfare guarantee for each total number of connected pieces. We also study a number of variants and extensions, including when approximate equitability is considered, or when the item to be divided is undesirable (also known as chore division).

1 Introduction Cake cutting refers to the problem of fairly allocating a divisible resource, often modeled as a cake, among agents with varying preferences. The problem dates back to shortly after the end of World War II (Steinhaus 1948) and, not surprisingly given its wide range of applications, still enjoys signiﬁcant attention in mathematics, computer science, economics, and political science to this day (Brams and Taylor 1996; Robertson and Webb 1998; Procaccia 2016). What does it mean for an allocation to be fair? Steinhaus (1948) proposed the following deﬁnition of fairness: if the cake is divided between n agents, each agent should receive a part that she values at least 1/n of the entire cake. This definition became known as proportionality, and is one of the most fundamental notions in the literature of fair division. In his seminal article, Steinhaus showed that a proportional allocation can be found for any number of agents with arbitrary preferences over the cake Steinhaus method, which he attributed to Knaster and Banach, was later formulated as a moving-knife procedure by Dubins and Spanier (1961). The procedure works by having a referee move a knife over

Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

the cake from left to right. Whenever the left part has value 1/n of the entire cake for one of the agents, the agent takes that part of the cake and leaves; the procedure is then repeated among the remaining agents. In addition to ensuring proportionality, the Dubins-Spanier protocol has the important property that it always allocates to every agent a connected piece of the cake. Without this property, it may well be that an agent is presented with in the famous words of Stromquist (1980) a union of crumbs . The proportionality guarantee of the Dubins-Spanier protocol holds for a variety of resources that one may wish to divide, since a resource of any shape or form can be projected onto a line, which we can then run the protocol on. However, the connectivity property does not necessarily translate from the line back to the original shape. A simple illustrating example is when the resource has the shape of a ring (e.g., a donut or a ring road): projecting the ring onto a line and applying Dubins-Spanier may result in an agent receiving disconnected pieces of the ring. For this example, the difﬁculty can be circumvented by cutting the ring at an arbitrary point, stretching it into a line, and running the protocol to achieve proportionality. Nevertheless, one may already begin to suspect that this type of ﬁx no longer works when the shapes get more complex. In this paper, we consider a natural setting where the cake is represented by the set of edges of an arbitrary undirected graph. The graph corresponds to a resource in the form of a network, such as a road network to be divided among construction companies. Each company has its own preference on different parts of the network, and it is desirable for every company to receive a single connected component, or not too many such components. The canonical cake-cutting setting where the cake is assumed to be an interval is a special case of our setting, with the graph consisting of a single edge. We show that proportionality cannot always be attained in our generalized setting if connectivity is required. Therefore, our goal in this work is to provide the best possible approximation of proportionality that can be achieved for arbitrary graphs and agents preferences. Furthermore, we study a number of variants and extensions, including when each agent can get more than one connected piece we show that better guarantees can indeed be obtained as the number of permitted pieces increases or when the item to be divided is undesirable (often referred to as a chore).

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

1.1 Our Results

We assume throughout the paper that the agents are endowed with valuation functions that are additive and normalized with each agent having value 1 for the entire cake; these assumptions are standard in the cake-cutting literature (Procaccia 2016). We also assume that the pieces of cake that different agents receive may intersect in a ﬁnite number of points. Our formal model is described in Section 2. In Section 3, we provide general guarantees for any number of agents. For n agents with arbitrary valuations and any graph, we establish the existence of a connected allocation that gives every agent a utility of at least 1 2n 1. We also show that this bound is tight even when the agents have identical valuations and the graph is a star with 2n 1 edges. In addition, for every speciﬁc star graph, we determine the optimal utility that can be guaranteed for each number of agents. In Section 4, we delve deeper into the case of two agents. While we know from Section 3 that both agents can be guaranteed a utility of 1/3 in general, for certain graphs it is possible to do better. Perhaps surprisingly, we show that the optimal guarantee for each graph is always either 1/3 or 1/2; the latter case corresponds to a proportional allocation. The classiﬁcation depends on a graph property that we call almost bridgeless a graph satisﬁes this property if we can add an edge so that the resulting graph contains no bridges , where a bridge refers to an edge that is not contained in any cycle. We show that a guarantee of 1/2 can be obtained if the graph is almost bridgeless, while 1/3 is the best possible guarantee otherwise. Moreover, we consider allocating more than one connected piece to each agent in arbitrary graphs: we show that for any positive integer k, both agents can be guaranteed a utility of 1

2 1 2 3k if we allow the agents to receive a total of k + 1 connected pieces, and this is tight. We also study approximate equitability and prove the existence of a connected allocation for which the agents utilities differ by no more than 1/3; we again establish the tightness of the bound. Finally, in Section 5, we turn our attention to chore division. In the case of two agents there is a simple reduction between the settings of cake and chores, so all of our results in Section 4 carry over to chore division. By contrast, when there are more than two agents, the relationship between the two settings is much less clear. We show that there exists a connected allocation that incurs cost at most 2 n+1 for n 5, and that no better bound can be obtained for any n. We remark that all of our positive results are constructive: for each result, we exhibit a moving-knife protocol that achieves the desired guarantee. Moreover, one can make these protocols discrete, so that they only use the cut and evaluation queries allowed by the Robertson-Webb query model in order to access the valuation functions of the agents (Robertson and Webb 1998).

1.2 Further Related Work

While our graphical cake model is new to the best of our knowledge, graphs have been studied in the context of allocating indivisible items. In particular, the items correspond to vertices of an undirected graph, and each agent must be

allocated a connected subgraph of the graph. A line of work has explored existence and complexity questions for several fairness notions, both in the case of goods (Bouveret et al. 2017; Lonc and Truszczynski 2018; Bil o et al. 2019; Igarashi and Peters 2019; Suksompong 2019; Bei et al. 2021) and chores (Bouveret, Cechl arov a, and Lesca 2019). Connectivity constraints are commonly considered in the cake-cutting literature, where each agent is allocated a single subinterval of the interval cake (Stromquist 1980, 2008; Su 1999; Bei et al. 2012; Cechl arov a and Pill arov a 2012; Aumann, Dombb, and Hassidim 2013; Cechl arov a, Doboˇs, and Pill arov a 2013; Aumann and Dombb 2015). Segal-Halevi et al. (2017) studied the fair division of land and introduced geometric constraints to the setting by requiring that allocated pieces be of certain shape such requirements are important since a long but narrow piece of land is likely to be of little practical use. Similarly to our setting, a proportional allocation does not always exist in the presence of these constraints, and the authors examined the approximations of proportionality that can be obtained. A related line of work also considers a graphical model of resource allocation, but uses graphs to model the relationship between agents instead of the resource (Abebe, Kleinberg, and Parkes 2017; Bei, Qiao, and Zhang 2017; Chevaleyre, Endriss, and Maudet 2017; Aziz et al. 2018). Specifically, a graph represents the acquaintance relationship between the agents, and agents only evaluate their shares relative to those of other agents with whom they are acquainted.

2 Preliminaries

Let N = {1, 2, . . . , n} be the set of agents, and G = (V, E) be a ﬁnite and connected undirected graph representing the cake, with no loops but possibly with multiple edges joining the same pair of vertices.1 Denote by m the number of edges. Each edge in E can be viewed as an interval of the cake. For any points x, y on an edge, we write [x, y] or [y, x] to denote the interval of the cake between x and y; we sometimes identify a vertex v V with the corresponding endpoint of the edges adjacent to v. A piece of cake is a ﬁnite union of disjoint intervals, where each interval is a subinterval of an edge and the intervals in the piece may belong to different edges. As is commonly done in cake cutting, we assume that all intervals are closed intervals. Two intervals are said to be disjoint if they intersect in at most one point, and two pieces of cake are said to be disjoint if they intersect in a ﬁnite number of points.2 A piece of cake is connected if for any two points in the piece, it is possible to get from one point to the other along the graph G by only traversing this piece of cake. Each agent

1A loop can be represented in our model by adding a new vertex inside the loop, thereby breaking the loop into two edges joining the same pair of vertices. 2If we adopt the stricter convention that each point can only be allocated to one agent (so intervals can be open, half-open, or closed) and two intervals are disjoint only if their intersection is empty, there are strong negative results. For example, on a star graph, at most one agent would be able to receive intervals from more than one branch in a connected allocation.

i has a nonnegative valuation function (or utility function) fi, which speciﬁes the agent s value for each piece of cake. An instance consists of the graph G, the agents, and their valuation functions. We assume that the valuation functions are normalized: the value of an agent for the entire cake is 1; divisible: for each interval [x, y] and 0 λ 1, there is a point z [x, y] such that fi([x, z]) = λ fi([x, y]); additive: the value of an agent for a piece of cake is the sum of her values for the intervals in the piece. These assumptions are standard in the cake-cutting literature (Procaccia 2016). An allocation of the cake is denoted by a vector A = (A1, . . . , An), where each Ai is a piece of cake, and Ai and Aj are disjoint for all i = j. An allocation is said to be complete if the entire cake is allocated, and connected if each Ai is a connected piece of cake. The egalitarian welfare of an allocation is deﬁned as mini N fi(Ai). An allocation is proportional if its egalitarian welfare is at least 1/n. The inequity of an allocation is deﬁned as maxi,j N |fi(Ai) fj(Aj)|; an allocation with inequity 0 is said to be equitable. We make analogous assumptions for chore division (Section 5). Each agent has a nonnegative cost function fi for the chore, which is normalized, divisible, and additive. The egalitarian cost of an allocation is deﬁned as maxi N fi(Ai). Naturally, we require the entire chore to be allocated, so we restrict our attention to complete allocations of the chore. All omitted proofs can be found in the full version of this paper (Bei and Suksompong 2019).

3 Any Number of Agents In this section, we present an egalitarian welfare guarantee that holds for any number of agents and arbitrary graphs, and derive improved guarantees when the graph is a star. We begin by showing that it is always possible to give every agent a utility of at least 1 2n 1, and this bound is tight. Similarly to the Dubins-Spanier protocol, our algorithm proceeds by identifying a piece that is valuable enough for one agent but at the same time not too valuable for the other agents, allocating such a piece to the former agent, and recursing on the latter agents. Theorem 3.1. For any graph G, there exists a connected allocation with egalitarian welfare at least 1 2n 1. On the other hand, there exists a graph G and identical valuations of the agents such that any connected allocation yields egalitarian welfare at most 1 2n 1.

Proof. Let α := 1 2n 1. To show the second part of the theorem, let G be a star with 2n 1 edges such that every agent values each edge exactly α, and the value is distributed uniformly within the edge. Assume for contradiction that there is a connected allocation with egalitarian welfare strictly greater than α. Consider any agent i. The agent must receive intervals from at least two edges, and these intervals must be connected via the center vertex. Note that the unallocated parts of these edges cannot be allocated to other

agents, since any agent who receives an interval from such a part cannot receive intervals from other edges and would therefore obtain value less than α. Hence, at least two edges are only allocated to agent i. However, this means that there must be at least 2n edges in total, a contradiction. We now prove the ﬁrst part of the theorem. Let G be an arbitrary graph. We will show that there exists a movingknife algorithm that produces a connected allocation with egalitarian welfare at least α. We proceed by induction on n; the statement trivially holds for n = 1 since we can simply allocate the entire cake to the only agent. Assume that the statement holds for n 1 agents, and consider an instance with n agents. First, we claim that we can turn G into a tree. As long as G contains at least one cycle, pick an edge uv that belongs to a cycle, add a new vertex v , and replace this edge by an edge uv while keeping the remaining edges of the graph as before (see Figure 1). Since at least one cycle is removed by this operation and no new cycle is created, G eventually becomes a tree. Note that any connected allocation of the modiﬁed graph is a connected allocation in the original graph with the same value for every agent, so it sufﬁces to prove the theorem for the modiﬁed graph.

Figure 1: The cycle-removing operation

Choose an arbitrary vertex u of the tree G as its root. Let v be a vertex such that the subtree rooted at v yields value at least α to some agent, and the same does not hold for the subtree rooted at any child of v. Let w1, . . . , wk be the children of v. We consider two cases:

Case 1: At least one of the k branches of v along with the corresponding subtree yields value at least α to some agent. Assume without loss of generality that the branch containing w1 is one such branch. By our assumption, the subtree rooted at w1 yields value less than α to all agents. Hence, by moving a knife from w1 to v, we can ﬁnd the point x closest to w1 such that some agent i values the interval [w1, x] together with the subtree rooted at w1 exactly α, and all other agents value this piece of cake at most α. We allocate this piece of cake to agent i, and make x a new vertex in the remaining graph, which has value at least 1 α for each of the remaining agents. By the inductive hypothesis, there exists a connected allocation of the remaining graph to the n 1 agents such that every agent receives value at least 1 2n 3 (1 α) = 1 2n 3 2n 2

2n 1 > α, as desired. Case 2: Every branch of v along with the corresponding subtree yields value less than α to all agents. Let t {1, 2, . . . , k} be the smallest number such that the ﬁrst t branches and their subtrees together yield value at least α to some agent i. We allocate this piece of cake to

agent i. For every other agent, the ﬁrst t 1 branches are worth less than α and the tth branch is also worth less than α, so the piece of cake allocated to agent i is worth less than 2α. By the inductive hypothesis, there exists a connected allocation of the remaining graph to the n 1 agents such that every agent receives value at least 1 2n 3 (1 2α) = 1 2n 1 = α, as desired.

The two cases together complete the induction.

For certain graphs, it is possible to improve upon the guarantee provided by Theorem 3.1 an obvious example is the graph consisting of a single edge, for which the Dubins Spanier protocol yields an egalitarian welfare of at least 1/n. We derive the optimal egalitarian welfare guarantee in the case where the graph is a star. For integers n 2 and k 3, deﬁne

1 n + k/2 1 for k < 2n 1;

1 2n 1 for k 2n 1.

Theorem 3.2. Let n 2 and k 3, and let G be a star with k edges. There exists a connected allocation with egalitarian welfare at least f(n, k). Moreover, the bound f(n, k) is tight.

4 Two Agents In this section, we focus on the case of two agents. We establish the optimal egalitarian welfare that can be obtained for each graph. In addition, we explore the extent to which our guarantees can be improved if we allow more than one connected piece per agent, and also consider approximate equitability. First, we make a general observation that the well-known cut-and-choose protocol allows us to ﬁnd an allocation that gives utility 1/2 to the ﬁrst agent and 1/3 to the second agent; this strengthens the case n = 2 of Theorem 3.1. Theorem 4.1. For n = 2 and any graph G, there exists a connected allocation such that the ﬁrst agent receives value at least 1/2 and the second agent receives value at least 1/3.

Proof. By Theorem 3.1, there exists a partition of the cake into two connected pieces such that the second agent values both pieces at least 1/3. The ﬁrst agent can then choose the piece that she prefers and obtain value at least 1/2.

4.1 Graph-Speciﬁc Guarantees Before we can state our results for speciﬁc graphs, we need some graph-theoretic terminology. Recall that a bridge of a graph is an edge that is not contained in any cycle. A graph is said to be bridgeless if it contains no bridges. Deﬁnition 4.2. A graph is said to be almost bridgeless if we can add an edge so that the resulting graph is bridgeless. Note that according to this deﬁnition, every connected bridgeless graph with at least two vertices is also almost bridgeless, since we can add a copy of an existing edge. A single edge is almost bridgeless, and so is a cycle of any length, whereas a star with at least three edges is not. Next, we deﬁne an oriented labeling of a graph.

Deﬁnition 4.3. An oriented labeling of a graph with m edges is a labeling of the edges with numbers 1, 2, . . . , m, using each number exactly once, together with a labeling of one endpoint of each edge i with i and the other endpoint with i+ (so each vertex receives a number of labels equal to the number of edges adjacent to it). An oriented labeling is said to be contiguous if: For each 2 i m, the edges labeled 1, 2, . . . , i 1 form a connected subgraph, and the vertex labeled i belongs to one of these edges. For each 1 i m 1, the edges labeled i + 1, i + 2, . . . , m form a connected subgraph, and the vertex labeled i+ belongs to one of these edges. An example is illustrated in Figure 2.

Figure 2: Example of an oriented labeling

As the following lemma shows, it turns out that a graph admitting a contiguous oriented labeling is equivalent to it being almost bridgeless. Lemma 4.4. A graph is almost bridgeless if and only if it admits a contiguous oriented labeling. Given a graph G with k vertices, a bipolar numbering of G is a labeling of the vertices with numbers 1, 2, . . . , k, with each number used exactly once, such that every vertex with label greater than 1 has a neighbor with a smaller label and each vertex with label smaller than k has a neighbor with a larger label. Bil o et al. (2019) characterized the class of graphs that admit a bipolar numbering as the graphs with the property that if the vertices of the graph represent indivisible items of possibly different values to the two agents, then there always exists a connected envy-free up to one item allocation. We show that the class of graphs that admit a bipolar numbering forms a strict subclass of the almost bridgeless graphs (which, by Lemma 4.4, is equivalent to the class of graphs that admit a contiguous oriented labeling). Proposition 4.5. Any graph that admits a bipolar numbering is almost bridgeless, but the converse does not hold. We are now ready to show our classiﬁcation result: the optimal egalitarian welfare that can always be obtained for a graph is 1/2 if the graph is almost bridgeless, and 1/3 otherwise. The former is shown in Theorem 4.6, while the latter follows from Theorems 3.1 and 4.8. Theorem 4.6. For n = 2 and any almost bridgeless graph G, there exists a connected proportional allocation.

Proof. Suppose that G is almost bridgeless. By Lemma 4.4, it admits a contiguous oriented labeling. We move a knife

over the edges of G in increasing order of the label. For each edge with label i, the knife goes from vertex i to vertex i+. If the knife is currently on edge i, we stop when the piece of cake containing edges 1, 2, . . . , i 1, together with the interval of edge i between i and the current position of the knife, yields value exactly 1/2 to one of the agents. We allocate this piece of cake to the agent who receives value 1/2, and the remainder of the cake to the other agent. Both agents receive value at least 1/2 and, by deﬁnition of the labeling, obtain a connected allocation of the cake.

Lemma 4.7. Let F be a nonempty set of bridges in a graph. If no path contains all bridges in F, there exist three bridges in F such that no path contains all three bridges.

Theorem 4.8. For n = 2 and any graph G that is not almost bridgeless, there exist identical valuation functions of the two agents such that any connected allocation yields egalitarian welfare at most 1/3.

Proof. Suppose that G is not almost bridgeless. Then no path can contain all bridges of G: if there exists such a path, we can eliminate all bridges by adding an edge that connects the endpoints of this path. By Lemma 4.7, there exist three bridges of G such that no path contains all three bridges. For each of the three bridges, the other two bridges must lie on the same side of it, since otherwise we can construct a path that contains all three bridges. See Figure 3.

Figure 3: Illustration for the proof of Theorem 4.8. The circles denote components and the edges correspond to the three bridges.

Assume that both agents value each of the three bridges exactly 1/3 (and every other edge 0), and the value is distributed uniformly within each bridge. Suppose for contradiction that there exists a connected allocation with egalitarian welfare strictly greater than 1/3. This means that each agent must receive intervals from at least two bridges. However, when an agent receives intervals from two bridges, each interval must contain the endpoint of the bridge that is on the same side as the other two bridges. This is impossible since there are only three bridges, yielding the desired contradiction.

4.2 Beyond One Connected Piece

As we mentioned in the introduction, an important motivation for considering connected allocations is to avoid situations where an agent receives a union of crumbs . In light of this motivation, it is interesting to explore whether we can obtain improved guarantees if we allow the agents to receive a small number of connected pieces. We demonstrate

in this subsection that such improvements are indeed possible by presenting a tight bound of 1

2 1 2 3k on the egalitarian welfare that can be guaranteed when a total of k + 1 connected pieces are permitted. We ﬁrst establish the lower bound. Note that by following the algorithm in the proof of Theorem 3.1, we obtain the following lemma, which we will use in the proof of the lower bound.

Lemma 4.9. Let H be a connected piece of cake in a graph G, and suppose that all agents have value exactly x for H. For any α x, there exists a partition of H into two connected pieces such that one of the agents has value at least α for the ﬁrst piece, while all of the remaining agents have value at most 2α for this piece.

Theorem 4.10. Let k be a positive integer. For n = 2 and any graph G, there exists an allocation in which the two agents receive a total of at most k + 1 connected pieces and the egalitarian welfare is at least 1

Proof. Let G be an arbitrary graph. It sufﬁces to show that there exists a partition of G into two parts with at most k +1 connected pieces in total such that both parts yield value at least 1

2 1 2 3k to the ﬁrst agent. Indeed, given such a partition, we can let the second agent choose the part that she prefers and obtain value at least 1/2. We therefore consider only the ﬁrst agent from now on. We proceed by induction on k; the base case k = 1 follows from Theorem 4.1. Suppose that the statement holds for k 1, i.e., there exists a partition of G into two parts with at most k connected pieces in total such that both parts yield value at least 1

2 1 2 3k 1 to the agent. Assume without loss of generality that the second part has value at least 1/2, so the ﬁrst part has value 1

2 x for some 0 x 1 2 3k 1 . Since the second part consists of at most k 1 connected pieces, it contains a connected piece of value at least 1 2k 2. Denote this piece by H. Since 2k 2 3k, we have 2x

3 1 3k 1 2k 2. By creating a duplicate of our agent and applying Lemma 4.9 with α = 2x/3, we can partition H into two connected pieces in such a way that our agent has value in the range [ 2x

3 ] for the ﬁrst piece. Move this piece from the second part of our partition of G to the ﬁrst part. The resulting partition of G consists of at most k + 1 connected pieces in total, and the ﬁrst part of this partition has value in the range [ 1

3]. This implies that both parts of the partition yield value at least 1 2 x

2 1 2 3k , completing the induction.

Next, we show that the bound established in Theorem 4.10 is tight for every k. First we need the following technical lemma.

Lemma 4.11. Let t be a positive integer, and let a1, a2, . . . , at be (not necessarily distinct) integers and ε1, ε2, . . . , εt { 1, 2}. Then ε1 3a1 + ε2 3a2 + + εt 3at 1

Theorem 4.12. Let k be a positive integer. There exists an instance with n = 2 and identical valuations such that any allocation in which the two agents receive a total of at most

k + 1 connected pieces yields egalitarian welfare at most 1 2 1 2 3k .

Figure 4: The graph in the proof of Theorem 4.12 for k = 2.

Proof. Let G be a rooted tree with k + 2 layers, where the ﬁrst layer consists only of the root of the tree. The root has one child, and every vertex in subsequent layers up to the (k+1)st layer has three children. In particular, the (k+2)nd layer consists of 3k leaves. The tree G for the case k = 2 is shown in Figure 4. Suppose that both agents value each edge adjacent to a leaf exactly 1/3k with the value distributed uniformly within the edge, and do not value any other edge. Consider an arbitrary allocation in which the two agents receive a total of at most k + 1 connected pieces. We will show that the egalitarian welfare is at most 1

2 1 2 3k . If there are unallocated parts of the cake, we arbitrarily allocate these parts so that the number of connected pieces that each agent receives does not increase; this does not lower the egalitarian welfare of the allocation. Hence we may assume that the entire cake is allocated (i.e., the allocation is complete). Denote by X1, . . . , Xp the connected pieces that agent 1 receives, and Y1, . . . , Yq the connected pieces that agent 2 receives, where p + q k + 1. We assume that each edge has length 1, and refer to the distance along the (unique) path between two points in G simply as the distance between these two points. Note that every connected piece has a unique point closest to the root: if there are two such points, they must be connected via a point that is strictly closer to the root than both of them. For every connected piece Z, denote by wz the unique point in Z closest to the root and u(Z) the utility of the piece Z. We will deﬁne a connected piece Z as follows:

If wz is not a vertex of G, let Z be the set of points w such that the path from w to the root goes through wz. In other words, Z is the part of the tree below wz. If wz is a vertex of G, let Z be the set of points w such that the intersection of Z and the path from w to the root has nonzero measure. Equivalently, Z consists of the edges adjacent to wz that have a nontrivial overlap with Z, along with everything below these edges.

Assume without loss of generality that agent 1 receives a piece containing the root of the tree. We claim that u(X1)+ +u(Xp) = [u(X 1)+ +u(X p)] [u(Y 1 )+ + u(Y q )]. First, note that for each Z where Z {X1, . . . , Xp, Y1, . . . , Yq}, every connected piece Xi and Yi is either contained in Z in its entirety or not at all.

Hence u(Z ) can be written as a sum of distinct u(Xi) s and u(Yi) s. Moreover, one can verify from the deﬁnition that a connected piece Z is contained in W if and only if Z = W or the path from wz to the root has a nontrivial overlap with W. This path alternates between pieces Xi and Yi and ends with a piece Xi. Therefore, each u(Xi) is contained in u(X 1) + + u(X p) exactly once more than in u(Y 1 ) + + u(Y q ), while each u(Yi) is contained in the two sums an equal number of times. This yields the claimed equality. Next, observe that each u(Z ) can be written as 3s/3k for some nonnegative integer s k, or 2 3s/3k for some nonnegative integer s k 1, or δ/3k for some δ [0, 1]. Note also that since agent 1 receives a piece containing the root of the tree, for this piece Xi we have u(X i ) = 1. It follows that [u(X 1)+ +u(X p)] [u(Y 1 )+ +u(Y q )] can be written as 1 (S + ), where S is a sum of a number of terms (say, r terms, where r k) of the form ε 3a with ε { 1, 2} and a an integer, and | | (k r)/3k. Hence, letting d := u(X1) + + u(Xp) 1

2 , we have

i=1 u(X i )

i=1 u(Y i ) 1

3k = 3k r 2(k r)

2 3k 1 2 3k ,

where the ﬁrst inequality follows from the triangle inequality, the second inequality follows from Lemma 4.11, and the last inequality holds since 3b 2b+1 for any integer b 0. This implies that the egalitarian welfare is at most 1

2 1 2 3k , as claimed.

Recall that the height of a rooted tree is the length of the longest path from the root to a leaf vertex. For example, a star rooted at the center vertex has height 1. Our next theorem shows that for graphs that can be represented as a tree of height at most 2, we can obtain full proportionality provided that we allow two connected pieces per agent. Theorem 4.13. For n = 2 and any graph G that can be represented as a rooted tree of height at most 2, there exists a proportional allocation such that each agent receives at most two connected pieces.

4.3 Equitability We end this section by brieﬂy considering another wellestablished fairness notion: equitability. Interestingly, while for approximate proportionality it is useful to consider the maximum among the agents values for the current piece (Theorem 3.1), for approximate equitability in the case of two agents, the appropriate quantity to consider is the sum of these values. Note that an empty allocation is always equitable but yields the lowest possible welfare of zero, so we are interested in complete allocations. Theorem 4.14. For n = 2 and any graph G, there exists a complete and connected allocation with inequity at most 1/3. Moreover, the bound 1/3 is tight.

Proof. To show tightness, let G be a star with three edges such that every agent values each edge exactly 1/3, and the value is distributed uniformly within the edge. In any complete and connected allocation, one of the agents must receive two full edges (and possibly part of the third). This implies that the inequity in such an allocation is at least 1/3. We now prove the ﬁrst part of the theorem. Let G be an arbitrary graph. Our goal is to ﬁnd a complete, connected allocation (A1, A2) such that |f1(A1) f2(A2)| 1/3. Since the allocation is complete, we may write f2(A2) = 1 f2(A1). The desired condition can be rewritten as 2/3 f1(A1) + f2(A1) 4/3. We use a similar procedure as in Theorem 3.1, turning the graph into a tree and considering a minimal subtree that has value at least 2/3 with respect to f1 + f2. We stop either when the knife cuts a subtree A1 such that f1(A1) + f2(A1) = 2/3 (Case 1), or when a set of branches A1 satisﬁes f1(A1) + f2(A1) 2/3 for the ﬁrst time (Case 2). An analogous argument shows that we must have f1(A1) + f2(A1) 2/3 + 2/3 = 4/3, which yields the desired inequality.

5 Chore Division

In this section, we assume in contrast to the previous sections that the graph represents a chore, i.e., an item that yields negative value to the agents. This models, for example, a situation where we wish to divide the responsibilities of maintaining a road network among relevant organizations. For the case of two agents, all results in cake cutting (Section 4) can be translated to analogous results in chore division using a simple reduction. The idea is that given a chore instance, we can turn it into a cake instance by pretending that the cost functions are cake valuation functions, applying a result in the cake setting to obtain an initial allocation of the chore, and having the agents swap their assigned pieces to arrive at the ﬁnal allocation. This reduction works for translating positive results to the chore setting. For negative results, we can use the reduction in the opposite direction, starting from a chore instance and reducing it to a cake instance. As an illustrating example, we show how to deduce an analogue of Theorem 4.1 in the chore setting.

Theorem 5.1. In chore division, for n = 2 and any graph G, there exists a connected allocation such that the ﬁrst agent incurs cost at most 1/2 and the second agent incurs cost at most 2/3.

Proof. Consider an arbitrary chore division instance. If we treat the chore valuations as cake valuations, then by Theorem 4.1, there exists a (complete) connected allocation such that the ﬁrst agent receives value at least 1/2 and the second agent receives value at least 1/3. Let the agents swap their assigned pieces in this allocation. In the resulting allocation, which is also connected, the ﬁrst agent incurs cost at most 1 1/2 = 1/2 and the second agent incurs cost at most 1 1/3 = 2/3.

When there are more than two agents, the relationship between the cake and the chore settings becomes much less clear, and we do not know how to translate results from one

setting to the other. In the chore setting, we show that for each n, the egalitarian cost may need to be as high as 2 n+1.

Proposition 5.2. In chore division, there exists a graph G and identical valuations of the agents such that any connected allocation yields egalitarian cost at least 2 n+1.

The bound 2 n+1 is tight for n = 2 due to Theorem 5.1. The following theorem shows that it remains tight as long as n 5.

Theorem 5.3. In chore division, for n 5 and any graph G, there exists a connected allocation with egalitarian cost at most 2 n+1.

The proof of Theorem 5.3 involves some elaborate analysis and is left to the full version (Bei and Suksompong 2019). Here we give a simpler protocol for the case n = 3, yielding egalitarian cost at most 1/2. First, pick two arbitrary agents. By Theorem 5.1, there exists a connected allocation to the two agents such that the ﬁrst agent incurs cost at most 1/2 and the second agent incurs cost at most 2/3. Fix the piece assigned to the ﬁrst agent, and divide the piece assigned to the second agent further between the second and third agents. By Theorem 5.1 again, there exists a connected allocation of the latter piece such that the third agent incurs cost at most 1/2 and the second agent incurs cost at most (2/3) (2/3) = 4/9 < 1/2. Hence the egalitarian cost of the resulting allocation is at most 1/2. We conjecture that the bound 2 n+1 is tight for all n, and leave it as an intriguing open question.

6 Conclusion and Future Work

In this paper, we introduce and study a generalized version of the classical cake-cutting problem, where the cake can be represented by an arbitrary graph instead of an interval. We establish bounds on the utilities that can be guaranteed to the agents for various classes of graphs, both for cake cutting and chore division, and demonstrate in several cases that our guarantees are tight. We also show that better guarantees are possible if we allow more connected pieces per agent, and exhibit an algorithm that computes an approximately equitable allocation. Our work opens up a number of new directions for future research. Besides proportionality and equitability, another prominent fairness notion is envy-freeness, which stipulates that no agent prefers another agent s bundle to her own in the allocation. In the case of two agents, envy-freeness and proportionality are equivalent, and approximate proportionality bounds readily translate to corresponding approximate envy-freeness results. However, this equivalence ceases to hold when there are more than two agents. If the graph consists of a single edge, a connected envy-free allocation always exists for any number of agents (Stromquist 1980). It would be interesting to see whether one can obtain (approximate) envy-freeness guarantees for different classes of graphs. Furthermore, one could consider dividing a mixture of goods and chores (Bogomolnaia et al. 2017; Segal-Halevi 2018; Aziz et al. 2019) in our model as well.

Acknowledgments

This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), by the European Research Council (ERC) under grant number 639945 (ACCORD), and by an NUS Start-up Grant. We would like to thank Edith Elkind and Lisa Sauermann for helpful discussions.

Abebe, R.; Kleinberg, J.; and Parkes, D. C. 2017. Fair division via social comparison. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems (AAMAS), 281 289.

Aumann, Y.; and Dombb, Y. 2015. The efﬁciency of fair division with connected pieces. ACM Transactions on Economics and Computation 3(4): 23:1 23:16.

Aumann, Y.; Dombb, Y.; and Hassidim, A. 2013. Computing socially-efﬁcient cake divisions. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 343 350.

Aziz, H.; Bouveret, S.; Caragiannis, I.; Giagkousi, I.; and Lang, J. 2018. Knowledge, fairness, and social constraints. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 4638 4645.

Aziz, H.; Caragiannis, I.; Igarashi, A.; and Walsh, T. 2019. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 53 59.

Bei, X.; Chen, N.; Hua, X.; Tao, B.; and Yang, E. 2012. Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence (AAAI), 1263 1269.

Bei, X.; Igarashi, A.; Lu, X.; and Suksompong, W. 2021. The price of connectivity in fair division. In Proceedings of the 35th AAAI Conference on Artiﬁcial Intelligence (AAAI). Forthcoming.

Bei, X.; Qiao, Y.; and Zhang, S. 2017. Networked fairness in cake cutting. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 3632 3638.

Bei, X.; and Suksompong, W. 2019. Dividing a graphical cake. Co RR abs/1910.14129.

Bil o, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2019. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), 14:1 14:21.

Bogomolnaia, A.; Moulin, H.; Sandomirskiy, F.; and Yanovskaya, E. 2017. Competitive division of a mixed manna. Econometrica 85(6): 1847 1871.

Bouveret, S.; Cechl arov a, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 135 141.

Bouveret, S.; Cechl arov a, K.; and Lesca, J. 2019. Chore division on a graph. Autonomous Agents and Multi-Agent Systems 33(5): 540 563. Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Cechl arov a, K.; Doboˇs, J.; and Pill arov a, E. 2013. On the existence of equitable cake divisions. Information Sciences 228: 239 245. Cechl arov a, K.; and Pill arov a, E. 2012. On the computability of equitable divisions. Discrete Optimization 9(4): 249 257. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2017. Distributed fair allocation of indivisible goods. Artiﬁcial Intelligence 242: 1 22. Dubins, L. E.; and Spanier, E. H. 1961. How to cut a cake fairly. American Mathematical Monthly 68(1): 1 17. Igarashi, A.; and Peters, D. 2019. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI), 2045 2052. Lonc, Z.; and Truszczynski, M. 2018. Maximin share allocations on cycles. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 410 416. Procaccia, A. D. 2016. Cake cutting algorithms. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 13, 311 329. Cambridge University Press. Robertson, J.; and Webb, W. 1998. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press. Segal-Halevi, E. 2018. Fairly dividing a cake after some parts were burnt in the oven. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1276 1284. Segal-Halevi, E.; Nitzan, S.; Hassidim, A.; and Aumann, Y. 2017. Fair and square: Cake-cutting in two dimensions. Journal of Mathematical Economics 70(8): 1 28. Steinhaus, H. 1948. The problem of fair division. Econometrica 16(1): 101 104. Stromquist, W. 1980. How to cut a cake fairly. American Mathematical Monthly 87(8): 640 644. Stromquist, W. 2008. Envy-free cake divisions cannot be found by ﬁnite protocols. Electronic Journal of Combinatorics 15: #R11. Su, F. E. 1999. Rental harmony: Sperner s lemma in fair division. American Mathematical Monthly 106(10): 930 942. Suksompong, W. 2019. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics 260: 227 236.