A fictitious play approach to large-scale optimization
成果类型：
Article
署名作者：
Lambert, TJ III; Epelman, MA; Smith, RL
署名单位：
Nevada System of Higher Education (NSHE); Truckee Meadows Community College; University of Michigan System; University of Michigan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0178
发表日期：
2005
页码：
477-489
关键词：
摘要：
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),..., y(n)) is an element of y(1) x(...)x y(n)} i.e., in which the feasible region is a Cartesian product of finite sets y(i), i is an element of 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.