Joint strategy fictitious play with inertia for potential games

Jason R. Marden*, Gürdal Arslan, Jeff S. Shamma

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

257 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)208-220
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume54
Issue number2
DOIs
StatePublished - 2009
Externally publishedYes

Bibliographical note

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.

Keywords

  • Fictitious play (FP)
  • Joint strategy fictitious play (JSFP)

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Joint strategy fictitious play with inertia for potential games'. Together they form a unique fingerprint.

Cite this