Maximin-Aware Allocations of Indivisible Goods

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, Spliddit 1 , the University of Pennsylvania's Course Match 2 , and Fair Outcomes, Inc 3 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 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.

∗The authors are ordered alphabetically.

1 http://www.spliddit.org/

2 https://mba-inside.wharton.upenn.edu/course-match/

3 https://www.fairoutcomes.com/

When indivisible goods are to be allocated among unaware agents, what is the appropriate envy-free notion and how efficiently 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 defined for unaware agents. In PROP, it is required that the value of every agent's bundle is at least a 1n 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 significant 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 sufficiently 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 satisfied 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 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 approximated 4 .

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 find (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 finding 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 12 -approximate EFX when all agents have subadditive valuations, and thus answer this problem affirmatively.

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

4 Consider 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 definitions 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 12 -approximate MMAX allocation for additive valuations; and 12 -approximate EFX allocation for subadditive valuations.

2 Preliminaries and Definitions

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) = ∑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., ⋃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̸=iAj 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 definitions.

Definition 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.

Definition 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}).

Definition 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

Definition 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 = ( ¯ Aij )j∈N such that ¯ Aii = Ai and vi(Ai) ≥ vi( ¯ Aij ) for any j ∈ N. For the purpose of presenting our results, we provide the definition of proportionality (PROP) fairness. An allocation A is PROP if for any i ∈ N, vi(Ai) ≥ 1n · vi(M).

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.

Definition 3.1 (MMA) For any α ∈ [0, 1], an allocation A is α-MMA if for any agent i ∈ N, vi(Ai) ≥ α·MMSi(A-i, n1). 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 definition 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 satisfies the condition of MMA.

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

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

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 definition 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 allocationA and any agent i. It follows that vi(Ai) ≥ 1n · vi(M). Since the valuations are additive,

Note that the other direction is not true: in Example 3.1, agent 1 is satisfied 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 satisfied 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.

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

The allocation is MMA1 when α = 1.

4.1 Connection to EF1 andMMS

We first 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 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 ⌈ n2 ⌉. 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) ≥ ⌈ n2 ⌉.

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 anMMS allocation. It follows that vi(Ai) ≥ MMSi(M, n) for every agent i. Fix any agent i ∈ N, it suffices 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

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 definition 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.

Proof: Since binary additive functions are submodular, it suffices to prove the "⇒" direction. Fix any MMA1 allocation A = (Ai)i∈N, we prove that vi(Ai) ≥ ki for every agent i, where ki = MMSi(M, n) = ⌊ vi(M) n ⌋.

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

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

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 define 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 first 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

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.

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).
5. 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.
6. 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

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

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

We first 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 ⌈ n2 ⌉. It is not difficult 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

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

In both case, agent i is satisfied w.r.t. MMAX. □

However, when agents have general additive valuations, EFX does not imply MMAX. More specifically, 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 Efficiently

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 12 -MMA or MMAX. Moreover, the allocation our algorithm outputs is 12 -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 define a procedure P, which is useful in our main algorithm. Given an allocation A, we define 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

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 matchingMbetween 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) 12 -EFX and EF1 when all agents have subadditive valuations; (2) either 12 -MMA or exact MMAX for each agent when the valuations are additive.

Proof: We first show that Algorithm 2 is well defined. 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 definition we have N1 ∪ N2 ∪ N3 = N \ {i}.

We first show that the final allocation A is 12 -EFX and EF1 when the valuations are subadditive. Note that it suffices 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 satisfied w.r.t. EF1. On the other hand, we also have vi(Ai) ≥ vi(ej), since otherwise in the first 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

which implies that agent i is satisfiedw.r.t. 1 2 -EF, and 12 -EFX. Finally, we show that when the valuations are additive, agent i is also satisfied 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

which implies that agent i is also satisfied 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 satisfied w.r.t. 12 -MMA.

We first prove that MMSi(A-i, n - 1) is at most the average value of bundles allocated to agents in N1 ∪ N3:

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

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

which implies that agent i is satisfied w.r.t. 12 -MMA. □

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 efficient 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.