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.