Convex Program Duality, Fisher Markets, and Nash Social Welfare

Understand

We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results.

• In particular, we obtain: -- A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap.
• In contrast, the natural integer program has an unbounded integrality gap.
• -- An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2.