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

This is the authors' abstract. We don't add key points for this paper.

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G G , and n agents, A A , where each agent i ∈ A i ∈ A has a valuation vᵢⱼ≥ 0 v ij ≥ 0 for each item j∈ G j ∈ G . In addition, every agent i has a non-negative weight wᵢ w i such that the weights collectively sum up to 1. The goal is to find an assignment σ :G→ A σ : G → A that maximizes ∏ i∈ A ( ∑ _j∈ σ ⁻¹(i) vᵢⱼ) wᵢ ∏ i ∈ A ∑ j ∈ σ - 1 ( i ) v ij w i , the product of the weighted valuations of the players. When all the weights equal 1/n 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· DKL(w\, ||\, 1⃗n)) = 5· exp ( 2log n + 2∑ ᵢ₌₁ⁿ wᵢ log wᵢ) 5 · exp 2 · D KL ( w | | 1 → n ) = 5 · exp