# fairly_allocating_many_goods_with_few_queries__c9ba14c1.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Fairly Allocating Many Goods with Few Queries

Hoon Oh Computer Science Department Carnegie Mellon University

Ariel D. Procaccia Computer Science Department Carnegie Mellon University

Warut Suksompong Department of Computer Science University of Oxford

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

1 Introduction

Fair division is the study of how to allocate resources among interested agents in such a way that all agents ﬁnd the resulting allocation to be fair (Brams and Taylor 1996; Moulin 2003). One of the ﬁeld s paradigmatic applications is the allocation of indivisible goods; this task typically arises in inheritance cases, when, say, an art or jewelry collection is divided between several heirs. Indeed, dividing goods is one of ﬁve applications offered by Spliddit (Goldman and Procaccia 2014), a not-for-proﬁt fair division website; since its launch in November 2014, the website has served more than 130,000 users, and, in particular, has solved thousands of goods-division instances submitted by users. While Steinhaus (1948) was the ﬁrst to study fairness from a mathematical point of view, the history of fair division actually goes back much further: A simple fair division mechanism called the cut-and-choose protocol is mentioned in the Book of Genesis. After a dispute between Abraham and Lot, Abraham suggests that the two go their separate ways. He divides the land into two parts that here we are perhaps using artistic license he likes equally, and lets Lot choose the part that he prefers. The cut-and-choose protocol ensures that the resulting allocation satisfy an important fairness property called envy-freeness each of Abraham and Lot ﬁnds his part to be worth at least as much as the other

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

person s part. Even though envy-freeness can always be satisﬁed when the allocated resources are divisible (Stromquist 1980), this is not the case when we deal with indivisible resources. With two agents and a single indivisible good, we already see that one of the agents will not receive the good and envy the other agent. Consequently, various relaxations of envy-freeness have been considered, the most prominent one being envyfreeness up to one good (EF1). This means that some agent may envy another agent under the given allocation, but that envy can be eliminated by removing a single good from the latter agent s bundle. Lipton et al. (2004) showed that EF1 can be guaranteed even when the agents have arbitrary monotonic valuations. They achieved this by using an algorithm that we will refer to as the envy cycle elimination algorithm, which runs in time O(n3m), where n is the number of agents and m the number of goods. Given that an EF1 allocation always exists and can be found efﬁciently at this level of generality, a natural question to ask is how much we need to know about the agents valuations to compute such an allocation. This issue is crucial for combinatorial valuations, since merely writing down a complete valuation might already take exponential time. But the question is equally important for additive valuations; while expressing such a valuation only takes linear time, this may already be prohibitive if the number of goods is very large. In fact, the goods application on Spliddit elicits additive valuations and computes an EF1 allocation (Caragiannis et al. 2016); the largest instance that was encountered involved ten siblings and roughly 1400 goods. In this case, the siblings actually prepared a spreadsheet with their value for each of the goods!

1.1 Our Results We allow algorithms to elicit the valuations of agents via a standard interface, value queries, which ask an agent for her value for a given subset of goods. The complexity of algorithms is measured in terms of the worst-case number of queries they require. In Section 3 we consider the case of two agents. We show that it is possible to compute an EF1 allocation for agents with arbitrary monotonic valuations using a logarithmic number of queries (Theorem 3.1). This is asymptotically tight, even for two agents with identical and very simple

Fairness notion Monotonic valuations Additive valuations

EF m m/2 (Prop. 3.3) Θ(m) (Thm. 3.4)

EFX Ω 1 m m (m 1)/2 (Plaut and Roughgarden 2018) Θ(m) (Thm. 3.5)

EF1 Θ(log m) (Thm. 3.1, Prop. 3.2) Θ(log m) (Thm. 3.1, Prop. 3.2)

Table 1: Query complexity in the setting with two agents. All lower bounds hold even when the two agents have identical valuations.

binary valuations (Proposition 3.2). We then turn to envyfreeness and establish that determining whether an envy-free allocation exists takes an exponential number of queries for agents with identical monotonic valuations (Proposition 3.3) and a linear number of queries for agents with identical additive valuations (Theorem 3.4); our latter bound is also exactly tight. We end our investigation of the two-agent case by considering another relaxation of envy-freeness called envyfreeness up to any good (EFX), a stronger notion than EF1. We show that computing an EFX allocation already takes a linear number of queries for agents with identical additive valuations (Theorem 3.5). This complements a recent result of Plaut and Roughgarden (2018), who showed that while an EFX allocation always exists for two agents with arbitrary monotonic valuations, computing one such allocation already requires an exponential number of queries in the worst case, even when the valuations of the agents are identical. Taken together, these results suggest that, when the number of goods is large, EF1 is the right notion of fairness, whereas EFX is too demanding. The results of Section 3 are summarized in Table 1. In Section 4 we address the case of three agents. Our main result is an algorithm that computes an EF1 allocation for three agents with additive valuations using a logarithmic number of queries (Theorem 4.4). Our algorithm adapts the Selfridge-Conway procedure, a classical cakecutting protocol for computing an envy-free allocation of a heterogeneous divisible good, to the setting of indivisible goods. In particular, as a building block we use an algorithm that, for three agents with identical additive valuations, computes an EF1 allocation satisfying the extra property that any three predetermined goods belong to three different bundles (Lemma 4.3). Finally, in Section 5 we consider the setting where there can be any number of agents. We show that the envy cycle elimination algorithm of Lipton et al. (2004) can be implemented using a relatively modest number of queries (Theorem 5.1). To complement this positive result, we conclude by presenting a lower bound on the number of queries needed to compute an EF1 allocation (Theorem 5.2).

1.2 Related Work

The paper that is most closely related to ours is the one mentioned above, by (Plaut and Roughgarden 2018). Using an interesting reduction from the local search problem on a class of graphs known as Kneser graphs, they show that the

problem of ﬁnding an EFX allocation requires an exponential number of queries, even for two agents with identical valuations. They also examine when EFX can be achieved in conjunction with other properties such as Pareto optimality, and establish the existence of allocations satisfying an approximate version of EFX for agents with subadditive valuations. A bit further aﬁeld, query complexity has long been a topic of interest in computational fair division, albeit in the context of cake cutting (Procaccia 2013). The standard query model is due to Robertson and Webb (1998), and allows two types of operations: evaluate (which is similar to our value queries) and cut. In this model, the query complexity of achieving fair cake allocations, under various notions of fairness, is well studied (Edmonds and Pruhs 2006; Procaccia 2009; Deng, Qi, and Saberi 2012; Aziz and Mackenzie 2016a).

2 Preliminaries

There is a set G = {g1, g2, . . . , gm} of goods and a set A = {a1, a2, . . . , an} of agents. A bundle is a subset of G. Each agent ai has a nonnegative valuation ui(G ) for each G G. We sometimes abuse notation and write ui(g) for ui({g}). A valuation is said to be monotonic if ui(G1) ui(G2) for any i and any G1 G2 G. It is said to be additive if ui(G ) = P

g G ui(g) for any G G, and binary if it is additive and ui(g) = 0 or 1 for each g G. While additivity is signiﬁcantly more restrictive than monotonicity, many papers in fair division assume that agents valuations are additive (Bouveret and Lemaˆıtre 2016; Caragiannis et al. 2016; Kurokawa, Procaccia, and Wang 2018). This assumption is also made by Spliddit s app for dividing goods (Caragiannis et al. 2016), as, in practice, additive valuations hit a sweet spot between expressiveness and ease of elicitation. We assume throughout the paper that agents have monotonic valuations1 and that, without loss of generality, ui( ) = 0 for all i. An allocation is a partition of G into n bundles (G1, G2, . . . , Gn), where bundle i is allocated to agent i. If the goods lie on a line, for each good g we denote by Lg and Rg the set of goods to the left and right of g, respectively. A

1Without this assumption, neither of the relaxations of envyfreeness that we consider can always be satisﬁed even when there are two agents.

contiguous allocation is an allocation in which every bundle forms a contiguous block on the line. We now deﬁne the fairness notions that we consider.

Deﬁnition 2.1. An allocation (G1, G2, . . . , Gn) is said to be

envy-free if ui(Gi) ui(Gj) for any i, j. envy-free up to any good (EFX) if for any i, j and any good g Gj, ui(Gi) ui(Gj\{g}). envy-free up to one good (EF1) if for any i, j such that ui(Gi) < ui(Gj), there exists a good g Gj such that ui(Gi) ui(Gj\{g}).2

It is easy to see that envy-freeness is stronger than EFX, which is in turn stronger than EF1. Envy-freeness is a classical and well-studied fairness notion that goes back to Foley (1967). By contrast, its two relaxations are relatively new: EF1 was introduced by Budish (2011) and a related property was studied by Lipton et al. (2004), while EFX was only proposed recently by Caragiannis et al. (2016). Interestingly, it is not known whether an EFX allocation always exists, even for three agents with additive valuations (Caragiannis et al. 2016; Plaut and Roughgarden 2018). We will consider algorithms that compute fair allocations according to these fairness notions. In order to discover the agents valuations, an algorithm is allowed to issue value queries. In each query, the algorithm chooses an agent ai and a subset G G, and ﬁnds out the value of ui(G ). We assume that the algorithm is deterministic, and allow it to be adaptive, i.e., the algorithm can determine its next query based on its past queries and the corresponding answers.

3 Two Agents In this section, we consider the setting with two agents. We organize our results based on fairness notion: EF1, envyfreeness, and EFX.

3.1 EF1 We begin by describing an algorithm that computes an EF1 allocation for two agents with arbitrary monotonic valuations. The algorithm is similar to the cut-and-choose protocol for cake cutting: the ﬁrst agent partitions the goods into two bundles with the property that she would be satisﬁed with either bundle, and the second agent chooses the bundle that she prefers. In order to minimize the number of queries, we arrange the goods on a line and use binary search to determine the cut point of the ﬁrst agent.

Algorithm 1 (for two agents with monotonic valuations)

Step 1: Arrange the goods on a line in arbitrary order. Find the rightmost good g such that u1(Lg) u1(Rg {g}).

2The clause such that ui(Gi) < ui(Gj) is necessary for the case where Gj = .

Step 2: If u1(Lg) u1(Rg), consider the partition (Lg {g}, Rg); else, consider the partition (Lg, Rg {g}). Give a2 the bundle from the partition that she prefers, and a1 the remaining bundle.

We claim that the algorithm computes an EF1 allocation using a logarithmic number of queries.

Theorem 3.1. For two agents with arbitrary monotonic valuations, Algorithm 1 computes an EF1 allocation. Moreover, the algorithm can be implemented to use O(log m) queries in the worst case.

Proof. We ﬁrst show that the algorithm computes an EF1 allocation. Since a2 gets the bundle that she prefers, she does not envy a1. To reason about a1 s envy, assume ﬁrst that u1(Lg) u1(Rg). It holds that u1(Lg {g}) u1(Rg): This is clearly true if g is the rightmost good on the line, and otherwise it follows from the deﬁnition of g that u1(Rg) < u1(Lg {g}). Therefore, if a1 receives Lg {g}, she is not envious at all. And if she receives Rg, it holds that

u1(Rg) u1(Lg) = u1((Lg {g}) \ {g}),

so EF1 is satisﬁed. The second case is where u1(Lg) > u1(Rg). If a1 gets Rg {g} then she is not envious, since, by the deﬁnition of g, u1(Rg {g}) u1(Lg). If she gets Lg instead, then EF1 holds, because

u1(Lg) > u1(Rg) = u1((Rg {g}) \ {g}).

Next, we show that the algorithm can be implemented to use O(log m) queries. By monotonicity, Step 1 can be done by binary search using O(log m) queries. In Step 2, we use two queries to compare u1(Lg) and u1(Rg), and two more queries to compare a2 s valuation for the two bundles in the partition. Hence the total number of queries is O(log m).

The following proposition shows that the bound O(log m) in Theorem 3.1 is tight.

Proposition 3.2. Any deterministic algorithm that computes an EF1 allocation for two agents with identical binary valuations uses Ω(log m) queries in the worst case, even when each agent values only two goods.

Since Proposition 3.2 will later be generalized by Theorem 5.2, we do not present its proof here.

3.2 Envy-freeness Next, we turn our attention to envy-freeness. Unlike the case of EF1, allocations that satisfy envy-freeness are not guaranteed to exist. We show that for two agents with identical monotonic valuations, even an algorithm that only decides whether an envy-free allocation exists already needs to make an exponential number of queries in the worst case. A similar argument holds for algorithms that compute an envy-free allocation whenever one exists.

Proposition 3.3. Assume that m is even. Any deterministic algorithm that determines whether an envy-free allocation exists for two agents with identical monotonic valuations uses at least m m/2 queries in the worst case.

The proof of Proposition 3.3, and all other omitted proofs, can be found in the full version of our paper (Oh, Procaccia, and Suksompong 2018). Even though an algorithm that decides whether an envyfree allocation exists needs to make an exponential number of queries for agents with monotonic valuations, when we restrict our attention to agents with additive valuations, the exponential lower bound no longer holds since the algorithm can query the value of both agents for every good and ﬁnd out the full valuations. Nevertheless, it is still conceivable that there are algorithms that do asymptotically better, e.g., use a logarithmic number of queries. We show that this is not the case: a linear number of queries is necessary, even when the two agents have identical valuations. In fact, we leverage linear-algebraic techniques to establish that at least m queries are needed in this case. This bound is tight for two identical agents since the algorithm can ﬁnd out the common valuation by querying the value of each of the m goods.

Theorem 3.4. Assume that m is even. Any deterministic algorithm that decides whether an envy-free allocation exists for two agents with identical additive valuations uses at least m queries in the worst case.

Proof. For ease of notation, let xi = u(gi) for i = 1, 2, . . . , m, where u is the common valuation. Note that an envy-free allocation exists if and only if the goods can be partitioned into two sets of equal value. Consider an algorithm that always uses at most m 1 queries. Assume without loss of generality that the algorithm always uses exactly m 1 queries; whenever it uses fewer than m 1 queries, we add arbitrary queries for the algorithm. The idea is that for each query, if the queried subset has size s, we will give an answer close to s in such a way that after all queries, it is still possible that there exists an envy-free allocation, but also that there does not exist one. This will allow us to obtain the desired conclusion. For i = 1, 2, . . . , m 1, let vi be a vector of length m where the jth component is 1 if good gj is included in the ith query, and 0 otherwise. Therefore the ith query asks for the value vi x = Pm j=1 vi,jxj. Furthermore, let W be the set of all vectors of length m all of whose components are 1, and let W W be the set of vectors with an equal number of 1 and 1. Note that an envy-free allocation exists exactly when w x = 0 for some w W. When we receive the ith query, if vi span(v1, v2, . . . , vi 1), our answer is already determined by previous answers. Assume therefore that vi span(v1, v2, . . . , vi 1) for all i. For each w W such that w span(v1, v2, . . . , vi)\span(v1, v2, . . . , vi 1), there exists a unique answer that would force w x = 0. We avoid all such (ﬁnite number of) answers. After query number m 1 we have a subspace V = span(v1, v2, . . . , vm 1) of dimension m 1 such that we know the value v x if and only if v is in the subspace.

Next, let W = span(W ). Clearly, all vectors in W are orthogonal to the vector (1, 1, . . . , 1). We claim that W in fact has dimension m 1, and therefore consists of all vectors orthogonal to (1, 1, . . . , 1). To see this, take two distinct vectors in W that differ only in the ﬁrst and ith component for i = 2, 3, . . . , m. The difference vector, which consists of a 1 in the ﬁrst position, a 1 in the ith position, and 0 elsewhere belongs to W . No nontrivial linear combination of these vectors can produce the all-zero vector, meaning that W indeed has dimension m 1. Now, since any vector vi is not orthogonal to (1, 1, . . . , 1), we have V = W , and so there exists w W such that w V. (If this were not the case, we would have W V, and then the two subspaces would be equal because they are of the same dimension.) Since V is of dimension m 1 and w V, setting the value of w x will, in combination with the previous constraints, uniquely determine x. If we set w x = 0, an envy-free allocation exists. On the other hand, if we set w x so that w x = 0 for all w W, an envy-free allocation does not exist. This choice of value for w x is available because for each w W, only one value of w x forces w x = 0. It remains to show that we can give the answers so that after setting the value of w x, all components of the unique solution for x are nonnegative. Let δ > 0 be such that for any vector z with |zi| < δ for all i = 1, 2, . . . , m, and any m m invertible matrix M all of whose entries are 1, 0, or 1, the unique solution y to My = z has |yi| < 1 for all i. The existence of δ is guaranteed by the fact that the linear transformation M takes the all-zero vector to itself, by the continuity of the transformation, and by the fact that there are a ﬁnite number of such matrices M. For each query on a subset of size k, we give an answer in the range (k δ, k+δ). Moreover, we choose the value of w x to be in the range ( δ, δ). Write yi = xi 1 for all i, where x is the unique solution according to our choices. Our answers to the queries ensure that the values of vi y for i = 1, 2, . . . , m 1 belong to the range ( δ, δ), and our choice of w x ensures that w y also belong to the same range. Since all elements of vi and w belongs to the set { 1, 0, 1}, by taking M to be the m m matrix with v1, v2, . . . , vm 1 and w as its rows, and z to be a vector of length m with v1 y, v2 y, . . . , vm 1 y and w y as its elements, our deﬁnition of δ implies that |yi| < 1 for all i. It follows that xi > 0 for all i, as desired.

For two agents with additive valuations, envy-freeness is equivalent to another well-known fairness notion called proportionality, which requires that each agent receive at least half of her value for the whole set of goods. Thus, the lower bound in Theorem 3.4 also holds for two agents with identical additive valuations with respect to proportionality.

3.3 EFX We end this section by considering EFX. For two agents with monotonic valuations, Plaut and Roughgarden (2018) showed that an EFX allocation is guaranteed to exist, but computing it takes an exponential number of queries in the worst case. If the agents have additive valuations, however, the algorithm can already ﬁnd out the full valuations using

only a linear number of queries. Our next result shows that a linear number of queries is, in fact, needed for computing an EFX allocation.

Theorem 3.5. Assume that m is odd. Any deterministic algorithm that computes an EFX allocation for two agents with identical additive valuations uses at least (m 1)/2 queries in the worst case.

Note that Theorem 3.5 is incomparable with Theorem 3.4, even though EFX is a relaxation of envy-freeness, because the former result deals with a search problem (ﬁnding an EFX allocation knowing that one always exists), whereas the latter deals with a decision problem (deciding whether an EF allocation exists at all).

4 Three Agents In this section, we study the setting with three agents who are endowed with additive valuations. Our main result is an algorithm that ﬁnds an EF1 allocation using O(log m) queries, but we ﬁrst need to develop some machinery for the case where the agents have identical valuations.

4.1 Identical Additive Valuations While the case of identical additive valuations might seem trivial at ﬁrst glance, as we will see, there are already several interesting statements that we can make about the setting, so it may be of independent interest. We begin by establishing some properties of a particular partition of goods on a line into two contiguous blocks.

Lemma 4.1. Assume that the goods lie on a line. Suppose that an agent with an additive valuation u chooses the partition of the goods into two contiguous blocks that minimizes the difference between the values of the two blocks. (If there are goods of value 0 next to the cut point, move the cut point until these goods belong to the block of lower value.) Let L be the left block and gl the rightmost good of the block. Similarly, let R be the right block and gr the leftmost good of the block. Then:

1. We have that min{u(G)/2, u(L)} u(R\{gr}) and min{u(G)/2, u(R)} u(L\{gl}). 2. The partition can be computed using O(log m) queries in the worst case.

Next, we present an algorithm that computes a contiguous EF1 allocation for three agents with identical valuations using a logarithmic number of queries. Not only will the contiguity condition be useful later in our algorithm for three agents with arbitrary valuations, but in certain applications it may also be desirable to produce a contiguous allocation. For example, if the goods are ofﬁce space, it is conceivable that each research group wishes to have a consecutive block of ofﬁces in order to facilitate collaboration within the group. While contiguous fair allocations of indivisible goods have recently been studied (Bouveret et al. 2017; Suksompong 2017), to the best of our knowledge even the existence of a contiguous EF1 allocation for three agents with identical valuations has not been established before, let alone an algorithm that computes such an allocation using a

small number of queries. Hence our result may be of interest even if one is not concerned with the number of queries made. In the full version of our paper (Oh, Procaccia, and Suksompong 2018), the existence result is generalized to any number of agents with identical monotonic valuations.3

Algorithm 2 (for three agents with identical additive valuations)

Step 1: Assume that the goods lie on a line, and denote by u the common valuation of the three agents. Let g1 be the leftmost good such that u(Lg1 {g1}) > u(G)/3, and let g2 be the rightmost good such that u(Rg2 {g2}) > u(G)/3. (Possibly g1 = g2.) Assume without loss of generality that u(Lg1) u(Rg2).

Step 2: If Lg1 = , let g3 be the leftmost good such that u(Lg3 {g3}) u(Rg2). Set A = Lg3 {g3}. Else, set A = . In both cases, set C = Rg2 and B = G\(A C).

Step 3: If u(C) u(B\{g2}), return the allocation (A, B, C). Else, set C = Rg2 {g2}. Partition the remaining goods into two contiguous blocks according to Lemma 4.1; denote by A the left block and B the right block. Return the allocation (A , B , C ).

The following lemma establishes the claimed properties of Algorithm 2.

Lemma 4.2. Assume that the goods lie on a line. For three agents with identical additive valuations, Algorithm 2 computes a contiguous EF1 allocation. Moreover, the algorithm can be implemented to use O(log m) queries in the worst case.

A bonus of Algorithm 2 is that in the allocation produced by the algorithm, if some agent envies another agent, then the envy can be eliminated by removing not just some arbitrary good from the latter agent s bundle, but one of the goods at the end of the latter agent s block. In fact, we can also choose this good to be a good next to a cut point; this nails down a unique good for the agents getting the left or right block. The property can be deduced from the proof of Lemma 4.2. To demonstrate that even the problem of establishing the existence of a contiguous EF1 allocation in this setting is not straightforward, we present a very natural approach that, perhaps surprisingly, does not work. We ﬁrst pretend that the goods are divisible and ﬁnd the two cut points that would divide the goods into three parts of exactly equal value. For each cut point, if the cut point falls between two (now indivisible) goods, we keep it; otherwise we round it either to the left or to the right. One might be tempted to claim that

3After we published an initial version of our paper, Bil o et al. (2019) independently proved this generalization. In addition, they showed the existence of an EF1 allocation for up to four agents with arbitrary monotonic valuations.

at least one of the resulting allocations must be EF1. Indeed, Lemma 4.1 implies that an analogous approach works for two agents. However, an example given in the full version of our paper (Oh, Procaccia, and Suksompong 2018) shows that the approach does not work for three agents, no matter how we round the cut points. Next, we leverage Algorithm 2 to show that for three agents with identical additive valuations, if we designate three goods in advance, it is possible to compute an EF1 allocation such that all three designated goods belong to different bundles.

Lemma 4.3. Let g1, g2, g3 be three distinct goods. For three agents with identical additive valuations, there exists a deterministic algorithm that computes an EF1 allocation such that the three goods belong to three different bundles using O(log m) queries in the worst case.

Note that for two agents, an analogous statement holds even when the agents have arbitrary monotonic valuations, since we can place the two designated goods at different ends of a line and apply Algorithm 1.

4.2 Arbitrary Additive Valuations

With Algorithm 2 and Lemma 4.3 in hand, we are now ready to present an algorithm that computes an EF1 allocation for three agents with arbitrary additive valuations using a logarithmic number of queries. The algorithm is based on the Selfridge-Conway procedure for computing an envy-free allocation of divisible goods, often modeled as a cake, for three agents. At a high level, the Selfridge-Conway procedure operates by letting the ﬁrst agent divide the cake into three equal pieces and letting the second agent trim her favorite piece so that it is equal to her second favorite piece. Then, the procedure allocates one main piece to each agent, with the third agent choosing ﬁrst, and allocates the leftover cake in a carefully designed way. Like the Selfridge-Conway procedure, our algorithm starts by letting the ﬁrst agent divide the goods into three almost equal bundles using Algorithm 2, so that no matter how the bundles are allocated, the agent ﬁnds the allocation to be EF1. It then proceeds by letting the second agent trim her favorite bundle so that her value for the bundle goes just below that for her second favorite bundle. However, a difﬁculty in our indivisible goods setting is that at this point, the second agent might ﬁnd the remaining part of her favorite bundle to be worth less than her second favorite bundle even if we remove any good from her second favorite bundle. This is possible, for instance, if the last good that she removes from her favorite bundle is of high value, and her second favorite bundle only consists of goods of low value. We will need to ﬁx this problem by ﬁnding large goods in the leftover bundle that help us recover the EF1 guarantee; this is done in Step 3 of the algorithm. While identifying these large goods can be done easily if we can make queries for the value of every good in the leftover bundle, we would not achieve the logarithmic bound if the leftover piece contained more than a logarithmic number of goods.

Algorithm 3 (for three agents with additive valuations)

Step 1: Compute an EF1 allocation (A, B, C) for three identical agents with valuation u1. If a2 and a3 have different favorite bundles among A, B, C, give them their favorite bundles, and give the remaining bundle to a1. Else, assume without loss of generality that u2(A) > u2(B) u2(C) and u3(A) > max{u3(B), u3(C)}.

Step 2: Let a2 divide A into A and T such that u2(A ) u2(B) and there exists g T with u2(A {g}) > u2(B). If u3(A ) max{u3(B), u3(C)}, give A to a3, B to a2, and C to a1. Compute an EF1 allocation (T1, T2, T3) of the goods in T for three identical agents with valuation u2. Let a3 choose her favorite bundle followed by a1, and let a2 take the remaining bundle. Else, we have u3(A ) < max{u3(B), u3(C)}.

Step 3: Deﬁne d = u2(B) u2(A ) 0. Call a good g large if g T and u2(g) d, where we update A , T, and d during the course of the step. Let a2 ﬁnd up to three large goods. The ﬁrst large good is the good g T such that u2(A {g}) > u2(B). To ﬁnd further large goods, let E T be such that u2(E) d, u2(E\{g}) < d for some g E, and E does not contain any identiﬁed large good. If such a set E (and good g) exists, remove the goods in E\{g} from T and add them to A , and decrease d by u2(E\{g}). (For the ﬁrst large good, take E = {g}.) Then g is a new large good. If u3(A ) max{u3(B), u3(C)} with the updated set A , allocate the goods according to Step 2. So we may still assume that u3(A ) < max{u3(B), u3(C)}. On the other hand, if no such set E exists, remove all goods except the (up to two) identiﬁed large goods from T and add them to A , and decrease d by a2 s value for these goods.

Step 4: Compute an EF1 allocation (T1, T2, T3) of the goods in T for three identical agents with valuation u3 in such a way that all identiﬁed large goods belong to different bundles.

Step 5: Let S3 be a3 s preferred bundle between B and C, and let S1 be the other bundle. Give S2 := A to a2, S3 to a3, and S1 to a1.

Step 6: If there is an identiﬁed large good in each of T1, T2, and T3, give a2 her favorite bundle Ti if we were to remove the identiﬁed large good from each of these bundles. Let a1 choose her preferred bundle from the remaining two bundles (without removing the large goods), and give a3 the remaining bundle. Else, give the ﬁrst identiﬁed large good to a2 and the second identiﬁed large good (if exists) to a1.

The following theorem, which we view as our main re-

sult, establishes the claimed properties of Algorithm 3 by leveraging the machinery developed above. Theorem 4.4. For three agents with additive valuations, Algorithm 3 computes an EF1 allocation. Moreover, the algorithm can be implemented to use O(log m) queries in the worst case.

5 Any Number of Agents In this section, we consider the general setting where there can be any number of agents. We state and discuss some results here, and relegate several results that require stronger assumptions to the full version of our paper (Oh, Procaccia, and Suksompong 2018). Our starting point is the envy cycle elimination algorithm of Lipton et al. (2004), which computes an EF1 allocation for agents with arbitrary monotonic valuations. The algorithm works by allocating one good at a time in arbitrary order. It also maintains an envy graph, which has the agents as its vertices, and a directed edge from ai to aj if ai envies aj with respect to the current (partial) allocation. At each step, the next good is allocated to an agent with no incoming edge, and any cycle that arises as a result is eliminated by giving aj s bundle to ai for any edge from ai to aj in the cycle. This allows the algorithm to maintain the invariant that the envy graph has no cycles and therefore has an agent with no incoming edge before each allocation of a good. The envy cycle elimination algorithm runs in time O(n3m) in the worst case. We refer to the paper of (Lipton et al. 2004) for the proof of correctness and detailed analysis of this algorithm. Our main positive result for this section is the observation that the envy cycle elimination algorithm can be implemented using a relatively modest number of (value) queries. Theorem 5.1. For any number of agents with arbitrary monotonic valuations, the envy cycle elimination algorithm can be implemented to compute an EF1 allocation using: 1. O(nm) queries in the worst case. 2. O(n3k log m) queries in the worst case, if the valuation of each agent takes at most k (possibly unknown) values across all subsets of goods. Theorem 5.1 illustrates a sharp contrast between EF1 and the stronger fairness notions of envy-freeness and EFX. For the latter two notions, computing a fair allocation requires an exponential number of queries in the worst case, even in the most restricted setting of two agents with identical valuations. On the other hand, for EF1 we can get away with only O(nm) queries even in the most general setting of any number of agents with arbitrary monotonic valuations. Moreover, if n and k are small compared to m, the bound of Item 2 of the theorem can be better than that of Item 1. In particular, if n and k are constant, the implementation only requires O(log m) queries. The case of k = 2 corresponds to the setting where each agent either approves or disapproves each subset of goods.4 A small value of k may occur in settings where the mechanism designer gives a predeﬁned set

4This is not to be confused with what we call binary valuations in this paper, for which k can be as large as m.

of preferences that the agents can express on each subset of goods, e.g., very interested , somewhat interested , and not interested . To complement this positive result, we conclude by giving a lower bound (which, sadly, does not match the upper bound) on the number of queries needed to compute an EF1 allocation.

Theorem 5.2. Let m nα for some constant α > 1. Any deterministic algorithm that computes an EF1 allocation for n agents with binary valuations uses Ω(n log m) queries in the worst case.

Proof. Assume ﬁrst that n is even, say n = 2k, and that each agent has value 1 for two goods and 0 for the remaining goods. Suppose further that for i = 1, 2, . . . , k, agents a2i 1 and a2i have identical valuations; we abuse notation and denote this valuation by ui. Note that if both of the goods valued by some agent are allocated to a single agent, the resulting allocation cannot be EF1. Initially, for each i = 1, 2, . . . , k, let Gi be the whole set of goods. As long as |Gi| > 2, we answer the query of the algorithm on the value of ui(H) for a subset H of goods as follows. If |Gi H| |Gi|/2, answer 2 and replace Gi by Gi H; else, answer 0 and replace Gi by Gi\H. While |Gi| > n, the only information that the algorithm has is that both valued goods are contained in Gi. This information is not sufﬁcient to return an allocation such that the two valued goods are guaranteed to be in different bundles, so the algorithm must keep making queries until |Gi| n for every i. Since initially |Gi| = m and the size of Gi decreases by no more than half with each query, the algorithm uses at least k log(m/n) queries in the worst case. The conclusion follows from the observation that log(m/n) α 1

α log m. If n is odd, we can assume that the last agent has value 0 for all goods and deduce the same asymptotic bound using the remaining n 1 agents.

Since the assumption of Theorem 5.2 holds for any constant n if m is large enough, and when n = 2 the two agents considered in the proof have identical valuations and each agent values only two goods, this theorem implies Proposition 3.2.

6 Discussion From a technical viewpoint, the main take-home message of our work is this: Envy-free cake cutting protocols, designed for divisible goods, can be adapted to yield EF1 allocations of indivisible goods using a logarithmic number of queries. On a high level, the idea is to arrange the goods on a line, and approximately implement cut operations using binary search. We do this to obtain Theorem 3.1, by adapting the cut-and-choose protocol, and Theorem 4.4, by building on the classic Selfridge-Conway protocol. However, making sure the approximation errors do not add up in a way that violates EF1 already becomes nontrivial when there are three agents, as illustrated by Algorithm 3 and Theorem 4.4. Extending the approach even to four agents with arbitrary additive valuations, therefore, seems very challenging. A related difﬁculty is that

the known envy-free cake cutting protocols for four or more agents are quite involved (Brams and Taylor 1995; Aziz and Mackenzie 2016a; 2016b; Amanatidis et al. 2018). Another intriguing question is whether the logarithmic upper bound on the complexity of EF1 extends to three agents with monotonic valuations. Such valuations cannot be handled by the Selfridge-Conway procedure, which is designed for the cake cutting setting where additivity is assumed. Of course, it is possible that, in fact, there is superlogarithmic lower bound on the query complexity in this case.

Acknowledgments This work was partially supported by the National Science Foundation under grants IIS-1350598, IIS-1714140, CCF1525932, and CCF-1733556; by the Ofﬁce of Naval Research under grants N00014-16-1-3075 and N00014-17-12428; and by a Sloan Research Fellowship, a Guggenheim Fellowship, and a Stanford Graduate Fellowship.

References Amanatidis, G.; Christodoulou, G.; Fearnley, J.; Markakis, E.; Psomas, C.-A.; and Vakaliou, E. 2018. An improved envy-free cake cutting protocol for four agents. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), 87 99. Aziz, H., and Mackenzie, S. 2016a. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), 416 427. Aziz, H., and Mackenzie, S. 2016b. A discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 454 464. Bil o, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2019. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), 14:1 14:21. Bouveret, S., and Lemaˆıtre, M. 2016. Characterizing conﬂicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems 30(2):259 290. Bouveret, S.; Cechl arov a, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 135 141. Brams, S. J., and Taylor, A. D. 1995. An envy-free cake division protocol. The American Mathematical Monthly 102(1):9 18. Brams, S. J., and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Budish, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6):1061 1103.

Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), 305 322. Deng, X.; Qi, Q.; and Saberi, A. 2012. Algorithmic solutions for envy-free cake cutting. Operations Research 60(6):1461 1476. Edmonds, J., and Pruhs, K. 2006. Cake cutting really is not a piece of cake. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 271 278. Foley, D. 1967. Resource allocation and the public sector. Yale Economics Essays 7:45 98. Goldman, J., and Procaccia, A. D. 2014. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13(2):41 46. Kurokawa, D.; Procaccia, A. D.; and Wang, J. 2018. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM 64(2): article 8. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 6th ACM Conference on Economics and Computation (EC), 125 131. Moulin, H. 2003. Fair Division and Collective Welfare. MIT Press. Oh, H.; Procaccia, A. D.; and Suksompong, W. 2018. Fairly allocating many goods with few queries. ar Xiv:1807.11367. Plaut, B., and Roughgarden, T. 2018. Almost envy-freeness with general valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2584 2603. Procaccia, A. D. 2009. Thou shalt covet thy neighbor s cake. In Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI), 239 244. Procaccia, A. D. 2013. Cake cutting: Not just child s play. Communications of the ACM 56(7):78 87. Robertson, J. M., and Webb, W. A. 1998. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters. Steinhaus, H. 1948. The problem of fair division. Econometrica 16:101 104. Stromquist, W. 1980. How to cut a cake fairly. American Mathematical Monthly 87(8):640 644. Suksompong, W. 2017. Fairly allocating contiguous blocks of indivisible items. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), 333 344.