Abstract
This paper introduces a generalized version of the Fictitious Play algorithm designed to find Nash equilibria in games with an infinite "continuum" of anonymous players. By developing a novel way to compute best responses across continuous player types using interval-based step functions, the authors successfully solved for equilibria in complex simultaneous auctions. Experimental results demonstrate that the algorithm achieves fast convergence and low regret, making it a scalable solution for large-scale game theoretic problems that were previously computationally intractable.
Introduction
In game theory, "anonymous games" are those where a player's payoff depends on the aggregate behavior of the crowd rather than the specific identity of any single opponent. When the number of players becomes massive—as seen in global markets or internet traffic—researchers model them as a Continuum of Anonymous Players (CAPs).
While mathematicians have proven that equilibria exist in these large-scale games, actually computing them is a significant challenge. Most existing algorithms struggle with "continuous types," where players have a sliding scale of private information, such as a personal valuation for an item. Previous attempts often relied on restrictive assumptions like linearity. This paper presents a generic, domain-independent algorithm to bridge this gap.
Methodology: Generalized Fictitious Play
The authors build upon Fictitious Play (FP), a classic iterative algorithm where players track the historical frequency of their opponents' actions and play the "best response" to that distribution. To adapt this for a continuum of players, two key innovations were introduced:
- Generalized Beliefs: Instead of tracking individuals, the algorithm tracks a distribution over the entire space of player types and actions.
- Interval-Based Best Response: For games where utility is linear relative to a player's private type, the authors proved that the optimal strategy can be represented as a step function. By dividing the continuous type space into a finite set of intervals where the best response is identical, an infinite-dimensional problem is transformed into a manageable, discrete one.
Experimental Evaluation
The algorithm was evaluated using simulated simultaneous auction environments. In these tests, multiple auctions (3 to 5) ran concurrently with a varying number of bidders (10 to 20). Bidders had private values drawn from a uniform distribution $[0, 1]$ and could choose from 10 discrete bid levels. This simulated environment serves as a benchmark for "large games" where traditional iterative methods usually fail to converge due to the complex correlations between auctions.
Key Results
The results indicate that the Generalized FP handles these correlations gracefully. Two primary metrics were tracked: Convergence Error (the difference between beliefs and the actual distribution) and Average Regret (the incentive for a player to deviate from their current strategy).
- Quick Convergence: The algorithm demonstrated "exponentially fast" reduction in convergence error. In tests, the error dropped significantly within the first 20–40 iterations.
- Low Regret: Average regret dropped even faster than the belief error, suggesting the algorithm finds "good enough" strategies very early in the process.
- Scalability: By focusing on the distribution of actions rather than individual players, the complexity of the game becomes independent of the actual number of participants.
Conclusion
The authors have successfully obtained a pure Bayes-Nash equilibrium for simultaneous auctions with continuous private values using an iterative learning approach. While the algorithm currently requires discrete action spaces and simple utility structures, it represents a major step forward in computing equilibria for large-scale anonymous games. Future work will explore continuous action spaces and more complex utility functions.
Summary updated