# welfare_loss_in_connected_resource_allocation__31c0ea96.pdf

Welfare Loss in Connected Resource Allocation

Xiaohui Bei1 , Alexander Lam2 , Xinhang Lu3 and Warut Suksompong4

1Nanyang Technological University 2City University of Hong Kong 3UNSW Sydney 4National University of Singapore xhbei@ntu.edu.sg, alexlam@cityu.edu.hk, xinhang.lu@unsw.edu.au, warut@comp.nus.edu.sg

We study the allocation of indivisible goods that form an undirected graph and investigate the worstcase welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifically, we introduce the concept of egalitarian (resp., utilitarian) price of connectivity, which captures the worst-case ratio between the optimal egalitarian (resp., utilitarian) welfare among all allocations and that among the connected allocations. We provide tight or asymptotically tight bounds on the price of connectivity for various large classes of graphs when there are two agents as well as for paths, stars and cycles in the general case. Many of our results are supplemented with algorithms which find connected allocations with a welfare guarantee corresponding to the price of connectivity.

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 utilitarian welfare, 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.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

1: 0.5 2: 0.2 1: 0.0 2: 0.4

1: 0.4 2: 0.0 1: 0.1 2: 0.4

Figure 1: An instance with n = 2 agents and m = 4 items. The numbers in each node indicate the agents utilities for the item. The items allocated to agent 2 under the optimal connected egalitarian and utilitarian outcomes are circled by the blue ellipse and red dashed lines, respectively.

Egalitarian Utilitarian

Stars m n + 1 (Thm. 3.12) Ω(n) (Thm. 4.6)

m n + 1, n m < 2n 1 n, 2n 1 m (Thm. 3.13)

Ω(n) (Thm. 4.7)

m n + 1, n m < 2n 2 n 1, 2n 2 m < n2

n, n2 m (Thm. 3.14)

Ω(n) (Thm. 4.8)

Any graph m n + 1 (Lem. 3.1) n (Prop. 4.5)

Table 1: Table of Po C results for any number of agents.

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 (Po C) 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 Po C 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 Po C is a constant, regardless of how many vertices the other side has.

We also consider graphs with low connectivity, finding the egalitarian Po C in the two-agent case for the broad classes of graphs with connectivity 1, including all trees, and graphs with connectivity 2. Although the Po C for graphs with connectivity 1 is lower bounded by the maximum number of disjoint connected subgraphs resulting from the removal of a vertex, the Po C for graphs with connectivity 2 is simply a constant. We also extend to the three-agent case, finding the egalitarian Po C 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 Po C for trees and cycles. Unlike in the egalitarian case, the utilitarian Po C 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 Po C bounds, while Section 4 presents the utilitarian Po C results.

1.2 Related Work 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 (Po C) 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 Po C 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 Po C 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) Po C results by Bei et al. [2022] imply egalitarian Po C 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.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

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 ) = P 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 allocation M = (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 allocation M = (M1, M2, . . . , Mn) of the instance,

the egalitarian welfare of M, denoted as SW-egal(M), is the minimum among the agents utilities; that is, SW-egal(M) := mini N ui(Mi);

the utilitarian welfare of M, denoted as SW-util(M), is the sum of the agents utilities; that is, SW-util(M) := P 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 paper the price of connectivity (Po C) which captures the largest multiplicative gap between the optimal welfare among all allocations and that among all connected allocations.

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

Egal-Po C(G, n) = sup I= N,G,U

OPT-egal(I) max M C(I) SW-egal(M),

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.

1We interpret 0 0 in this context to be equal to 1. Note that OPT-egal(I) = 0 if and only if max M 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-Po C(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 Po C 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. Lemma 3.1. Given any G, Egal-Po C(G, n) m n + 1. 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 Po C 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 b I IG, there exists a connected allocation c M such that SW-egal( c M) β OPT-egal(b I). Then, Egal-Po C(G, n) 1/β. Lemma 3.2 suggests that when proving upper bounds on the egalitarian Po C, 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 Po C 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 Po C 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-Po C(G, 2) = 2 if G is K3 with an edge removed, or L5, which is K5 with two disjoint edges removed,

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

and Egal-Po C(G, 2) = m 2

m 3 otherwise.

Following this, we address another class of dense graphs, complete bipartite graphs, where we find that the egalitarian Po C 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,

Egal-Po C(G, 2) =

( m 1 if x = 1; x x 1 otherwise.

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 Po C 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-Po C(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 Po C for graphs with connectivity 2.

2A 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-Po C(G, 2) = 2.

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

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

A graph with connectivity 2 is not 2-linked,4 and therefore by Lemma 3.7, has an egalitarian Po C 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 Po C 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-Po C(G, 2) = 2 if the block decomposition of G is a path, and Egal-Po C(G, 2) = 3 otherwise. When d 3, Egal-Po C(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 Po C 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-Po C(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-Po C(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

3A 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. 4This can be seen by letting a and b be the vertices which, when removed from G, result in at least two disjoint connected subgraphs G1, G2, . . . , and by taking vertices c G1 and d G2.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Algorithm 1: Allocating a Graph with Connectivity 1 for Two Agents

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

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 )

γ for some agent i and uj(T ) < uj(G)

γ for the other

agent j, then uj(T \ T ) > uj(G)(1 1

γ . Further-

more, all subtrees of T are worth strictly lower than u1(G)

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

γ 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

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 Po C 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-Po C(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-Po C(G, 2) δ.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

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)

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 from G 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)

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.) Output: A connected allocation M with SW-egal(M) 1

n OPT-egal(I).

1 M = (M1, . . . , Mn) ( , . . . , )

2 while |N| 2 do

4 Process the vertices along the path from left to right and add them one at a time to bundle B until for some i N, ui(B) 1

n OPT-egal(I).

6 N N \ {i}, G G \ B

7 Give all remaining vertices to the last agent and update M accordingly.

8 return A connected allocation M.

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)

δ 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 Po C for any number of agents, beginning with stars.

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

Our next result is for paths.

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

Egal-Po C(G, n) = m n + 1 if n m < 2n 1; n if 2n 1 m.

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 1

n 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 1

n OPT-egal(I). Finally, the last agent values all remaining vertices at least 1

n OPT-egal(I), because

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

otherwise OPT-egal(I) ui(G) < (n 1)/n OPT-egal(I)+ 1/n OPT-egal(I) = OPT-egal(I), a contradiction.

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

Egal-Po C(G, n) =

m n + 1 if n m < 2n 2; n 1 if 2n 2 m < n2; n if n2 m.

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-Po C(G, 2) = 4

3 if G is K3 with an edge removed, or L5, which is K5 with two disjoint edges removed, and Util-Po C(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 Po C 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-Po C(G, 2) = 4 3 if |V1| = 2 or |V2| = 2, and Util-Po C(G, 2) = 2 2 1 |V1| 1 |V2| otherwise.

We next find that the utilitarian Po C for trees is only dependent on the number of items. This contrasts with the egalitarian Po C, which is lower bounded by the maximum degree of the tree (Theorem 3.8). Theorem 4.3. Let G be a tree. Then, Util-Po C(G, 2) = 2(m 1)

m . Next, we provide tight bounds for the case of cycles. Again, the utilitarian Po C is only dependent on the total number of items. Theorem 4.4. Let G be a cycle. Then, Util-Po C(G, 2) = 2k k+1, where k = m

4.2 Any Number of Agents We now move to the case of general n. In this section, all of our utilitarian Po C bounds are asymptotically tight, with the lower bounds matching (as m ) the following upper bound for any connected graph. Proposition 4.5. Given any instance I = N, G, U , Util-Po C(G, n) n.

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-Po C(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-Po C(G, n) c2n+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. Theorem 4.8. Let n 2 and G be a cycle graph. Then, when m = cn + d, where c Z+ and d {0, . . . , n 1},

Util-Po C(G, n)

c2n+cn c2+cn+n+1 if d = 0;

c2n+cn c2+cn+c+n 3 if d = 1 and c 2; n n 1

2 if d = 1 and c = 1;

c2n+cn c2+cn+c d+n 1 if d 2.

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 1or 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 Po C for arbitrary graphs is still unknown, and the utilitarian Po C for graphs with connectivity 1 and 2 is also open. Furthermore, it would be interesting to generalize the existing egalitarian Po C result for trees and three agents to graphs with connectivity 1, and to also supplement this result with utilitarian Po C 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].

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

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.

[Amanatidis et al., 2023] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Herv e Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023.

[Asadpour and Saberi, 2010] Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39(7):2970 2989, 2010.

[Barman et al., 2020] Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds on the price of fairness for indivisible goods. In Proceedings of the 16th International Conference on Web and Internet Economics (WINE), pages 356 369, 2020.

[Bei et al., 2021] Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods. Theory of Computing Systems, 65(7):1069 1093, 2021.

[Bei et al., 2022] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. The price of connectivity in fair division. SIAM Journal on Discrete Mathematics, 36(2):1156 1186, 2022.

[Bei et al., 2024] Xiaohui Bei, Alexander Lam, Xinhang Lu, and Warut Suksompong. Welfare loss in connected resource allocation. Co RR, abs/2405.03467, 2024.

[Bertsimas et al., 2011] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. The price of fairness. Operations Research, 59(1):17 31, 2011.

[Bez akov a and Dani, 2005] Ivona Bez akov a and Varsha Dani. Allocating indivisible goods. ACM SIGecom Exchanges, 5(3):11 18, 2005.

[Biggs, 1993] Norman Biggs. Algebraic Graph Theory. Cambridge University Press, 2nd edition, 1993.

[Bil o et al., 2022] Vittorio Bil o, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131:197 221, 2022.

[Biswas and Barman, 2018] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 91 97, 2018.

[Bollob as, 1998] B ela Bollob as. Modern Graph Theory. Springer, 1998.

[Bondy and Murty, 2008] John A. Bondy and Uppaluri S. R. Murty. Graph Theory. Springer, 2008. [Bouveret et al., 2017] Sylvain Bouveret, Katar ına Cechl arov a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pages 135 141, 2017. [Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996. [Caragiannis et al., 2012] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. The efficiency of fair division. Theory of Computing Systems, 50(4):589 610, 2012. [Caragiannis et al., 2022] Ioannis Caragiannis, Evi Micha, and Nisarg Shah. A little charity guarantees fair connected graph partitioning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4908 4916, 2022. [Celine et al., 2023] Karen Frilya Celine, Muhammad Ayaz Dzulfikar, and Ivan Adrian Koswara. Egalitarian price of fairness for indivisible goods. In Proceedings of the 20th Pacific Rim International Conference on Artificial Intelligence (PRICAI), pages 23 28, 2023. [Chartrand and Zhang, 2020] Gary Chartrand and Ping Zhang. Chromatic Graph Theory. CRC Press, Taylor & Francis Group, 2nd edition, 2020. [Dror et al., 2023] Amitay Dror, Michal Feldman, and Erel Segal-Halevi. On fair division under heterogeneous matroid constraints. Journal of Artificial Intelligence Research, 76:567 611, 2023. [Igarashi and Peters, 2019] Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 2045 2052, 2019. [Igarashi, 2023] Ayumi Igarashi. How to cut a discrete cake fairly. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5681 5688, 2023. [Li et al., 2024] Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao. A complete landscape for the price of envy-freeness. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1183 1191, 2024. [Lonc and Truszczynski, 2020] Zbigniew Lonc and Miroslaw Truszczynski. Maximin share allocations on cycles. Journal of Artificial Intelligence Research, 69:613 655, 2020. [Lonc, 2023] Zbigniew Lonc. Approximating fair division on d-claw-free graphs. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 2826 2834, 2023. [Maon et al., 1986] Yael Maon, Baruch Schieber, and Uzi Vishkin. Parallel ear decomposition search (EDS) and

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

st-numbering in graphs. Theoretical Computer Science, 47:277 298, 1986. [Moulin, 2003] Herv e Moulin. Fair Division and Collective Welfare. MIT Press, 2003. [Steinhaus, 1948] Hugo Steinhaus. The problem of fair division. Econometrica, 16(1):101 104, 1948. [Suksompong, 2019] Warut Suksompong. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics, 260:227 236, 2019. [Suksompong, 2021] Warut Suksompong. Constraints in fair division. ACM SIGecom Exchanges, 19(2):46 61, 2021. [Thomson, 2016] William Thomson. Introduction to the theory of fair allocation. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 11, pages 261 283. Cambridge University Press, 2016.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)