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

随着先进计算技术的普及，制造、电信、物流、运输、供应链和其他工程系统的仿真模型越来越复杂。这种模型通常缺乏数学特性，而这些特性在传统上对于确定最佳系统设计的有效计算程序的发展是必不可少的。因此，需要开发新的优化算法，即使在没有简化数学结构的情况下仍然有效。本研究探讨了虚拟游戏（FP）的计算效率变体的分析和实践潜力，这是一种来自数学学习理论的迭代技术，作为实现这一目标的优化范例。关键思想是将优化问题建模为人工“玩家”之间的共同利益博弈，这些玩家对应于精心选择的设计变量分区的组件。这些参与者的共同利益是优化系统性能的度量。这种方法的理论依据源于一个众所周知的事实，即对于共同利益的博弈，FP的极限点是纳什均衡，因此可以被视为一种局部最优。该研究建立在研究人员早期对抽样虚拟游戏（SFP）的研究基础上，这是一种修改，它用抽样近似值取代了FP中异常苛刻的预期效用计算，同时仍然保留了FP的理论性质。这项工作将在一套强大而严格的算法中达到高潮，研究者称之为近似虚拟游戏（AFP），其中“玩家”通过独立计算策略样本的最佳对策，并自适应地从他们过去最佳对策的历史概率分布中选择最佳对策，从而相互作用。AFP的一个主要计算优势是，最佳响应子问题嵌入到原始优化问题中，并且比原始优化问题小得多，与寻找联合最优策略相比，效率显著提高。传统上，复杂系统的仿真模型被用作描述性工具来测试知识渊博的用户建议的“经验法则”替代方案。AFP范式承诺使这些模型具有规定性，因为它的收敛性和最优性不依赖于此类系统和模型不太可能表现出的规则条件。

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.