- A fictitious play approach to large-scale optimization Theodore Lambert (tlamberttmcc.edu) Marina A. Epelman (mepelmanumich.edu) Robert L. Smith (rlsmithumich.edu) Abstract: 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^1,\ldots,y^n)\in\setY^1\times\cdots\times\setY^n\}$, i.e., in which the feasible region is a Cartesian product of finite sets $\setY^i,\ i\in N=\{1,\ldots,n\}$. The contributions of this paper are two-fold. 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 which allows for errors in players' best replies. Moreover, we introduce sampling-based approximate fictitious play which 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(\cdot)$ comes from a black box,'' such as a simulation model, where significant computational effort is required for each function evaluation. Keywords: Game theory, Heuristic algorithms Category 1: Other Topics (Game Theory ) Category 2: Other Topics (Optimization of Simulated Systems ) Citation: Operations Research, 53(3):477-489, 2005. Available at http://www-personal.engin.umich.edu/~mepelman/research/ Download: Entry Submitted: 08/01/2004Entry Accepted: 08/05/2004Entry Last Modified: 06/30/2005Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.