Joint Strategy Fictitious Play With Inertia for Potential Games
Top Cited Papers
- 10 February 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 54 (2), 208-220
- https://doi.org/10.1109/tac.2008.2010885
Abstract
We consider multi-player repeated games involving a large number of players with large strategy spaces and enmeshed utility structures. In these ldquolarge-scalerdquo games, players are inherently faced with limitations in both their observational and computational capabilities. Accordingly, players in large-scale games need to make their decisions using algorithms that accommodate limitations in information gathering and processing. This disqualifies some of the well known decision making models such as ldquoFictitious Playrdquo (FP), in which each player must monitor the individual actions of every other player and must optimize over a high dimensional probability space. We will show that Joint Strategy Fictitious Play (JSFP), a close variant of FP, alleviates both the informational and computational burden of FP. Furthermore, we introduce JSFP with inertia, i.e., a probabilistic reluctance to change strategies, and establish the convergence to a pure Nash equilibrium in all generalized ordinal potential games in both cases of averaged or exponentially discounted historical data. We illustrate JSFP with inertia on the specific class of congestion games, a subset of generalized ordinal potential games. In particular, we illustrate the main results on a distributed traffic routing problem and derive tolling procedures that can lead to optimized total traffic congestion.Keywords
This publication has 25 references indexed in Scilit:
- Generalised weakened fictitious playGames and Economic Behavior, 2006
- Adaptive HeuristicsEconometrica, 2005
- Uncoupled Dynamics Do Not Lead to Nash EquilibriumAmerican Economic Review, 2003
- Convergent multiple-timescales reinforcement learning algorithms in normal form gamesThe Annals of Applied Probability, 2003
- A simple adaptive procedure leading to correlated equilibriumEconometrica, 2000
- Learning Mixed EquilibriaGames and Economic Behavior, 1993
- The Evolution of ConventionsEconometrica, 1993
- Dynamic network models and driver information systemsTransportation Research Part A: General, 1991
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- CORRESPONDENCE. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952