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: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Scopus citations

Abstract

We consider finite 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. A motivating example is a congestion game in a complex transportation system, in which a large number of vehicles make daily routing decisions to optimize their own objectives in response to their observations. In this setting, observing and responding to the individual actions of all vehicles on a daily basis would be a formidable task for any individual driver. This disqualifies some of the well known decision making models such as "Fictitious Play" (FP) as suitable models for driver routing behavior. A more realistic assumption on the information tracked and processed by an individual driver is the daily aggregate congestion on the specific roads that are of interest to that driver. We will show that Joint Strategy Fictitious Play (JSFP), a close variant of FP, accommodates such information aggregation. Furthermore, we establish the convergence of JSFP to a pure Nash equilibrium in congestion games, or equivalently in finite potential games, when players use some inertia in their decisions and in both cases of with or without exponential discounting of the historical data.

Original languageEnglish (US)
Title of host publicationProceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Pages6692-6697
Number of pages6
DOIs
StatePublished - Dec 1 2005
Event44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 - Seville, Spain
Duration: Dec 12 2005Dec 15 2005

Publication series

NameProceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Volume2005

Other

Other44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
CountrySpain
CitySeville
Period12/12/0512/15/05

ASJC Scopus subject areas

  • Engineering(all)

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

Cite this