Convex program duality, fisher markets, and nash social welfare

The main focus of this paper is on the problem of maximizing the Nash social welfare (NSW). In particular, given a collection of indivisible goods that needs to be allocated to a set of agents, our goal is to compute an allocation that maximizes the geometric mean of the agents' utilities. This objective has been studied since the fifties, and is known to provide a natural balance between fairness and efficiency. For additive agent utilities, Cole and Gkatzelis [1] gave the first constant factor approximation algorithm. The natural integer program for maximizing the NSW in this setting is closely related to the Fisher market model: if we relax the integrality constraint of the allocation, i.e., assume that the the goods are divisible, this program reduces to the Eisenberg- Gale (EG) convex program, whose solutions correspond to market equilibria for the linear Fisher market. Therefore, a canonical approach for designing a NSW approximation algorithm would be to compute a fractional allocation via the EG program, and then "round" it to get an integral one. However, Cole and Gkatzelis observed that this program's integrality gap is unbounded, and they were forced to follow an unconventional approach in designing and analyzing their algorithm. This algorithm used an alternative fractional allocation, the spending-restricted (SR) equilibrium, and they had to come up with an independent upper bound of the optimal NSW in order to prove that the approximation factor is at most 2e1/e ≈ 2.89. The absence of a conventional analysis for this problem could be, in part, to blame for the lack of progress on important follow-up problems. For instance, the SR equilibrium introduces constraints that are incompatible with the EG program so, instead of a convex program, Cole and Gkatzelis had to use a complicated algorithm for computing this allocation. Generalizing such an algorithm and proving new upper bounds for the optimal NSW may be non-Trivial. In this paper we remove this obstacle by uncovering the underlying structure of the NSW problem and shedding new light on the results of Cole and Gkatzelis. Specifically, we propose a new integer program which, as we show, computes the optimal NSW allocation. More importantly, we prove that the relaxation of this program computes the SR equilibrium, and, quite surprisingly, we also show that the objective of this program happens to be precisely the upper bound that was used by Cole and Gkatzelis. As a result, this new integer program yields a convex program for computing the SR equilibrium and, unlike the standard program, it has an integrality gap that is bounded by 2.89. In addition to this, we provide a tight analysis of the algorithm of Cole and Gkatzelis to show that its approximation factor is 2, which also puts an upper bound of 2 on the integrality gap of the new program. Further, we prove a lower bound of e1/e ≈ 1.44 on the integrality gap.