Nash Social Welfare Approximation for Strategic Agents

Simina Brânzei, Vasilis Gkatzelis, Ruta Mehta

Research output: Contribution to journalArticlepeer-review


A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants' strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents' values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of two for concave utility functions and becomes essentially optimal for complements, where it can reach (1 + ϵ) for any (ϵ > 0). Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality.

Original languageEnglish (US)
Pages (from-to)402-415
Number of pages14
JournalOperations Research
Issue number1
StatePublished - Jan 1 2022


  • Nash social welfare
  • Price of anarchy
  • Trading post

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Nash Social Welfare Approximation for Strategic Agents'. Together they form a unique fingerprint.

Cite this