The prevalence of advanced computing technology has resulted in > increasingly complex simulation models of manufacturing, > telecommunication, logistic, transportation, supply chain and other > engineering systems. Such models often lack mathematical properties > that have traditionally been essential to the development of efficient > computational procedures for determining an optimal system design. > Consequently, the need arises to develop new optimization algorithms > that remain efficient even in the absence of simplifying mathematical > structures. This research investigates the analytical and practical > potential of computationally efficient variants of Fictitious Play > (FP), an iterative technique from the mathematical theory of learning, > as an optimization paradigm to achieve this goal. > > The key idea is to model the optimization problem as a game of common > interest between artificial "players" that correspond to components of > a carefully chosen partition of the design variables. The shared > interest of these players is to optimize the metric of system > performance. Theoretical justification for this approach is rooted in > the well-known fact that for games of common interest, limit points of > FP are Nash equilibria and thus may be viewed as a type of local > optimum. The research builds on the investigators' earlier work on > Sampled Fictitious Play (SFP), a modification that replaces the > exceptionally demanding expected utility calculations in FP with their > sampled approximations while still preserving FP's theoretical > properties. The work will culminate in a powerful and rigorous suite > of algorithms the investigators term Approximate Fictitious Play > (AFP), where the "players" interact with one another by calculating a > best response to a sample of strategies independently and adaptively > chosen from a probability distribution over their history of past best > responses. A major computational benefit of AFP is that the best > response subproblems are embedded in and significantly smaller than > the original optimization problem, leading to a dramatic increase in > efficiency compared to finding jointly optimal strategies. > Traditionally, simulation models of complex systems have been employed > as descriptive tools to test "rule-of-thumb" alternatives suggested by > a knowledgeable user. The AFP paradigm promises to make these models > prescriptive as its convergence and optimality properties do not rely > on regularity conditions that such systems and models are unlikely to > exhibit.
