Maximum Nash Welfare and Other Stories About EFX

1 Introduction

Fair division refers to the general problem of allocating a set of resources to a set of agents in a way satisfying a desired fairness criterion. A well-known example of such a criterion is envy-freeness [Gamow and Stern, 1958], where each agent perceives the share she receives to be no worse than what any other agent receives. Since the problem was formally introduced by Banach, Knaster and Steinhaus [1948], fair division has attracted the attention of various scientific disciplines, including mathematics, economics, and political science. During the last two decades, the algorithmic aspects of fair division have been the focus of a particularly active line of work within the computer science community, e.g., see [Procaccia, 2016; Bouveret et al., 2016] and references therein.

We consider the classic setting where the resources are indivisible goods that need to be fully allocated and the agents have additive valuation functions. One of the main challenges in this setting is that classic fairness notions such as equitability, envy-freeness and proportionality-introduced several decades ago having divisible resources in mind-are impossible to satisfy. To see this for envy-freeness, it suffices to consider two agents and one good of value; one agent is going to be envious. This has led to the recent emergence of several weaker fairness notions (see Related work). As a result, there is a plethora of open questions about the existence, the computation and the interrelationships of such notions. In this work we focus on two of the most prominent: envy-freeness up to any good (EFX) and maximum Nash welfare (MNW).

EFX, introduced recently by Caragiannis et al. [2019b], is an additive relaxation of envy-freeness. Here an agent may envy another agent but only by the value of the least desirable good in the other agent's bundle. While this added flexibility of EFX takes care of extreme pathological cases like the one mentioned above (2 agents, 1 good), this notion is not well understood yet. Despite the active interest in it, it is unknown whether EFX allocations always exist, even for 4 agents with additive valuation functions. 1 We consider the problem of showing the existence of EFX allocations to be one of the most intriguing currently open questions in fair division.

The Nash social welfare (or, simply, Nash welfare) is the geometric mean of the agents' utilities. By considering maximum Nash welfare (MNW) allocations, i.e., allocations that maximize the product of the utilities, we achieve some kind of balance between the efficiency of the maximum utilitarian social welfare-the sum of the utilities-and the individual fairness of the maximum egalitarian social welfare-the minimum utility. Although not a fairness concept per se, MNW has strong ties to fairness. In the setting where the goods are divisible, each (possibly fractional) MNW allocation corresponds to a competitive equilibrium of equal incomes, a market equilibrium (under the assumption that all agents are endowed with the same budget) that is known to guarantee envy-freeness and Pareto optimality [Varian, 1974]. Even in our setting, Caragiannis et al. [2019b] showed that integral MNW allocations, besides being Pareto optimal, are envy-free up to one good (EF1) and satisfy maximin share fairness up to a Θ(1/√n) factor, where n is the number of agents. Both these guarantees are significantly weaker than EFX.

1 Existence of EFX allocations for 3 agents was very recently shown by Chaudhury et al. [2020a].

In general, MNW does not imply EFX. One of our goals is to identify the cases where it does, in terms of the allowed number of distinct values for the goods. For such cases, we want to obtain efficient algorithms for computing EFX allocations, either through maximizing the Nash welfare or directly. Since, in general, MNW does not even imply a non-trivial approximation of EFX, we further introduce a less stringent, yet natural, new interpretation of approximate EFX and investigate how it is related to MNW.

1.1 Contribution

There are two variants of EFX used in the related literature, depending on whether only the positively valued goods are considered or not; for the latter case we adopt the name EFX0 suggested by Kyropoulou et al. [2019]. We start by establishing a strong algorithmic connection between the two variants (Proposition 2.1). Then we explore the relationship between maximizing the Nash welfare and achieving EFX or EFX0 allocations. In doing so, we also obtain some interesting results for the individual notions. In particular:

• In case there are at most two possible values for the goods (2-value instances), we show that any allocation that maximizes the Nash welfare is EFX0 (Theorem 3.1). This has the following two consequences:
• (a) For any 2-value instance, there exists an EFX0 allocation. Note that this is the first such existence result for non-identical valuations that holds for any number of agents and goods;
• (b) For the special case of binary valuations, by adapting an algorithm of Barman et al. [2018c], we can efficiently construct an allocation that is both MNW and EFX0.

The implication MNW ⇒ EFX0 is no longer true for three or more distinct values.

• For 2-value instances, the efficient computation of an MNW allocation remains an open problem. Nevertheless, we propose a polynomial-time algorithm for producing EFX0 allocations in this case (Theorem 5.1). This algorithm, which we call MATCH&FREEZE, is based on repeatedly computing maximum matchings and "freezing" certain agents whenever they acquire too much value compared to their peers. We believe these novel ideas might be a stepping stone for proving the existence of EFX allocations in more general settings.
• For general additive valuations, we show that an MNW allocation does not guarantee any non-trivial approximation of EFX. However, we argue that the current definition of approximate EFX allocations is not always meaningful. Instead, we explore a different natural definition based on the idea of (hypothetically) augmenting an agent's bundle until an EFX-like condition is satisfied. For this new benchmark, which we call EFX-value, we show that any MNW allocation is a 1/2-approximation of EFX (Theorem 6.2).

1.2 RelatedWork

As there is a vast literature on fair division, here we focus on the indivisible items setting and on related fairness notions. The concept of envy-freeness up to one good (EF1) was implicitly suggested by Lipton et al. [2004] and formally defined by Budish [2011]. Budish [2011] also introduced the notion of maximin share (MMS), which has been studied extensively [Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishnamurthy, 2017; Garg et al., 2019; Ghodsi et al., 2018; Garg and Taki, 2019] and has yielded several very interesting variants like pairwise MMS [Caragiannis et al., 2019b], groupwise MMS [Barman et al., 2018a], and MMS for groups of agents [Suksompong, 2018].

As already mentioned, EFX was introduced by Caragiannis et al. [2019b]. Plaut and Roughgarden [2018] defined what an α-approximate EFX (or α-EFX) allocation is and studied exact and approximate EFX allocations with both additive and general valuations. Most of their results, including the existence of EFX allocations for identical valuations, hold under the similar but stricter notion of EFX0 which is implicitly introduced therein. The currently best 0.618-approximation of either EFX or EFX0 for the additive case is due to Amanatidis et al. [2019]. For binary additive valuations, Aleksandrov and Walsh [2019] recently proposed an algorithm that produces EFX-but not necessarily EFX0-allocations. Independently and at the same time with our work, Babaioff et al. [2020] designed an algorithm that computes an EFX0 allocation which maximizes the Nash welfare for submodular dichotomous valuations, a class that includes binary, but does not include general 2-value additive valuations.

Besides [Caragiannis et al., 2019b], there are several recent papers which relate allocations that maximize (exactly or approximately) the Nash welfare with other fairness notions. Caragiannis et al. [2019a] showed that there exist incomplete allocations that are EFX and in which each agent receives at least half of the value they get in a MNW allocation; Chaudhury et al. [2020b] achieved the same with only a few unallocated goods. Garg and McGlaughlin [2019] showed how to get an allocation that 2-approximates the Nash welfare of an MNW allocation that is also proportional up to one good, satisfies a weak MMS guarantee and is Pareto optimal.

Since computing MNW allocations is an APX-hard problem [Lee, 2017], there is an active interest on special cases like binary valuations [Barman et al., 2018c] or on approximation algorithms for additive [Cole and Gkatzelis, 2018; Cole et al., 2017; Barman et al., 2018b] or even more general valuation functions [Garg et al., 2020].

2 Preliminaries and Notation

We consider fair division instances I = (N,M, (vi)i∈N) in which there is a set N of n agents and a set M of m indivisible goods. Each agent i ∈ N has a valuation function vi : M → R≥0 assigning a non-negative value vi(g) to each good g ∈ M. We assume vi is additive, i.e., vi(A) = ∑g∈A vi(g) for every set (or bundle) of goods A ⊆ M.

We pay particular attention to the following subclasses of additive valuation functions: (1) Binary: vi(g) ∈ {0, 1} for every i ∈ N and g ∈ M, and (2) k-value: there is a set V

consisting of |V | = k distinct, non-negative real values such that vi(g) ∈ V for every i ∈ N and g ∈ M. Of course, any binary instance is a 2-value instance with V = {0, 1} but we distinguish between these cases for technical reasons that will become apparent later on.

A complete allocation (or just allocation) A = (Ai)i∈N is a vector listing the bundle Ai of goods that each agent i receives, such that Ai ∩ Aj = ∅ for every i, j ∈ N, and ∪i∈NAi = M. Our goal is to come up with allocations that are considered to be fair by all agents. We begin by defining envy-freeness and its additive relaxations.

Definition 2.1. An allocation A = (Ai)i∈N is

• envy-free (EF) if vi(Ai) ≥ vi(Aj) for every i, j ∈ N;
• envy-free up to one good (EF1) if for every i, j ∈ N with Aj ̸= ∅ there exists a good g ∈ Aj, such that vi(Ai) ≥ vi(Aj \ {g});
• envy-free up to any (positively-valued) good (EFX) if for every i, j ∈ N and every good g ∈ Aj for which vi(g) > 0, we have vi(Ai) ≥ vi(Aj \ {g});
• envy-free up to any good (EFX0) if for every i, j ∈ N and every good g ∈ Aj , we have vi(Ai) ≥ vi(Aj \{g}).

By definition, we have EF ⇒ EFX0 ⇒ EFX ⇒ EF1, but no implication works in the opposite direction. For brevity, we say that agent i is E towards agent j when the criterion of E ∈ {EF, EF1, EFX, EFX0} is true for the ordered pair (i, j).

Definition 2.2. The Nash welfare of an allocation A = (Ai)i∈N is the product 2 of the values of the agents for their bundles: NW(A) = ∏i∈N vi(Ai).

We will usually denote by A∗ one of the allocations that maximize the Nash welfare (MNW). Among all such allocations, we will sometimes select A∗ so that some additional properties are satisfied; e.g., see the discussion in Section 3. Caragiannis et al. [2019b] showed that MNW ⇒ EF1, but the exact connection between MNW and the variants of EFX is not well-understood.

Before we dive into our main technical results, we show a somewhat surprising connection between EFX and EFX0. In particular, assuming agents with k-value valuation functions, for any k ∈ N, the question of finding an EFX0 allocation reduces to finding an EFX allocation for an instance with only slightly perturbed valuation functions. An immediate corollary is that the existence (resp. the efficient computation) of EFX allocations for additive agents implies the existence (resp. the efficient computation) of EFX0 allocations; the converse statements are obvious.

Proposition 2.1. Let k ∈ N. The problem of computing EFX0 allocations for k-value instances reduces to the problem of computing EFX allocations for k-value instances. When all values are rational numbers, this reduction requires only polynomial time.

2 As mentioned in the Introduction, the Nash welfare is usually defined as the geometric mean of the values rather than their product. As the allocations (exactly) maximizing the Nash welfare are the same under both definitions, we use the product for simplicity.

3 When Does MNW Imply EFX?

In this section we focus on allocations that maximize the Nash welfare. We first identify the subclasses of valuation functions for which the MNW allocations are always EFX0, and then consider computational complexity questions. Our main result here is that for all 2-value instances (including binary) any MNW allocation is also EFX0. Moreover, this result is tight: there exist 3-value instances for which this implication is no longer true.

Throughout this section, we assume that for every good g, there exists at least one agent i with vi(g) > 0, but our results hold without this assumption.

When we talk about MNW allocations, the standard interpretation would be to include all complete allocations which achieve the maximum Nash welfare for an instance. When it is possible to achieve positive Nash welfare this is indeed true. However, for the extreme case of instances where all allocations have zero Nash welfare we are going to need a refinement. Following the work of Caragiannis et al. [2019b], for instances with maximum Nash welfare equal to zero, we call an allocation an MNW allocation if it (1) maximizes the number of agents with positive value, and then (2) maximizes the product of the values of such agents. This restriction is necessary because when all allocations have zero Nash welfare, the idea of maximizing it clearly fails to distinguish "good" allocations in any sense. To illustrate this, consider the next instance:

Since the first two agents only like g1, the Nash welfare of any allocation is 0. However, not all allocations are EFX0. The allocation {∅, ∅, {g1, g2, g3}} is clearly not EFX0 since the first two agents envy agent 3 even after the removal of either g2 or g3. Even an allocation such as {{g1, g2}, ∅, {g3}}, which maximizes the number of agents with positive value, is not EFX0 since agent 2 envies agent 1 even after the removal of g2. On the other hand, the allocation {{g1},∅, {g2, g3}}, which maximizes the number of agents with positive value as well as the product of their values, is indeed EFX0: the envy of agent 2 towards agent 1 is eliminated by the removal of g1.

It should be noted that both (1) and (2) are by default true for MNW allocations in instances with positive Nash welfare. We next show that maximizing the Nash welfare subject to (1) and (2) yields an EFX0 allocation for any 2-value instance.

Theorem 3.1. Each MNW allocation is an EFX0 allocation, for any 2-value instance.

Proof. Due to space constraints, we prove the statement for two values {a, b} such that a > b > 0. Then EFX0 coincides with EFX. The proof for when b = 0 (essentially the binary case) is of similar flavor, albeit simpler, despite having to consider instances with zero Nash welfare.

Let i and j be any two agents who are given the sets of goods Ai and Aj in an MNW allocation A∗ . We say that a good is of type Txy if i and j have values vi(g) = x and vj(g) = y for good g, respectively; so there are four different types of goods: Taa, Tab, Tba and Tbb. If ming∈Aj vi(g) = a or maxg∈Aj vi(g) = b, then i is EFX towards j since i is EF1 towards j [Caragiannis et al., 2019b] and the two notions coincide in this case for the pair (i, j). Therefore, from now on, we will assume that ming∈Aj vi(g) = b and maxg∈Aj vi(g) = a, which implies that |Aj| ≥ 2 and Aj includes at least one good of type Tba or Tbb.

Case I: There is at least one good of type Tbb in Aj.

Subcase (a): Aj does not include any good of type Tab. Assume, towards a contradiction, that i is not EFX towards j: vi(Ai) < vi(Aj)-b. Since vj(g) ≥ vi(g) for all g ∈ Aj , we have that vj(Aj) ≥ vi(Aj). We now define a new allocation by moving a good h ∈ Aj of type Tbb from j to i. In this new allocation, the product of the values of i and j is

Since the allocation of all other agents has not been changed, the new allocation achieves a strictly larger Nash welfare than A∗ , yielding a contradiction.

Subcase (b): Aj includes at least one good g of type Tab. We will argue about the structure of set Ai. If Ai includes any good x of type Taa, Tba or Tbb, then by exchanging g with x, we obtain an allocation with strictly higher Nash welfare, contradicting the choice of A∗ . For example, if x is of type Taa, then in the new allocation (after swapping x and g) agent i has exactly the same value, but agent j's value has strictly increased by an amount a - b > 0. One can verify that the same holds for the other two types. Hence, Ai must include only goods of type Tab, which implies that vi(Ai) = |Ai|a.

Towards a contradiction, assume that i is not EFX towards j. If |Aj| ≤ |Ai| + 1, since Aj includes some good h for which vi(h) = b, we have that

i.e., agent i is EFX towards j. So, it must be |Aj| ≥ |Ai|+2. We create a new allocation by moving a good g ∈ Tab from j to i. The product of the values of i and j then becomes

Since vj (Aj ) ≥ |Aj |b ≥ (|Ai| + 2)b and vi(Ai) = |Ai|a, we have that

Since the bundles of the other agents have not been changed, we have that the new allocation has strictly larger Nash welfare than A∗ , contradicting its choice.

Case II: There are no goods of type Tbb in Aj .

ThenAj includes at least one good of type Tba. If Aj includes at least one good of type Tab, then, as we argued in Case I(b) above, in order for A∗ to be an MNW allocation, Ai cannot include any goods of type Taa, Tba or Tbb. As a result, Ai includes only goods of type Tab and by reproducing the analysis used in Case I(b) it follows that A∗ is EFX.

So, we may assume that Aj includes goods of type Tba and Taa only. This implies that vj(Aj) = |Aj|a. Assume towards a contradiction that i is not EFX towards j: vi(Ai) < vi(Aj) - b. Since Aj contains at least one good that i values as b, we also have that vi(Aj ) ≤ (|Aj | - 1)a + b. Combining the last two expressions, we obtain that

Now, consider the allocation that is obtained from A∗ by moving a good of type Taa from j to i. We know that such an item exists since maxg∈Aj vi(g) = a. By using the last inequality, the product of the values of i and j in the new allocation is

which combined with the fact that the bundles of the other agents have not been changed, contradicts the choice of A∗ . In any case, we conclude that A∗ must be EFX.

Caragiannis et al. [2019b] presented a 3-value instance in which no MNW allocation is EFX. For completeness, we include here a simpler such instance. Let ε be a small positive constant and consider an instance with two agents and three goods with values as shown in the table:

This is a 3-value instance with values {1 - ε, 1, 1 + ε}. It is easy to verify that there are exactly two allocations achieving the maximum Nash welfare of 2 + ε: A1 = ({g2}, {g1, g3}) and A2 = ({g2, g3}, {g1}). The Nash welfare of any other allocation is either 2(1-ε) or 2+ε-ε2 . Now, for ℓ ∈ {1, 2}, observe that in Aℓ agent ℓ is not EFX towards the other agent since she envies her even after the removal of gℓ.

3.1 Complexity of Maximizing the NashWelfare

We now turn our attention to the complexity of computing a maximum Nash welfare allocation. This problem is already known to be hard for many domain restrictions, and easy for only a few special cases. Nevertheless, its complexity for kvalue instances with k ∈ {2, 3, 4} has been open. Here we make significant progress towards settling these cases.

For binary instances, Barman et al. [2018c] gave the greedy algorithm ALG-BINARY that outputs an allocation maximizing the Nash welfare. If the Nash welfare is positive, then the outputted allocation is also EFX0 by Theorem 3.1. However, if the Nash welfare is zero, ALG-BINARY might not output an MNW allocation in our sense, i.e., an allocation that maximizes the number of agents with positive values and their product (in that order). To circumvent this, we define a bipartite graph consisting of nodes corresponding to the agents on the left and nodes corresponding to the goods on the right, while an edge between an agent and a good exists if and only if the agent has value 1 for the good. By computing a maximum bipartite matching on this graph, it is guaranteed that the number of agents with positive value is maximized. Then, we run ALG-BINARY on the restricted instance where the set of agents includes only the ones that participate in the maximummatching, so that the product of their values (which now is going to be positive) is also maximized. This leads to the following statement.

Theorem 3.2. For binary instances, computing an MNW allocation (and thus an EFX0 allocation) can be done in polynomial time.

For general 2-value instances we were unable to resolve the complexity of computing an MNW allocation, but we show that the problem is NP-hard for 3-value instances. This extends the hardness aspect (but not the inapproximability) of the result of Lee [2017] for 5-value instances.

Theorem 3.3. Computing an MNW allocation is NP-hard, even for 3-value instances.

4 EFXAllocations for 2-Value Instances

Even though we showed that any MNW allocation is also EFX0 for agents with 2-value valuation functions, it remains an open question whether there exists a polynomial-time algorithm for computing such allocations beyond the binary case. In this section, we try to circumvent this and aim to design an efficient algorithm for computing EFX0 allocations (which might not maximize the Nash welfare) for 2-value instances. We assume values {a, b}, such that a > b ≥ 0.

Our algorithm, which we call MATCH&FREEZE, proceeds in rounds and maintains a set of active agents L, initially containing everyone. In each round, every active agent is given exactly one of the remaining goods, with the possible exception of the last round in which there might not be enough goods left for all agents. The algorithm terminates when all goods have been allocated.

To determine which good each active agent gets during a round, we create a bipartite graph G = (L∪R, E) with nodes corresponding to the active agents L on one side and to the remaining goods R on the other. An edge between an active agent i and a good g exists if and only if vi(g) = a. We first compute a maximum matching on this graph. Then each agent gets the good to which she is matched. If there are agents who are not matched to any good and there are still available goods, the unmatched agents receive one arbitrary available good each (subject to availability).

There are two possible reasons why an agent i is not matched to any good in a round: (1) she does not have value a for any good (only b), or (2) the maximum matching is such that all goods for which her value is a are given to other agents. Case (1) does not affect whether the final allocation will be EFX0, but case (2) is crucial. This is because agent i might now have much smaller value for her own bundle compared to her value for the bundles of some agents that just received one good each that i values as a. Let Z be the set of these agents. To make up the distance, agent i should possibly receive multiple goods of value b while all agents in Z must freeze for a number of subsequent rounds depending on the ratio a/b.

Algorithm 1 MATCH&FREEZE(N, M, (vi)i∈N )

1: Input: a 2-value instance using the values a, b (a > b ≥ 0) 2: L←N ▷ set of active agents 3: R←M ▷ set of unallocated goods 4: ℓ = (1, 2, . . . , n) ▷ ordered list of agents 5: while R ̸= ∅ do ▷ every iteration is a round 6: Construct the bipartite graph G = (L∪R,E). 7: Compute a maximummatching on G. 8: for each matched pair (i, g) do 9: Allocate good g to agent i. 10: Remove g fromR. 11: for each unmatched active agent i w.r.t. ℓ do 12: Allocate one arbitrary unallocated good g to i. 13: Remove g fromR. 14: Construct the set F of agents that need to freeze. 15: Remove agents of F fromL for the next ⌊a/b-1⌋ rounds. 16: Put agents of F to the end of ℓ. 17: return the resulting allocation A.

We define the set F of agents that need to freeze at the end of round r to consist of all those agents who must become inactive because they have obtained too much value from the perspective of other agents (similarly to Case (2) above). Formally, for every active agent i, let gi be the good she gets in round r. We begin by setting F = {i ∈ L| ∃j ∈ L : vj(gi) = a, vj(gj) = b}. Then, iteratively, as long as there is an agent i ∈ L\F such that there exists j ∈ F with vj(gi) = a, we also add i to F. Each agent in F will remain frozen for the next ⌊a/b - 1⌋ rounds. In the case b = 0, we use the interpretation ⌊a/b - 1⌋ = +∞ in which case agents in F remain frozen forever. Exploiting the properties of the maximum matchings used to allocate goods we can prove that no agent in F will become envious while frozen, and that F is always a strict subset of L. The latter means that there is at least one (non-frozen) active agent at any time, and thus the algorithm will terminate after at most m rounds.

Theorem 4.1. MATCH&FREEZE computes an EFX0 allocation in polynomial time, for any 2-value instance.

Proof sketch. For any i ∈ N, let ri be the round in which the last goods of value a for agent i were allocated. Since the goods in every round are allocated by computing a maximum matching, we can show that for each agent i ∈ N:

• She received a good for which she has value a in each of the rounds 1, 2, . . . , ri - 1.
• She can freeze only at the end of round ri, and only if during ri she received a good for which she has value a.
• She can freeze at most once. After freezing, she has value b for each of the remaining goods.

First, let us see why the algorithm terminates in polynomial time. If no agent ever becomes frozen, then the algorithm terminates after at most ⌈m/n⌉ rounds. Otherwise, let r be the first round at the end of which an agent becomes frozen, i.e., there exists some agent j with vj(gj) = b and some agent i with vj(gi) = a. By the definition of rj and the above observations, r = rj. Since agent j did not become frozen in round r = rj (because vj(gj) = b), this means that she will never freeze. Since agent j gets a good in every round, the algorithm terminates after at most m rounds.

Now, it remains to show that the final allocation is EFX0. This follows by a careful case analysis and the following observation: If at the beginning of some round r > ri, an active agent i is envy-free towards agent j, then agent i will be EFX0 towards agent j at the end of the algorithm. Due to space constraints, we omit the details.

5 MNWand the EFX-Value

As we saw in Section 3, maximizing the Nash welfare does not yield an EFX allocation in general. Here we take a different route and instead of considering exact EFX allocations, we focus on approximation. We start by showcasing that maximizing the Nash welfare does not guarantee any meaningful approximation of EFX according to the current definition of approximation used in the literature [Plaut and Roughgarden, 2018; Chan et al., 2019; Amanatidis et al., 2019].

Definition 5.1 (α-EFX allocation). For α ∈ (0, 1], an allocation A is α-EFX if for every pair i, j ∈ N and every good g ∈ Aj such that vi(g) > 0, it holds that vi(Ai) ≥ αvi(Aj \{g}). Let w > 1 and ε < 1 2w . Consider the following very simple instance with two agents, three goods, and values:

We first claim that the allocation A∗ = (A1 = {g1, g3}, A2 = {g2}) is the only one that achieves the maximum Nash welfare of w+1/2. Indeed, the Nash welfare of any allocation that gives g2 to agent 1 can only increase by moving g2 to agent 2, while any allocation other than A∗ that gives g2 to agent 2 has Nash welfare either (w + 1)/2 or w + εw < w+1/2. Notice, however, that A∗ is not EFX since v2(A2) = 1 < w = v2(A1 \ {g3}). Instead, it is only 1/w-EFX, an approximation factor that can be arbitrarily close to zero as w becomes large.

Nevertheless, A∗ is not that far away from being an EFX allocation! To see this, consider the allocation B = (B1 = {g1}, B2 = {g2, g3}) that is obtained from A∗ by only moving g3 from agent 1 to agent 2. Clearly, agent 2 is EFX towards agent 1, as the latter gets only one good. Moreover, the value agent 2 has now is v2(B2) = 1 + ε, which is extremely close to the value v2(A2) = 1 that agent 2 has in A∗ . So, even though A∗ is 1/w-EFX because v2(A2) is very low compared to v2(A1 \ {g3}), v2(A2) is actually very close to the value she would have in a nearby EFX allocation. Consequently, if we accept that agent 2 considers the EFX allocation B as fair, then she should also consider A∗ as being almost fair.

We say that the value v2(B2) = 1+ε is the EFX-value that agent 2 can achieve by augmenting her bundle with a subset of goods from agent 1 in order to create the closest-to-A∗ (in terms of value) allocation B which she considers as EFX. Then, since v2(A2) = 1 1+ε v2(B2), agent 2 achieves an approximation of 1 1+ε of her EFX-value. Let us now formalize these notions for any number of agents.

Definition 5.2 (EFX-value). Let A = (A1, . . . ,An) be an allocation. For every pair of agents i, j ∈ N, let Xij ⊆ Aj be a set of goods such that vi(Ai ∪Xij) ≥ vi(Aj \ (Xij ∪{g})) for every g ∈ Aj \Xij and vi(Ai ∪Xij) is minimized. Then, the EFX-value of agent i is

Definition 5.3 (α-vEFX allocation). For α ∈ (0, 1], an allocation A is α-vEFX if vi(Ai) ≥ αχi(A) for every i ∈ N.

We remark that using EFX0 instead of EFX in the above definitions does not make any difference since adding zeros does not affect the EFX-value. Furthermore, observe that a 1vEFX allocation is an EFX allocation but not necessarily an EFX0 allocation.

Our first result in this section illustrates the connection between approximate EFX and vEFX allocations.

Theorem 5.1. An α-EFX allocation is also an α 1+α -vEFX allocation and this guarantee is tight. On the other hand, an α-vEFX allocation is not guaranteed to be β-EFX, for any α, β ∈ (0, 1).

Even though maximizing the Nash welfare may not yield a β-EFX for any β ∈ (0, 1) as we showed above, it is guaranteed to produce a 1/2-vEFX allocation!

Theorem 5.2. Any maximum Nash welfare allocation A∗ is a 1/2-vEFX allocation and this factor is tight.

6 Directions for FutureWork

We studied the connection between two celebrated notions, that of maximum Nash welfare and envy-freeness up to any good. The first question that our work leaves open is whether it is possible to compute in polynomial time an allocation that maximizes the Nash welfare for 2-value instances. Another direction is to investigate whether the algorithmic ideas presented in Section 5 for 2-value instances can be extended to computing EFX0 allocations for k-value instances, for any k ≥ 3. Finally, going beyond exact MNW or EFX allocations, a natural question is whether one can design polynomial-time algorithms with constant approximation guarantees for both the EFX-value and the Nash welfare.

Acknowledgements

We would like to thank Ioannis Caragiannis for fruitful discussions. G. Amanatidis was partially supported by the ERC Advanced Grant AMDROMA (No. 788893), the MIUR PRIN project ALGADIMAR and the NWO Veni project VI.Veni.192.153. G. Birmpas and A. Voudouris were partially supported by the ERC Starting Grant 639945 ACCORD "Algorithms for Complex Collective Decisions on Structured Domains". A. Hollender was partially supported by an EPSRC doctoral studentship (Reference 1892947).