The Price of Connectivity in Fair Division

Introduction

We consider a classical resource allocation setting where a set of goods is to be allocated among interested agents. Our goal is to find an allocation that is fair to all agents. This problem has been addressed in a large body of literature on fair division (Brams and Taylor 1996a; Moulin 2003), which has found applications ranging from divorce settlement (Brams and Taylor 1996b) to credit assignment (de Clippel et al. 2008). The two most prominent fairness notions in the literature are envy-freeness and proportionality. An allocation is said to be envy-free if every agent likes her bundle at least as much as any other agent’s bundle, and proportional if every agent receives value at least $1/n$ of her value for the entire set of goods, where $n$ denotes the number of agents.

Our focus in this paper is on the setting where we allocate indivisible goods. This pertains to the allocation of houses, cars, artworks, electronics, and many other common items. When goods are indivisible, neither envy-freeness nor proportionality can always be fulfilled, e.g., when two agents try to divide a single valuable good. As a result, relaxations of both notions have been studied. Envy-freeness is often relaxed to envy-freeness up to one good (EF1)—this means that any envy that an agent has towards another agent can be eliminated by removing a good from the latter agent’s bundle. An EF1 allocation exists for any number of agents with arbitrary monotonic utilities (Lipton et al. 2004). Likewise, proportionality can be relaxed to maximin share fairness—the maximin share (MMS) of an agent is the largest value that the agent can guarantee for herself if she is allowed to divide the goods into $n$ parts and always receives the worst part. An allocation that gives every agent her maximin share—said to satisfy maximin share fairness—does not always exist for additive utilities, but a constant multiplicative approximation can be obtained (Kurokawa et al. 2018).

Perhaps the most well-known fair division protocol is the cut-and-choose protocol, which dates back to at least the Bible and can be used to allocate a divisible good between two agents. In this protocol, the first agent divides the good into two equal parts (this is possible because the good is divisible), and the second agent chooses the part that she prefers. The cut-and-choose protocol has a direct analogue in the indivisible goods setting: since an equal partition may no longer exist, the first agent now divides the goods into two parts that are as equal as possible in her view. The resulting allocation is guaranteed to satisfy both maximin share fairness and EF1. In fact, it also satisfies a notion called envy-freeness up to any good (EFX), which is stronger than EF1 (Plaut and Roughgarden 2020a). However, these guarantees rely crucially on the assumption that any allocation of the goods to the two agents can be chosen—in reality, there are often constraints on the allocations that we desire. One common type of constraints is captured by a model of Bouveret et al. 2017, where the goods are vertices of a connected undirected graph and each agent must be allocated a connected subgraph. For instance, the goods could represent offices in a university building that we wish to divide between research groups, and it is desirable for each group to receive a connected set of offices in order to facilitate communication within the group. To what extent do the fairness guarantees continue to hold when connectivity constraints are imposed, and how does the answer depend on the underlying graph? Put another way, what is the price in terms of fairness that we have to pay if we desire connectivity?

In this paper, we make several contributions to the active line of work on fairly allocating indivisible goods under connectivity constraints. We survey this line of work in Section 1.2. While we also provide fairness guarantees for any number of agents, the majority of our results concern the setting of two agents. We emphasize here that this setting is fundamental in fair division. Indeed, a number of fair division applications including divorce settlements, inheritance division, and international border disputes often fall into this setting, and numerous prominent works in the field deal exclusively with the two-agent case (e.g., (Brams and Fishburn 2000; Brams et al. 2012; Brams et al. 2014; Kilgour and Vetschera 2018)). See also (Plaut and Roughgarden 2020b, Section 1.1.1) for further discussion on the importance of the two-agent setting. In addition, as we will see, under connectivity constraints the setting with two agents is already surprisingly rich and gives rise to several mathematically deep and challenging questions.

We begin by studying maximin share fairness for agents with additive utilities. We define the price of connectivity (PoC) of a graph to be the largest multiplicative gap between the maximin share defined over all possible partitions and the graph maximin share (G-MMS), which is defined over all partitions that respect the connectivity constraints of the graph. For any graph and any number of agents, it follows from the definitions that if the PoC is $\alpha$ and one can give each agent $\beta$ times her G-MMS, then it is also possible to guarantee all agents a $\beta/\alpha$ fraction of their MMS. Moreover, in cases where giving every agent their full G-MMS is possible (i.e., $\beta=1$), we observe in Section 2 that the resulting factor $1/\alpha$ is tight—in other words, the PoC is the reciprocal of the optimal MMS approximation that can be achieved. Since it is known from prior work that $\beta=1$ for two agents and arbitrary graphs as well as for any number of agents and trees, our PoC notion precisely captures the best possible MMS guarantee in these cases. Hence, determining the PoC, whose definition only involves a single utility function, allows us to identify the optimal MMS guarantee for agents with possibly different utility functions.

With this relationship in hand, we proceed to determine the PoC of various graphs; our results are summarized in Table 1. In the two-agent case (Section 3.1), we show that the PoC is related to the vertex connectivity of the graph, i.e., the minimum number of vertices whose deletion disconnects the graph. For graphs with connectivity exactly $1$, including all trees, we show that the PoC is equal to the maximum number of connected components that result from deleting one vertex. As a consequence, the PoC is at least $2$ for any graph in this class. On the other hand, we show an upper bound of $4/3$ for all graphs with connectivity at least $2$—this bound is tight for all graphs with connectivity exactly $2$ and, perhaps surprisingly, for certain graphs with connectivity up to $5$. In addition, we pose an intriguing conjecture that the PoC of any graph with connectivity at least $2$ is closely related to its “linkedness”—the two-agent case would be completely solved if the conjecture holds—and verify our conjecture when the graph is a complete graph with an arbitrary matching removed.

For any number of agents (Section 3.2), we establish a general upper bound of $m-n+1$ on the PoC (where $m$ and $n$ denote the number of goods and agents, respectively), and show that this implies the existence of a connected allocation that gives every agent at least a $1/(m-n+1)$ fraction of her MMS with respect to any graph. We also derive the exact PoC for paths and stars. Notably, in order to establish the PoC for paths, we introduce a new relaxation of proportionality that we call the indivisible proportional share (IPS) property. This notion strengthens a number of relaxations of proportionality in the literature while maintaining guaranteed existence, so we believe that it may be of independent interest as well.

Next, in Section 4 we turn our attention to envy-freeness relaxations and allow agents to have arbitrary monotonic utilities. In the case of two agents, Bilò et al. 2022 characterized the graphs for which an EF1 allocation always exists as the graphs that admit a “bipolar ordering” (defined in Section 2). While the characterization yields a strong fairness guarantee for this class of graphs, it does not give any guarantee for the remaining graphs. We generalize this result by establishing the optimal relaxation of envy-freeness for every graph—specifically, for each graph, we determine the smallest $k$ for which an allocation that is envy-free up to $k$ goods (EF$k$) always exists with two agents. Intuitively, the less connected the graph is, the weaker the fairness guarantee we can make, i.e., the higher the price we have to pay. As a corollary, an EF$(m-2)$ allocation exists for any connected graph, and the bound $m-2$ is tight for stars. By contrast, we show that the fairness notion envy-freeness up to any good (EFX), which is stronger than EF1, can only be guaranteed for complete graphs with two agents. We then address the case of three agents, where we characterize the set of trees and complete bipartite graphs that admit an EF1 allocation for arbitrary utilities. In particular, our result for complete bipartite graphs answers an open question raised by Bilò et al. 2022.

From a technical point of view, our work makes extensive use of tools and concepts from graph theory, including vertex connectivity, linkedness, ear decompositions, bipolar orderings, and block decompositions. While bipolar ordering and block decomposition have been used by Bilò et al. 2022 in the EF1 characterization that we mentioned, the other concepts have not previously appeared in the fair division literature to the best of our knowledge. We believe that establishing these connections enriches the growing literature and lays the groundwork for fruitful collaborations between researchers across the two well-established fields.

Finally, we remark that with the exception of Theorem 3.11, all of our guarantees are constructive. In particular, we exhibit polynomial-time algorithms that produce allocations satisfying the guarantees.

2 Related Work

The fair allocation of indivisible goods has received considerable attention from various research communities, especially in the last few years. We refer to surveys by Thomson 2016, Markakis 2017, and Moulin 2019 for an overview of recent developments in the area.

The papers most closely related to ours are the two papers that we mentioned, by Bouveret et al. 2017 and Bilò et al. 2022. Bouveret et al. showed that for any number of agents with additive utilities, there always exists an allocation that gives every agent her maximin share when the graph is a tree, but not necessarily when the graph is a cycle. It is important to note that their maximin share notion corresponds to our G-MMS notion and is defined based on the graph, with only connected allocations with respect to that graph taken into account in an agent’s calculation. As an example of a consequence, even though a cycle permits strictly more connected allocations than a path, it offers less guarantee in terms of the G-MMS. Our approach of considering the (complete-graph) MMS allows us to directly compare the guarantees that can be obtained for different graphs.

Bilò et al. 2022 investigated the same model with respect to relaxations of envy-freeness. As we mentioned, they characterized the set of graphs for which EF1 can be guaranteed in the case of two agents with arbitrary monotonic utilities. Moreover, they showed that an EF1 allocation always exists on a path for $n\leq 4$. Intriguingly, the existence question for $n\geq 5$ remains open, although they showed that an EF2 allocation can be guaranteed for any $n$.

Besides Bouveret et al. 2017 and Bilò et al. 2022, a number of other authors have recently studied fairness under connectivity constraints. Lonc and Truszczynski 2020 investigated maximin share fairness in the case of cycles, also using the G-MMS notion, while Suksompong 2019 focused on paths and provided approximations of envy-freeness, proportionality, as well as another fairness notion called equitability. Igarashi and Peters 2019 considered fairness in conjunction with the economic efficiency notion of Pareto optimality. Bouveret et al. 2019 studied the problem of chore division, where all items yield disutility to the agents, and gave complexity results on deciding the existence of envy-free, proportional, and equitable allocations for paths and stars. Bei and Suksompong 2021 and Igarashi and Zwicker 2021 proposed similar models in which the resource is divisible and forms the edges of a graph (as opposed to the vertices). Elkind et al. 2021b studied such models with respect to maximin share fairness.

Considering connected allocations can also be useful in settings where we are not interested in connectedness per se, or perhaps the goods do not even lie on any graph. A technique that has received interest recently is to arrange the goods on a path and compute a connected allocation with respect to the path. Variants of this technique have been used to devise algorithms that find a fair allocation using few queries (Oh et al. 2021) or divide goods fairly among groups of agents (Segal-Halevi and Suksompong 2019; Kyropoulou et al. 2020).

A related line of work also combines graphs with resource allocation, but uses graphs to capture the connection between agents instead of goods. In particular, a graph specifies the acquaintance relationship among agents. Abebe et al. 2017 and Bei et al. 2017 defined graph-based versions of envy-freeness and proportionality with divisible resources where agents only evaluate their shares relative to other agents with whom they are acquainted. Beynier et al. 2019 and Bredereck et al. 2022 studied the graph-based version of envy-freeness with indivisible goods. Aziz et al. 2018 introduced a number of fairness notions parameterized by the acquaintance graph. In addition to graphs, other types of constraints that have been considered in the fair division literature include cardinality constraints (Biswas and Barman 2018), matroid constraints (Gourvès and Monnot 2019; Dror et al. 2021), and separation constraints (Elkind et al. 2021a; Elkind et al. 2021c). Constraints in fair division have recently been surveyed by Suksompong 2021.

Beyond resource allocation, the problem of partitioning a graph into connected subgraphs has been studied in other areas of discrete mathematics and theoretical computer science (Dyer and Frieze 1985; van ’t Hof et al. 2009; Paulusma and van Rooij 2011).

Preliminaries

Let $N=\{1,2,\dots,n\}$ denote the set of agents, and $M=\{1,2,\dots,m\}$ the set of goods. There is a bijection between the goods in $M$ and the $m$ vertices of a connected undirected graph $G$; we will refer to goods and vertices interchangeably. A bundle is a subset of goods, and an allocation is a partition of $M$ into $n$ bundles $(M_{1},\dots,M_{n})$ such that agent $i$ receives bundle $M_{i}$. A bundle is called connected if the goods in it form a connected subgraph of $G$, and an allocation or a partition is connected if all of its bundles are connected. We assume in this paper that allocations are required to be connected.

Each agent $i$ has a nonnegative utility $u_{i}(M^{\prime})$ for each bundle $M^{\prime}\subseteq M$, where we assume without loss of generality that $u_{i}(\emptyset)=0$ for all $i$. For a good $g\in M$, we will use $u_{i}(\{g\})$ and $u_{i}(g)$ interchangeably. We assume that utilities are additive, i.e., $u(M^{\prime})=\sum_{g\in M^{\prime}}u(g)$ for all $M^{\prime}\subseteq M$; this assumption is commonly made in the fair division literature, especially when studying maximin share fairness (Bouveret et al. 2017; Kurokawa et al. 2018; Gourvès and Monnot 2019; Lonc and Truszczynski 2020). An instance consists of the goods, their underlying graph, the agents, and their utilities for the goods.

We are ready to define maximin share fairness.

Given a graph $G$, an additive utility function $u$, and the number of agents $n$, the graph maximin share (G-MMS) for $G,u,n$ is defined as

where the maximum is taken over all partitions $(M_{1},\dots,M_{n})$ that are connected with respect to $G$. The maximin share (MMS) for $u,n$ is defined as

where $K_{m}$ denotes the complete graph over the goods. When the parameters are clear from the context, we will refer to the graph maximin share and the maximin share simply as G-MMS and MMS, respectively. A partition for which the maximum is attained is called a G-MMS partition (resp., MMS partition).

for all $G,u,n$, and $\text{G-MMS}(G_{1},u,n)\leq\text{G-MMS}(G_{2},u,n)$ if $G_{1}$ is a subgraph of $G_{2}$. Moreover, $\text{G-MMS}(G,u,n)=\text{MMS}(u,n)=0$ if $m<n$.

Next, we define the price of connectivity.

Given a graph $G$ and the number of agents $n$, the price of connectivity (PoC) of $G$ for $n$ agents is defined as

where the supremum is taken over all possible additive utility functions $u$. We interpret $\frac{0}{0}$ in this context to be equal to $1$. Note that $\text{MMS}(u,n)=0$ if and only if $\text{G-MMS}(G,u,n)=0$—indeed, since we assume that $G$ is connected, both conditions are equivalent to the condition that fewer than $n$ goods yield a positive utility according to $u$. We denote the PoC of a graph $G$ for $n$ agents by $\text{PoC}(G,n)$.

for any $G,u,n$, and the factor $\text{PoC}(G,n)$ cannot be replaced by any smaller factor. When $G$ and $n$ are clear from the context, we will refer to $\text{PoC}(G,n)$ simply as PoC. Note that the PoC is always at least $1$, and is exactly $1$ for complete graphs of any size. Moreover, the PoC is $1$ if $m\leq n$.

Suppose that for some graph $G$ and number of agents $n$, there always exists a connected allocation that gives each agent at least $\beta$ times her G-MMS. By (1), this allocation also gives each agent at least $\beta/\text{PoC}(G,n)$ times her MMS. Prior work has established that $\beta=1$ when $n=2$ and $G$ is arbitrary (Lonc and Truszczynski 2020, Cor. 2), as well as when $G$ is a tree and $n$ is arbitrary (Bouveret et al. 2017, Thm. 5.4). Hence, in these cases, we can guarantee each agent at least $1/\text{PoC}(G,n)$ times her MMS. The factor $1/\text{PoC}(G,n)$ is also the best possible. To see this, consider $n$ agents with the same utility function $u$. From the definition of G-MMS, any connected allocation gives some agent a value of at most $\text{G-MMS}(G,u,n)$. By considering $u$ such that $\text{G-MMS}(G,u,n)$ is arbitrarily close to $\text{MMS}(u,n)/\text{PoC}(G,n)$, this agent receives arbitrarily close to $1/\text{PoC}(G,n)$ times her MMS. To summarize, we have the following proposition.

Let $n$ be any positive integer and $G$ be any graph. If $n=2$ (and $G$ is arbitrary), or if $G$ is a tree (and $n$ is arbitrary), then there always exists a connected allocation that gives each agent at least $1/\text{PoC}(G,n)$ times her MMS. Moreover, the factor $1/\text{PoC}(G,n)$ is tight in both cases.

Proposition 2.3 implies that if there are two agents or $G$ is a tree, in order to determine the optimal MMS approximation for agents with possibly different utilities, it suffices to determine the value $\text{PoC}(G,n)$, which only concerns a single utility function.

We now introduce relaxations of envy-freeness (Lipton et al. 2004; Caragiannis et al. 2019).

An allocation $(M_{1},\dots,M_{n})$ satisfies

envy-freeness up to $k$ goods (EF$k$), for a given nonnegative integer $k$, if for any agents $i,j$, there exists a (possibly empty) bundle $M^{\prime}\subseteq M_{j}$ with $|M^{\prime}|\leq k$ such that $u_{i}(M_{i})\geq u_{i}(M_{j}\setminus M^{\prime})$.

envy-freeness up to any good (EFX) if for any agents $i,j$ and any good $g\in M_{j}$, we have $u_{i}(M_{i})\geq u_{i}(M_{j}\setminus\{g\})$.

An EF0 allocation is said to be envy-free. It follows immediately from the definition that envy-freeness implies EFX, which in turn implies EF1. If we do not have to allocate all of the goods, achieving envy-freeness and all of its relaxations is trivial, for example by simply not allocating any good. Hence we will assume that all goods must be allocated when we discuss envy-freeness and its relaxations.

All graphs considered in this paper are assumed to be connected. The vertex connectivity (or simply connectivity) of a graph $G$ is the minimum number of vertices whose deletion disconnects $G$. A graph with vertex connectivity at least $k$ is said to be $k$-connected. By definition, every connected graph is 1-connected. A 2-connected graph is also called biconnected. A bipolar ordering (also called bipolar numbering) of a graph is an ordering of its vertices such that every prefix and every suffix of the ordering forms a connected graph.

Maximin Share Fairness

In this section, we consider maximin share fairness. Our goal is to derive bounds on the PoC for arbitrary graphs in the case of two agents, and for paths and stars in the general case. By Proposition 2.3, this also yields the optimal MMS approximation for each of these cases.

We first focus on the case of two agents and start by establishing the PoC for all graphs with connectivity $1$.

Let $G$ be a graph with connectivity exactly $1$, and let $k\geq 2$ be the maximum number of connected components that can result from deleting a single vertex of $G$. Then $\text{PoC}(G,2)=k$.

First, we show that the PoC of $G$ is at least $k$. Let $v$ be a vertex of $G$ whose deletion results in $k$ components. Consider a utility function with value $k$ for $v$, value $1$ for an arbitrary vertex in each of the $k$ components, and value $0$ for all other vertices. The MMS is $k$. In any connected bipartition, the part that does not contain $v$ is a subset of one of the $k$ components, so this part has value at most $1$. Hence the PoC is at least $k$.

Next, we show that the PoC of $G$ is at most $k$. Take an arbitrary utility function $u$, and assume without loss of generality that $u(M)=1$. Since $\text{MMS}(u,2)\leq u(M)/2=1/2$, the desired claim follows if there is a connected bipartition such that both parts have value at least $1/(2k)$. Assume that no such bipartition exists.

Pick a spanning tree $T$ of $G$, and let $v$ be an arbitrary vertex. The removal of $v$ results in a number of subtrees of $T$; clearly, at most one of these subtrees can have value more than $1/2$. If such a subtree exists, we move from $v$ towards the adjacent vertex in that subtree and repeat the procedure with the new center vertex. Note that we will never traverse back an edge—otherwise there are two disjoint subtrees with value more than $1/2$ each, contradicting $u(M)=1$. Since the tree is finite, we eventually reach a vertex $v$ such that all subtrees $T_{1},\dots,T_{r}$ resulting from the removal of $v$ have value at most $1/2$ each.

Since $T_{i}$ and $T\setminus T_{i}$ are both connected for every $i$, by our earlier assumption, each of the subtrees $T_{1},\dots,T_{r}$ has value less than $1/(2k)$. Recall that in the original graph $G$, removing $v$ can result in at most $k$ components. This means that if $r>k$, the $r$ subtrees must be connected by some edges not belonging to $T$. If subtrees $T_{i}$ and $T_{j}$ are connected by such an edge, we can merge $T_{i}$ and $T_{j}$ into one component. Note that $T_{i}\cup T_{j}$ has value less than $1/(2k)+1/(2k)=1/k\leq 1/2$, so since $T_{i}\cup T_{j}$ and $T\setminus(T_{i}\cup T_{j})$ are both connected, $T_{i}\cup T_{j}$ must again have value less than $1/(2k)$. Our procedure can be repeated until the components can no longer be merged, at which point we are left with at most $k$ components. Each of these components has value less than $1/(2k)$, which implies that $v$ has value more than $1-k/(2k)=1/2$. In this case, a bipartition with $v$ as one part is an MMS partition, so $\text{MMS}(u,2)=1-u(v)$. On the other hand, at least one of the (at most) $k$ components has value at least $(1-u(v))/k$, which is $1/k$ of the MMS. We can take a connected bipartition with such a component as one part and obtain the desired result. ∎

We remark that the proof of Theorem 3.1 also yields a polynomial-time algorithm for computing a bipartition such that both parts have value at least $1/k$ of the MMS. To compute an allocation between two agents such that both agents receive $1/k$ of their MMS, we simply let the first agent compute a desirable bipartition, and let the second agent choose the part that she prefers. Since $\text{MMS}(u,2)\leq u(M)/2$, the second agent is always satisfied.

Before we move on to results about graphs with higher connectivity, we show the following lemma, which will help simplify our subsequent proofs. The lemma implies that in order to prove an upper bound on the PoC in the case of two agents, it suffices to establish the bound for utility functions such that in an MMS partition, the two parts are of equal value.

For $n=2$ and any graph $G$, the PoC remains the same if instead of taking the supremum in Definition 2.2

over all utility functions $u$, we only take the supremum over all utility functions $u$ such that in any MMS partition according to $u$, the two parts are of equal value.

Let $u$ be an arbitrary utility function, and suppose that in an MMS partition, the two parts are of value $x\leq y$. We have $\text{MMS}(u,2)=x$. Let $\alpha:=\frac{\text{MMS}(u,2)}{\text{G-MMS}(G,u,2)}$. In any connected bipartition, each part either has value at most $x/\alpha$, or at least $(x+y)-x/\alpha=y+(1-1/\alpha)x$.

Consider a modified utility function $u^{\prime}$ where in the MMS partition above, we arbitrarily decrease the values of some goods in the part with value $y$ so that the part has value $x$. It is clear that $\text{MMS}(u^{\prime},2)=x$. With respect to $u^{\prime}$, in any connected bipartition, each part either has value at most $x/\alpha$, or at least $y+(1-1/\alpha)x-(y-x)=(2-1/\alpha)x$. This means that $\text{G-MMS}(G,u^{\prime},2)\leq x/\alpha=\text{MMS}(u^{\prime},2)/\alpha$, or $\frac{\text{MMS}(u^{\prime},2)}{\text{G-MMS}(G,u^{\prime},2)}\geq\alpha$. Since the two parts in any MMS partition according to $u^{\prime}$ are of equal value, the proof is complete. ∎

Next, we consider biconnected graphs, i.e., graphs with connectivity at least $2$. We show that the PoC is at most $4/3$ for all such graphs—this is in contrast to graphs with connectivity $1$, which have PoC at least $2$ according to Theorem 3.1. For this result, we will use a property of biconnected graphs which we state in the following proposition. An open ear decomposition of a graph consists of a cycle as the first ear and a sequence of paths as subsequent ears such that in each path, the first and last vertices (which must be different) belong to previous ears while the remaining vertices do not. See Figure 1 for an illustration.

In a biconnected graph with at least three vertices, any two vertices belong to a common cycle, and there exists an open ear decomposition. Moreover, we may choose any cycle in the graph as the first ear. There is also a linear-time algorithm for computing an open ear decomposition with an arbitrary cycle as the first ear (Schmidt 2013).

Let $G$ be a biconnected graph. Then $\text{PoC}(G,2)\leq 4/3$.

The case $m\leq 2$ is trivial since $n=2$ and the PoC is $1$ in this case, so consider $m\geq 3$. Take an arbitrary utility function $u$, and assume without loss of generality that $u(M)=1$. By Lemma 3.2, we may also assume that $\text{MMS}(u,2)=1/2$. Call a good heavy if it has value strictly more than $1/4$. Since there can be at most one heavy good in each part of an MMS partition, there are at most two heavy goods in total. Pick goods $g_{1}$ and $g_{2}$ so that together they include all of the heavy goods. By Proposition 3.3, there is a cycle in $G$ containing $g_{1}$ and $g_{2}$, and an open ear decomposition with this cycle as the first ear.

We will construct a bipolar ordering of the vertices that begins with $g_{1}$ and ends with $g_{2}$. Assume that the first ear is a cycle with vertex order

see Figure 1 for an illustration. We arrange these vertices as

For each subsequent ear, suppose that the two vertices belonging to previous ears are $h$ and $h^{\prime}$, where $h$ appears before $h^{\prime}$ in the current ordering. We insert the remaining vertices on the path from $h$ to $h^{\prime}$ into the ordering directly after $h$, following the same order as in the path. One can check (for example, by induction on the number of ears) that the resulting ordering is a bipolar ordering beginning with $g_{1}$ and ending with $g_{2}$.

Consider first the case where $\max\{u(g_{1}),u(g_{2})\}>1/2$; assume without loss of generality that $u(g_{1})>1/2$. In this case, $\text{MMS}(u,2)=1-u(g_{1})<1/2$, contradicting the assumption that $\text{MMS}(u,2)=1/2$.

Assume now that $\max\{u(g_{1}),u(g_{2})\}\leq 1/2$, and recall that $u(g)\leq 1/4$ for all $g\not\in\{g_{1},g_{2}\}$. Since $\text{MMS}(u,2)=1/2$, it suffices to find a connected bipartition such that both parts have value at least $3/8$. Let $S=\{g_{1}\}$, so $u(S)\leq 1/2$. We add one good at a time to $S$ following the bipolar ordering until $u(S)\geq 1/2$. Since $u(g_{2})\leq 1/2$, we stop (not necessarily directly) before we add $g_{2}$. Moreover, since each good besides $g_{1}$ and $g_{2}$ has value at most $1/4$, at some point during this process we must have $3/8\leq u(S)\leq 5/8$. In the bipartition with $S$ as one part, both parts are connected and have value at least $3/8$, completing the proof. ∎

Unlike for Theorem 3.1, the proof of Theorem 3.4 does not directly lead to a polynomial-time algorithm for computing an allocation such that both agents receive at least $3/4$ of their MMS. The problematic step is when we apply Lemma 3.2, since computing the MMS value is NP-hard by a straightforward reduction from the partition problem. Woeginger 1997 showed that a PTAS for the problem exists—using his PTAS, we can obtain a $(3/4-\epsilon)$-approximation algorithm that runs in polynomial time for any constant $\epsilon>0$. Nevertheless, we show in Appendix A that by building upon the proof of Theorem 3.4, we can also achieve a polynomial-time $3/4$-approximation algorithm.

In light of Theorems 3.1 and 3.4, it is tempting to believe that for graphs with connectivity $3$ or higher, the PoC is strictly less than $4/3$. Perhaps surprisingly, this is not the case: a counterexample is the wheel graph shown in Figure 2, which has connectivity $3$. In the instance shown in the figure, the MMS is $4$ while the G-MMS is $3$, so the PoC of the graph is at least $4/3$ (and by Theorem 3.4, exactly $4/3$). The key point of this example is that the graph cannot be partitioned into two connected subgraphs in such a way that one subgraph contains the vertices with value $1$ and $3$, while the other subgraph contains the two vertices with value $2$. This observation allows us to generalize the counterexample. A graph is said to be $2$-linked if for any two disjoint pairs of vertices $(a,b)$ and $(c,d)$, there exist two vertex-disjoint paths, one from $a$ to $b$ and the other from $c$ to $d$.

Let $G$ be a graph that is not $2$-linked. Then $\text{PoC}(G,2)\geq 4/3$.

Suppose that $G$ is not $2$-linked, and let $(a,b)$ and $(c,d)$ be disjoint pairs of vertices such that there do not exist two disjoint paths, one from $a$ to $b$ and the other from $c$ to $d$. Consider a utility function $u$ such that $u(a)=u(b)=2$, $u(c)=3$, $u(d)=1$, and $u(g)=0$ for every other vertex $g$. We have $\text{MMS}(u,2)=4$. On the other hand, the graph cannot be partitioned into two connected subgraphs in such a way that one subgraph contains $a$ and $b$ while the other subgraph contains $c$ and $d$—indeed, such a partition would give rise to two disjoint paths that cannot exist by our assumption. This means that $\text{G-MMS}(G,u,2)\leq 3$. Hence $\text{PoC}(G,2)\geq 4/3$. ∎

Every graph with connectivity at most $2$ is not $2$-linked, Indeed, given such a graph, let $a,b$ be two vertices whose removal disconnects the graph, and let $c,d$ be vertices from distinct components in the resulting graph. Then any path between $c$ and $d$ must go through either $a$ or $b$. and Figure 2 shows an example of a $3$-connected graph that also does not satisfy the property. In fact, Mészáros 2015 constructed a $5$-connected graph that still fails to be $2$-linked! On the other hand, a $6$-connected graph is always $2$-linked (Jung 1970). Combining these facts with Theorem 3.4 yields the following corollaries:

For every graph $G$ with connectivity $2$, $\text{PoC}(G,2)=4/3$.

For some graph $G$ with connectivity $5$, $\text{PoC}(G,2)=4/3$.

While we have not been able to precisely determine the PoC for all graphs with connectivity $3$ or above, we present a conjecture that, if settled in the affirmative, would complete the picture for the two-agent case. Before we can describe the conjecture, we need the following generalization of 2-linkedness (Mészáros 2015):

Given positive integers $a,b$, a graph $G$ is said to be $(a,b)$-linked if for any disjoint set of vertices $M_{1},M_{2}$ with $|M_{1}|=a$ and $|M_{2}|=b$, there exist disjoint connected subgraphs $G_{1},G_{2}$ of $G$ such that $M_{i}$ is contained in $G_{i}$ for $i=1,2$.

For example, $(2,1)$-linkedness is equivalent to biconnectivity, To see this, first consider a graph $G$ that is not biconnected—suppose that removing a vertex $x$ disconnects $G$. If $y$ and $z$ are vertices in different components of the resulting disconnected graph, then taking $M_{1}=\{y,z\}$ and $M_{2}=\{x\}$ yields a violation of Definition 3.8, meaning that $G$ is not $(2,1)$-linked. Conversely, suppose that $G$ is biconnected, and consider any disjoint set of vertices $M_{1}=\{y,z\}$ and $M_{2}=\{x\}$. By definition of biconnectivity, the graph $G$ remains connected upon the removal of $x$. Hence, we may take $G_{2}$ to be the subgraph induced only on $x$ and $G_{1}$ to be the subgraph induced on all vertices except $x$ in Definition 3.8. This implies that $G$ is $(2,1)$-linked. while $(2,2)$-linked graphs correspond to what we have so far called $2$-linked graphs. The new definition allows us to extend the lower bound from Proposition 3.5.

Let $k$ be a positive integer, and let $G$ be a graph that is not $(2,k)$-linked. Then $\text{PoC}(G,2)\geq 2k/(2k-1)$.

Suppose that $G$ is not $(2,k)$-linked, and let $\{a_{1},a_{2}\}$ and $\{b_{1},b_{2},\dots,b_{k}\}$ be sets of vertices for which there do not exist disjoint connected subgraphs separating them. Consider a utility function $u$ such that $u(a_{1})=u(a_{2})=k$, $u(b_{1})=k+1$, $u(b_{2})=u(b_{3})=\dots=u(b_{k})=1$, and $u(g)=0$ for every other vertex $g$. We have $\text{MMS}(u,2)=2k$. On the other hand, the graph cannot be partitioned into two connected subgraphs in such a way that one subgraph contains $a_{1},a_{2}$ while the other subgraph contains $b_{1},b_{2},\dots,b_{k}$. Since all vertex values are integers, this implies that $\text{G-MMS}(G,u,2)\leq 2k-1$. Hence $\text{PoC}(G,2)\geq 2k/(2k-1)$. ∎

Our conjecture is that for biconnected graphs, the PoC is exactly captured by $(2,k)$-linkedness:

Let $k\geq 2$ be an integer, and let $G$ be a graph that is $(2,k-1)$-linked but not $(2,k)$-linked. Then $\text{PoC}(G,2)=2k/(2k-1)$.

The case $k=2$ of Conjecture 3.10 holds by Corollary 3.6. We demonstrate next that the conjecture also holds for ‘almost-complete’ graphs, i.e., for complete graphs with a nonempty matching removed. These graphs have minimum degree $m-2$, where $m$ is the number of vertices (i.e., goods), and, with the exception of the graph $L_{5}$ that results from removing two disjoint edges from the complete graph $K_{5}$ (Figure 3), are $(2,m-3)$-linked but not $(2,m-2)$-linked. We show that the PoC of these graphs is always exactly $(2m-4)/(2m-5)$. The exceptional graph $L_{5}$ is not $2$-linked, so Proposition 3.5 (or alternatively, the utilities in Figure 3) implies that its PoC is at least $4/3$ instead of $6/5$. In fact, since the graph has connectivity $3$, Theorem 3.4 tells us that its PoC is exactly $4/3$, thereby again confirming Conjecture 3.10.

Let $G$ be a graph that results from removing a nonempty matching from a complete graph with at least three vertices, and assume that $G$ is different from $L_{5}$. Then $\text{PoC}(G,2)=(2m-4)/(2m-5)$.

To prove Theorem 3.11, we will use the following lemma.

Let $k$ be a positive integer, $2\leq s\leq 2k$ be a real number, and let $x_{1},x_{2},\dots,x_{k}\geq 1$ be real numbers with sum $s$. For any real number $0\leq r\leq s-2$, there exists a subset $J\subseteq\{1,2,\dots,k\}$ such that $r\leq\sum_{j\in J}x_{j}\leq r+2$.

We proceed by induction on $k$. For the base case $k=1$ we must have $s=2$, $x_{1}=2$, $r=0$, and the result holds trivially. Suppose now that the result holds for $k-1$; we will prove it for $k$. Assume without loss of generality that $x_{1}=\max\{x_{1},x_{2},\dots,x_{k}\}$.

First, assume that $x_{1}\leq 2$. Define $y_{i}:=x_{1}+x_{2}+\dots+x_{i}$ for each $i$. The sequence $0,y_{1},y_{2},\dots,y_{k}=s$ is strictly increasing and any two consecutive terms differ by at most $2$, so one of the terms $x_{1}+x_{2}+\dots+x_{i}$ must be between $r$ and $r+2$. Hence we may take $J=\{1,2,\dots,i\}$ to fulfill the claim.

Assume from now on that $x_{1}>2$. We first prove the statement for $r\geq s/2-1$. If $x_{1}>s/2+1$, then since $x_{i}\geq 1$ for all $i$, we have

thus $s>2k$, a contradiction. So $x_{1}\leq s/2+1\leq r+2$. If $x_{1}\geq r$, we are done by choosing $J=\{1\}$, so assume that $x_{1}<r$.

Let $t:=x_{2}+x_{3}+\dots+x_{k}$. Note that $0\leq t\leq s-2\leq 2(k-1)$ and $0<r-x_{1}\leq s-2-x_{1}=t-2$. Applying the induction hypothesis on $x_{2},x_{3},\dots,x_{k}$, we find that there is a set $L\subseteq\{2,3,\dots,k\}$ such that $r-x_{1}\leq\sum_{l\in L}x_{l}\leq r-x_{1}+2$. Take $J=L\cup\{1\}$. We have $r\leq\sum_{j\in J}x_{j}\leq r+2$, as desired.

so we know from the previous case ($r\geq s/2-1$) that there exists a subset $J\subseteq\{1,2,\dots,k\}$ for which $s-r-2\leq\sum_{j\in J}x_{j}\leq s-r$. Since $\sum_{j=1}^{k}x_{j}=s$, it follows that $r\leq\sum_{j\in\{1,2,\dots,k\}\setminus J}x_{j}\leq r+2$, completing the proof. ∎

We are now ready to establish Theorem 3.11.

First, we show that the PoC of $G$ is at least $(2m-4)/(2m-5)$. Let $(v_{1},v_{2})$ be a missing edge. Consider a utility function with value $m-2$ for each of $v_{1}$ and $v_{2}$, value $m-1$ for another vertex $v_{3}$, and value $1$ for each of the remaining $m-3$ vertices (so the total value is $4m-8$). The MMS is $2m-4$, attained by the bipartition with $\{v_{1},v_{2}\}$ as one part. Take an arbitrary connected bipartition. If $v_{1}$ and $v_{2}$ are in the same part, this part must contain at least one other vertex, so the other part has value at most $2m-5$. On the other hand, if $v_{1}$ and $v_{2}$ are in different parts, the part that does not contain $v_{3}$ has value at most $2m-5$. In either case, there is a part with value no more than $2m-5$, so the G-MMS is at most $2m-5$. It follows that the PoC is at least $(2m-4)/(2m-5)$.

Next, we show that the PoC of $G$ is at most $(2m-4)/(2m-5)$. Take an arbitrary utility function $u$, and assume without loss of generality that $u(M)=4m-8$. By Lemma 3.2, we may also assume that $\text{MMS}(u,2)=(4m-8)/2=2m-4$. It suffices to show that $\text{G-MMS}(G,u,2)\geq 2m-5$. Consider any MMS partition. If the partition is connected, we have that the G-MMS is $2m-4$. Suppose therefore that the partition is not connected. Since $G$ results from removing a nonempty matching from a complete graph, this means that (at least) one of the parts corresponds to a missing edge. Let $v_{1}$ and $v_{2}$ be the two vertices in that part (so $u(\{v_{1},v_{2}\})=2m-4$), and $v_{3},\dots,v_{m}$ be the remaining vertices of $G$.

Assume first that there exists a vertex $v\not\in\{v_{1},v_{2}\}$ such that $u(v)\leq 1$. We have $2m-4\leq u(\{v_{1},v_{2},v\})\leq 2m-3$, and the vertices $v_{1},v_{2},v$ form a connected subgraph. Moreover, since the graph $G$ is different from $L_{5}$, the remaining vertices also form a connected subgraph; together these vertices have value at least $(4m-8)-(2m-3)=2m-5$. Hence, in the connected bipartition with $\{v_{1},v_{2},v\}$ as one part, both parts have value at least $2m-5$. It follows that $\text{G-MMS}(G,u,2)\geq 2m-5$ in this case.

Assume now that every vertex $v\not\in\{v_{1},v_{2}\}$ satisfies $u(v)>1$. If $u(v_{1})\geq 2m-5$, then taking the connected bipartition with $v_{1}$ alone as one part again yields $\text{G-MMS}(G,u,2)\geq 2m-5$; an analogous argument applies if $u(v_{2})\geq 2m-5$. Suppose therefore that $\max\{u(v_{1}),u(v_{2})\}<2m-5$. Since $u(v_{1})+u(v_{2})=2m-4$, we have $1<u(v_{1})<2m-5$, and so $0<2m-5-u(v_{1})<2m-6$. Applying Lemma 3.12 with $k=m-2$, $s=2m-4$, $\{x_{1},\dots,x_{k}\}=\{u(v_{3}),\dots,u(v_{m})\}$, and $r=2m-5-u(v_{1})$, we find that there exists a subset of $\{u(v_{3}),\dots,u(v_{m})\}$ for which the sum of the elements belongs to the interval $[2m-5-u(v_{1}),2m-3-u(v_{1})]$. Letting $S$ be the set of corresponding goods along with $v_{1}$, we have $2m-5\leq u(S)\leq 2m-3$. Hence, in the connected bipartition with $S$ as one part, both parts have value at least $2m-5$. Therefore $\text{G-MMS}(G,u,2)\geq 2m-5$ in this case as well, and the proof is complete. ∎

One can check that any graph $G$ satisfying the condition of Theorem 3.11 is $(2,m-3)$-linked but not $(2,m-2)$-linked, so Theorem 3.11 confirms Conjecture 3.10 for this class of graphs.

2 Any Number of Agents

We proceed to the general setting where the goods are divided among an arbitrary number of agents. In this setting, it is no longer true that the PoC alone captures the MMS approximation that can be guaranteed to the agents—this is evident in the case of a complete graph, where the PoC is $1$ by definition, but an allocation that gives all agents their full MMS does not always exist (Kurokawa et al. 2018). At first glance, it may seem conceivable that certain graphs do not admit any useful MMS approximation. However, we provide a non-trivial guarantee for arbitrary graphs that depends only on the number of agents and goods and, in particular, not on the utilities (Theorem 3.14). We begin by establishing a general upper bound on the PoC.

For any graph $G$ and number of agents $n$, we have $\text{PoC}(G,n)\leq\max\{1,m-n+1\}$.

If $m<n$, the PoC is $1$. Assume that $m\geq n$, and consider an arbitrary utility function $u$. Let $(M_{1},\dots,M_{n})$ be a (not necessarily connected) partition of $M$ that maximizes $\min_{i=1,\dots,n}u(M_{i})$. We assume without loss of generality that $|M_{i}|\geq 1$ for each $i$, which also means that $|M_{i}|\leq m-n+1$ for every $i$.

For each $i$, let $g_{i}$ be a good of highest value in $M_{i}$ according to $u$, and let $M_{i}^{\prime}=\{g_{i}\}$. As long as $\cup_{i=1}^{n}M_{i}^{\prime}\neq M$, we add a good not already in $\cup_{i=1}^{n}M_{i}^{\prime}$ to one of the bundles $M_{i}^{\prime}$ so that the bundle remains connected; this is always possible since $G$ is connected. At the end of this process, $(M_{1}^{\prime},\dots,M_{n}^{\prime})$ is a connected partition of $M$. By our choice of $g_{i}$, we have

Hence, we have that $\text{PoC}(G,n)\leq m-n+1$. ∎

As we will see in Theorems 3.16 and 3.19, the bound $m-n+1$ is tight for sufficiently short paths and all stars. We now give a maximin share guarantee for arbitrary graphs.

For any graph $G$ and any number of agents $n$, if $m\geq n$, there exists a connected allocation that gives each agent at least $1/(m-n+1)$ of her MMS. On the other hand, if $m<n$, there exists a connected allocation that gives each agent her full MMS.

The statement for $m<n$ is trivial since the MMS is $0$ in that case, so assume that $m\geq n$. Take an arbitrary spanning tree $H$ of $G$. By Theorem 3.13, $\text{PoC}(H,n)\leq m-n+1$. By Proposition 2.3, there exists a connected allocation with respect to $H$ that gives each agent at least $1/(m-n+1)$ times her MMS. Since any connected allocation with respect to $H$ is also connected with respect to $G$, the conclusion follows. ∎

Next, we derive tight bounds on the PoC in the cases of paths and stars for any number of agents. By Proposition 2.3, this also yields the optimal MMS approximation for each of these cases. The following simple fact will be useful:

Let $m\geq n$, and let $M^{\prime}\subseteq M$ be an arbitrary set of at least $m-n+1$ goods. For an agent with utility function $u$, we have $u(M^{\prime})\geq\text{MMS}(u,n)$.

Observe that in any partition of the vertices into $n$ parts, at least one of the parts is contained in $M^{\prime}$. In particular, this holds for an MMS partition. It follows that $\text{MMS}(u,n)\leq u(M^{\prime})$, as claimed. ∎

Let $n\geq 2$ and let $G$ be a star. Then

Moreover, when $m\geq n$, there exists a polynomial-time algorithm that computes a connected allocation in which every agent receives at least $1/(m-n+1)$ of her MMS.

If $m<n$ the PoC is $1$, so assume that $m\geq n$. We first show that the PoC is at least $m-n+1$. Consider a utility function $u$ with value $m-n+1$ for the center vertex and for $n-2$ of the leaves, and value $1$ for each of the remaining $m-n+1$ leaves. We have $\text{MMS}(u,n)=m-n+1$. In any connected partition into $n$ parts, at least $n-1$ parts contain a single leaf. This means that at least one of these parts contains a single leaf with value $1$. Hence the PoC is at least $m-n+1$.

Next, we show that the PoC is at most $m-n+1$; while this bound already follows from Theorem 3.13, our proof will yield a polynomial-time algorithm for computing a desirable connected allocation in the case of stars. Take an arbitrary utility function $u$, let $v^{*}$ be the center vertex, and let $v_{1},v_{2},\dots,v_{n-1}$ be the leaves with the highest value where $u(v_{1})\geq\dots\geq u(v_{n-1})$. Consider a connected partition $\Pi$ with each of these $n-1$ vertices as a part, and the remaining $m-n+1$ vertices as the last part.

Let $A:=M\setminus\{v^{*},v_{1},\dots,v_{n-2}\}$. By Lemma 3.15, $\text{MMS}(u,n)\leq u(A)$. Since there are $m-n+1$ vertices in $A$ and $v_{n-1}$ is a vertex with the highest value, we have

It follows that $u(v_{i})\geq\text{MMS}(u,n)/(m-n+1)$ for all $i=1,2,\dots,n-1$, so the first $n-1$ parts of $\Pi$ have value at least $\text{MMS}(u,n)/(m-n+1)$ each. The last part of $\Pi$ is $B:=M\setminus\{v_{1},v_{2},\dots,v_{n-1}\}$. By Lemma 3.15 again, we have $\text{MMS}(u,n)\leq u(B)$. This means that all parts of $\Pi$ have value at least $\text{MMS}(u,n)/(m-n+1)$, as desired.

This proof also gives rise to a polynomial-time algorithm for computing a connected allocation for $n$ agents on a star such that each agent receives at least $1/(m-n+1)$ of her MMS: Let each of the first $n-1$ agents pick a favorite leaf from the remaining leaves in turn, and let the last agent take the remaining $m-n+1$ vertices. ∎

To address the more involved case of paths, we introduce an approximation of proportionality that can be of interest even in the absence of connectivity considerations. Recall that an allocation is said to be proportional if it gives every agent at least her proportional share, which is defined as $u(M)/n$. Even though a proportional allocation always exists for divisible goods, as we explained in the introduction, this is not the case for indivisible goods—our definition of indivisible proportional share therefore adapts proportionality to the setting of indivisible goods. In order to ensure a nontrivial approximation, we will need to hypothetically remove up to $n-1$ goods from the entire bundle. Indeed, when there are $n-1$ goods overall, in any allocation, one of the agents is necessarily left empty-handed. If this agent is only allowed to hypothetically remove at most $n-2$ goods, then she cannot guarantee any positive (multiplicative) approximation of her utility for the entire bundle. Thus, we are interested in the optimal approximation of each agent’s utility after $n-1$ goods are removed. When the number of goods is large, this approximation is $1/n$, which is reasonable because there are $n$ agents. However, for smaller numbers of goods, we will be able to achieve a better approximation, which is captured by our IPS factor in the following definition.

Given $n$ agents and $m$ goods, a bundle $A$ is said to satisfy the indivisible proportional share (IPS) property for an agent with utility function $u$ if there exists a (possibly empty) set $B\subseteq M\setminus A$ with $|B|\leq n-1$ such that

An allocation is said to satisfy the IPS property if every agent receives a bundle that satisfies the IPS property. For brevity, we will refer to a bundle or allocation that satisfies the IPS property as being IPS.

We remark that IPS is a stronger property than PROP${}^{*}(n-1)$ considered by Segal-Halevi and Suksompong 2019, which corresponds to taking $\text{IPS}(n,m)=1/n$ for $m\geq n$ and $0$ for $m<n$. (In particular, note that $\frac{1}{m-n+1}>\frac{1}{n}$ when $n\leq m<2n-1$.) It is also stronger than PROP1 considered by Conitzer et al. 2017 and Aziz et al. 2022, as well as a proportionality relaxation studied by Suksompong 2019. Despite its strength, we show that an IPS allocation always exists. Moreover, we can obtain a connected IPS allocation if the graph is a path.

Let $n\geq 2$ and let $G$ be a path. There exists a connected IPS allocation of the $m$ goods to the $n$ agents.

If $m<n$, each agent needs utility $0$ in an IPS allocation, so the claim holds trivially. Assume that $m\geq n$. Starting with an empty bundle, we process the goods along the path (say, from left to right) and add them one at a time to the current bundle until the bundle is IPS to at least one of the agents. We then allocate the bundle to one such agent, and repeat the procedure with the remaining goods and agents. Any leftover goods are allocated to the agent who receives the last bundle.

We claim that this procedure always results in an IPS allocation. Notice from Definition 3.17 that if a bundle is IPS for an agent, then so is any superset of the bundle. Hence it suffices to show that after $n-1$ bundles are allocated, the last agent still finds the remaining bundle to be IPS. Assume without loss of generality that the bundles are allocated to agents $1,2,\dots,n$ in this order, and let $u$ be the utility function of agent $n$. The claim holds trivially if the empty bundle is IPS for agent $n$, so assume that it is not. For $1\leq i\leq n-1$, let the bundle allocated to agent $i$ be $M_{i}=X_{i}\cup Y_{i}$, where $Y_{i}$ consists of the last good added to $M_{i}$ (if $M_{i}$ is nonempty), and $X_{i}$ consists of the remaining goods. Let $X=\cup_{i=1}^{n-1}X_{i}$ and $Y=\cup_{i=1}^{n-1}Y_{i}$. In particular, $|Y|\leq n-1$.

Let $M_{n}$ be the bundle allocated to agent $n$.

Case 1: $m\geq 2n-1$. By definition of the procedure, agent $n$ does not find any of the bundles $X_{1},\dots,X_{n-1}$ to be IPS. In particular, noting that $Y\subseteq M\setminus X_{i}$ for each $1\leq i\leq n-1$ and taking $B=Y$ in Definition 3.17, we have $u(X_{i})<\text{IPS}(n,m)\cdot u(M\setminus Y)=u(M\setminus Y)/n$ for all $i$. Hence,

Since $Y\subseteq M\setminus M_{n}$, bundle $M_{n}$ is IPS for agent $n$.

Case 2: $n\leq m\leq 2n-1$. First, we show that at most $m-n$ of the first $n-1$ agents can receive at least two goods. Assume for contradiction that at least $m-n+1$ of these agents receive at least two goods, and suppose that the first $m-n+1$ of them are agents $a_{1},\dots,a_{m-n+1}$ in this order. Let $j$ be the first good in agent $a_{m-n+1}$’s bundle. We claim that the bundle consisting of good $j$ alone is IPS for agent $n$; this is sufficient for the desired contradiction because agent $n$ should have taken this bundle ahead of agent $a_{m-n+1}$.

Before agent $a_{m-n+1}$ receives her bundle, the goods in $X$ allocated to earlier agents are precisely those in the set $X^{\prime}:=\cup_{i=1}^{m-n}X_{a_{i}}$. Let $Z=M\setminus(X^{\prime}\cup\{j\})$. Since $|X^{\prime}|\geq m-n$, we have $|Z|\leq m-(m-n)-1=n-1$. By definition of the procedure, agent $n$ does not find any of the bundles $X_{a_{1}},\dots,X_{a_{m-n}}$ to be IPS. In particular, noting that $Z\subseteq M\setminus X_{a_{i}}$ and taking $B=Z$ in Definition 3.17, we have $u(X_{a_{i}})<u(M\setminus Z)/(m-n+1)$ for all $1\leq i\leq m-n$. Hence,