CombOpt Reading Group | Rian Neogi, Approximating Nash Social Welfare via stable polynomials

Abstract: In this talk, I will go through the paper of "Nash Social Welfare, Matrix Permanent, and Stable Polynomials" by Anari, Oveis Gharan, Saberi, Singh. We will consider the problem of allocating m items to n agents. Each agent has a value v_{ij} for item j. The goal is to construct an allocation A_1,...,A_n so as to maximize the Nash social welfare \prod_i \sum_{j in A_i} v_{ij}. We will prove a simple 1/e approximation for the problem.

The techniques involve proving a generalization of the Van Der Waerden theorem for bounding the permanent of a doubly-stochastic matrix. We setup a convex program relaxation of the problem. Using the aforementioned theorem, we show that a simple rounding procedure on the optimal solution of this program gives the 1/e-approximation.