Privacy and truthful equilibrium selection for aggregative games
From MaRDI portal
Abstract: We study a very general class of games --- multi-dimensional aggregative games --- which in particular generalize both anonymous games and weighted 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 follow its 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 . 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.
Recommendations
Cites work
- Approximately optimal mechanism design via differential privacy
- Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)
- Best-reply dynamics in large binary-choice anonymous games
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 2038846 (Why is no real title available?)
- Is privacy compatible with truthfulness?
- Mechanism design in large games: incentives and privacy (extended abstract)
- Mediators in position auctions
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the complexity of Nash equilibria in anonymous games
- Optimal Auction Design
- Privacy and truthful equilibrium selection for aggregative games
- Privacy-Preserving Public Information for Sequential Games
- Privately solving linear programs
- Strong mediated equilibrium
- The multiplicative weights update method: a meta-algorithm and applications
- Theory of Cryptography
Cited in
(9)- Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner
- Mechanism design in large games: incentives and privacy (extended abstract)
- Privacy-Preserving Public Information for Sequential Games
- Determining a Discrete Set of Site-Constrained Privacy Options for Users in Social Networks Through Stackelberg Games
- Privacy and truthful equilibrium selection for aggregative games
- Scalable and Jointly Differentially Private Packing
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- Resilient Information Aggregation
This page was built for publication: Privacy and truthful equilibrium selection for aggregative games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460796)
