# fair_and_efficient_allocations_under_subadditive_valuations__730043d5.pdf

Fair and Efﬁcient Allocations under Subadditive Valuations

Bhaskar Ray Chaudhury 1, Jugal Garg 2, Ruta Mehta 2

1 Max Planck Institute for Informatics, Saarland Informatics Campus 2 University of Illinois at Urbana-Champaign braycha@mpi-inf.mpg.de, {jugal, rutameht}@illinois.edu

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efﬁcient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely 1

2-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents valuations) is one of the most commonly used measures of efﬁciency. In case of additive valuations, an allocation that maximizes Nash welfare also satisﬁes fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisﬁes either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p ( , 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = while also retaining the remarkable fairness properties.

Introduction

Discrete fair division of resources is a fundamental problem in various multi-agent settings, where the goal is to partition a set M of m indivisible goods among n agents in a fair and efﬁcient manner. Each agent i has a valuation function vi : 2M R 0 that quantiﬁes the amount of utility i derives from every subset of goods. We assume that vi s are monotone, i.e., vi(A) vi(A {g}) for all g M, normalized i.e., vi( ) = 0 and subadditive, i.e., vi(A B) vi(A)+vi(B), for all A, B M. Subadditive functions naturally arise in practice because they capture the notion of complement-freeness (Lehmann, Lehmann, and

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

Nisan 2006). Furthermore, they strictly contain submodular functions1, which capture the notion of diminishing marginal returns. Among various choices, envy-freeness is the most natural fairness concept, where no agent i envies another agent j s bundle, i.e., partition of goods into n bundles X1, X2, . . . , Xn so that for all agents i and j, we have vi(Xi) vi(Xj). However, envy-free allocation do not always exist, e.g., consider allocating a single valuable good among two agents. Its mild relaxation envy-freeness up to any good (EFX) (Caragiannis et al. 2016) is arguably the most compelling notion of fairness in discrete setting, where no agent envies other s allocation after the removal of any good, i.e., for all agents i and j, we have vi(Xi) vi(Xj \ {g}) for all g Xj. While it is not known whether an EFX allocation always exists or not beyond the simple case of two agents under subadditive valuations, the following relaxations exist:

1 2-EFX allocation X = X1, X2, . . . , Xn where vi(Xi) 1 2 vi(Xj \ {g}), for all g Xj (Plaut and Roughgarden 2018). In this paper we will be referring to a relaxed version of 1

2-EFX namely, ( 1

2 ε)-EFX allocation where vi(Xi) ( 1

2 ε) vi(Xj \{g}) for all g Xj. A ( 1

2 ε)-EFX allocation can also be computed in polynomial time when agents have subadditive valuations.

EFX allocation with bounded charity X = X1, X2, . . . , Xn where we do not allocate a set P of goods (set P is donated to charity) where |P| < n and vi(Xi) vi(P), for all i [n] and the partial allocation X is EFX (Chaudhury et al. 2020). There is also a polynomial time algorithm to ﬁnd an (1 ε)-EFX allocation with bounded charity for general valuations for any ε > 0 (Chaudhury et al. 2019)2.

Another popular (and stronger) relaxation is envyfreeness up to one good (EF1) (Budish 2011), where no agent envies other s allocation after the removal of some good from the other s bundle, i.e., vi(Xi) vi(Xj \ {g}), for some g Xj. Clearly, EFX implies EF1. Although

1A function v(.) is submodular if v(A) + v(B) v(A B) + v(A B), A, B M. 2This is an updated version of the paper which goes beyond the preliminary version published in SODA 2020

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

the existence of EFX allocations still remains a major open question, an EF1 allocation always exists for general valuations and can be obtained in polynomial time (Lipton et al. 2004). We note that none of the above algorithms provides, as such, any efﬁciency guarantees. For efﬁciency, among many choices, maximum Nash welfare, deﬁned as the geometric mean of agents valuations, serves as a focal point. In contrast to other popular welfare measures such as social welfare and max-min welfare, Nash welfare is scale invariant, i.e., scaling one agent s valuation by any positive constant does not change the outcome. In case of additive valuations3, an allocation that maximizes Nash welfare is both EF1 and Pareto optimal4 (Caragiannis et al. 2016). However, such an allocation does not provide the EF1 property beyond additive (e.g., subadditive valuations (Caragiannis et al. 2016)), and further, no meaningful guarantee in terms of EFX even in the case of additive valuations (Amanatidis et al. 2020). Furthermore, maximizing the Nash welfare is a hard problem, and the best known approximation guarantees are O(n log n) and O(m) for submodular (Garg, Kulkarni, and Kulkarni 2020) and subadditive (Nguyen and Rothe 2014) valuations, respectively. As is the case with the algorithms providing fairness guarantees, these Nash welfare approximation algorithms do not provide any fairness guarantees. Therefore, a natural question is:

Does there exist a polynomial-time algorithm that provides the best known fairness guarantees as well as the best known efﬁciency guarantees simultaneously?

In this paper, we answer this question afﬁrmatively. We design a simple algorithm that outputs an allocation that provides (i) either of the best-known EFX approximations mentioned above, (ii) EF1 guarantee, and (iii) O(n) approximation to the maximum Nash welfare. The latter also improves the best-known approximation factor. Further, we show that our algorithm can be easily adapted to obtain the same guarantees for the entire family of p-mean welfare measures Mp(X), deﬁned as,

Mp(X) = ( X

1 n(vi(Xi))p)1/p for p ( , 1].

The p = , 0, and 1 correspond to the well-studied cases of max-min welfare, Nash welfare, and social welfare, respectively. We note that this also matches the current best approximation ratio for the max-min welfare (Khot and Ponnuswami 2007) while also retaining the above mentioned fairness guarantees. One crucial difference between Nash welfare and p-mean welfare when p = 0 is that p-mean is no longer scale invariant. Therefore, it is not intuitive that the allocation that maximizes welfare will be fair when our fairness measures are

3A valuation function v(.) is additive if vi(S) = P

j S vi({j}), S. 4An allocation X = (X 1, . . . , X n) Pareto dominates another allocation X = (X1, . . . , Xn) if vi(X i) vi(Xi), i and vk(X k) > vk(Xk) for some k. An allocation X is Pareto optimal if no allocation X dominates X.

relaxations of envy-freeness.5 However, we manage to give a polynomial time algorithm that achieves a good approximation (independent of the number of goods in the instance) to the p-mean welfare while still retaining all the fairness properties.

Technical Overview In this section, we brieﬂy sketch our main result and overall approach. We ﬁrst state the main result of our paper Theorem 1. Given a discrete fair division instance with a set [n] of n agents, a set M of m indivisible goods, where each agent i has a subadditive valuation function vi : 2M R 0, for any ε > 0, we can ﬁnd in polynomial time

a partition X1, X2, . . . , Xn of M such that X is ( 1

2 ε)- EFX and Mp(X) 1 2ε 8(n+1) Mp(X ), and

a partition X1, X2, . . . , Xn, P of M such that X is (1 ε)-EFX with bounded charity and Mp(X) 1 ε 4(n+1) Mp(X ), where X is the allocation with maximum p-mean value. We now brieﬂy sketch our main techniques: Let us consider the scenario that a given instance admits an envyfree allocation, i.e., a partition of the goods into n bundles X1, X2, . . . , Xn such that for all pairs of agents i and j we have vi(Xi) vi(Xj). In that case for each agent i we have

j [n] vi(Xj)

vi( j [n]Xj) (by subadditivity)

This implies that vi(Xi) 1

n vi(M). Since in any optimal allocation no agent can get a valuation more than vi(M), we can conclude that each agent has a bundle worth 1

n times his bundle at optimum. This would immediately give us an n approximation for generalized p-mean welfare. However, most instances may not admit an envy-free allocation. Naturally, we then look into the closest relaxation of envyfreeness that is known to exist in the context of indivisible goods6. ( 1

2-EFX (Plaut and Roughgarden 2018) and EFX with bounded charity7 (Chaudhury et al. 2020)). So let us consider the 1

2-EFX allocation: Here we can partition the given instance into n bundles X1, X2, . . . , Xn such that for all pairs of agents i and j we have vi(Xi) 1

2vi(Xj \ {g}) for all g Xj. Let us ﬁrst look into all the bundles

5Consider a special case when p = . Here the p-mean welfare is equal to the valuation of the agent with smallest valuation. In particular, consider the scenario with two agents and n goods where agent 1 has a valuation of 1 for each good and agent 2 has a valuation of ε < 1 n for each good. The allocation that maximizes the p-mean welfare here will give exactly one good to agent 1 and n 1 goods to agent 2, which is very far from satisfying any relaxation of envy-freeness. 6In our algorithm we consider relaxed variants of these notions like ( 1

2 ε)-EFX and (1 ε)-EFX with bounded charity, but for clarity in this section we keep the original notions 7deﬁned in Section

Xj that are not singleton, i.e., |Xj| 2: We have that vi(Xi) 1 2 vi(Xj \ {g}) for all g Xj, implying that

2 max vi(Xj \ {g}), vi({g}) (as |Xj| 2). Thus,

2 vi(Xj \ {g}) + vi({g})

|Xj| 2 vi(Xj)

(by subadditivity)

4 vi( |Xj| 2Xj) (1)

(by subadditivity)

Let S be the set of all the goods in singleton bundles in X, i.e., S = {g | there is a Xj = {g}}. Then from (1) we have the guarantee that for every agent vi(Xi) 1 4n vi(M \ S). Therefore, in any 1

2-EFX allocation every agent has an 1 4n fraction of his valuation on the goods he receives from M \S in the optimal allocation, i.e., vi X i (M \ S) where X = (X 1, . . . , X n) is the allocation that has the highest generalized p-mean welfare. The only problem is how to allocate the goods in the set S appropriately. The only scenario where an incorrect allocation of the goods in S causes a signiﬁcant decrease in the p-mean welfare is when there are agents who have a substantially high valuation for some goods in S. However, we could very well be in a scenario where there are only a few goods in S (say less than n

3 ) which are very valuable to many agents and then we may not be able to give every agent a bundle that he values 1

n times the whole set S.8 Therefore we need to compare our allocation with the allocation that maximizes the p-mean welfare. We brieﬂy sketch how we overcome this barrier. The good aspect of the situation is that the number of goods in S is small, i.e., |S| n. Let Hi denote the set of n goods that are valued by agent i the most, i.e., all goods in Hi are more valuable than any good outside Hi. Now we ﬁnd a single good allocation (where each agent gets exactly one good) of the high valued goods, namely the set H = i [n]Hi, optimally to the agents assuming that we can give each agent at least 1

n times their valuation for the low valued goods, namely the set M \Hi. That is, we ﬁnd a single good allocation, where every agent i gets exactly one high valued good hi Hi, that maximizes P i [n] vi({hi})+ 1

nvi(M \Hi) p

(such allocations can be found efﬁciently with matching algorithms). Let us call the current single good allocation Y . Note that Y is trivially EFX as every agent has exactly one good (therefore Y is also 1

2-EFX). We then run the 1

8A very simple scenario is to divide n goods among n agents with identical additive valuations, where all agents have a valuation of 1 for a single good and ε 1 n for the rest of the goods. In any division there will be n 1 agents who do not get 1

n of their valuation on the set of n goods

algorithm starting with Y as the initial partial 1

2-EFX allocation. The intuition being that the low valued goods appear in non-singleton bundles and the high valued goods occur in singleton bundles in the ﬁnal 1

2-EFX allocation, but we have allocated the high valued goods correctly (up to a factor of 1 n as we computed a single good allocation, while the optimum need not necessarily give every agent exactly one high valued good) as we started out with an optimal allocation of the high valued goods. Since the low valued goods occur in non-singleton bundles we are indeed able to give every agent 1 n times their valuation for the low valued goods.

Related Work

Fair division has been extensively studied for more than seventy years since the seminal work of Steinhaus (Steinhaus 1948). A complete survey of all different settings and the fairness and efﬁciency notions used is well beyond the scope of this paper. We limit our attention to fair division of indivisible goods (as mentioned in Section ). There have been extensive studies on relaxations of envy-freeness like EF1 (Budish et al. 2017; Barman et al. 2018; Lipton et al. 2004; Caragiannis et al. 2016) and EFX (Chaudhury et al. 2020; Caragiannis, Gravin, and Huang 2019; Plaut and Roughgarden 2018) and relaxations of proportionality like maximin shares (MMS) (Budish 2011; Bouveret and Lemaˆıtre 2016; Amanatidis et al. 2017; Barman and Krishnamurthy 2017; Kurokawa, Procaccia, and Wang 2018; Ghodsi et al. 2018; Garg, Mc Glaughlin, and Taki 2019; Garg and Taki 2019) and proportionality up to one good (PROP1) (Conitzer, Freeman, and Shah 2017; Barman and Krishnamurthy 2019; Garg and Mc Glaughlin 2019). While there is a signiﬁcant interest in ﬁnding fair allocations, there has also been a lot of interest in guaranteeing efﬁcient fair allocations. A common measure of economic efﬁciency is Pareto-Optimality9. (Caragiannis et al. 2016) showed that when agents have additive valuations, any allocation that maximizes the Nash welfare is guaranteed to be Pareto-optimal (efﬁcient) and EF1 (fair). Hence the Nash welfare is also a good measure of efﬁciency of fair allocations. Unfortunately, ﬁnding an allocation with the maximum Nash welfare is APX-hard (Lee 2017). However, approximation algorithms for Nash welfare under different types of valuations have received signiﬁcant attention recently, e.g., (Cole and Gkatzelis 2018; Cole et al. 2017; Anari et al. 2017; Garg, Hoefer, and Mehlhorn 2018; Anari et al. 2018; Barman, Krishnamurthy, and Vaish 2018; Chaudhury et al. 2018; Garg, Kulkarni, and Kulkarni 2020; Babaioff, Ezra, and Feige 2020; Benabbou et al. 2020).

Independent Work

Independently of our work, (Barman et al. 2020) also ﬁnd an O(n)-approximation algorithm for the generalized pmean welfare when agents have subadditive valuations. On a high level, both algorithms, ﬁrst carefully allocate a single highly valuable good to each agent and then carefully allocate the remaining goods. However, the procedures used to

9Deﬁned in Section

determine the initial (the single highly valuable good allocation) and the ﬁnal allocations are signiﬁcantly different. Also, contrary to the allocation determined by the algorithm in (Barman et al. 2020), we are able to obtain guarantees on the fairness of our allocation, namely the properties of EF1 and the two relaxations of EFX. In the same paper, (Barman et al. 2020) show that it requires an exponential number of value queries to provide any sublinear approximation for the generalized p-mean welfare under subadditive valuations. Therefore, in polynomial time, our algorithm yields an allocation that satisﬁes the best relaxations of EFX known for subadditive valuations, and also achieves the best approximation for the generalized p-mean welfare possible in polynomial time.

Preliminaries

Any discrete fair division instance I is a tuple [n], M, V comprising of a set of n agents ([n]), a set of m goods (M) and a set of valuation functions V = {v1, v2, . . . , vn}. The valuation function vi : 2M R 0 tries to capture agent i s utility for each subset of goods. Throughout this paper we will be dealing with the case where all the valuation functions are

normalized: vi( ) = 0 for all i [n],

monotone: vi(A {g}) vi(A) for all i [n] and A M, and

subadditive: for any sets A, B M we have vi(A) + vi(B) vi(A B) for all i [n].

For ease of notation we use vi(g) instead of vi({g}) and vi(A \ g) instead of vi(A \ {g})

Generalized p-mean welfare: Given an allocation X the p-mean welfare of X (parametrized by p) is deﬁned by

i [n] vi(Xi)p 1

This captures a wide range of fairness and efﬁciency measures that have been used frequently in the literature: Nash welfare for p = 0, max-min welfare (also known as the egalitarian welfare) for p = and social welfare for p = 1. Barman and Sundaram (Barman and Sundaram 2020) also mention that,

generalized means with p ( , 1] exactly constitute the family of welfare functions that satisfy the Pigou-Dalton transfer principle and a few other key axioms.

In the same paper they show that when agents have identical valuations, there is an algorithm that provides an O(1) factor approximation to the p-mean welfare.

EFX Allocations and Relaxations: EFX is arguably the strongest notion of fairness in the context of indivisible goods. Formally,

Deﬁnition 2. An allocation X = X1, X2, . . . , Xn is said to be an EFX allocation if for all pairs of agents i and j, we have vi(Xi) vi(Xj \ g) for all g Xj.

Although the existence of complete EFX allocations is not known yet, there have been results pertaining to the existence of certain relaxations of EFX. We state two major relaxations here. Plaut and Roughgarden (Plaut and Roughgarden 2018) introduced the notion of approximate EFX or equivalently α-EFX:

Deﬁnition 3. An allocation X is α-EFX with α (0, 1) if and only if for all pairs of agents i and j we have vi(Xi) α vi(Xj \ g) for all g Xj.

(Plaut and Roughgarden 2018) showed that 1

2-EFX allocations exist and can be computed in pseudo-polynomial time. With a very minor change in their algorithm10 we can obtain an ( 1

2 ε)-EFX allocation in polynomial time. Another relaxation introduced by (Chaudhury et al. 2020) is EFX with bounded charity:

Deﬁnition 4. A partial allocation X is an EFX allocation with bounded charity with the set of unallocated goods P such that

X is EFX, |P| < n, and vi(Xi) vi(P) for all i [n].

The updated version of the paper (Chaudhury et al. 2019) gives a polynomial time algorithm to determine (1 ε)-EFX allocation with bounded charity.11

Throughout the paper we will outline algorithms that ﬁnd allocations with high welfare and are ﬂexible with the fairness that the allocations satisfy, i.e., we can get ( 1

2 ε)-EFX allocations with high welfare or (1 ε)-EFX allocations with bounded charity and high welfare. Therefore we now introduce some common notation for ease of referring to both these relaxations of EFX at the same time:

Deﬁnition 5. An allocation X is an (α, c)-EFX allocation with α (0, 1) and c {0, 1} if and only if

X is α-EFX and EF1, |P| < n, and vi(Xi) vi(P) for all i [n]. P = if c = 1.12

Therefore an (α, 1)-EFX allocation would refer to an αEFX (which is also EF1) allocation and a (α, 0)-EFX allocation would refer to an α-EFX allocation with bounded charity. In particular we would only be interested in (( 1

2 ε), 1)- EFX allocation and (1 ε, 0)-EFX allocation. Similarly, we also introduce the notion of an (α, c)-EFX algorithm:

10Just run the same algorithm replacing the violation condition from 1

2-EFX to ( 1

2 ε)-EFX 11Just relax the ﬁrst condition in Deﬁnition 4 to X is (1 ε)- EFX 12c serves as an indicator to whether the allocation is complete or not.

Deﬁnition 6. An (α, c)-EFX algorithm takes as input any partial α-EFX allocation X and outputs an (α, c)-EFX allocation Y as the ﬁnal allocation such that

the valuation of every agent in the ﬁnal allocation is at least as high as his valuation in the initial allocation, i.e., vi(Yi) vi(Xi), and if there exists an agent i such that |Yi| = 1 and Yi = Xi, then vi(Yi) > vi(Xi).

In particular an (α, c)-EFX algorithm outputs a ﬁnal (α, c)-EFX allocation that preserves (if not improves) all the welfare guarantees of the initial α-EFX allocation. Both the existing algorithms for determining an ( 1

2 ε, 1)-EFX allocation (a trivial modiﬁcation of the algorithm in (Plaut and Roughgarden 2018)) and (1 ε, 0)-EFX (Chaudhury et al. 2019) allocation are an ( 1

2 ε, 1)-EFX algorithm and an (1 ε, 0)-EFX algorithm respectively.

In this section, we show that we can determine an (α, c)- EFX allocation with an O(n) approximation on the p-mean welfare. The algorithm is very simple and it has just two phases: In the ﬁrst phase we try to determine a reasonable allocation of high valued goods (we call this allocation Y ) and then in the second phase we just run an (α, c)-EFX algorithm with the remaining set of goods (we call our ﬁnal allocation Z).

Allocating the high valued goods Y : We ﬁrst formally deﬁne the notion of high valued goods for an agent: For each agent i let us order the goods in M as gi 1, gi 2, . . . , gi m

such that vi(gi 1) vi(gi 2) vi(gi m). Let Hi = gi 1, gi 2, . . . , gi n . We refer to Hi to be the set of high valued goods for agent i. Also for each good gi k and an agent i we deﬁne rank i(gi k) = k. Notice that if for any agent i rank i(g) < rank i(g ), then vi(g) vi(g ). We now outline how we compute the initial allocation Y . We construct the complete bipartite graph G = ([n] M, [n] M) with the weight of the edge from agent i to good g, wig being

n vi(g) + vi(M \ Hi) if p = ,

log n vi(g) + vi(M \ Hi) if p = 0 and

n vi(g) + vi(M \ Hi) p otherwise.

Depending on the value of p we choose an appropriate matching mechanism to determine Y : Y is determined such that i [n](i, Yi) is

a maximum weight matching in G if p 0,

a minimum weight perfect matching in G if p < 0 and p = ,

a max-min matching13 in G if p = .

13This is a matching that maximizes the weight of the smallest edge in the matching.

Let Y be the allocation outputted by the corresponding matching subroutine. Also let Y = i [n]Yi. We modify the allocation Y slightly such that i [n](i, Yi) still remains the optimum matching, but no agent will prefer a good outside Y to the good allocated to him in Y (Yi), i.e., we wish to determine an allocation Y such that for all agent i [n] and all g / Y we have that rank i(Yi) < rank i(g). To achieve this, as long as there is an agent i [n] and a good g / Y such that rank i(g) < rank i(Yi) we set Yi {g}. Note that such an operation does not decrease the optimum value of the matching: vi(g) vi(Yi) (as rank i(g) < rank i(Yi)) and hence wig wi Yi for p = and p [0, 1], while wig wi Yi for p < 0 and p = . This implies that the objective value of the matching does not decrease when p [0, 1] and p = and the objective value of the matching does not increase when p < 0 and p = . Therefore, i [n](i, Yi) still stays an optimum matching, but P i [n] rank i(Yi) strictly decreases. Since n P i [n] rank i(Yi) nm, after O(nm) iterations we will have an allocation Y such that i [n](i, Yi) is still an optimum matching, but for all agents i [n] and for all goods g / Y we have rank i(Yi) < rank i(g). The complete algorithm is outlined in Algorithm 1 (Selection of the allocation Y is captured in steps 1 to 5).

Lemma 7. For all i [n] we have Yi Hi. Furthermore, for all

g / Hi, and g / Y,

we have vi(Yi) vi(g).

Proof. We ﬁrst show that Yi Hi. We prove the same by contradiction. Assume otherwise, i.e., Yi Hi. In that case note that there is always a good g Hi\Y (as |Hi| = |Y| = n and there is a good in Y (namely Yi) which is not in Hi). By the deﬁnition of Hi it is clear that rank i(g) < rank i(g ) for all g / Hi. Thus we have rank i(g) < rank i(Yi) when g / Y, which is a contradiction. Therefore Yi Hi. This also immediately shows that for all g / Hi we have vi(g) vi(Yi) (as Yi Hi and any good in Hi is at least as valuable as any good outside Hi to agent i). The proof of the last statement of the lemma is immediate. We have that rank i(Yi) < rank i(g) for all g / Y, immediately implying that vi(Yi) vi(g).

Run (α, c)-EFX algorithm on the remaining goods: Once we determined the initial allocation Y , we run an (α, c)-EFX algorithm on the remaining goods starting with Y as the initial allocation (Y is a feasible initial allocation as it is trivially an α-EFX allocation as every agent has exactly a single good). Let Z be the ﬁnal (α, c)-EFX allocation. As mentioned earlier in Section the singleton sets allocated to the agents are the barriers to proving our desired approximation for any (α, c)-EFX allocation. However since we started with a good initial allocation (namely Y ), we ﬁrst show that we have some nice properties about the singleton sets in the ﬁnal allocation Z.

Observation 8. If |Zℓ| = 1 for any ℓ [n], then we have Zℓ Y.

Proof. Since Z is obtained by running an (α, c)-EFX algorithm starting with Y as the initial allocation, we have for every agent i that vi(Zi) vi(Yi) (from the deﬁnition of (α, c)-EFX algorithm). Note that if for any agent i we have Zi = Yi, and |Zi| = 1, then vi(Zi) > vi(Yi) (from the definition of (α, c)-EFX algorithm). Now consider the agent ℓ such that |Zℓ| = 1. If Zℓ= Yℓ, then we immediately have Zℓ Y. So now consider the case when Zℓ = Yℓ. Then we have vℓ(Zℓ) > vℓ(Yℓ). By Lemma 7 we know that no good outside Y can be more valuable to agent ℓthan Yℓ. Therefore Zℓ Y.

Now we show a lower bound on the ﬁnal valuation of an agent in terms of the low valued goods.

Observation 9. We have vi(Zi) αvi(M\Y)

2(n+1) for all i [n].

Proof. Fix an agent i. Now consider any agent j such that Zj is not a singleton. Since Z is an α-EFX allocation, we have that vi(Zi) α vi(Zj \g) for all g Zj. Since |Zj| 2 we can say that vi(Zi) α max(vi(Zj \ g), vi(g)). Therefore we have,

vi(Zi) α (vi(Zj \ g) + vi(g))

2 ( by subadditivity)

Let S = |Zℓ|=1Zℓ. By Observation 8 we know that S Y. Note that even if Z is a partial allocation (if c = 0 in the (α, c)-EFX allocation Z) and there exists a set of goods P unallocated, we have vi(Zi) vi(P) (since Z is an (α, c)- EFX allocation) . Therefore we have,

(n + 1 |S|)vi(Zi) α

|Zj| 2 vi(Zj) + vi(P)

|Zj| 2 Zj P

( by subadditivity) = α

2 vi(M \ S)

2 vi(M \ Y )

( since S Y)

Therefore we have vi(Zi) α 2(n+1 |S|)vi(M \ Y) α 2(n+1)vi(M \ Y).

Now we show a lower bound on vi(Zi) in terms of the initial allocation Y and the set of low-valued goods for agent i, i.e., M \ Hi.

Lemma 10. For all i [n] we have vi(Zi) α 4(n+1) n

vi(Yi) + vi M \ Hi .

Algorithm 1 Determining an (α, c)-EFX allocation with O(n) approximation on optimum p-mean.

1: Construct G = [n] M, [n] M with

n vi(g) + vi(M \ Hi) if p =

log n vi(g) + vi(M \ Hi) if p = 0 n vi(g) + vi(M \ Hi) p otherwise

2: Set Y such that

i [n](i, Yi) =

Max-Min-Matching(G) if p = Min-Weight-Perfect-Matching(G) if p < 0 and p = Max-Weight-Matching(G) otherwise

3: while i [n] and g / Y such that rank i(g) < rank i(Yi) do 4: Yi {g}.

5: Set Z (α, c)-EFX Y1, . . . , Yn , M \ i [n]Yi

Proof. Proof can be found in the full version of the paper (Lemma 10 in (Chaudhury, Garg, and Mehta 2020)).

The ﬁnal allocation is the set Z which is obtained by running an (α, c)-EFX algorithm starting with Y as the initial allocation. Therefore our ﬁnal allocation is an (α, c)-EFX allocation. We will now show the approximation guarantees that the algorithm achieves. The section that follows, proves that the allocation Z has a Nash-welfare that is α 4(n+1) times Nash-welfare achieved by the optimal allocation. We now discuss the case where p = 0 and Mp(X) = Q i [n] vi(Xi) 1

n . Let X be the allocation with the highest p-mean value and let g i be agent i s most valuable good in X i . Like in the earlier sections we will show in this section that Mp(Z) α 4(n+1) Mp(X ). First observe that by Lemma 10, we have that for all i [n], vi(Zi) α 4(n+1) n vi(Yi) + vi M \ Hi . Therefore, Q i [n] vi(Zi) 1

is greater than or equal to, Y

α 4(n + 1) n vi(Yi) + vi M \ Hi 1

= α 4(n + 1) Y

n vi(Yi) + vi M \ Hi 1

Recall that Y was chosen such that (i, Yi) is a maximum weight matching in the bipartite graph G = ([n] M, [n] M) where the weight of an edge from agent i to

good g, wig = log n vi(g) + vi(M \ Hi) . Note that

i [n](i, g i ) is a feasible matching in G. Thus we have P i [n] log n vi(Yi) + vi(M \ Hi) P i [n] log n

vi(g i )+vi(M \Hi) . This implies that Q i [n] n vi(Yi)+

vi(M \Hi) Q i [n] n vi(g i )+vi(M \Hi) . Therefore

we have, Q i [n] vi(Zi) 1

n to be greater than or equal to

α 4(n + 1) Y

n vi(Yi) + vi(M \ Hi) 1

α 4(n + 1) Y

n vi(g i ) + vi(M \ Hi) 1

α 4(n + 1) Y

n vi(g i )+

vi X i (M \ Hi) 1

α 4(n + 1) Y

vi(X i Hi)+

vi X i (M \ Hi) 1

(as |Hi| = n)

α 4(n + 1) Y

i [n] vi(X i ) 1

( by subadditivity)

This shows that Mp(Z) α 4(n+1) Mp(X ) when p = 0. In the full version of the paper (Chaudhury, Garg, and Mehta 2020), we show that with a very similar proof, we can prove Mp(Z) α 4(n+1) Mp(X ) for all p [ , 1]. The following theorem summarizes the main result of our paper. Theorem 11. Given any instance [n], M, V , in polynomial time we can determine an allocation Z such that Z is either (1 ε, 0)-EFX allocation or ( 1

2 ε, 1)-EFX allocation for any positive ε and Mp(Z) α 4(n+1)Mp(X ).

where X is the allocation with maximum p-mean welfare.

Proof. The proof can be found in the full version of the paper (Theorem 12 in (Chaudhury, Garg, and Mehta 2020)).

Remark: Theorem 11 also suggests that we can ﬁnd a 4(n+1)

1 ε approximation to the p-mean welfare in polynomial time. Also, it can be veriﬁed that a minor variant of our approach (changing the weights of the edges of the complete bipartite graph G([n] B, [n] B) appropriately - step 1

of Algorithm 1) gives a O(n) approximation on weighted generalized p-mean, deﬁned as WM p(X) = P i [n] ηi

Acknowledgements

Jugal Garg is supported by NSF CAREER Grant CCF1942321. Ruta Mehta is supported by NSF CAREER Grant CCF 1750436.

Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; Hollender, A.; and Voudouris, A. A. 2020. Maximum Nash Welfare and Other Stories About EFX. Co RR abs/2001.09838.

Amanatidis, G.; Markakis, E.; Nikzad, A.; and Saberi, A. 2017. Approximation algorithms for computing maximim share allocations. ACM Transactions on Algorithms 13(4): 52:1 52:28.

Anari, N.; Gharan, S. O.; Saberi, A.; and Singh, M. 2017. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS), 1 12.

Anari, N.; Mai, T.; Gharan, S. O.; and Vazirani, V. V. 2018. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. In Proc. 29th Symp. Discrete Algorithms (SODA), 2274 2290.

Babaioff, M.; Ezra, T.; and Feige, U. 2020. Fair and Truthful Mechanisms for Dichotomous Valuations. Co RR abs/2002.10704.

Barman, S.; Bhaskar, U.; Krishna, A.; and Sundaram, R. G. 2020. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. Co RR abs/2005.07370.

Barman, S.; Biswas, A.; Murthy, S. K. K.; and Narahari, Y. 2018. Groupwise Maximin Fair Allocation of Indivisible Goods. In AAAI, 917 924. AAAI Press.

Barman, S.; and Krishnamurthy, S. K. 2017. Approximation algorithms for maximin fair division. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), 647 664.

Barman, S.; and Krishnamurthy, S. K. 2019. On the Proximity of Markets with Integral Equilibria. In Proc. 33rd Conf. Artif. Intell. (AAAI).

Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018. Finding Fair and Efﬁcient Allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), 557 574.

Barman, S.; and Sundaram, R. G. 2020. Uniform Welfare Guarantees Under Identical Subadditive Valuations. Co RR abs/2005.00504.

Benabbou, N.; Chakraborty, M.; Igarashi, A.; and Zick, Y. 2020. Finding Fair and Efﬁcient Allocations When Valuations Don t Add Up. In SAGT, volume 12283 of Lecture Notes in Computer Science, 32 46. Springer.

Bouveret, S.; and Lemaˆıtre, M. 2016. Characterizing conﬂicts in fair division of indivisible goods using a scale of criteria. In Autonomous Agents and Multi-Agent Systems (AAMAS) 30, 2, 259 290. Budish, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6): 1061 1103. Budish, E.; Cachon, G. P.; Kessler, J. B.; and Othman, A. 2017. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Operations Research 65(2): 314 336. Caragiannis, I.; Gravin, N.; and Huang, X. 2019. Envy Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In EC, 527 545. ACM. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), 305 322. Chaudhury, B. R.; Cheung, Y. K.; Garg, J.; Garg, N.; Hoefer, M.; and Mehlhorn, K. 2018. On Fair Division for Indivisible Items. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, 25:1 25:17. Chaudhury, B. R.; Garg, J.; and Mehta, R. 2020. Fair and Efﬁcient Allocations under Subadditive Valuations. Co RR abs/2005.06511. Chaudhury, B. R.; Kavitha, T.; Mehlhorn, K.; and Sgouritsa, A. 2019. A Little Charity Guarantees Almost Envy Freeness. Co RR abs/1907.04596. Chaudhury, B. R.; Kavitha, T.; Mehlhorn, K.; and Sgouritsa, A. 2020. A Little Charity Guarantees Almost Envy Freeness. In Proceedings of the 31st Symposium on Discrete Algorithms (SODA), 2658 2672. Cole, R.; Devanur, N.; Gkatzelis, V.; Jain, K.; Mai, T.; Vazirani, V.; and Yazdanbod, S. 2017. Convex Program Duality, Fisher Markets, and Nash Social Welfare. In Proc. 18th Conf. Economics and Computation (EC). Cole, R.; and Gkatzelis, V. 2018. Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput. 47(3): 1211 1236. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proc. 18th Conf. Economics and Computation (EC), 629 646. Garg, J.; Hoefer, M.; and Mehlhorn, K. 2018. Approximating the Nash Social Welfare with Budget-Additive Valuations. In Proc. 29th Symp. Discrete Algorithms (SODA). Garg, J.; Kulkarni, P.; and Kulkarni, R. 2020. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. In SODA. Garg, J.; and Mc Glaughlin, P. 2019. Improving Nash Social Welfare Approximations. In IJCAI, 294 300. ijcai.org. Garg, J.; Mc Glaughlin, P.; and Taki, S. 2019. Approximating Maximin Share Allocations. In Proceedings of the 2nd

Symposium on Simplicity in Algorithms (SOSA), volume 69, 20:1 20:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Garg, J.; and Taki, S. 2019. An Improved Approximation Algorithm for Maximin Shares. Co RR abs/1903.00029. Ghodsi, M.; Hajiaghayi, M. T.; Seddighin, M.; Seddighin, S.; and Yami, H. 2018. Fair Allocation of Indivisible Goods: Improvements and Generalizations. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), 539 556. Khot, S.; and Ponnuswami, A. K. 2007. Approximation Algorithms for the Max-Min Allocation Problem. In APPROXRANDOM, volume 4627 of Lecture Notes in Computer Science, 204 217. Springer. Kurokawa, D.; Procaccia, A. D.; and Wang, J. 2018. Fair enough: Guaranteeing approximate maximin shares. Journal of ACM 65(2): 8:1 27. Lee, E. 2017. APX-hardness of Maximizing Nash Social Welfare with Indivisible Items. Inf. Process. Lett. 122: 17 20. Lehmann, B.; Lehmann, D.; and Nisan, N. 2006. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2): 270 296. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), 125 131. Nguyen, T. T.; and Rothe, J. 2014. Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics 179: 54 68. Plaut, B.; and Roughgarden, T. 2018. Almost Envy-Freeness with General Valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2584 2603. Steinhaus, H. 1948. The Problem of Fair Division. Econometrica 16(1): 101 104.