TY - GEN
T1 - Nash social welfare approximation for strategic agents
AU - Brânzei, Simina
AU - Gkatzelis, Vasilis
AU - Mehta, Ruta
N1 - Funding Information:
Simina was supported by ISF grant 1435/14 administered by the Israeli Academy of Sciences and Israel-USA Bi-national Science Foundation (BSF) grant 2014389, and the I-CORE Program of the Planning and Budgeting Committee and The Israel Science Foundation. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 740282). Vasilis was supported by NSF grants CCF-1408635, CCF-1216073, and CCF-1161813. This work was done in part while the authors were research fellows at the Simons Institute for the Theory of Computing.
Publisher Copyright:
© 2017 ACM.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017/6/20
Y1 - 2017/6/20
N2 - The fair division of resources among strategic agents is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist mechanisms that can implement fair outcomes, despite the agents' strategic behavior. A fundamental objective function used for measuring the fairness of an allocation is the geometric mean of the agents' values, known as the Nash social welfare (NSW). This objective function is maximized by widely known solution concepts such as Nash bargaining and the competitive equilibrium with equal incomes. In this work we focus on the question of (approximately) implementing this objective. The starting point of our analysis is the Fisher market, a fundamental model of an economy, whose benchmark is precisely the (weighted) Nash social welfare. We begin by studying two extreme classes of valuations functions, namely perfect substitutes and perfect complements, and find that for perfect substitutes, the Fisher market mechanism yields a constant approximation: At most 2 and at least e 1 e (≈ 1.44). However, for perfect complements, the Fisher market mechanism does not work well, its bound degrading linearly with the number of players. Strikingly, the Trading Post mechanism-An indirect market mechanism also known as the Shapley-Shubik game-has significantly better performance than the Fisher market on its own benchmark. Not only does Trading Post achieve an approximation of 2 for perfect substitutes, but this bound holds for any concave utilities, and it becomes essentially optimal for perfect complements, where it reaches (1 +) for any ? > 0. Moreover, we show that all the Nash equilibria of the Trading Post mechanism are pure (hence the approximation factors extend to all Nash equilibria), and satisfy an important notion of individual fairness known as proportionality.
AB - The fair division of resources among strategic agents is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist mechanisms that can implement fair outcomes, despite the agents' strategic behavior. A fundamental objective function used for measuring the fairness of an allocation is the geometric mean of the agents' values, known as the Nash social welfare (NSW). This objective function is maximized by widely known solution concepts such as Nash bargaining and the competitive equilibrium with equal incomes. In this work we focus on the question of (approximately) implementing this objective. The starting point of our analysis is the Fisher market, a fundamental model of an economy, whose benchmark is precisely the (weighted) Nash social welfare. We begin by studying two extreme classes of valuations functions, namely perfect substitutes and perfect complements, and find that for perfect substitutes, the Fisher market mechanism yields a constant approximation: At most 2 and at least e 1 e (≈ 1.44). However, for perfect complements, the Fisher market mechanism does not work well, its bound degrading linearly with the number of players. Strikingly, the Trading Post mechanism-An indirect market mechanism also known as the Shapley-Shubik game-has significantly better performance than the Fisher market on its own benchmark. Not only does Trading Post achieve an approximation of 2 for perfect substitutes, but this bound holds for any concave utilities, and it becomes essentially optimal for perfect complements, where it reaches (1 +) for any ? > 0. Moreover, we show that all the Nash equilibria of the Trading Post mechanism are pure (hence the approximation factors extend to all Nash equilibria), and satisfy an important notion of individual fairness known as proportionality.
KW - Fisher market
KW - Nash social welfare
KW - Trading post
UR - http://www.scopus.com/inward/record.url?scp=85025825378&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85025825378&partnerID=8YFLogxK
U2 - 10.1145/3033274.3085143
DO - 10.1145/3033274.3085143
M3 - Conference contribution
AN - SCOPUS:85025825378
T3 - EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
SP - 611
EP - 628
BT - EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 18th ACM Conference on Economics and Computation, EC 2017
Y2 - 26 June 2017 through 30 June 2017
ER -