# maximinaware_allocations_of_indivisible_goods__779363da.pdf

Maximin-Aware Allocations of Indivisible Goods

Hau Chan 1 , Jing Chen2 , Bo Li2 and Xiaowei Wu3

1Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA 2Department of Computer Science, Stony Brook University, USA 3Faculty of Computer Science, University of Vienna, Austria hchan3@unl.edu, {jingchen, boli2}@cs.stonybrook.edu, xiaowei.wu@univie.ac.at

We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations, and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisﬁes MMA or its relaxations. Interestingly, the returned allocation is also 1

2-approximate EFX when all agents have subadditive valuations, which improves the algorithm in [Plaut and Roughgarden, 2018].

1 Introduction

In the last few years or so, there has been a tremendous demand for fair division services to provide systematic and fair ways of dividing a set of (indivisible) goods such as rooms, courses, and properties among a group of agents so that the agents do not envy each other. Such demand gave rise to, for examples, Spliddit1, the University of Pennsylvania s Course Match2, and Fair Outcomes, Inc3 which are all based on mathematical and fairness notions. To capture the fairness of an allocation, which is arguably initiated by the work of [Foley, 1967], envy-freeness (EF) (and its relaxations, such as EF1 and EFX) is often used to ensure that each agent should not envy or prefer the allocated goods of other agents. In this paper, we study an envy-free allocation domain where the planner of the division tasks wishes to withhold allocation information of others from the user or the user simply does not know the allocation of others in the system. There are a couple of good reasons why it is desirable for the planner to withhold such information. First, in many private

The authors are ordered alphabetically. 1http://www.spliddit.org/ 2https://mba-inside.wharton.upenn.edu/course-match/ 3https://www.fairoutcomes.com/

fair allocations of goods such as tasks or gifts, the planner requires the system to preserve anonymity as not to give away the received bundles of other agents. Second, due to the large number of (unrelated) agents and items that could be potentially be involved in the division tasks (e.g., on the Internet such as MTurks), it is not meaningful for the planner to provide such information due to various reasons. Motivated by this domain, we focus on answering the following questions. When indivisible goods are to be allocated among unaware agents, what is the appropriate envy-free notion and how efﬁciently can the allocation be found subject to the notion? Proportionality (PROP) and maximin share (MMS) [Budish, 2011] are two widely studied and well accepted fair allocation notions, both of which are deﬁned for unaware agents. In PROP, it is required that the value of every agent s bundle is at least a 1

n fraction of her value for the whole goods, where n is the number of agents. It is well known that there may not exist an allocation that has guaranteed approximation of proportionality, thus a weaker and more realistic notion is desired for indivisible goods. MMS is a proper relaxation of PROP, which studies an adversarial situation: when the goods are partitioned into bundles and an agent would always get the least preferred bundle of goods, what is the best way she can partition the goods? The value of such a bundle is the MMS value of the agent. In addition to its non-existence result, MMS allocation only guarantees each agent s best minimum value, and the value of some agent s bundle can still be the least compared with others, which may cause signiﬁcant envy (demonstrated by the below example).

Example 1.1 Suppose there are 2 agents and 2 goods, v1({1}) = H, v1({2}) = 1 and v2({1}) = 1, v2({2}) = H, where H is a sufﬁciently large number and v1 and v2 are valuation functions. Then each agent s MMS value is 1 and A1 = {2}, A2 = {1} is an MMS allocation, but each agent envies each other. However, if we exchange their allocations, everyone s value can be improved to H.

Recently, [Aziz et al., 2018] introduced epistemic envyfree (EEF) notion to study unaware setting. With respect to EEF, each agent is satisﬁed if there exists one reallocation of the goods that she does not get among the other agents, such that her value for her bundle is at least as good as every bundle in this reallocation. This measure is not robust if the reallocations are restricted by agent s reasoning (e.g., adversarial

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

settings in MMS). Moreover, it can be shown that EEF and PROP allocations (and their relaxations, e.g., removing any item) barely exist and cannot be properly approximated4. Due to space limit, some proofs, examples and discussions are provided in the full version of this paper [Chan et al., 2019].

Our Contributions In this paper, we focus on modeling the envy-freeness for indivisible goods allocation as well as deriving new algorithms to ﬁnd (approximately) fair allocations subject to different fairness notions in an unaware environment. Our main contributions include the following. First, we introduce a novel fairness notion of maximin aware (MMA), which guarantees that the agent s bundle value is at least as much as her value for some other agent s bundle, no matter how the remaining goods are distributed, i.e., there is always somebody who gets no more than her. We provide a detailed picture of the relationship between MMA and classic fairness notions for different valuations. Then we show that MMA is a strong requirement and cannot be guaranteed in general, and provide two relaxations of MMA: MMA1 and MMAX. We also prove that MMA1 (and MMAX) potentially has stronger egalitarian guarantee than EF1 and such an allocation is guaranteed to exist for the following situations: (1) there are at most three agents with submodular valuations and (2) there are any number of agents but all of them have identical submodular valuation. If the above requirement of submodularity is replaced by strictly increasing subadditivity, an MMAX allocation is guaranteed to exist. In contrast, MMS allocation may not exist even for three agents with additive valuations [Kurokawa et al., 2018] and an EFX allocation is only known to exist when there are two agents [Plaut and Roughgarden, 2018]. We present a polynomial-time algorithm that computes an allocation such that every agent is either 1

2-approximate MMA or exactly MMAX for additive valuations. It is shown in [Plaut and Roughgarden, 2018] that a 1

2-approximate EFX allocation exists for general subadditive valuations, but ﬁnding it may need exponential time, which leaves an open question whether such an allocation can be found in polynomial time. We show that the allocation by our algorithm computes is also 1

2-approximate EFX when all agents have subadditive valuations, and thus answer this problem afﬁrmatively.

Other Related Works For indivisible goods allocations, EF or PROP allocations may not exist. [Budish, 2011] introduced the relaxed concept of envy-freeness up to one good (EF1). In an EF1 allocation, it is only required that each agent s value for a bundle is at least as much as her value for every other agent s bundle minus a single good (in the bundle). It is shown in [Lipton et al., 2004] that an EF1 allocation always exists, and can be found in polynomial time (with a different name). [Caragiannis et al., 2016] introduced the envy-free up to any good

4Consider three agents with two goods such that every agent has value 1 for each good. Then the agent that receives no good has no bounded guarantee for both PROP and EEF (and their relaxations by removing any item from the items she has not obtained).

(EFX) notion, where the comparison is made to any single good instead of a single good. The state-of-the-art results show that an EFX allocation exists in the following settings: (1) there are 2 agents, or (2) any number of agents but all have identical valuation [Plaut and Roughgarden, 2018]. It is still an open question whether an EFX allocation exists in general, even for additive valuations. Very recently, we see many new fairness notions, such as Nash social welfare [Caragiannis et al., 2016], epistemic envy-freeness [Aziz et al., 2018], pairwise maximin share [Caragiannis et al., 2016], and groupwise maximin share [Barman et al., 2018], which are adapted for different settings. There is also a line of works making connections (or constraints) of fair allocations to graphs or networks [Abebe et al., 2017; Bei et al., 2017; Aziz et al., 2018]. More works studying the fair allocation problem under different constraints can be found in [Ferraioli et al., 2014; Bouveret et al., 2017; Biswas and Barman, 2018].

Organization We provide necessary deﬁnitions in Section 2. We introduce MMA and show its connections with classic fairness notions in Sections 3. In Sections 4 and 5, we study the two relaxations of MMA, MMA1 and MMAX. and discuss their connections with other fairness notions and their existences in different settings. Finally, in Section 6, we present a polynomial time algorithm to compute a 1

2-approximate MMAX allocation for additive valuations; and 1

2-approximate EFX allocation for subadditive valuations.

2 Preliminaries and Deﬁnitions In the envy-free division problem on indivisible goods, there is a set N = {1, ..., n} of n agents and a set M = {1, ..., m} of m indivisible goods. Each agent i N has a valuation function vi : 2N R 0 that maps every subset of goods to a non-negative real number. We assume that vi is normalized (i.e., vi( ) = 0) and montone (i.e., vi(S) vi(T) for every S T M) for each agent i N. For convenience we use v(j) to denote v({j}), for every valuation v and every good j M. Throughout the whole paper, we call a valuation v additive if v(S) = P j S v(j) for each S M; binary additive (BA) if v is additive, and v(j) {0, 1} for any good j; subadditive (SA) if v(S T) v(S)+v(T) for any S, T M; submodular (SM) if for any S T and e M \ T, v(S {e}) v(S) v(T {e}) v(T). An allocation A = (A1, ..., An) is a partition of M among agents in N, i.e., S i N Ai = M and Ai Aj = for any i = j. In other words, Ai is the set of goods allocated to agent i. Let A i = j =i Aj be the goods not assigned to agent i. For ease of analysis, we assume that for every j M, there exists i N such that vi(j) > 0. Below we state some standard fairness deﬁnitions.

Deﬁnition 2.1 (EF) For any α [0, 1], an allocation A is α-envy-free (α-EF) if for any i, j N, vi(Ai) α vi(Aj). The allocation is EF when α = 1.

Deﬁnition 2.2 (EF1) An allocation A is envy-free up to one good (EF1) if for any i, j N, there exists e Aj such that vi(Ai) vi(Aj\{e}).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Deﬁnition 2.3 (EFX) For any α [0, 1], an allocation A is α-envy-free up to any good (α-EFX) if for any i, j N, vi(Ai) α vi(Aj\{e}) for any e Aj. The allocation is EFX when α = 1.

Next, we introduce another fairness notion called maximin share (MMS). Let Πk(S) be the set of all k-partitions of a set S. The maximin share of agent i on S among k players is

MMSi(S, k) = max π Πk(S) min S π vi(S).

Deﬁnition 2.4 (MMS) For any α [0, 1], an allocation A is α-MMS if for any i N, vi(Ai) α MMSi(M, n). The allocation is MMS when α = 1.

The most relevant fairness notion to this work is the epistemic envy-freeness (EEF) proposed in [Aziz et al., 2018]. An allocation A is EEF if for any i, there exists an allocation Ai = ( Ai j)j N such that Ai i = Ai and vi(Ai) vi( Ai j) for any j N. For the purpose of presenting our results, we provide the deﬁnition of proportionality (PROP) fairness. An allocation A is PROP if for any i N, vi(Ai) 1

Finally, we say that X type == Y if every X allocation is also a Y allocation when agents have type valuations, where X and Y are the fairness notions (e.g., MMA1 and MMS) and type is the function type (e.g. SA and SM).

3 Maximin-Aware Allocation In this section, we introduce the fairness notion of maximinaware (MMA), and study its connection to other existing fairness notions.

Deﬁnition 3.1 (MMA) For any α [0, 1], an allocation A is α-MMA if for any agent i N, vi(Ai) α MMSi(A i, n 1). The allocation is MMA when α = 1.

There is a modeling and conceptual advantage of MMA: an MMA allocation guarantees for every agent, no matter how the goods that she does not get are distributed among the other agents, there is always an agent who gets no more than her. Compared to EEF, where the happiness of each each agent depends on the existence of a reallocation of the other goods, MMA provides a robust way for the agents to reason about their reallocations of the remaining goods. Observe that an MMS allocation need not be MMA. Recall, Example 1.1 where A1 = {2} and A2 = {1} is an MMS allocation. However, this allocation is far from being MMA since v1(A1) v1(A2) and v2(A2) v2(A1). The only MMA allocation in this example is A1 = {1} and A2 = {2}. Seemingly MMA being a stronger deﬁnition than MMS, Example 3.1 shows that this is not true.

Example 3.1 Suppose there are four agents (N = {1, 2, 3, 4}) and eight goods (M = {1, 2, , 8}). Agent 1 has the additive valuation shown in Table 1.5 It is easy to check that MMS1(M, 4) = 0.5. Let S = {5, 6, 7, 8}. Then v1(S) = 0.4 < MMS1(M, 4). That is, for agent 1, S does not satisfy the condition of MMS . However, MMS1(M \ S, 3) = 0.4 = v1(S), which satisﬁes the condition of MMA.

5It is easy to design other agents valuations such that S is allocated to agent 1.

Goods 1 2, 3, 4 5, 6, 7, 8 Value 1 0.4 0.1

Table 1: MMA does not imply MMS in general.

However, when all agents have binary additive valuations, MMA actually implies MMS.

Lemma 3.1 MMA BA == MMS.

Proof: Fix any agent i N, let mi = vi(M) be the number of goods agent i is interested in. Then MMSi(M, n) = ki = mi

n . Fix any MMA allocation A, we show that it is also MMS. Suppose otherwise, i.e., vi(Ai) < ki. Then we have

MMSi(A i, n 1) = mi vi(Ai)

which contradicts the fact that A is MMA. Hence A is also an MMS allocation.

Indeed, similar to MMS, MMA is a more realistic and appropriate deﬁnition for indivisible goods allocation, in the sense that MMA is more approachable than EF and PROP for additive valuations. In the following, we show that PROP A = MMA. Combining with Theorem 4 of [Aziz et al., 2018], it implies EF A = EEF A = PROP A = MMA.

Lemma 3.2 EF A = EEF A = PROP A = MMA

Proof: Fix any PROP allocation A and any agent i. It follows that vi(Ai) 1

n vi(M). Since the valuations are additive,

MMSi(M \ Ai, n 1) 1 n 1 (1 1

n) vi(M) = vi(M)

Hence, the allocation is also MMA.

Note that the other direction is not true: in Example 3.1, agent 1 is satisﬁed with S = {5, 6, 7, 8} w.r.t. MMA, but the portion is only 0.4

2.6 < 0.25. On the other hand, MMA is a strong requirement for indivisible goods allocation, in the sense that it cannot be satisﬁed even in some simple settings. The proof of Lemma 3.3 is included in the full version.

Lemma 3.3 MMA allocations may not exist even when the agents have identical binary additive valuation.

4 Maximin-Aware up to One Good

In this section, we relax the MMA notion to maximin-aware up to one good (MMA1) that is analogous to EF1.

Deﬁnition 4.1 (MMA1) For any α [0, 1], an allocation A is α-MMA1 if for any i, there exists e A i such that

vi(Ai) α MMSi(A i\{e}, n 1).

The allocation is MMA1 when α = 1.

4.1 Connection to EF1 and MMS We ﬁrst note that while MMA1 is a relaxed version of MMA, it may have better egalitarian guarantee than EF1 allocations. An MMA1 allocation A guarantees that for each agent i and her favorite item e A i (assume e Ak, k = i), vi(Ai) is

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

at least as large as the worst bundle in any (n 1)-partition of A i \{e}. However, EF1 implies that there exists an (n 1)- partition of A i \ {e}, (i.e., Ai for i = k and Ak \ {e}) such that vi(Ai) is at least as large as the worst bundle, i.e. Ak \ {e}. We illustrate this as the following example.

Example 4.1 Consider n+1 agents and 2n+1 goods, where every agent has identical additive valuation v with v({j}) = n for 1 j n and v({j}) = 1 for n + 1 j 2n + 1. Thus allocation Ai = {i, n + i} for 1 i n and An+1 = {2n + 1} is EF1. In such an allocation, agent n + 1 only gets value 1. However, there is an allocation (for example: Ai = {i} for 1 i n and An+1 = {n + 1, , 2n + 1}) where everyone obtains value at least n.6

In Example 4.1, an EF1 allocation can be arbitrarily bad to agent n + 1. However, we show that any MMA1 allocation A in this example guarantees that each agent s value is at least n

2 . If everyone s value is at least n, then our claim trivially holds. Suppose for some agent i, v(Ai) = k < n. Then among all goods in A i, there are n goods with value n and n + 1 k goods with value 1. Thus by removing the most favorite good, the maximin share for the remaining set is min{n, n + 1 k}. Since A is an MMA1 allocation, v(Ai) = k n + 1 k, which means v(Ai) n

2 . In the following, we show that MMS implies MMA1 when the agents s valuations are submodular.

Lemma 4.1 MMS SM == MMA1.

Proof: Let A be an MMS allocation. It follows that vi(Ai) MMSi(M, n) for every agent i. Fix any agent i N, it sufﬁces to show that there exists e A i such that vi(Ai) MMS(A i \ {e}, n 1). If for every e A 1, vi(Ai {e}) = vi(Ai), then by the submodularity of v, we have

vi(M) vi(Ai)+P e A i(vi(Ai {e}) vi(Ai)) = vi(Ai),

where the inequality holds since the marginal contribution of each good does not increase. Thus A is also an MMA1 allocation for agent i. Otherwise, let e A i be such that vi(Ai {e}) > vi(Ai). For the sack of contradiction, suppose there exists a partition B = (Bj)j N\{i} of A i \ {e} such that vi(Bj) > vi(Ai) for all j N \ {i}. Then if we include e into Ai, the resulting partition of M (into n parts) has minimum value strictly larger than MMSi(M, n) on every agent, which contradicts the deﬁnition of MMSi(M, n).

By a similar argument, we can show that every α-MMS allocation is also α-MMA1. Recall Example 3.1 where we show an MMA allocation is not necessarily MMS (thus neither an MMA1 allocation), this implication is strict. Next, we show that for binary additive valuations, MMA1 and MMS are actually equivalent.

Lemma 4.2 MMA1 BA MMS.

Proof: Since binary additive functions are submodular, it sufﬁces to prove the direction. Fix any MMA1 allocation

6We note that there is no exact EF allocation for this example.

A = (Ai)i N, we prove that vi(Ai) ki for every agent i, where ki = MMSi(M, n) = vi(M)

n . Fix any agent i and assume the contrary that vi(Ai) < ki. Let mi = vi(M). Then for any e A i we have

MMSi(A i \ {e}, n 1) = mi 1 vi(Ai)

n 1 ki > vi(Ai),

which contradicts the fact that A is MMA1.

It is shown in [Kurokawa et al., 2018] that even for three agents with additive valuations, MMS allocations do not always exist. As we will show later, for a broader class of situations, an MMA1 allocation is guaranteed to exist.

4.2 The Existence of MMA1 Allocations By Lemma 4.2, we know that an MMA1 allocation always exists when the valuations are binary additive. In this section, we explore the existence of MMA1 allocations for instances with subadditive valuations. First, for any valuation v over a set M of goods, we deﬁne the leximin n-partition as follows. A leximin n-partition is a partition which divides M into n subsets and maximizes the lexicographical order when the values of the partitions are sorted in non-decreasing order. In other words, a leximin npartition maximizes the minimum value over all n-partitions, and if there is a tie it selects the one maximizing the second minimum value, and so on. In the following, we show that MMA1 allocations exist when all agents have identical submodular valuation, or when there are three agents with (different) submodular valuations. We ﬁrst show that when all agents have identical submodular valuation, the leximin n-partition of M is indeed an MMA1 allocation.

Theorem 4.1 When all agents have the identical submodular valuation, the leximin n-partition of M is MMA1.

Proof: Let v be the submodular valuation and A be the leximin n-partition of M. We show that allocating each partition Ai to agent i gives an MMA1 allocation. As before, if for all e A i, v(Ai {e}) = v(Ai), then we have

v(Ai) = v(M) MMS(A i, n 1)

by submodularity of v. Otherwise let e A i be any good such that v(Ai {e}) > v(Ai). Assume the contrary that v(Ai) < MMS(A i\{e}, n 1). Let B = (Bj)j N\{i} be the partition of A i \ {e} such that v(Ai) < v(Bj) for all j = i. Then by including e into Ai, we obtain a partition of M such that every bundle has value strictly larger than v(Ai). In other words, the resulting partition is strictly better than the leximin n-partition, which is a contradiction.

Next we show a divide-and-choose style algorithm (shown in Algorithm 1) which gives an MMA1 allocation for three agents. For space limit, the proof of Theorem 4.2 is deferred to the full version.

Theorem 4.2 When n = 3 and the valuations are submodular, Algorithm 1 computes an MMA1 allocation.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Algorithm 1 Divide-and-choose algorithm for three agents

1. Agent 3 divides M as a leximin partition to her, which is denoted by A = (A1, A2, A3). 2. If agent 1 s and agent 2 s favorite bundles are different, each of them takes her favorite bundle and the remaining bundle is allocated to agent 3. 3. Otherwise (agent 1 and agent 2 have the same favorite bundle), we compare their second favorite bundle. If their second favorite bundles are also the same, agent 2 takes her favorite two bundles (w.o.l.g, say A1 and A2), and leaves A3 to agent 3. Next, agent 2 repartitions A1 A2 by her leximin 2-partitions, denoted by B1 and B2. Agent 1 chooses her favorite one in B1 and B2, and the other one is allocated to agent 2. 4. Finally, suppose their second favorite bundles are different. W.o.l.g, suppose v1(A1) v1(A2) v1(A3) and v2(A1) v2(A3) v2(A2). (1) If 2 v1(A2) > v1(A1) + v1(A3) and 2 v2(A3) > v2(A1) + v2(A2), allocate A2 to agent 1, A3 to agent 2 and A1 to agent 3. (2) Otherwise (assume w.l.o.g. that 2 v1(A2) v1(A1) + v1(A3)). Agent 2 takes A1 and A3, which are her favorite two bundles, and leave A2 to agent 3. Next, agent 2 repartitions A1 A3 by her leximin 2-partition C = (C1, C2), and let Agent 1 choose her favorite one in C1 and C2. The other one is allocated to agent 2.

5 Maximin-Aware up to Any Good

Deﬁnition 5.1 (MMAX) For any α [0, 1], an allocation A is α-MMAX if for any i,

vi(Ai) α MMSi(A i \ {e}, n 1)

for any e A i. The allocation is MMAX when α = 1.

We ﬁrst note that MMAX allocations give an even better egalitarian guarantee than MMA1 and EF1 allocations. Recall Example 4.1, where we show there is an EF1 allocation such that some agent only gets value 1 and any MMA1 allocation guarantees each agent s value is at least n

2 . It is not difﬁcult to show that any MMAX allocation guarantees each agent s value is at least n. Obviously, an MMAX allocation is also MMA1. Together with Lemma 4.2, we have MMAX BA == MMA1 BA MMS. However, beyond BA valuations, the above implication does not hold. We can see this by borrowing an example from [Kurokawa et al., 2018], for which there is no MMS allocation, but MMAX (and MMA1) allocations do exist. For space limit we defer the example and analysis to the full version. Next we show the connection between MMAX and EFX when the valuations are binary additive.

Lemma 5.1 EFX BA == MMAX.

Proof: Let A be any EFX allocation. Consider any agent i N and let x = vi(Ai) be the value of i s bundle under the allocation A. Since A is EFX, then for any j N \ {i},

one of the following statements holds: (1) vi(Aj) = x + 1 and |Aj| = x + 1 (i.e., agent i has value 1 for every good in Aj); (2) vi(Aj) x (i.e., Aj may contain more than x + 1 goods, but agent i has value 1 for exact x goods). This is because if both of them do not hold, then vi(Aj) x+1 and |Aj| > x+1, which means agent i has value 0 for at least one good in Aj. Thus agent i still envies agent j after removing the good with value 0 from Aj. Note that as long as there exists an agent j = i such that vi(Aj) x, then vi(A i) (x + 1)(n 1) 1. Hence

MMSi(A i, n 1) x = vi(Ai).

Otherwise we have vi(A i) = |A i| = (x+1)(n 1). Then by removing any good e A i, we have

MMSi(A i \ {e}, n 1) x = vi(Ai).

In both case, agent i is satisﬁed w.r.t. MMAX.

However, when agents have general additive valuations, EFX does not imply MMAX. More speciﬁcally, there are examples (we will include one in our full version), for which EFX allocations exist but are not MMAX. The existence of MMAX allocations. First, note that for two agents, MMAX is equivalent to EFX and thus exists for general subadditive valuations [Plaut and Roughgarden, 2018]. Indeed, following exactly the same analysis as in Theorems 4.1 and 4.2, we obtain the following result.

Theorem 5.1 When there are at most three agents having strictly increasing subadditive valuations, or any number of agents having identical strictly increasing subadditive valuations, an MMAX allocation exists.

6 Computing Allocations Efﬁciently In this section, we provide a polynomial-time algorithm (see Algorithm 2) for computing an allocation such that when all agents have additive valuations every agent is either 1

2-MMA or MMAX. Moreover, the allocation our algorithm outputs is 1 2-EFX when all agents have subadditive valuations. In each round (the while loop) of Algorithm 2, we assign at most one good to each agent that is not envied by any other agent. The assignment of goods to agents in each round is given by a maximum weight matching between the unenvied agents L and the unallocated goods R, where the weight of every edge is given by the marginal increase in the value, after allocating the good to the corresponding agent. If all edges between L and R have weight 0, we assign goods to unenvied agents according to some maximum cardinality matching. To make sure that there is always an unenvied agent, we use the approach (procedure P in the following) introduced in [Lipton et al., 2004], which is now widely used in the resource allocation literature. Next, we deﬁne a procedure P, which is useful in our main algorithm. Given an allocation A, we deﬁne its corresponding envy-graph G as follows. Every agent is represented by a node in G and there is a directed edge from node i to node j iff vi(Ai) < vi(Aj), i.e., i is envies j. A directed cycle in G is called an envy-cycle. Let C = i1 i2 it i1 be such a cycle. If we reallocate Aik+1 to agent ik for all

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Algorithm 2 Algorithm for (sub-)additive valuations

1: Initiate L = N and R = M. 2: Initiate Ai = for all i N. 3: while R = do 4: Compute a maximum weight matching M between L and R, where the weight of edge between i L and j R is given by vi(Ai {j}) vi(Ai). If all edges have weight 0, then we compute a maximum cardinality matching M instead. 5: For every edge (i, j) M, allocate j to i: Ai = Ai {j} and exclude j from R: R = R \ {j}. 6: As long as there is an envy-cycle w.r.t. A = (Ai)i N, invoke procedure P (to be described later). 7: Update A = (Ai)i N to be the allocations after P. 8: Update the set of agents not envied by any other agents: L = {i N : j N, vj(Aj) vj(Ai)}. 9: end while

k [t 1], and reallocate Ai1 to agent it, the number of edges of G will be strictly decreased. Thus, by repeatedly using this procedure, we eventually get another allocation whose envygraph is acyclic. It is shown in [Lipton et al., 2004] that P can be done in time O(mn3). Next, we prove the following main result of this section.

Theorem 6.1 Algorithm 2 computes an allocation in polynomial time that is (1) 1

2-EFX and EF1 when all agents have subadditive valuations; (2) either 1

2-MMA or exact MMAX for each agent when the valuations are additive.

Proof: We ﬁrst show that Algorithm 2 is well deﬁned. In each round, there must be at least one agent who is not envied by anybody, since after Step 6, the envy-graph is acyclic. Thus there will be at least one agent whose in-degree is 0, i.e., L = . Moreover, since at least one good will be allocated in each round (each while loop), Algorithm 2 terminates in at most m rounds. Given that each round (including procedure P, the computation of maximum weight matching, and the updates of edge weights and unenvied agents L) can be done in polynomial time, Algorithm 2 runs in polynomial time. Fix any agent i. We classify other agents into three sets: agents not envied by i: N1 = {j N \ {i} : vi(Ai) vi(Aj)}; agents envied by i that receive only one good: N2 = {j N \ {i} : vi(Ai) < vi(Aj) and |Aj| = 1}; agents envied by i that receive more than one good: N3 = {j N \ {i} : vi(Ai) < vi(Aj) and |Aj| 2}. By deﬁnition we have N1 N2 N3 = N \ {i}. We ﬁrst show that the ﬁnal allocation A is 1

2-EFX and EF1 when the valuations are subadditive. Note that it sufﬁces to consider N3, as the other agents are either not envied by i, or allocated only one good. Fix any agent j N3. Let ej be the last good allocated to j. As we only allocate goods to unenvied agents, we have vi(Ai) vi(Aj \{ej}), which implies that agent i is satisﬁed w.r.t. EF1. On the other hand, we also have vi(Ai) vi(ej), since otherwise in the ﬁrst round, matching ej (which is not allocated yet) with i (which is not envied) gives a matching with strictly larger weight. Combing the two inequalities and

by subadditivity of valuation vi, we have

2 vi(Ai) vi(Aj \ {ej}) + vi(ej) vi(Aj),

which implies that agent i is satisﬁed w.r.t. 1

2-EF, and 1

2-EFX. Finally, we show that when the valuations are additive, agent i is also satisﬁed w.r.t. 1

2-MMA or MMAX. The case when N2 = N \ {i}, i.e., all other agents receive one good and is envied by agent i, is trivial: by removing any good e from A i, there is always some agent with no good. Thus we have

MMSi(A i \ {e}, n 1) = 0 vi(Ai),

which implies that agent i is also satisﬁed w.r.t. MMAX. Now suppose that N2 = N \ {i}. In other words, we have N1 N3 = , and n 1 |N2| 1. We prove that in this case we have MMSi(A i, n 1) 2 vi(Ai), which implies that agent i is satisﬁed w.r.t. 1

2-MMA. We ﬁrst prove that MMSi(A i, n 1) is at most the average value of bundles allocated to agents in N1 N3:

MMSi(A i, n 1)

P j N1 vi(Aj) + P j N3 vi(Aj)

Let τ = MMSi(A i, n 1). Observe that if we have vi(e) τ for every e A i, then X

j N1 vi(Aj) + X

j N3 vi(Aj) = vi(M) X

j N2 vi(Aj)

vi(M) |N2| τ (n 1 |N2|) MMSi(A i, n 1).

Indeed, the assumption is w.l.o.g., since otherwise we can reset every vi(e) to min{τ, vi(e)}, which does not change MMSi(A i, n 1). The reason is, in any partitioning of A i into n 1 bundles, the bundle with minimum value (whose value is at most τ = MMSi(A i, n 1)) is not touched. As we have shown before (for subadditive valuations), for every j N3, we have vi(Aj) 2 vi(Ai). Since we have vi(Aj) vi(Ai) for all j N1, we conclude that

MMSi(A i, n 1) 2 vi(Ai),

which implies that agent i is satisﬁed w.r.t. 1

7 Conclusion In this paper, we introduce the novel fairness notions MMA and its two relaxations MMA1 and MMAX in an unaware environment. We study their connections with other fairness notations, and propose an efﬁcient algorithm for computing allocations that is (approximately) MMA and MMAX. We leave the existence of MMA1 and MMAX allocations for the broader class of valuations as a future direction. Another promising direction would be to extend our work to other preference representations, including ordinal preferences, or to chores instead of goods. Finally, it will be interesting to obtain analogue concepts for asymmetric agents, where agents may have different entitlements or shares.

Acknowledgments The authors thank Haris Aziz and David Parkes for reading a draft of this paper and for helpful discussions. This work is partially supported by NSF CAREER Award No. 1553385.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Abebe et al., 2017] Rediet Abebe, Jon Kleinberg, and David C Parkes. Fair division via social comparison. In Proceedings of the 16th Conference on Autonomous Agents and Multi Agent Systems, pages 281 289. International Foundation for Autonomous Agents and Multiagent Systems, 2017. [Aziz et al., 2018] Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and J erˆome Lang. Knowledge, fairness, and social constraints. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence, 2018. [Barman et al., 2018] Siddharth Barman, Arpita Biswas, Sanath Kumar Krishnamurthy, and Yadati Narahari. Groupwise maximin fair allocation of indivisible goods. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence, 2018. [Bei et al., 2017] Xiaohui Bei, Youming Qiao, and Shengyu Zhang. Networked fairness in cake cutting. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, pages 3632 3638. AAAI Press, 2017. [Biswas and Barman, 2018] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, pages 91 97, 2018. [Bouveret et al., 2017] Sylvain Bouveret, Katar ına Cechl arov a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In 26th International Joint Conference on Artiﬁcial Intelligence, 2017. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Caragiannis et al., 2016] Ioannis Caragiannis, David Kurokawa, Herv e Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 305 322. ACM, 2016. [Chan et al., 2019] Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. Maximin-aware allocations of indivisible goods (full version). https://arxiv.org/abs/1905.09969, 2019. [Ferraioli et al., 2014] Diodato Ferraioli, Laurent Gourv es, and J erˆome Monnot. On regular and approximately fair allocations of indivisible goods. In Proceedings of the 2014 international conference on Autonomous agents and multiagent systems, pages 997 1004. International Foundation for Autonomous Agents and Multiagent Systems, 2014. [Foley, 1967] Duncan K Foley. An improved envy-free cake cutting protocol for four agents. Yale Economics Essays, pages 45 98, 1967. [Kurokawa et al., 2018] David Kurokawa, Ariel D Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM), 65(2):8, 2018.

[Lipton et al., 2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce, pages 125 131. ACM, 2004. [Plaut and Roughgarden, 2018] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. In Proceedings of the Twenty-Ninth Annual ACMSIAM Symposium on Discrete Algorithms, pages 2584 2603. SIAM, 2018.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)