@article{1d76f61c3c154427b5696cf7622b7538,
title = "Nash Social Welfare Approximation for Strategic Agents",
abstract = "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.",
keywords = "Nash social welfare, Price of anarchy, Trading post",
author = "Simina Br{\^a}nzei and Vasilis Gkatzelis and Ruta Mehta",
note = "Funding Information: This project has received funding from the European Research Council under the European Union's H2020 European Research Council Research and Innovation Programme [Grant 740282]. S. Br{\^a}nzei was supported in part by the Israel Science Foundation [Grant 1435/14] administered by the Israeli Academy of Sciences and by the United States-Israel Binational Science Foundation [Grant 2014389]. V. Gkatzelis was supported by the Division of Computing and Communication Foundations [Grants 1408635, 1216073, and 1161813] and by the National Science Foundation [Grant CCF-175595]. R. Mehta was supported by the National Science Foundation [CAREER Grant CCF-1750436]. This work was done in part while the authors were research fellows at the Simons Institute for the Theory of Computing. An earlier version of some of the results of this paper appeared at the Association for Computing Machinery Conference in Economics and Computation (Br{\^a}nzei et al. 2017). Funding Information: Funding: This project has received funding from the European Research Council under the European Union{\textquoteright}s H2020 European Research Council Research and Innovation Programme [Grant 740282]. S. Br{\^a}nzei was supported in part by the Israel Science Foundation [Grant 1435/14] administered by the Israeli Academy of Sciences and by the United States-Israel Binational Science Foundation [Grant 2014389]. V. Gkatzelis was supported by the Division of Computing and Communication Foundations [Grants 1408635, 1216073, and 1161813] and by the National Science Foundation [Grant CCF-175595]. R. Mehta was supported by the National Science Foundation [CAREER Grant CCF-1750436]. Publisher Copyright: {\textcopyright} 2021 INFORMS",
year = "2022",
month = jan,
day = "1",
doi = "10.1287/OPRE.2020.2056",
language = "English (US)",
volume = "70",
pages = "402--415",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",
}