Convex program duality, fisher markets, and nash social welfare

Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, Sadra Yazdanbod

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages459-460
Number of pages2
ISBN (Electronic)9781450345279
DOIs
StatePublished - Jun 20 2017
Event18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States
Duration: Jun 26 2017Jun 30 2017

Publication series

NameEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation

Other

Other18th ACM Conference on Economics and Computation, EC 2017
CountryUnited States
CityCambridge
Period6/26/176/30/17

Keywords

  • Convex program duality
  • Fisher market
  • Nash social welfare

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Computational Mathematics
  • Economics and Econometrics

Fingerprint Dive into the research topics of 'Convex program duality, fisher markets, and nash social welfare'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Devanur, N. R., Gkatzelis, V., Jain, K., Mai, T., Vazirani, V. V., & Yazdanbod, S. (2017). Convex program duality, fisher markets, and nash social welfare. In EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation (pp. 459-460). (EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3033274.3085109