# how_to_cut_a_discrete_cake_fairly__bf9b2d98.pdf

How to Cut a Discrete Cake Fairly

Ayumi Igarashi

The University of Tokyo, igarashi@mist.i.u-tokyo.ac.jp

Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing a discrete cake fairly in which the indivisible goods are aligned on a path and agents are interested in receiving a connected subset of items. We prove that a connected division of indivisible items satisfying a discrete counterpart of envyfreeness, called envy-freeness up to one good (EF1), always exists for any number of agents n with monotone valuations. Our result settles an open question raised by Bil o et al. (2019), who proved that an EF1 connected division always exists for the number of agents n 4. Moreover, the proof can be extended to show the following (1) secretive and (2) extra versions: (1) for n agents with monotone valuations, the path can be divided into n connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the secretive agent ; (2) for n + 1 agents with monotone valuations, the path can be divided into n connected bundles such that when any extra agent leaves, an EF1 assignment of the bundles can be made to the remaining agents.

1 Introduction Imagine a group of researchers scheduling time slots for meetings. Their preferences may be heterogeneous: for example, one researcher may prefer a morning meeting, whereas another may prefer an afternoon meeting. This situation raises the question: how can we allocate time slots fairly? This problem falls within the ﬁeld of the well-known cake-cutting problem, in which the cake, often represented by the unit interval [0, 1], has to be divided between n agents with different preferences. Here, the term cake is a metaphor for a heterogeneous divisible resources, such as land or time. A central notion of fairness in the literature is envyfreeness (Foley 1967), which requires that each agent receives their personal best piece out of the allocated pieces. In this scenario, no agent wishes to replace their allocated portion with that of any other agent. The classical result shows that under mild assumptions on the agents preferences, there is an envy-free division offering each agent a

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

connected piece (Stromquist 1980; Su 1999; Woodall 1980). Note that the connectivity constraint is crucial in various contexts, particularly when the resource has temporal or spacial structure. In many application domains, the resource may be indivisible. For example, time is often divided into discrete time units, such as scheduled shifts and research seminars. As another example, land may be divided into discrete land plots, due to geographical or historical constraints. A discrete version of the cake-cutting problem has been considered in several papers recently (Bil o et al. 2019; Bouveret et al. 2017; Marenco and Tetzlaff 2014; Suksompong 2019). In this framework, the indivisible items are aligned on a path and each agent is allocated to a connected bundle of items. In allocation of indivisible resources, envy-freeness is not guaranteed. Indeed, in the case of one item and two agents, one agent necessarily receives nothing and therefore envies the other. Nevertheless, the objective can be naturally relaxed via approximations. An approximate notion of envyfreeness, called envy-freeness up to one good (EF1), has been intensively investigated in recent years (Budish 2011). EF1 allows agents to envy other agents but the envy can be eliminated after removing one item from others bundles. Several algorithms achieve EF1 within the standard setting of fair division of indivisible items (Lipton et al. 2004; Caragiannis et al. 2016). For agents with monotone valuations, the envy-cycle algorithm in Lipton et al. (2004) returns an EF1 division. For agents with monotone additive valuations, an allocation maximizing the Nash product of agents valuations satisﬁes EF1 (Caragiannis et al. 2016). Can we achieve EF1 under the connectivity constraint of a path? This question was partially answered by Bil o et al. (2019). They showed that an EF1 connected division exists for any monotone valuations when there are at most four agents. They followed Su s approach (Su 1999) using Sperner s lemma: The possible divisions of the path can be encoded by the vertices of a triangulated (n 1)-dimensional simplex; see Figure 1 for an illustration with n = 3. Each agent colors each vertex with the index of the most preferred bundle of the partition represented by each vertex. Sperner s lemma then implies the existence of a small simplex labeled with distinct agents and colored with different indices of bundles. Loosely speaking, this simplex corresponds to a sequence of similar divisions, each of which satisﬁes different agents

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

with different bundles. Bil o et al. (2019) developed a rounding technique of such a simplex that works for four or fewer agents. However, the existence of EF1 is unclariﬁed when the number of agents n is more than four, while a connected division satisfying the weaker fairness notion of EF2, requiring the envy to be bounded up to two items, exists for any number of agents (Bil o et al. 2019). A key issue in this proof lies in the left-right symmetry in the agents evaluation. Since agents treat left-most and right-most items of a bundle symmetrically, they may face a conﬂict with another agent who want neighboring bundles. See Section 3.1 for details. To settle this open question, we show that an EF1 connected division exists for any number of agents with monotone valuations. Our proof adopts the rounding technique of a simplex, similar to that developed in Bil o et al. (2019), but our ﬁnal path division has left-right asymmetry. Namely, our rounding algorithm prioritizes an agent who wants a left bundle over an agent who wants a right bundle on the simplex. In our proof, each agent is pessimistic about obtaining the left-most item and optimistic about obtaining the rightmost item, which ensures that the estimate of each agent i on the j-th bundle of the ﬁnal output is neither overly optimistic nor overly pessimistic. In this way, we can successfully circumvent the difﬁculty arising when n 5. In fact, we show the existence of a connected division satisfying a slightly stronger notion of EF1outer, which additionally requires that the envied bundles remain connected after removing an item.1

Exploiting the proof of this theorem, we further obtain the discrete analogs of the existential result concerning a secretive envy-free divisions of the cake (Woodall 1980; Asada et al. 2018; Meunier and Su 2019): for any number n of agents with monotone valuations over a path, one can divide the path into n parts such that whichever part a secretive agent chooses, an EF1outer assignment of the remaining bundles can be made to the other agents. For two agents, such existence directly follows from a discrete version of the cut-and-choose protocol over the path: the ﬁrst agent computes an EF1outer connected division among two agents as if the other agent has the same valuation, and then the second agent (called the secretive agent) selects a preferred bundle, leaving the remainder for the ﬁrst agent. Here, the valuation of one agent is sufﬁcient to ﬁnd a partition such that whichever part another agent chooses, the resulting assignment is EF1outer. More generally, our result shows that the valuations of n 1 agents sufﬁce to ﬁnd an EF1outer connected division among n agents. Note that without connectivity constraints, a secretive EF1 division is known to exist and can be computed in polynomial time when the agents have monotone valuations (Arunachaleswaran, Barman, and Rathi 2019). However, our result is the ﬁrst to show that the existential result holds in conjunction with connectivity requirements. Finally, we show the dual statement that for n + 1 agents with monotone valuations, the path can be partitioned into n connected subsets such that when any extra agent leaves, an

1The result of Bil o et al. (2019) also holds with EF2outer for any number of agents with monotone valuations.

( , 1234, )

( , 123, 4)

( , 12, 34)

( , 1, 234)

(1, , 234) ( , , 1234)

Figure 1: Illustration of a simplex whose vertices represent divisions of a path with four vertices into three bundles. In the small triangle colored in light gray, agent A most-prefers the third bundle at the left corner vertex, B most-prefers the ﬁrst bundle at the middle corner vertex, and C most-prefers the second bundle at the right corner vertex.

EF1outer assignment of the bundles can be made to the remaining agents, thereby establishing the discrete counterpart of the existence of an extra envy-free cake division, recently shown by Meunier and Su (2019). An important application of our results is that for graph fair division proposed by Bouveret et al. (2017). This setting captures, e.g., the division of road networks, where the items can be aligned on a graph and the agents value connected bundles of the items. Our results on a path apply to a wider class of traceable graphs that admit a Hamiltonian path. Indeed, for such graphs, one can take a Hamiltonian path of the original graph and apply our result to obtain an EF1outer connected division of the Hamiltonian path; the resulting division is trivially both EF1outer and connected in the original graph.2 Thus, for any number of agents with monotone valuations, an EF1outer connected division of a graph exists whenever the graph is traceable. Related work To the best of our knowledge, the problem of dividing a discrete cake, i.e., a path, has been ﬁrst considered in (Marenco and Tetzlaff 2014; Suksompong 2019; B ar any and Grinberg 2015). Marenco and Tetzlaff (2014) studied a special valuation in which each item is liked by exactly one agent and showed that an envy-free division exists for such valuations. Suksompong (2019) considered approximation of envy-freeness, showing that a simple rounding of an envy-free division gives us a division such that the envy is bounded by at most 2vmax for agents with additive valuations, where vmax is the maximum value of the agents for the single items. A result similar to this has been obtained in B ar any and Grinberg (2015). Bouveret et al. (2017) proposed a model for allocating indivisible goods under connectivity constraints of a graph. The graph fair division has attracted a great deal of attention since then (Bouveret, Cechl arov a, and Lesca 2019; Igarashi and Peters 2019; Bei et al. 2021; Truszczynski and Lonc 2020; Bil o et al. 2019;

2This observation has already been made in Bil o et al. (2019).

Bouveret et al. 2017; Greco and Scarcello 2020; Deligkas et al. 2021). Bil o et al. (2019) developed several methods to obtain an EF1 division under connectivity constraints of a path when the number of agents is two, three, or four, or when the agents have identical monotone valuations.

2 Preliminaries For each natural number s N, we write [s] = {1, 2, . . . , s}. For each pair of natural numbers s, t N with s t, we write [s, t] = {s, s + 1, . . . , t}. We are given n agents and m items (or goods). We may refer to subsets of items as bundles. The items are aligned along a path (1, 2, . . . , m). Each agent i has a valuation function vi that assigns a real value to every connected subset of the path. For two connected subsets S and T, an agent i weakly prefers (resp. strictly prefers) S to T if vi(S) vi(T) (resp. vi(S) > vi(T)). We assume that all agents have monotone valuations, i.e., each agent i weakly prefers T to S whenever S T and that vi( ) = 0 for each i N. A division is a partition I = (I1, I2, . . . , In) of the path into n connected bundles, where Ii is the ith bundle from the left. A division I is envy-free if there exists a permutation π: [n] [n] such that vi(Iπ(i)) vi(Iπ(j)) for any pair i, j of agents. An envy-free division is not guaranteed when the items are indivisible. For instance, when two agents desire one item, one agent gets the item, whereas the other gets nothing. Thus, Budish (2011) relaxed the envy-freeness condition to envy-freeness up to one good (EF1). In an EF1 division, an agent can envy another agent, but envy will disappear after one item is removed from the other s bundle. We adopt a slightly more robust version of EF1, introduced in Bil o et al. (2019), requiring that removing the items leave the envied bundles connected. Deﬁnition 2.1 (EF1outer: envy-freeness up to one outer good). A division I satisﬁes EF1outer if there exists a permutation π: [n] [n] such that for any pair i, j of agents, vi(Iπ(i)) vi(Iπ(j)), or there exists a good g Iπ(j) such that Iπ(j)\{g} is connected3 and vi(Iπ(i)) vi(Iπ(j)\{g}). In our context, EF1outer is fairer than EF1. In particular, EF1 may not be binding at all when nonconnected subsets are less preferred compared with connected subsets or even undesirable; for instance, when allocating time slots for certain tasks among multiple employees, people often value being allocated a contiguous chuck of time, instead of being allocated to a disconnected one. We introduce the following notation in Bil o et al. (2019). For every connected subset I, we deﬁne the up-to-one valuation v i of agent i as

0 if I = , min vi(I \ {g}) : g I such that I \ {g} is connected if I = .

Clearly, a division I satisﬁes EF1outer if and only if there exists a permutation π: [n] [n] such that vi(Iπ(i)) v i (Iπ(j)) for any pair i, j of agents.

3We consider the empty set to be connected.

Throughout this paper, we assume that the number of items exceeds the number of agents, i.e., m n. Note that if m < n, a trivial EF1outer division exists.

2.1 Sperner s Lemma and Envy-free Divisions We review basic notions of combinatorial topology and explain the link between Sperner s lemma and the classical cake cutting problem. An (n 1)-simplex S is the convex hull of n main vertices x1, x2, . . . , xn; we write S = x1, x2, . . . , xn . For j [n], we write ej {0, 1}n as the j-th unit vector, where ej h = 1 if h = j and ej h = 0 otherwise. The (n 1) standard simplex n 1 is the (n 1)- simplex whose main vertices are given by e1, e2, . . . , en. A triangulation T of an (n 1)-simplex S is a collection of smaller n 1 simplices S1, S2, . . . , Sk where S = Sk j=1 Sj, and for each pair of distinct indices i, j [k], the intersection Si Sj is either empty or a face common to them. We refer to S1, S2, . . . , Sk as elementary simplices. We denote by V (T) the set of vertices of a triangulation T. Given a triangulation T of an (n 1)-simplex S, a coloring is a function λ: V (T) 2[n] that assigns to each vertex x V (T) a subset λ(x) [n], where each element of [n] is (called) a color. A coloring λ: V (T) 2[n] is (called) proper if we can write S = x1, x2, . . . , xn such that if a vertex x V (T) is colored by index j, i.e., j λ(x), then xj is a vertex of a minimal face containing x. A fully-colored elementary simplex S = x 1, x 2, . . . , x n has a complete set of colors, i.e., there exists a permutation π: [n] [n] such that π(i) λ(x i ) for each i [n]. Sperner s lemma states that a triangulated simplex with a proper coloring admits a fully-colored elementary simplex.

Theorem 2.2 (Sperner s lemma). Any triangulation T of an (n 1)-simplex with a proper coloring λ: V (T) 2[n] admits a fully-colored elementary simplex.

Su (1999) was the ﬁrst to demonstrate the usefulness of Sperner s lemma in the context of cake-cutting, citing Simmons as the one who conceptualized the proof. The Simmons Su method encoded possible divisions of the cake [0, 1] by the points of an (n 1) standard simplex where the i-th coordinate can be interpreted as the i-th knife position, obtaining an envy-free division based on a labeling and coloring of the (n 1) standard simplex as follows. First, we assign an agent label to each vertex so that the vertices of each elementary simplex have n distinct agent labels. Formally, an owner labeling of the triangulation T of an (n 1)-simplex is a function a: V (T) [n] such that for each pair of distinct vertices xi and xj of S with i = j, a(xi) = a(xj), where each a(x) is called the owner of a vertex. There is a triangulation of the simplex that does not admit an owner labeling; see, e.g., Figure 1 in Deng, Qi, and Saberi (2012). Nevertheless, some triangulations, e.g., Kuhn s triangulation and the barycentric triangulation, do admit owner labelings, while allowing small mesh size (Su 1999; Deng, Qi, and Saberi 2012). Second, since the vertices of the triangulation correspond to divisions of the cake, we go to each vertex of the triangu-

Figure 2: Illustration of the labeling-coloring proof when there are three agents A, B, C. The blue, red, white vertices correspond to the divisions where the ﬁrst, second, and third pieces are the most favorite pieces of an owner agent, respectively. The three elementary simplices colored in light gray correspond to fully-colored simplices.

lation and ask the owner to color that vertex with the indices of the most preferred piece of the corresponding division. An illustration of a triangulation and the labeling-coloring approach is given in Figure 2. Such a coloring is proper if each agent never chooses the piece of zero-length. For example, when n = 3, the corner vertices have distinct colors as they correspond to divisions in which one piece includes the entire cake; further, the vertices on each side correspond to divisions in which one piece is empty, thus missing one color that corresponds to the empty piece. By Sperner s lemma, this construction yields a fully-colored elementary simplex S . Now, observe that in S , each agent points out a different piece of her owned division as a most preferred piece. If the simplex vertices are close enough, it corresponds to an approximate solution that converges to an envy-free contiguous division for a sequence of ﬁner triangulations. In the next section, we will adopt the Simmons Su method to the setting of discrete cake-cutting.

3 Existence of Connected EF1 Divisions In this section, we prove the the main result of this paper. Theorem 3.1. For any number of agents with monotone valuation functions on a path, a connected EF1outer division exists. Let us ﬁrst illustrate potential approaches to prove the existence of a connected EF1outer division. We will then proceed to identifying some of the problems with these approaches, and explain how we overcome them.

3.1 Potential Approach One possible approach to prove Theorem 3.1 is to treat a path (1, 2, . . . , m) as an interval [0, m], extend valuation functions to continuous ones, and apply some rounding of an envy-free connected division of the cake, which is guaranteed to exist (Su 1999; Woodall 1980; Stromquist 1980). This approach was also investigated by Suksompong (2019);

however, a division obtained via this approach satisﬁes a weaker fairness property. In particular, it can lead agents to steal an item instead of removing it from another agent s bundle to eliminate envy; see Section 5 of Bil o et al. (2019) for details. Instead, Bil o et al. (2019) followed the approach of Su (1999) that directly works on the simplex and rounds an elementary simplex, corresponding to a series of divisions. Like Su (1999), they encoded possible conﬁgurations of the n 1 knives as the vertices of a triangulated simplex. Bil o et al. observed that if the conﬁguration space only considers fully integral divisions, i.e., if knives move from one edge to another edge, the divisions corresponding to the vertices in each elementary simplex are too far apart from each other to ensure EF1: in their ﬁnal rounding, one agent may get one additional item together with her desired bundle while another may lose one item, which makes it difﬁcult to bound the envy up to one item. Thus, they consider a ﬁner triangulation, allowing knives to move at both edges and vertices of a path. More precisely, they consider the following simplex:

Sm := x Rn 1 +

1 2 x1 x2 xn 1 m + 1

and use a Kuhn s triangulation Thalf of Sm (Deng, Qi, and Saberi 2012) where the vertices V (Thalf) are given by

V (Thalf) = x Rn 1 +

2, 1, . . . , m + 1

and it satisﬁes the property that each elementary simplex S = x1, x2, . . . , xn of Thalf is balanced, meaning that there exists a permutation φ: [n] [n] such that

xφ(i+1) = xφ(i) + 1

2eφ(i), for each i [n 1]. (1)

The above property ensures that the vertices of the elementary simplex can be arranged in such a way that every distinct knife in this sequence moves always in half-step and in the same direction and such a movement happens exactly once over the sequence. For each vertex x = (x1, x2, . . . , xn 1) V (Thalf), we call each xj the j-th knife position; item y {1, 2, . . . , m} is hidden by a knife xj if y = xj. Here, V (Thalf) encodes all the possible conﬁgurations (x1, x2, . . . , xn 1) of the n 1 knives that move in half-steps. Speciﬁcally, each vertex x V (Thalf) induces a partial division I(x) = (I1(x), I2(x), . . . , In(x)) where each j-th bundle for j [n] is given by

Ij(x) = {y {1, 2, . . . , m} | xj 1 < y < xj },

setting x0 = 1

2 and xn = m + 1

2. For example, when m = 12, n = 5, and x = (3, 9

2 ), I(x) corresponds to the partial division ({1, 2}, {4}, {5, 6, 7}, {9, 10}, {11, 12}). Items 3 and 8 are hidden by the two knives x2 and x3 and the other items are uncovered at x. For each x V (Thalf) and each j [n], we say that ℓj(x) := xj 1 + 1

2 is the left-most boundary item of Ij(x); similarly, we say that rj(x) := xj 1

2 is the right-most boundary item of Ij(x). Note that if ℓj(x) is hidden by the (j 1)-th knife, it is the

B1 B2 B3 B4 B5 y1 y2 y3 y4

I(xφ(1)) 1 2 3 4 5 6 7 8 9 10 11 12 x1 x2 x3 x4

I(xφ(2)) 1 2 3 4 5 6 7 8 9 10 11 12 x1 x2 x3 x4

I(xφ(3)) 1 2 3 4 5 6 7 8 9 10 11 12 x1 x2 x3 x4

I(xφ(4)) 1 2 3 4 5 6 7 8 9 10 11 12 x1 x2 x3 x4

I(xφ(5)) 1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12

x1 x2 x3 x4

Figure 3: Example of a sequence of partial divisions represented by an elementary simplex of Thalf. Each knife moves in half-step and the movement happens only once over the sequence.

I 1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12 xi

Figure 4: Division returned by Algorithm 1 for an elementary simplex whose vertices correspond to the partial divisions of Figure 3. Note that the second bundle I 2 receives the boundary item 5 because it satisﬁes the condition (b) of Line 9 while the fourth bundle I 4 does not receive item 11 because it violates the condition (b) of Line 9.

boundary item between Ij 1(x) and Ij(x) and if not, it is the leftmost item of Ij(x); similarly, if rj(x) is hidden by the j-th knife, it is the boundary item between Ij(x) and Ij+1(x), and if not, it is the rightmost item of Ij(x). We say that item y {1, 2, . . . , m} fully appears (or, is fully visible) in Ij(x) if y Ij(x). How does each agent evaluate each of the partial divisions I(x)? Bil o et al. introduced the following virtual valuations: for a bundle Ij(x) in which at least one of the boundary items is fully visible, agents expect to obtain only those items that are fully visible in the bundle; for other bundles Ij(x) in which no boundary item fully appears, agents expect to obtain the items that are fully visible in the bundle as well as at least one of the boundary items (choose one that is less valuable). Agents then color each of the vertices with the index of the favorite bundles based on virtual valuations. This coloring can be shown to be proper; thus, using a more general version of Sperner s lemma considering n colorings, we get a fully-colored simplex S that is fullylabeled, meaning that S receives different agent labels that like different bundles best.4

4Because Kuhn s triangulation admits an owner labeling, instead of using a general version of Sperner s lemma, the labelingcoloring approach of Su (1999) also shows the existence of S . In

Note that each vertex in S only induces a partial division. How can we use S to obtain a full division? Bil o et al. showed that S can be rounded to yield an EF1outer connected division for four or fewer agents as follows. First of all, recall that for each elementary simplex S = x1, x2, . . . , xn of Thalf, there exists a permutation φ : [n] [n] satisfying (1). Thus, S corresponds to a sequence of partial divisions (I(xφ(1)), I(xφ(2)), . . . , I(xφ(n))), where each partial division I(xφ(k)) is obtained from I(xφ(k 1)) by moving one of the knives in half-step and the movement of each knife occurs only once across n partial divisions. An example of such sequences of partial divisions is shown in Figure 3. Using this, our path can be divided into (B1, y1, B2, . . . , yn 1, Bn) where each Bj is the set of items that fully appear in the j-th bundle of all partial divisions, and each yj is the boundary item that can appear in both of the j-th and the (j+1)-th bundles over the sequence. Building (B1, y1, B2, . . . , yn 1, Bn) for S , a division I = (I 1, I 2, I 3, I 4) for four agents can be constructed as follows:

our proof of the next subsection, we use this approach to construct a proper coloring as the proof becomes slightly more elementary.

1. Each I j of interior bundles with j {2, 3} consists of Bj together with the boundary items yj 1 or yj fully appearing in the j-th bundle of some partial division represented by the vertices in S . If none of the boundary items yj 1 or yj fully appears in the j-th bundle, I j additionally gets one boundary item that is adjacent to an exterior bundle I j with j {1, 4}. 2. Each exterior bundle I 1 (respectively, I 4) consists of B1 together with y1 (respectively, y3) if y1 (respectively, y3) is not allocated yet.

With this approach, Bil o et al. established an EF1outer connected division for four or fewer agents. However, the fouragent proof in Bil o et al. does not extend to the general case. Their proof requires that each interior bundle receives an item traversed by a knife due to the left-right symmetry in their valuations. This requirement is met by four agents as the interior bundles (i.e., the second and third bundles) are adjacent to some exterior bundle (i.e., the ﬁrst and fourth bundles). When the number of agents is ﬁve or more, any division includes a bundle that is not adjacent to any of exterior bundles.

3.2 Our Approach Following the discretization approach developed in Bil o et al. (2019), we prove that an EF1 connected division exists for any number of agents with monotone valuations. When extending the result beyond four agents, the main difﬁculty is to ﬁnd appropriate ways to evaluate bundles of partial divisions and to round the half-integral simplices. To this end, we create a left-right asymmetry both in the evaluation phase and in partial-division rounding. Intuitively, our rounding algorithm, formalized in Algorithm 1, prioritizes a left agent (i.e., an agent who is assigned to j-th bundle) over a right agent (i.e., an agent who is assigned to (j + 1)-th bundle) when allocating each boundary item yj. Our deﬁnition of virtual valuations allows us to do such rounding since each agent is pessimistic about obtaining the left-most boundary item and optimistic about obtaining the right-most boundary item. This then guarantees that the value of each agent s allocated bundle in the ﬁnal division I is at least the value of the favorite bundle in their owned division, which is at least the value of another bundle in I after the removal of one outer-item. Below, we prove that our technique successfully ensures that the ﬁnal division is EF1outer. Our proof is divided into the following two steps of coloring and rounding: ﬁrst, we assign to each vertex an owner labeling and a color according to the preferences of owners; second, we round a fully-colored simplex into a full division. See Figure 2 for an illustration. We use the same simplex Sm and triangulation V (Thalf) as previously described.

Coloring We deﬁne the virtual valuation ˆvi(x, j) of each vertex x of the triangulation. The virtual valuation determines how each owner agent assigns a color to his or her owned vertex. First, an agent who obtains the left exterior bundle j = 1 expects to obtain the items not hidden by the right-most knife:

ˆvi(x, 1) = vi(I1(x)).

For the interior bundles 2 j n 1, we set ˆvi(x, j) = 0 if Ij(x) = . Otherwise, the value ˆvi(x, j) is given as follows:

ˆvi(x, j) =

v i (Ij(x) {ℓj(x), rj(x)}) if ℓj(x) Ij(x) and rj(x) Ij(x), vi(Ij(x) \ {ℓj(x)}) if ℓj(x) Ij(x) and rj(x) Ij(x), v i (Ij(x) {rj(x)}) if ℓj(x) Ij(x) and rj(x) Ij(x), vi(Ij(x)) if ℓj(x) Ij(x) and rj(x) Ij(x).

For the right exterior bundle j = n, the item ℓn(x) is not expected in the ﬁnal bundle I j :

ˆvi(x, n) = vi(In(x) \ {ℓn(x)})

Based on these virtual valuations, we deﬁne coloring functions λi : V (Thalf) 2[n] for each agent i [n] where

λi(x) = argmax{ ˆvi(x, j) | j [n] such that Ij(x) = }.

It is not difﬁcult to see that these colorings are proper. It is known that Kuhn s triangulation admits an owner labeling a: V (Thalf) [n] where each elementary simplex has distinct owner labels (Deng, Qi, and Saberi 2012). We aggregate the colorings according to the preference of each owner as follows: λ(x) = λa(x)(x).

Because each coloring λi is proper, so is λ.

Rounding Next, we present how to round each elementary simplex S = x1, x2, . . . , xn of Thalf into a division I = (I 1, I 2, . . . , I n) as speciﬁed in Algorithm 1. Initially, in Line 2, each I j is allocated to the set Bj of items that fully appear in all the j-th bundles Ij(x1), . . . , Ij(xn) of partial partitions represented by the elementary simplex S. In Lines 3 10, Algorithm 1 allocates, from left to right, each boundary item yj that appears in both jth and j+1st bundles on the sequence Ij(x1), . . . , Ij(xn). Speciﬁcally, we use the following left-right asymmetric rounding (Line 9): each bundle I j obtains item yj if

(a) yj fully appears in some of the j-th bundles Ij(x1), . . . , Ij(xn), or (b) I j does not obtain item yj 1 in the previous step and none of the Ij(xk) coincides with Bj for k [n].

In this way, each interior bundle I j must receive at least one of its adjacent boundary items, except when Ij(xk) coincides with Bj for some k [n]. See Figure 4 for an example of the division returned by Algorithm 1. In Lemma 3.2, we show that the estimate of each agent i on the j-th bundle of the output is neither overly optimistic nor overly pessimistic when applying Algorithm 1 to any elementary simplex S of Thalf. The case distinction in the proof of Lemma 3.2 considers whether the bundle is an interior or exterior one, whether the bundle receives two boundary items, exactly one boundary item, or none of them, and

Algorithm 1: Rounding into a division

Input: an elementary simplex S = x1, x2, . . . , xn Output: a division I = (I 1, I 2, . . . , I n)

1 for j [n], let Bj = Ij(x1) Ij(x2) Ij(xn) and let yj be the item such that yj = xj k for some k [n];

2 initialize I j Bj for each j = 1, 2, . . . , n;

3 if y1 fully appears in the ﬁrst bundle of some division, i.e., y1 I1(xk) for some k then

4 I 1 I 1 {y1};

5 for j = 2, . . . , n 1 do

6 if yj 1 is unallocated, i.e., yj 1 S k j 1 I k then

7 I j I j {yj 1};

8 if yj 1 = yj then

9 if (a) yj Ij(xk) for some k [n]; or (b) yj 1 is already allocated to some other agent, i.e., yj 1 S k j 1 I k, and there is no k [n] with xj 1 k = yj 1 + 1

2 and xj k = yj 1

10 I j I j {yj};

11 if yn 1 is unallocated, i.e., yn 1 S k n 1 I k then

12 I n I n {yn 1};

13 return (I 1, I 2, . . . , I n);

whether each of the knives that induce the bundle is located left to the boundary item, at the boundary item, or right to the boundary item. The proof is presented in the full version (?). Lemma 3.2. Consider the triangulation Thalf of Sm. Let S = x1, x2, . . . , xn be any elementary simplex of Thalf and let (I 1, I 2, . . . , I n) be a division returned by Algorithm 1. Then, for each i, j, k [n], we have vi(I j ) ˆvi(xk, j) v i (I j ). We are now ready to prove Theorem 3.1.

Proof of Theorem 3.1. Applying Theorem 2.2 to the triangulation Thalf with the coloring function λ, we obtain an elementary simplex S = x 1, x 2, . . . , x n of Thalf. On this simplex, there exists a permutation π: [n] [n] such that for each i [n], π(i) λ(x i ). That is, for each i [n], the bundle with index π(i) in the division I(x i ) is the bundle most preferred by the owner a(x i ):

ˆva(x i )(x i , π(i)) ˆva(x i )(x i , j) for each j [n]. (2)

Without loss of generality, we assume that a(x i ) = i for each i [n]. Applying Algorithm 1 to S , we obtain a division I = (I 1, I 2, ..., I n). For every pair of agents i, j [n], we have

vi(I π(i)) ˆvi(x i , π(i)) by Lemma 3.2,

ˆvi(x i , j) since π(i) λi(x i ),

v i (I j ) by Lemma 3.2.

Thus, π certiﬁes that I is a desired division.

4 Secretive and Extra Versions

In this section, we consider the secretive and extra versions of EF1 existence. A secretive EF1outer division for agent i is a division I = (I1, I2, . . . , In) of a path into n connected subsets where whichever part a secretive agent i selects, an EF1outer assignment of the remaining bundles can be made to the other agents, i.e., for every index j [n], there exists a bijection π: [n]\{i } [n]\{j} such that for every nonsecretive agent i [n]\{i }, vi(Iπ(i)) maxi [n] v i (Ii ). For n + 1 agents with monotone valuations, an extra EF1outer division is a division I = (I1, I2, . . . , In) of a path into n connected subsets when any extra agent i leaves, an EF1outer assignment of the bundles can be made to the remaining agents, i.e., for every extra agent i [n + 1], there exists a bijection π: [n + 1] \ {i } [n] such that for every remaining agent i [n + 1] \ {i }, vi(Iπ(i)) maxj [n] v i (Ij ). By using a more general version of Sperner s lemma for multiple proper colorings (Meunier and Su 2019) and applying our rounding technique in the previous section, we obtain the existence of a secretive EF1outer connected division as well as that of an extra EF1outer connected division. The proofs are presented in the full version (?).

Theorem 4.1. Suppose that there are n agents with monotone valuations over connected bundles of a path. Then, for any agent i [n], there exists a secretive EF1outer division for i .

Theorem 4.2. Suppose that there are n + 1 agents with monotone valuations over connected bundles of a path. Then, there exists an extra EF1outer division.

5 Conclusion and Future Work

We proved that under connectivity constraints, an EF1 division exists for any number of agents with monotone valuations, thereby resolving the open problem raised by Bil o et al. (2019). We further demonstrated the robustness of our rounding technique, by extending this existential result to the secretive and extra variants. Recent research on fair division extensively investigates the setting where agents may have both positive and negative values for the items (Aziz et al. 2019; Meunier and Zerbib 2019; Segal-Halevi 2018; B erczi et al. 2020; Joji c, Panina, and ˇZivaljevi c 2021). In particular, Aziz et al. (2019) proposed an extension of EF1 to this more general setting, requiring agents envy to disappear after removal of one chore from an envious bundle or that of one good from an envied bundle. It will be interesting to investigate whether such fairness notion can be achieved under connectivity constraints of a path. Finally, this study highlights that the complexity of ﬁnding an EF1 connected division is an open problem. It would be interesting to settle the complexity question for a simple class of valuations, e.g. binary additive valuations.

Acknowledgments

The author thanks Fr ed eric Meunier, Dominik Peters, Warut Suksompong, William S. Zwicker, and the anonymous reviewers for valuable insights and feedback. This work was partially supported by JST PRESTO under grant number JPMJPR20C1.

Arunachaleswaran, E. R.; Barman, S.; and Rathi, N. 2019. Fair Division with a Secretive Agent. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI), 1732 1739.

Asada, M.; Frick, F.; Pisharody, V.; Polevy, M.; Stoner, D.; Tsang, L. H.; and Wellner, Z. 2018. Fair Division and Generalizations of Spernerand KKM-type Results. SIAM Journal of Discrete Mathematics, 32(1): 591 610.

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.; 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), volume 35, 5151 5158.

B erczi, K.; B erczi-Kov acs, E. R.; Boros, E.; Gedefa, F. T.; Kamiyama, N.; Kavitha, T.; Kobayashi, Y.; and Makino, K. 2020. Envy-free Relaxations for Goods, Chores, and Mixed Items. Co RR, abs/2006.04428.

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. Extended version: Co RR, abs/1808.09406.

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: 540 563.

Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6): 1061 1103.

B ar any, I.; and Grinberg, V. S. 2015. Block partitions of sequences. Israel Journal of Mathematics, 206: 155 164.

Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), 305 322.

Deligkas, A.; Eiben, E.; Ganian, R.; Hamm, T.; and Ordyniak, S. 2021. The Parameterized Complexity of Connected Fair Division. In Proceedings of the 30th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 139 145.

Deng, X.; Qi, Q.; and Saberi, A. 2012. Algorithmic Solutions for Envy-Free Cake Cutting. Operations Research, 60(6): 1461 1476. Foley, D. K. 1967. Resource Allocation and the Public Sector. Yale Economics Essays, 7(1): 45 98. Greco, G.; and Scarcello, F. 2020. The Complexity of Computing Maximin Share Allocations on Graphs. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI), 2006 2013. 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), volume 33, 2045 2052. Joji c, D.; Panina, G.; and ˇZivaljevi c, R. 2021. Splitting Necklaces, with Constraints. SIAM Journal on Discrete Mathematics, 35(2): 1268 1286. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), 125 131. Marenco, J.; and Tetzlaff, T. 2014. Envy-free Division of Discrete Cakes. Discrete Applied Mathematics, 164: 527 531. Meunier, F.; and Su, F. E. 2019. Multilabeled Versions of Sperner s and Fan s lemmas and Applications. SIAM Journal on Applied Algebra and Geometry, 3: 391 411. Meunier, F.; and Zerbib, S. 2019. Envy-free Cake Division without Assuming the Players Prefer Nonempty Pieces. Israel Journal of Mathematics, 234: 907 925. 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 Multi Agent Systems (AAMAS), 1276 1284. Stromquist, W. 1980. How to Cut a Cake Fairly. The American Mathematical Monthly, 87(8): 640 644. Su, F. E. 1999. Rental Harmony: Sperner s Lemma in Fair Division. The American Mathematical Monthly, 106(10): 930 942. Suksompong, W. 2019. Fairly Allocating Contiguous Blocks of Indivisible Items. Discrete Applied Mathematics, 260: 227 236. Truszczynski, M.; and Lonc, Z. 2020. Maximin Share Allocations on Cycles. Journal of Artiﬁcial Intelligence Research, 69: 613 655. Woodall, D. R. 1980. Dividing a Cake Fairly. Journal of Mathematical Analysis and Applications, 78(1): 233 247.