We study a very general class of games — multi-dimensional aggregative games — which in particular generalize both anonymous games andweighted congestion games. For any such game that is also large, we solve the equilibrium selection problem in a strong sense. In particular, we give an efficient weak mediator: a mechanism which has only the power to listen to reported types and provide non-binding suggested actions, such that (a) it is an asymptotic Nash equilibrium for every player to truthfully report their type to the mediator, and then followits suggested action; and (b) that when players do so, they end up coordinating on a particular asymptotic pure strategy Nash equilibrium of the induced complete information game. In fact, truthful reporting is an ex-post Nash equilibrium of the mediated game, so our solution applies even in settings of incomplete information, and even when player types are arbitrary or worst-case (i.e. not drawn from a common prior). We achieve this by giving an efficient differentially private algorithm for computing a Nash equilibrium in such games. The rates of convergence to equilibrium in all of our results are inverse polynomial in the number of players n. We also apply our main results to a multi-dimensional market game. Our results can be viewed as giving, for a rich class of games, a more robust version of the Revelation Principle, in that we work with weaker informational assumptions (no common prior), yet provide a stronger solution concept (ex-post Nash versus Bayes Nash equilibrium). In comparison to previous work, our main conceptual contribution is showing that weak mediators are a game theoretic object that exist in a wide variety of games – previously, they were only known to exist in traffic routing games. We also give the first weak mediator that can implement an equilibrium optimizing a linear objective function, rather than implementing a possibly worst-case Nash equilibrium.
|Original language||English (US)|
|Title of host publication||Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings|
|Editors||Guido Schäfer, Evangelos Markakis|
|Number of pages||14|
|State||Published - 2015|
|Event||11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands|
Duration: Dec 9 2015 → Dec 12 2015
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||11th International Conference on Web and Internet Economics, WINE 2015|
|Period||12/9/15 → 12/12/15|
Bibliographical noteFunding Information:
Research supported in part by NSF grants 1253345, 1101389, CNS-1254169, US-Israel Binational Science Foundation grant 2012348, Simons Foundation grant 361105, a Google Faculty Research Award, and the Alfred P. Sloan Foundation. Research performed while the first author was visiting the University of Pennsylvania.
© Springer-Verlag Berlin Heidelberg 2015.
- Differential privacy
- Equilibrium computation
- Mechanism design