Networked Fairness in Cake Cutting

1 Introduction

In a nutshell, economics studies how resources are managed and allocated [Mankiw, 2014], and one of the most fundamental targets is to achieve certain fairness in the allocation of resources. In a standard setting, different people have possibly different preferences on parts of a common resource, and a fair allocation aims to distribute the resource to the people so that everyone feels that she is treated "fairly". When the resource is divisible, the problem is also known as "cake cutting", and two of the most prominent fairness notions in this domain are envy-freenss and proportionality. Here an allocation is envy-free if no agent i envies any other agent j; formally, this requires that for all i, j ∈ [n], vi(Ai) ≥ vi(Aj), where vk is the valuation function of agent k and Ak is the part allocated to agent k. It is known that an envy-free allocatio always exists [Brams and Taylor, 1996]. However, it is until recently that a finite-step procedure to find an envyfree allocation was proposed [Aziz and Mackenzie, 2016a]. A weaker fairness solution concept is called proportionality, which requires that each agent gets at least the average of the total utility (with respect to her valuation). Envy-freeness implies proportionality, but not vice versa.

∗This work was supported by Australian Research Council DECRA DE150100720 and Research Grants Council of the Hong Kong S.A.R. (Project no. CUHK14239416)

When studying these fairness conditions, almost all previous works consider all (ordered) pairs of relations among agents. However, in many practical scenarios, the relations that need to be considered are restricted. Such restrictions are motivated from two perspectives: (1) the system often involves a large number of people with an underlying social network structure, and most people are not aware of their nonneighbors' allocation or even their existence. It is thus inefficient and sometimes meaningless to consider any potential envy between pairs of people who do not know each other; (2) institutional policies may introduce priorities among agents, and envies between agents of different priorities will not be considered toward unfairness. For example, when allocating network resources such as bandwidth to users, priorities will be given to users who paid a higher premium and they are expected to receive better shares even in a considered "fair" allocation.

To capture the most salient aspect of the motivations above, in this paper, we initialize the study of fair cake cutting on graphs. Formally, we consider a graph G with vertices being the agents. An allocation is said to be envy-free on graph G if no agent envies any of her neighbors in the graph. An allocation is proportional on graph G if each agent gets at least the average of her neighbors' total allocation (with respect to her own valuation). By only considering the fairness conditions between connected pairs, the problem could potentially admit fair allocations with more desired properties such as efficiency, and lead to simpler and more efficient algorithms to produce them.

With regard to envy-freeness, one can easily see that an envy-free allocation in the traditional definition is also an envy-free allocation on any graph. However, the algorithm to compute such a solution to the former [Aziz and Mackenzie, 2016a] has extremely high complexity in terms of both the number of queries and the number of cuts it requires. One goal of this line of studies is to design simple and easy-toimplement algorithms for fair allocations on special graphs. It is easy to observe that (cf. Section 2.2), an envy-free allocation protocol on a connected graph G induces an envy-free protocol on any of its spanning trees. Therefore, trees form a first bottleneck to the design of envy-free algorithms for more sophisticated graph families. The first result we will show is an efficient moving-knife algorithm to find an envyfree allocation on an arbitrary tree, removing this bottleneck. The procedure allocates the cake from the tree root in a topdown fashion and is significantly simpler than the protocol proposed by Aziz et al. [2016a].

When the graph is more than a tree, the added edges significantly increase the difficulty of producing an envy-free allocation. However, if we lower the requirements and only aim at proportionality, then it is possible to go beyond trees. Note that though a proportional allocation can be produced for complete graphs by several algorithms, such globally proportional solutions may be no longer proportional on an incomplete graph. Our second result gives an discrete and efficient algorithm to find a proportional allocation on descendant graphs, a family of graphs that are generated from rooted trees by connecting all ancestor-descendant pairs in the tree. Descendant graphs are interesting from both practical and theoretical viewpoints (cf. Section 2.2).

1.1 RelatedWork

Cake cutting has been a central topic in recource allocation for decades; see, e.g., [Brams and Taylor, 1996; Robertson and Webb, 1998; Procaccia, 2013]. As mentioned, envyfreeness and proportionality are two of the most prominent solution concepts for fairness consideration in this domain. An envy-free allocation always exists, even if only n-1 cuts are allowed [Su, 1999]. The computation of envy-free and proportional allocations has also received considerable attention, with a good number of discrete and continuous protocols designed for different settings [Dubins and Spanier, 1961; Robertson and Webb, 1998; Brams and Taylor, 1995; Brams et al., 1997; Barbanel and Brams, 2004; Procaccia, 2009; 2015; Aziz and Mackenzie, 2016b]. It had been a long standing open question to design a discrete and bounded envy-free protocol for n agents, until settled very recently by Aziz and Mackenzie [2016a]. For proportionality, much simpler algorithms are known that yield proportional allocations with a reasonable number of cuts. Even and Paz [1984] gave a divide-and-conquer protocol that could produce a proportional allocation with O(n logn) cuts. Woeginger and Sgall [2007] and Edmonds and Pruhs [2006] later also showed a matching Ω(n log n) lower bound.

The idea of restrictive relations, i.e., people comparing the allocation only with their peers, have also been considered in scenarios other than cake cutting. Chevaleyre et al. [2007] proposed a negotiation framework with a topology structure, such that agents may only trade indivisible goods with their neighbors, and the envy also could only happen between connected pairs. Todo et al [2011] generalized the envy-freeness to allow envies between groups of agents, and discussed the combinatorial auction mechanisms that satisfy these concepts.

Shortly before our work, [Abebe et al., 2016] proposed the same notion of fairness on networks. Despite this, the paper and ours have completely different technical contents. [Abebe et al, 2017] shows that proportional allocations on networks do not satisfy any natural containment relations, characterizes the set of graphs for which a single-cutter protocol can produce an envy-free allocation, and analyzes the price of envy-freeness. In this paper, we focus on designing simple and efficient protocols for fair allocations on special classes of graphs. The graph families considered in these two papers are also different.

2 Our Framework

In a cake cutting instance, there are n agents to share a cake, which is represented by the interval [0, 1]. Each agent i has an integrable, non-negative density function vi : [0, 1] ↦→ R. A piece S of the cake is the union of finitely many disjoint intervals of [0, 1]. The valuation of agent i for a piece S is Vi(S) = ∫S vi(x)dx.

An allocation of the cake is a partition of [0, 1] into n disjoint pieces, denoted by A = (A1, . . . ,An), such that agent i receives piece Ai, where all pieces are disjoint and ⋃i Ai = [0, 1].

2.1 Fairness Notions on Graphs

First we review two classic fairness notions in resource allocation.

Envy-Freeness. An allocation A is called envy-free if for all i ̸= j, vi(Ai) ≥ vi(Aj).

Proportionality. An allocation A is called proportional if for all i, vi(Ai) ≥ 1n vi([0, 1]).

To account for a graphical topology, we generalize the above definitions by assuming a network structure over all agents. That is, we assume an undirected simple graph G = (V,E) in which each vertex i represents an agent. Let N(i) be the set of neighbors of agent i in G.

Definition 1 (Envy-free on networks). An allocation A is called envy-free on a network G = (V,E) if for all i and all j ∈ N(i), vi(Ai) ≥ vi(Aj).

Definition 2 (Proportional on networks). An allocation A is called proportional on a network G if for all i, vi(Ai) ≥ 1 |N(i)| ∑j∈N(i) vi(Aj).

Both definitions can be viewed as generalizations of the original fairness concepts, which correspond to the case of G being the complete graph.

For envy-freeness, we have the following properties.

Fact 1. Any allocation that is envy-free on a graph G is also envy-free on any subgraph G′ ⊆ G.

Corollary 1. An envy-free allocation is also envy-free on any graph G.

The corollary implies that the envy-free protocol recently proposed by Aziz and Mackenzie [2016a] would also give an envy-free allocation on any graph. However, the protocol is highly involved and requires a large number of queries and cuts, which naturally raises the question of designing simpler protocols for graphs with special properties.

Goal 1: Design simple protocols that could produce envy-free allocations on certain types of graphs.

While envy-freeness is closed under the operation of edge removal, proportionality is not, as removing edges changes the set of neighbors and thus also the average of neighbors' values. Therefore, although a number of proportional protocols are known, they do not readily translate to proportional allocations on subgraphs in any straightforward way.

At a first glance, even the existence of a proportional allocation on all graphs is not obvious. Interestingly, the existence can be guaranteed from that of an envy-free allocation, since any envy-free allocation is also proportional on the same network. Therefore an envy-free protocol for complete graphs would also produce a proportional allocation on any graph. In light of this, we turn to the quests for simpler proportional protocols on interesting graph families as in the envy-free case.

Goal 2: Design simple protocols that could produce proportional allocations on certain types of graphs.

2.2 Motivations for the Two Graph Families

In this paper we focus on two graph families, trees and descendant graphs. Note that for both envy-freeness and proportionality, we only need to consider connected graphs (since otherwise we can focus on the easiest connected component). Without an envy-free algorithm for trees, there would be no chance to design envy-free protocols for more complicated graph families (see Fact 1).

For descendant graphs, recall that a descendant graph is obtained by connecting all ancestor-descendant pairs of a rooted tree (cf. Section 4 for a formal definition). Descendant graphs can be used to model the relations among members in an extended family, where each edge connects a pair of ancestor and descendant. It can also model the management hierarchy in a company, where each edge connects a superior and a subordinate. From a theoretical viewpoint, we note that for any undirected graph G, if we run a depth-first search, then all edges in G are either edges on the DFS tree T or a back edge of T. Thus G is a subgraph of the upward closure T uc of T , where T uc is obtained from T by connecting all (ancestor, descendant) pairs. Note that T uc is a descendant graph. Therefore, if there is an envy-free allocation protocol for the family of descendant graphs, then there is an envy-free allocation protocol for any graph. This indicates that envy-freeness for descendant graphs may be hard. Interestingly, if we relax to proportionality, we do get a protocol on this family, as shown in Section 4.

3 Envy-Freeness on Trees

We first present an algorithm that produces an envy-free allocation on trees. The algorithm makes use of the Austin moving-knife procedure [Austin, 1982] as a subroutine. Given a rooted tree T, let |T| denote the number of vertices. For any vertex i in T, denote by T(i) the subtree rooted at vertex i.

Definition 3 ([Austin, 1982]). An Austin moving-knife procedure AUSTINCUT (i, j, n, S) takes two agents i, j, an integer n > 0 and a subset S of cake as input parameters, and outputs a partition of S into n parts, such that both agents value these n pieces as all equal, each of value exactly 1/n fraction of the value of S. An Austin procedure needs 2n cuts.

It should be noted that this is a continuous procedure, and it is not known that whether it can be implemented by a discrete algorithm. With that being said, to the best of our knowledge, it is not known whether Austin's moving knife procedure can help to obtain an algorithm achieving envy-freeness (on complete graphs) that is simpler than the algorithm in [Aziz and Mackenzie, 2016a].

Now we are ready to present our allocation algorithm in Algorithm ALLOCATIONTREE, which calls a sub-procedure given in Algorithm ALGTREE.

Algorithm 1 ALGTREE (T, r, (A1, . . . , An))

Require: Tree T with root vertex r, size of tree n, an allocation A = (A1, . . . , An).

• 1: for each immediate child i of root r do
• 2: Among all remaining pieces of A1, . . . ,An, pick |T(i)| pieces that agent i values the highest.
• 4: end for
• 3: Let Si denote the union of these |T(i)| pieces.
• 5: Allocate the remaining one piece to r.
• 6: for each child i of root r do
• 7: Apply AUSTINCUT (i, r, |T(i)|, Si) to divide Si into |T(i)| equal parts X1, . . . ,X|T(i)| for i and r.
• 8: Run ALGTREE (T(i), i, (X1, . . . ,X|T(i)|)).
• 9: end for

Algorithm 2 ALLOCATIONTREE (T, r)

Require: Tree T with root vertex r.

• 1: Let r cut the cake into n = |T| equal parts (A1, . . . ,An) with respect to her valuation.
• 2: Run ALGTREE (T, r, (A1, . . . ,An)).

Theorem 2. For any n-node tree T with root r, Algorithm ALLOCATIONTREE (T, r) outputs an allocation that is envyfree on T with O(n2 ) cuts.

Proof. We will prove this by induction on the height of the tree. The base case is when the tree has only one vertex, the root r. In this case n = 1 and the algorithm simply gives the whole set A1 to r, and the envy-free property holds trivially. Now we assume that the theorem holds for trees of height d and will prove it for any tree T of height d+1. First, the root r receives exactly 1/n as she cuts the cake into n equal pieces (in Algorithm ALLOCATIONTREE) and gets one of them (in line 5 of Algorithm ALGTREE). In addition, in r's valuation, each child i (of r) gets |T(i)|/n fraction of the total utility (the first for loop in Algorithm ALGTREE), and cuts it into |T(i)| equal pieces (with respect to r's valuation, in line 7 in Algorithm ALGTREE) and finally gets one of them. So r thinks that child i's share is also worth 1/n utility, same as hers. Thus r does not envy any of her children.

Also note that all children of r pick pieces before r does, so each child i values her part Si at least |T(i)| times of what r gets. Then the second for loop in Algorithm ALGTREE cuts this part into |T(i)| equal pieces (with respect to child i's valuation, in line 7 in Algorithm ALGTREE). Since child i gets one of these pieces (in line 5 of the recursive call of Algorithm ALGTREE) she views this piece at least 1 |T(i)| · |T(i)| = 1 times what r gets. Namely, child i does not envy root r.

Among vertices inside each subtree rooted at child i of r, no envy occurs by the inductive hypothesis. Putting everything together, we can see that there is no envy between any pair of connected vertices.

Finally we analyze the number of cuts of the algorithm. Recall that AUSTINCUT (i, j, n, S) makes at most 2n cuts. When each vertex u is being processed in ALGTREE, it makes at most ∑i:child of u 2|Ti| ≤ 2n cuts. Thus in total the algorithm requires O(n2 ) cuts.

4 Proportionality on Descendant Graphs

We first define descendant graphs formally.

Definition 4. An undirected graph G = (V, E) is called a descendant graph on a rooted tree T , if T is a spanning tree of G, and there exists a vertex r such that for any two vertices i and j, (i, j) ∈ E if and only if (i, j) is an ancestor-descendant pair on tree T rooted at r.

In other words, a descendant graph G of a rooted tree T can be obtained from T by connecting all of ancestor-descendant pairs.

We now present an algorithm that produces a proportional allocation on descendant graphs. The idea of the algorithm can be described as a process of collecting and distributing:

We start with the root vertex holding the whole cake, and process the tree in top-down fashion. Each vertex v, when being processed, applies a three-step procedure. (1) Collect phase: agent v collects all cake pieces that she has received (from her ancestors); (2) Cut phase: agent v cuts these cakes into f(v) equal pieces according to her own evaluation, for some function f(v) to be defined later; (3) Distribute phase: let each descendant of v pick certain number of these pieces that they value the highest.

To formally describe the algorithm, we shall need the following notation. For a vertex v ∈ T , let d(v) denote the depth of vertex v in tree T (i.e. the number of edges on the unique path from v to the root), d = maxv d(v) denote the depth of T .

We then define a function f : T → N as

We first make some easy observations from this definition.

• When d(v) ≥ 1, d(v) divides f(v). This guarantees that in the algorithm described below, each distribute step reallocates an integral number of slices.
• f(r) = |T| · d! for root r of the tree.
• f(v) = d! for every leaf v of the tree.

Proposition 3. Function f(v) satisfies

Now let us take a closer look at term X. Note that it is summed over all vertices u at the path between v(exclusive)

and u′ (inclusive). These vertices have depth d(v)+1, d(v)+ 2, . . . , d(u′ ) in tree T , respectively. Thus we have

Plugging this back to the previous formula gives

Therefore,

To summarize, we just showed

Multiplying both sides by d! completes the proof.

The proportional allocation algorithm is formally presented as below.

Algorithm 3 ALGDESCENDANTGRAPH (G)

Require: Descendant graph G of tree T and root vertex r, size of tree n, depth of tree d

• 1: for u ∈ T in increasing order of d(u) do // collect and cut phase:
• 2: Let Xu be the union of all cake pieces that vertex u possesses
• 3: SliceXu into f(u) equal piecesXu 1 , . . .Xu f(u) according to u's evaluation function // distribute phase:
• 4: for v ∈ T (u) - {u} in increasing order of d(v) do
• 5: Among all the remaining pieces of Xu 1 , . . . ,X u f (u) , agent v takes f(v)/d(v) pieces that she values the highest.
• 6: end for
• 7: end for

Figure 2 illustrates the f values and the execution of the algorithm on a simple 5-node tree.

From the algorithm description and equations (1) and (2), it is easy to observe the following properties on the number of cake slices during the algorithm.

Properties:

1. Every agent v, except the root of the tree, received f(v) pieces of the cake in total from her ancestors.
2. Every agent will have exactly d! slices of cake in her possession after the algorithm terminates.

Theorem 4. For any n-node descendant graph G of a tree, ALGDESCENDANTGRAPH (G) outputs an allocation that is proportional on G with at most n2 · d! cuts.

Proof. First note that the root r cuts the cake into |T| · d! equal pieces and finally gets d! of them, so its value is 1/|T| fraction of that of the whole cake. As the root connects to all nodes in the graph, it achieves exactly the average of its neighbors.

Now we consider an arbitrary node v of depth at least 1. Let N(v) be the set of v's neighbors. Furthermore, let Na(v) be the set of v's ancestors in T, and Nd(v) the set of v's descendants in T . It is clear that N(v) = Na(v) ∪Nd(v). Also note that, as G is a descendant graph, Nd(v) = T (v) \ {v}.

Let Av be the final allocation of agent v at the end of the algorithm. We are interested in S = ⋃i∈N(v) Ai, the union of all pieces of cake belonging to agents in N(v). Note that S consists of the following two components:

• Those held by v's ancestors: Each Au for u ∈ Na(v) contains d! slices from {Xu i }i=1,...,f(u). These are the leftover slices after the distribute phase of agent u.
• Those held by v's descendants: ⋃w∈Nd(v) Aw consists of two parts:
• The slices from {Xu i } distributed by agent u ∈ Na(v) in their distribute phase to agents in Nd(v). For each u ∈ Na(v), each agent w ∈ Nd(v) picks f (w) d(w) slices from{Xu i }. In total, agent u distributes ∑w∈Nd(v) f (w) d(w) slices of cake to agents in Nd(v). From Eq (2), this number equals to f(v) - d!.
• The f(v)-d! slices from{Xv i } distributed by agent v in her distribute phase to her descendants. Note that Xv comes from all ancestors u.

Note that each ancestor u of v has her collection Xu distributed first to v, then to v's descendants, and finally to u herself. Denote these parts by Su v , Su d and Su u , respectively. Agent v later distributes exactly f(v)-d! f(v) fraction of Su v to its descents, and keeps d! f(v) fraction of Su v to herself. Let us denote these two parts by Su vd and Su vv , respectively. To avoid potential confusion of notation, we use αv to denote the valuation function of agent v. We will show the following inequality.

Once this is shown for all ancestors u of v, we can sum these inequalities over all ancestors u and obtain

5 Conclusion

This paper introduces a graphical framework for fair allocation of divisible good, defines envy-freeness and proportionality on a graph, and proposes an envy-free allocation algorithm on trees and a proportional allocation algorithm on descendant graphs. The framework opens new research directions in developing simple and efficient algorithms that produce fair allocations under important special graph structures.

Acknowledgments

We thank Ariel Procaccia and Nisarg Shah for pointing out [Chevaleyre et al., 2007; Todo et al., 2011], and an anonymous reviewer for pointing out [Abebe et al., 2016] to us.

where we used the facts that

• Av = ⊎uSu vv is what v finally has, where the notation ⊎u stands for the disjoint union over all ancestors u of v.
• Sa = ⊎uSu u is the part of cake that v's ancestors collectively have,
• Sd = ⊎uSu d is the set of pieces that v's ancestors give to v's descendants, and
• Svd = ⊎uSu vd is the set of pieces that v gives to its descendants.

Note that the numerator in the right hand side of Eq. (4) is exactly the total value of N(v), and the denominator is exactly the size of N(v). Thus the inequality is actually

as the proportionality requires.

So it remains to prove Eq. (3). We will examine the four sets involved in this inequality one by one, and represent or bound them all in terms of αv(Su v ).

• αv(Su vv ) = αv(Su v ) · d!/f(v), as v divides Su v into f(v) equal pieces and takes d! of them.
• αv(Su u ) d! ≤ αv(Su v ) f(v)/d(v) , as v takes f(v)/d(v) pieces of {Xu i : i ∈ [f(u)]} before u is left with d! pieces.
• αv(Su d ) f(v)-d! ≤ αv(Su v ) f(v)/d(v) , as v takes f(v)/d(v) pieces of {Xu i : i ∈ [f(u)]} before its descendants collectively take (f(v) - d!) pieces.
• αv(Su vd ) = αv(Su v ) · (f(v) - d!)/f(v) as v divides Su v into f(v) equal pieces and pass (f(v) - d!) of them to descendants.

Putting these four (in)equalities and the definition of f(v) in Eq. (1) together, one can easily verify Eq. (3). This completes the proof of the proportionality.

For the number of cuts, each agent v, when being processed, makes f(v) cuts in the cut phase. In total the algorithm requires ∑v f(v) ≤ n · f(r) ≤ n2 · d! cuts.

Note that though the number of cuts required here is exponential, this singly exponential bound is much better than the one for the general protocol in [Aziz and Mackenzie, 2016a].