Fair Division of a Graph

1 Introduction

The department of computer science at University X is about to move to a new building. Each research group has preferences over rooms, but it would also be desirable for each group to have a contiguous set of offices, to facilitate communication. This situation can be seen as a problem of fair division (where agents are research groups and items are offices) with an additional connectivity requirement. This constraint could be captured by an undirected graph whose vertices are rooms (items) and there is an edge between two vertices if the respective rooms are adjacent; each agent should obtain a connected piece of this graph.

In this paper, we introduce and study a formal model for such scenarios. Specifically, we consider the problem of fair allocation of indivisible items in settings where there is a graph capturing the dependency relation between items, and each agent's share has to be connected in this graph. Besides the example in the first paragraph, our model captures a variety of applications, such as time-sharing a processor where tasks can be switched only at pre-defined times, allocating a set of indivisible land plots, or assigning administrative duties

Dominik Peters

University of Oxford, UK dominik.peters@cs.ox.ac.uk

to members of an academic department, where there are dependencies among tasks (e.g., dealing with incoming foreign students has some overlap with preparing study programmes in foreign languages, but not with fire safety).

Our contribution We propose a framework for fair division under connectivity constraints, and investigate the complexity of finding good allocations in this framework according to three well-studied solution concepts: proportionality, envyfreeness (in conjunction with completeness), and maximin share guarantee. We focus on additive utility functions.

For proportionality and envy-freeness, we obtain hardness results even for very simple graphs: finding proportional allocations turns out to be NP-hard even for paths, and finding complete envy-free allocations is NP-hard both for paths and for stars. Nevertheless, we also obtain some positive results for these solution concepts. In particular, both proportional and complete envy-free allocations can be found efficiently when the graph is a path and agents can be classified into a small number of types, where agents are said to have the same type when they have the same preferences over items. 1 If we assume that not just the number of player types, but the actual number of players is small, we obtain an efficient algorithm for finding proportional allocations on arbitrary trees.

Recently, several papers have studied the concept of the maximin share guarantee (MMS) [Budish, 2011], which captures a desirable property of allocations that is easy to achieve for divisible items via cut-and-choose protocols. For indivisible goods, such allocations need not exist [Procaccia and Wang, 2014; Kurokawa et al., 2016]. We prove a strong positive result for our setting: an MMS allocation always exists if the underlying graph is a tree, and can be computed efficiently. Our algorithm is an adaptation of the classic last-diminisher procedure for the divisible case. In contrast, we provide an example where the underlying graph is a cycle of length 8 and there is no MMS allocation. We believe that these results are useful for developing an intuitive understanding of the concept of MMS; in particular, our example for the cycle is much simpler than known examples of instances with no MMS allocation in the absence of graph constraints.

1 The same parameter was used by Brˆanzei et al. [2016] to obtain results for maximizing social welfare; similar ideas have been used in the context of coalition formation [Shrot et al., 2010; Aziz and De Keijzer, 2011].

Related work Fair allocation of indivisible items has received a considerable amount of attention in the (computational) social choice literature; we refer the reader to a survey by [Bouveret et al., 2016]. However, ours is the first attempt to impose a graph-based constraint on players' bundles. In contrast, in the context of fair allocation of divisible items (also known as cake-cutting) contiguity is a well-studied requirement. For instance, [Stromquist, 1980] showed that an envy-free division in which each player receives a single contiguous piece always exists, but it cannot be obtained by a finite algorithm, even for three players [Stromquist, 2008]. These results extend to equitable division with contiguous pieces [Cechl´arov´a et al., 2013; Aumann and Dombb, 2015; Cechl´arov´a and Pill´arov´a, 2012]. [Bei et al., 2012] consider fair allocations with contiguous pieces that approximately maximize social welfare; [Aumann et al., 2013] investigate a variant of this question without fairness constraints.

[Conitzer et al., 2004] analyze a combinatorial auction setting that is somewhat similar to ours: in their model, too, there is an undirected graph describing connections between items, and each agent's bid is connected with respect to this graph. They provide an algorithm for finding an allocation that maximizes the social welfare and is in FPT with respect to the treewidth of the item graph. [Aumann et al., 2015] consider auctioning of a time interval, and obtain results both for the case of pre-determined time slots (which corresponds to the model of [Conitzer et al., 2004], with the item graph being a line) and for the case where the interval can be cut into arbitrary slots (which is similar in spirit to cake-cutting). However, neither paper considers any fairness constraints.

Two very recent papers, like ours, combine graphs and fair division. [Chevaleyre et al., 2017] consider the setting where agents are located in vertices of a graph. Each agent has an initial endowment of goods and can trade with her neighbors in the graph. The authors ask what outcomes can be achieved by a sequence of mutually beneficial deals. In the work of [Abebe et al., 2017], the graph describes a visibility relation: agents are located in vertices and an agent can only envy agents who are adjacent to her. In contrast, in our model graphs represent the relationship between items rather than agents.

2 Our Model

We study fair allocation of indivisible goods where each allocated bundle is connected in an underlying graph.

Definition 2.1. An instance of the connected fair division problem (CFD) is a triple I = (G, N, U) where

• G = (V, E) is an undirected graph,
• N = {1, . . . , n} is a set of players, or agents,
• U is an n-tuple of utility functions ui : V →R⩾0, where ∑v∈V ui(v) = 1 for each i ∈ N.

We refer to elements of V as items, and denote the number of items by m.

Note that when G is a clique, CFD is equivalent to the classic problem of fair allocation with indivisible items.

For each X ⊆ V , we set ui(X) = ∑v∈X ui(v), so valuations in this paper are always additive. Two players i, j ∈ N

are of the same type if ui(v) = uj(v) for all v ∈ V . We denote the number of player types in a given instance by p.

An allocation is a function π : N → 2V assigning each player a bundle of items. An allocation π is valid if for each player i ∈ N the bundle π(i) is connected in G and no item is allocated twice, so that π(i) ∩ π(j) = ∅ for each pair of distinct players i, j ∈ N. We say that a valid allocation π is

• proportional if ui(π(i)) ⩾ 1n for all i ∈ N,
• envy-free if ui(π(i)) ⩾ ui(π(j)) for all i, j ∈ N, and
• complete if ⋃i∈N π(i) = V .

Notice that an allocation that gives everybody an empty bundle is envy-free, so, to better express the idea of fairness, the requirement of envy-freeness is typically accompanied by completeness or Pareto-optimality.

We also consider maximin share (MMS) allocations [Budish, 2011], adapting the usual definition to our setting as follows. Given an instance I = (G, N, U) of CFD with G = (V, E), let Πn denote the space of all partitions of V into n connected pieces. The maximin share guarantee of a player i ∈ N is

Note that since we are only taking the maximum over connected partitions, these values may be lower than in the general setting without graph constraints. A valid allocation π is a maximin share (MMS) allocation if we have ui(π(i)) ⩾ mmsi(I) for each player i ∈ N.

We consider the following computational problems that all take an instance I = (G, N, U) of the connected fair division problem as input. For computational purposes, we assume that utility functions take values in Q. Hardness results will use unary encodings of utility values (unless noted otherwise).

• PROP-CFD: Does I admit a proportional valid allocation?
• COMPLETE-EF-CFD: Does I admit a complete envy-free valid allocation?
• MMS-CFD: Does I admit an MMS allocation?

We note that, given a valid allocation, one can check in polynomial time whether it is proportional or envy-free; thus, the respective computational problems are in NP.

In what follows, we assume that the number of items m is at least as large as the number of players n, since otherwise at least one player gets nothing. Also, given a positive integer k, we write [k] to denote the set {1, . . . , k}.

3 Proportionality

We start with the bad news: it is hard to find a proportional allocation, even if the graph G is a path.

Theorem3.1. PROP-CFD is NP-complete even if G is a path.

Proof. We describe a polynomial-time reduction from the NP-complete problem EXACT-3-COVER (X3C) [Garey and Johnson, 1979]. Recall that an instance of X3C is given by a set of elements X = {x1, x2, . . . , x3s} and a family T = {T1, T2, . . . , Tr} of three-element subsets of X; it is a 'yes'-instance if and only if X can be covered by s sets from T .

This problem remains NP-complete if for each element x ∈ X its frequency px = |{T ∈ T : x ∈ T}| is at most 3.

Consider an instance J = (X, T ) of X3C; for each T ∈ T , we denote the elements of T by x1T , x2T , x3T . We construct an instance I of PROP-CFD as follows. There are three small vertices v1T , v2T , v3T for each set T ∈ T , a set of s big vertices B = {b1, b2, . . . , bs} and a dummy vertex w. The edges of G are shown in Figure 1.

There is one player iT for each T ∈ T , one player ix for each x ∈ X and one dummy player d. Hence the total number of players is n = 3s + r + 1. Define the utilities as:

By construction ui(V ) = 1 for each i ∈ N. As player d assigns a positive value to vertex w only, she must receive this vertex in every proportional allocation. Given that w is allocated to d, an allocation is proportional if and only if each player ix receives a small vertex vkT such that x ∈ T , and each player iT receives vertices v1T , v2T , v3T (a triple interval) or a vertex from B.

Suppose that J admits a cover T ′ of size s. Let µ be a matching between T ′ and B. Assign intervals to players ix and iT as follows:

• For each T ∈ T ′ , player iT is assigned to vertex µ(T).
• For each T /∈ T ′ , player iT is assigned to the triple interval v1T , v2T , v3T .
• Each player ix is assigned to the small vertex vkT such that x = xkT and T ∈ T ′ .

Then each player is assigned one connected piece and her value for that piece is at least 1/n.

Conversely, suppose that I admits a proportional valid allocation. As |B| = s, the number of T-players assigned to triple intervals is r - s. Hence, the number of triple intervals available for x-players is s, and the respective sets constitute an exact cover for X.

In contrast, if G is a star, finding a proportional allocation is easy. Our algorithm for this problem, as well as all other algorithms in this section, use matching techniques and can be adapted to also find valid allocations that maximize egalitarian welfare, i.e., the utility of the worst-off agent.

Theorem 3.2. PROP-CFD is solvable in polynomial time if G is a star.

3.1 Bounded Number of Agent Types

If the underlying graph is a path and all players are of the same type, then a simple greedy algorithm finds a proportional allocation (or reports that none exists) in linear time: we build connected pieces one by one, by moving along the path from left to right and adding vertices to the current piece until its value to a player reaches 1/n; at this point we start building a new piece. This procedure creates at most n pieces; a proportional valid allocation exists if and only if it creates exactly n pieces. More generally, if G is a path and the number of agent types is bounded by a constant, a simple dynamic program can check the existence of a proportional allocation in polynomial time. A problem is slice-wise polynomial (XP) with respect to a parameter k if each instance I of this problem can be solved in time |I|f(k) where f is a computable function.

Theorem 3.3. PROP-CFD is in XP with respect to the number of player types p if G is a path.

Proof. Let G = (V,E), where V = {v1, . . . , vm}, E = {{vi, vi+1} : i ∈ [m - 1]}. Suppose there are nt players of type t, for t ∈ [p]. We say that a player is happy if she gets a connected piece of value at least 1/n. Let V0 = ∅ and Vi = {v1, . . . , vi}, i > 1.

For i = 0, . . . ,m, and a collection of indices j1, . . . , jp such that 0 ⩽ jk ⩽ n for each k ∈ [p], let Ai[j1, . . . , jp] = 1 if there exists a valid partial allocation π of Vi with jk happy agents of type k, k ∈ [p], and let Ai[j1, . . . , jp] = 0 otherwise. Clearly, A0[j1, . . . , jp] = 1 if and only if jk = 0 for all k ∈ [p]. For i = 1, . . . ,m, we have Ai[j1, . . . , jp] = 1 if and only if there exists a value s < i and t ∈ [p] such that As[j1, . . . , jt - 1, . . . , jp] = 1 and a player of type t values the set of items {vs+1, . . . , vi} at 1/n or higher.

A proportional allocation exists if Am[j1, . . . , jp] = 1 for some collection of indices j1, . . . , jp such that jt ⩾ nt for all t ∈ [p]. There are at most (m+1)(n+1)p values to compute, and each value can be found in time O(mt) using unit cost arithmetics. Thus, PROP-CFD is in XP with respect to p.

3.2 Bounded Number of Agents

Theorem 3.3 immediately implies that PROP-CFD can be solved in polynomial time if the number of agents n is bounded by a constant and the graph is a path. A more careful argument shows that PROP-CFD on trees, is, in fact, fixed parameter tractable with respect to this (weaker) parameter. A problem is fixed parameter tractable (FPT) with respect to a parameter k if each instance I of this problem can be solved in time f(k)poly(|I|) where f is a function that depends only on k.

Theorem 3.4. PROP-CFD is in FPT with respect to n when G is a tree.

Proof sketch. We turn G into a rooted tree by choosing an arbitrary node r as the root. Given a vertex v, we denote by C(v) the set of children of v and by D(v) the set of descendants of v (including v) in the rooted tree.

For each v ∈ V , S ⊊ N, and i ∈ N \ S, let Πi,v,S be the set of all valid allocations π : S ∪ {i} → 2D(v) with v ∈ π(i) and uj(π(j)) ⩾ 1/n for all j ∈ S, and define

by convention, Av[i, S] = -∞ when Πi,v,S is empty. Note that we have a 'yes'-instance of PROP-CFD if and only if Ar[i, N \ {i}] ⩾ 1/n for some i ∈ N.

To complete the proof, we show that the values Av[i, S] can be efficiently computed in a bottom-up manner. We observe that for every internal vertex v of the rooted tree, in each allocation π ∈ Πi,v,S the bundle of each player in S is fully contained in a subtree D(z) for some z ∈ C(v). This induces a partition of players in S into |C(v)| groups. We can go through all possible partitions of S with at most |C(v)| parts and try to find a valid allocation compatible with this partition, maximizing the utility of each agent. Such an allocation can be found efficiently by solving a matching problem. We omit the details due to space constraints.

We note that placing strong constraints on the underlying graph is crucial for obtaining the easiness results in Theorems 3.3 and 3.4. This is illustrated by the following simple proposition, obtained by adapting a proof by [Demko and Hill, 1998] for the standard setting (with no graph constraints), which shows that the XP membership with respect to the number of players/types cannot be extended to arbitrary graphs.

Proposition 3.5. When utilities are encoded in binary, PROPCFD is NP-complete even for n = 2, p = 1, and even if the underlying graph G is bipartite.

4 Envy-freeness

Envy-freeness turns out to be computationally more challenging than proportionality: finding a complete envy-free allocation is NP-hard even if the underlying graph is a star (for complete graphs, this result is shown by Lipton et al. [2004]).

Theorem 4.1. COMPLETE-EF-CFD is NP-complete even if G is a star.

Proof. Our hardness proof proceeds by a reduction from INDEPENDENT SET. Recall that an instance of INDEPENDENT SET is given by an undirected graph (W, L) and an integer k; it is a 'yes'-instance if and only if (W, L) contains an independent set of size k. Given an instance (W, L) of INDEPENDENT SET, we construct an instance of COMPLETE-EF-CFD as follows. For each vertex w ∈ W we create an item w and a player iw. Similarly, for each edge ℓ ∈ L we create an item ℓ and a player iℓ. We also create a set of dummy items D with |D| = k, as well as an item c and a player ic. The graph G is a star with center c and set of leaves W ∪ L ∪ D. Finally, define utility functions as follows.

• For each w ∈ W, we set uiw (w) = 1/(k + 1) and uiw (d) = 1/(k + 1) for each d ∈ D.
• For each ℓ ∈ L with ℓ = {x, y}, we set uiℓ (ℓ) = 3/7, uiℓ (x) = uiℓ (y) = 2/7.
• We set uic (c) = 1.
• All other utilities are set to 0.

We will now argue that there exists an independent set of size k in the graph (W, L) if and only if this instance of CFD admits a complete envy-free valid allocation.

Suppose there exists an independent set X ⊆ W of size k. We construct an allocation π as follows:

• player ic receives X ∪ {c};
• for w ∈W \X, player iw receives w;
• for w ∈ X, player iw receives one item in D;
• for ℓ ∈ L, player iℓ receives ℓ.

Clearly, π is a complete valid allocation. It remains to show that π is envy-free. First, player ic does not envy any other player since she receives all her positive-utility items. Vertex players {iw : w ∈ W} receive utility 1/(k + 1) in π; they could only envy someone who has multiple dummies, but no one does. Edge players {iℓ : ℓ ∈ L} receive utility 3/7 in π; the only way an edge player iℓ could envy another player is if that player got both items corresponding to endpoints of ℓ. But the only player who receives more than one vertex item is player ic whose items correspond to an independent set. So no player envies anyone, and π is envy-free.

Conversely, suppose that there is a complete envy-free valid allocation π. By completeness, π allocates the central piece c to some player. If ic does not receive c then she would envy the player who receives it; so c ∈ π(ic). Thus, every other player receives at most one item. Since π is complete, this means that ic gets at least k leaf items. Further, if iℓ does not receive ℓ, she would envy the player who receives it, so π(iℓ) = {ℓ}. Next, consider the bundle of player ic. If it contains more than one dummy item, vertex players would envy ic. Thus, it contains at least one item w ∈ W. If π(ic) also contains a dummy item, iw would envy ic, so π(ic) consists of c and k vertex items. Now, if there is an edge ℓ = (x, y) such that x, y ∈ π(ic), then player iℓ envies ic. Hence, π(ic) \ {c} forms an independent set of size k in (W, L).

We also obtain a hardness result for paths; the proof is similar to that of Theorem 3.1.

Theorem 4.2. The problem COMPLETE-EF-CFD is NPcomplete even if G is a path.

On the positive side, just as for PROP-CFD, the problem COMPLETE-EF-CFD is also in XP with respect to the number of player types p, as long as G is a path.

Theorem 4.3. COMPLETE-EF-CFD is in XP with respect to the number of player types p if G is a path.

Proof sketch. Note that for an allocation to be envy-free, all pieces assigned to players of a given type should have the same value to players of that type. When G is a path, there are only (m+1 2 ) ⩽ m2 different connected bundles. Hence there are at most m2 many possibilities for the utility that a player of a given type can obtain in a valid allocation.

Our algorithm works as follows. For each player type, it guesses the utility that players of that type assign to their pieces (this guessing can be implemented by going over all possibilities, as there are at most (m2 )p of them). It then proceeds similarly to the dynamic programming algorithm in the proof of Theorem 3.3; the only difference is that, when creating a piece of the form {vs+1, . . . , vi} for a player of a given type, it checks that the utility of that player type for this piece is what it guessed for that type, and that other players' utility for this piece is at most their guessed utility.

5 Maximin Share Guarantee

After Budish [2011] introduced the notion of an MMS allocation, it was open for some time whether every allocation problem (without connectivity constraints) admitted such an allocation. Procaccia and Wang [2014] found a counterexample. A family of more compact examples was found by Kurokawa et al. [2016]; these examples implicitly use an underlying grid graph; hence, for grid graphs, existence of MMS allocations is not guaranteed. Here, we show that for trees an MMS allocation always exists. Our argument is constructive, and our algorithm corresponds to a discrete version of the last-diminisher method, which ensures proportionality while cutting a divisible resource [see, e.g., Brams and Taylor, 1996]. This method proceeds by letting one player identify a bundle of items. Every other player, in order, then has the option to diminish this bundle by removing some of the items from it. The last player who chose to diminish is allocated the (diminished) bundle. The same procedure is then applied to divide the rest of the cake among the remaining n - 1 players.

We first describe an efficient procedure that guarantees each player a pre-specified level of utility.

Proposition 5.1. Let I = (G,N, U) be an instance of CFD where G is a tree and let (qi)i∈N be an n-tuple of rational numbers. If mmsi(I) ⩾ qi for all i ∈ N, then there exists a valid allocation π such that each player i ∈ N receives the bundle of value at least qi, i.e., ui(π(i)) ⩾ qi. Moreover, one can compute such an allocation in polynomial time.

Proof. We will give an informal description of our recursive algorithm A (Algorithm 1), followed by pseudocode. For each X ⊆ V , we let G\X denote the subgraph induced by V \X; also, we denote the restriction of ui to X by ui|X.

The algorithm first checks whether its input graph G′ has a value of at least qi for each player i ∈ N ′ ; if this is not the case, it fails. Then, if there is only one player, the algorithm simply returns the allocation that assigns all items to that player. When there are at least two players, A turns the graph into a rooted tree by choosing an arbitrary node as its root; denote by D(v) the set of descendants of a vertex v in this rooted tree. Then each player i finds a vertex vi such that his value for D(vi) is at least qi, but for each child w of v his value for D(w) is less than qi. The algorithm then allocates D(vi) to the last-diminisher i whose vertex vi has minimal height. The player i exits with the bundle D(vi), and the same algorithm A is called on the remaining instance (see Fig. 2).

It is immediate that A runs in polynomial time. Let In, . . . , I1 be the sequence of instances constructed by A when called on I and (qi)i∈N , where Ik = (Gk, Nk, Uk) and |Nk| = k (i.e., I = In). If A does not fail on any of these instances, then A(I, (qi)i∈N) returns a desired allocation: each agent is allocated a bundle that she values at least as highly as her given value qi. We need to prove that none of the recursive calls fails. To this end, we will prove the following lemma.

Algorithm 1: A(I ′ , (qi)i∈N ′ )

input :I ′ = (G′ ,N ′ , U ′ ) and (qi)i∈N ′ where G′ is a subtree of G, N ′ is a subset of N, and u′i = ui|V ′ for all i ∈ N ′ output :A valid allocation π such that ui(π(i)) ⩾ qi for all i ∈ N ′ 1 if u′i (V ′ ) < qi for some i ∈ N ′ then 2 return fail 3 else if |N ′ | = 1 then 4 return π where π(i) = V ′ for {i} = N ′ ; 5 else 6 Turn G′ into a rooted tree; 7 Find i ∈ N ′ and vi ∈ V ′ such that u′i (D(vi)) ≥ qi, but u′j (D(w)) < qj for each child w of vi and each player j ∈ N ′ ; 8 Set I ′′ = (G′ \D(vi),N ′ \ {i}, U ′′ ) where U ′′ is given by u′′ j = u′j |V ′ \D(vi) for all j ∈ N ′ \ {i}; 9 if A(I ′′ , (qj)j∈N ′ \{i}) does not fail then 10 Set π′ ← A(I ′′ , (qj)j∈N ′ \{i}); 11 Set π(i) = D(vi) and π(j) = π′ (j) for each j ∈ N ′ \ {i}; 12 return π;

Proof. The proof proceeds by backwards induction on k. For k = n the statement of the lemma is true. Suppose that the claim is true for some k > 1; we will prove it for k - 1. Consider the player i ∈ Nk \Nk-1, and let D(vi) be the bundle allocated to this player. For each player j ∈ Nk-1 = Nk\{i} by the inductive hypothesis we have mmsj(Ik) ⩾ qj . Consider a partition P = (P1, . . . , Pk) witnessing this; uj(Pℓ) ⩾ qj for each ℓ ∈ [k]. Assume without loss of generality that vi ∈ P1. Then D(vi) is fully contained in P1: if there is a vertex w in D(vi) \ P1, then the part of P that contains w is fully contained in a subtree rooted at a child of vi, and hence the value of that part is strictly less than qj, a contradiction.

Now, if P1 \ D(vi) is not empty, then it is a subtree of G, and there is another part P ∈ P that is adjacent to P1 \ D(vi) in G. Therefore, P ′ = (P \ {P1}) ∪ {P ∪ (P1 \ D(vi))} is a partition of Gk-1 into k - 1 connected components. By construction, uj(P ′ ) ⩾ qj for each P ′ ∈ P ′ , which proves that mmsj (Ik-1) ⩾ qj .

Now, consider what happens when A is called on Ik and (qi)i∈Nk for some k ∈ [n]. Let Gk = (Vk,Ek). We have ui(Vk) ⩾ mmsi(Ik) ⩾ qi for all i ∈ Nk, which implies that the algorithm does not fail. This completes the proof.

Proposition 5.1 relies on being given (qi)i∈N as its input, so we still need to show that MMS values on trees can be computed efficiently. It turns out that this can be accomplished by the same recursive algorithm. We note that for the general problem (without graph constraints, or equivalently, on complete graphs), computing MMS values is NP-hard, though they can be well-approximated [Woeginger, 1997].

• (a) The first player proposes a bundle.
• (b) Other players may diminish the bundle.
• (c) The last-diminisher receives the bundle.

Figure 2: A discrete version of the last-diminisher method

Lemma 5.3. For an instance of CFD where G is a tree, and a player i ∈ N, we can compute mmsi(I) in polynomial time.

Proof sketch. Calculating mmsi(I) is the same as maximizing the worst payoff for the instance I ′′ where all players are copies of player i. That is, mmsi(I) is equal to the maximum value of q such that A does not fail on (I ′′ , (q, . . . , q)). By scaling up the utilities, we can ensure that this value of q is a not-too-large integer (we omit the arithmetical details), and can therefore be found by binary search.

It now follows from Proposition 5.1 and Lemma 5.3 that for trees an MMS allocation can be computed efficiently.

Theorem 5.4. Every instance I = (G, N, U) of CFD where G is a tree admits an MMS allocation. Moreover, such an allocation can be computed in polynomial time.

The known examples of instances without MMS allocations are very intricate. Our graph-based setting allows for simpler constructions: our next example shows that an MMS allocation may not exist on a cycle of 8 vertices. We conjecture that this is the shortest cycle that admits such an example. Our example is similar in spirit to an example for 2-additive utility functions by [Bouveret and Lemaˆıtre, 2015].

To normalize to 1, each utility value above is divided by 20. Now, we have mms1(I) = mms2(I) ⩾ 1/4, as witnessed by the partition P1 = {{v1, v2}, {v3, v4}, {v5, v6}, {v7, v8}}, which offers value 1/4 for these players. Similarly, we have mms3(I) = mms4(I) ⩾ 1/4, as witnessed by the partition P2 = {{v2, v3}, {v4, v5}, {v6, v7}, {v8, v1}}. These two partitions are illustrated below (note the cyclic shift):

Now, suppose towards a contradiction that the instance I admits an MMS allocation π. Then π has to allocate at least two vertices to each player, as no player values any single item at 1/4 or higher. This means that π partitions the cycle into either P1 or P2. Suppose first that π cuts the graph into P1. Then, there is only one connected piece in P1 that players 3 and 4 value at 1/4 or higher, namely, {v1, v2}, so at least one of these players is allocated a piece whose value is less than his maximin share. A similar argument holds when π cuts the graph into P2. Therefore, there is no MMS allocation.

6 Conclusions and FutureWork

There are several exciting directions for the study of connected fair division of indivisible goods. For the solution concepts we have studied in this paper, one can ask whether certain graph classes yield better approximations than the general case, both in terms of existence guarantees and complexity results. In particular, it would be interesting to obtain a characterization of graphs for which an MMS allocation is guaranteed to exist. There are also further solution concepts that we have not considered, most notably the maximum Nash welfare solution [see Caragiannis et al., 2016], which could be studied in this context both from the axiomatic and the computational points of view. Another promising direction would be to extend the work to other preference representations, including ordinal preferences [Aziz et al., 2015], or to chores instead of goods [e.g., Aziz et al., 2017]. Also, it would be interesting to obtain analogues of procedures such as sequential allocation and round-robin that respect the connectivity constraints and still produce desirable allocations. Finally, we may consider placing constraints on the 'shapes' of players' pieces, e.g., by requiring that the size of each piece is large relative to its diameter; similar ideas have been recently explored by [Segal-Halevi et al., 2015] for the land division problem.

Acknowledgements

We thank the reviewers for helpful comments. This work was partly supported by the European Research Council (ERC) under grant number 639945 (ACCORD). Katar´ına Cechl´arov´a is supported by grant APVV-15-0091 from the Slovak Research and Development Agency. Sylvain Bouveret is partly supported by the project ANR-14-CE24-0007-01 CoCoRICoCoDec. The authors are grateful to the organizers of the Dagstuhl Seminar 16232 "Fair Division" and Budapest Workshop on Future Directions in Computational Social Choice (supported by COST Action IC 1205).