Collaborative Research : Approximate Fictitious Play for the Optimization of Complex Systems

点击翻译按钮获取中文摘要

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.