Welfare Loss in Connected Resource Allocation

1 Introduction

The allocation of indivisible goods among interested agents with heterogeneous preferences is a fundamental problem in society. Taking a utilitarian standpoint, allocating each item to an agent with the highest utility for the item, though economically efficient, can lead to unfair allocations where some agents may have little or no utility for their bundle. To address this issue, the study of fair division focuses on allocating resources in a manner that is fair, and possibly ideal in terms of other desirable properties. The concept of fairness can either be represented in the form of axioms which enforce certain fairness criteria, or in our case, as an egalitarian objective reflecting the utility obtained by the worst-off agent.

In the real world, there may be constraints on the range of feasible allocations, such as budget or cardinality constraints; see the survey by Suksompong [2021] for a detailed overview. Our paper studies the important constraint of connectivity initially proposed by Bouveret et al. [2017], in which each good corresponds to a vertex of a pre-defined graph, and each agent's bundle of items must form a connected subgraph. Under this constraint, we are interested in quantitative measures of fairness and efficiency, and we specifically address the following research question:

When allocating connected subsets of items, what is the worst-case degradation of social welfare resulting from the constraint of connectivity?

Answers to this question may help central decision makers decide whether the loss of welfare from imposing connectivity constraints outweighs the benefits of having connected allocations. For example, when allocating offices or desks among different research groups, it may be desirable for each research group to receive a connected set of offices/desks, and when partitioning players into sports teams, we may want to require that each player knows at least one other player on the same team. Enforcing connected allocations in these scenarios may provide collaborative benefits at the cost of social welfare. Our model and results can also be applied to multirobot task allocation. In this scenario, robots (items) are to be partitioned into fleets (bundles) which will be assigned to tasks (agents), and an edge between two robots in the graph indicates that they are able to directly communicate with each other. Imposing a connectivity constraint allows for the fleets of robots to be decentralized, without the need of a central server for communication, but this comes at the cost of welfare loss, which our findings help to quantify. Even when connected allocations are mandatory and the central decision maker cannot choose to neglect them, it is still interesting to know how much welfare loss is incurred from the constraint.

Specifically, we quantify the loss of fairness and efficiency, corresponding to two well-studied social welfare functions: the egalitarian welfare, defined as the utility of the worst-off agent, and the , which is the sum of the

agents' utilities. To illustrate our key concepts, consider the instance in Figure 1. Here, the optimal egalitarian and utilitarian welfares are 0.8 and 1.7, respectively, both achieved by giving each item to the agent that values it most. However, the optimal egalitarian welfare among all connected outcomes is 0.5, with agent 2's egalitarian allocation inside the blue ellipse, and the optimal connected utilitarian welfare is 1.4, with agent 2's utilitarian allocation inside the red dashed shape. Thus, due to the connectivity constraint, the optimal egalitarian welfare decreases by a factor of 0.8/0.5 = 1.6, and the optimal utilitarian welfare decreases by a factor of 1.7/1.4 ≈ 1.21. This is because the top left and bottom left items are not directly connected, so to give agent 1 both items in a connected allocation, we must also give her the top right item, which she does not value.

1.1 Our Results

In this paper, we investigate the potential loss of welfare when a connectivity constraint is imposed on the allocations. To this end, we introduce the concept of egalitarian (resp., utilitarian) price of connectivity (PoC) of a graph, which is the worst-case ratio between the optimal egalitarian (resp., utilitarian) welfare from any (possibly disconnected) allocation, and the optimal egalitarian (resp., utilitarian) welfare from a connected allocation, over all possible utility profiles.

We prove tight or asymptotically tight bounds on the price of connectivity for various classes of graphs. Intuitively, a more "connected" graph should have a lower price of connectivity, with a complete graph having an egalitarian/utilitarian PoC of 1. However, in the case of two agents, our results for complete graphs with a non-empty matching removed show that the egalitarian and utilitarian prices of connectivity are strictly higher than 1 even when only one edge is removed. Furthermore, with the exception of the 5-item case, the price of connectivity does not increase further when more disjoint edges are removed. We also supplement this result in the twoagent case with results for another dense class of graphs, that is, complete bipartite graphs. Interestingly, we find that if one side of the graph has two vertices, the utilitarian PoC is a constant, regardless of how many vertices the other side has.

We also consider graphs with low connectivity, finding the egalitarian PoC in the two-agent case for the broad classes of graphs with connectivity 1, including all trees, and graphs with connectivity 2. Although the PoC for graphs with connectivity 1 is lower bounded by the maximum number of disjoint connected subgraphs resulting from the removal of a vertex, the PoC for graphs with connectivity 2 is simply a constant. We also extend to the three-agent case, finding the egalitarian PoC for trees. These results come with algorithms for finding an allocation which guarantees a welfare corresponding to the price of connectivity. Similarly, in the two-agent case, we find the exact utilitarian PoC for trees and cycles. Unlike in the egalitarian case, the utilitarian PoC for trees does not depend on the maximum degree of the graph. Finally, we give results on stars, paths and cycles for any number of agents, which are summarized in Table 1.

Section 3 gives the egalitarian PoC bounds, while Section 4 presents the utilitarian PoC results.

1.2 RelatedWork

The mathematically rigorous treatment of fair division dates back to the work of Steinhaus [1948] on allocating divisible resources, and has attracted considerable attention since then [Brams and Taylor, 1996; Moulin, 2003; Thomson, 2016], with a growing interest in the allocation of indivisible goods in recent years [Amanatidis et al., 2023].

The connectivity constraint has been studied by many authors [Bouveret et al., 2017; Suksompong, 2019; Lonc and Truszczynski, 2020; Bei et al., 2022; Bil`o et al., 2022; Caragiannis et al., 2022; Igarashi, 2023; Lonc, 2023], with several of them addressing graphs such as paths, cycles, stars, etc. that we consider in this work. These authors have mostly focused on the existence, approximation and computational complexity of fair, connected allocations. One exception is the work by Igarashi and Peters [2019], who studied the problem of finding a connected allocation that is Pareto optimal.

The term "price of connectivity (PoC)" was introduced in the work by Bei et al. [2022], and measures the price in terms of a fairness notion called maximin share. More precisely, these authors defined the PoC as the worst-case ratio between the maximin share taken over all possible partitions of the items into n parts and the maximin share taken over all connected partitions into n parts. Note that their PoC is only defined with respect to the maximin share of one agent, whilst we define it with respect to the optimal welfare, and thus our definitions involve utilities of all of the agents. When translated to our setting, the (maximin share) PoC results by Bei et al. [2022] imply egalitarian PoC results for identical agents.

The price of connectivity concept is similar in spirit to the price of fairness [Bertsimas et al., 2011; Caragiannis et al., 2012], which captures the worst-case welfare loss resulting from fairness constraints. The price of fairness has been widely studied in various fair division settings [Suksompong, 2019; Barman et al., 2020; Bei et al., 2021; Celine et al., 2023; Li et al., 2024]. While these papers typically measure the loss of utilitarian welfare from fairness constraints, part of our work treats fairness as a welfare objective, measuring the loss of egalitarian welfare from connectivity constraints.

2 Preliminaries

For any positive integer t, let [t] := {1, 2, . . . , t}. Denote by N = [n] the set of n agents and M the set of m indivisible 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, items and vertices interchangeably. Each agent i ∈ N has a non-negative utility ui(g) for each good g ∈ M. We assume that utilities are additive, i.e., ui(M ′ ) = ∑g∈M′ ui(g) for all i ∈ N and M ′ ⊆ M, as well as normalized, that is, ui(M) = 1 for all i ∈ N. Denote by U = (u1, u2, . . . , un) the utility profile of the agents. We refer to a setting with the agents N, the goods M and their underlying graph G, and the utility profile U as an instance, denoted as I = ⟨N, G, U⟩.

A bundle is a subset of goods, and is called connected if the goods in the bundle form a connected subgraph of G. An allocationM= (M1,M2, . . . ,Mn) is a partition of the goods in M into n bundles such that agent i ∈ N receives bundle Mi. Moreover, an allocation or a partition is connected if all of its bundles are connected. Denote by C(I) the set of all connected allocations for instance I.

In this paper, we quantify the worst-case egalitarian and utilitarian welfare loss incurred when imposing that each agent must receive a connected bundle. Given an instance I and an allocationM= (M1,M2, . . . ,Mn) of the instance,

• the egalitarian welfare ofM, denoted as SW-egal(M), is the minimum among the agents' utilities; that is, SW-egal(M) :=mini∈N ui(Mi);
• the utilitarian welfare ofM, denoted as SW-util(M), is the sum of the agents' utilities; that is, SW-util(M) := ∑i∈N ui(Mi).

The optimal egalitarian (resp., utilitarian) welfare of instance I, denoted by OPT-egal(I) (resp., OPT-util(I)), is the maximum egalitarian (resp., utilitarian) welfare over all possible allocations of the instance.

2.1 Egalitarian / Utilitarian Price of Connectivity

We now proceed to define the central concept of the paperthe price of connectivity (PoC)-which captures the largest multiplicative gap between the optimal welfare among all allocations and that among all connected allocations.

Definition 2.1 (Egal-PoC). Given a graph G and the number of agents n, the egalitarian price of connectivity (egalitarian PoC) for G is defined as 1

where the supremum is taken over all possible instances.

The utilitarian price of connectivity is similarly defined by replacing OPT-egal with OPT-util and SW-egal with SW-util.

1 We interpret 00 in this context to be equal to 1. Note that OPT-egal(I) = 0 if and only if maxM∈C(I) SW-egal(M) = 0, because both conditions are equivalent to the condition that there does not exist an allocation where each agent attains positive utility.

3 Egalitarian Price of Connectivity

In this section, we investigate the loss of egalitarian welfare due to the connectivity constraint. Firstly, we remark that given any graph G, if m < n, then its optimal egalitarian welfare is always 0 and thus Egal-PoC(G, n) = 1. We therefore assume that m ≥ n for the rest of this section.

We start by establishing a general upper bound on the egalitarian PoC for any graph G. The intuition behind the bound is that for any instance I, by giving every agent their most preferred item from an optimal egalitarian allocation of the instance, each agent receives a utility of at least OPT-egal(I) m-n+1 . This is because each bundle in an optimal egalitarian allocation has at most m - n + 1 goods.

The proof of this lemma, along with all other omitted proofs, can be found in the full version of our paper [Bei et al., 2024]. We next introduce a reduction technique used in this section in order to simplify our proof for the upper bound on the egalitarian PoC for various graphs. Given any graph G, denote by IG the set of instances such that each vertex in G is positively valued by at most one agent. Note that we do not assume that the agents' utilities are normalized in IG.

Lemma 3.2. Let G be a graph and β ∈ (0, 1]. Suppose that for every instance ̂ I ∈ IG, there exists a connected allocation ̂ M such that SW-egal(̂ M) ≥ β · OPT-egal(̂ I). Then, Egal-PoC(G, n) ≤ 1/β.

Lemma 3.2 suggests that when proving upper bounds on the egalitarian PoC, it suffices to focus only on the instances in which each vertex is valued by at most one agent. The reduction, however, does not run in polynomial time because it requires an allocation that maximizes egalitarian welfare, which is known to be NP-hard even for 2 agents. Our algorithms in this section take reduced instances as their input. If we are given an optimal egalitarian allocation, such as by some oracle, then our algorithms run in polynomial time, as their general structure involves moving down a rooted subtree. We may also use a polynomial-time approximation algorithm (e.g., [Bez´akov´a and Dani, 2005; Asadpour and Saberi, 2010]) to create the reduced input instance and achieve a corresponding approximate solution.

3.1 Two Agents

We begin with the case of two agents, addressing a dense class of graphs. Although a complete graph has an egalitarian price of connectivity of 1, we find that even when only one edge is removed from it, the egalitarian PoC becomes strictly higher than 1, meaning that there exists some instance where the optimal egalitarian welfare cannot be achieved by a connected allocation. However, with the exception of the 5-item case, the egalitarian PoC does not increase as more disjoint edges are removed from the graph. Let Km denote the complete graph with m vertices.

Theorem 3.3. Let G be a complete graph with a non-empty matching removed. Then, Egal-PoC(G, 2) = 2 if G is

• K3 with an edge removed, or
• L5, which is K5 with two disjoint edges removed,

Following this, we address another class of dense graphs, complete bipartite graphs, where we find that the egalitarian PoC depends on the number of vertices on the smaller side of the graph.

Theorem 3.4. Let G be a complete bipartite graph with x vertices on the smaller side. Then,

We remark that the class of complete graphs with a matching removed can be represented by a complete k-partite graph Kn1,n2,...,nk where n1, . . . , nk ∈ {1, 2}: vertices are partitioned into k independent sets of size 1 or 2, and there is an edge between every pair of vertices from different independent sets [Chartrand and Zhang, 2020, p. 42]. This class forms a special case of the Tur´an graphs [Bollob´as, 1998, p. 108], but is more general than the cocktail-party graphs [Biggs, 1993, p. 17].

We now give results for graphs classified by vertex connectivity (sometimes referred to simply as connectivity). A graph has connectivity k if there exist k vertices whose removal results in the graph being disconnected and k is the smallest number with this property. We begin with graphs with connectivity 2. We first prove a useful lemma, which states that if a graph admits a bipolar ordering, 2 its egalitarian PoC is at most 2. The proof of the lemma gives an algorithm for finding a connected allocation which guarantees at least half of the optimal egalitarian welfare.

Lemma 3.5. Suppose that G admits a bipolar ordering. Then, Egal-PoC(G, 2) ≤ 2.

Proof. By Lemma 3.2, it suffices to consider the case where each item is positively valued by at most one agent. Take the bipolar ordering of the graph vertices, and starting from vertex 1, iteratively build a subgraph in ascending order of bipolar number until some agent i values it at least ui(G)/2. Give the subgraph to agent i and the remaining subgraph to the other agent j. Since each vertex is valued by at most one agent, agent i's subgraph must be worth less than uj(G)/2 utility to agent j; otherwise agent j would have received it earlier. Therefore agent j receives more than uj(G)/2 utility from its subgraph. Since every vertex assigned with a number i ∈ {2, . . . ,m-1} is adjacent to a vertex with a higher number and a vertex with a lower number, we see that agent i's subgraph, which consists of vertices numbered 1, . . . , k for some k, is connected. Similarly, agent j's subgraph, which consists of vertices k + 1, . . . ,m is also connected. Both agents receive at least half of their total utility for the graph, which means that the egalitarian price of connectivity is at most 2.

We now show the egalitarian PoC for graphs with connectivity 2.

2 A bipolar ordering of a graph G = (V, E) is a one-to-one assignment of the integers 1, . . . ,m to V such that every vertex assigned with a number i ∈ {2, . . . ,m- 1} is adjacent to a vertex with a higher number and a vertex with a lower number.

Theorem 3.6. Let G be a graph with connectivity 2. Then, Egal-PoC(G, 2) = 2.

Proof. We first show that if a graph is not 2-linked, 3 its egalitarian PoC is at least 2.

Lemma 3.7. Let G be a graph that is not 2-linked. Then, Egal-PoC(G, 2) ≥ 2.

A graph with connectivity 2 is not 2-linked, 4 and therefore by Lemma 3.7, has an egalitarian PoC of at least 2. Such a graph has a bipolar ordering [Maon et al., 1986], so the upper bound follows from Lemma 3.5.

Next, we consider the large class of graphs with connectivity 1, which includes tree graphs. We find that the upper bound depends on the maximum number of disjoint connected subgraphs when a single vertex is removed, and interestingly, the PoC may be lower if the block decomposition of the graph is a path. A block is a maximal subgraph with connectivity at least 2 of a graph, and a cut vertex is a vertex whose removal disconnects a graph. The block decomposition of a graph G is a bipartite graph with all blocks of G on one side and all cut vertices of G on the other side. There is an edge between a block and a cut vertex in the bipartite graph if and only if the cut vertex belongs to the block in G. For any connected graph G, the block decomposition of G is a tree [Bondy and Murty, 2008].

Theorem 3.8. Let G be a graph with connectivity 1. Denote by d the maximum number of connected subgraphs after a vertex has been removed from G. When d = 2, Egal-PoC(G, 2) = 2 if the block decomposition of G is a path, and Egal-PoC(G, 2) = 3 otherwise. When d ≥ 3, Egal-PoC(G, 2) = d.

Proof. We provide the upper bound proof here.

Upper Bound. If d = 2 and the block decomposition of G forms a path, then G has a bipolar ordering [Bil`o et al., 2022], and therefore by Lemma 3.5, G has an egalitarian PoC of at most 2. It remains to prove the theorem for the cases where d = 2 and the block decomposition of G does not form a path, and where d ≥ 3. In particular, we show that Egal-PoC(G, 2) ≤ max{d, 3}. By Lemma 3.2, it suffices to consider the case where each item in a given instance I is positively valued by at most one agent, meaning that OPT-egal(I) = mini∈[2] ui(G). Let γ = max{d, 3}. To show that Egal-PoC(G, 2) ≤ γ, we give an algorithm which produces a subtree T ′ of G such that T ′ is worth at least ui(G) γ to some agent i, and G \ T ′ is connected and worth at least uj (G) γ to the other agent j. The pseudocode can be found in Algorithm 1.

We now demonstrate the correctness of the algorithm. Firstly, when merging subtrees in lines 3 and 12, we remove Algorithm 1: Allocating a Graph with Connectivity 1 for Two Agents

3 A graph is 2-linked if for any disjoint pairs of vertices (a, b) and (c, d), there exist two disjoint connected subgraphs G1 and G2 of G where a, b ∈ G1 and c, d ∈ G2.

4 This can be seen by letting a and b be the vertices which, when removed fromG, result in at least two disjoint connected subgraphs G1, G2, . . . , and by taking vertices c ∈ G1 and d ∈ G2.

• Input: An instance I = ⟨[2], G, U⟩. (Each vertex in G
• is valued positively by at most one agent.) 1 γ ← max{d, 3}, where d is the maximum number of connected subgraphs after a vertex is removed. 2 Take arbitrary rooted spanning tree T of G. 3 while all subtrees of T are worth less than ui(G)/γ for all i ∈ [2] do 4 Take two subtrees of T which are connected by an edge in G, and merge them into one connected subtree with that edge. 5 Take subtree T ′ of T where ui(T ′ ) ≥ ui(G)/γ for some agent i. 6 while there exists a subtree of T ′ worth at least ui(G)/γ to some agent i do 7 Set T ′ to be such a further subtree. 8 if ui(T ′ ) ≥ ui(G) γ for some i and uj(G\ T ′ ) ≥ uj(G) γ for the other agent j then 9 return T ′ for agent i and G\T ′ for agent j 10 else 11 Root the original spanning tree T at the root of T ′ . 12 while all subtrees of T are worth less than ui(G)/γ for all i ∈ [2] do 13 Take two subtrees of T which are connected by an edge in G, and merge them into one connected subtree with that edge. 14 Take subtree T ′ of T where ui(T ′ ) ≥ ui(G)/γ for some agent i. 15 return T ′ for agent i and G\T ′ for the other agent j

the edge connecting one of the constituent subtrees to the root of the tree, to prevent any cycles from being created. The while-loop in line 3 eventually terminates, because after all subtrees are merged where possible, there will be at most d subtrees, where d ≤ γ by the definition of γ. Therefore in line 5, we know such a subtree must exist because the root of T is positively valued by at most one agent. If the algorithm terminates in line 9, the condition requires that T ′ and G \ T ′ meet the utility requirements, and we know they are both connected because T ′ is a subtree of the spanning tree T .

If the algorithm did not terminate in line 9, then u1(T ′ ) ≥ u1(G) γ and u2(T ′ ) ≥ u2(G) γ . This is because if ui(T ′ ) ≥ ui(G) γ for some agent i and uj(T ′ ) < uj(G) γ for the other agent j, then uj(T \ T ′ ) > uj(G)(1 - 1 γ ) ≥ uj(G) γ . Furthermore, all subtrees of T ′ are worth strictly lower than u1(G) γ to agent 1 and strictly lower than u2(G) γ to agent 2, as otherwise we would have set T ′ to be a further subtree in line 7. Finally, we know that u1(T \ T ′ ) < u1(G) γ and u2(T \ T ′ ) < u2(G) γ , as otherwise we would have been able to allocate T \ T ′ to one agent and T ′ to another agent in line 9.

When the original spanning tree T is re-rooted in line 11, T \ T ′ becomes a subtree of T, and the other subtrees of T are the same as the 'further subtrees' of T ′ which are worth strictly lower than u1(G) γ to agent 1 and strictly lower than u2(G) γ to agent 2. As previously explained, the while-loop in line 12 eventually terminates, so in line 14, ui(T ′ ) ≥ ui(G) γ for some agent i and uj(T ′ ) < 2uj(G) γ for the other agent j. This is because the two subtrees forming T ′ were worth less than u1(G) γ to agent 1 and less than u2(G) γ to agent 2 before merging. Hence, it follows that uj(T \T ′ ) > uj(G)(1- 2 γ ) ≥ uj (G) γ .

While we have given results for classes of dense and sparse graphs, it remains an intriguing question to give a complete characterization of the egalitarian price of connectivity in the 2-agent case. Even when agents have identical valuations, the egalitarian PoC for 2 agents is still unknown, as seen in Conjecture 3.10 of Bei et al. [2022]. Settling their conjecture could be a crucial step towards a complete characterization in our setting where agents have heterogeneous valuations.

3.2 Three Agents

Our main result in this subsection shows that when there are three agents, the egalitarian price of connectivity for a tree graph is equal to the maximum number of disjoint connected subgraphs when two vertices are removed, denoted by δ.

Theorem 3.9. Let G be a tree. Then, Egal-PoC(G, 3) = δ, where δ is the maximum number of disjoint connected subgraphs when two vertices are removed from G.

We first show that δ depends on the degrees of the two highest degree vertices, whose degrees we denote by ∆1(G) and ∆2(G), as well as whether these two vertices are adjacent to each other. In case of ties, we favor non-adjacent highest degree vertices.

Lemma 3.10. Let G be a tree. Then, δ = ∆1(G)+∆2(G)-1 if there exist two non-adjacent highest degree vertices, and δ = ∆1(G) + ∆2(G) - 2 otherwise.

We now prove the main result for this subsection.

Proof of Theorem 3.9. A tree with 3 or 4 vertices must be a path or a star, which will be covered in Theorem 3.12 (for stars) and Theorem 3.13 (for paths). We therefore assume that the tree has at least 5 vertices and is not a star, so that δ ≥ 3 and ∆2(G) ≥ 2. Let v1 and v2 denote the vertices with degrees ∆1(G) and ∆2(G) whose removal results in δ disjoint connected subgraphs.

Lower Bound. Let agents 1 and 2 have utility 1 for v1 and v2 respectively, and let agent 3 have utility 1/δ for each of the disjoint connected subgraphs resulting from the removal of v1 and v2. It can be verified that (i) the optimal egalitarian welfare of the instance is 1, and (ii) the optimal egalitarian welfare of a connected allocation is 1/δ, achieved by giving agents 1 and 2 vertices v1 and v2, respectively, and giving agent 3 one of the disjoint connected subgraphs. This shows that Egal-PoC(G, 2) ≥ δ.

Algorithm 2: A Subroutine of Tree Allocation for Three Agents in Case 1

Input: An instance I = ⟨[3], G, U⟩. (Each vertex in G

is valued positively by at most one agent.) 1 Root the tree at v1, the vertex with degree ∆1(G). 2 δ ←∆1(G) +∆2(G) -1 3 Take subtree T ′ of G where ui(T ′ ) ≥ ui(G)/δ for some agent i. 4 while there exists a branch T ′′ of T ′ such that for some i ∈ [3], ui(T ′′ ) ≥ ui(G) δ do 5 T ′ ← T ′′ 6 return T ′

Upper Bound. By Lemma 3.2, it suffices to consider instances where each vertex is positively valued by at most one agent, so we have OPT-egal(I) = mini∈[3] ui(G). We prove the upper bound by designing algorithms which, at a high level, find a subtree T ′ of G such that ui(T ′ ) ≥ ui(G)/δ for some agent i and such that the remaining subtree G \ T ′ is sufficiently valued and can be divided between the other two agents. We split the algorithm and proof into two cases depending on whether δ = ∆1(G) + ∆2(G) - 1 or δ = ∆1(G) + ∆2(G) - 2. Here, we present the full proof for Case 1 where δ = ∆1(G) + ∆2(G) - 1.

We start with a lemma which shows that if we can take a subtree T ′ fromG such that:

• T ′ is worth at least ui(G)/δ to some agent i, and
• T ′ is worth at most ∆2(G)-1 δ · uj(G) to all agents j ̸= i; in other words, uj(T ∗ := G \ T ′ ) ≥ ∆1(G) δ · uj(G),

then we can allocate T ′ to agent i and divide G \ T ′ between the remaining agents [3] \ {i} to complete a connected allocation.

Lemma 3.11. Let T ∗ be a subtree of G such that two agents i and j value T ∗ at least ∆1(G) δ · ui(G) and ∆1(G) δ · uj(G), respectively. Then, T ∗ can be divided between the two agents so that each agent receives a connected bundle worth at least ui(G)/δ and uj(G)/δ, respectively.

We now prove the correctness of Algorithm 2 which, given a tree G, finds such a subtree T ′ . Firstly, the subtree found in line 3 always exists because v1 can only be positively valued by at most one agent, and δ ≥ ∆1(G). This means that T ′ ̸= ∅ before executing the while-loop. By the design of Algorithm 2, when the while-loop terminates and the algorithm returns T ′ , ui(T ′ ) ≥ ui(G) δ for some i ∈ [3]. It remains to show that uj(T ′ ) ≤ ∆2(G)-1 δ · uj(G) for all j ∈ [3] \ {i}. Since the while-condition is evaluated as false for T ′ , for any branch T ′′ of T ′ and any i ∈ [3], ui(T ′′ ) < ui(G) δ . Suppose the root of T ′ is vertex v. As T ′ has at most ∆2(G) - 1 branches, for all i ∈ [3], ui(T ′ \ {v}) < ∆2(G)-1 δ · ui(G). If ui(v) = 0 for all i ∈ [3], meaning that ui(T ′ ) = ui(T ′ \ {v}) < ∆2(G)-1 δ · ui(G) for all i ∈ [3], then T ′ is as desired. Otherwise, denote by i∗

Algorithm 3: Discretized Moving-Knife: Path Allocation for n Agents

Input: An instance I = ⟨N, G, U⟩. (Each vertex in G is valued by at most one agent.)

• update M accordingly.
• 8 return A connected allocationM.

the agent with ui∗(v) > 0; note that the other two agents value vertex v at 0. If ui∗(T ′ ) ≥ ui∗(G) δ , then uj(T ′ ) = uj(T ′ \ {v}) < ∆2(G)-1 δ · ui(G) for all j ∈ [3] \ {i∗ }, as desired. Else, ui∗(T ′ ) < ui∗(G) δ ≤ ∆2(G)-1 δ · ui∗(G); recall that ∆2(G) ≥ 2. Thus, some agent i ∈ [3] \ {i∗ } values T ′ at least ui(G) δ , and for the agent (denoted as k) other than i∗ and i, uk(T ′ ) = uk(T ′ \ {v}) < ∆2(G)-1 δ · uk(G), as desired.

3.3 Any Number of Agents

We now prove tight egalitarian PoC for any number of agents, beginning with stars.

Theorem 3.12. Let n ≥ 2 and G be a star. Then, Egal-PoC(G, n) = m - n + 1.

Our next result is for paths.

Theorem 3.13. Let n ≥ 2 and G be a path. Then,

Proof. We present the upper bound proof here.

Upper Bound. For n ≤ m < 2n - 1, the upper bound follows from Lemma 3.1, so we consider the case where m ≥ 2n - 1. As in previous proofs, we invoke Lemma 3.2 and consider instances where each vertex is positively valued by at most one agent. Our algorithm is a discretized version of the well-known moving-knife procedure; the pseudocode can be found in Algorithm 3. By our assumption on the instances, whenever a vertex is added to bundle B in line 4, at most one agent's utility for bundle B strictly increases. As a result, at any point during the algorithm's run, only one agent may find bundle B to be worth at least 1n · OPT-egal(I). By the design of the algorithm, each agent removed from the instance in the while-loop receives a contiguous bundle of vertices and gets utility at least 1n · OPT-egal(I). Finally, the last agent values all remaining vertices at least 1n ·OPT-egal(I), because

We finish this section with the egalitarian PoC for cycles. Theorem 3.14. Let n ≥ 2 and G be a cycle. Then,

4 Utilitarian Price of Connectivity

In this section, we present results on the utilitarian price of connectivity, which measures the worst-case loss of utilitarian welfare due to the connectivity constraint.

4.1 Two Agents

We begin by computing the utilitarian price of connectivity for instances with two agents. Similar to the egalitarian case, the utilitarian price of connectivity is strictly higher than 1 when just one edge is removed from a complete graph, but does not increase further when additional disjoint edges are removed (with the exception of the 5-item case).

Theorem 4.1. Let G be a complete graph with a non-empty matching removed. Then, Util-PoC(G, 2) = 4 3 if G is

• K3 with an edge removed, or
• L5, which is K5 with two disjoint edges removed,

and Util-PoC(G, 2) = 2m-4 2m-5 otherwise.

We next study complete bipartite graphs. Interestingly, if one side of the graph has two vertices, then the utilitarian PoC is constant, regardless of how many vertices are on the other side.

Theorem 4.2. Let G be a complete bipartite graph with parts denoted as V1 and V2. Assuming that |V1|, |V2| ≥ 2, Util-PoC(G, 2) = 43 if |V1| = 2 or |V2| = 2, and Util-PoC(G, 2) = 2 2- 1 |V1| - 1 |V2| otherwise.

We next find that the utilitarian PoC for trees is only dependent on the number of items. This contrasts with the egalitarian PoC, which is lower bounded by the maximum degree of the tree (Theorem 3.8).

Theorem 4.3. Let G be a tree. Then, Util-PoC(G, 2) = 2(m-1) m .

Next, we provide tight bounds for the case of cycles. Again, the utilitarian PoC is only dependent on the total number of items.

Theorem 4.4. Let G be a cycle. Then, Util-PoC(G, 2) = 2k k+1 , where k = ⌊ m2 ⌋.

4.2 Any Number of Agents

We now move to the case of general n. In this section, all of our utilitarian PoC bounds are asymptotically tight, with the lower bounds matching (as m→∞) the following upper bound for any connected graph.

We begin by proving a lower bound for star graphs, which depends on the relation between n and m. Here, one agent only values the center vertex, and each of the remaining agents has a distinct set of leaf vertices which they value equally, and the cardinality of these leaf vertex sets differs by at most 1.

Theorem 4.6. Let n ≥ 2 and G be a star graph. Then, Util-PoC(G, n) ≥ nc(c+1) c2+2nc+n-c-m for m-1 = c(n-1)+d, where c ∈ Z+ and d ∈ {0, . . . , n-2}. This is Ω(n) for large c (i.e., large m).

We next move to the path graph lower bound, constructing an instance where each item is valued by exactly one agent and is listed in the repeating sequence (1, 2, . . . , n)∗ , where the number denotes the agent that values the item.

Theorem 4.7. Let n ≥ 2 and G be a path graph. Then, Util-PoC(G, n) ≥ c2 n+cn c2+cn-d+n+1 for m = cn + d, where c ∈ Z+ and d ∈ {0, . . . , n-1}. This is Ω(n) for large c (i.e., large m).

Lastly, we give lower bounds for cycle graphs.

Theorem4.8. Let n ≥ 2 andGbe a cycle graph. Then, when m = cn + d, where c ∈ Z+ and d ∈ {0, . . . , n - 1},

This is Ω(n) for large c (i.e., large m).

5 Discussion

In this work, we have introduced, for the allocation of indivisible goods on a graph, the concepts of egalitarian and utilitarian price of connectivity. These quantify the worst-case welfare loss due to connectivity constraints (i.e., each agent must receive a connected subgraph of items). We have studied the price of connectivity for various classes of graphs, including 1- or 2-connected graphs, complete graphs with a matching removed, complete bipartite graphs, stars, paths, and cycles, and produced tight or asymptotically tight bounds.

There is still room to extend the current results further. For the case of two agents, while we have addressed classes of dense and sparse graphs, a complete characterization of the egalitarian PoC for arbitrary graphs is still unknown, and the utilitarian PoC for graphs with connectivity 1 and 2 is also open. Furthermore, it would be interesting to generalize the existing egalitarian PoC result for trees and three agents to graphs with connectivity 1, and to also supplement this result with utilitarian PoC results.

As noted in the survey by Suksompong [2021], in addition to the connectivity constraint studied in this paper, other constraints have been studied in the fair division literature. For instance, a cardinality constraint could require the number of items received by each agent to be the same (or similar) [Biswas and Barman, 2018], and matroid constraints restrict the possible bundles received by each agent to a specific set of bundles [Dror et al., 2023].

Acknowledgments

This work was partially supported by the ARC Laureate Project FL200100204 on "Trustworthy AI", by the Singapore Ministry of Education under grant number MOET2EP20221-0001, by the Singapore Ministry of Education under its Academic Research Fund Tier 1 (RG23/20), and by an NUS Start-up Grant.