Asymptotically Truthful Equilibrium Selection in Large Congestion Games

Ryan Rogers, Aaron Roth

TL;DR

This paper introduces a novel, "weak" mediator for large congestion games that allows players to truthfully report their types and achieve an approximate Nash equilibrium of the underlying complete information game, even when players have incomplete information about each other. This is achieved using a differentially private algorithm that ensures truthful reporting is an equilibrium strategy, even without the mediator being able to verify types or enforce actions.

What Problem Does This Paper Address?

In many real-world scenarios, like traffic routing, we have large numbers of interacting agents (players) whose individual actions affect a shared resource (congestion). While complete information models of these games are well-understood and have desirable equilibrium properties, they are often unrealistic. In reality, players typically have incomplete information about each other's "types" (e.g., their specific origin-destination pair in a traffic network). This incomplete information can lead to worse equilibria, difficulty in coordination, and a loss of desirable ex-post properties. The authors aim to bridge this gap by finding a way to implement the desirable equilibria of the complete information game within a setting of incomplete information, specifically for large congestion games. They want to achieve this using a mediator that is as weak as possible, meaning it cannot force participation, verify types, or enforce its suggestions.

Methods

The core of the paper's contribution lies in designing a mediator that uses joint differential privacy to achieve its goals. This is a relaxation of standard differential privacy that allows for some sensitivity to individual player reports while still providing strong privacy guarantees. The mediator simulates best-response dynamics, a standard algorithm for finding approximate Nash equilibria in congestion games. However, to maintain privacy, it uses noisy edge counts instead of exact ones. This involves a binary mechanism to introduce controlled noise. The "largeness" condition of the game is crucial, as it ensures that individual players' actions have only a small impact on others, which helps bound the amount of noise needed for privacy and limits the number of times a player needs to change their strategy. The authors then prove that truthful reporting to this mediator, combined with following its suggestions, forms an approximate equilibrium of the incomplete information game and induces an approximate Nash equilibrium of the underlying complete information game.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Weak Mediator Power: The paper demonstrates that even a mediator with minimal enforcement capabilities (no participation guarantees, no type verification, no action enforcement) can be effective in large games. This is a significant departure from mechanisms that rely on strong enforcement.
  • Differential Privacy as a Coordination Tool: The authors cleverly leverage differential privacy not just for privacy, but as a mechanism to ensure truthful reporting and coordinate players towards a desirable equilibrium. The privacy mechanism inherently limits the influence of any single player's report on others, which is key to making truthful reporting an equilibrium.
  • Asymptotic Truthfulness: The core result is that truthful reporting becomes an asymptotically exact equilibrium strategy as the game size grows. This means that for very large games, players have virtually no incentive to lie to the mediator.
  • Bridging Complete and Incomplete Information: The work successfully shows how to recover desirable properties of complete information games (like Nash equilibria) in the more realistic setting of incomplete information, without requiring players to know a common prior distribution.

Key Results

  • The paper presents a mediator that, when used truthfully, results in an η'-approximate Bayes Nash equilibrium of the incomplete information game for any prior distribution.
  • When players play according to this equilibrium, their actions form an η'-approximate Nash equilibrium of the induced complete information game.
  • The approximation factor η' tends to zero as the size of the game (n) grows, meaning truthful play becomes asymptotically exact.
  • The algorithm is jointly differentially private, meaning it protects the privacy of individual player reports while still allowing for equilibrium computation.
  • The authors provide a concrete algorithm, BR-PRIVATE, that implements this mediator and achieves these guarantees.

Limitations and Future Work

  • Congestion Games Specificity: The current results are specific to congestion games. A major open question is whether this approach can be extended to general games.
  • Approximation Factors: While the approximation factors become asymptotically zero, they are still present in finite games. A key question is whether these approximation factors can be completely eliminated, even in small games, and whether exact Nash equilibria can be implemented as exact Bayes Nash equilibria.
  • Dominant Strategy Equilibria: The paper touches upon the question of whether dominant strategy equilibria can be achieved, which is a stronger form of equilibrium than Nash equilibrium. This remains an open area.
  • Computational Efficiency: While the algorithm is designed to be efficient in terms of players and description length, the theoretical bounds on running time and approximation might be further improved.

Summary updated

Abstract

Studying games in the complete information model makes them analytically tractable. However, large $n$ player interactions are more realistically modeled as games of incomplete information, where players may know little to nothing about the types of other players. Unfortunately, games in incomplete information settings lose many of the nice properties of complete information games: the quality of equilibria can become worse, the equilibria lose their ex-post properties, and coordinating on an equilibrium becomes even more difficult. Because of these problems, we would like to study games of incomplete information, but still implement equilibria of the complete information game induced by the (unknown) realized player types. This problem was recently studied by Kearns et al. and solved in large games by means of introducing a weak mediator: their mediator took as input reported types of players, and output suggested actions which formed a correlated equilibrium of the underlying game. Players had the option to play independently of the mediator, or ignore its suggestions, but crucially, if they decided to opt-in to the mediator, they did not have the power to lie about their type. In this paper, we rectify this deficiency in the setting of large congestion games. We give, in a sense, the weakest possible mediator: it cannot enforce participation, verify types, or enforce its suggestions. Moreover, our mediator implements a Nash equilibrium of the complete information game. We show that it is an (asymptotic) ex-post equilibrium of the incomplete information game for all players to use the mediator honestly, and that when they do so, they end up playing an approximate Nash equilibrium of the induced complete information game. In particular, truthful use of the mediator is a Bayes-Nash equilibrium in any Bayesian game for any prior.
BibTeX
@inproceedings{rogers2013asymptotically,
  author = {Ryan Rogers and Aaron Roth},
  title = {{Asymptotically Truthful Equilibrium Selection in Large Congestion Games}},
  booktitle = {EC},
  year = {2013},
}
Figure