Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i ∈ A has a valuation v ij ≥ 0 for each item j ∈ G. In addition, every agent i has a non-negative weight w i such that the weights collectively sum up to 1. The goal is to find an assignment σ : G → A that maximizes

, the product of the weighted valuations of the players. When all the weights equal 1 n , the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present a 5 • exp 2

i=1 w i log w i )-approximation algorithm for the weighted Nash Social Wel- fare problem, where D KL (w || 1 n ) denotes the KL-divergence between the distribution induced by w and the uniform distribution on [n].

We show a novel connection between the convex programming relaxations for the unweighted variant of Nash Social Welfare presented in [CDG + 17, AGSS17], and generalize the programs to two different mathematical programs for the weighted case. The first program is convex and is necessary for computational efficiency, while the second program is a nonconvex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation.