Fair Division of a Graph into Compact Bundles

1 Introduction

We study a fair allocation problem: m indivisible items are to be allocated among n agents, where the items are the vertices of a graph. The agents have preferences over the items, and we have to allocate the items in such a way that the allocation is fair (for appropriate notions of fairness) and each agent receives a bundle of items (i.e., a subset of vertices) that induces a subgraph with a specific "nice structure." The fairness notions that we study are proportionality, envy-freeness and maximin share guarantee; and the nice structure that we study requires that each agent must receive a set of "closely related" items.

While fair division of indivisible items has been studied extensively from both economics and computational perspectives [Moulin, 2003; Aziz et al., 2022; Amanatidis et al., 2022], fair division of graphs is a relatively recent line of study, starting with the work of [Bouveret et al., 2017]. The classic fair division literature assumes no relationship among the items; the items are independent of each other. But there are any number of scenarios where the items to be allocated, rather than being an assortment of isolated units, are related to one another. And we can often model such relationships between the items using a graph. The items, for example, may be rooms in a large building, and the graph models adjacency between pairs of rooms; or the items may be a valuable collection of postage stamps, and the graph models similarities between pairs of stamps on the basis of country, design or typography; or the items may be the topics for a course (to be divided between two professors who are planning to co-teach the course), and the graph models connections between the topics. Fair division of graphs attempts to capture precisely such settings.

While fair division of graphs has received considerable attention in recent years [Deligkas et al., 2021; Bil`o et al., 2022; Greco and Scarcello, 2020; Igarashi and Peters, 2019; Bei et al., 2022], to the best of our knowledge, all work so far has focused solely on connected fair division. That is, each agent should receive a set of vertices that induces a connected subgraph. Bouveret et al. [2017], who introduced this model of fair division of graphs, considered the example of office spaces in a university being allocated to various research groups, where each research group should receive a contiguous set of offices. This scenario can be modelled as a fair-division-of-a graph problem where each agent must get a connected subgraph-agents represent various research groups and the vertices and the edges of the graph respectively represent the offices and adjacency between offices. Notice that while contiguity might be useful, the "closeness" of the offices allocated to each group might be just as important. Simply demanding contiguity might leave a research group with a set of offices along a long and narrow corridor, which may not be an attractive proposition to the members of the group. In the absence of other constraints, the connectivity requirement, while desirable, might produce bundles with unwieldy topologies. In some cases, demanding connected bundles for every agent may be too stringent a requirement. For example, imagine a scenario with just one agent and two items that are isolated from each other. The agent has a utility of 1/2 for each of the two items and a total utility of 1 for the two items together. As we can see, demanding connectivity results in only one item being allocated to the agent, costing her half her total utility for the set of items.

We can also think of the connectivity requirement in the fair division of graphs as a direct adaptation of the contiguity requirement in the fair division of divisible items, i.e., the cake cutting problem where each agent should receive a contiguous piece of the cake [Stromquist, 1980; Goldberg et al., 2020]. But contiguity is a singularly important consideration in the cake cutting setting, for otherwise an agent "who hopes only for a modest interval of cake may be presented instead with a countable union of crumbs" [Stromquist, 1980]. That is not the case with graphs. Moreover, graphs are a rich combinatorial structure capable of modelling a variety of relationships among the items. And connectivity of the items allocated to each agent may not always be the most important consideration. There is, however, a void when it comes to our understanding of fair division of graphs under constraints other than connectivity. In this paper, we take a first step towards filling this void.

1.1 Our Contribution

We make three contributions. (1) Propose meaningful alternatives for connectivity in the fair division of graphs. (2) Study the computational complexity of finding fair allocations under such alternative constraints, even on restricted inputs. The restrictions on the input are based on the nature of the valuation functions and the structure of the graph on the set of items. (3) Identify and exploit results and techniques from structural and algorithmic graph theory to design efficient algorithms for fair division of graphs. To that end, we propose an alternative for connectivity: We demand that each agent must receive a compact bundle of items. Through compactness, we try to capture the idea that each agent must receive a set of closely related items.

To formally define compact graphs, we introduce the following notation. For n ∈ N, [n] denotes the set {1, 2, . . . , n} and [n]0 = [n] ∪ {0}. For a graph G, V (G) and E(G) respectively denote the set of vertices and edges of G. For vertices z, z′ ∈ V (G), the distance between z and z′ , denoted by distG(z, z′ ), is the length of a shortest path between z and z′ . For z ∈ V (G) and a non-negative integer β, BG(z, β) = {z′ ∈ V (G) | distG(z, z′ ) ≤ β}; we call BG(z, β) the ball of radius β centred at z.

Compact graphs: Definitions. For non-negative integers α and β, we say that a graph G is (α, β)-compact if there exist vertices z1, z2, . . . , zα ∈ V (G) such that for every z ∈ V (G), dist(z, zi) ≤ β for some i ∈ [α], i.e., V (G) = ⋃αi=1 BG(zi, β). 1 That is, G is (α, β)-compact if G can be "covered by α many balls, each of radius at most β." We also define a related class of graphs called strongly (α, β)- compact graphs. A graph G is strongly (α, β)-compact if there exist vertex subsets V1, V2, . . . , Vα ⊆ V (G) such that V (G) = ⋃αi=1 Vi and for every i ∈ [α] and for every z, z′ ∈ Vi, distG(z, z′ ) ≤ β. In this paper, we focus primarily on (α, β)-compact graphs. (We consider the empty graphthe graph G with V (G) = E(G) = ∅-to be both (α, β)- compact and strongly (α, β)-compact for every α, β ≥ 0.)

Compact graphs: Examples. If a graph G is strongly (α, β)-compact, then it also (α, β)-compact. But the converse need not hold. For example, a star is (1, 1)-compact, but not strongly (1, 1)-compact. But if G is (α, β) compact, then it is strongly (α, 2β)-compact. When β = 0, the two definitions coincide. For example, a graph is G is (strongly) (α, 0)-compact if and only if G has at most α many vertices. And G is strongly (1, 1)-compact if and only if G is a clique; and G is strongly (1, β)-compact if and only if G has diameter at most β. In particular, an m-vertex graph G is connected if and only if G is (strongly) (1,m- 1)-compact. Similarly, a graph G with α connected components is strongly (α, β)- compact if and only if every component has diameter at most β. As these examples show, (strong) compactness is expansive enough to accommodate several natural restrictions on the structure of G, including properties of graphs such as number of vertices, connectivity, bounded diameter etc.

1 In graph theory literature, a set Z ⊆ V (G) of vertices such that V (G) = ⋃z∈Z BG(z, β) is called a distance-β dominating set [Haynes et al., 2020]. So (α, β)-compact graphs are precisely those graphs that have a distance-β dominating set of size at most α.

Our Model

We study fair division problems of the following type. A typical instance of our problem consists of a triplet (G,N, V), where G is an m-vertex graph, N is a set of agents with |N| = n, and V is an n-tuple of functions (vi)i∈N, where vi : 2V (G) → Q≥0. For i ∈ N, vi is called the valuation function or the utility function of agent i. We assume throughout that the valuation functions are additive (unless otherwise stated). That is, for i ∈ N and S ⊆ V (G), we have vi(S) = ∑z∈S vi({z}) and vi(∅) = 0. When S = {z} is a singleton set, we omit the braces and simply write vi(z). We call the set of vertices of G goods or items as well. Throughout the paper, we use m for the number of items and n for the number of agents. And we use N or [n] for the set of agents.

Compact allocations. Consider (G,N, V). An allocation is a function that assigns pairwise disjoint subsets of V (G) to the agents. That is, an allocation is a function π : N → 2V (G) such that π(i) ∩ π(j) = ∅ for distinct i, j ∈ N. Consider an allocation π. We call π(i) agent i's bundle under the allocation π. We say that π(i) is (α, β)-compact if G[π(i)] is (α, β)-compact. An allocation π is (α, β)-compact if π(i) is (α, β)-compact for every i ∈ N. We define a strongly (α, β)- compact allocation analogously.

Fairness concepts. We consider three well-studied fairness concepts-proportionality, envy-freeness and maximin fairness. An allocation π is proportional if vi(π(i)) ≥ (1/n) · vi(V (G)) for every i ∈ N, i.e., every agent receives at least a 1/n fraction of her utility for the whole graph. And we say that π is envy-free if vi(π(i)) ≥ vi(π(j)) for every pair of distinct agents i, j ∈ N, i.e., every agent prefers her own bundle to that of the other agents. We now define maximin fair allocations by suitably adapting the definition introduced by Budish [2011]. For (G,N, V), let Π(G,N, V) be the set of all allocations φ : N → 2V (G) . Let Γ ⊆ Π(G,N, V) be any non-empty set of allocations. For every agent i ∈ N, we define the Γ-maximin share guarantee of i, denoted by Γ-mmsi(G,N, V), as follows:

Informally, Γ-mmsi(G,N, V) is the maximum utility agent i could guarantee for herself if agent i were to allocate the items, with the caveat that the allocation be in Γ, and allowed to choose only the least valued bundle for herself. We say that an allocation φ : N → 2V (G) is Γ-maximin fair if vi(π(i)) ≥ Γ-mmsi(G,N, V). We are interested in Γmaximin fair allocations, where Γ is the set of all (α, β)- compact allocations, which we denote by Γ((α, β)-com).

Economic efficiency constraints. We say that an allocation π is complete if π allocates all the vertices of G, i.e., ⋃i∈N π(i) = V (G). And we say that π is Pareto-optimal if there exists no allocation π′ such that vi(π′ (i)) > vi(π(i)) for some i ∈ N and vj(π′ (j)) ≥ vj(π(j)) for every j ∈ N \{i}.

Computational questions. Let α and β be fixed integers. We are interested in computational problems that take an instance (G,N, V) as input, and the question is to decide if (G,N, V) admits an allocation that is (strongly) (α, β)- compact and fair? Depending on the fairness concept, we have the following specific problems.

• PROP-(α, β)-COMPACT-FD: Does (G,N, V) admit an allocation that is proportional and (α, β)-compact?
• EF-(α, β)-COMPACT-FD: Does (G,N, V) admit an allocation that is envy-free and (α, β)-compact? As the empty allocation (where no item is allocated) is trivially envy-free, we often combine envy-freeness with efficiency constraints such as completeness or Paretooptimality (PO). Accordingly, we have the corresponding problems: COMPLETE-EF-(α, β)-COMPACT-FD and PO-EF-(α, β)-COMPACT-FD.
• MMS-(α, β)-COMPACT-FD: Does (G,N, V) admit an allocation that is Γ((α, β)-com)-maximin fair and (α, β)-compact?

We define the strongly compact variants of the problems analogously. Notice that α and β are fixed constants and not part of the input.

Our Results

We prove a host of hardness and algorithmic results for [X]- (α, β)-COMPACT-FD, where we use [X] as a placeholder for one of the three fairness concepts discussed above. Recall that n is the number of agents and m is the number of vertices in the input graph. We first discuss the polynomial time solvability versus (weak and strong) NP-hardness of the problems. These results are further divided into cases based on the choices for α and β. The hardness results hold only for problems corresponding to proportionality and envy-freeness, and they all hold for additive valuations. And then we move on to our algorithmic results, specifically, FPT and XP algorithms w.r.t. a combination of parameters, including the number of agents, maximum degree and treewidth of the graph. We now list our results one by one.

NP-hardness. A reduction due to Lipton et al. [2004] from the PARTITION problem shows that PROP-(α, β)- COMPACT-FD, COMPLETE-EF-(α, β)-COMPACT-FD and PO-EF-(α, β)-COMPACT-FD are all NP-hard for every α, β ≥ 1. But notice that a reduction from PARTITION only implies weak NP-hardness. Besides, these results do not cover the case when β = 0.

The case of β = 0. This case warrants special attention. In this case, every agent can receive at most α items as a graph is (α, 0)-compact if and only if it has at most α vertices. (So we can ignore the graph and treat the problem as an instance of the classic fair division problem with the additional constraint on the size of the bundles.) We have the following results.

1. If α = 1, then every agent can receive at most one item. In this case, for all three fairness notions, the corresponding problems are polynomial time solvable. We can reduce each of the problems to a matching problem in an agents-items bipartite graph. For envy-freeness, we have the the additional constraint that every agent must receive exactly one item; and the polynomial time algorithm is due to Gan et al. [2019].
2. The case of α = 2. PROP-(2, 0)-COMPACT-FD is NPhard; implied by a result due to Ferraioli et al. [2014]. The complexity of the problem corresponding to envyfreeness is still open.
3. The case of α ≥ 3 is covered by the next result.

The case of α ≥ 3. We prove that PROP-(α, β)- COMPACT-FD, COMPLETE-EF-(α, β)-COMPACT-FD and PO-EF-(α, β)-COMPACT-FD are all strongly NP-hard for every α ≥ 3 and β ≥ 0, even when G is edgeless.

Proportionality + (α = 1) + paths. If α = 1 and the graph G is a path, then for proportionality, the corresponding problem admits an algorithm with runtime 2n · mO(1) , and hence is fixed-parameter tractable (FPT) with respect to the number of agents. We also extend this result to an algorithm with runtime np · mO(1) , where p is the number of types of agents. Two agents are of the same type if their valuations are identical. These results hold for arbitrary valuations. Our algorithms involve dynamic programming, and are only a slight adaptation of the algorithm of Bouveret et al. [2017] for proportional and connected fair division. But the fact that α = 1 is crucial for these algorithms to work.

XP algorithms w.r.t. n +∆. For all three fairness concepts (and arbitrary valuations), we design slicewise polynomial time (XP) algorithms with respect to the parameter n + ∆, where ∆ is the maximum degree of G. The algorithms follow from the simple observation that for any vertex z ∈ V (G), |BG(z, β)| ≤ ∆β+1 . Hence we can enumerate all (α, β)-compact allocations in time mO(αn) · 2αn·∆O(β) .

Pseudo-XP algorithms w.r.t. n+ tw. For problems corresponding to all three fairness fairness concepts, we design pseudo-XP algorithms with respect to the parameter tw + n, where tw is the treewidth of G. We design a single dynamic programming procedure that works for all three fairness concepts. We assume here that the valuations are integer-valued. Let W be the maximum value any agent has for the whole graph, i.e., W = maxi∈N vi(V (G)). Our algorithms have a runtime of (tw + n)O(tw+n) · βO(tw) · mO(αn) · W O(n2 ) . In particular, when the valuations are polynomially bounded, we have XP algorithms. These algorithms yield a number of interesting corollaries, which we discuss below.

1. Welfare maximisation: We can use our dynamic programming procedure to compute (α, β)-compact alloca-

tions that maximise welfare. For example, we can answer questions such as this: Among all the allocations that maximise the utilitarian social welfare, is there one that is also (α, β)-compact? The utilitarian social welfare of an allocation π is the sum of the utilities of the agents have under π, i.e., ∑i∈N vi(π(i)).

1. Connected fair division: As noted earlier, an mvertex graphs is connected if and only if it is (1,m - 1) compact. Hence our algorithms work for connected fair division as well, with a runtime of (tw + n)O(tw+n)mO(tw+n) · W O(n2 ) .
2. Implications for planar graphs (and more): On planar graphs, our algorithms run in time nO(n) · mO(αn) · W O(n2 ) , i.e., a pseudo-XP algorithm parameterized by n. To derive this result, we leverage the follwing two facts. (1) Treewidth of a planar graph is O(D), where D is the diameter of the graph. (2) Diameter of every connected component of an (α, β)-compact graph is O(αβ). In fact, a runtime of nO(n) ·mO(αn) ·W O(n2 ) is possible not just on planar graphs, but on all graphs whose treewidth is bounded by a function of its diameter. In particular, if F is a minor-closed family of graphs and F excludes an apex-graph, then on any graph G ∈ F, our algorithms run in time f(n) · mO(αn) · W O(n2 ) , where the function f depends only on F. This follows from a result due to Eppstein [2000].

Results for strongly compact variants. All our hardness results mentioned above hold for the strongly compact variants of the respective problems as well. So do (i) our algorithm for proportional allocations on paths when α = 1 and (ii) the XP algorithms parametrized by n +∆. In addition, we show that for proportionality and envy-freeness + completeness, the corresponding strongly compact variants of the problems are strongly NP-hard for every α, β ≥ 1. (Notice that our strong NP-hardness results for the compact variants only cover the case of α ≥ 3.)

Runtime of our algorithms. The runtimes of the algorithmic results discussed above have an exponential dependence on n (the number of agents). But this need not be a disqualifying factor as several fair division settings only have a constant number of agents, and often, just two agents. Common examples of 2-agent settings, as noted by Plaut and Roughgarden [2020], include divorce settlements, inheritance division and international border disputes. In fact, 2-agent setting is one of the most intensively studied special cases in fair division; see, for example, [Brams and Fishburn, 2000; Brams et al., 2022]. We would also like to point out that the dependence of the runtime of our treewidth-based algorithm on both n and tw is also essential. Our NP-hardness results for proportional or envy-free, compact allocations when α ≥ 3 hold for graphs of treewidth zero (even when the valuations are additive and polynomially bounded). The runtime of our treewidth-based algorithm depends also on W, the maximum valuation of an agent for the whole graph. This may be inevitable as well. As noted above, we can use our algorithms to find welfare-maximising allocations. Our algorithms thus compute allocations with three properties: fairness, compactness and economic efficiency. And for algorithms that find efficient allocations, "pseudo" runtimes are rather common [Barman et al., 2018; Aziz et al., 2023].

Choice of parameters. We would also like to emphasise that the parameterizations that we use to design our algorithm are all commonly studied in the literature. In particular, parameterizations by the number of agents or agent types have been used by Bouveret et al. [2017] and Deligkas et al. [2021]. It is quite common in parameterized algorithms literature to leverage structural parameters such as maximum degree, degeneracy or treewidth to design efficient algorithms. Treewidth, in particular, is a popular structural parameter; see, for example, [Fomin et al., 2020] for the many applications of treewidth in algorithm design. We must also add that connected fair division of graphs has previously been studied on special graphs such as paths, stars, trees, cycles etc., which are all graphs of treewidth 1 or 2. Also, parameters such as treewidth and cliquewidth have been used as structural parameters in connected fair division. We discuss many of these works below. So it is very much in line with the existing literature to use treewidth as a parameter to design algorithms. In particular, one of our goals was to apply results and techniques from graph theory literature to problems in fair division. And for this purpose, treewidth is arguably the most suitable choice.

1.2 RelatedWork

Modern fair division literature goes back at least to the pioneering work of Steinhaus [1948]. See the surveys by Lindner and Rothe [2016] for the divisible goods setting; and by Aziz et al. [2022] or by Amanatidis et al. [2022] for the indivisible goods setting.

There is also a large volume of literature on fair division under connectivity constraints. As for the cake cutting setting (i.e., divisible goods), Stromquist [1980] proved that an envy-free allocation of the cake into connected pieces exists, but there is no finite protocol that can find such an allocation [Stromquist, 2008]. Coming to the indivisible goods setting, the work of Bouveret et al. [2017], which formally introduced this line of study, contains several algorithmic and hardness results for connected fair division of a graph. They showed that finding a connected allocation that is envy-free or proportional is NP-hard, even when the graph is a path. On the other hand, a maximin allocation always exists and can be computed in polynomial time if the graph is a tree. They also designed several FPT and XP algorithms with respect to parameters such as number of agents and number of agent types, for special cases of the graph. This was followed by the work of Lonc and Truszczynski [2018], who studied the existence and complexity of maximin fair allocations on cycles. Among other results, they proved that when there are only three agents, there exists an allocation that guarantees each agent a constant fraction of her maximin share. Most related to our work is that of Deligkas et al. [2021], who undertook an in-depth study of the parameterized complexity of connected fair division. They established a host of hardness and algorithmic results-under various combinations of parameters such as the number of agents, treewidth, cliquewidth etc.-with respect to fairness concepts such as proportionality, envy-freeness, EF1 and EFX. A number of recent works deal with the special case when the graph is a path, under various fairness notions. In particular, Bil`o et al. [2022] studied the existence and complexity of EF1 and EF2 allocations; Igarashi [2022] studied EF1 allocations and showed that EF1 allocations always exists for any number of agents with monotone valuations; Suksompong [2019] studied approximate guarantees for proportionality, envy-freeness and equitability; and Misra et al. [2021] studied the complexity of finding allocations that are equitable up to one item (EQ1) combined with economic efficiency notions such as Paretooptimality, non-wastefulness etc. In addition to these works that mainly deal with the existence or computational questions associated with connected fair division, Bei et al. [2022] studied the price of connectivity-the loss incurred by agents when the connectivity constraint is imposed-for maximin fair allocations. Their techniques included the application of several graph theoretic tools and concepts to fair division.

Much of the literature on fair division under restricted input settings focus on restrictions on valuations, number of agents or relaxations of fairness notions. To the best of our knowledge, there have only been a handful of works that consider restrictions on the structure of bundles allocated to agents (other than connected fair division in the context of graphs). The typical restriction on bundles involves what can be called cardinality constraints. The canonical example is the house allocation problem, where each agent must receive exactly one item. Gan et al. [2019] studied envy-freeness and Kamiyama et al. [2021] studied proportionality and equitability in the house allocation setting. Ferraioli et al. [2014] et al. studied the problem of maximising egalitarian welfare, under the additional constraint that each agent be allocated exactly k items. Biswas and Barman [2018] introduced a more general variant of cardinality constraints: the items are partitioned into groups and there is a cap on each group's contribution to any agent's bundle. Among other results, they showed that a 1/3-approximate maximin fair allocation can be computed efficiently. Recently, Hummel and Hetland [2022] improved the approximation guarantee to 1/2. See the survey by Suksompong [2021] for a comprehensive discussion of various constraints in fair division.

Organisation of the paper. Due to space constraints, we present only a representative subset of results here. We sketch the proofs for an NP-hardness result and our treewidth DP.

2 Strong NP-Hardness of Compact FD

We show that checking if a proportional, (α, β)-compact allocation exists is strongly NP-hard when α ≥ 3.

Theorem 1. For every α ≥ 3 and β ≥ 0, PROP-(α, β)- COMPACT-FD is strongly NP-hard.

Proof sketch. Fix α ≥ 3 and β ≥ 0. We show the NPhardness of PROP-(α, β)-COMPACT-FD by a reduction from EXACT COVER BY α-SETS (XαC), which is known to be NP-complete for every α ≥ 3 [Karp, 1972]. 2 In XαC, the input consists of a set X such that |X| = αs and a family F ⊆ 2X of subsets of X such that |F| = α for every F ∈ F; and the question is to decide if (X,F) has an exact cover, i.e., a sub-family F ′ ⊆ F such that |F ′ | = s and ⋃F∈F ′ F = X. Consider an instance (X,F) of XαC. Let |F| = r and F = {F1, F2, . . . , Fr}. We assume without loss of generality that r > s. Given (X,F), we now construct an instance (G,N, V) of PROP-(α, β)-COMPACT-FD as follows. Corresponding to each Fi ∈ F, we introduce an agent i; in addition we introduce a "dummy" agent r + 1. Thus N = [r + 1]. Corresponding to each x ∈ X, we introduce an item wx; in addition, we introduce r - s "auxiliary" items y1, y2, . . . , yr-s and a "special" item y∗. And we define the graph G to be the edge-less graph with vertex set V (G) = {y∗} ∪ {yj | j ∈ [r - s]} ∪ {wx | x ∈ X}. Finally, we define the valuation functions as follows. Consider i ∈ [r]. For each x ∈ X, we set

2 Karp [1972] only shows the NP hardness of X3C. But it is straightforward to reduce X3C to XαC for every α > 3.

vi(yj) = 1/(r+1) for every j ∈ [r-s]; and vi(y∗) = s/(r+ 1). Finally, vr+1(wx) = 0 for every x ∈ X; vr+1(yj) = 0 for every j ∈ [r - s]; and vr+1(y∗) = 1. Notice that we have ∑z∈V (G) vi(z) = 1 for every i ∈ N. And notice also that since G is edge-less, for every non-empty subset S ⊆ V (G), the subgraph G[S] is (α, β)-compact if and only if |S| ≤ α. We can verify that (X, F) is a yes-instance of XαC if and only if (G,N, V) is a yes-instance of PROP-(α, β)- COMPACT-FD.

3 Fair Division of Graphs of Bounded Treewidth

In this section, we show that for each of the three fairness concepts-proportionality, envy-freeness and maximin fairness-the corresponding problem of checking if there exists an allocation that is fair and (α, β) compact admits a pseudo-XP algorithm, when parameterized by the treewidth of the item graph and the number of agents. We design a single dynamic programming procedure that works for all three fairness concepts. We assume that the valuations are integer-valued. The following theorem is the main contribution of this section.

Theorem 2. For every α and β, PROP-(α, β)-COMPACT-FD, EF-(α, β)-COMPACT-FD and MMS-(α, β)-COMPACT-FD admit algorithms that run in time (tw + n)O(tw+n) · βtw · mO(αn) ·W O(n2 ) , where tw is the treewidth of the input graph G and W is the maximum valuation of an agent for G, i.e., W = maxi∈N vi(V (G)).

Annotated allocations. To prove theorem 2, we introduce an auxiliary problem. For a graph G, a vertex ˆ z ∈ V (G) and β > 0, we say that G is a (ˆ z; β)-annotated graph if z ∈ BG(ˆ z, β) for every z ∈ V (G), i.e., every vertex in G is within a distance of at most β from ˆ z. Consider a graph G, a set N of n agents and β > 0. For an n-tuple (ˆ zi)i∈N and an allocation π : N → 2V (G) , we say that π is ((ˆ zi)i∈N; β)-annotated if for every i ∈ N, ˆ zi ∈ π(i) and G[π(i)] is a (ˆ zi; β)-annotated graph. And we define the associated computational problem ANNOTATED-FD as follows: Given (G,N, V), (ˆ zi)i∈N and β as input, does (G,N, V) admit a ((ˆ zi)i∈N ; β)-annotated allocation?

Remark 3 (Reducing to ANNOTATED-FD). We now show how to use annotated allocations to prove Theorem 2. Suppose (G,N, V) is a yes-instance [X]-(α, β)-COMPACT-FD; and let π : N → 2V (G) be the hypothetical fair and (α, β)- compact allocation that we are looking for. Then for every i ∈ N, G[π(i)] is (α, β)-compact. Hence for every i ∈ N, there exist vertices z1 i , z2 i , . . . , zα i such that π(i) = ⋃αj=1 BG[π(i)](zj i , β). To design our algorithm, we first guess the vertices z1 i , z2 i , . . . , zα i for every i ∈ N. There are mO(αn) many guesses. For each guess, we do as follows. For every i ∈ N, we add a new vertex ˆ zi and make it adjacent to z1 i , z2 i , . . . , zα i ; and for every j ∈ N, we set vj(ˆ zi) = 0. We then look for a fair and ((ˆ zi)i∈N , β +1)-annotated allocation. Notice that for any vertex z ∈ V (G) and i ∈ N, j ∈ [α], z is at a distance of at most β from zj i if and only if z is at a distance of at most β +1 from ˆ zi. To summarise, given an instance of [X]-(α, β)-COMPACT-FD, we can construct mO(αn) instances of ANNOTATED-FD such that the original instance is a yes-instance if and only if at least one of the instances of ANNOTATED-FD is a yes-instance.

In light of Remark 3, to solve [X]-(α, β)-COMPACT-FD, it is enough to solve ANNOTATED-FD, for which we design an algorithm. More precisely, we prove the following lemma.

Lemma 4. There is an algorithm that, given an instance (G, [n], V, β, (ˆ zi)i∈[n]) of ANNOTATED-FD, an n2 tuple ( ˆwij)i,j∈[n], where 0 ≤ ˆwij ≤ W for every i, j ∈ [n] and a nice tree decomposition (T, {Xt | t ∈ V (T)}) of G as input, runs in time (tw+n)O(tw+n) ·βO(tw+n) ·mO(1) ·W O(n2 ) , and correctly decides if (G, [n], V, β, (ˆ zi)i∈[n])) admits a ((ˆ zi)i∈[n]; β)-annotated allocation π : [n] → 2V (G) such that vi(π(j)) = ˆwij for each i, j ∈ [n].

The rest of this section is dedicated to sketching a proof of Lemma 4. And for that, we design a dynamic programming algorithm over a (nice) tree decomposition of G. We assume basic familiarity with tree decompositions and refer the reader to [Cygan et al., 2015, Chapter 7] for an overview on tree decomposition based algorithms.

A tool for our DP: Rooted partition. Consider a nonempty set S. A partition of S is a family P ⊆ 2S of nonempty subsets of S such that ⋃P∈P P = S and P ∩ P ′ = ∅ for every distinct P, P ′ ∈ P. For a partition P of S, each set P ∈ P is called a block of P. And for z ∈ S, we denote the unique block of P that contains z by blockP(z). We now define what we call a rooted partition. For a non-empty set S, a rooted partition P of S is nothing but a partition of S, but each block P of P has a designated element, which we call the root of P. Formally, a rooted partition of S is an ordered pair (P, R) such that P is a partition of S, R ⊆ S with |R| = |P| and for each block P of P, |P ∩R| = 1; we call the unique element of P ∩ R the root of P .

From now on, we assume that we are given (G, [n], V, β, (ˆ zi)i∈[n]), an n2 tuple ( ˆwij)i,j∈[n], where

0 ≤ ˆwij ≤ W for every i, j ∈ [n] and a nice tree decomposition (T, {Xt | t ∈ V (T)}) of G of width tw. We first add the vertices ˆ z1, ˆ z2, . . . , ˆ zn to every bag Xt (and denote the resulting tree decomposition by (T, {Xt | t ∈ V (T)}) as well). Notice that this increases the width of the tree decomposition by n; and (T, {Xt | t ∈ V (T)}) still remains a nice tree decomposition but for the fact that the bags corresponding to the root node and the leaf nodes of T are non-empty. In particular, for t ∈ V (T), where t is a leaf node or t is the root of T , we have Xt = {ˆ z1, ˆ z2, . . . , ˆ zn}.

Outline of our algorithm. Suppose that π is the ((ˆ zi)i∈[n]; β)-annotated allocation that we are looking for. Then distG[π(i)](ˆ zi, z) ≤ β for each i ∈ [n] and for each z ∈ π(i). Let Hi be a BFS tree of G[π(i)], rooted at ˆ zi. Since Hi is a BFS tree rooted at ˆ zi, we have distG[π(i)](ˆ zi, z) = distHi (ˆ zi, z) for every z ∈ π(i). For a node t ∈ V (T), we guess how Hi intersects with the graph Gt. Notice that Hi is an acyclic graph and it could possibly split into multiple connected components when intersected with Gt. With this in mind, we guess the following features of the intersection of Hi with Gt: (a) the intersection of V (Hi)(= π(i)) with Xt, (b) how Hi partitions the vertices of Xt ∩π(i) into connected components (c) for each z ∈ Xt ∩ π(i), the distance in Hi between z and ˆ zi and (4) agent i's valuations for the subsets of goods in Gt that have been allocated to herself as well as the other agents, i.e., vi(π(j) ∩ V (Gt)) for every i, j ∈ [n]. We argue that these four pieces of information are sufficient to design a dynamic programming algorithm that constructs π in a bottom up fashion over T .

Designing the DP: Necessary Ingredients. To design our DP, for each node t ∈ V (T), we first define a set Ct, (which formalises our guesses). Formally, for each t ∈ V (T), let Ct be the set of all tuples ((Si, fi, (Pi, Ri))i∈[n], (wij)i,j∈[n]) with the following properties.

• For each i ∈ [n], Si is a vertex subset such that ˆ zi ∈ Si and Si ⊆ Xt ∩ BG(ˆ zi, β) and Si ∩ Sj = ∅ for every j ∈ [n] \ {i}.
• For each i ∈ [n], (Pi, Ri) is a rooted partition of Si such that ˆ zi ∈ Ri.
• For each i ∈ [n], fi : Si → [β]0 is a function such that fi(ˆ zi) = 0 and fi(z) ̸= 0 for every z ∈ Si \ {ˆ zi}.
• The tuple (wij)i,j∈[n] is an n2 -tuple of non-negative integers such that 0 ≤ wij ≤ W for every i, j ∈ [n].

Observation 5. For each t ∈ V (T), we have |C|t ≤ (tw + n)O(tw+n) · βO(tw) · W O(n2 ) . To see this, observe the following facts that follow from the definition of Ct. (i) As the sets S1, S2, . . . , Sn ⊆ Xt are pairwise disjoint, each element of Xt belongs to at most one Si, and therefore, the number of choices for (Si)i∈[n] is (n + 1)|Xt| . By identical reasoning, the number of choices for (Ri)i∈[n] is (n + 1)|Xt| . (ii) For each choice of (Si)i∈[n], the family ⋃ni=1 Pi is a partition of ⋃ni=1 Si ⊆ Xt. Therefore, corresponding to each (Si)i∈[n], the number of choices for (Pi)i∈[n] is at most |Xt||Xt| . (iii) As the sets S1, S2, . . . , Sn are pairwise disjoint, we may think of the n-tuple (fi)i∈[n] of functions as a single function from ⋃ni=1 Si to [β]0. Therefore, the number of choices for (fi)i∈[n] is at most (β + 1)|Xt| . (iv) We have |Xt| ≤ tw + 1 + n; the "+n" accounts for the fact that we added ˆ z1, ˆ z2, . . . , ˆ zn to every bag. (v) The number of choices for the tuple (wij)i,j∈[n] is at most (W +1)n2 .

Valid allocations. We now define what we call valid allocations. Informally, these are allocations that agree with our guesses (i.e., the tuples in Ct). For a node t ∈ V (T), let Gt be the subgraph of G made up of all the vertices and edges introduced in the subtree rooted at t. Consider a node t ∈ V (T) and an allocation π : [n] → 2V (Gt) . For a tuple η ∈ Ct, where η = ((Si, fi, (Pi,Ri))i∈[n], (wij)i,j∈[n]), we say that π is (t, η)-valid if

(VA.1) for each i ∈ [n], π(i) ∩Xt = Si;

(VA.2) for each i ∈ [n], Gt[π(i)] has a spanning forest Hi such that

• (a) for every z, z′ ∈ Si, z and z′ are in the same connected component of Hi if and only if z and z′ are in the same block of Pi;
• (b) for every z ∈ Si, fi(z) = fi(x) + distHi (x, z), where x is the root of blockPi (z);
• (c) for every z ∈ π(i) \ Xt, there exists y ∈ Ri such that distHi (y, z) ≤ β - fi(y); and

(VA.3) for each i, j ∈ [n], vi(π(j)) = wij.

For a t ∈ V (T), η ∈ Ct, a (t, η)-valid allocation π : [n] → 2V (Gt) and i ∈ [n], we call a spanning forest Hi of Gt[π(i)] that satisfies conditions (VA.2)(a)-(VA.2)(c) a (t, η, i)-witness for π. The correctness of our DP crucially relies on the following lemma, which says that every connected component of a (t, η, i)-witness intersects Xt.

Lemma 6. Consider i ∈ [n]. For t ∈ V (T) and η = ((Si, fi, (Pi,Ri))i∈[n], (wij)i,j∈[n]) ∈ Ct, let π : [n] → 2V (Gt) be a (t, η)-valid allocation and Hi a (t, η, i)-witness for π. Then for each connected component H of Hi, there exists a unique vertex xH ∈ V (H) ∩ Ri.

Observation 7 ((Structure of a (t, η, i)-witness)). For i ∈ [n], we can think of a (t, η, i)-witness Hi as a rooted foresteach connected component is a rooted tree; Ri is precisely the set of roots of the components of Hi, each connected component of Hi intersects Xt and the partition Pi is such that for z, z′ ∈ Si, z and z′ are in the same block of Pi if and only if z and z′ are in the same connected component of Hi.

Before proceeding further with our DP, let us first see how valid allocations help us prove Lemma 4.

Lemma 8. Consider (G, [n], V, β, (ˆ zi)i∈[n]), ( ˆwij)i,j∈[n], and (T, {Xt | t ∈ V (T)}) of G as defined in Lemma 4. And consider an allocation π : [n] → 2V (G) . Then π is a ((ˆ zi)i∈[n]; β)-annotated allocation with vi(π(j)) = ˆwij for every i, j ∈ [n] if and only if π is (ˆ t, ˆ η)- valid, where ˆ t is the root of the tree T and ˆ η = ((Si, fi, (Pi,Ri))i∈[n], ( ˆwij)i,j∈[n]) ∈ Cˆ t with Si = {ˆ zi}, fi : Si → [β]0 is the function that maps ˆ zi to 0, Pi = {{ˆ zi}} and Ri = {ˆ zi} for each i ∈ [n].

Proof. Assume first that π is a ((ˆ zi)i∈[n]; β)-annotated allocation and vi(π(j)) = ˆwij for every i, j ∈ [n]. We show that π satisfies each of the conditions in the definition of (ˆ t, ˆ η)-valid allocation. Recall that Xˆ t = {ˆ z1, ˆ z2, . . . , ˆ zn} and Gˆ t = G. Consider i ∈ [n]. First, π(i) ∩ Xˆ t = π(i) ∩ {ˆ z1, ˆ z2, . . . , ˆ zn} = {ˆ zi} = Si. Thus π satisfies condition (VA.1). Since π is ((ˆ zi)i∈[n] ; β)-annotated, distG[π(i)](ˆ zi, z) ≤ β for every z ∈ π(i). Now, fix a BFS tree Hi of G[π(i)], rooted at ˆ zi. Since π(i) ∩ Xt = {ˆ zi} and Pi = {{ˆ zi}}, Hi trivially satisfies condition (VA.2)(a). Again, since Si = {ˆ zi}, fi(ˆ zi) = 0 and distHi (ˆ zi, ˆ zi) = 0, Hi trivially satisfies condition (VA.2)(b) as well. Observe now that by the definition of a BFS tree, for every z ∈ π(i), we have distHi (ˆ zi, z) = distG[π(i)](ˆ zi, z) ≤ β, which along with the fact that fi(ˆ zi) = 0, implies that distHi (ˆ zi, z) ≤ β - fi(ˆ zi). Thus Hi satisfies condition (VA.2)(c). Finally, as vi(π(j)) = ˆwij, π satisfies condition (VA.3). We have thus shown that π is (ˆ t, ˆ η)-valid.

Conversely, assume that π is (ˆ t, ˆ η)-valid. Consider i ∈ [n]. Recall that Si = {ˆ zi} and fi(ˆ zi) = 0. By condition (VA.1), we have ˆ zi ∈ π(i). By the definition of a (ˆ t, ˆ η)-valid allocation, π has a (t, η, i)-witness, say H′ i . By condition (VA.2)(c), for every z ∈ π(i) \ {ˆ zi}, we have distH′ i (ˆ zi, z) ≤ β, which implies that distG[π(i)](ˆ zi, z) ≤ β. Thus ((ˆ zi)i∈[n] ; β)- annotated.

Definition of the states of the DP. Lemma 8 tells us that to check if (G,N, V) admits a ((ˆ zi)i∈[n]; β)-annotated allocation, it is sufficient to check if (G,N, V) admits a (ˆ t, ˆ η)-valid allocation. In light of this, we now define the states of our DP as follows. For each t ∈ V (T ) and each tuple η ∈ Ct, we define A[t, η] = 1 if there exists a (t, η)-valid allocation and A[t, η] = 0 otherwise.

We omit the details of the computation of A[t, η]. We conclude with the observation that since the DP allows us to check if there exists an allocation π with vi(π(j)) = wij for all possible values of wij for every i, j ∈ [n], it is straightforward to check if there exists an allocation that satisfies the required fairness constraints.

4 Conclusion

We proposed an alternative for connectivity in the fair division of graphs. Our results demonstrate that we can achieve tractability results under such alternative constraints. Our results also demonstrate that a number of tools and deep results from graph theory could find applications in fair division; this is still an under-explored direction. Compact allocations, we believe, can be a compelling alternative for connected allocations, and warrant further study. This work leaves several questions open. First, it would be interesting to see if our algorithmic results translate to the strongly compact setting. Second, all our strong NP-hardness results rely on an arbitrary number of agents and non-identical valuations. It would be interesting to see if strong NP-hardness results can be proved for restricted input settings. Third, apart from connectivity and compactness, there may be other structured bundles that are worth investigating. We hope this work will trigger such questions.

Acknowledgements

This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) [EP/V032305/1]. The author thanks the anonymous referees and Jessica Enright for their comments on the manuscript.