# approximate_envyfreeness_in_graphical_cake_cutting__6373f33d.pdf

Approximate Envy-Freeness in Graphical Cake Cutting

Sheung Man Yuen and Warut Suksompong National University of Singapore {yuens,warut}@comp.nus.edu.sg

We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We focus on the existence and computation of connected allocations with low envy. For general graphs, we show that there is always a 1/2additive-envy-free allocation and, if the agents valuations are identical, a (2 + ϵ)-multiplicativeenvy-free allocation for any ϵ > 0. In the case of star graphs, we obtain a multiplicative factor of 3 + ϵ for arbitrary valuations and 2 for identical valuations. We also derive guarantees when each agent can receive more than one connected piece. All of our results come with efficient algorithms for computing the respective allocations.

1 Introduction Cake cutting refers to the classic problem of fairly allocating a divisible resource such as land or advertising spaces playfully modeled as a cake among agents who may have different values for different parts of the resource [Robertson and Webb, 1998; Procaccia, 2013]. The most common fairness criteria in this literature are proportionality and envyfreeness. Proportionality demands that if there are n agents among whom the cake is divided, then every agent should receive at least 1/n of her value for the entire cake. Envyfreeness, on the other hand, requires that no agent would rather have another agent s piece of cake than her own. Early work in cake cutting established that a proportional and envyfree allocation that assigns to each agent a connected piece of cake always exists, regardless of the number of agents or their valuations over the cake [Dubins and Spanier, 1961; Stromquist, 1980; Su, 1999]. Although existence results such as the aforementioned guarantees indicate that a high level of fairness can be achieved in cake cutting, they rely on a typical assumption in the literature that the cake is represented by an interval. This representation is appropriate when the resource corresponds to machine processing time or a single road, but becomes insufficient when one wishes to divide more complex

resources such as networks. For example, one may wish to divide road networks, railway networks, or power cable networks among different companies for the purpose of construction or maintenance. In light of this observation, Bei and Suksompong [2021] introduced a more general model called graphical cake cutting, wherein the cake can be represented by any connected graph. With a graphical cake, a connected proportional allocation may no longer exist see Figure 1 (left). Nevertheless, these authors showed that more than half of the proportionality guarantee can be retained: any graphical cake admits a connected allocation such that every agent receives at least 1/(2n 1) of her entire value. The result of Bei and Suksompong [2021] demonstrates that approximate proportionality is attainable in graphical cake cutting. However, the allocation that their algorithm produces may lead to high envy between the agents. In particular, while each agent i is guaranteed 1/(2n 1) of her value, it is possible that the algorithm assigns the remaining (2n 2)/(2n 1) of the value to another agent j from i s perspective, so that i envies j by almost the entire value of the cake (for large n) when measured additively, and by a factor linear in n when measured multiplicatively. Note that envy-freeness is a much more stringent benchmark than proportionality for instance, although there exists a simple protocol for computing a connected proportional allocation of an interval cake [Dubins and Spanier, 1961], no finite protocol can compute a connected envy-free allocation of it [Stromquist, 2008], and even without the connectivity requirement, the only known envy-free protocol requires an enormous number of queries [Aziz and Mackenzie, 2016]. The goal of our work is to investigate the existence of connected allocations of a graphical cake with low envy, as well as to design algorithms for computing such allocations.

1.1 Our Results

We assume that the cake is represented by the edges of a connected graph, and each edge can be subdivided into segments to be allocated to different agents. Each agent is to receive a connected piece, though we will also briefly explore relaxations of this constraint towards the end. The whole cake must be allocated, and each agent s value for it is additive and normalized to 1; the value of each agent does not need to be uniform within each edge or across different edges. Following Bei and Suksompong [2021],

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Figure 1: (Left) A star graph with three edges of equal length. Two agents with identical valuations distributed uniformly over the three edges cannot each receive a connected piece worth at least 1/2 of the whole cake at the same time. (Right) A star graph with many edges to be divided between two agents. If sharing of vertices is disallowed, then the agent who does not receive the center vertex will be restricted to at most one edge, and will incur envy equal to almost the value of the entire cake.

we also assume that each vertex can be shared by multiple agents.1 We consider both additive envy for α [0, 1], an allocation is α-additive-EF if no agent envies another agent by an amount of more than α and multiplicative envy for α 1, an allocation is α-EF if no agent envies another agent by a factor of more than α. An α-EF allocation is also α 1 α+1 -additive-EF; we refer to Proposition 1 for details. In Section 3, we consider agents with (possibly) nonidentical valuations. We show that for any graph, there exists a 1/2-additive-EF allocation, and such an allocation can be computed by iteratively allocating to each agent a share that other agents do not value too highly. If the graph is a star, we present an algorithm that, for any ϵ > 0, finds a (3 + ϵ)-EF allocation (which is therefore nearly 1/2-additive-EF as well) by allowing agents to repeatedly relinquish their current share for a higher-value share, and allocating the remaining shares by following certain rules. Our two algorithms generalize ideas from algorithms for the interval cake by Goldberg et al. [2020] and Arunachaleswaran et al. [2019], respectively. We remark here that star graphs are of particular interest in graphical cake cutting because they constitute perhaps the most intuitive generalization of the well-studied interval cake, and therefore provide a natural platform for attempts to extend techniques and results from the interval-cake setting.2 Next, in Section 4, we demonstrate how the bounds for non-identical valuations can be improved in the case of identical valuations; this case captures scenarios in which there is an objective valuation among agents.3 For arbitrary graphs, we devise an algorithm that computes a (2 + ϵ)-EF allocation (which is therefore nearly 1/3-additive EF). Our algorithm is inspired by the work of Chu et al. [2010] on partitioning edges of a graph (see Section 1.2), and involves repeatedly adjusting the shares along a path from the minimum share to the maximum share so that

1Without this assumption, one cannot obtain nontrivial envy-free guarantees see the caption of Figure 1 (right) for a brief discussion. 2Star graphs (and path graphs) are also often studied in the context of indivisible items (see Section 1.2). In graphical cake cutting, all path graphs are equivalent to the classic interval cake, which is why the role of star graphs is further highlighted. 3We discuss further motivation for investigating this case at the beginning of Section 4.

General graphs Star graphs

Non-identical valuations

1/2-additive-EF (Thm. 3) (3 + ϵ)-EF (Thm. 4)

Identical valuations

(2 + ϵ)-EF (Thm. 6) 2-EF (Thm. 7)

Table 1: Summary of results in Sections 3 and 4.

the shares become more balanced in value. For star graphs, we provide a simpler algorithm that returns a 2EF allocation using a bag-filling idea. As we discuss after Proposition 1, an approximate proportionality result of Bei and Suksompong [2021] implies that both of our guarantees in this section are (essentially) tight. Finally, in Section 5, we explore the fairness guarantees when each agent can receive more than one connected piece. We introduce the notion of path similarity number to discuss the relationship between connected interval cake cutting and (non-connected) graphical cake cutting. Our results in Sections 3 and 4 are summarized in Table 1, and all proofs can be found in the full version of our paper [Yuen and Suksompong, 2023]. All of our algorithms can be implemented in the standard cake-cutting model of Robertson and Webb [1998] in time polynomial in n, the size of the graph, and, if applicable, 1/ϵ.

1.2 Further Related Work Cake cutting is a topic of constant interest for researchers in mathematics, economics, and computer science alike. For an overview of its intriguing history, we refer to the books by Brams and Taylor [1996] and Robertson and Webb [1998], as well as the book chapter by Procaccia [2016]. The cake-cutting literature traditionally assumes that the cake is given by an interval, and connectivity of the cake allocation is often desired in order to avoid giving agents a union of crumbs [Stromquist, 1980; Stromquist, 2008; Su, 1999; Bei et al., 2012; Cechl arov a et al., 2013; Arunachaleswaran et al., 2019; Goldberg et al., 2020; Barman and Kulkarni, 2022].4 Besides Bei and Suksompong [2021], a few authors have recently addressed the division of a graphical cake. Igarashi and Zwicker [2021] focused on envy-freeness but made the crucial assumption that vertices cannot be shared between agents as discussed in the caption of Figure 1 (right), with their assumption, one cannot obtain nontrivial guarantees even for star graphs and identical valuations. Deligkas et al. [2022] explored the complexity of deciding whether an envy-free allocation exists for a given instance (and, if so, finding one), both when vertices can and cannot be shared, but did not consider approximate envy-freeness. Elkind et al. [2021] investigated another fairness notion called maximin share fairness in graphical cake cutting. For additional discussion of related work, please refer to the full version of our paper [Yuen and Suksompong, 2023].

4While connectivity is the most frequently studied constraint in cake cutting, other constraints, such as geometric and separation constraints, have also been explored [Suksompong, 2021].

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

2 Preliminaries

Let G = (V, E) be a connected undirected graph representing the cake. Each edge e E, isomorphic to the interval [0, 1] of the real numbers, is denoted by e = [v1, v2] = [v2, v1] where v1, v2 V are the endpoints of edge e. If x1 and x2 are points on an edge, then the segment between them is denoted by [x1, x2] or [x2, x1] we sometimes call it an interval. We shall restrict our attention to closed intervals only. Two intervals of a cake G are considered disjoint if their intersection is a finite set of points. A share of a cake G is a finite union of pairwise disjoint (closed) intervals of G where the intervals may belong to different edges such that it is connected, i.e., for any two points in the share, there exists a path between the two points that only traverses the share.5 As with intervals, two shares of a cake G are considered disjoint if their intersection is a finite set of points. Let N = {1, 2, . . . , n} be a set of n 2 agents. Each agent i N has a valuation function (or utility function) µi, which maps each share of G to a nonnegative real number. Following the cake-cutting literature [Procaccia, 2016], we assume that each valuation function µi is

normalized: µi(G) = 1,

divisible: for each interval [x1, x2] and λ [0, 1], there exists a point y [x1, x2] such that µi([x1, y]) = λ µi([x1, x2]), and

additive: for any two disjoint intervals I1 and I2, we have µi(I1 I2) = µi(I1) + µi(I2).

An instance of graphical cake cutting consists of a graph G, a set of agents N, and valuation functions (µi)i N. Given an instance, a partial allocation of G is a list A = (A1, . . . , An) of pairwise disjoint shares of the cake, where Ai is agent i s share we say that Ai is allocated to agent i. A share is unallocated if its intersection with every agent s share is a finite set of points. An allocation of G is a partial allocation such that every point in the cake is allocated to some agent. For a parameter α, a partial allocation A is

α-additive-EF if µi(Ai) µi(Aj) α for all i, j N,

α-EF if µi(Ai) µi(Aj)/α for all i, j N,

envy-free if A is 1-EF (or, equivalently, 0-additive-EF),

α-proportional if µi(Ai) 1/(αn) for all i N, and

proportional if A is 1-proportional.

In order for algorithms to access the cake valuations, we assume that they can make CUT and EVAL queries available in the standard model of Robertson and Webb [1998]. For completeness, we state the relationships between different fairness notions.

Proposition 1. Let A be an allocation for n 2 agents, and let α 1.

If A is α-EF, then it is α α 1

n -proportional.

If A is α-EF, then it is α 1 α+1 -additive-EF.

5For brevity, we use the term share for what is sometimes referred to as a connected piece of cake .

If A is α-proportional, then it is 1 2 αn -additive-EF.

Bei and Suksompong [2021] demonstrated that for every n 2, there exists an instance in which no allocation is α-proportional for any α < 2 1/n, even for identical valuations and star graphs. By Proposition 1, one cannot obtain a better guarantee than 2-EF for such instances. We now state a useful lemma about the existence of a share that has sufficiently high value for one agent and, at the same time, not exceedingly high value for other agents.

Lemma 2. Let H be a connected subgraph of a graphical cake, and suppose that H is worth β0 to some agent in a subset N N. Then, for any positive β β0 and any vertex r of H, there exists an algorithm, running in time polynomial in n and the size of H, that finds a partition of H into two (connected) shares such that the first share is worth at least β to some agent in N and less than 2β to every agent in N , and the second share contains the vertex r.

Bei and Suksompong [2021, Lemma 4.9] made this claim for the special case where all agents have the same value for H and no vertex r is specified. We will use Lemma 2 as a subroutine in ITERATIVEDIVIDE (Algorithm 1) and BALANCEPATH (Algorithm 4); ITERATIVEDIVIDE considers the case where different agents may have different values for H, while BALANCEPATH requires the condition on the vertex r in order to maintain connectivity along the minimum-maximum path. We shall use DIVIDE(H, N , β, r) to denote the ordered pair of the two corresponding shares as described in the lemma. The idea behind the proof of Lemma 2 is similar to that of the special case shown by Bei and Suksompong [2021]: we convert H into a tree rooted at the vertex r by removing cycles iteratively keeping the edges and duplicating the vertices if necessary then traverse the tree from r until a vertex v with a subtree of an appropriate size is reached, and finally identify some connected subgraph of the subtree as the first share while assigning the remaining portion as the second share. The full details, including the pseudocode, are given in the full version of our paper [Yuen and Suksompong, 2023].

3 Non-Identical Valuations

In this section, we allow agents to have different valuations. For arbitrary graphs, we present an algorithm that computes an approximately envy-free allocation of a graphical cake when measured additively. For the case where the graph is a star, we give an algorithm that finds an allocation wherein the envy is bounded by a multiplicative factor of roughly 3.

3.1 General Graphs A priori, it is not even clear whether there exists a constant α < 1 independent of n such that an α-additive-EF allocation always exists. We now describe the algorithm, ITERATIVEDIVIDE (Algorithm 1), which finds a 1/2additive-EF allocation for arbitrary graphs and non-identical valuations, using ideas similar to the algorithm by Goldberg et al. [2020] for computing a 1/3-additive-EF allocation of an interval cake. Choose any arbitrary vertex r of G, and start with the entire graph G and all agents in contention. If there

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Algorithm 1 ITERATIVEDIVIDE(G, N). Input: Graph G, set of agents N = {1, . . . , n}. Output: Allocation (A1, . . . , An). Initialization: r any vertex of G; Hn G; N N.

1: for i = 1, . . . , n 1 do 2: βi 1/4 3: if there exists i N such that µi (Hn) βi then 4: (Hi, Hn) DIVIDE(Hn, N , βi, r) 5: i any agent in N who values Hi at least βi 6: else 7: Hi 8: i any agent in N

9: end if 10: Ai Hi 11: N N \ {i } 12: end for 13: Aj Hn, where j is the remaining agent in N

14: return (A1, . . . , An)

is only one agent remaining, allocate the remaining graph to that agent. If the remaining graph is worth less than β = 1/4 to every remaining agent,6 allocate an empty graph to any one of the remaining agents and remove this agent. Otherwise, apply the algorithm DIVIDE on the remaining graph and the remaining agents with threshold β. Allocate the first share to any agent who values that share at least β, and remove this agent along with her share. Repeat the procedure with the remaining graph until the whole graph is allocated. We claim that the resulting allocation is indeed 1/2-additive-EF.

Theorem 3. Given an instance of graphical cake cutting, there exists an algorithm that computes a 1/2-additive-EF allocation in time polynomial in n and the size of G.

While an additive envy of 1/2 can be seen as high, the left example of Figure 1 shows that an envy of 1/3 is inevitable. Moreover, even for an interval cake, the (roughly) 1/4additive approximation of Barman and Kulkarni [2022] is the current best as far as polynomial-time computability is concerned. Although ITERATIVEDIVIDE guarantees that the envy between each pair of agents is at most 1/2, it is possible that some agents receive an empty share from the algorithm. In the remainder of this paper, we present algorithms that find approximately envy-free allocations up to constant multiplicative factors for star graphs as well as for agents with identical valuations. Any such allocation ensures positive value for every agent and, by Proposition 1, is also approximately envy-free when measured additively.

3.2 Star Graphs The case of star graphs presents a natural generalization of the canonical interval cake and, as can be seen in Figure 1, already highlights some of the challenges that graphical cake cutting poses. For this class of graphs, we devise an algorithm

6While the value of β is the same for all iterations here, we write βi in the pseudocode because we will later consider a generalization in which β can be different for different iterations.

that, for any constant ϵ > 0, computes a (3+ϵ)-EF allocation in polynomial time. The algorithm consists of four phases. It starts with an empty partial allocation and finds a small star of stubs near the center vertex (Phase 1). It then repeatedly finds an unallocated share worth slightly more than some agent s share, and allows that agent to relinquish her existing share for this new share care must be taken to ensure that other agents do not have too much value for this new share (Phase 2). This new share could be a segment of an edge (Phase 2a) or a union of multiple complete edges (Phase 2b). This phase is repeated until there are no more unallocated shares suitable for agents to trade with. Finally, the unallocated shares are appended to the agents existing shares (Phases 3 and 4). See Figure 2 for an illustration of each phase. We remark that Phases 2a and 3 of our algorithm are adapted from the algorithm of Arunachaleswaran et al. [2019] for finding a (2 + ϵ)-EF allocation of an interval cake. Let G = (V, E) be a star graph centered at vertex v with m 2 edges. Label the other vertices vk and the edges ek = [vk, v] for k {1, . . . , m}. Fix any ϵ (0, 1).

Phase 1: Preparation. Define ϵ = ϵ 16nm. Initialize an empty partial allocation A = (A1, . . . , An). For each edge ek, find a point xk [vk, v] such that the segment [xk, v] is worth at most ϵ /m to all agents. Define e1 k = [vk, xk] and e2 k = [xk, v] for k {1, . . . , m}, and let E1 and E2 be the sets containing all e1 k s and all e2 k s, respectively. Note that E2 is worth at most ϵ to every agent.

Phase 2: Increase agents shares incrementally. If there is a segment e1 k E1 such that some unallocated interval within e1 k is worth at least µi(Ai) + ϵ to some agent i, go to Phase 2a. Otherwise, consider the segments in E1 that are entirely unallocated. If the union of these segments is worth at least µi(Ai) + ϵ to some agent i, go to Phase 2b. Otherwise, Phase 2 ends; go to Phase 3.

Phase 2a: Allocate a subinterval of some e1 k. Pick an unallocated interval I e1 k that is worth at least µi(Ai) + ϵ to some agent i, and assume without loss of generality that it cannot be extended in either direction without overlapping an allocated share or e2 k. Suppose that I = [a, b], where a is closer to vk than b is. If a = vk, find the point z I closest to a such that [a, z] is worth exactly µi (Ai ) + ϵ to some agent i , and let Ai = [a, z], i.e., agent i relinquishes her existing share for this new share. Else, a = vk; find the point z I closest to b such that [z, b] is worth exactly µi (Ai )+ϵ to some agent i , and let Ai = [z, b]. Repeat Phase 2.

Phase 2b: Allocate multiple edges in E. Let K0 be the set of all indices k such that the entire segment e1 k is unallocated. Initialize K = , and add the indices from K0 to K one by one until {e1 k | k K} is worth at least µi (Ai ) + ϵ to some agent i . Let Ai be the union of ek over all k K, i.e., agent i relinquishes her existing share for this new share. Note that this new share is connected by the center vertex v. Repeat Phase 2.

Phase 3: Append unallocated subintervals within e1 k. Let N1 N consist of all agents who last received a subinterval of some e1 k via Phase 2a, and N2 N consist of all agents

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

(a) Phase 1

(b) Phase 2

(before) xk

(c) Phase 3

(d) Phase 4

Figure 2: (a) The points xk are found, where [xk, v] is worth at most ϵ /m to every agent. (b) The unallocated intervals (dotted lines) are the ones to be considered in Phase 2a. (c) The unallocated intervals (dotted lines) are appended leftwards in vk s direction, except for the one containing vk which is appended rightwards. (d) The remaining unallocated portion H (bold lines) is a share connected by v.

who last received two or more complete edges in E via Phase 2b (we will show later that, in fact, N1 N2 = N). For each e1 k of which some agent from N1 is allocated a subinterval, and for each unallocated interval I = [a, b] e1 k that cannot be extended in either direction without overlapping an allocated share or E2, where a is closer to vk than b is, append I to the share of the agent who is allocated the point a (i.e., append towards vk s direction). The only time this is not possible is when a = vk, in which case we append to the share of the agent who is allocated the point b. Phase 4: Append H. Consider the remaining unallocated portion H of the graph. Note that for each k {1, . . . , m}, we have H ek = {v} or e2 k or ek this means that H is connected by the center vertex v. If N2 is nonempty, append H to the share of an arbitrary agent in N2. Else, if some segment e1 k is allocated to at least two agents, give H to the agent who has been allocated the point xk. Otherwise, we know that every agent is allocated exactly one segment in E1 give H to the agent who traded her share last in Phase 2 (in particular, Phase 2a). We claim that this algorithm yields a (3+ϵ)-EF allocation. By Proposition 1, such an allocation is roughly 1/2-additive EF and (by taking ϵ = 1/n) 3-proportional as well. Theorem 4. Given an instance of graphical cake cutting consisting of a star graph with m edges, there exists an algorithm that, for any ϵ > 0, computes a (3 + ϵ)-EF allocation in time polynomial in n, m, and 1/ϵ.

4 Identical Valuations In this section, we focus on the case where the valuation functions of all agents are identical. While this case is uninteresting for interval cake cutting since a fully envy-free allocation can be trivially found, it becomes highly nontrivial when graphs are involved (see, for example, the left of Figure 1). Indeed, a number of works on dividing edges or vertices of a graph can be interpreted as dealing with the identical-valuation setting [Wu et al., 2007; Chu et al., 2010; Caragiannis et al., 2022]. Moreover, this setting captures scenarios where there is an objective measure across agents, for example, when a town wants to divide the responsibility of maintaining its streets among contractors based on the lengths or numbers of residents on the streets.

As we mentioned in Section 2, an α-EF allocation is not guaranteed to exist for any α < 2, even with identical valuations and star graphs. We will show in this section that, for arbitrary graphs and any ϵ > 0, it is possible to find an allocation that is (2 + ϵ)-EF, which means that the approximation factor of 2 is essentially tight. To this end, we first discuss how we can find a 4EF allocation using a variation of the ITERATIVEDIVIDE algorithm that we saw in Section 3. This 4-EF allocation will later be used as an input to an algorithm that computes a (2 + ϵ)-EF allocation. For star graphs, we also describe a simpler method for computing a 2-EF allocation. Let us denote by µ the common valuation function of the agents, and define max(A) = maxi N µ(Ai) and min(A) = mini N µ(Ai) for any allocation A = (A1, . . . , An).

4.1 4-EF In ITERATIVEDIVIDE, we used the threshold β = 1/4 in every call to DIVIDE so as to allocate a share worth at least 1/4 to some agent, which results in a 1/2-additive-EF allocation. Even with identical valuations, each iteration of DIVIDE is unpredictable in the sense that the recipient could receive a share worth anywhere between β and 2β. If β is chosen to be more than 1/(2n 2) and the first n 1 agents all take shares of value close to 2β, then the last agent will be left effectively empty-handed. In contrast, if β is chosen to be at most 1/(2n 2) and the first n 1 agents all take shares of value only β, then the last agent will receive a share of value at least 1/2, which leads to an envy factor linear in n. To resolve this problem, let us consider using an adaptive threshold that takes the values of the previous shares into account. If the previous agents took large shares, then the threshold β is reduced appropriately for the current agent, and vice versa. Without loss of generality, assume that for each i {1, . . . , n 1}, agent i is the one who takes the first share generated by the ith iteration of DIVIDE. By choosing βi = 1

2( 2i 2n 1 Pi 1 j=1 µ(Aj)) to be the threshold for the ith

iteration of DIVIDE, we claim that the resulting allocation is 4-EF.7 Along the way, we shall see that the allocation is also (2 1/n)-proportional.

7Even better, the allocation is actually (4 1/2n 3)-EF, as shown in the proof of Theorem 5 [Yuen and Suksompong, 2023].

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Algorithm 2 RECURSIVEBALANCE(A, ϵ). Input: Allocation A = (A1, . . . , An), ϵ (0, 1). Output: Allocation A = (A1, . . . , An).

1: while max(A)

min(A) > 2 + ϵ do

2: A BALANCE(A, ϵ) 3: end while 4: return A

Algorithm 3 BALANCE(A, ϵ). Input: Allocation A = (A1, . . . , An), ϵ (0, 1). Output: Allocation A = (A1, . . . , An).

1: P MINMAXPATH(A) 2: A (A \ P) BALANCEPATH(P, ϵ) 3: return A

Theorem 5. Given an instance of graphical cake cutting consisting of n agents with identical valuations, there exists an algorithm that computes a 4-EF and (2 1

n)-proportional allocation in time polynomial in n and the size of G.

As mentioned in Section 2, an α-proportional allocation is not guaranteed to exist for any α < 2 1/n, so the algorithm in Theorem 5 attains the optimal proportionality approximation. In terms of envy-freeness, one may consider adjusting the values of βi in ITERATIVEDIVIDE so as to obtain an allocation with a better approximation factor than 4. While this might be possible, it seems unlikely that this approach could lead to 2-EF, given that the guarantee from Lemma 2 already has a multiplicative gap of 2. This motivates us to devise another algorithm that reduces the factor to arbitrarily close to 2.

4.2 (2 + ϵ)-EF Let us first define a minimum-maximum path of an allocation A = (A1, . . . , An) as a list P = (P1, . . . , Pd) (where d n) satisfying the following conditions:

For each i {1, . . . , d}, Pi = Aj for some j {1, . . . , n},

Pi = Pj for 1 i < j d,

For each i {1, . . . , d 1}, there exists at least one point belonging to both Pi and Pi+1, and

µ(P1) = min(A) and µ(Pd) = max(A).

Intuitively, a minimum-maximum path is a list of shares that chains a minimum-valued one to a maximum-valued one in the underlying graph without crossing any share more than once. Such a list can be found in polynomial time: we locate a minimum-valued share and a maximum-valued share of A, find a path through the graph that connects both shares, and identify the shares corresponding to this path. If some share Ai appears more than once, we repeatedly remove the part between the two occurrences of Ai (including one of these occurrences). Let us use MINMAXPATH(A) to denote an arbitrary minimum-maximum path of A. We now describe the algorithm, RECURSIVEBALANCE (Algorithm 2), which finds a (2 + ϵ)-EF allocation for

Algorithm 4 BALANCEPATH(P, ϵ). Input: List of shares P = (P1, . . . , Pd), ϵ (0, 1). Output: List of d shares (P1, . . . , Pd). Initialization: γ µ(Pd).

1: for i = 1, . . . , d 1 do 2: if µ(Pi) γ 2+ϵ then 3: return (P1, . . . , Pd) 4: end if 5: P Pi Pi+1 6: if µ(P ) < 2γ 2+ϵ then 7: Pi P

8: r any vertex in Pd 9: (Pi+1, Pd) DIVIDE Pd, N, γ

10: return (P1, . . . , Pd) 11: end if 12: if i = d 1 then 13: r any vertex in Pd 14: else 15: r any vertex in Pi+1 Pi+2 16: end if 17: (Pi, Pi+1) DIVIDE P , N, γ 2+ϵ, r

18: end for 19: return (P1, . . . , Pd)

any given ϵ > 0. We employ similar ideas as the ones used by Chu et al. [2010] in their work, they partition the (indivisible) edges of a graph, whereas we have to account for the divisibility of the edges. Assume without loss of generality that ϵ (0, 1). Given an allocation A, RECURSIVEBALANCE repeatedly replaces A with the allocation BALANCE(A, ϵ), then terminates when A is (2 + ϵ)-EF. The algorithm BALANCE (Algorithm 3) finds a minimum-maximum path P of A, and replaces the shares in A that appear in P by BALANCEPATH(P, ϵ). Note that the order of shares in A does not affect the fairness properties due to the identical valuation across all agents. Now, BALANCEPATH (Algorithm 4) does the bulk of the work. This algorithm adjusts the shares in P = (P1, . . . , Pd) so that their values meet certain criteria. Let γ = µ(Pd) and b P1 = P1.8 For each i from 1 to d 1, the algorithm does one of the following unless it is terminated prematurely via Case 1 or Case 2.

Case 1: The value of b Pi is at least γ 2+ϵ.

Set P i = b Pi and P j = Pj for all j {i + 1, . . . , d}. Terminate the algorithm by returning (P 1, . . . , P d).

Case 2: The value of b Pi is less than γ 2+ϵ and the value

of b Pi Pi+1 is less than 2γ 2+ϵ.

Set P i = b Pi Pi+1. Set (P i+1, P d) to be the output of DIVIDE(Pd, N, γ

3 , r), where r is any point in Pd; note that this call to DIVIDE is valid because Pd has value γ. Set P j = Pj for all j {i + 2, . . . , d 1}. Terminate

8We reuse Pi for P i and b Pi in the pseudocode for simplicity; however, we differentiate them in the main text for clarity.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

the algorithm by returning (P 1, . . . , P d).

Case 3: The value of b Pi is less than γ 2+ϵ and the value

of b Pi Pi+1 is at least 2γ 2+ϵ.

Consider the graph P = b Pi Pi+1. Set (P i, b Pi+1) to be the output of DIVIDE(P , N, γ 2+ϵ, r), where r is any point belonging to both Pi+1 and Pi+2 (unless i = d 1, in which case r is any point in Pd); note that this call to DIVIDE is valid because P has value at least 2γ 2+ϵ. The

choice of r ensures that, if i < d 1, b Pi+1 and Pi+2 share at least one point. Continue with the next i by incrementing it by 1.

If the algorithm still has not terminated after i = d 1, set P d = b Pd and return (P 1, . . . , P d). We claim that the algorithm RECURSIVEBALANCE terminates in polynomial time if it receives a 4-EF allocation as input (provided by Theorem 5), and upon termination the algorithm returns a (2 + ϵ)-EF allocation. Theorem 6. Given an instance of graphical cake cutting consisting of n agents with identical valuations, there exists an algorithm that, for any ϵ > 0, computes a (2 + ϵ)-EF allocation in time polynomial in n, 1/ϵ, and the size of G.

4.3 Star Graphs Although RECURSIVEBALANCE provides a nearly 2-EF allocation, the algorithm is rather complex and involves many steps. Moreover, it seems difficult to improve the guarantee to exactly 2-EF via the algorithm, as the balancing of shares may be too slow and we may not reach a 2-EF allocation in finite time.9 For the case of star graphs, it is possible to obtain a 2-EF allocation using a simpler bag-filling approach. Theorem 7. Given an instance of graphical cake cutting consisting of a star graph with m edges and n agents with identical valuations, there exists an algorithm that computes a 2-EF allocation in time polynomial in n and m.

5 Beyond One Connected Piece In previous sections, we made the crucial assumption that each agent necessarily receives a connected piece of the graphical cake. We now relax this assumption and explore improvements in envy-freeness guarantees if each agent is allowed to receive a small number of connected pieces. As mentioned in Section 1.2, extensive research has been done on (approximate) envy-free connected allocations of an interval cake; it will be interesting to draw connections between these results and graphical cake cutting. As an example, consider a star graph with edges ek for k {1, . . . , m}. Rearrange the edges to form a path graph with the edges e1 to em going from left to right; the farthest end of each edge from the center vertex in the star graph is oriented towards the right on the path graph. Note that any segment along the path graph corresponds to at most

9For example, agents with shares of 1 unit and 2 + ϵ units respectively may repeatedly exchange and adjust their shares with each other (through multiple calls to Algorithm 4) but may never reach a multiplicative envy factor of 2.

two connected pieces in the star graph.10 It follows that if a connected α-EF (resp., α-additive-EF) allocation of an interval cake can be found in polynomial time, then there also exists a polynomial-time algorithm that finds an α-EF (resp., α-additive-EF) allocation of the star cake where each agent receives at most two connected pieces. We now consider an arbitrary graph G. Let ϕ be a bijection of the edges of G onto the edges of a path graph with the same number of edges as G, where the orientation of the edges along the path can be chosen. By an abuse of notation, let ϕ(G) be the corresponding path graph. Define the path similarity number of G associated with ϕ, denoted by PSN(G, ϕ), as the smallest number k such that any segment along ϕ(G) corresponds to at most k connected pieces in G. Any results pertaining to connected allocations of an interval cake11 can be directly applied to allocations of G in which each agent receives at most PSN(G, ϕ) connected pieces.

Proposition 8. Let G be a graph and ϕ be a bijection of the edges of G onto ϕ(G) with orientation such that ϕ can be found in polynomial time. If there exists a polynomial-time algorithm that computes a connected α-EF allocation of an interval cake, then there exists a polynomial-time algorithm that computes an α-EF allocation of a graphical cake G where each agent receives at most PSN(G, ϕ) connected pieces. An analogous statement holds for α-additive-EF.

To complement Proposition 8, we provide upper bounds of PSN(G, ϕ) where ϕ can be computed in polynomial time.

Theorem 9. Let G be a tree of height h. Then there exists a bijection ϕ that can be computed in polynomial time such that PSN(G, ϕ) h + 1.

Theorem 10. Let G be a connected graph, and let d be the diameter of a spanning tree of G with the minimum diameter. Then there exists a bijection ϕ that can be computed in polynomial time such that PSN(G, ϕ) d/2 + 2.

6 Conclusion and Future Work

In this paper, we have studied the existence and computation of approximately envy-free allocations in graphical cake cutting. An interesting question left open by our work is whether a connected allocation with a constant multiplicative approximation of envy-freeness can be guaranteed for general graphs and non-identical valuations the techniques that we developed for star graphs (Section 3.2) do not seem sufficient for answering this question. If a non-connected allocation is allowed, then tightening the bounds for the path similarity number (Section 5) will reduce the number of connected pieces each agent receives to achieve the same envyfreeness approximation. Another intriguing direction for nonconnected allocations is whether we can obtain improved envy bounds using a different approach than converting the graph into a path.

10A segment can start and end at points within an edge and span across different edges it need not start and end at vertices. 11For instance, Barman and Kulkarni [2022] presented a polynomial-time algorithm that computes a (roughly) 1/4-additive EF and 2-EF allocation of an interval cake.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Acknowledgments This work was partially supported by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001 and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.

References [Arunachaleswaran et al., 2019] Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, and Nidhi Rathi. Fair and efficient cake division with connected pieces. In Proceedings of the 15th Conference on Web and Internet Economics (WINE), pages 57 70, 2019. Extended version available at Co RR abs/1907.11019v4. [Aziz and Mackenzie, 2016] Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 416 427, 2016. [Barman and Kulkarni, 2022] Siddharth Barman and Pooja Kulkarni. Approximation algorithms for envy-free cake division with connected pieces. Co RR, abs/2208.08670, 2022. [Bei and Suksompong, 2021] Xiaohui Bei and Warut Suksompong. Dividing a graphical cake. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5159 5166, 2021. [Bei et al., 2012] Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1263 1269, 2012. [Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996. [Caragiannis et al., 2022] Ioannis Caragiannis, Evi Micha, and Nisarg Shah. A little charity guarantees fair connected graph partitioning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4908 4916, 2022. [Cechl arov a et al., 2013] Katar ına Cechl arov a, Jozef Doboˇs, and Eva Pill arov a. On the existence of equitable cake divisions. Information Sciences, 228:239 245, 2013. [Chu et al., 2010] An-Chiang Chu, Bang Ye Wu, Hung Lung Wang, and Kun-Mao Chao. A tight bound on the min-ratio edge-partitioning problem of a tree. Discrete Applied Mathematics, 158(14):1471 1478, 2010. [Deligkas et al., 2022] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. The complexity of envy-free graph cutting. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 237 243, 2022. [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., 2021] 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), pages 161 167, 2021. [Goldberg et al., 2020] Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong. Contiguous cake cutting: Hardness results and approximation algorithms. Journal of Artificial Intelligence Research, 69:109 141, 2020. [Igarashi and Zwicker, 2021] Ayumi Igarashi and William S. Zwicker. Fair division of graphs and of tangled cakes. Co RR, abs/2102.08560, 2021. [Procaccia, 2013] Ariel D. Procaccia. Cake cutting: Not just child s play. Communications of the ACM, 56(7):78 87, 2013. [Procaccia, 2016] Ariel D. Procaccia. Cake cutting algorithms. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 13, pages 311 329. Cambridge University Press, 2016. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press, 1998. [Stromquist, 1980] Walter Stromquist. How to cut a cake fairly. American Mathematical Monthly, 87(8):640 644, 1980. [Stromquist, 2008] Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols. The Electronic Journal of Combinatorics, 15:#R11, 2008. [Su, 1999] Francis Edward Su. Rental harmony: Sperner s lemma in fair division. American Mathematical Monthly, 106(10):930 942, 1999. [Suksompong, 2021] Warut Suksompong. Constraints in fair division. ACM SIGecom Exchanges, 19(2):46 61, 2021. [Wu et al., 2007] Bang Ye Wu, Hung-Lung Wang, Shih Ta Kuan, and Kun-Mao Chao. On the uniform edge-partition of a tree. Discrete Applied Mathematics, 155(10):1213 1223, 2007. [Yuen and Suksompong, 2023] Sheung Man Yuen and Warut Suksompong. Approximate envy-freeness in graphical cake cutting. Co RR, abs/2304.11659, 2023.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)