Fictitious Play for Complex Systems Optimization

越来越多地，出现了解决大规模复杂优化问题的需求，这些问题通过模拟来建模，这些模拟几乎不允许或不允许对其目标函数的形式进行结构性假设。然而，它们的复杂性和范围要求采用综合方法来寻找最佳设计。这笔赠款将用于从理论和实践的角度研究虚拟游戏范式作为解决此类问题的算法方法的潜力。虚拟博弈(FP)是一种源于博弈论的迭代过程，它在由潜在系统优化问题的决策变量的划分表示的参与者之间重复执行非合作博弈。因此，与联合最优策略相反，最佳回复可以显著降低问题的计算复杂性。提出的工作将集中在这种算法的计算实用变体，以及它们在两个实际问题上的应用：动态交通信号配时计划的设计和动态规划的大规模实例。特别是，作为我们研究的一部分，我们希望在博弈论和动态规划中的概念和结果之间建立密切的联系，这些概念和结果到目前为止似乎还没有被探索过。使用复杂系统的真实模拟来寻求更好的系统性能的机会，以及提供并行计算的算法，可以对诸如但不限于交通和制造等领域产生显著的好处。如果这项研究成功，不仅将在这些应用领域带来潜在的改进，而且还将为改进复杂的真实建模大系统的设计提供一种通用而高效的算法工具，具有广泛而容易应用的前景。这项研究承诺与行业和政府产生重大互动，以确保所开发的模型和数据的真实性。

Increasingly, the need arises to solve large-scale complex optimization problems modeled by simulations that allow little or no structural assumptions on the form of their objective functions. And yet their complexity and scope demand integrated approaches to finding optimal designs. This grant will fund the investigation of the potential of a fictitious play paradigm as an algorithmic approach to such problems, both from theoretical and practical points of view. Fictitious Play (FP), which is an iterative process originating in game theory, executes a non-cooperative game repeatedly among players represented by a partition of the decision variables of the underlying system optimization problem. Best replies, as opposed to jointly optimal strategies, can thus dramatically reduce the computational complexity of the problem. Proposed work will focus on computationally practical variants of such an algorithm, and their application to two practical problems: design of dynamic traffic signal timing plans and large-scale instances of Dynamic Programming. In particular, as part of our research, we hope to establish close links between concepts and results in game theory and dynamic programming that so far appear to be unexplored.The opportunity to seek better system performance using realistic simulations of complex systems with an algorithm that gracefully scales and offers the opportunity to compute in parallel can have significant benefits for areas such as, but not limited to, transportation and manufacturing. If successful, this research will not only lead to potential improvements in these application arenas, but will also provide a general and efficient algorithmic tool for improving design of complex realistically-modeled large scale systems, which promises to be broadly and easily applicable. The research promises to produce significant interactions with industry and government to insure realism for the models and data developed.