# envyfree_division_of_sellable_goods__c6c122a5.pdf

Envy-Free Division of Sellable Goods

Jeremy Karp Tepper School of Business Carnegie Mellon University jkarp@andrew.cmu.edu

Aleksandr M. Kazachkov Tepper School of Business Carnegie Mellon University akazachk@cmu.edu

Ariel D. Procaccia Computer Science Department Carnegie Mellon University arielpro@cs.cmu.edu

We study the envy-free allocation of indivisible goods between two players. Our novel setting includes an option to sell each good for a fraction of the minimum value any player has for the good. To rigorously quantify the efﬁciency gain from selling, we reason about the price of envy-freeness of allocations of sellable goods the ratio between the maximum social welfare and the social welfare of the best envy-free allocation. We show that envy-free allocations of sellable goods are signiﬁcantly more efﬁcient than their unsellable counterparts.

1 Introduction After decades of unresolved communication problems (Kushilevitz and Nisan 1996), Alice and Bob have decided to get a divorce. Their worldly goods include a well-worn (shared) blackboard, a museum-quality collection of private keys, and a 19th century French vase. Can Alice and Bob divide these goods in a way that is fair to both sides? To answer this question we must be more speciﬁc about what we mean by fair . The notion of envy-freeness provides a natural interpretation: Alice (weakly) prefers her own bundle of goods to Bob s bundle, and Bob is likewise convinced that he got the better deal. In other words, when the allocation is envy free, neither Alice nor Bob is interested in swapping bundles. While envy-freeness is a compelling ideal, envy may clearly be unavoidable when the goods are indivisible. But envy-freeness can nevertheless be achieved if we are willing to split one of the goods. This concession enables the famous Adjusted Winner (AW) protocol (Brams and Taylor 1996) an envy-free protocol that has been patented by New York University and licensed to the law ﬁrm Fair Outcomes, Inc. In their book, Brams and Taylor (1996, pp. 102 108) apply AW to the real divorce case of Jolis vs. Jolis, which was decided in 1981 (let us call the wife Alice Jolis, and the husband Bob Jolis). The marital property included a Paris apartment, a Paris studio, a New York City coop, a farm, cash and receivables, securities, a proﬁt-sharing plan, and a life insurance policy. Deducing Alice and Bob s values for these

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

goods (from available data) and applying AW yields an allocation that gives the studio, coop, farm, securities, and life insurance policy to Bob, the Paris apartment to Alice, and splits the cash (giving a 1/11 fraction to Bob and the rest to Alice). In this case AW split a good that happens to be divisible, but this is by no means guaranteed: had Alice and Bob expressed different preferences, AW could have split one of the indivisible goods, say, the Paris apartment. In practice, this would typically mean selling the Paris apartment and splitting the cash. However, for example, 40% of the market price of the Paris apartment may not be equal to 40% of Bob s value for owning the entire apartment, invalidating the assumptions underlying AW and thus nullifying its guarantees. Moreover, if we are indeed allowed to sell goods, perhaps there is a better envy-free allocation? This paper is motivated by the preceding observations and questions, which, we believe, call for an explicit model of the envy-free division of sellable goods.

1.1 Our Approach and Formal Model We consider a setting with two players, Alice (denoted A) and Bob (denoted B). Our approach cannot give rise to nontrivial positive results when there are more than two players, as we discuss in Section 4. There is also a set of m indivisible goods to be allocated, denoted by [m] = {1, . . . , m}. For each j [m] and P {A, B}, P s value for j is denoted v P (j) [0, 1]. We make two assumptions regarding the valuation functions: 1. Additivity: For P {A, B} and J [m], v P (J) = P j J v P (j). In particular, v P ( ) = 0.

2. Normalization: For P {A, B}, it holds that v P ([m]) = P j [m] v P (j) = 1.

An allocation (partition of the goods between Alice and Bob) X = {XA, XB} is envy free if v A(XA) v A(XB) and v B(XB) v B(XA). We are also interested in the economic efﬁciency of allocations, which we measure via their (utilitarian) social welfare: SW(X, v A, v B) = v A(XA) + v B(XB). Our main conceptual contribution is the idea that indivisible goods can be sold, and thereby converted into an inﬁnitely divisible cash value (which Alice and Bob value equally). We assume that there is a universal constant c

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

(0, 1] such that the selling price of a set of goods J [m] is c P j J min{v A(j), v B(j)}. The rationale is that Alice and Bob both value each good at least at its market value, because they can always sell a good they have obtained. But their value for a good can be strictly higher than its market value this is captured by the constant c. While we assume, for ease of exposition, that the price is exactly a c-fraction of the minimum value, our results naturally hold if this expression is just a lower bound; this observation is important when different goods can be sold for different fractions of the minimum value. With this in mind, we deﬁne an allocation with selling as X = {XA CA, XB CB}, where CA and CB are cash derived from the sale of a subset of the items, given to Alice and Bob, respectively. To rigorously quantify the gain from selling, we use the notion of (utilitarian) price of envy-freeness, independently introduced by Caragiannis et al. (2012) and (in slightly different form) by Bertsimas et al. (2011). For valuation functions v A, v B, let OPT(v A, v B) be the social welfare of the welfare-maximizing allocation; i.e., OPT(v A, v B) max X SW(X, v A, v B). Similarly, deﬁne OPTEF(v A, v B) to be the social welfare of the welfare-maximizing envyfree allocation without selling, and OPTEFS(v A, v B) to be the social welfare of the welfare-maximizing envyfree allocation with selling. The price of envy-freeness is the worst-case (over valuation functions v A, v B) ratio OPT(v A, v B)/OPTEF(v A, v B). With selling, it is the worstcase ratio OPT(v A, v B)/OPTEFS(v A, v B). Hereinafter the valuation functions will always be clear from the context, so we simply write OPT, OPTEF and OPTEFS. We now formulate our primary research challenge:

Show that the option to sell goods provides a major boost to efﬁciency by establishing that the price of envy-freeness with selling is signiﬁcantly lower than the price of envy-freeness without selling.

1.2 Our Results

Table 1 summarizes our results regarding the price of envyfreeness. The columns distinguish between two scenarios: (i) the general setting where an envy-free allocation without selling may not exist, and (ii) such an allocation does exist. The ﬁrst row shows our bounds on the price of envy-freeness with selling (which are tight), the second row instantiates these bounds for c = 1, and the third row gives the price of envy-freeness without selling. In scenario (i), the price of envy-freeness without selling is (or, alternatively, it is not well deﬁned). In contrast, our analysis (Theorem 1) gives a bound of 3/2 for the case of c = 1. In scenario (ii), Caragiannis et al. (2009) show that the price of envy-freeness (without selling) is 3/2; our bound (Theorem 2) instantiates to 6/5 when c = 1. As c 0, our results match the bounds without selling. We also investigate the problem of computing a social welfare maximizing allocation of sellable goods. While the problem is NP-complete (Theorem 3), we show that, when c = 1, it admits a fully polynomial time approximation scheme (Theorem 4).

Is there an EF allocation?

Selling max{ 3 c

c+c2 , 3 1+c} max{ 3 2c

2 c , 6 4+c}

Selling (c = 1) 3/2 6/5

No selling 3/2

Table 1: Summary of our results.

1.3 Additional Context and Signiﬁcance in AI The rigorous study of fair division dates back to the work of Steinhaus (1948). Over the years a deep theory has been developed by economists, mathematicians, and political scientists; see, e.g., the books by Brams and Taylor (1996) and Moulin (2003). More recently, the study of fair division has attracted signiﬁcant attention from the AI community. This relatively newfound interest is partly motivated by the idea that fair division theory can inform the design of multiagent systems (Chevaleyre et al. 2006). The fair division literature makes a distinction between two typically disjoint cases, depending on whether the goods are divisible or indivisible. The divisible case usually involves a single, heterogeneous good, and the task of dividing this good is known as cake cutting. This setting has been extensively studied by AI researchers in recent years (Procaccia 2009; Chen et al. 2013; Caragiannis, Lai, and Procaccia 2011; Cohler et al. 2011; Brams et al. 2012; Bei et al. 2012; Kurokawa, Lai, and Procaccia 2013; Brˆanzei, Procaccia, and Zhang 2013); see the survey by Procaccia (2013) for an overview. In the context of indivisible goods, AI researchers have also studied issues like complexity, preference handling, and incentives (Bouveret and Lang 2008; 2011; Kalinowski et al. 2013). Our work attempts to bridge these two worlds, by essentially allowing the division of indivisible goods at a cost. In this sense, our paper is somewhat related to a line of work on reaching envy-free states through distributed negotiation over indivisible goods (Chevaleyre et al. 2007; Chevaleyre, Endriss, and Maudet 2007; 2010), because these papers allow players to pay each other in order to achieve envy-freeness (as long as the sum of payments is zero). That said, our motivation, questions, approach, and results are all fundamentally different.

2 Bounds on the Price of Envy-Freeness To gain some intuition for price of fairness bounds, we start by discussing the price of envy-freeness without selling. As mentioned above, Caragiannis et al. (2009) restrict their attention to instances where an envy-free allocation does exist, and for these instances show that OPT/OPTEF < 3/2. The proof is simple. First, notice that a player is not envious if and only if his or her bundle is worth at least 1/2 (because the sum of values for the two bundles is 1). Now, if the optimal allocation is envy-free we are done. If not, on the one hand either Alice or Bob is envious under the optimal solution, so OPT < 1 + 1/2 = 3/2; and on the other hand, OPTEF 1/2 + 1/2 = 1. Crucially, Caragiannis et

al. (2012) also show that this bound is tight; i.e., for every ϵ > 0 there is an example where the ratio is 3/2 ϵ. In contrast, when the goods are sellable, there always exists an envy-free allocation, so the price of envy-freeness is always well deﬁned. Interestingly, it turns out that the price of envy-freeness (with selling) when an envy-free allocation without selling is assumed to exist (Theorem 2) is signiﬁcantly lower than the price of envy-freeness in the general case (Theorem 1), so we present these results as two separate theorems, starting with the (simpler, surprisingly) general case. Theorem 1. When an envy-free solution without selling does not exist for a particular instance, for any c (0, 1], OPT OPTEFS max{ 3 c

c+c2 , 3 1+c}.

Before proving the theorem, we demonstrate that the bound is tight. For c (0, 3/4] it holds that 3 c

c+c2 3 1+c. Let there be two goods, and let v A(1) = 1 c/2 ϵ, v A(2) = c/2+ϵ, v B(1) = 1/2+ϵ, v B(2) = 1/2 ϵ, for an arbitrarily small ϵ > 0. We have OPT = 3/2 c/2 2ϵ. The only way to get an envy-free allocation is to sell both goods, and split the cash equally. The value of the resulting allocation is just the amount of cash: OPTEFS = c (1/2+ϵ+c/2+ϵ) (c+c2)/2. Then OPT/OPTEFS (3 c)/(c + c2). For c [3/4, 1], 3 1+c 3 c c+c2 . Let v A(1) = 1, v A(2) = 0, v B(1) = 1/2 + ϵ, v B(2) = 1/2 ϵ, for an arbitrarily small ϵ > 0. For this instance, OPT = 3/2 ϵ. To obtain an EF allocation, good 1 must be sold we then allocate good 2 to Bob and divide that cash so that Alice and Bob are both satisﬁed. Therefore, OPTEFS = c (1/2 + ϵ) + (1/2 ϵ) (c + 1)/2, and OPT/OPTEFS 3/(1 + c).

Proof of Theorem 1. Suppose we start with a social welfare maximizing allocation S = {SA, SB}, and assume without loss of generality that v A(SA) v B(SB). It holds that v A(SA) v B(SA) and v B(SB) v A(SB), because to maximize social welfare each good is allocated to the player who values it more highly. Since no envy-free solution exists without selling, we have that 1 v A(SA) v B(SA) > 1/2 > v B(SB) v A(SB). Thus, selling only SB would leave the player that does not receive SA envious. Hence, to obtain an envy-free allocation, it may be necessary to sell the entirety of SA, in the worst case that it is a single good. It may also be required to sell SB to guarantee the existence of an envy-free allocation. If only SA is sold, it is possible that the player that does not receive SB will be envious, if v A(SB) > c v B(SA).

Case 1: v A(SB) c v B(SA). In this case we only sell SA. Alice s total remaining value is

v A(SB) + c v B(SA) = 1 v A(SA) + c v B(SA) 1 (1 c) v B(SA),

and Bob s total remaining value is 1 (1 c) v B(SA). We ﬁrst show that there is enough cash from selling SA to satisfy both Alice and Bob in an envy-free allocation. Suppose that v B(SB) c v B(SA); i.e., Bob does not need to be given any cash to be envy-free. Alice s total (remaining) value is v A(SB) + c v B(SA) 2c v B(SA), so giving her the cash will make her envy-free.

Otherwise, suppose Bob is not immediately envy-free after selling SA. It is easy to see there is enough cash to satisfy both Alice and Bob, since the following equation can be obtained by rearranging the terms of the identity v B(SA) + v B(SB) = 1:

c v B(SA) = 1

2(1 (1 c) v B(SA))

2(1 (1 c) v B(SA)) v B(SB) .

We conclude that in Case 1 we can obtain an envy-free allocation by selling only SA and letting Bob keep SB. This yields

OPTEFS c v B(SA) + v B(SB) = 1 (1 c) v B(SA).

Since OPT 2 v B(SA), and letting x v B(SA),

OPT OPTEFS 2 x 1 (1 c) x g(x, c).

We want the maximum of g over the entire range v B(SA) [1/2, 1]. The partial derivative of g with respect to x is

x = 1 2c (1 (1 c) x)2 .

Thus, the maximum occurs at g(1/2, c) for all c [1/2, 1], since for such c, g is non-increasing as x increases, and at g(1, c) for all c (0, 1/2], since for these values, g is nondecreasing as x increases. Hence,

OPT OPTEFS max 1

3 2 1 (1 c) 1

c , 3 1 + c

Case 2: v A(SB) > c v B(SA). It may be required to sell both SA and SB to guarantee the existence of an envy-free solution, if both are single goods. Take the allocation in which everything is sold and the resulting cash is split evenly. We have already established that v B(SA) > 1/2. As a result,

OPT = 2 (v A(SB) + v B(SA)) < 2 c/2 1/2,

OPTEFS c (v A(SB) + v B(SA)) > c (1 + c) v B(SA)

> c (1 + c) 1

Thus, OPT OPTEFS < 3 c c+c2 .

Wrapping up. Since 3 c c+c2 1 c for all c 1, we proved OPT OPTEFS max{ 1

c+c2 , 3 1+c} = max{ 3 c

c+c2 , 3 1+c}.

Next, we assume that an envy-free allocation without selling exists. Recall that in this case, even without selling the price of envy-freeness is 3/2 (so Theorem 1 does not give a better bound). However, we are able to show that, with selling, the price of envy-freeness is signiﬁcantly lower. In particular, for c = 1, the price of envy-freeness is only 6/5. Theorem 2. Suppose an envy-free solution without selling exists for a particular instance. Then for c (0, 1], OPT OPTEFS max{ 3 2c

2 c , 6 4+c}.

Once again, before proving the theorem we give an example showing that the bound is tight. For c [1/2, 1] it holds that 6 4+c 3 2c

2 c . Let there be four goods, with values given by the following table:

1 2 3 4 v A 1 ϵ

2 ϵ 0 v B 1/4 + ϵ 1/4 + ϵ 1/4 ϵ 1/4 ϵ

ϵ > 0 is arbitrarily small. Note that an envy-free allocation without selling exists (Alice gets 1 and 3 and Bob gets 2 and 4). Moreover, we have that OPT 3/2. The optimal envyfree allocation with selling would sell either 1 or 2, resulting in OPTEFS 1 + c/4. Thus, OPT/OPTEFS 6/(4 + c). For c (0, 1/2], the values are given by the following table:

1 2 3 4 v A 1 ϵ

1/2 2 c ϵ 1/2 2 c ϵ (1 c)/2

2 c + ϵ (1 c)/2

The social welfare maximizing solution, where Alice receives 1 and 2 and Bob receives 3 and 4, yields a total value of OPT (3 2c)/(2 c). The envy-free with selling solution sells 1 or 2, and yields OPTEFS = 1. The ratio is therefore roughly (3 2c)/(2 c). We are now ready to prove the theorem. The proof is quite long and intricate, so the proofs of several lemmas are omitted. All omitted proofs can be found in the extended version of the paper.1

Proof of Theorem 2. Let X = {XA CA, XB CB} be an allocation where XA and XB are disjoint subsets of the goods and CA + CB is the cash obtained from selling [m] \ (XA XB). We let

XA {j XA : v A(j) < v B(j)},

XB {j XB : v B(j) < v A(j)},

and deﬁne their complements, XA XA \ XA, and XB XB \ XB. We have assumed that an envy-free allocation without selling exists, so let Y = {YA, YB} be a social welfare maximizing envy-free allocation without selling; that is, OPTEF = SW(Y, v A, v B). Note that OPTEF 1, because v A(YA) 1/2 and v B(YB) 1/2 due to envy-freeness. Without loss of generality, assume that v A(YA) v B(YB). Note that when v A(YA) 1/2, Y satisﬁes YA = (so that v A(YA) = v B(YA) = 0), since giving those goods to Alice is not necessary for envy-freeness, and Alice values them strictly less than Bob. Next, S = {SA, SB} will refer to a particular social welfare maximizing allocation: SA = YA YB, and SB = YB YA. Note that when v B(YB) = 0, v A(YA) + v B(YB) = 0, so SW(S) = SW(Y), in which case the price of fairness is 1. This is not an interesting case so assume henceforth that

1Available at: http://cs.cmu.edu/ arielpro/papers

the price of envy-freeness is strictly greater than one; i.e., assume v B(YB) > 0. Our ﬁrst lemma is used throughout the theorem s proof.

Lemma 1. v A(SA) 1

2 and v B(SB) < 1

Consider the following two allocations. They both begin with the allocation S, and involve Alice selling one of YA or YB.

Allocation 1. Alice sells YB and gives Bob cash worth

C1 B max 0, 1

2 v B(YB) v B(YB) v B(YA) .

Let C1 A c v B(YB) C1 B be Alice s remaining cash. Then deﬁne Z1 {YA C1 A, YB YA C1 B}. Note that Alice s value for all the remaining goods and the cash from the sale is 1 v A(YB) + c v B(YB) 1 (1 c) v B(YB), while Bob s value for everything is 1 (1 c) v B(YB).

Allocation 2. Alice sells YA and gives Bob cash worth

C2 B max 0, 1

2 v B(YA) v B(YB) v B(YA) .

Let C2 A c v B(YA) C2 B. Then deﬁne Z2 {YB C2 A, YB YA C2 B}. Observe that Alice s value for all the remaining goods and the cash from the sale is 1 v A(YA) + c v B(YA) 1 (1 c) v B(YA), while Bob s value for everything is 1 (1 c) v B(YA). The next two lemmas show that, if the two allocations Z1 and Z2 have enough cash, then they are envy free and provide certain guarantees with respect to social welfare.

Lemma 2. Assume that C1 B c v B(YB) (that is, there is enough cash to give to Bob under Allocation 1), and OPT > 6 4+c. Then the allocation Z1 is envy free, and SW(Z1) = v A(YA) + v B(YA) + v B(YB) + c v B(YB).

Proof. The statement about the value of SW(Z1) is trivial. Turning to envy-freeness, clearly Bob has no envy in this transaction, since his value is

v B(YB) + v B(YA) + v B(C1 B) 1 (1 c) v B(YB)

i.e., half his total (remaining) value. We need to show that Alice is not envious.

Case 1: C1 B = 0. Note that this case cannot happen if c = 1, since then 1/2 v B(YB) v B(YA) 0, contradicting Lemma 1. Thus, suppose c (0, 1). We show that if Alice receives YA and all the cash, then she would not envy Bob. Assume for the sake of contradiction that Alice would actually envy Bob: v A(YA) + v A(YB) > v A(YA) + c v B(YB).

Note that, by Lemma 1, v B(YA) + v B(YB) = v B(SA) > 1/2. Since we are assuming OPT > 6 4+c, and

6 4 + c < OPT = 2 (v B(YA) + v B(YB) + v A(YA) + v A(YB))

2 (v A(YA) + v A(YB)),

it follows that v A(YA) + v A(YB) < 3c 2(4+c). By our earlier assumption that Alice would envy Bob,

3c 2(4 + c) > v A(YA) + v A(YB)

> v A(YA) + c v B(YB)

v B(YA) + c v B(YB)

= v B(YA) + v B(YB) (1 c) v B(YB)

2 (1 c) v B(YB).

Thus, v B(YB) > 2 c (1 c)(4+c). This value is strictly greater than 1/2 for all c (0, 1), which is a contradiction to the envy-freeness of Y, since then v A(YB) v B(YB) > 1/2. Hence, when C1 B = 0, v A(YA)+v A(YB) v A(YA)+c v B(YB), so Alice does not envy Bob.

Case 2: C1 B > 0. Alice s value is

v A(YA) + c v B(YB) 1

+ v B(YB) + v B(YA)

= v A(YA) + c v B(YB) 1

+ (1 v B(YB) v B(YA))

2 v B(YB) + v A(YA) v B(YA)

1 (1 c) v B(YB) ,

where the last line follows from the assumption that v A(YA) v B(YA). The right hand side is at least half of Alice s total (remaining) value.

The proofs of the following two lemmas, 3 and 4, are relegated to the full version of the paper.

Lemma 3. Assume that C2 B c v B(YA) (that is, there is enough cash to give to Bob under Allocation 2), and OPT 6 4+c. Then the allocation Z2 is envy free, and SW(Z2) = v A(YB) + v B(YA) + v B(YB) + c v B(YA).

At this point, it will be useful to deﬁne the maximum of Allocations 1 and 2, with respect to social welfare, as Z. That is,

( Z1 if v A(YA) + c v B(YB) > v A(YB) + c v B(YA), Z2 otherwise.

We will use C A to refer to the cash received by Alice in Z, and C B for the cash Bob receives in Z.

Lemma 4. When OPT 6 4+c OPTEF, Z has sufﬁcient cash: C A and C B are both non-negative.

With all the lemmas in place, we can now complete the proof of Theorem 2. Observe that the lemmas imply Z is envy-free. Also note that OPTEF 1, so assuming OPT > max{ 3 2c

2 c , 6 4+c} OPTEF allows Lemmas 2, 3, and 4 to apply. Since the maximum of two numbers is at least their average, and

v B(YA) + v B(YB) = OPT v A(YA) v A(YB) OPT 1,

we have that

OPTEFS SW(Z)

= max{v A(YA) + c v B(YB) + v B(YA) + v B(YB),

v A(YB) + c v B(YA) + v B(YA) + v B(YB)}

v A(YA) + v A(YB) + c (v B(YA) + v B(YB))

+ 2(v B(YA) + v B(YB))

OPT v B(YA) v B(YB)

+ c (1 v B(YA) v B(YB))

+ 2(v B(YA) + v B(YB))

OPT + c + (1 c)(v B(YA) + v B(YB))

(2 c) OPT + 2c 1 .

This implies

OPT OPTEFS 2 OPT (2 c) OPT + 2c 1 f(OPT, c).

For every c, we want to re-write this bound to be only in terms of c and not OPT. Note that it sufﬁces to consider OPT (max{ 3 2c

2 c , 6 4+c}, 3/2). This follows from the reasoning from the beginning of Section 2: if at least one player is envious, then OPT < 1 + 1/2 = 3/2. Since we want the bound to hold across the entire possible range of OPT, we need to take the maximum of f(OPT, c) over the range. Thus, we take the derivative, with respect to OPT, of f(OPT, c).

OPT = 4c 2 ((2 c) OPT + 2c 1)2 .

For c [1/2, 1], f OPT 0, so

OPT OPTEFS f 3

2, c = 6 4 + c.

For c (0, 1/2], f OPT 0 and max{ 3 2c

2 c , 6 4+c} = 3 2c

2 c , so OPT OPTEFS f 3 2c

2 c , c = 3 2c

3 An Algorithmic Retrospective Our theorems in Section 2 are existence results: they state that there always exists an envy-free allocation of sellable goods that yields a certain fraction of the optimal social welfare. The proof of Theorem 1 constructs an allocation that achieves the stated bound by selling portions of the social welfare maximizing allocation S. The allocation S is easy to compute (just give each good to the player that values it more). In contrast, from a computational viewpoint, the guarantees of Theorem 2 may be hard to achieve, as the proof requires Alice to sell bundles from a welfaremaximizing envy-free (without selling) allocation Y, which is far trickier to compute (Bouveret and Lang 2008). The optimal envy-free allocation with selling is at least as good as the allocations constructed in the two proofs. And, in theory, the option to sell goods may actually make its computation easy. Our next result shows that this is not the case.2 To be more formal, let us deﬁne the MAX-EFS(c) problem as follows: the input is the set of goods [m] that can be sold for a c-fraction of the minimum value, the valuation functions v A and v B, and k R+; the question is whether there is an envy-free allocation with social welfare at least k.

Theorem 3. For any c (0, 1], the MAX-EFS(c) problem is NP-complete.

Intuitively, though, what makes the problem hard is that, starting from a social welfare maximizing allocation (which is not envy free), an optimal solution would have to sell a set of goods that is sufﬁcient to satisfy the envious player, while losing as little value as possible. For c = 1, this can be formulated as a MIN-KNAPSACK problem, which admits a fully polynomial time approximation scheme (FPTAS) (Kellerer, Pferschy, and Pisinger 2004). Leveraging this insight, we establish following result.

Theorem 4. MAX-EFS(1) admits an FPTAS; i.e., there is an algorithm that, for any ϵ > 0, returns an envyfree allocation X (which possibly includes cash) such that SW(X, v A, v B) (1 ϵ) OPTEFS(v A, v B), and runs in polynomial time in the parameters of the problem and 1/ϵ.

Moreover, it is easy to see that for any value of c, MAXEFS(c) can be formulated as an integer linear program (ILP), which can be solved using a variety of practical algorithms. To conclude, we do not view Theorem 3 as a serious obstacle to solving fair division problems in our framework, and, in particular, to achieving the guarantees given by Theorems 1 and 2.

4 Discussion All of our results focus on the case of two players. This is because, when there are three or more players, the price of envy-freeness with selling is unbounded. To see why, let there be two goods and three players A, B, C; set v A(1) =

2A related computational problem is whether OPTEFS = OPT. This question does turn out to be tractable for c = 1; the proof is implicit in the arguments in the extended version of the paper. In contrast, the question of whether OPTEF = OPT is NP-complete.

v B(1) = 1 ϵ, v C(1) = 0, v A(2) = v B(2) = ϵ, and v C(2) = 1. Both goods needs to be sold to prevent envy, but this only generates ϵ cash. In contrast, the case of two players (which is of special signiﬁcance) gives rise to a rich collection of insights. Another assumption this one implicit worth discussing is the conversion between value and cash. We have assumed that Alice and Bob s valuations for the complete bundle of goods are normalized to 1. This assumption is also made in many other fair division papers that reason about utilitarian social welfare (see, e.g., (Caragiannis et al. 2009; Cohler et al. 2011; Brams et al. 2012)). In practice, this could mean assigning Alice and Bob the same number of points to distribute between goods. But the conversion to cash means that the normalized valuation of a good can be compared to its market value. This is clearly possible, for example, if Alice and Bob have the same actual value for the complete bundle of goods. In any case, the fact that c can be any number in (0, 1] gives us the ﬂexibility to handle a range of conversion schemes, possibly at the cost of slightly weaker guarantees. Finally, note that the Adjusted Winner protocol (Brams and Taylor 1996), discussed in Section 1, actually guarantees another fairness property called equitability: the players have equal values for their own bundles of goods. In principle, one can ask the same questions we have answered above about the price of equitability instead of envy-freeness but that would be a bit repetitive!

5 Acknowledgments

Karp was supported in part by NSF grant CCF-1218382. Procaccia was supported in part by NSF grant CCF1215883.

Bei, X.; Chen, N.; Hua, X.; Tao, B.; and Yang, E. 2012. Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence (AAAI), 1263 1269. Bertsimas, D.; Farias, V. F.; and Trichakis, N. 2011. The price of fairness. Operations Research 59(1):17 31. Bouveret, S., and Lang, J. 2008. Efﬁciency and envyfreeness in fair division of indivisible goods: logical representation and complexity. Journal of Artiﬁcial Intelligence Research 32:525 564. Bouveret, S., and Lang, J. 2011. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 73 78. Brams, S. J., and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Brams, S. J.; Feldman, M.; Morgenstern, J.; Lai, J. K.; and Procaccia, A. D. 2012. On maxsum fair cake divisions. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence (AAAI), 1285 1291.

Brˆanzei, S.; Procaccia, A. D.; and Zhang, J. 2013. Externalities in cake cutting. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 55 61. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2009. The efﬁciency of fair division. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), 475 482. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2012. The efﬁciency of fair division. Theory of Computing Systems 50(4):589 610. Caragiannis, I.; Lai, J. K.; and Procaccia, A. D. 2011. Towards more expressive cake cutting. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 127 132. Chen, Y.; Lai, J. K.; Parkes, D. C.; and Procaccia, A. D. 2013. Truth, justice, and cake cutting. Games and Economic Behavior 77:284 297. Preliminary version in AAAI 10. Chevaleyre, Y.; Dunne, P. E.; Endriss, U.; Lang, J.; Lemaˆıtre, M.; Maudet, N.; Padget, J.; Phelps, S.; Rodr ıguez-Aguilar, J. A.; and Sousa, P. 2006. Issues in multiagent resource allocation. Informatica 30:3 31. Chevaleyre, Y.; Endriss, U.; Estivie, S.; and Maudet, N. 2007. Reaching envy-free states in distributed negotiation settings. In Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 1239 1244. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2007. Allocating goods on a graph to eliminate envy. In Proceedings of the 22nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 700 705. Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2010. Simple negotiation schemes for agents with simple preferences: Sufﬁciency, necessity and maximality. Autonomous Agents and Multi-Agent Systems 20(2):234 259. Cohler, Y. J.; Lai, J. K.; Parkes, D. C.; and Procaccia, A. D. 2011. Optimal envy-free cake cutting. In Proceedings of the 25th AAAI Conference on Artiﬁcial Intelligence (AAAI), 626 631. Kalinowski, T.; Narodytska, N.; Walsh, T.; and Xia, L. 2013. Strategic behavior when allocating indivisible goods sequentially. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI), 452 458. Kellerer, H.; Pferschy, U.; and Pisinger, D. 2004. Knapsack Problems. Springer. Kurokawa, D.; Lai, J. K.; and Procaccia, A. D. 2013. How to cut a cake before the party ends. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI), 555 561. Kushilevitz, E., and Nisan, N. 1996. Communication Complexity. Cambridge University Press. Moulin, H. 2003. Fair Division and Collective Welfare. MIT Press. 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. Steinhaus, H. 1948. The problem of fair division. Econometrica 16:101 104.