Marden, J. R. and Arslan, G. and Shamma, J. S. (2009) Joint strategy fictitious play with inertia for potential games. IEEE Transactions on Automatic Control, 54 (2). pp. 208-220. ISSN 0018-9286 http://resolver.caltech.edu/CaltechAUTHORS:20090527-154250949
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20090527-154250949
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.
|Additional Information:||© 2009 IEEE. Manuscript received December 07, 2006. Current version published February 11, 2009. This work was supported by NSF Grants CMS-0339228, ECS-0501394, and ECCS-0547692, and ARO Grant W911NF-04-1-0316. This paper appeared in part at the 44th IEEE Conference on Decision and Control, 2005. Recommended by Associate Editor F. Bullo.|
|Subject Keywords:||fictitious play (FP); joint strategy fictitious play (JSFP)|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||04 Jun 2009 17:49|
|Last Modified:||26 Dec 2012 11:01|
Repository Staff Only: item control page