An Approximation Framework for Large-Scale Spatial Games

Abstract

Game theoretic modeling paradigms such as Evolutionary Games and Mean Field Games (MFG) are used to model a variety of multi-agent systems in which the agents interact in a game theoretic fashion. These models seek to answer two questions: how to predict the forward dynamics of a population and how to control them. However, both modeling paradigms have unique issues that can make them difficult to analyze in closed form when applied to spatial domains. On one hand, spatial EGT models are difficult to evaluate mathematically and both simulations and approximations run into accuracy and tractability issues. On the other hand, MFG models are not typically formulated to handle domains where agents have strategies and physical locations. Furthermore, any MFG approach for controlling strategy evolution on spatial domains need also address the same accuracy and efficiency challenges in the evaluation of its forward dynamics as those faced by evolutionary game approaches.

This dissertation presents a new modeling paradigm and approximation technique termed Bayesian-MFG for large-scale multi-agent games on spatial domains. The new framework lies at an intersection of techniques drawn from spatial evolutionary games, mean field games, and probabilistic reasoning. First, we describe our Bayesian network approximation technique for spatial evolutionary games to address the accuracy issues faced by lower order approximation methods. We introduce additional algorithms used to improve the computational efficiency of Bayesian network approximations. Alongside this, we describe our Pair-MFG model, a method for defining pair level approximate MFG for problems with distinct strategy and spatial components.

We combine the pair-MFG model and Bayesian network approximations into a unified Bayesian-MFG framework. Using this framework, we present a method for incorporating Bayesian network approximations into a control problem framework allowing for the derivation of more accurate control policies when compared to existing MFG approaches. We demonstrate the effectiveness of our framework through its application to a variety of domains such as evolutionary game theory, reaction-diffusion equations, and network security.