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

Abstract In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, $$\mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> , and n agents, $$\mathcal {A}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> , where each agent $$i \in \mathcal {A}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>A</mml:mi> </mml:mrow> </mml:math> has a valuation $$v_{ij}\ge 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>v</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> for each item $$j\in \mathcal {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>G</mml:mi> </mml:mrow> </mml:math> . In addition, every agent i has a non-negative weight $$w_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> such that the weights collectively sum up to 1. The goal is to find an assignment $$\sigma :\mathcal {G}\rightarrow \mathcal {A}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>:</mml:mo> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> <mml:mi>A</mml:mi> </mml:mrow> </mml:math> that maximizes $$\prod _{i\in \mathcal {A}} \left( \sum _{j\in \sigma ^{-1}(i)} v_{ij}\right) ^{w_i}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>∏</mml:mo> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>A</mml:mi> </mml:mrow> </mml:msub> <mml:msup> <mml:mfenced> <mml:msub> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mi>σ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:msub> <mml:msub> <mml:mi>v</mml:mi> <mml:mrow> <mml:mi>ij</mml:mi> </mml:mrow> </mml:msub> </mml:mfenced> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:msup> </mml:mrow> </mml:math> , the product of the weighted valuations of the players. When all the weights equal $$\frac{1}{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>n</mml:mi> </mml:mfrac> </mml:math> , 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) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>5</mml:mn> <mml:mo>·</mml:mo> <mml:mo>exp</mml:mo> <mml:mfenced> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:msub> <mml:mi>D</mml:mi> <mml:mtext>KL</mml:mtext> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>w</mml:mi> <mml:mspace/> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> <mml:mspace/> </mml:mrow> <mml:mfrac> <mml:mover> <mml:mn>1</mml:mn> <mml:mo>→</mml:mo> </mml:mover> <mml:mi>n</mml:mi> </mml:mfrac> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mfenced> <mml:mo>=</mml:mo> <mml:mn>5</mml:mn> <mml:mo>·</mml:mo> <mml:mo>exp</mml:mo>