Toronto Networking Seminar 2005

Learning via Correlated Fictitious Play:
Identical Interest Games and Decentralized Optimization

Stephen Patek
University of Virginia

Date:  December  2,  3pm
Location: 1210 Bahen Center

Abstract

We study a new class of fictitious-play algorithms for identical interest games, where, instead of assuming that all players act according to independent mixed strategies, each player interprets the play history of all other players as though they are acting in a correlated fashion. Instead of evolving a set of mixed strategies, one for each player, our Correlated Fictitious Play (CFP) algorithm maintains a mixed strategy over the joint selection of actions by all players, and at each stage of the algorithm each player chooses a pure action that is a best response assuming that all other players play according to the relative frequency distribution of the joint selection of actions. We establish a convergence property associated with this algorithm which asserts that the limit points of CFP are “endogenous” correlated equilibria (a result analogous to Monderer and Shapley’s convergence theorem for conventional fictitious play and its set convergence to mixed strategy Nash equilibria). Our setting allows us to generalize this result to (1) allow for the approximate computation of best replies by sampling the play history distribution and (2) allow for the noisy evaluation of disutility associated with the specification of joint actions. We use the generalized convergence theorem to motivate the construction of a decentralized simulation optimization algorithm based on CFP, where we attribute player status to the individual components of the solution vector for the optimization problem. We illustrate our results as they apply to an Internet traffic engineering problem.

Bio:

Stephen D. Patek is an Associate Professor of Systems and Information Engineering at the University of Virginia. He received his Bachelor’s degree in Electrical Engineering in 1991 from the University of Tennessee, Knoxville. As an ONR Fellow, he completed his SMEE and Ph.D. degrees in Electrical Engineering and Computer Science (EECS) at the Massachusetts Institute of Technology, in 1994 and 1997 respectively. Dr. Patek’s research interests are in the areas of Stochastic Optimization, Control, and Game Theory, with applications in communications networks and sensor systems.