Privacy and truthful equilibrium selection for aggregative games

Rachel Cummings, Michael Kearns, Aaron Roth, Zhiwei Steven Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationWeb and Internet Economics - 11th International Conference, WINE 2015, Proceedings
EditorsGuido Schäfer, Evangelos Markakis
PublisherSpringer Verlag
Pages286-299
Number of pages14
ISBN (Print)9783662489949
DOIs
StatePublished - 2015
Externally publishedYes
Event11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands
Duration: Dec 9 2015Dec 12 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9470
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Conference on Web and Internet Economics, WINE 2015
Country/TerritoryNetherlands
CityAmsterdam
Period12/9/1512/12/15

Bibliographical note

Funding 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.

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

Keywords

  • Differential privacy
  • Equilibrium computation
  • Mechanism design

Fingerprint

Dive into the research topics of 'Privacy and truthful equilibrium selection for aggregative games'. Together they form a unique fingerprint.

Cite this