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.
