Talks
Fall 2015

# Nash Social Welfare Approximation for Strategic Agents

Friday, April 28th, 2017 10:00 am10:30 am

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 has a constant approximation: at most 2 and at least $e^{\frac{1}{e}}$ ($\approx$ 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 becomes arbitrarily close to optimal for perfect complements, where it reaches $(1+\epsilon)$ for every $\epsilon>0$. Moreover, we show that all the Nash equilibria of the Trading Post mechanism are pure