This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Lambert, T. J. Articles by Smith, R. L. Search for Related Content

A Fictitious Play Approach to Large-Scale Optimization

Mathematics Department, Truckee Meadows Community College, 7000 Dandini Boulevard, Vista B200, Reno, Nevada 89512
Department of Industrial and Operations Engineering, University of Michigan, 1205 Beal Avenue, Ann Arbor, Michigan 48109
Department of Industrial and Operations Engineering, University of Michigan, 1205 Beal Avenue, Ann Arbor, Michigan 48109
lamber12{at}tmcc.nevada.edu
mepelman{at}umich.edu
rlsmith{at}umich.edu

In this paper, we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form max{u(y): y = (y¹,...,yⁿ) ¹xxⁿ}, i.e., in which the feasible region is a Cartesian product of finite sets ⁱ, i N = {1,...,n}. The contributions of this paper are twofold. In the first part of the paper, we broaden the existing results on convergence properties of the fictitious play algorithm on games with identical payoffs to include an approximate fictitious play algorithm that allows for errors in players’ best replies. Moreover, we introduce sampling-based approximate fictitious play that possesses the above convergence properties, and at the same time provides a computationally efficient method for implementing fictitious play. In the second part of the paper, we motivate the use of algorithms based on sampled fictitious play to solve optimization problems in the above form with particular focus on the problems in which the objective function u(·) comes from a "black box," such as a simulation model, where significant computational effort is required for each function evaluation.

Subject classifications: games/group decisions:noncooperative; programming:algorithms/heuristic; transportation:route choice.
History: Received December 2002; revision received January 2004; accepted March 2004.

This article has been cited by other articles:

				E. Campos-Nanez, A. Garcia, and C. Li A Game-Theoretic Approach to Efficient Power Management in Sensor Networks Operations Research, May 1, 2008; 56(3): 552 - 561. [Abstract] [PDF]

				A. Garcia, S. D. Patek, and K. Sinha A Decentralized Approach to Discrete Optimization via Simulation: Application to Network Flow Operations Research, July 1, 2007; 55(4): 717 - 732. [Abstract] [PDF]