Approximating Fair Division on D-Claw-Free Graphs

1 Introduction

The problem of fair allocation of indivisible goods is a fundamental problem in social choice theory [Brams and Taylor, 1996; Bouveret et al., 2016]. We assume that we have a set of items that we call goods and a set of agents, each with her own utility function, which assigns some values to all subsets of goods (called bundles). The utility functions are commonly assumed to be additive and so we need to specify their values on individual goods only. We make this assumption in this paper, too. The objective is to assign the goods to the agents so that some fairness criterion is satisfied. Some of these criteria like proportionality or envy-freeness originate from the problem of fair allocation of divisible goods which is known as the cake cutting problem [Brams and Taylor, 1996; Procaccia 2016]. Unlike in the case of allocation of divisible goods where proportional and envy-free allocations always exist, for indivisible goods it is very easy to construct examples when no allocations satisfying these criteria exist.

[Budish, 2011] proposed a new fairness criterion for indivisible goods called the maximin share fairness criterion. It is based on the well-known cut and choose protocol in the cake cutting problem. Each of n agents first finds a partition of the set of goods into n bundles such that the least-valued bundle is maximized. The maximin share for this agent is equal to the value of this least-valued bundle. An allocation satisfies the maximin criterion if each agent receives a set of goods of value not smaller than her maximin share. We call such allocations mms-allocations. There are examples which show that an mms-allocation may not exist [Procaccia and Wang, 2014; Kurokawa et al., 2016]. Nevertheless such examples are quite intricate. To get around the difficulty of constructing mms-allocations, several researchers proposed to relax the maximin share criterion by requiring that the value of each agent's share in an allocation be at least equal to some positive fraction of the maximin share [Procaccia and Wang, 2014; Amanatidis et al., 2017; Barman and Murthy, 2017; Garg et al., 2019; Ghodsi et al., 2018]. Currently, the strongest result of this kind shows that a 3/4-approximating mms-allocation always exists and can be found in polynomial-time [Garg and Taki, 2021].

In this paper we study the problems of proportional and maximin share allocations in the setting proposed by [Bouveret et al., 2017]. In that setting the goods are vertices of an undirected graph (that we call the graph of goods) and the bundles to be assigned to the agents, as well as those in the definition of the maximin share, induce connected subgraphs of the graph of goods. This setting captures constraints that appear in some applications by excluding certain undesirable sets of goods. Typical examples of such applications include problems of consolidating land plots [King and Burton, 1982], or allocating rooms in a building to research groups [Bouveret et al., 2017]. In these applications agents might require that the sets of goods (rooms or plots of land) allocated to them form a connected subgraph of the graph of goods describing the neighborhood relation between the goods. The original problem of fair allocation of indivisible goods is now a special case of this generalization when the graph of goods is complete.

[Bouveret et al., 2017] showed several complexity and algorithmic results on envy-free, proportional and mmsallocations for different graphs of goods. Among others, they proved that if the graph of goods is a tree then an mmsallocation always exists and can be computed in polynomial time. Moreover, they gave an example demonstrating that for some choice of utility functions of the agents an mmsallocation does not exist when the graph of goods is a cycle.

The case of cycles as graphs of goods was thoroughly studied by [Lonc and Truszczynski, 2020]. They proved that in this case it is possible to guarantee to each agent the fraction √5-1 2 ≈ 0.62 of her maximin share. They also found an example showing that if the graph of goods is a cycle then for some choice of the utility functions of the agents in any allocation some agent receives at most 34 of her maximin share.

For arbitrary graphs of goods it is not known whether a positive fraction of the maximin share can be guaranteed. In this paper we prove that for a large class of graphs (including graphs with vertex degrees bounded by a constant) such guarantee indeed exists.

We focus on a wide class of graphs of goods called d-clawfree graphs. These are graphs that do not contain a d-edge star K1,d as an induced subgraph. Obviously, all graphs with maximum degree at most d are (d + 1)-claw-free. Probably the most interesting case concerns 3-claw-free graphs for which the approximation ratios that we prove are the largest. The class of 3-claw-free graphs (also called just claw-free graphs) is a large and important class of graphs widely studied in graph theory [Faudree et al., 1997; Chudnovsky and Seymour, 2010].

The problem of fair allocation for 3-claw-free graphs of goods is closely related to the following "edge variant" proposed by [Truszczynski, 2021]: Given a connected graph G, where edges represent goods, and a set of agents with utilities on edges, find a fair allocation of connected bundles of edges to agents. This problem is equivalent to the problem where vertices of a graph represent goods, considered for the graph of goods L(G) being the line graph of G. (In the line graph L(G) the edges of G are vertices and two vertices of L(G) are adjacent if the corresponding edges in G have a common vertex.) It is well-known that line graphs are 3-claw-free, which provides additional motivation to consider fair allocations for 3-claw-free graphs of goods.

The "edge variant" described above has the following natural interpretation: Several air carriers (agents) want to offer service between some cities. Connections (goods) between some pairs of cities, to be distributed among carriers, are edges of a graph whose vertices represent cities. The goal for each carrier is to have its connections form a connected subgraph of this graph. The goal of the authority constructing an allocation is to cover all edges by distributing them to carriers according to some fairness criterion.

Our contribution Intuitively, for proportional allocations, the smaller the values of goods relative to the agent's proportional share, the closer to the proportional allocation we can get. Our first main contribution quantifies this intuition for connected (d + 1)-claw-free graphs of goods, where d ≥ 2 (Theorem 1). More precisely, let Si be the total value to agent i of all vertices of the graph of goods. For every 0 < α ≤ 1 we find the largest value of β = β(α) such that for any connected (d+1)-claw-free graph of goods and any n agents for whom the values of single vertices are bounded by α Si n , there exists an allocation which assigns every agent i a connected bundle of value at least β Si n .

For mms-allocations, we prove that for any (d + 1)-clawfree graph of goods, any set of agents and d ≥ 2, there exists an allocation that guarantees each agent a bundle of value at least 1d of her maximin share (Theorem 2). In contrast to Theorem 1 for which we provide examples showing that the results are tight, we do not have a tightness result for Theorem 2.

Theorem 1 is a crucial ingredient of the proof of Theorem 2. We also use in this proof another result (Lemma 2) that allows us to reduce the problem of existence of an allocation assigning each agent a c fraction of her maximin share value when the agents are arbitrary, to the analogous problem when the agents are not arbitrary but their utility functions are bounded by the product of c and the maximin share value. Lemma 2, which is perhaps of an independent interest, applies not only to the class of (d + 1)-claw-free graphs but to any hereditary class of graphs.

Proofs of Theorem 2 and Lemma 2 require an extension of the problem of approximation of mms-allocations to disconnected graphs of goods. Therefore, we formulate and prove these results in this more general setting. In this extension we still require that bundles are sets of vertices of connected subgraphs of the graph of goods. However, we do not require that all vertices of the graph of goods are distributed to agents.

Even though mms-allocations for disconnected graphs of goods play an auxiliary role in this paper, we believe that studying such allocations is a natural and interesting direction for future research.

Related work The subject of fair division of a graph into connected bundles received a considerable attention in recent years (see a survey paper by [Suksompong, 2021]). We have already mentioned the papers by [Bouveret et al., 2017], which initiated research in this direction, and by [Lonc and Truszczynski, 2020] who examined the case when the graph of goods is a cycle. [Bei et al., 2022] studied the concept of price of connectivity for a graph G which they defined as the worst-case ratio between the maximin share computed with the restriction that all bundles are connected in G and without this restriction. Their result most closely related to the problems considered in this paper [Bei et al., 2022, Theorem 3.14] implies that for every graph of goods G there exists an allocation that guarantees each agent a bundle of value at least 1 m-n+1 of her maximin share, where n is the number of agents, m is the number of vertices in G and m ≥ n. This guarantee becomes, however, very weak when the size of the graph grows. Our Theorem 2 guarantees that, for a large class of graphs, a fraction of the maximin share independent on the size of the graph can be assigned to each agent. [Bil`o et al., 2022] and [Bei et al., 2022] proved several results on some relaxations of envy-free allocations with connected bundles. [Suksompong, 2019] showed several approximation results on envy-freeness, proportionality and equitability fairness criteria when the graph of goods is a path. [Igarashi and Peters, 2019] studied the problem of allocation of connected bundles that are Pareto optimal. [Bouveret et al., 2019] examined the problem of connected fair allocation of indivisible chores (i.e., items that yield disutility to the agents). [Greco and Scarcello, 2020] and [Deligkas et al., 2021] studied computational complexity issues pertaining to fair allocation on graphs.

2 Preliminaries

Let N = {1, . . . , n} be a set of agents and let V be a set of goods. We assume that the set of goods V is the vertex set of some undirected (and not necessarily connected) graph G called the graph of goods. Every subset of V inducing in G a connected subgraph is called a G-bundle (or just a bundle if the graph G is clear from the context).

For each agent i ∈ N there is a utility function ui which assigns non-negative real numbers to goods in V . We extend utility functions to subsets of V by assuming additivity, i.e., for a utility function ui defined on V and for every X ⊆ V , we define ui(X) := ∑v∈X ui(v). We say that a good v ∈ V (respectively, a set of goods X ⊆ V ) is of value x to agent i if ui(v) = x (resp. ui(X) = x).

In our setting by an allocation we mean an assignment of pairwise disjoint G-bundles to the agents in N. We do not assume here that every good of V is assigned to some agent. If it is then we call such an allocation complete. We represent allocations by sequences (A1, . . . , An), where each set Ai ⊆ V is a G-bundle assigned to agent i ∈ N.

Any family {P1, . . . , Pn} of pairwise disjoint G-bundles is called a (G, n)-packing. If, in addition, ⋃ni=1 Pi = V then such a (G, n)-packing is called a (G, n)-split of G. For an agent with utility function u we define the maximin share as

where the maximum is computed over all (G, n)-splits {P1, . . . , Pn} of G. We call a (G, n)-split for which the maximum is attained an mms-split.

If the graph of goods G is disconnected and has more than n components then no (G, n)-split exists so the maximin share is undefined. However, if we replace in the definition of the maximin share (G, n)-splits by (G, n)-packings then we get a parameter which is defined for every (not necessarily connected) graph G. Formally, for an agent with utility function u, the packing maximin share is:

where the maximum is computed over all (G, n)-packings {P1, . . . , Pn} of G. 1 We call a (G, n)-packing for which the maximum is attained an mms-packing. Obviously, pmms(n) (G, u) ≥ mms(n) (G, u) for every graph for which mms(n) (G, u) is defined.

An allocation (A1, . . . ,An) is an mms-allocation (resp. packing mms-allocation) if

1 The abbreviation PMMS has already been used in the literature for 'pairwise maximin share fairness' (e.g., see [Amanatidis et al., 2022]). These two meanings of this abbreviation should not be confused.

for every agent i ∈ N. For any c > 0, an allocation (A1, . . . ,An) is a c-mms allocation (resp. c-pmms allocation) if

for every agent i ∈ N with utility function ui.

For a connected graph of goods, we call an allocation (A1, . . . ,An) proportional (resp. c-proportional) if

for every agent i ∈ N with utility function ui.

Every c-proportional allocation is both a c-mms and a c-pmms allocation. Indeed, let {P1, . . . , Pn} be an mmspacking for a connected graph G and agent i. Then,

Let G be a connected graph of goods and let c > 0. An agent i ∈ N with utility function ui is c-proportionally bounded (resp. c-mms bounded) if

for every vertex v ∈ V (G).

Clearly, by the inequalities (1), every c-mms bounded agent is c-proportionally bounded.

To illustrate some of the concepts introduced above, let us consider the graph, say G, in Figure 1. The graph defines the set of goods V = {v1, . . . , v6} and their adjacency relation. The table in the figure shows two utility functions u1 and u2 of two different agents on the set of goods. By checking all (G, 2)-splits one can easily show that the family {{v1, v2}, {v3, v4, v5, v6}} is a (G, 2)- mms split for the utility function u1 with its bundles having values 8 and 10, respectively. Thus, mms(2) (G, u1) = 8. Similarly, mms(2) (G, u2) = 3, so the sequence ({v1, v2, v3}, {v4, v5, v6}) is an mms-allocation because u1({v1, v2, v3}) = 12 ≥ 8 and u2({v4, v5, v6}) = 3.

Since u1(V ) = 18 and u2(V ) = 10, the sequence ({v4, v5, v6}, {v1, v2, v3}) is a 23 -proportional allocation because u1({v4, v5, v6}) = 6 ≥ 2 3 · 18 2 and u2({v1, v2, v3}) =

7 ≥ 2 3 · 10 2 . The agent 1 is 12 -proportionally bounded because the lagest value of a single vertex for this agent is 4 ≤ 1 2 · 18 2 .

In this paper we use standard graph theoretic definitions and notation. In particular, we write V (G) for the set of vertices of a graph G. A subgraph H of a graph G is induced by a set of vertices X ⊆ V (G) if V (H) = X and a pair of vertices x, y ∈ V (H) is an edge in H if and only if xy is an edge in G. For any Y ⊆ V (G) we denote by G- Y the subgraph of G induced by the set of vertices V (G) - Y . If Y has only one vertex, say x, then we write G - x instead of G - {x}. A subgraph H of a graph G is spanning if V (H) = V (G).

By K1,m we denote a star with m edges. We say that a graph G is m-claw-free if G does not contain a copy of K1,m as an induced subgraph. A family of graphs G is hereditary if any induced subgraph of a graph in G is in G, too.

For connected graphs of goods the relationship between pmms-allocations and mms-allocations is very close. The proposition below explains this relationship.

Proposition 1. Let G be a connected graph of goods.

(i) For any utility function u defined on V (G) and a positive integer n, pmms(n) (G, u) = mms(n) (G, u).

(ii) For any c > 0 and any collection of n ≥ 1 agents a complete c-mms allocation exists if and only if a c-pmms allocation exists.

(iii) For any utility function u defined on V (G) and positive integers m, n such that m ≤ n, pmms(m) (G, u) ≥ pmms(n) (G, u). □

Simple proofs of parts (i) and (ii) base on an observation that for a connected graph G, every (G, n)-packing extends to a (G, n)-split. Part (iii) follows from the fact that by removing any n - m bundles from an mms-packing for G and n agents we get a (G,m)-packing with the value of every bundle at least pmms(n) (G, u).

3 Approximate Proportional Allocations

In this section we will show the following result.

Theorem 1. Let d ≥ 2 be an integer and 0 < α ≤ 1. Define

For every connected (d + 1)-claw-free graph of goods and every set of α-proportionally bounded agents there exists a β-proportional allocation.

Before we prove this theorem let us recall some basic definitions and facts from graph theory. A cut vertex of a connected graph is any vertex whose removal makes the graph disconnected. A connected graph is biconnected if it has no cut vertices. A block of a graph G is a maximal biconnected subgraph of G. It is easy to observe [Bondy and Murty, 2008, Proposition 5.3] that each two blocks of a graph G have at most one vertex in common and this vertex, if it exists, is a cut vertex of G.

Following the terminology introduced in [Bondy and Murty, 2008], for a connected graph G, we define B(G) to be a bipartite graph with bipartition (B,C), where B is the set of blocks of G and C is the set of cut vertices of G. A block B and a cut vertex v are adjacent in B(G) if B contains v. It is easy to observe that the graph B(G) is a tree. The blocks corresponding to the leaves of the tree B(G) are called end blocks of G. If G is not biconnected then it has at least two end blocks. Clearly, each end block contains exactly one cut vertex of G.

Every tree with more than one vertex contains a vertex whose all neighbors except for possibly one, are leaves. If G is not biconnected then B(G) has more than one vertex so it contains such a vertex, say v. Since leaves in B(G) are end blocks in G, the vertex v is a cut vertex of G such that all blocks containing v except for possibly one, are end blocks. We call such a cut vertex of G terminal.

A bipolar ordering of a graph G is an ordering v1, . . . , vm of all vertices of G such that for each i ∈ {1, . . . , m-1} both the graph induced in G by the set of vertices {v1, . . . , vi} and the graph induced in G by the set of vertices {vi+1, . . . , vm} are connected. This concept as well as the concepts of a block and a block decomposition were already used before in the context of fair division [Bei et al., 2022; Bil`o et al., 2022].

In the proof of Theorem 1 we apply the following lemma. A somewhat stronger version of this lemma, formulated in a different terminology, was proved by [Lempel et al., 1967].

Lemma 1. If G is a biconnected graph then for every vertex v of G there exists a bipolar ordering starting with v. □

We are ready to prove the main result of this section.

Proof of Theorem 1. We will prove this theorem here for 1d ≤ α ≤ 1. For this range of α, we have β = 1-α d-1 for every integer d ≥ 2. The proof for 0 < α < 1d is similar but differs by some details.

Our assumption that α ≥ 1d implies that 0 ≤ β ≤ 1d . In particular, β ≤ α.

The theorem is obviously true for one agent so we assume that there are at least two agents.

Suppose the theorem is false and let n ≥ 2 be the smallest number of agents such that for some connected (d + 1)- claw-free graph G of goods and a set N = {1, . . . , n} of α-proportionally bounded agents, a β-proportional allocation does not exist. Assume additionally that the graph G has the smallest number of vertices among such graphs.

For every agent i ∈ N, let ui be her utility function. To simplify notation, we define Si := ui(V (G)).

Let B be the set of blocks of G and let C be the set of its cut vertices. If G is not biconnected then it contains a terminal cut vertex, say v. Let B0,B1, . . . ,Bs be the blocks in G containing v indexed so that B1, . . . ,Bs are end blocks (B0 may but does not have to be an end block). Obviously, v is the only cut vertex contained in the blocks B1, . . . ,Bs. Let B = V (B1)∪. . .∪V (Bs). Clearly, s+1 ≤ d because otherwise v is the center of an induced star K1,d+1, a contradiction as G is (d + 1)-claw-free. Moreover, by the definition of v, the graph G - B is connected.

We consider three cases.

Case 1. G is biconnected or G is not biconnected but for some terminal cut vertex v, some end block Br containing v and some agent i, we have ui(V (Br - v)) > β · Si n .

If G is biconnected then we define H := G, i is an arbitrary agent and v is an arbitrary vertex of G. If G is not biconnected then we define H := Br. In the former case, ui(V (H-v)) = Si - ui(v) ≥ Si - α Si n = (n - α) Si n > (1 - α) Si n = β(d - 1) Si n ≥ β Si n because the agents are α-proportionally bounded and d ≥ 2.

By Lemma 1, there exists a bipolar ordering v1, v2, . . . , vm, where m = |V (H)|, of vertices of H such that v1 = v.

Let ℓ > 1 be the largest t such that there is an agent, say k ∈ N, for whom the value of the set {vt, vt+1, . . . , vm} is at least β Sk n . Clearly, ℓ is well-defined because the value for the agent i of the set {v2, v3, . . . , vm} = V (H - v) is larger than β Si n . By the definition of a bipolar ordering, the graph induced in G by the set of vertices L = {vℓ, vℓ+1, . . . , vm} is connected. We assign this set to the agent k.

By the definition of ℓ the value of the set {vℓ+1vℓ+2, . . . , vm} for each agent j ∈ N is smaller than β Sj n . Since uj(vℓ) ≤ α Sj n for every agent j, we have uj(L) < (β + α) Sj n = (1 - β(d - 2)) Sj n ≤ Sj n as d ≥ 2. By the definition of a bipolar ordering, the graph G - L is connected.

Let G′ = G - L and N ′ = N - {k}. For every agent j ∈ N ′ the total value of all vertices of G′ is S′j = Sj - uj(L) > Sj - Sj n = (n-1)Sj n , so for each vertex x ∈ V (G′ ), we have uj(x) ≤ α Sj n ≤ α S′j n-1 . Thus, the utility functions uj restricted to the set of vertices of G′ are α-proportionally bounded for each agent j ∈ N ′ . By minimality of n there exists a β-proportional allocation for the graph of goods G′ and the set of agents N ′ . In this allocation every agent j ∈ N ′ receives a bundle of goods of value at least β S′j n-1 ≥ β Sj n . This allocation together with the set L assigned to the agent k defines a β-proportional allocation of the vertices of G to the agents of N, a contradiction which completes the proof in this case.

Case 2. G is not biconnected and for each agent i ∈ N, ui(B) ≤ α Si n .

Let G′ be the graph obtained from G by removing the vertices of B - {v}. Clearly, the graph G′ is connected. For each agent i ∈ N we define a new utility function u′i on the set V (G′ ) as follows: u′i (v) := ui(B) ≤ α Si n and u′i (x) := ui(x) for all x ̸= v.

By the minimality of G, there is a β-proportional allocation (A1, . . . ,An) for the graph of goods G′ and the agents of N with the utility functions u′i which assigns the bundle Ai to agent i, for each i ∈ N. We add to the bundle, say Aj, containing v the vertices of B - {v}. This way we get a β-proportional allocation for the graph of goods G and the agents of N with the utility functions ui, a contradiction with the definition of G.

Case 3. G is not biconnected and there is an agent k ∈ N with uk(B) > α Sk n .

Clearly, uk(B) > β Sk n because α ≥ β. We can assume that for every agent i ∈ N and every r ∈ {1, . . . , s}, we have ui(V (Br-v)) ≤ β Si n because otherwise the condition in Case 1 is satisfied.

Thus, for every agent i

because s + 1 ≤ d.

We assign the set B to the agent k.

Let G′ be the graph obtained from G by removing the set of vertices B and let N ′ = N - {k}. By the definition of B, the graph G′ is connected. For every agent i ∈ N ′ the total value of all vertices of G′ is S′ i = Si - ui(B) ≥ Si - Si n = (n-1)Si n so for each vertex x ∈ G′ , we have ui(x) ≤ α Si n ≤ α S′i n-1 . By the minimality of n, there exists a β-proportional allocation for the graph of goods G′ assigning each agent i ∈ N ′ = N - {k} a bundle of value at least β S′i n-1 ≥ β Si n . This allocation together with the set B assigned to agent k defines a β-proportional allocation for the graph of goods G and the agents of N, a contradiction with the definition of G. □

Theorem 1 is sharp. More precisely, for every d ≥ 2, 0 < α ≤ 1 and ε > 0, there is an example of a (d + 1)-claw-free graph G = G(d, α, ε) and a set of α-proportionally bounded agents such that there is no (β + ε)-proportional allocation, where β is defined by the equality (2). The example described below shows this sharpness when β = 1-α d-1 , i.e., for d ≥ 3 and 0 < α ≤ 1 and for d = 2 and 1 2 ≤ α ≤ 1. We also have an example demonstrating sharpness of Theorem 1 for d = 2 and α < 12 but we do not present it here.

We construct the graph G in the following way. Let T be a tree consisting of d-1 paths, each with p = ⌈(β + ε/2)/α⌉+ 1 vertices, sharing one common vertex which is an end of each path. We call this vertex the center of T. We define G to be the tree obtained from k ≥ max ( 2 (d-1)ε , 2(β+ε) ε ) disjoint copies T1, . . . , Tk of the tree T by joining with an edge the center of Ti+1 with one of the leaves of Ti, for each i = 1, . . . , k - 1 (see Figure 2). Clearly, the graph G is connected and (d + 1)-claw-free.

There are n = k + 1 agents with the same utility function assigning the value α to the k vertices which are centers of the trees Ti and the value β+ε/2 p-1 = β+ε/2 ⌈(β+ε/2)/α⌉ ≤ α to the remaining k(p - 1)(d - 1) vertices of G. The total value of all vertices of G is equal to S = kα + k(d - 1)(β + ε/2) =

k(α + (d - 1)β) + k(d - 1)ε/2 = k + k(d - 1)ε/2 ≥ k for each agent. By the inequality k ≥ 2 (d-1)ε , it follows that β+ε/2 p-1 ≤ α = α k+1 n ≤ α k+k(d-1)ε/2 n = α Sn so the agents are α-proportionally bounded.

To show that there is no (β+ε)-proportional allocation for our n agents and the graph G we observe that the total value of every connected subgraph of G which does not contain the center of any tree Ti is at most β + ε/2. Since there are k = n - 1 centers only, in any allocation of bundles of G to n agents there is an agent who does not receive the center of any tree Ti. Thus, this agent gets a bundle of value at most β + ε/2. Since n = k + 1 > 2(β+ε) ε and S ≥ k, we have β + ε/2 < (β + ε)(1 - 1n ) = (β + ε) kn ≤ (β + ε) Sn . Thus, no (β + ε)-proportional allocation exists.

We will now extract from Theorem 1 several corollaries, including the result that will be of use when dealing with mms-allocations in Section 4.

Applying Theorem 1 for α = 1d we get the following statement.

Corollary 1. Let d ≥ 2 be an integer. For every connected (d + 1)-claw-free graph of goods and every set of 1d - proportionally bounded agents there exists a 1d -proportional allocation. □

It follows easily from Theorem 1 that Corollary 1 is best possible in the sense that there is no constant c > 1d such that for every connected (d + 1)-claw-free graph of goods and any set of c-proportionally bounded agents there exists a c-proportional allocation.

Theorem 1 can be generalized in the following way.

Corollary 2. Let d ≥ 2 be an integer and 0 < α ≤ 1. Moreover, let β be defined by the equality (2). If a graph G has a (d + 1)-claw-free connected spanning subgraph then, for any set of α-proportionally bounded agents, there exists a β-proportional allocation for the graph of goods G.

Proof. This corollary follows immediately from Theorem 1 and the observation that for any β ≥ 0 a β-proportional allocation for a spanning connected subgraph of G is a βproportional allocation for the graph G.

In Corollary 2 the largest value of the approximation factor is achieved for d = 2 and it is equal to 12 . Since a path is obviously 3-claw-free, we have the following corollary which can also be easily proved directly.

Corollary 3. If the graph of goods G has a Hamilton path then for any set of 1 2 -proportionally bounded agents there exists a 1 2 -proportional allocation. □

4 Approximate Mms-Allocations

The following theorem is the main result of this section.

Theorem 2. Let d ≥ 2 be an integer. For every connected (d + 1)-claw-free graph of goods and any set of agents there exists a complete 1d -mms allocation.

In fact, we will prove a stronger version of this theorem for graphs which do not have to be connected.

Theorem 2'. Let d ≥ 2 be an integer. For every (d + 1)- claw-free graph of goods and any set of agents there exists a 1d -pmms allocation.

Theorem 2 follows immediately from Theorem 2' by Proposition 1 (i) and (ii).

We first prove a general lemma which reduces the problem of the existence of a c-pmms allocation for arbitrary agents to the existence of a c-mms allocation for c-mms bounded agents, if the graphs of goods belong to a hereditary class of graphs. We will apply this lemma in the proof of Theorem 2' for the class of (d + 1)-claw-free graphs which is, obviously, hereditary. However, it is worth noting that there are many other important hereditary classes of graphs (e.g., the class of all graphs, the class of planar graphs, the class of bipartite graphs, the class of perfect graphs).

Lemma 2. Let G be a fixed hereditary class of graphs and let c > 0 be a fixed real. If there exists a c-mms allocation for any connected graph in G and any set of c-mms bounded agents then there exists a c-pmms allocation for any graph of goods in G and any set of agents.

Proof. Consider an arbitrary graph of goods G ∈ G and an arbitrary set N = {1, . . . , n} of agents. Let, for each agent i ∈ N, ui be the utility function of i and let Πi be an mms-packing for this agent. To simplify notation we define pmmsi := pmms(n) (G, ui) for every agent i ∈ N. We need to construct an allocation assigning each agent i a bundle of value at least c · pmmsi to this agent.

We define X := {x1, . . . , xℓ} to be a maximal with respect to inclusion (and possibly empty) set of pairwise different vertices of G such that every vertex xj is of value at least c · pmmsij to some agent ij and the agents i1, . . . , iℓ are pairwise different. Every agent ij receives the vertex xj in our allocation.

It remains to show that there is an allocation assigning to each agent i ∈ N ′ = N - {i1, . . . , iℓ} a bundle inducing a connected subgraph of G - X which is of value at least c · pmmsi to this agent. By the maximality of X, for every vertex v ∈ V (G-X) and every agent i ∈ N ′ ,

Since |X| = ℓ, for every agent i ∈ N ′ there are at least n- ℓ bundles in Πi which do not intersect X.

Let G1, . . . ,Gs be the components of G - X. Let Πji be the set of bundles in Πi that are contained in V (Gj) and let f(i, j) be the number of such bundles. Clearly, Πji is a (Gj , f(i, j))-packing. Moreover, ∑sj=1 f(i, j) ≥ n - ℓ for each agent i ∈ N ′ . We observe that, by Proposition 1 (i) and the fact that the value of each of f(i, j) bundles in Πji is at least pmmsi for agent i, we have

for every agent i ∈ N ′ and every j ∈ {1, . . . , s}.

Claim. Let Ij ⊆ N ′ be a set of agents such that f(i, j) ≥ |Ij | for each agent i ∈ Ij. Then, there is a c-mms allocation for the graph of goods Gj and the set of agents Ij .

Proof of the Claim. We observe that the agents of Ij are cmms bounded with respect to the graph of goods Gj and the Algorithm 1 al locate (N ′ , G - X, c)

utility functions restricted to V (Gj). Indeed, applying in turn the inequalities (3), (4) and Proposition 1 (iii), for every vertex v ∈ V (Gj) we get

Since G is a hereditary class of graphs, Gj ∈ G. Thus, by our lemma assumption, there is a c-mms allocation for the graph of goods Gj and the set of agents Ij. ■

We denote by A(Ij,Gj) the allocation whose existence is guaranteed by the Claim.

We shall prove that the algorithm allocate shown in the figure Algorithm 1 produces the required c-pmms allocation of the vertices of G - X to the agents of N ′ . In the jth pass of the loop of this algorithm bundles of vertices of the component Gj of G-X are distributed to agents. First, we sort (line 3) the agents i which have not got their bundles yet non increasingly according to the number f(i, j) of bundles in their mms-packings Πi which are contained in Gj. We denote the ℓth agent in this sorting by ijℓ . Next, we define the set Ij which consists of kj initial agents in the sorting (line 5), where kj is the largest p such that f(ijp , j) ≥ p (line 4) . We observe that, by the definition of kj, f(i, j) ≥ kj = |Ij| for every agent i ∈ Ij. Thus, it follows from the Claim that there is an allocation A(Ij,Gj) assigning to each agent i ∈ Ij a bundle of value at least

We applied here, in turn, Proposition 1 (i), (iii) and the inequality (4). We distribute the vertices of Gj to agents of Ij according to the allocation A(Ij,Gj) (line 6) and the agents of Ij quit the game (line 7).

It remains to show that when the algorithm stops, the set T is empty, i.e., all agents received their bundles. Suppose otherwise. Let i be an agent who is still in the set T when the algorithm stops. Let Tj be the set T at start of the jth pass of the loop of our algorithm. By the definition of kj, for all agents t ∈ Tj, which are not included in the set Ij (so do not receive a bundle) in the jth pass of the loop, we have f(t, j) < kj + 1, i.e., f(t, j) ≤ kj . Since the agent i was not allocated a bundle in any pass of the loop, we have f(i, j) ≤ kj for all j's. Clearly, ∑sj=1 kj is the total number of agents who received their bundles when the algorithm stops. Hence,

a contradiction. Thus, all agents received their bundles when the algorithm stops.

Theorem 2' follows now from Lemma 2 and Corollary 1.

Proof of Theorem 2'. Let G be the class of (d + 1)-claw-free graphs. Since G is hereditary, by Lemma 2, it suffices to show our theorem for connected (d+1)-claw-free graphs of goods G and 1d -mms bounded agents.

By Corollary 1, for every connected (d + 1)-claw-free graph of goods G and any set of 1d -proportionally bounded agents, there exists a 1d -proportional allocation. Since c-mms bounded agents are c-proportionally bounded for any c > 0, a 1d -proportional allocation exists for 1d -mms bounded agents and the graph of goods G. Our theorem follows now from the fact that a c-proportional allocation is a c-mms allocation, for any c > 0. □

5 Final Remarks and Open Problems

As we mentioned in the Introduction, we do not know if the approximation ratio 1d in Theorem 2 can be improved, even in the case of 3-claw-free graphs, i.e., for d = 2.

Problem 1. What is the largest constant c such that for each 3-claw-free graph of goods and any set of agents there exists a c-mms allocation?

It was shown [Lonc and Truszczynski, 2020, p. 639] that if the graph of goods is a cycle with 12 vertices (which is obviously 3-claw-free) then for some 6 agents no c-mms allocation exists for any c > 34 . This statement and Theorem 2 imply that the constant c in Problem 1 satisfies the inequalities 12 ≤ c ≤ 3 4 .

A similar question as the one in Problem 1 can be asked for arbitrary graphs. In this case, however, we do not even know whether c > 0.

Problem 2. Is there an absolute constant c > 0 such that for each graph of goods and any set of agents there exists a c-mms allocation?

We do not know any example of a graph and a collection of agents such that for this graph and these agents no 34 -mms allocation exists. Thus, it is conceivable that the constant c in Problem 2 can be as large as 34 .

Finally, there are some computational complexity issues related to the subject of this paper. While the proof of Theorem 1 can be easily turned into a polynomial time algorithm constructing a β-proportional allocation for α-proportionally bounded agents, it is not the case for the proof of Theorem 2. In the latter proof we use the value of packing maximin share which is NP-hard to compute even for complete graphs [Bouveret and Lemaˆıtre, 2016]. Finding a polynomial time algorithm for constructing a 1d -mms allocation for (d + 1)- claw-free graphs of goods will be a subject of our future research.

Acknowledgements

The author thanks Miroslaw Truszczynski for his comments which allowed to improve significantly the way of presentation of the results of this paper.