TY - JOUR
T1 - Joint strategy fictitious play with inertia for potential games
AU - Marden, Jason R.
AU - Arslan, Gürdal
AU - Shamma, Jeff S.
N1 - Funding Information:
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.
Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.
PY - 2009
Y1 - 2009
N2 - We consider multi-player repeated games involving a large number of players with large strategy spaces and enmeshed utility structures. In these "large-scale" 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 "Fictitious Play" (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.
AB - We consider multi-player repeated games involving a large number of players with large strategy spaces and enmeshed utility structures. In these "large-scale" 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 "Fictitious Play" (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.
KW - Fictitious play (FP)
KW - Joint strategy fictitious play (JSFP)
UR - http://www.scopus.com/inward/record.url?scp=61349086863&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=61349086863&partnerID=8YFLogxK
U2 - 10.1109/TAC.2008.2010885
DO - 10.1109/TAC.2008.2010885
M3 - Article
AN - SCOPUS:61349086863
SN - 0018-9286
VL - 54
SP - 208
EP - 220
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 2
ER -