Almost Envy-Free Allocations with Connected Bundles

Introduction

A famous literature considers the problem of cake-cutting (Brams and Taylor, 1996; Robertson and Webb, 1998; Procaccia, 2016). There, a divisible heterogeneous resource (a cake, usually formalized as the interval $$) needs to be divided among$n$agents. Each agent has a valuation function over subsets of the cake, usually formalized as an atomless measure over$$. The aim is to partition the cake into$n$ pieces, and allocate each piece to one agent, in a “fair” way. By fair, we will mean that the allocation is envy-free: no agent thinks that another agent’s piece is more valuable than her own.

When there are two agents, the classic procedure of cut-and-choose can produce an envy-free division: a knife is moved from left to right, until an agent shouts to indicate that she thinks the pieces to either side are equally valuable. The other agent then picks one of the pieces, leaving the remainder for the shouter. As is easy to see, the result is an envy-free allocation. For three or more agents, finding an envy-free division has turned out to be much trickier. An early result by Dubins and Spanier (1961) used Lyapunov’s Theorem and measure-theoretic techniques to show, non-constructively, that an envy-free allocation always exists. However, as Stromquist (1980) memorably writes, “their result depends on a liberal definition of a ‘piece’ of cake, in which the possible pieces form an entire $\sigma$-algebra of subsets. A player who only hopes for a modest interval of cake may be presented instead with a countable union of crumbs.” In many applications of resource allocation (such as land division, or the allocation of time slots), agents have little use for a severely disconnected piece of cake.

Stromquist (1980) himself offered a solution, and gave a new non-constructive argument (using topology) which proved that there always exists an envy-free division of the cake into intervals. Forest Simmons later observed that the proof could be simplified by using Sperner’s lemma, and this technique was subsequently presented in a paper by Su (1999). For the three-agent case, Stromquist (1980) also presented an appealing moving-knife procedure that more directly yields a connected envy-free allocation. For $n\geqslant 4$ agents, no explicit procedures are known to produce a connected envy-free allocation (i.e., an allocation where the cake is cut in exactly $n-1$ places). However, for $n=4$, several moving-knife procedures exist that only need a few cuts; for example, the Brams–Taylor–Zwicker (1997) procedure requires 11 cuts, and a protocol of Barbanel and Brams (2004) requires 5 cuts.

In many applications, the resources to be allocated are not infinitely divisible, and we face the problem of allocating indivisible goods. Most of the literature on indivisible goods has not assumed any kind of structure on the item space, in contrast to the rich structure of the interval $$ in cake-cutting. Thus, there has been little attention on minimizing the number of “cuts” required in an allocation. However, when the items have a spatial or temporal structure, this consideration is important.

In this paper, we study the allocation of items that are arranged on a path or other structure, and impose the requirement that only connected subsets of items may be allocated to the agents. Formally, we work in the model of Bouveret et al. (2017), who assume that the items form the vertex set of a graph $G$, and a bundle is connected if it induces a connected subgraph of $G$. For example, such connectivity requirements are encountered in allocation problems in which the items correspond to indivisible pieces of an underlying region of Euclidean space (such as plots of land), and each allocated bundle (i.e., a collection of pieces) must be a connected portion of the space. We are most interested in the case when $G$ is a path, on which connectivity requirements are natural when the items are time slots, for example. In practice, connectivity may not be a hard constraint, and agents may find bundles with few connected components acceptable, but we will not consider such relaxations.

In the work of Bouveret et al. (2017), it became apparent that techniques from cake-cutting can be usefully ported to achieve good connected allocations in the indivisible case. For example, moving-knife procedures that achieve proportionality in cake-cutting have analogues that produce allocations that satisfy the maximin share guarantee (Budish, 2011).Another paper by Suksompong (2019) works in the same model, and also found that procedures for proportionality and other concepts can be applied to the indivisible setting.

Do envy-free procedures for cake-cutting also translate to the indivisible case? Of course, in general, it is impossible to achieve envy-freeness with indivisibilities (consider two agents and a single desirable item), but we can look for approximations. A relaxation of envy-freeness that has been very influential recently is envy-freeness up to one good (EF1), introduced by Budish (2011). It requires that an agent’s envy towards another bundle vanishes if we remove some item from the envied bundle. In the setting without connectivity constraints and with additive valuations, the maximum Nash welfare solution satisfies EF1, as does a simple round-robin procedure (Caragiannis et al., 2019). The well-known envy-graph algorithm (Lipton et al., 2004) also guarantees EF1. However, none of these procedures respects connectivity constraints.

When items are arranged on a path, we prove that connected EF1 allocations exist when there are two, three, or four agents. As was necessary in cake-cutting, we use successively more complicated tools to establish these existence results. For two agents, there is a discrete analogue of cut-and-choose that satisfies EF1. In that procedure, a knife moves across the path, and an agent shouts when the knife reaches what we call a lumpy tie, that is when the bundles to either side of the knife have equal value up to one item. For three agents, we design an algorithm mirroring Stromquist’s moving-knife procedure which guarantees EF1. For four agents, we show that Sperner’s lemma can be used to prove that an EF1 allocation exists, via a technique inspired by the Simmons–Su approach, and an appropriately triangulated simplex of connected partitions of the path. For five or more agents, we were not able to establish the existence of EF1 allocations on a path, but we can show (again via Sperner’s lemma) that EF2 allocations exist, strengthening a prior result of Suksompong (2019). We also show that if all agents have the same valuation function over bundles, then an egalitarian-welfare-optimal allocation, after suitably reallocating some items, is EF1.

These existence results require only that agents’ valuations are monotonic (they need not be additive), and in addition, ensure that the constructed allocation satisfies the maximin share guarantee (see Appendix A.1). Moreover, the fairness guarantee of our algorithms is slightly stronger than the standard notion of EF1: in the returned allocations, envy can be avoided by removing just an outer item – one whose removal leaves the envied bundle connected. Computationally speaking, all our existence results are constructive in the weak sense that an EF1 allocation can be found by iterating through all $O(m^{n})$ connected allocation (this stands in contrast to cake-cutting where we cannot iterate through all possibilities). While we know of no faster algorithms to obtain an EF1 or EF2 allocation in the cases where we appeal to Sperner’s lemma, our other procedures (for two or three agents, or for identical valuations) can all be implemented efficiently to produce a fair allocation in polynomial time. We summarize our results concerning paths in Table 1.

In simultaneous and independent work, Oh et al. (2019) designed protocols to find EF1 allocations in the setting without connectivity constraints, aiming for low query complexity. They found that adapting cake-cutting protocols to the setting of indivisible items arranged on a path is an especially potent way to achieve low query complexity. This led them to also study a discrete version of the cut-and-choose protocol which achieves connected EF1 allocations for two agents, and they found an alternative proof that an EF1 allocation on a path always exists with identical valuations. They also present a discrete analogue of the Selfridge–Conway procedure which, for three agents with additive valuations, produces an allocation of a path into bundles that have a constant number of connected components. However, they do not study connected allocations on graphs that are not paths, and they do not consider the case of (non-identical) general valuations with more than two agents.

A recurring theme in our algorithms is the specific way that the moving knives from cake-cutting are rendered in the discrete setting. While one might expect knives to be placed over the edges of the path, and ‘move’ from edge to edge, we find that this movement is too ‘fast’ to ensure EF1 (see also footnote 5 regarding EF2). Instead, our knives alternate between hovering over edges and items. When a knife hovers over an item, we imagine the knife’s blade to be ‘thick’: the knife covers the item, and agents then pretend that the covered item does not exist. These intermediate steps are useful, since they can tell us that envy will vanish if we hide an item from a bundle.

What about graphs $G$ other than paths? Our existential results for paths immediately generalize to traceable graphs (those that contain a Hamiltonian path), since we can run the algorithms pretending that the graph only consists of the Hamiltonian path. For the two-agent case, we completely characterize the class of graphs that guarantee the existence of EF1 allocations: Our discrete cut-and-choose protocol can be shown to work on all graphs $G$ that admit a bipolar numbering, which exists if and only if the biconnected components (blocks) of $G$ can be arranged in a path. By constructing counterexamples, we prove that no graph failing this condition (for example, a star) guarantees EF1, even for identical, additive, binary valuations. For the case of three or more agents, it is a challenging open problem to characterize the class of graphs guaranteeing EF1 (or even to find an infinite class of non-traceable graphs that guarantees EF1).

Preliminaries

We say that the agents have identical valuations if, for all $i,j\in N$ and every bundle $I\in\mathcal{C}(V)$, we have $u_{i}(I)=u_{j}(I)$. A valuation function $u_{i}$ is additive if $u_{i}(I)=\sum_{v\in I}u_{i}(\{v\})$ for each bundle $I\in\mathcal{C}(V)$. Many examples in this paper will use identical additive valuations, and will take $G$ to be a path. In this case, we use a shorthand to specify these examples; the meaning of this notation should be clear. For example, we write “2–1–3–1” to denote an instance with four items $v_{1},v_{2},v_{3},v_{4}$ arranged on a path, and where $u_{i}(\{v_{1}\})=2$, …, $u_{i}(\{v_{4}\})=1$ for each $i$. For such an instance, an allocation will be written as a tuple, e.g., (2, 1–3–1) denoting an allocation allocating bundles $\{v_{1}\}$ and $\{v_{2},v_{3},v_{4}\}$, noting that with identical valuations it does not usually matter which agent receives which bundle.

An allocation $A$ is envy-free if $u_{i}(A(i))\geqslant u_{i}(A(j))$ for every pair $i,j\in N$ of agents, that is, if every agent thinks that their bundle is at least as good as any other bundle in the allocation. It is well-known that an envy-free allocation may not exist (consider two agents and one good). The main fairness notion that we study is a version of envy-freeness up to one good (EF1), a relaxation of envy-freeness introduced by Budish (2011), adapted to the model with connectivity constraints. This property states that an agent $i$ will not envy another agent $j$ after we remove some item from $j$’s bundle. Since we only allow connected bundles in our set-up, we may only remove an item from $A(j)$ if removal of this item leaves the bundle connected.

An allocation $A$ satisfies EF1 if, for any pair $i,j\in N$ of agents, either $A(j)=\emptyset$ or there is a good $v\in A(j)$ such that $A(j)\setminus\{v\}$ is connected and $u_{i}(A(i))\geqslant u_{i}(A(j)\setminus\{v\})$.

In the instance 2–1–3–1 for two agents, the allocation (2–1, 3–1) is EF1, since the left agent’s envy can be eliminated by removing the item of value 3 from the right-hand bundle. However, the allocation (2, 1–3–1) fails to be EF1 according to our definition, since eliminating either outer good of the right bundle does not prevent envy.This example shows that our definition is strictly stronger than the standard definition of EF1 without connectivity constraints. In the instance 2–1–3–1, considered without connectivity constraints, the allocation (2, 1–3–1) does satisfy EF1 since in the standard setting we are allowed to remove the middle item (with value 3) of the right bundle.

A graph $G$ guarantees EF1 for $n$ agents if, for all possible monotonic valuations for $n$ agents, there exists some connected allocation that is EF1. A graph $G$ guarantees EF1 for $n$ agents and a restricted class of valuations if, for all allowed valuations, a connected EF1 allocation exists.

Thus, an allocation $A$ satisfies EF1 if and only if $u_{i}(A(i))\geqslant u_{i}^{-}(A(j))$ for any pair $i,j\in N$ of agents.

As we show in the appendix in Example A.5, allocations satisfying a strengthened version of EF1 called envy-freeness up to the least good (EFX) (Caragiannis et al., 2019) may not exist on a path.

Given an ordered sequence of the vertices $P=(v_{1},v_{2},\ldots,v_{m})$, and $j,k\in[m]$ with $j\leqslant k$, we write $P(v_{j},v_{k})$ for the subsequence from $v_{j}$ to $v_{k}$, so $P(v_{j},v_{k})=(v_{j},v_{j+1},\ldots,v_{k-1},v_{k})$. With a little abuse of notation, we often identify a subsequence $P(v_{j},v_{k})$ with the bundle of the corresponding vertices. Let $L(v_{j})=P(v_{1},v_{j-1})$ be the subsequence of vertices strictly left of $v_{j}$ and $R(v_{j})=P(v_{j+1},v_{m})$ be the subsequence of vertices strictly right of $v_{j}$. When graph $G$ is a path, we always implicitly assume that its vertices $v_{1},v_{2},\ldots,v_{m}$ are numbered from left to right according to the order they appear along the path, so that the set of the edges of $G$ is $\{\{v_{j},v_{j+1}\}:1\leqslant j<m\}$. Each connected bundle in the path clearly corresponds to a subpath or subsequence of the vertices. A Hamiltonian path of a graph $G$ is a path that visits all the vertices of the graph exactly once. A graph is traceable if it contains a Hamiltonian path.

EF1 existence for two agents

In cake-cutting for two agents, the standard way of obtaining an envy-free allocation is the cut-and-choose protocol: Alice divides the cake into two equally-valued pieces, and Bob selects the piece he prefers; the other piece goes to Alice. The same strategy almost works in the indivisible case when items form a path; the problem is that Alice might not be able to divide the items into two exactly equal pieces. Instead, we ask Alice to divide the items into pieces that are equally valued “up to one good”. The formal version is as follows. For a sequence of vertices $P=(v_{1},v_{2},\ldots,v_{m})$ and an agent $i$, we say that $v_{j}$ is the lumpy tie over $P$ for agent $i$ if $j$ is the smallest index such that

For example, when $i$ has additive valuations 1–3–2–1–3–1, then the third item (of value 2) is the lumpy tie for $i$, since $1+3+2\geqslant 1+3+1$ and $2+1+3+1\geqslant 1+3$. The lumpy tie always exists: taking $j$ to be the smallest index such that $u_{i}(L(v_{j})\cup\{v_{j}\})\geqslant u_{i}(R(v_{j}))$ (which exists as the inequality holds for $j=m$ by monotonicity), the first part of (3.1) holds. If $j=1$, the second part of (3.1) is immediate by monotonicity. If $j>1$, then since $j$ is minimal, we have $u_{i}(L(v_{j}))=u_{i}(L(v_{j-1})\cup\{v_{j-1}\})<u_{i}(R(v_{j-1}))=u_{i}(R(v_{j})\cup\{v_{j}\})$ as required.

Using lumpy ties, our discrete version of the cut-and-choose protocol is specified as follows.

The discrete cut-and-choose protocol for $n=2$ agents on a sequence $P=(v_{1},v_{2},\ldots,v_{m})$ proceeds as follows:

Step 1. Alice selects her lumpy tie $v_{j}$ over $(v_{1},v_{2},\ldots,v_{m})$.

Step 2. Bob chooses a weakly preferred bundle among $L(v_{j})$ and $R(v_{j})$.

Step 3. Alice receives the bundle of all the remaining vertices, including $v_{j}$.

Intuitively, the protocol allows Alice to select an item $v_{j}$ that she will receive for sure, with the advice that the two pieces to either side of $v_{j}$ should have almost equal value to her. Then, Bob is allowed to choose which side of $v_{j}$ he wishes to receive. In our example with valuations 1–3–2–1–3–1, Alice selects the lumpy tie of value 2, then Bob chooses the bundle 1–3–1 to the right and receives it, and Alice receives the bundle 1–3–2. The result is EF1. This is true in general, and also if valuations are not identical.

When $G$ is a path and there are $n=2$ agents, the discrete cut-and-choose protocol yields an EF1 allocation.

Clearly, the protocol returns a connected allocation. The returned allocation satisfies EF1: Bob does not envy Alice up to item $v_{j}$, since Bob receives his preferred bundle among $L(v_{j})$ and $R(v_{j})$. Also, by (3.1), Alice does not envy Bob, since Alice either receives the bundle $L(v_{j})\cup\{v_{j}\}$ which she weakly prefers to Bob’s bundle $R(v_{j})$, or she receives the bundle $R(v_{j})\cup\{v_{j}\}$, which she weakly prefers to Bob’s bundle $L(v_{j})$. ∎

Proposition 3.2 implies that an EF1 allocation always exists on a path. Hence, an EF1 allocation exists for every traceable graph $G$: simply use the discrete cut-and-choose protocol on a Hamiltonian path of $G$. In fact, the discrete cut-and-choose protocol works on a broader class of graphs: We only need to require that the vertices of the graph can be numbered in a way that the allocation resulting from the discrete cut-and-choose protocol is guaranteed to be connected. Since the protocol always partitions the items into an initial and a terminal segment of the sequence, such a numbering needs to satisfy the following property.

A bipolar numbering of a graph $G$ is an ordering $(v_{1},v_{2},\dots,$ $v_{m})$ of its vertices such that for all $j\in[n]$, the sets $L(v_{j})\cup\{v_{j}\}$ and $R(v_{j})\cup\{v_{j}\}$ are connected in $G$.

In a slightly different context, bipolar numberings are known as $st$-numberings and turn out to be useful in algorithms for testing planarity and for graph drawing (Lempel et al., 1967; Even and Tarjan, 1976; Tarjan, 1986). The more common (equivalent) definition is phrased to say that a numbering is bipolar if, for every $j\in[n]$, the vertex $v_{j}$ has a neighbor that appears earlier in the sequence, and a neighbor that appears later in the sequence.

Clearly, every traceable graph has a bipolar numbering, since we can just use a Hamiltonian path. However, there are also non-traceable graphs that admit a bipolar numbering. Figure 1 shows some examples.

When there are $n=2$ agents, then the discrete cut-and-choose protocol run on a bipolar numbering of $G$ yields an EF1 allocation.

The discrete cut-and-choose protocol returns an allocation whose bundles are either initial or terminal segments of the ordered sequence $(v_{1},v_{2},\dots,v_{m})$. By definition of a bipolar numbering, such an allocation is connected, and it is EF1 by the same argument as in Proposition 3.2. ∎

It is clear that the discrete cut-and-choose protocol cannot be extended to graphs other than those admitting a bipolar numbering. However, it could be that a different protocol is able to produce EF1 allocations on other graphs. In the remainder of this section, we prove that this is not the case: for $n=2$ agents, a connected graph $G$ guarantees the existence of an EF1 allocation if and only if it admits a bipolar numbering. This completely characterizes the class of graphs that guarantee EF1 existence in the two-agent case.Note that no non-trivial disconnected graph guarantees EF1 for two agents: If $G$ is disconnected, take a connected component $C$ with at least two vertices. Let both agents have additive valuations that value each item in $C$ at 1, and value items outside of $C$ at 0. Then, in a connected allocation, all items in $C$ must go to a single agent, since the other agent needs to receive items from another connected component. This induces envy in the other agent that is not bounded by one good.

For a different number of agents, the class of graphs guaranteeing an EF1 allocation will be different. In particular, the star with three leaves does not guarantee an EF1 allocation for two agents (as it does not have a bipolar numbering, see below), but one can check that this star does guarantee an EF1 allocation for three or more agents (see Example A.6 in the appendix).

Based on a known characterization of graphs admitting a bipolar numbering, we characterize this class in terms of forbidden substructures. We then show that these forbidden structures are also forbidden for EF1: if a graph contains such a structure, we can exhibit an additive valuation profile for which no EF1 allocation exists.

As a simple example, consider the star with three leaves, which is the smallest connected graph that does not have a bipolar numbering.

Take two agents with identical additive valuations that value each item at 1. Any connected allocation must allocate three items to one agent, and a single item to the other agent. Then the latter agent envies the former agent, even up to one good. This star is an example of a forbidden substructure called a trident, which takes one of two forms, illustrated in Figure 2.

there is a vertex $s$ whose removal from $G$ leaves three or more connected components (a type I trident), or

there are subgraphs $C,P_{1},P_{2},P_{3}$ of $G$ such that (i) $P_{1},P_{2},P_{3}$ are vertex-disjoint, (ii) each $P_{i}$ contains at least two vertices, (iii) $C$ has exactly one contact vertex $s_{i}$ in common with $P_{i}$, $i=1,2,3$, and (iv) for $i=1,2,3$, removal of vertex $s_{i}$ from $G$ disconnects $P_{i}\setminus\{s_{i}\}$ from $C\setminus\{s_{i}\}$ (hence from the other two $P_{j}$) in $G$ (a type II trident).

We will prove that a graph $G$ fails to admit a bipolar numbering, and fails to guarantee EF1 for two agents, if and only if $G$ contains a trident. To reason about these structures, it is useful to consider the standard concept of the block decomposition of a graph (see, e.g., the textbook Bondy and Murty, 2008, Sec. 5.2).

A decomposition of a graph $G=(V,E)$ is a family $\{F_{1},F_{2},\ldots,F_{t}\}$ of edge-disjoint subgraphs of $G$ such that $\bigcup^{t}_{i=1}E(F_{i})=E$ where $E(F_{i})$ is the set of edges of $F_{i}$. A vertex is called a cut vertex of a graph $G$ if removing it increases the number of connected components of $G$. A graph $G$ is biconnected if $G$ is connected and does not have a cut vertex. A block of $G$ is a maximal biconnected subgraph of $G$.

Equivalently, a block of a graph $G$ can be defined as a maximal subgraph of $G$ where each pair of vertices lie on a common cycle (Bondy and Murty, 2008). Given a connected graph $G$, we define a bipartite graph $B(G)$ with bipartition $(\mathcal{B},S)$, where $\mathcal{B}$ is the set of blocks of $G$ and $S$ is the set of cut vertices of $G$; a block $B$ and a cut vertex $v$ are adjacent in $B(G)$ if and only if $B$ includes $v$. Since every cycle of a graph is included in some block, the graph $B(G)$ is a tree:

any two blocks of $G$ have at most one cut vertex in common;

the set of blocks forms a decomposition of $G$; and

Thus, for a connected graph $G$, we call $B(G)$ the block tree of $G$. It turns out that $G$ admits a bipolar numbering if and only if $B(G)$ is a path. For example, the graphs shown in Figure 1 all have their blocks arranged in a path (so that $B(G)$ is a path), as shown in Figure 3.

A graph $G$ admits a bipolar numbering if its block tree $B(G)$ is a path.

Lempel et al. (1967) show that $G$ admits a bipolar numbering if there are $s,t\in V$ such that adding an edge $\{s,t\}$ to $G$ makes it biconnected. If $B(G)$ is a path, let $B_{1}$ and $B_{2}$ be the leaf blocks at the ends of the path $B(G)$. Take any $s\in B_{1}$ and $t\in B_{2}$. If we add the edge $\{s,t\}$ to $G$, the graph becomes biconnected. Hence, $G$ admits a bipolar numbering. ∎

There is a linear-time algorithm based on depth-first search to construct a bipolar numbering for any biconnected graph (Even and Tarjan, 1976; Tarjan, 1986), and one can also calculate the block tree $B(G)$ of a given graph in linear time (Hopcroft and Tarjan, 1973). Thus, in linear time, we can compute a bipolar numbering of a graph or report that none exists. Clearly, given a bipolar numbering, the discrete cut-and-choose protocol can also be run in linear time.

Next, we show that if $B(G)$ is not a path, then $G$ cannot guarantee EF1. The proof constructs explicit counter-examples, which have a very simple structure. We say that additive valuations $u_{i}$ are binary if $u_{i}(\{v\})\in\{0,1\}$ for every $v\in V$.

If the block tree $B(G)$ of $G$ is not a path, then $G$ contains a trident.

If $G$ contains a trident, then there exist identical, additive, binary valuations over $G$ for two agents such that no connected allocation is EF1.

If $B(G)$ is not a path, then it contains a vertex with at least three neighbors, and thus either

there is a cut vertex $s$ adjacent to three blocks $B_{1}$, $B_{2}$, and $B_{3}$; or

there is a block $B$ adjacent to three different cut vertices $s_{1}$, $s_{2}$, and $s_{3}$.

Note that in both cases, all blocks contain at least two vertices each, as maximality guarantees that a block in a connected graph $G$ never consists of a single vertex, unless $G$ itself has only one vertex. Thus, in case (a), $G$ contains a type I trident. In case (b), the cut vertices $s_{1}$, $s_{2}$, and $s_{3}$ serve as the contact vertices in the earlier definition of type II tridents and are adjacent to blocks that serve as the subgraphs $P_{1}$, $P_{2}$, and $P_{3}$. This proves the first part.

To prove the second part, we construct identical additive valuations that do not admit an EF1 allocation. If $G$ contains a type I trident, let $s$ be the corresponding cut vertex, and choose vertices $v_{1},v_{2},v_{3}$ from each of three different connected components that remain after $s$ is deleted from $G$. The two agents have utility $1$ for each of $s$, $v_{1}$, $v_{2}$, and $v_{3}$, and for the remaining vertices. Now take any connected allocation $(I_{1},I_{2})$. One of the bundles, say $I_{1}$, includes the cut vertex $s$. Then $I_{2}$ can contain at most one of the vertices $v_{1}$, $v_{2}$, $v_{3}$, since $I_{2}$ is connected and does not contain $s$ yet any path between distinct $v_{i}$ and $v_{j}$ goes through $s$. Hence $u_{i}(I_{2})\leqslant 1$. Now, the bundle $I_{1}$ contains $s$ and at least two of $v_{1}$, $v_{2}$, $v_{3}$, so $u_{i}(I_{1})\geqslant 3$. Thus, the allocation is not EF1.

Suppose $G$ contains a type II trident consisting of subgraphs $C,P_{1},P_{2},P_{3}$ with contact vertices $s_{1},s_{2},s_{3}$. Then for $i=1,2,3$ choose a vertex $v_{i}\neq s_{i}$ from $P_{i}$. The two agents have utility $1$ for each of $s_{1}$, $s_{2}$, $s_{3}$, $v_{1}$, $v_{2}$, and $v_{3}$, and for the remaining vertices. Now take any connected allocation $(I_{1},I_{2})$. One of the bundles, say $I_{1}$, contains at least two contact vertices $s_{i}$ and the other contains at most one contact vertex $s_{i}$. Say that $s_{1},s_{2}\in I_{1}$. Now, $G\setminus\{s_{1},s_{2}\}$ has at least three connected components, and since $I_{2}$ is connected, it must be contained in one of these components. But each component contains at most two vertices with utility 1, so $u_{i}(I_{2})\leqslant 2$. Since there are six vertices with utility 1 in total, $u_{i}(I_{1})\geqslant 4$. Thus, the allocation is not EF1. ∎

Combining these results, we obtain the promised characterization.

The following conditions are equivalent for every connected graph $G$:

$G$ guarantees EF1 for two agents with identical, additive, binary valuations.

The implication $(1)\Rightarrow(2)$ follows from Proposition 3.4 which shows that the discrete cut-and-choose protocol yields a connected EF1 allocation when run on a bipolar numbering. The implication $(2)\Rightarrow(3)$ is immediate. The implications $(3)\Rightarrow(4)$ and $(4)\Rightarrow(5)$ follow from Lemma 3.9 which proves the contrapositives. Finally, $(5)\Rightarrow(1)$ follows from Lemma 3.8. ∎

The equivalence $(2)\Leftrightarrow(3)$ is noteworthy and perhaps surprising: It is often easier to guarantee fairness when agents’ valuations are identical, yet in terms of the graphs that guarantee EF1 for two agents, there is no difference between identical and non-identical valuations. Intriguingly, even for more than two agents, we do not know of a graph which guarantees EF1 for identical valuations, but fails it for non-identical valuations.

EF1 existence for three agents: A moving-knife protocol

We will now consider the case of three agents. Stromquist (1980) designed a protocol that results in an envy-free contiguous allocation of a divisible cake. We now give a brief outline of the protocol, illustrated by Figure 4.

A referee holds a sword over the cake. Each of the three agents holds their own knife over the portion of the cake to the right of the sword, positioning it so that this portion is divided into two pieces they judge to have the same value. Now, initially, the sword is at the left end of the cake. It starts moving at a constant speed from left to right, while the agents continuously move their knives to keep dividing the right-hand portion into equally-valued pieces. At some point (when the leftmost piece becomes valuable enough), one of the agents shouts “cut”, and the cake will be cut twice: once by the sword, and once by the middle one of the three knives. Agents shout “cut” as soon as the left piece is a highest-valued piece among the three. The agent who shouts receives the left piece. The remaining agents each receive a piece containing their knife. The resulting allocation is envy-free, since the agent receiving the left piece prefers it to the other pieces, and the other agents who are not shouting receive at least half the value of the part of the cake to the right of the sword.

Let $G$ be a path, $P=(v_{1},v_{2},\ldots,v_{m})$. There are several difficulties in translating Stromquist’s continuous procedure to the discrete setting for $G$. First, agents need to divide the piece to the right of the sword in half, and this might not be possible exactly given indivisibilities; but this can be handled using our concept of lumpy ties from Section 3. Next, when the sword moves one item to the right, the lumpy ties of the agents may need to jump several items to the right, for example, because the new member of the leftmost bundle is very valuable. To ensure EF1, we will need to smoothen these jumps, so that the middle piece grows one item at a time. Also, it will be helpful to have the sword move in half-steps: it alternates between being placed between items (so it cuts the edge between the items), and being placed over an item, in which case the sword covers the item and agents ignore that item. Finally, while the sword covers an item, we will only terminate if at least two agents shout to indicate that they prefer the leftmost piece; this will ensure that there is an agent who is flexible about which of the bundles they are assigned. The algorithm moves in steps, and alternates between moving the sword, and updating the lumpy ties.

In our formal description of the algorithm, we do not use swords and knives. Instead, we maintain three bundles $L$, $M$, and $R$ that can be seen as resulting from a certain configuration this cutting implements. We also need a few definitions. For a subsequence of vertices $P(v_{s},v_{r})=(v_{s},v_{s+1},\ldots,v_{r})$ and an agent $i$, recall that $v_{j}$ ($s\leqslant j\leqslant r$) is the lumpy tie over $P(v_{s},v_{r})$ for $i$ if $j$ is the smallest index such that

Here, the definitions of $L(v_{j})$ and $R(v_{j})$ apply to the subsequence $P(v_{s},v_{r})$. The lumpy tie always exists by the discussion after equation (3.1). Each of the three agents has a lumpy tie over $P(v_{s},v_{r})$; a key concept for us is the median lumpy tie which is the median of the lumpy ties of the three agents, where the median is taken with respect to the ordering of $P(v_{s},v_{r})$. We say that $i\in N$ is a left agent (respectively, a middle agent or a right agent) over $P(v_{s},v_{r})$ if the lumpy tie for $i$ appears strictly before (respectively, is equal to, or appears strictly after) the median lumpy tie. Note that by definition of the median, there is at most one left agent, at most one right agent, and at least one middle agent. Suppose that the median lumpy tie over the subsequence $P(v_{s},v_{r})$ is $v_{j}$, and let $i$ be an agent. Then using the definitions of lumpy tie and left/right agents, we find that

Given the median lumpy tie $v_{j}$ over $P(v_{s},v_{r})$, and a two-agent set $S=\{i,k\}\subseteq N$, we define $\mathsf{Lumpy}(S,v_{j},P(v_{s},v_{r}))$ to be the allocation of the items in $P(v_{s},v_{r})$ to $S$ such that

if $i$ is a left agent and $k$ is a right agent, then $i$ receives $L(v_{j})$ and $k$ receives $R(v_{j})\cup\{v_{j}\}$;

if $i$ is a middle agent, then agent $k$ receives $k$’s preferred bundle among $L(v_{j})$ and $R(v_{j})$, and agent $i$ receives the other bundle along with $v_{j}$.

Using (4.1) and (4.2), we see that $\mathsf{Lumpy}(S,v_{j},P(v_{s},v_{r}))$ is an EF1 allocation:

Let $S=\{i,k\}\subseteq N$ and let $v_{j}$ be the median lumpy tie over $P(v_{s},v_{r})$. Then $\mathsf{Lumpy}(S,v_{j},P(v_{s},v_{r}))$ is an EF1 allocation of the items in $P(v_{s},v_{r})$ to $S$. Further, each agent in $S$ weakly prefers their bundle to $L(v_{j})$ and $R(v_{j})$.

The discrete moving-knife protocol for $n=3$ agents on a sequence $P=(v_{1},v_{2},\ldots,v_{m})$ proceeds as follows. We say that an agent $i\in N$ is a shouter if $u_{i}(L)\geqslant u_{i}(M)$ and $u_{i}(L)\geqslant u_{i}(R)$.

The moving-knife protocol finds an EF1 allocation for three agents and runs in $O(m)$ time, when $G$ is a path.

The algorithm terminates and returns an allocation, since the bundle $L$ grows throughout the algorithm until eventually, at least two agents will think that $L$ is a best bundle and thus will shout and thereby terminate the algorithm. We will now consider every possible way that the algorithm could have terminated, and show that the resulting allocation is EF1.

Step 4(a). We first prove that if $i$ is a shouter who did not shout in the previous step, then

In the previous step (which was either Step 3 or Step 4), the middle bundle was $M\setminus\{v_{r-1}\}$ and the right bundle was $\{v_{r}\}\cup R$. (While Step 4 allows for the possibility that the middle and right bundles are not changed in Step 4, this is not the case if we enter Step 4(a): if the bundles are unchanged and two agents shout, these agents already shouted in Step 3, contradicting that we did not terminate then.) Since $i$ did not shout with the middle and right bundles of the previous step, we have

Since $i$ is a shouter, $u_{i}(L)\geqslant u_{i}(M)$, so that the first case is impossible by monotonicity. Hence $u_{i}(\{v_{r}\}\cup R)>u_{i}(L)$, showing (4.5), when combined with $u_{i}(L)\geqslant u_{i}(M)$.

Agent ${s}$ does not envy others up to one good:

EF2 existence for any number of agents

For two or three agents, we have seen algorithms that are guaranteed to find an EF1 allocation on a path (and on traceable graphs). Both algorithms were adaptations of procedures that identify envy-free divisions in the cake-cutting problem. For the case of four or more agents, we face a problem: there are no known procedures that find connected envy-free division in cake-cutting if the number of agents is larger than three. However, in the divisible setting, a non-constructive existence result is known: Su (1999) proved, using Sperner’s lemma, that for any number of agents, a connected envy-free division of a cake always exists. One might try to use this result as a black box to obtain a fair allocation for the indivisible problem on a path: Translate an indivisible instance with additive valuations into a divisible cake (where each item corresponds to a region of the cake), obtain an envy-free division of the cake, and round it to get an allocation of the items. Suksompong (2019) followed this approach and showed that the result is an allocation where any agent $i$’s envy $u_{i}(A(j))-u_{i}(A(i))$ is at most $2u_{\text{max}}$, where $u_{\text{max}}$ is the maximum valuation for a single item.

In this section, rather than using Su’s (1999) result as a black box, we directly apply Sperner’s lemma to the indivisible problem. This allows us to obtain a stronger fairness guarantee: We show that on paths (and on traceable graphs), there always exists an EF2 allocation.To see that EF2 is a stronger property than bounding envy up to $2u_{\text{max}}$, consider a path of four items and two agents with additive valuations $1$–$10$–$2$–$2$. The allocation $(1,10$–$2$–$2)$ is not EF2, but the first agent has an envy of $13<20=2u_{\text{max}}$. An allocation is EF2 if any agent’s envy can be avoided by removing up to two items from the envied bundle. Again, we only allow removal of items if this operation leaves a connected bundle.

An allocation $A$ satisfies EF2 if, for any pair $i,j\in N$ of agents, either $|A(j)|\leqslant 1$, or there are two goods $u,v\in A(j)$ such that $A(j)\setminus\{u,v\}$ is connected and $u_{i}(A(i))\geqslant u_{i}(A(j)\setminus\{u,v\})$.

Let us first give a high-level illustration with three agents of how Sperner’s lemma can be used to find low-envy allocations.

Given a path $P=(a,b,c,d)$, the family of connected partitions of $P$ can naturally be arranged as the vertices of a subdivided simplex, as in Figure 5.

For each of these partitions, each agent $i$ labels the corresponding vertex by the index of a bundle from that partition that $i$ most-prefers. For example, the top vertex will be labelled as “index 1” by all agents, since they all most-prefer the leftmost bundle in $(abcd,\emptyset,\emptyset)$. Now, Sperner’s lemma will imply that at least one of the simplices (say the shaded one) is “fully-labeled”, which means that the first agent most-prefers the leftmost bundle at one vertex, the second agent most-prefers the middle bundle at another vertex, and the third agent most-prefers the rightmost bundle at the last vertex. Notice that the partitions at the corner points of the shaded simplex are all “similar” to each other (they can be obtained from each other by moving only one item). Hence, we can “round” the corner-partitions into a common allocation $A^{*}$, say by picking one of the corner partitions arbitrarily and then allocating bundles to agents according to the labels. The resulting allocation has the property that any agents’ envy can be eliminated by moving at most one good.One can generalize this argument to show that on paths, there exists an allocation $A$ satisfying a weak form of EF1: for any $i,j\in[n]$, we have $u_{i}(I_{i}\cup\{g_{i}\})\geqslant u_{i}(I_{j}\setminus\{g_{j}\})$ for some items $g_{i},g_{j}$ such that $I_{i}\cup\{g_{i}\}$ and $I_{j}\setminus\{g_{j}\}$ are connected. For additive valuations, this implies that envy is bounded by $u_{i}(g_{i})+u_{i}(g_{j})\leqslant 2u_{\text{max}}$, which is the result of Suksompong (2019).

The argument sketched above does not yield an EF1 nor even an EF2 allocation. Intuitively, the problem is that the connected partitions at the corners of the fully-labeled simplex are “too far apart”, so that no matter how we round the corner partitions into a common allocation $A^{*}$, some agents’ bundles will have changed too much, and so we cannot prevent envy even up to one or two goods. In the following, we present a solution to this problem, by considering a finer subdivision: we introduce $n-1$ knives which move in half-steps (rather than full steps), and which might ‘cover’ an item so that it appears in none of the bundles. The result is that the partial partitions in the corners of the fully-labeled simplex are closer together, and can be successfully rounded into an EF2 allocation $A^{*}$.

In our approach, we use a specific triangulation (Kuhn’s triangulation, Kuhn, 1960). This triangulation has the needed property that the partitions at the corners of sub-simplices are close together, and adjacent partitions can be obtained from each other in a natural way. While this type of triangulation has also been used in cake-cutting, e.g., by Deng et al. (2012), there it was only used to speed up algorithms (compared to the barycentric subdivision used by Su (1999)), not to obtain better fairness properties.

For each main vertex $\boldsymbol{v}_{i}$ of the simplex, $L$ assigns color $i$ to $\boldsymbol{v}_{i}$: $L(\boldsymbol{v}_{i})=i$; and

$L(\boldsymbol{v})\neq i$ for any vertex $\boldsymbol{v}\in V(T)$ belonging to the $(n-2)$-face of $S$ not containing $\boldsymbol{v}_{i}$.

Sperner’s lemma states that if $L$ is a proper labeling function, then there exists an elementary simplex of $T$ whose vertices have all different labels.

We will consider a generalized version of Sperner’s lemma, proved, for example, by Bapat (1989). In this version, there are $n$ labeling functions $L_{1},\dots,L_{n}$, and we are looking for an elementary simplex that is fully-labeled for some way of assigning labeling functions to vertices, where we must use each labeling function exactly once. The formal definition is as follows.

The generalized version of Sperner’s lemma that we consider, taken from Bapat (1989), guarantees the existence of a fully-labeled simplex.

Let $T$ be a triangulation of an $(n-1)$-simplex $S$, and let $L_{1},\dots,L_{n}$ be proper labeling functions. Then there is a fully-labeled simplex $S^{*}$ of $T$.

2 Existence of EF2 allocations

Consider the $(n-1)$-simplexThe simplex $S_{m}$ is affinely equivalent to the standard $(n-1)$-simplex $\Delta_{n-1}=\{(l_{1},\dots,l_{n})\geqslant 0:\sum l_{i}=1\}$ via $x_{i}=m\cdot(l_{1}+l_{2}+\cdots+l_{i})+\frac{1}{2}$. In these coordinates, $l_{i}$ is the length of the $i$-th piece (times $1/m$).

where $\mathbf{e}^{j}=(0,\dots,1,\dots,0)$ is the $j$-th unit vector.

Property (5.2) means that, if we visit the knife positions $\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots\boldsymbol{x}_{n}$ at the corners of an elementary simplex in the listed order, then at each step exactly one of the knives moves by half a step, and each knife moves only at one of the steps.

If there are several most-preferred bundles in $A(\boldsymbol{x})$, ties can be broken arbitrarily. However, we insist that the index $L_{i}(\boldsymbol{x})$ always corresponds to a non-empty bundle (this can be ensured since $A(\boldsymbol{x})$ always contains a non-empty bundle, and $u_{i}$ is monotonic).

The labeling functions $L_{i}$ are proper. For each $j\in[m]$, the main vertex $\boldsymbol{v}_{j}$ of the simplex $S_{m}$ has the form $\boldsymbol{v}_{j}=(\frac{1}{2},\dots,\frac{1}{2},m+\frac{1}{2},\dots,m+\frac{1}{2})$, where the first $j-1$ entries are $\frac{1}{2}$ and the rest are $m+\frac{1}{2}$. In the partition $A(\boldsymbol{v}_{j})$, the bundle $I^{j}(\boldsymbol{v}_{j})$ contains all the items, so is most-preferred (since $u_{i}$ is monotonic and by our tie-breaking), and so $L_{i}(\boldsymbol{v}_{j})=j$. Further, any vertex $\boldsymbol{x}$ belonging to the $(n-2)$-face of $S_{m}$ not containing $\boldsymbol{v}_{j}$ satisfies $x^{j-1}=x^{j}$, and thus in partition $A(\boldsymbol{x})$, bundle $I^{j}(\boldsymbol{x})$ is empty, hence is not selected, and so $L_{i}(\boldsymbol{x})\neq j$.

The fully-labeled elementary simplex $S^{*}$ corresponds to a sequence $(A_{1},A_{2},\ldots,A_{n})$ of partial partitions of $P$, which we call the Sperner sequence, where $A_{i}=(I_{i}^{1},\dots,I_{i}^{n}):=A(\boldsymbol{x}_{i})$ for each $i\in[n]$. An example of a Sperner sequence is shown in Figure 6. From the labeling, for each agent $i\in[n]$, since $L_{i}(\boldsymbol{x}_{i})=\phi(i)$, the bundle with index $\phi(i)$ in the partition $A_{i}$ is a best bundle for $i$:

Now, for each $j\in[n]$, we define the basic bundle $B^{j}:=I_{1}^{j}\cap\cdots\cap I_{n}^{j}$ to be the bundle of items that appear in the $j$-th bundle of every partition in the Sperner sequence. The set of basic bundles is a partial partition. Let us analyze the items between basic bundles.

From (5.2), each of the $n-1$ knives moves exactly once, by half a step, while passing through the Sperner sequence $(A_{1},A_{2},\ldots,A_{n})$. Thus, the numbers $x_{1}^{j},\dots,x_{n}^{j}$ take on two different values, one of which is integral and the other half-integral. We write $y^{j}$ for the integral value (so $y^{j}=x_{i}^{j}$ for some $i\in[n]$), and call $y^{j}$ a boundary item. The $j$-th knife covers the item $y^{j}$ in some, but not all, of the partial partitions in the Sperner sequence. Now, there are two cases:

$x_{1}^{j}=\dots=x_{i}^{j}=y^{j}-\frac{1}{2}$ and $x_{i+1}^{j}=\dots=x_{n}^{j}=y^{j}$ for some $i\in[n]$, so that $y^{j}$ never occurs in the $j$-th bundle in the Sperner sequence but sometimes occurs in the $(j+1)$-th bundle, or

$x_{1}^{j}=\dots=x_{i}^{j}=y^{j}$ and $x_{i+1}^{j}=\dots=x_{n}^{j}=y^{j}+\frac{1}{2}$ for some $i\in[n]$, so that $y^{j}$ sometimes occurs in the $j$-th bundle in the Sperner sequence but never occurs in the $(j+1)$-th bundle.

Since $y^{j}$ is sometimes covered by a knife, it is not part of any basic bundle. Note that

We now construct a complete partition of the path $P$ into the bundles $(I_{*}^{1},I_{*}^{2},\ldots,I_{*}^{n})$ which are defined as follows:

Thus, the bundle $I_{*}^{j}$ contains the basic bundle $B^{j}$, plus all of the boundary items $y^{j-1}$ or $y^{j}$ that occur in the $j$-th bundle at some point of the Sperner sequence. Precisely, for each boundary item $y^{j}$, $j\in[n-1]$, the item $y^{j}$ is placed in bundle $I_{*}^{j+1}$ in case (a) above, and it is placed in bundle $I_{*}^{j}$ in case (b). Thus, every item is allocated to exactly one bundle.

We first show that the partition $(I_{*}^{1},I_{*}^{2},\ldots,I_{*}^{n})$ is such that agents’ expectations about the value of the bundles $I_{*}^{j}$ are approximately correct (up to two items):

This follows by monotonicity of $u_{i}$, since $I_{*}^{j}=I_{1}^{j}\cup\cdots\cup I_{n}^{j}\supseteq I_{i}^{j}\supseteq B^{j}$ by (5.4).

Now, based on the partition, we define an allocation $A_{*}$ by $A_{*}(i)=I_{*}^{\phi(i)}$ for each agent $i\in[n]$. Then $A_{*}$ satisfies EF2: For any pair $i,j\in[n]$ of agents, we have

Hence, we have proved the main result of this section:

On a path, for any number of agents with monotone valuation functions, a connected EF2 allocation exists.

EF1 existence for four agents

We have seen that Sperner’s lemma can be used to show EF2 existence for any number of agents. Why does our proof in the previous section only establish EF2, and not EF1? The reason is that agents’ expectations about the contents of a bundle might differ by up to two goods from what the bundle will actually contain. In the notation of the previous section, an agent $i$ may be presented with a partial partition $I_{i}$ where the $j$-th bundle $I_{i}^{j}$ is the basic bundle, i.e., $I_{i}^{j}=B^{j}$. The agent then selects their favorite bundle from $I_{i}$, implicitly assuming that the $j$-th bundle in the rounded partition $I_{*}$ will also equal $B^{j}$, i.e., that $I_{*}^{j}=B^{j}$. However, it may happen that in fact $I_{*}^{j}=\{y^{j-1}\}\cup B^{j}\cup\{y^{j}\}$, and then $i$ envies the agent who receives bundle $j$ by a margin of two goods.

For four agents, we can adapt our argument to achieve EF1. To do this, we both change the way we round the Sperner sequence into an allocation, and define new labeling functions that better anticipate how a partial partition will be rounded into the final allocation. In this way, agents’ expectations about bundles can only be wrong up to one good. In crude terms, agents will expect that each of the two interior bundles will be assigned at least one of the boundary items, and the rounding method ensures that this will indeed happen.

Thus, for an interior bundle $j=2,3$, if both the items $x^{j-1}$ and $x^{j}$ to either side of the bundle are covered by a knife, an agent expects that one of these items (the less-valuable one) will be put into bundle $I_{*}^{j}$ of the final rounded allocation (recall the definition of $u_{i}^{-}$ in equation (2.1)). For exterior bundles, $j=1$ (resp. $j=4$), if the item $x^{1}$ (resp. $x^{3}$) is not covered by a knife, the agent does not expect the interior item (next to the knife) to belong to the final bundle $I_{*}^{j}$, even though it belongs to the observed bundle $I_{i}^{j}$. Otherwise, the virtual allocations are equal to $u_{i}(I^{j}(\boldsymbol{x}))$, so the agent expects that $I_{*}^{j}=I_{i}^{j}$. Later, we show that these expectations are correct up to one item.

One can check that these valuation functions are still proper.

To shorten a case distinction, we assume that $y^{2}\in I^{2}_{1}\cup I^{2}_{2}\cup I^{2}_{3}\cup I^{2}_{4}$, i.e., that the boundary item $y^{2}$ appears in the second but not in the third bundle in the Sperner sequence. This assumption is without loss of generality, since by the left-right symmetry of the definition of virtual valuations, if necessary we can reverse the path $P$ and consider the same elementary simplex with vertices ordered in reverse ($\boldsymbol{x}_{4},\boldsymbol{x}_{3},\boldsymbol{x}_{2},\boldsymbol{x}_{1}$); it will still be fully-labeled.

With this assumption made throughout the rest of the argument, we now round the Sperner sequence into a complete partition $(I_{*}^{1},I_{*}^{2},I_{*}^{3},I_{*}^{4})$ of $P$ defined as follows:

Depending on the placement of the boundary item $y^{1}$, we will either have $I_{*}^{1}=B^{1}$ or $I_{*}^{1}=B^{1}\cup\{y^{1}\}$; and either $I_{*}^{2}=\{y^{1}\}\cup B^{2}\cup\{y^{2}\}$ or $I_{*}^{2}=B^{2}\cup\{y^{2}\}$. With these choices, each interior bundle ($j=2,3$) receives at least one of the boundary items adjacent to it.

The main part of showing that the partition $(I_{*}^{1},I_{*}^{2},I_{*}^{3},I_{*}^{4})$ can be made into an EF1 allocation is an analogue of (5.5), which shows that agents’ expectations about their bundle are approximately correct. The following analogous proposition is proved by case analysis.

For each $i\in[n]$ and each $j\in[n]$, we have $u_{i}(I_{*}^{j})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},j)\geqslant u_{i}^{-}(I_{*}^{j})$.

We consider each bundle $j=1,2,3,4$ separately.

$y^{1}=x_{i}^{1}-\frac{1}{2}$ so that $y^{1}\in I_{i}^{1}$, and so $I_{*}^{1}=B^{1}\cup\{y^{1}\}=\{1,\dots,x_{i}^{1}-\frac{1}{2}\}$, or

$y^{1}=x_{i}^{1}+\frac{1}{2}$ so that $y^{1}\not\in I_{*}^{1}$, and so $I_{*}^{1}=B^{1}=\{1,\dots,x_{i}^{1}-\frac{1}{2}\}$.

In either case, $I_{*}^{1}=\{1,\dots,x_{i}^{1}-\frac{3}{2},x_{i}^{1}-\frac{1}{2}\}$, so $u_{i}(I_{*}^{1})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},1)\geqslant u_{i}^{-}(I_{*}^{1})$.

Suppose $j=2$, and suppose that $I_{*}^{2}=B^{2}\cup\{y^{2}\}$

Otherwise $\hat{u}_{i}(\boldsymbol{x}_{i},2)=u_{i}(I_{i}^{2}(\boldsymbol{x}))$. Since $y^{1}\not\in I_{1}^{2}(\boldsymbol{x})$ (because $y^{1}\in I^{1}_{*}$), we have that $I_{i}^{2}(\boldsymbol{x})$ is either $B^{2}$ or $B^{2}\cup\{y^{2}\}$. So $u_{i}(I_{*}^{2})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},2)=u_{i}(I_{i}^{2}(\boldsymbol{x}))\geqslant u_{i}^{-}(I_{*}^{2})$ since $I_{*}^{2}=B^{2}\cup\{y^{2}\}$.

Suppose $j=2$, and suppose that $I_{*}^{2}=\{y^{1}\}\cup B^{2}\cup\{y^{2}\}$.

Otherwise $\hat{u}_{i}(\boldsymbol{x}_{i},2)=u_{i}(I_{i}^{2}(\boldsymbol{x}))$. First note that $I_{i}^{2}(\boldsymbol{x})\neq B^{2}$: this is because both $y^{1}$ and $y^{2}$ appear in the second bundle of the Sperner sequence (by the case and the wlog assumption), so that $x_{i}^{1}\leqslant y^{1}$ and $y^{2}\leqslant x_{i}^{2}$. Since at least one of $x_{i}^{1}$ or $x_{i}^{2}$ is not integral, at least one of $y^{1}$ or $y^{2}$ must be in $I_{i}^{2}(\boldsymbol{x})$. Hence $I_{i}^{2}(\boldsymbol{x})$ is either $\{y^{1}\}\cup B^{2}\cup\{y^{2}\}$ or $\{y^{1}\}\cup B^{2}$ or $B^{2}\cup\{y^{2}\}$. In each case, $u_{i}(I_{*}^{2})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},2)=u_{i}(I_{i}^{2}(\boldsymbol{x}))\geqslant u_{i}^{-}(I_{*}^{2})$ since $I_{*}^{2}=\{y^{1}\}\cup B^{2}\cup\{y^{2}\}$.

Otherwise, since $y^{2}$ does not appear in $I_{1}^{3}(\boldsymbol{x})$ (by our wlog assumption), we have that $I_{i}^{3}(\boldsymbol{x})$ is either $B^{3}$ or $B^{3}\cup\{y^{3}\}$. Now $u_{i}(I_{*}^{3})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},3)=u_{i}(I_{i}^{3}(\boldsymbol{x}))\geqslant u_{i}^{-}(I_{*}^{3})$ since $I_{*}^{3}=B^{3}\cup\{y^{3}\}$.

$y^{3}=x_{i}^{3}+\frac{1}{2}$ so $I_{*}^{4}=B^{4}=\{x_{i}^{3}+\frac{3}{2},\dots,m\}$, or

$y^{3}=x_{i}^{3}-\frac{1}{2}$ so $I_{*}^{4}=B^{4}=\{x_{i}^{3}+\frac{1}{2},\dots,m\}$.

In either case, $u_{i}(I_{*}^{4})\geqslant\hat{u}_{i}(\boldsymbol{x}_{i},4)=u_{i}(\{x_{i}^{3}+\frac{3}{2},\dots,m\})\geqslant u_{i}^{-}(I_{*}^{4})$.∎

Now again, based on the partition, we can define an allocation $A_{*}$ by $A_{*}(i)=I_{*}^{\phi(i)}$ for each agent $i\in[n]$. Thus, each agent $i$ receives the bundle in the complete partition corresponding to $i$’s most-preferred index $\phi(i)$. We prove that $A_{*}$ satisfies EF1: For any pair $i,j\in[n]$ of agents, we have

Hence, we have proved the main result of this section:

On a path, for four agents with monotone valuation functions, a connected EF1 allocation exists.

For five or more agents, we were not able to construct labeling functions and a rounding scheme which ensure that agents’ expectations are correct up to one item. In the four-agent case, each interior bundle is adjacent to an exterior bundle (which helps in the construction), but for five agents, there is a middle bundle whose neighboring bundles are also interior.

EF1 existence for identical valuations

A special case of the fair division problem is the case of identical valuations, where all agents have the same valuation for the goods: for all agents $i,j\in N$ and every bundle $I\in\mathcal{C}(V)$, we have $u_{i}(I)=u_{j}(I)$. We then write $u(I)$ for the common valuation of bundle $I$. The case of identical valuations often allows for more positive results and an easier analysis. Indeed, we can prove that, for identical valuations and any number of agents, an EF1 allocation connected on a path is guaranteed to exist and can be found in polynomial time.

Now, one might guess that in the restricted case of identical valuations, egalitarian allocations are EF1. However, the leximin-optimal connected allocation may fail EF1: Consider a path with five items and additive valuations 1–3–1–1–1 shared by three agents. The unique leximin allocation is (1, 3, 1–1–1), which induces envy even up to one good. The same allocation also uniquely maximizes Nash welfare, so the Nash optimum also does not guarantee EF1. In contrast, when requiring bundles to satisfy matroid constraints (rather than connectivity constraints), the Nash optimum is EF1 with identical valuations (Biswas and Barman, 2018).

Maximizing an egalitarian objective seemed promising because it ensures that no-one is too badly off, and therefore has not much reason to envy others. The problem is that some bundles might be too desirable. To fix this, we could try to reallocate items so that no bundle is too valuable. This is exactly the strategy of our algorithm: It starts with a leximin allocation, and then moves items from high-value bundles to lower-value bundles, until the result is EF1. In more detail, the algorithm identifies one agent $i$ who is worst-off in the leximin allocation, and then adjusts the allocation so that $i$ does not envy any other bundle up to one good. The algorithm does this by going through all bundles in the allocation, outside-in, and if $i$ envies a bundle $I^{j}$ even up to one good, it moves one item from $I^{j}$ inwards (in $i$’s direction), see Figure 7. As we will show, a key invariant preserved by the algorithm is that the value of $I^{i}$ never increases, and $i$ remains worst-off. Thus, since $i$ does not envy others up to one good, the allocation at the end is EF1.

Formally, a leximin allocation is an allocation which maximizes the lowest utility of an agent; subject to that it maximizes the second-lowest utility, and so on. In particular, if the highest achievable minimum utility is $u_{L}$, then the leximin allocation is such that every agent has utility at least $u_{L}$, and the number of agents with utility exactly $u_{L}$ is minimum.

For identical valuations on a path, Algorithm 1 finds an EF1 allocation.

For an allocation $A=(I^{1},\dots,I^{n})$, write $u_{L}(A):=\min_{j\in N}u(I^{j})$ for the minimum utility obtained in $A$, and write $L(A):=\{j\in[n]:u(I^{j})=u_{L}(A)\}$ for the set of agents (losers) who obtain this utility. For the leximin allocation $A_{\text{leximin}}$ obtained at the start of the algorithm, write $u_{L}^{*}:=u_{L}(A_{\text{leximin}})$ and $L^{*}:=L(A_{\text{leximin}})$. Note that by leximin-optimality, for every allocation $A$ we must have $u_{L}(A)\leqslant u_{L}^{*}$, and if $u_{L}(A)=u_{L}^{*}$ then $|L(A)|\geqslant|L^{*}|$. Let $i\in L^{*}$ be the agent fixed at the start of the algorithm.