# maximizing_nash_social_welfare_in_2value_instances__73f7b58c.pdf

Maximizing Nash Social Welfare in 2-Value Instances

Hannaneh Akrami,1 Bhaskar Ray Chaudhury,2 Martin Hoefer,3 Kurt Mehlhorn,4 Marco Schmalhofer,3 Golnoosh Shahkarami,1 Giovanna Varricchio,3 Quentin Vermande,5 Ernest van Wijland5

1 Max Planck Institute for Informatics, Graduiertenschule Informatik, Universit at des Saarlandes 2 University of Illinois, Urbana-Champaign, Department of Computer Science 3 Goethe University Frankfurt, Institute for Computer Science 4 Max Planck Institute for Informatics, Universit at des Saarlandes 5 Ecole Normale Sup erieure, Paris {hakrami, mehlhorn, gshahkar}@mpi-inf.mpg.de, braycha@illinois.edu, {mhoefer, varricchio, schmalhofer}@em.uni-frankfurt.de , {quentin.vermande, ernest.van.wijland}@ens.fr

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent i N for every good j G is vij {p, q}, for p, q N, p q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p = 1 and q N after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p 3. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.

Introduction

Fair division is an important area at the intersection of economics and computer science. While fair division with divisible goods is relatively well-understood in many contexts, the case of indivisible goods is signiﬁcantly more challenging. Recent work in fair division has started to examine extensions of standard fairness concepts such as envy-freeness to notions such as EF1 (envy-free up to one good) (Lipton et al. 2004) or EFX (envy-free up to any good) (Caragiannis et al. 2016), most prominently in the case of non-negative, additive valuations of the agents. In this additive domain, notions of envy-freeness are closely related to the Nash social welfare (NSW), which is deﬁned by the geometric mean of the valuations. An allocation maximizing the Nash social welfare is Pareto-optimal, satisﬁes EF1 (Caragiannis et al. 2016) and in some cases even EFX (Amanatidis et al. 2020). An important question is, thus, if we can efﬁciently compute or approximate an allocation that maximizes NSW. This is the question we study in this paper. More formally, we consider an allocation problem with a set N of n agents and a set G of m indivisible goods. Each agent i N has a valuation function vi : 2G Q 0. We

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

assume all functions to be non-negative, monotone, and normalized to vi( ) = 0. For convenience, we assume every vi maps into the rational numbers. The goal is to ﬁnd an allocation of the goods A = (A1, . . . , An) to maximize the Nash social welfare, i.e., the geometric mean of the valuations

Of particular interest are the instances admitting strictly positive NSW; clearly, in this case, an allocation that maximizes the NSW is Pareto-optimal. By maximizing the NSW, we strike a balance between maximizing the utilitarian social welfare P i vi(Ai) and the egalitarian social welfare mini vi(Ai). Notably, optimality and approximation ratio for NSW are invariant to scaling each valuation vi(Ai) by an agent-speciﬁc parameter ci > 0. This is yet another property that makes NSW an attractive objective function for allocation problems. It allows a further normalization we can assume every vi : 2G N0 maps into the natural numbers. Finding desirable approximation algorithms for maximizing the NSW has become an active ﬁeld of research only recently. For instances with additive valuations, where vi(A) = P j A vij for every i N, in a series of papers (Cole et al. 2017; Cole and Gkatzelis 2018; Anari et al. 2017; Barman, Krishnamurthy, and Vaish 2018a) several algorithms with constant approximation factors were obtained. The currently best factor is e1/e 1.445 (Barman, Krishnamurthy, and Vaish 2018a). The algorithm uses prices and techniques inspired by competitive equilibria, along with suitable rounding of valuations to guarantee polynomial running time. Even for identical additive valuations, (i.e., vij = vj for all i N, j G,) the problem is NP-hard, and a greedy algorithm with factor of 1.061 (Barman, Krishnamurthy, and Vaish 2018b) as well as a PTAS (Nguyen and Rothe 2014) were obtained. In terms of inapproximability, the best known lower bound for additive valuations is p

8/7 1.069 (Garg, Hoefer, and Mehlhorn 2018). Notably, this lower bound applies even in the case when the additive valuation is composed of only three values with one of them being 0 (i.e.,

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

vij {0, p, q} for all i N, j G, where p, q N). For the case of two values with one 0 (i.e., vij {0, q} for all i N, j G), an allocation maximizing the NSW can be computed in polynomial time (Barman, Krishnamurthy, and Vaish 2018b).

Contribution and Results. In this paper, we consider computing allocations with (near-)optimal NSW when every agent has a 2-value valuation. In such an instance, vij {p, q} for every i N and j G, where p, q N0. Notably, in 2-value instances any optimal allocation satisﬁes EFX, which is not true when agents have 3 or more values (Amanatidis et al. 2020). The case p = q is trivial. An optimal allocation can be computed in polynomial time when p = 0 < q (Barman, Krishnamurthy, and Vaish 2018b). Hence, we concentrate on the case 1 p < q. We design a polynomial-time algorithm to ﬁnd an optimal allocation when p divides q, i.e., after appropriate scaling, when p = 1 and q N. Even if p does not divide q, the algorithm still guarantees an approximation factor of at most 1.0345. This is signiﬁcantly lower than the constant factors obtained for general additive valuations (Cole et al. 2017; Cole and Gkatzelis 2018; Barman, Krishnamurthy, and Vaish 2018a). An approximation algorithm for 2-value instances with approximation factor 1.061 has been obtained in (Garg and Murhekar 2021). The algorithm is based on ideas from competitive equilibria. Our algorithm is a greedy procedure and improves this guarantee. Complementing these positive results, we also prove new hardness results for 2-value instances. Maximizing the NSW is NP-hard whenever p and q are coprime and p 3. Since for p = 1 we have a polynomial-time algorithm, p = 2 remains as an interesting open problem. Maximizing the NSW in 2-value instances is APX-hard. Our reduction from Gap4D-Matching avoids the use of utilities vij = 0, which poses a substantial technical challenge over the more direct reduction for 3-value instances in (Garg, Hoefer, and Mehlhorn 2018). Our lower bound on the approximation factor is 1.000015 for p/q = 4/5. This answers an open problem from (Amanatidis et al. 2020). Due to space constraints, all the missing proof can be found in the full version of the paper.

Related Work

Other than additive valuations, the design of approximation algorithms for maximizing NSW with submodular valuations has been subject to signiﬁcant progress very recently. While small constant approximation factors have been obtained for special cases (Garg, Hoefer, and Mehlhorn 2018; Anari et al. 2018) (such as a factor e1/e for capped additive-separable concave (Chaudhury et al. 2018) valuations), (rather high) constants for the approximation of NSW with Rado valuations (Garg, Husic, and V egh 2021) and also general non-negative, monotone submodular valuations (Li and Vondr ak 2021) have been obtained. Interestingly, for dichotomous submodular valuations where the marginal valuation of every agent for every good j has only one possible non-negative value (i.e., vi(S {j}) v(S) {0, p} for p N), an allocation maximizing the

NSW can be computed in polynomial time (Babaioff, Ezra, and Feige 2021). In particular, in this case one can ﬁnd in polynomial time an allocation that is Lorenz dominating, and simultaneously minimizes the lexicographic vector of valuations, and maximizes both utilitarian and Nash social welfare. Moreover, this allocation also has favorable incentive properties in terms of misreporting of agents. More generally, approximation algorithms for maximizing NSW with subadditive valuations (Barman et al. 2020; Chaudhury, Garg, and Mehta 2021) and asymmetric agents (Garg, Kulkarni, and Kulkarni 2020) have been obtained, albeit so far not with constant approximation ratios.

Preliminaries An instance I is given by the triple (N, G, {vi}i N ) where N is a set of n agents and G is a set of m indivisible goods. Every agent i N has an additive valuation function with vi(A) = P j A vij for every A G. Here vij represents the value i assigns to the good j G. We assume that all vij 0. In this paper, we study 2-value additive valuations, in which vij {p, q} for p, q N0. To avoid trivialities, we assume 0 < p < q. Note that for p = 0 we recover the dichotomous case studied in (Barman, Krishnamurthy, and Vaish 2018b; Babaioff, Ezra, and Feige 2021). We scale down the valuation of every agent by q such that vij {v, 1} where 0 < v = p/q < 1. Moreover, throughout the paper we assume p and q are coprime. An allocation A = (A1, . . . , An) is a partition of G among the agents, where Ai Aj = , for each i = j, and S i N Ai = G. We evaluate an allocation using the Nash

social welfare NSW(A) = Q i N vi(Ai) 1

n . Notice that there might exist allocations with NSW = 0, however, not all such allocations have to be considered equal. In particular, among these allocations, the ones maximizing the number of agents with non-empty bundles are more preferable. Hence, for same number agents with nonempty bundles, the higher is NSW restricted on these agents the better is the allocation. In this scenario, to do not overload our notation, while comparing two allocations with 0 NSW, we say one has better NSW than the other if satisﬁes the aforementioned conditions. Further, when m < n, it is always possible to compute an optimal allocation in this sense; hence, in the rest of this paper, we assume m n. We represent every valuation by distinguishing between big and small goods for agents. We use sets Bi = {j | vij = 1} and Si = G \Bi to denote the subsets of goods that agent i considers as big and small, respectively. If not differently speciﬁed, whenever we say agent i has a small (resp. big) good it means that it is a small (resp. big) for i. Globally, we use B = S i Bi and S = T i Si = G \B for the sets of goods that are big for at least one agent or small for all agents, respectively. As such, an instance I with 2-value additive valuations can be fully described by (N, G, (Bi)i N , v). Of particular interest will be non-wasteful allocations (c.f. (Babaioff, Ezra, and Feige 2021)), in which we only assign the goods from B and give them to agents that value them as big goods. Formally, a non-wasteful allocation Ab = (Ab 1, . . . , Ab n) has Ab i Bi and S Ab i = B.

Comparing Optimal Allocations. In our analysis, we often compare optimal allocations for 2-value valuations to optimal allocations for the same 2-value valuations with v replaced by 0. Given a fair allocation instance I, we denote by O an optimal allocation and NSW(O ) the NSW of an optimal allocation. Similarly, for any I we consider a corresponding dichotomous instance I(d) = (N, B, {v(d) i }i N ) obtained by setting v(d) ij = 0 for all i N, j Si. We use O to denote an optimal allocation in the dichotomous instance I(d). In particular, if we cannot assign a big good to every agent in I(d), we assume O assigns a big good to as many agents as possible, and it maximizes the NSW among this set of agents. Note that we assume the goods in S that are small for all agents are never assigned in O, and as such we exclude them from consideration in I(d). Clearly, O will be a non-wasteful allocation. In O , by Pareto-optimality, each good must be assigned to an agent. However, for any agent i, the set of big goods in Oi might not be a superset of the set of big goods in O i . We denote by bi = |Bi Oi| and by b i = |Bi O i | the number of big goods agent i is receiving in O and O , respectively. Also, b and b are used to represent the vectors of bi and b i , respectively.

Example 1. Let I be a fair allocation instance with n = 2 agents, m = 5 goods, and v = 2/3. All agents have identical valuations. There are two big goods and three small goods. Then only two optimal allocations exist (with NSW = 2) obtained by assigning all big goods to one agent and all small goods to the other. However, for v = 0, every optimal allocation assigns each agent one big good.

In general, there is no simple direct connection between O and O , not even between vectors b and b . Nonetheless, it is possible to choose O in such a way it is, to some extent, the closest to a given O. Hence, in order to simplify our proofs, we will assume that N is numbered in nonincreasing order of bi s and subject to that in non-increasing order of b i s, i.e., for i, j N, if bi < bj, or bi = bj and b i < b j, then j < i. There can be many optimal solutions O . For a rigorous reasoning we pick O based on a hierarchy of three criteria based on a ﬁxed O: (1) O maximizes the NSW (i.e., it is optimal); among all these solutions it (2) maximizes the overlap in big goods P i N |Oi O i | (i.e., it is sum-closest to O); among all these solutions it (3) maximizes lexicographically (|Oi O i |)i N (i.e., it is sum-lexclosest to O). Condition (3) is tied to the ordering of the agents, for which the tie-breaking in turn depends on O . Tie-breaking and lexicographic maximization allow a consistent choice of O , since both aim to maximize the number of big goods in O for agents with small index. Given this choice of O , we capture the relation to O in a structured way using the notion of a transformation graph. Let A and A be two possible allocations. We denote by GA A the transformation graph from allocation A to allocation A . More formally, GA A = (N, EA A ) is a directed multigraph, where N is the set of the vertices. Each edge e = (i, j) EA A corresponds to some good k Ai A j and vice versa. Observe that a transforma-

tion graph is well deﬁned when the allocations A and A are partial allocations, i.e., not all the goods have been allocated. We use the notation g(e) = k. Observe that GA A can be obtained by simply reversing all the directed edges in GA A . A path in GA A can be seen as a sequence of goods (g(e1), g(e2), . . . , g(ek 1)) such that ej = (ij, ij+1) and g(ej) Aij A ij+1 for all j = 1, . . . , k 1. We say we trade (goods along) a path if we remove g(ej) from Aij and add it in Aij+1, for each j = 1, . . . , k 1. Moreover, we say that a path is a balancing path if after trade the utilities of the interior agents remain unchanged, i.e., vij(g(ej)) = vij(g(ej 1)), for each j = 2, . . . , k 1. Observe that every edge in the transformation graph is a balancing path; moreover, every path contained in a balancing path is a balancing path as well. In general, there exist four types of balancing paths. A small-to-big or SB-balancing path is a balancing path (g(e1), g(e2), . . . , g(ek 1)), where g(e1) Si1 and g(ek 1) Bik. BS/SS/BB-balancing paths are deﬁned accordingly. Finally, we will brieﬂy pay attention to BB-balancing paths starting and ending at the same agent we term them balancing cycles (and omit the preﬁx BB, since clear from context).

Preliminaries on O, O , and GO O. Given the pair of allocations O and O with vectors b and b for the numbers of big goods, the next lemmas reveal some interesting structure of GO O. Notice that by the properties of O and O described above, the graph GO O neither has SSnor BS-balancing paths. Moreover, it has no balancing cycles, since O is optimal and sum-closest to O. We are particularly interested in all agents, for which the number of big goods assigned in O and O differ. These agents are inherently connected to each other in the transformation graph. Lemma 1. For every agent i with b i > bi there is an agent j with b j < bj such that in GO O there is a BB-balancing path from i to j. Lemma 2. For every agent j with b j < bj there is an agent i

1. such that in GO O there is an SB-balancing path from i to j, or 2. with b i > bi such that in GO O there is a BBbalancing path from i to j.

An Optimal Algorithm when p Divides q Consider algorithm TWOVALUEAPPROX. In phase 1, it computes O, an optimal allocation in the corresponding dichotomous instance I(d). This can be done in polynomial time (Barman, Krishnamurthy, and Vaish 2018b). Note that after phase 1, there can be agents with empty bundles. Then we assume O maximizes the number of agents receiving at least one good. Moreover, restricting attention to the set of agents with nonempty bundles, O maximizes the NSW among them. It is easy to see that an allocation O with this property is computed both by the algorithm for dichotomous additive instances in (Barman, Krishnamurthy, and Vaish 2018b) and its generalization to dichotomous submodular ones in (Babaioff, Ezra, and Feige 2021). For phases 2 and 3, the algorithm calls procedure BALANCE. In phase 2, if there exist unassigned goods (i.e., goods

Algorithm 1: Algorithm TWOVALUEAPPROX

Input: A fair allocation instance I = (N, G, (Bi)i N , v) Output: An allocation A = (A1, . . . , An) /* Phase 1: Find optimal allocation for dichotomous instance */

1 Compute an optimal allocation O = (O1, . . . , On) for I(d) for goods in B /* Phases 2 and 3 */

2 A BALANCE(I, O)

Algorithm 2: Algorithm BALANCE

Input: A fair allocation instance I = (N, G, (Bi)i N , v) and a non-wasteful allocation Ab = (Ab 1, . . . , Ab n) (i.e. with Ab i Bi and S Ab i = B) Output: An allocation A = (A1, . . . , An) of all goods in G /* Phase 2: Adding only-small valued goods */

1 Let Ai = Ab i for all i N;

2 while there exists g S do

3 i = arg minj vj(Aj)

4 Ai Ai {g} and S S \ {g} /* Phase 3: Local search */

5 i1 = arg maxj vj(Aj) and i2 = arg minj vj(Aj)

6 while moving a good g Ai1 to Ai2 strictly increases NSW(A) do

7 Ai1 Ai1 \ {g} and Ai2 Ai2 {g}

8 i1 = arg maxj vj(Aj) and i2 = arg minj vj(Aj)

that are small for all agents), they get assigned sequentially to an agent with the currently smallest valuation. Finally, in phase 3, big goods received by the agents may be reallocated and turned into small ones. In particular, we greedily move a big good from the agent with the highest valuation to an agent with the smallest valuation if and only if this move increases the NSW. Observe that if the current allocation has NSW = 0, moving one good to an empty bundle is considered proﬁtable for the NSW as long as the number of agents with non-empty bundle increases.

Running Time. To bound the running time, we start by proving a lemma about properties of phases 2 and 3 of the algorithm. We denote by it 1 and it 2 the agents i1 and i2 in round t of phase 3.

Lemma 3. The following properties hold during the execution of BALANCE(I, O):

Every agent i with small goods has a valuation of at most vi(Ai) minj N vj(Aj) + v. If a move in round t of phase 3 strictly increases the NSW, then (1) it 1 only has big goods, (2) we never moved a good

away from agent it 2 during earlier rounds 1, . . . , t 1 of phase 3, and (3) none of the goods g Ait 1 is big for it 2.

Algorithm TWOVALUEAPPROX runs in polynomial time: Phase 1 runs in polynomial time (Barman, Krishnamurthy, and Vaish 2018b), and Lemma 3 shows that BALANCE(I, O) (re-)allocates each good at most once.

Optimality. Let us now focus on the Nash social welfare of the ﬁnal allocation. We show that the algorithm computes an optimal allocation when p divides q, i.e., when p = 1 and q N (after scaling valuations). In this case, an integer number of small goods are exactly as valuable as a big one. This fact will be key to show the main result in this section. Theorem 1. If p = 1 and q N, then TWOVALUEAPPROX computes an optimal allocation in polynomial time. Proposition 1 is the ﬁrst step toward proving the theorem. It implies that BALANCE(I, O) maintains an optimal assignment for a ﬁxed number of big goods assigned to each of the agents. Towards this end, consider a partial bigallocation AP such that AP i Bi for all i N, i.e., in AP

all agents only receive big goods. Since AP is partial, there might be unassigned goods GU = G \ S i AP i . Now consider a small-extension A of AP obtained by assigning each good g GU to some agent i with g Si. Note that if a good g GU is big for all agents, then AP does not have any small-extension. We use the notation si = |Ai Si|. Proposition 1. If for all pairs i, j that satisfy vi(Ai) + v < vj(Aj) we have sj = 0, then A is a small-extension of AP with maximum NSW.

Proof. Assume by contradiction that A is not the best smallextension of AP . Let A be a small-extension of AP with largest NSW that is sum-lex-closest to A (i.e., maximizes P i N |Ai A i |). We deﬁne s i = |A i Si|. If A is not optimal, then there exists i N such that si < s i . Thus, there must be an SS-balancing path in GA A from i to j with s j < sj. Observe that sj > 0. Hence, there exists a way to trade along the path without changing the valuation of interior agents. Since A is an optimal small-extension that is sum-lex-closest to A, this must be strictly proﬁtable, so vi(A i ) vj(A j) > (vi(A i ) v) vj(A j) + v . Then, since v > 0, this is equivalent to vj(A j)+v > vi(A i ). Since Ai Bi = A i Bi = AP i and Aj Bj = A j Bj = AP j , we see that vj(A j) vj(Aj) v and vi(A i ) vi(Ai)+v. Putting it all together we get vj(Aj) v j (A j) + v > vi(A i ) vi(Ai) + v. However, we have sj > 0, a contradiction to the assumption of A in the lemma.

We observed in Lemma 3 that throughout BALANCE(I, O), all agents receiving small goods differ in valuation by at most v. This implies that when vi(Ai) + v < vj(Aj) at any point during the algorithm, then sj = 0, i.e., j has no small goods. For the next proposition, we assume BALANCE(I, ) is applied to a particular form of non-wasteful allocation, which will eventually result in an optimal allocation. Recall that numbers bi and b i refer to the number of big goods that agent i receives in allocations O and O , respectively, and

that agents are numbered in non-increasing order of their valuation in O and then in O , i.e., if i j, then (bi > bj) or (bi = bj and b i b j).

Deﬁnition 1. An allocation O is said to be well-structured if it is non-wasteful and there is some value 0 K n s.t.

b = (b1, . . . , b K, b K+1, . . . , b n), for each i K either bi > b i , or bi = b i and there is j K with bj > b j and b j < b i , for each i K and j > K, b i b j.

Proposition 2. Let O be any well-structured allocation. Then BALANCE(I, O) computes an optimal allocation.

Proof. We denote by m = PK i=1 bi PK i=1 b i the number of goods from B assigned as small in O . We start with some structural observations. Suppose we remove an arbitrary set G of m goods from S i K Oi in such a way that the numbers of the remaining big goods for agents i K are a permutation of (b 1, . . . , b K). We then assign the goods in S G sequentially to an agent with the currently lowest valuation. Moreover, let us pretend for the moment that the goods in S G are small for all the agents, that means, we increase the valuation of the agents receiving them by v. By Proposition 1, this will lead to an optimal small-extension and, since we start from a partial allocation inducing a permutation of (b 1, . . . , b K), this must be an allocation with maximum NSW. This has several implications:

1. The goods in this process are indeed small for any agent receiving it. Otherwise, the allocation could be Paretoimproved, contradicting the optimality of O . 2. All small goods in O are allocated to agents i with i > K. For contradiction, suppose agent i K receives a small good. As the small goods were allocated in turn to an agent with minimum valuation, we can assume that i has mink K b k big goods. Thus i must have given some big good away. Then exchanging this good with the small one Pareto-improves the allocation, contradicting the optimality of the allocation.

We now show that BALANCE indeed removes a set G of m goods as described above. If m = 0, the statement is trivial and the proposition follows. We denote by Ot the allocation after the t-th round in BALANCE (counting both phases 2 and 3) and bt the vector of big goods. We will show inductively that (1) in every round the number of big goods remain above O , i.e., there is a permutation σ of {1, . . . , K} such that b σ(i) bt i for all i K; and (2) in phase 3 the agent with highest valuation is an i K. As the base case, consider t = 0 before the start of phase 2. Clearly, (1) and (2) hold by assumption. Suppose both properties hold until the end of some round t < m + |S| 1. Consider round t + 1. By hypothesis there is a permutation σ such that b σ(i) bt i for all i K and P i N bt i > P i N b i . This implies that Ot is sum-closer to O than O , hence cannot be optimal. Moreover, there is i < K such that bt i > b σ(i). If for all j K we remove

bt j b σ(j) goods and assign them iteratively to the leastvaluation agents k > K, the NSW becomes optimal and thus strictly improves. This implies that after round t there is a move improving the NSW, so BALANCE will not terminate since it would execute another round of phase 3. Now consider i as the highest-valuation agent at the end of round t. By (2) this is an agent i K. Suppose round t + 1 is in phase 2. Then σ still ﬁts, and (1) holds after round t + 1. Suppose (2) does not hold, i.e., after round t+1 an agent j > K has highest valuation. This agent must have received the small good in round t+1, so the valuations of all agents differ by at most v. Hence, phase 3 would not start if phase 2 ended after round t + 1. However, since there is at least one agent k K with b σ(k) < bt k, we proved above phase 3 would start after round t + 1, a contradiction. Now suppose round t + 1 is in phase 3. If b σ(i) < bt i, then

σ still ﬁts, so let us assume that b σ(i) = bt i. If there is j K

such that bt j = bt i and b σ(j) < bt j, then (i, j) σ works.

Let us assume that all agents with maximum valuation in Ot

have as many goods as in O . We have bt+1 i < b σ(i) and P j K b j P j K bt+1 j (because t + 1 m ), so there is j K such that b σ(j) < bt+1 j . Since j cannot have maxi-

mum valuation in Ot, so bt+1 j bt+1 i . Consider the allocation where every k K gives away max(0, bt+1 k b σ(k))

goods, except j that gives bt+1 j b σ(j) 1 goods. This allocation differs in valuation proﬁle from O only by agents i and j (up to a permutation) and we have b σ(j) < bt+1 j bt+1 i b σ(i), so this new allocation has higher NSW than O , a contradiction to the optimality of O . This proves that (1) holds after round t + 1. Suppose (2) does not hold, i.e., there is an agent j > K with highest valuation. This agent must have a small good, since b i b j for all i K, j > K. Hence, at the end of round t + 1, the valuations of all agents differ by at most v, and there is no improving move left for round t + 2. If t + 1 < m + |S| we have an agent k K with b σ(k) < bt k, and BALANCE will execute another round in phase 3, a contradiction. Note that the good moved in round t + 1 must be given to an agent j > K even if we expanded the set of goods removed from agents 1, . . . , K from the ones in rounds 1, . . . , t + 1 to a set G of goods considered above, all goods would be given only to agents j > K. Finally, we consider the case t = m + |S| 1. Then after round t + 1, we obtain a permutation σ of {1, . . . , K} such that b σ(i) bm i for all i K. We also have P i K bm +|S| i = P i K bi m = P i K b i . Hence, bm +|S| i = b i for all i K. Thus, the set of removed goods is a set G considered above, and as such the resulting allocation Om |S| is optimal. As a consequence, BALANCE stops after this iteration and returns an optimal allocation.

The proposition shows that if the allocation computed in phase 1 has suitable properties, then the allocation computed by BALANCE is an optimal one. We now further compare O and O to better understand why the hypothesis of Proposition 2 is not always satisﬁed by O and which conditions on v = p/q are sufﬁcient for it. In O the big goods are as evenly balanced as possible. When v = 0, an optimal allocation O might require to make the big goods more unbalanced. In the next proposition, we examine the details of this observation. In case 1 v N, we observe that Proposition 2 holds, and thus Algorithm 1 computes an optimal allocation. Recall that we assume agents to be numbered in non-increasing order of bi. The following proposition holds even when O is optimal and sum-closest to O (but not necessarily sum-lex-closest).

Proposition 3. Suppose O is optimal and sum-closest to O and there is an agent i such that bi < b i . Consider an agent j such that b j < bj and there is a BB-balancing path in GO O from i to j. Then vi(O i ) 1 + v 1

v < vj(O j ) < vi(O i ) 1 + v 1

v , bj bi + 1, and bj b i .

Proof. For k N, we denote by s k = |O k Sk| the number of goods of k that are small to k. As O is optimal, trading along a BB-balancing path in GO O from i to j cannot increase the NSW, i.e. vi(O i ) vj(O j ) (vi(O i ) 1) (vj(O j )+1) and, hence, vi(O i ) vj(O j ) + 1, leading to the optimality condition b i + vs i b j + vs j + 1. Besides, if j has a good that is big to i, then either there is a balancing cycle, which contradicts the fact that O is closest to O, or the good is small for j and trading along the cycle gives a new allocation that Pareto-dominates O . So none of the goods of j is considered big by i. We ﬁrst show that bj bi + 1. Suppose for contradiction that this is not the case. Then by reversing the path between i and j and trading goods, we see that O is not optimal in the dichotomous instance. Next we show b i b j 2 and bj b i . If bj bi, then b j < bj bi < b i and since these numbers are integers we obtain b i b j 2, as well as bj b i . Thus, we are left with the case bj = bi + 1. We have b j bi and bj b i , and thus the following inequalities: b j bi = bj 1 b i 1. If one of the inequalities is strict, then we obtain b j b i 2 and bj b i . Otherwise, b j = bi and bj = b i . Then the optimality condition gives s i s j. Now we trade along the path. Thereby we assign a big good to j. In exchange, agent i receives s j s i many small goods from j s bundle. This exchanges vi(O i ) and vj(O j ), and thus does not impact the NSW. This contradicts the fact that O is closest to O. Having shown that b i b j 2, we see with the optimality condition that s j s i 1

v. We prove by contradiction that the relation between vj(O j ) and vi(O i ) holds. Assume vj(O j ) vi(O i ) 1 + v 1

v . Then vi(O i ) vj(O j ) (vi(O i ) 1+v 1

v )(vj(O j )+1 v 1

v ), which means that trading along the path from i to j and transferring 1

v small goods from O j to Oi does not decrease the NSW of the allocation. This is impossible because O was taken as close to O as possible.

Now, if vj(O j ) vi(O i ) 1 + v 1

v , then vi(O i ) vj(O j ) (vi(O i ) 1+v 1

v )(vj(O j )+1 v 1

v ) and same reasoning applies by using 1

v small goods.

We can now prove Theorem 1.

Proof of Theorem 1. We show that BALANCE(I, O) is an optimal allocation. To this aim we show that O satisﬁes the assumptions of Proposition 2. We ﬁrst observe that if 1

v N, then there exists no agent i such that bi < b i . Otherwise, by Lemma 1 and Proposition 3, vi(O i ) 1+v 1

v < vj(O j ) < vi(O i ) 1+v 1

v for some j. Since, 1

v N, we have 1

v implying vi(O i ) < vj(O j ) + 1 v 1

v < vi(O i ) which is impossible. Thus, for each i N, bi b i . Moreover, the entries of b are sorted in non-increasing order. By selecting K as the maximum index i {0, . . . , n} for which bi > b i , we see that O is well-structured. Therefore, by Proposition 2, BALANCE(I, O) returns an optimal allocation.

Approximation In this section we study the case 1

v N and prove a small approximation ratio for our algorithm. The idea is to compare the behavior of BALANCE(I, O) to BALANCE(I, O) for a suitably chosen allocation O such that the ﬁnal allocation of the latter procedure is optimal. In the following, we discuss a high-level description of the arguments. We transform O into an allocation O by moving each good from B that is assigned as small in O to the agent that owns it in O and removing all goods of S from the agents bundles. The obtained allocation O has the corresponding vector of big goods b such that for each i N either bi = bi or bi = b i . In particular, the vector b can be written as (b1, . . . , b K, b K+1, . . . , b n), for some index 0 K n. We set K to the largest index such that i K we have bi = bi > b i , or bi = b i and there is j K such that bj = bj > b j and b j < b i . If there is no such index, we simply set K = 0. Intuitively, we choose K as the largest index such that O qualiﬁes as a well-structured allocation in the sense of Deﬁnition 1. Hence, by Proposition 2, we have that BALANCE(I, O) returns an optimal allocation. Suppose we run BALANCE(I, O). Let Ot denote the allocation after t time steps, and let T be the last step before BALANCE(I, O) terminates. By the choice of O, the allocation O T is an optimal allocation (possibly different from O ). BALANCE moves big goods from agents i K and assigns them as small to agents j > K as long as it is strictly proﬁtable for the NSW. Hence, for every agent j > K the number of big goods stays the same during the procedure. In O T , every agent j > K has b j big goods, while, for agents i K, the numbers of big goods can be different from b i . To show the approximation factor of our algorithm, we relate O T to the output of our algorithm, i.e., the output of BALANCE(I, O) to the one of BALANCE(I, O). For this purpose, we track the allocations in BALANCE(I, O) and simultaneously apply them on O. Let Ot denote the allocation

after t time steps. We couple the changes to big goods in Ot and Ot in the following way: 1. In a step t of phase 2, a globally small good from S is added to both Ot and Ot. It is given to an agent with the current smallest valuation in the respective allocation. 2. In a step t of phase 3, in which a big good is removed from the bundle of agent i K in Ot, we also remove one big good from i s bundle in Ot. The good is given to an agent with the current smallest valuation in the respective allocation. Note that we couple the removal of the big good, but as small it gets assigned to potentially different agents in Ot and Ot. Let T be the ﬁnal step of BALANCE(I, O). Observe that in every step t T, we can assume that the coupled process on O behaves exactly like BALANCE(I, O). However, it might be that T = T. Then, if T > T, the coupled process forces BALANCE(I, O) to continue turning big goods into small ones although this is not proﬁtable for the NSW. We also observe that, if i is the agent with current lowest valuation in O T , then she will receive a small good. More generally, we show that for any t < T: 1. no agent i K has a minimum valuation in Ot, 2. no agent j > K receives big goods, 3. no agent i > K has a maximum valuation in Ot . These properties also lead to the following result.

Lemma 4. NSW(O T ) NSW(OT ). As a consequence, we can upper-bound the approximation factor of our algorithm by NSW( O T )/NSW(O T ). Finally, to bound the approximation factor of Algorithm 1, we show that we can partition the agents into two groups. In one group, the agents have the same valuation in O T and O T . In the other, the following properties are satisﬁed: 1) the utilitarian social welfare and, in particular, the number of goods assigned as big/small is the same 2) in O T valuations of any pair of agents differ by at most v. The properties sufﬁce to prove the main result of this section. Theorem 2. Algorithm 1 has an approximation factor of at most 24

493 < 1.0345. Observe that Example 1 provides a lower bound to Algorithm 1 of 1.01418. It is an interesting open problem whether the approximation of Algorithm 1 can be tight.

NP-Hardness when p 3 In this section we almost complement our positive results on polynomial-time NSW optimization. In particular, we show: Theorem 3. No polynomial-time algorithm computes an allocation with optimal NSW for 2-value instances, for any coprime integers q > p 3, unless P=NP. We provide a reduction from Exact-p-Dimensional Matching (Ex-p-DM): Given a graph G consisting of p disjoint vertex sets V1, . . . , Vp, each of size n, and a set E V1 . . . Vp of m edges, it is NP-hard to decide whether there exists a p-dimensional perfect matching in G or not.

Note that for p = 3 the problem is Ex-3-DM and thus NPhard. NP-hardness for p > 3 follows by simply copying the third set of vertices in the Ex-3-DM instance p 3 times, thereby also extending the edges to the new vertex sets.

Reduction: There is one good for each vertex of G, call them vertex goods. Additionally, there are q(m n) dummy goods. For each edge of G, there is one agent who values the p incident vertex goods 1 and all other goods p/q.

Lemma 5. If G has a perfect matching, then there is an allocation A of goods with NSW(A) = p.

Proof. Suppose there exists a perfect matching in G. We allocate the goods as follows: Give each agent corresponding to a matching edge all p incident vertex goods. Now there are m n agents left. Give each of them q dummy goods. As each agent has valuation p, the NSW is p as well.

Lemma 6. If G has no perfect matching, then for every allocation A of goods, NSW(A) < p.

Proof. Suppose there is an allocation A = (A1, . . . , Am) of goods with NSW(A) p. We show that in this case there must be a perfect matching in G. First, observe that if we allocate each good to an agent with maximal value for it, we obtain an upper bound on the average utilitarian social welfare of A, i.e. 1

m P i vi(Ai) 1

m(pn+q(m n) p

q ) = p. Applying the AM-GM inequality gives us also NSW(A) = (Q i vi(Ai))1/m p, and, in particular, NSW(A) = p iff vi(Ai) = p for all agents i. Hence each agents valuation must be p in A and each vertex good must be allocated to an incident agent. The next claim allows to conclude that there are only two types of agents in A:

Claim. If an agent i has valuation vi(Ai) = p, then she either gets her p incident vertex goods or q other goods.

We show that (p, 0) and (0, q) are the only integral solutions (i, j) of the equation p = i + j p

q , where i, j 0. Clearly, every solution different from the above must satisfy 0 < i < p. Assume for contradiction that there exists such a solution. Then it must hold (p i)q = jp. Since p and q are coprime, p i must be a multiple of p and thus i {0, p}, a contradiction. This concludes the proof of the claim. Let b be the number of agents receiving their p incident vertex goods in A, and m b the number of agents receiving q other goods. Since each vertex good must be allocated to an incident agent, bp = np and thus b = n. Hence there must be n agents receiving their p incident vertex goods, which implies that there is a perfect matching in G.

Lemma 5 and Lemma 6 yield the proof of Theorem 3. Using a similar reduction (with slightly different number of dummy goods), we provide a gap-preserving reduction from Gap-4D-Matching with almost perfect completeness to get the following APX-hardness result.

Theorem 4. No polynomial-time algorithm approximates the maximum NSW for 2-value instances to within a factor better than 1.000015, unless P=NP.

Acknowledgements MH and GV were supported by DFG grant Ho 3831/5-1.

References Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; Hollender, A.; and Voudouris, A. 2020. Maximum Nash welfare and other stories about EFX. In Proc. 29th Int. Joint Conf. Artif. Intell. (IJCAI), 24 30. Anari, N.; Gharan, S. O.; Saberi, A.; and Singh, M. 2017. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In Proc. 8th Symp. Innov. Theoret. Comput. Sci. (ITCS). Anari, N.; Mai, T.; Gharan, S. O.; and Vazirani, V. 2018. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. In Proc. 29th Symp. Discret. Algorithms (SODA), 2274 2290. Babaioff, M.; Ezra, T.; and Feige, U. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. In Proc. 35th Conf. Artif. Intell. (AAAI), 5119 5126. Barman, S.; Bhaskar, U.; Krishna, A.; and Sundaram, R. 2020. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. In Proc. 28th European Symp. Algorithms (ESA), 11:1 11:17. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018a. Finding Fair and Efﬁcient Allocations. In Proc. 19th Conf. Econ. Comput. (EC), 557 574. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018b. Greedy Algorithms for Maximizing Nash Social Welfare. In Proc. 17th Conf. Auton. Agents and Multi-Agent Syst. (AAMAS), 7 13. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A.; Shah, N.; and Wang, J. 2016. The unreasonable fairness of maximum Nash welfare. In Proc. 17th Conf. Econ. Comput. (EC), 305 322. Chaudhury, B.; Cheung, Y. K.; Garg, J.; Garg, N.; Hoefer, M.; and Mehlhorn, K. 2018. On Fair Division for Indivisible Items. In Proc. 38th Conf. Found. Software Tech. Theor. Comput. Sci. (FSTTCS), 25:1 25:17. Chaudhury, B. R.; Garg, J.; and Mehta, R. 2021. Fair and Efﬁcient Allocations under Subadditive Valuations. In Proc. 35th Conf. Artif. Intell. (AAAI), 5269 5276. 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. Econ. Comput. (EC), 459 460. Cole, R.; and Gkatzelis, V. 2018. Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput., 47(3): 1211 1236. Garg, J.; Hoefer, M.; and Mehlhorn, K. 2018. Approximating the Nash Social Welfare with Budget-Additive Valuations. In Proc. 29th Symp. Discret. Algorithms (SODA), 2326 2340. Garg, J.; Husic, E.; and V egh, L. 2021. Approximating Nash social welfare under Rado valuations. In Proc. 53rd Symp. Theory Comput. (STOC), 1412 1425.

Garg, J.; Kulkarni, P.; and Kulkarni, R. 2020. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. In Proc. 31st Symp. Discret. Algorithms (SODA), 2673 2687. Garg, J.; and Murhekar, A. 2021. Computing Fair and Efﬁcient Allocations with Few Utility Values. In Proc. 14th Symp. Algorithmic Game Theory (SAGT). Li, W.; and Vondr ak, J. 2021. A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. In Proc. 62nd Symp. Found. Comput. Sci. (FOCS). To appear. Lipton, R.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proc. 5th Conf. Electr. 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. Discret. Appl. Math., 179(31): 54 68.