Connected EF1 Allocations Exist in Discrete Chore Cutting

1 Introduction

Cake cutting is a fundamental problem that has attracted extensive attention in economics, mathematics, and computer science [Brams and Taylor, 1996; Procaccia, 2016; Robertson and Webb, 1998]. In this problem, the "cake" - represented as the unit interval [0, 1] - serves as a metaphor for a heterogeneous, divisible resource to be allocated among agents with varying preferences. Beyond its scientific importance, the cake-cutting problem is intellectually engaging and gives rise to a variety of intriguing and challenging questions [Procaccia, 2013]. One such question is how to divide the cake in an envy-free manner [Aziz and Mackenzie, 2016; Dubins and Spanier, 1961; Varian, 1974], i.e., every agent believes her piece is weakly better than all other pieces. Remarkably, it has been shown in [Stromquist, 1980; Su, 1999]

contiguous piece, always exists. The contiguity property is particularly valuable in practical scenarios, especially when the resource has temporal or spatial structures.

The assumption that the cake can be divided arbitrarily is often too strong and unrealistic for many real-world applications. For instance, the use of a lecture room is typically allocated in discrete time slots, and land is commonly divided into distinct plots due to geographical concerns. These problems fall within the umbrella of the discrete cake-cutting problem [Heydrich and van Stee, 2015; Marenco and Tetzlaff, 2014; Suksompong, 2019], where m indivisible items are arranged on the vertices of a path and each item must be allocated in its entirety to a single agent. The discrete cakecutting problem is often considered together with connectivity constraints, which require that each agent receive a contiguous block of items along the path [Goldberg et al., 2020; H¨ohne and van Stee, 2021; Kawase et al., 2024].

The indivisibility of items introduces significant challenges, since envy-free allocations are not always possible. For example, if there is a single indivisible item to be allocated between two agents who both value it positively, the recipient will inevitably be envied by the other. To resolve the above impossibility, Bil`o et al. [2019; 2022] considered envy-free up to one item (EF1) divisions, first introduced by Budish [2011]. In an EF1 division, any agent's envy towards another can be eliminated by removing an item from the latter's allocation. While EF1 allocations are always guaranteed in the unconstrained setting of the allocations of indivisible items [Lipton et al., 2004], the problem becomes more complex in the discrete version of cake-cutting due to the connectivity constraint. In this paper, we denote a slightly more robust version of EF1 as EF1outer, which informally requires that envy can be eliminated by removing an item at the boundary. Bil`o et al. [2019; 2022] proved that an EF1outer division exists for at most four agents, leaving the general case unresolved for several years. Until 2023, Igarashi [2023] revised the rounding technique in [Bil`o et al., 2019; Bil`o et al., 2022] and affirmatively answered the question of the existence of EF1outer divisions for any number of agents.

However, the analogous problem of dividing chores remains unresolved. While the fair allocation of a discrete chore has been studied in the literature [Bouveret et al., 2019; H¨ohne and van Stee, 2021], the existence of EF1outer allocations in this context has not been established. This challenge arises from two key differences: first, the allocation of goods and chores is fundamentally distinct; second, the definitions of EF1outer for goods and chores differ. In particular, an EF1outer division of goods requires that an agent A does not envy agent B after removing a boundary item from B's bundle. In contrast, for chores, the requirement becomes that A

does not envy B after removing a boundary item from A's own bundle. This asymmetry in the definitions precludes straightforward reductions between the goods and chores settings, as noted in [Aziz, 2016]. In this work, we provide an affirmative answer to this question by presenting a constructive proof that guarantees the existence of a contiguous EF1outer division for chores.

1.1 Our Results and Contributions

Our main result is the existence of EF1outer divisions for the discrete chore division for an arbitrary number of agents with monotone disutility functions. The discrete version of the cake-cutting problem has been studied by Bil`o et al. [2022] and Igarashi [2023]. In particular, Igarashi [2023] provided a bright and powerful framework to achieve EF1outer for an arbitrary number of agents. However, the protocol for cakecutting does not directly work for the chores division problem. This is because the protocols for positive valuations are not usually applicable for negative valuations, and "in general there are no reductions from allocation of chores to goods or vice versa" [Aziz, 2016].

In the following, we present the high-level idea of the techniques used in the paper and also compare our techniques with those in [Bil`o et al., 2022; Igarashi, 2023]. We follow the general framework of Simmons-Su protocol [Su, 1999]. In particular, it encodes the possible divisions of a path by vertices of a triangulated (n-1)-simplex, where n is the number of agents. It then assigns ownership labels to the vertices of the triangulation, and each agent colors every vertex she owns with the index of her most preferred bundle in the division encoded by that vertex. By Sperner's lemma, there exists a fully colored elementary simplex, which corresponds to a sequence of similar divisions in which different agents prefer different bundles. By considering finer and finer triangulations, the protocol yields approximate solutions that converge to an envy-free cake-cutting division.

For the discrete version of cake cutting, Bil`o et al. [2022] observed that encoding only integral divisions can make the divisions corresponding to the vertices of an elementary simplex too far apart. They therefore considered a finer triangulation by allowing the knife to move in half-steps. Moreover, when coloring, agents' preferences over bundles are determined by virtual valuations, which do not necessarily coincide with their actual preferences. Using half-step triangulations and virtual valuations, Bil`o et al. [2022] proposed a rounding technique that works for at most four agents.

In follow-up work, Igarashi [2023] pointed out that virtual valuations in [Bil`o et al., 2022] treat left-most and rightmost items of a bundle symmetrically (left-right symmetry), which prevents their approach from extending to more than four agents. Instead, Igarashi [2023] introduced left-right asymmetric virtual valuations and a corresponding rounding technique, thereby extending the existence of EF1 divisions in discrete cake-cutting to an arbitrary number of agents.

In this paper, we follow the general framework in [Bil`o et al., 2022; Igarashi, 2023], but reconstruct key components with new structural insights. At a high level, the inherent differences between goods and chores, together with the asymmetric definitions of EF1outer in the two settings, prevent the rounding algorithm of Igarashi [2023] from working for chores. The detailed differences between our rounding and the existing ones arise from the different definitions of the virtual functions, which act as agents' preferences when coloring. In particular, the virtual functions in [Bil`o et al., 2022; Igarashi, 2023] rely only on the information between two knife positions. This limited information is unlikely to suffice for producing an EF1outer division for chores, regardless of whether the virtual functions exhibit left-right asymmetry. Instead, we propose new virtual functions that depend not only on the information of the bundle between the knives but also on the item immediately outside to the left of the bundle. We explain this difference in detail after the definition of our virtual functions in Section 3.

Under the framework of Simmons-Su protocol, the procedure of rounding the fully colored elementary simple is not independent of the coloring functions, which is also the case in [Bil`o et al., 2022; Igarashi, 2023]. Since we employ different virtual functions, the detailed procedures for rounding the fully colored elementary simple into an EF1outer division inevitably differ from those in [Bil`o et al., 2022; Igarashi, 2023]. In a nutshell, while we follow the general idea of the framework in [Bil`o et al., 2022; Igarashi, 2023], we rebuild the virtual functions and the rounding, which are essential for establishing the existence of EF1outerwhen dividing a discrete chore among any number of agents with monotone disutility functions.

1.2 Other RelatedWork

The connected cake cutting problem has been extensively studied since the seminal work of Stromquist [1980], who first proved the existence of a connected EF division. Su [1999] simplified Stromquist's proof via Sperner's lemma, and this technique is now widely used in fair division. Aumann et al. [2013] studied the problem of computing connected divisions that maximize social welfare. Bei et al. [2012] investigated the problem of maximizing social welfare among all proportional connected divisions. Aumann and Dombb [2015] quantified the efficiency loss under fairness constraints in connected cake cutting. For the case of a divisible chore, Robertson and Webb [1998] gave the first envy-free protocol for three agents. Peterson and Su extended this protocol to four agents in [Peterson and Su, 2002], and an arbitrary number of agents in [Peterson and Su, 2009]. Dehghani et al. [2018] gave the first discrete and bounded envyfree protocol for chore division among any number of agents. Heydrich and van Stee [2015] studied the trade-off between fairness and efficiency.

The connectivity constraint has also been explored in the discrete version of the cake-cutting problem. Marenco and Tetzlaff [2014] proved the existence of envy-free connected divisions when each item is valued positively by at most one agent. Subsequent research has shown the existence of relaxed notions of envy-freeness in cases where items may be valued positively by any number of agents [Barrera et al., 2017; Suksompong, 2019]. The computational complexity of determining the existence of a fair connected allocation has been studied, for goods in [Goldberg et al., 2020; Kawase et al., 2024] and for chores in [Bouveret et al., 2019].

The trade-off between fairness and efficiency has been studied in [Caragiannis et al., 2012; H¨ohne and van Stee, 2021; Suksompong, 2019; Sun and Li, 2025], considering various definitions of fairness and efficiency.

2 Preliminaries

For any positive integer k, let [k] := {1, . . . , k}. There is a set V of m indivisible chores v1, . . . , vm placed on the vertices of a path, which are to be allocated to n agents. The chores are named from left to right, with chore vj placed at position j. Throughout the paper, we use vj both as the identifier of the chore and as its position j on the path, so that vj can also be compared with real numbers.

A subset X ⊆ V is called connected if it induces a connected subgraph. Let C(V ) denote the set of all connected subsets of V . We consider the empty set and any singleton set as connected. Agents are required to receive connected subsets or bundles. Moreover, each agent i ∈ [n] is associated with a cost or disutility function ui : C(V ) → R≥0. Each ui is monotone, that is, for any connected subset S ⊆ T ⊆ V , ui(S) ≤ ui(T). For ease of representation, we write ui(v) for ui({v}).

A division is a partition P = (P1, . . . , Pn) of the path into n connected bundles, such that for any i, j ∈ [n], Pi ∩Pj = ∅ and ⋃t∈[n] Pt = V . Given partition P, the subset Pi is the i-th piece from the left.

The division P is envy-free if there exists a permutation π : [n] → [n] such that for any i, j ∈ [n], ui(Pπ(i)) ≤ ui(Pπ(j)) holds. As we have discussed, envy-free divisions are not guaranteed to exist for indivisible items. Thus, we shift our attention to the relaxation, namely envy-free up to one item (EF1). In an EF1 chores division, the envy can be eliminated by removing a chore from the bundle of the envious agent. In the original definition of EF1, there is no connectivity requirement on the resulting bundle after removing an item. Motivated by the fact that agents prefer connected subsets over disconnected ones, we instead consider a stronger version, namely envy-free up to an outer item (EF1outer), which requires that the resulting bundle after removing an item should be connected. The notion of EF1outer has been studied in the context of the discrete version of cake-cutting [Bil`o et al., 2022; Igarashi, 2023]. Below, we present the formal definition of EF1outer in the discrete chore division problem.

Definition 1 (EF1outer). For the problem of discrete chore division, a division P = (P1, . . . , Pn) is EF1outer if there exists a permutation π : [n] → [n] such that for any i, j ∈ [n], either (1) ui(Pπ(i)) ≤ ui(Pπ(j)), or (2) ∃v ∈ Pπ(i) such that Pπ(i) \ {v} is connected and ui(Pπ(i) \ {v}) ≤ ui(Pπ(j)).

2.1 Sperner's Lemma and Simmons-Su Protocols

We provide a brief overview of Sperner's Lemma and Simmons-Su protocols. Let us begin with combinatorial topology. A (n - 1)-simplex is the convex hull of n affinely independent points in space Rm with m ≥ n - 1. Let conv(x1, . . . , xn) denote the convex hull of the x1, . . . , xn. For (n - 1)-simplex S = conv(x1, . . . , xn), x1, . . . , xn are referred to as the main vertices of S. Given a subset J ⊆ {x1, . . . , xn} with |J| = k + 1, the k-simplex spanned by J is said to be a k-face of S, denoted as FJ. A facet of simplex S is the face spanned by the n - 1 of the n main vertices of S.

A triangulation T of an (n - 1)-simplex S is a collection of smaller simplices S1, . . . , St, satisfying that ⋃j∈[t] Sj = S and for any i, j ∈ [t], simplices Si and Sj either intersect at a shared face or do not intersect at all. The smaller simplices S1, . . . , St are the elementary simplices of T .

Fix simplex S and its triangulation T. Let V (T) denote the set of vertices of T . In other words, V (T) is the union of the vertices of all the elementary simplices in T. A coloring function is a mapping λ : V (T) → 2[n] that assigns a set of numbers, also referred to as colors, to each vertex of T. A coloring function λ is called Sperner coloring if the main vertices of S are assigned different colors, and moreover, any other vertex in the interior of some k-face must be assigned one of the labels of the main vertices that span that face. An elementary simplex S∗ = conv(x∗1 , . . . , x∗n ) is called fully colored under coloring function λ if each of its vertices is assigned a distinct color by λ, i.e., there exists a permutation π : [n] → [n] such that λ(x∗i ) = π(i) for all i ∈ [n].

Theorem 2 (Sperner's lemma). For an (n-1)-simplex S and its triangulation T , if V (T) is colored by a Sperner coloring function λ, then there must exist an odd number of fully colored elementary (n-1)-simplices. In particular, there exists at least one.

We next briefly introduce the Simmons-Su protocols with an example of three agents. Consider dividing a cake [0, 1] of total size 1 using 2 knives among Alice, Betty, and Charlie. Let x1 and x2 be respectively the positions of the first and the second knives. Then 0 ≤ x1 ≤ x2 ≤ 1, and (x1, x2) ranges over a 2-simplex S (a triangle). Then triangulate S with a triangulation T and assign "ownership" to each vertex so that the vertices of every elementary simplex in T have three distinct labels, as shown in Figure 1a. Each vertex x = (x1, x2) corresponds to a division of the cake, with xi being the position of the i-th knife. For example, the upper-left vertex marked in red in Figure 1b is (0, 1), and in the corresponding division, the first and third pieces are empty while the second piece is the entire cake. Visit each vertex of the triangulation and let the owner color the vertex with the indices of their most preferred pieces of the corresponding division. If each agent prefers any piece with mass over an empty piece, i.e., the agents are hungry, then the resulting color is Sperner's color. By Sperner's lemma, there exists a fully colored elementary simplex S∗ , which corresponds to three similar divisions (one for each vertex of S∗ ) in which different agents choose different pieces of cake. By repeating this procedure on a sequence of finer and finer triangulations, we obtain approximate solutions that converge to an envy-free connected division.

3 The Existence of EF1outer Divisions

In this section, we present the main result of this work: for the discrete version of chore division problem, EF1outer divisions always exist for an arbitrary number of agents with monotone disutility functions.

The discrete version of cake-cutting has been studied by Bil`o et al. [2022] and Igarashi [2023]. They followed the Simmons-Su protocol and rounded a fully colored elementary simplex. They observed that if the encoded divisions at the vertices are restricted to integral cuts (i.e., the knife always moves in full steps), then the divisions corresponding to the vertices of an elementary simplex are too far apart. Thus, they considered a finer triangulation that allows the knives to move in half-steps. In particular, they considered the simplex

and Kuhn's triangulation Thalf of Sm, with the vertex set V (Thalf ) defined as:

The Kuhn's triangulation has the property that for each elementary simplex S = conv(x1, . . . , xn), there exists a permutation ϕ : [n] → [n] such that

where ek denotes the k-th standard unit vector (i.e., k-th coordinate is 1 and all others are 0). This property ensures that the vertices of each elementary simplex can be ordered such that each subsequent vertex is generated by adding 12 along a unique coordinate axis, with each axis being selected exactly once over the sequence. For the purposes of this work, we focus on Sm and Kuhn's triangulation.

For a vertex x = (x1 , . . . , xn-1 ) ∈ V (Thalf ), each coordinate xi functions as a partitioning threshold. This vertex x then induces a (partial) division P(x) = (P1(x), . . . , Pn(x)) of m chores v1, . . . , vm, where the subsets are defined as:

• P1(x) = {vk | vk < x1 },
• for j = 2, . . . , n-1: Pj(x) = {vk | xj-1 < vk < xj },

The P(x) can be a partial division, as not all of v1, . . . , vm are necessarily included in some Pj(x). In particular, if xj = vk for some j and k, then chore vk /∈ Pℓ(x) for all ℓ. In this case, we say item vk is hidden by knife xj .

For a vertex x ∈ V (Thalf ) and a bundle Pj (x), chore vk is the left-boundary item of Pj(x) if vk = ⌈xj-1 ⌉. We also use ℓj(x) to denote the left-boundary item of Pj(x). Note that P1(x) does not have a left-boundary item, as there is no x0 . Chore vk is the right-boundary item of Pj(x) if vk = ⌊xj ⌋, and, in this case, we use rj(x) to denote chore vk. The Pn(x) does not have the right-boundary item, as there is no xn . We remark that if ℓj(x) is hidden by the (j - 1)-th knife, then it is the right-boundary item of Pj-1(x) and the left-boundary item of Pj(x). We say that item vk ∈ V fully appears in Pj(x) if vk ∈ Pj(x).

Recall that for every elementary simplex S = conv(x1, . . . , xn) of Thalf , there exists a permutation ϕ : [n] → [n] that satisfies Equation (1). Then S induces an ordered sequence of partial divisions P(xϕ(1)),P(xϕ(2)), . . ., P(xϕ(n)). In this sequence, for t ≥ 2, each P(xϕ(t)) is obtained from P(xϕ(t-1)) by moving one of the knives in half-step, and the movement of each knife occurs exactly once across n partial divisions. Given elementary simplex S = conv(x1, . . . , xn), the path can be decomposed into (B1, v1 ,B2, . . . , vn-1 ,Bn), where each Bj is the set of items that fully appear in every Pj(xt), and each vj is the boundary item that appears either j-th bundle or (j + 1)-th bundle in the sequence of the partial division. It is crucial to note that as each knife only moves once in a half-step, it never happens that vj fully appears in the j-th bundle of one partial division and fully appears in the (j + 1)-th bundle of another partial division. Figure 2 illustrates the boundary items, path decomposition, and the property of Kuhn's triangulation.

With these preliminary definitions established, we are now prepared to show the existence of EF1outer connected division for an arbitrary number of agents with monotone disutility functions.

The first step involves assigning ownership labels to the vertices of V (Thalf ). This assignment must ensure that the n vertices within any elementary simplex bear n distinct labels. The existence of such an assignment is guaranteed because Thalf is Kuhn's triangulation [Deng et al., 2012].

Coloring. The second step involves agents coloring the vertices they own. In Bil`o et al. [2022] and Igarashi [2023], the coloring is based on virtual valuations, which are not necessarily identical to agents' valuations. In this work, we adopt their approach by having agents color vertices based on preferences that differ from their actual disutility functions ui's. However, the virtual valuations in [Bil`o et al., 2022; Igarashi, 2023] are designed for cake-cutting and are not applicable to the chore division problem. Thus, we must define new virtual functions to establish the existence of EF1outer for chores.

In this work, we define the virtual disutility functions {ˆui}i, based on which agents color their vertices. For each agent i ∈ [n], her virtual function ˆui(x, j) takes as input x ∈ V (Thalf ) and an index j ∈ [n], returning a non-negative real number. Informally, ˆui(x, j) represents agent i's virtual disutility for Pj(x), and depends on not only the elements in Pj(x) but also the boundary items and positions of the (j - 1)-th and j-th knives.

Before formally defining ˆui(x, j), we first introduce the up-to-one disutility function u-i : C(V ) → R≥0. For any S ∈ C(V ), it is defined as

In particular, when S is the empty set, u-i (S) = 0.

We now fix agent i and a vertex x, and formally define virtual functions. For j = 1 and j = n, ˆui(x, j) = ui(Pj(x)). An agent receiving an exterior subset (leftmost or rightmost) does not consider any chore hidden by some knife.

For j = 2, . . . , n - 1, the virtual function ˆui(x, j) is defined as:

where vL /∈ Pj(x) is the chore to the left of Pj(x) such that {vL}∪Pj(x) is connected. One can introduce a dummy chore v0 immediately to the left of v1, with disutility 0 for every agent, so that vL always exists. Moreover, due to Kuhn's triangulation, xj-1 < ℓj(x) implies xj-1 = ℓj(x) - 1 2 and xj > rj(x) implies xj = rj(x) + 12 .

Compared our virtual functions with those in [Igarashi, 2023], although our ˆui(x, j) handles similar cases, its definitions differ from theirs in each of the four cases. Moreover, the virtual functions in [Igarashi, 2023] use only information about Pj(x) and its boundary items, while our ˆui(x, j) requires the agent to take vL, an item that is outside Pj(x) and not one of its boundary items

The coloring function of agent i is λi : V (Thalf) → 2[n] , defined as:

For any x, there always exists some j achieving the minimum value of ˆui(x, j), so each agent can identify her most preferred bundle. This satisfies the "Good House" condition in Su [1999]. We then verify "Miserly Tenants" condition in Su [1999], which requires that no agent strictly prefers a piece of positive length to a piece of zero length. If an agent receives the left or right exterior bundle of zero length, then the corresponding P1(x) or Pn(x) is empty, and the virtual disutility is 0. Moreover, for any x and j = 2, . . . , n - 1 with xj-1 = xj , one can verify that ˆui(x, j) = 0. The coloring function {λi}i satisfies "Miserly Tenants" condition, and therefore forms a Sperner's coloring.

Rounding. We next introduce how to round an elementary simplex S = conv(x1, . . . , xn) into a complete division P ∗ = (P ∗ 1 , . . . , P ∗ n ). Under the framework of Simmons-Su, the rounding procedure depends on the coloring functions, and thus, is not independent of the virtual functions. Since our virtual functions differ from those in [Bil`o et al., 2022; Igarashi, 2023], and due to the inherent differences between goods and chores, we must design a new rounding algorithm.

Recall that vertices x1, . . . , xn decompose the path as (B1, v1 , B2, . . . , vn-1 , Bn), where each Bj is the set of items that fully appear in Pj(xt) for all t, i.e., Bj = ⋂t∈[n] Pj(xt). The vj 's are items hidden by knives.

Our rounding algorithm is described as follows. For each j ∈ [n], first initialize P ∗ j as Bj. It then remains to allocate the hidden items v1 , . . . , vn-1 . Let us begin with the leftmost hidden item v1 . If v1 fully appears in the first bundle of some xt, i.e., v1 ∈ P1(xt) for some xt, then allocate v1 to P ∗ 1 . Next, we allocate vj with j = 2, . . . , n - 1 one by one. Suppose that we are at the round of allocating vj . When vj-1 ̸= vj , if vj-1 has not allocated yet, then assign it to P ∗ j (Line 8). For item vj , assign it to P ∗ j if (1) vj fully appears in the j-th bundle of some xt and vj-1 /∈ P ∗ j , or (2) vj fully appears in the j-th bundle of some xt, vj-1 ∈ P ∗ j , and there is no xℓ satisfying xj-1 ℓ = vj-1 and xjℓ = vj (Line 9). When vj-1 = vj , it trivially holds that Bj = ∅. Assign vj to P ∗ j if vj (equivalently vj-1 ) is unallocated and vj fully appears in the j-th bundle of some xt (Line 12). The rounding is formally presented in Algorithm 1.

Algorithm 1 Rounding an elementary simplex

Input: An elementary simplex S = conv(x1, . . . , xn). Output: A complete division P ∗ = (P ∗ 1 , . . . , P ∗ n ) of the

path. 1: For each j ∈ [n], let Bj = Pj(x1) ∩ Pj(x2) ∩ · · · ∩ Pj(xn) and let vj be the item such that vj = xjt for some t ∈ [n]. 2: For each j ∈ [n], initialize P ∗ j ←Bj. 3: if item v1 ∈ P1(xt) for some xt then 4: P ∗ 1 ←P ∗ 1 ∪ {v1 }. 5: end if 6: for j = 2, . . . , n-1 do 7: if vj-1 ̸= vj then 8: If vj-1 is unallocated, i.e., vj-1 /∈ ⋃i∈[n] P ∗ i , then P ∗ j ←P ∗ j ∪ {vj-1 }. 9: Allocate vj to P ∗ j if one of the following two conditions is satisfied: (1) vj ∈ Pj(xt) for some xt and vj-1 /∈ P ∗ j , or (2) vj ∈ Pj(xt) for some xt, vj-1 ∈ P ∗ j , and there is no xℓ such that xj-1 ℓ = vj-1 and xjℓ = vj . 10: end if 11: if vj-1 = vj and vj-1 is unallocated then 12: Allocate vj to P ∗ j if vj ∈ Pj(xt) for some xt. 13: end if 14: end for 15: if vn-1 is unallocated then 16: P ∗ n ←P ∗ n ∪ {vn-1 }. 17: end if

We next present a crucial lemma for establishing the main result. Due to the page limit, we include only part of the proofs in the main body and defer the remaining proofs to the full version.

Lemma 3. Let S = conv(x1, . . . , xn) be an elementary simplex of Thalf and let P ∗ = (P ∗ 1 , . . . , P ∗ n ) be the division returned by Algorithm 1 with input S. For any agent i, any bundle P ∗ j , and any xk, it holds that

Partial proof. We first claim that for each j ∈ [n-1], vj-1 ≤ vj . Assume for the contradiction that vj ′-1 > vj ′ for some j ′ ∈ [n - 1]. Then there exists k′ , k′′ such that xj ′-1 k′ = vj ′-1 > vj ′ = xj ′ k′′ . Since vj ′-1 and vj ′ are integers, we have xj ′-1 k′ ≥ xj ′ k′′ +1 > xj ′ k′ , where the last inequality transition is due to the property of the Thalf . This yields a contradiction. Below, we split the proof based on the value of j and the possible cases of P ∗ j .

For j = 1. By Algorithm 1, bundle P ∗ 1 can possibly be B1 or B1 ∪ {v1 }. The arguments below also hold when B1 = ∅.

Case 1: P ∗ 1 = B1. By Algorithm 1, chore v1 does not fully appear in any P1(xt), and hence, x1t ∈ {v1 - 12 , v1 } for all t. By the definition of ˆui, for both cases of x1k = v1 - 1 2 and x1k = v1 , we have ˆui(xk, 1) = ui(B1). Therefore, u-i (P ∗ 1 ) ≤ ˆui(xk, 1) = ui(P ∗ 1 ) holds.

Case 2: P ∗ 1 = B1 ∪ {v1 }. By Algorithm 1, chore v1 fully appears in some P1(xt), and hence, x1t ∈ {v1 , v1 + 12 } for all t. Next, we compute possible values of ˆui(xk, 1) and prove that the desired inequalities hold for every possible value.

We illustrate the two subcases in Figure 3. As v1 is the right-most chore of P ∗ 1 , we have u-i (P ∗ 1 ) ≤ ui(B1). Therefore, it always holds that u-i (P ∗ 1 ) ≤ ˆui(xk, 1) = ui(P ∗ 1 ).

For j = n. By Algorithm 1, bundle P ∗ n can possibly be Bn or {vn-1 } ∪ Bn. The arguments below also hold when Bn = ∅.

Case 1: P ∗ n = Bn. By Algorithm 1, chore vn-1 fully appears in some Pn-1(xt), and hence, xn-1 t ∈ {vn-1 , vn-1 + 1 2 } for all t. By the definition of ˆui, for both cases of xn-1 k = vn-1 and xn-1 k = vn-1 + 1 2 , we have ˆui(xk, 1) = ui(Bn). Therefore, u-i (P ∗ n ) ≤ ˆui(xk, n) = ui(P ∗ n ) always holds.

Case 2: P ∗ n = {vn-1 } ∪ Bn. As vn-1 is hidden by some xn-1 t′ , it holds that xn-1 t ∈ {vn-1 - 1 2 , vn-1 , vn-1 + 12 } for all t due to the property of Kuhn's triangulation. Below, we compute possible values of ˆui(xk, 1) and prove that the desired inequalities hold for all possible values of ˆui(xk, 1).

We illustrate the three subcases in Figure 4. As vn-1 is the left-most item of P ∗ n , it holds that u-i (P ∗ n ) ≤ ui(Bn). Since ˆui(xk, n) is either ui({vn-1 }∪Bn) or ui(Bn), the inequality u-i (P ∗ n ) ≤ ˆui(xk, 1) = ui(P ∗ n ) always holds.

For j = 2, . . . , n- 1 and vj-1 < vj . By Algorithm 1, P ∗ j can possibly be Bj , Bj ∪ {vj }, {vj-1 } ∪ Bj , and {vj-1 } ∪ Bj ∪ {vj }.

Case 1: P ∗ j = Bj. By Algorithm 1, chore vj-1 fully appears in some Pj-1(xt′) and vj does not fully appear in any Pj(xt). Thus, xj-1 t ∈ {vj-1 , vj-1 + 12 } and xjt ∈ {vj - 12 , vj } for all t. We compute possible values of ˆui(xk, j) and prove that the desired inequalities always hold.

(1d): xj-1 k = vj-1 + 12 and xjk = vj . We have ˆui(xk, j) = ui(Bj ).

Figure 5: Illustration of possible cases for j = 2, . . . , n - 1 and Case 1.

We illustrate the four subcases in Figure 5. Since ˆui(xk, j) is either u-i ({vj-1 } ∪ Bj) or ui(Bj), we have u-i (Bj) ≤ ˆui(xk, j). Moreover, as vj-1 is the left-most item of {vj-1 } ∪Bj, we have u-i ({vj-1 } ∪Bj) ≤ ui(Bj). Therefore, u-i (P ∗ j ) ≤ ˆui(xk, j) ≤ ui(P ∗ j ) always holds.

Case 2: P ∗ j = Bj ∪ {vj }. By Algorithm 1, chore vj-1 fully appears in some Pj-1(xt) and vj fully appears in some Pj(xt′). Thus, xj-1 t ∈ {vj-1 , vj-1 + 12 } and xjt ∈ {vj , vj + 12 } for all t. We compute possible values of ˆui(xk, j) and then prove the desired inequalities.

(2a): xj-1 k = vj-1 and xjk = vj . We have ˆui(xk, j) = ui(Bj ).

(2d): xj-1 k = vj-1 + 12 and xjk = vj + 12 . We have ˆui(xk, j) = u-i ({vj-1 } ∪Bj ∪ {vj }).

We illustrate the four subcases in Figure 6. Note that ˆui(xk, j) is either u-i ({vj-1 }∪Bj ∪{vj }) or ui(Bj). Since vj is the right-most item of P ∗ j , it holds that u-i (P ∗ j ) ≤ ui(Bj). Moreover, as u-i ({vj-1 } ∪Bj ∪ {vj }) ≥ u-i (Bj ∪

{vj }), it always holds that ˆui(xk, j) ≥ u-i (P ∗ j ). Furthermore, since vj-1 is the left-most item of {vj-1 }∪Bj ∪{vj }, we have u-i ({vj-1 } ∪ Bj ∪ {vj }) ≤ ui(Bj ∪ {vj }). Therefore, u-i (P ∗ j ) ≤ ˆui(xk, j) ≤ ui(P ∗ j ) always holds.

Theorem 4. For an arbitrary number of agents with monotone valuations, there always exists an EF1outer connected division.

Proof. First, assign ownership labels to vertices of Thalf , ensuring that n vertices of any elementary simplex have n distinct labels. Then let owners color their vertices based on the {λi}i. By Sperner's lemma (Theorem 2), there exists a fully colored elementary simplex S∗ = conv(x∗1 , . . . , x∗n ). Without loss of generality, assume that for each i ∈ [n], vertex x∗i is owned by agent i. Since S∗ = conv(x∗1 , . . . , x∗n ) is fully colored, then there exists a permutation π : [n] → [n] such that for each i ∈ [n], the π(i)-th bundle in the P(x∗i ) is the bundle most preferred (based on the virtual function) by agent i. Formally, for any i, j ∈ [n], it holds that

Then apply Algorithm 1 and round S∗ = conv(x∗1 , . . . , x∗n ) to the complete division P ∗ = (P ∗ 1 , . . . , P ∗ n ). For an agent i ∈ [n], bundle P ∗ π(i) , vertex x∗i , and j ∈ [n], we have

where (a) and (c) follow from Lemma 3 and (b) is because agent i color her vertex x∗i as π(i). Therefore, assigning each i bundle P ∗ π(i) yields an EF1outer connected division.

4 Conclusion

In this work, we prove the existence of a connected EF1 division of indivisible chores for an arbitrary number of agents with monotone disutility functions. On top of Simmons-Su's framework, we introduce a rounding approach which relies on virtual disutility functions that utilize not only the information of the bundle between the boundaries but also the information outside.

Our results raise many interesting questions for future research. First, we have proven the existence of EF1outer division when all items are chores, while Igarashi [2023] established the existence when all items are goods. It would be worthwhile to explore settings where an item can be a good for one agent but a chore for another. Second, we focus on fairness in this work, while exploring the compatibility of fairness and Pareto optimality (PO) is also an interesting direction. In particular, Mahara [2026] recently demonstrated that EF1 and PO are compatible when all items are chores (without connectivity constraints) and agents have additive disutility functions; that is, the disutility of a subset equals the sum of the disutilities of all chores within it. It is worthwhile to investigate whether EF1 and PO are also compatible in the discrete chores division setting. Finally, our work provides only a constructive proof, and the computational complexity of finding an EF1outer chores division remains unknown.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. Bo Li is supported in part by the Hong Kong SAR Research Grants Council (Grant No. PolyU 15224823) and Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515011524).