In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, \(\mathcal {G}\) , and n agents, \(\mathcal {A}\) , where each agent \(i \in \mathcal {A}\) has a valuation \(v_{ij}\ge 0\) for each item \(j\in \mathcal {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 \(\sigma :\mathcal {G}\rightarrow \mathcal {A}\) that maximizes \(\prod _{i\in \mathcal {A}} \left( \sum _{j\in \sigma ^{-1}(i)} v_{ij}\right) ^{w_i}\) , the product of the weighted valuations of the players. When all the weights equal \(\frac{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\cdot \exp \left( 2\cdot D_{\textrm{KL}}(\textbf{w}\, ||\, \frac{\vec {\textbf{1}}}{n})\right) = 5\cdot \exp \left( 2\log {n} + 2\sum _{i=1}^n w_i \log {w_i}\right) \) -approximation algorithm for the weighted Nash Social Welfare problem, where \(D_{\textrm{KL}}(\textbf{w}\, ||\, \frac{\vec {\textbf{1}}}{n})\) denotes the KL-divergence between the distribution induced by \(\textbf{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 [1, 10], 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 non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation.
