Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2009 | Published
Journal Article Open

Joint strategy fictitious play with inertia for potential games

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.

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.

Attached Files

Published - Marden2009p12410.1109TAC.2008.2010885.pdf

Files

Marden2009p12410.1109TAC.2008.2010885.pdf
Files (886.9 kB)
Name Size Download all
md5:afabd548f6891fbc328ed284a8bd7c84
886.9 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 18, 2023