Learning Mean Field Games on Sparse Graphs
Christian Fabian_Learning Mean Field Games on Sparse Graphs_Figure1Figure 1: Four networks, each with around 15k nodes and 50k edges. The Erdös-Renyi graph (left) generated by a standard graphon does not have any high degree nodes. The Lp graphon graph (middle left) has a few high degree nodes expressed by the flat degree distribution tail. The graphex (middle right) and real subsampled Flickr network (right) show a very similar degree distribution with rather broad tails and a core-periphery like structure.
Christian Fabian
Christian Fabian_Learning Mean Field Games on Sparse Graphs_Figure2Figure 2: Comparison of the empirically observed MF with the predicted equilibrium MF for different problems and real world networks.
Christian FabianEinleitung
Learning the behavior of large agent populations is an important task for numerous research areas. Although the field of multi-agent reinforcement learning (MARL) has made significant progress towards solving these systems, solutions for many agents often remain computationally infeasible and lack theoretical guarantees. Mean Field Games (MFGs) address both of these issues and can be extended to Graphon MFGs (GMFGs) to include network structures between agents. Despite their merits, the real world applicability of GMFGs is limited by the fact that graphons only capture dense graphs. Since most empirically observed networks show some degree of sparsity, such as power law graphs, the GMFG framework is insufficient for capturing these network topologies. Thus, we introduce the novel concept of Graphex MFGs (GXMFGs) which builds on the graph theoretical concept of graphexes. Graphexes are the limiting objects to sparse graph sequences that also have other desirable features such as the small world property. Learning equilibria in these games is challenging due to the rich and sparse structure of the underlying graphs. To tackle these challenges, we design a new learning algorithm tailored to the GXMFG setup. This hybrid graphex learning approach leverages that the system mainly consists of a highly connected core and a sparse periphery. After defining the system and providing a theoretical analysis, we state our learning approach and demonstrate its learning capabilities on both synthetic graphs and real-world networks. This comparison shows that our GXMFG learning algorithm successfully extends MFGs to a highly relevant class of hard, realistic learning problems that are not accurately addressed by current MARL and MFG methods. Our contributions can be summarized as follows: (i) We define the novel concept of graphex mean field games to extend MFGs to an important class of problems; (ii) We provide theoretical guarantees to show that GXMFGs are an increasingly accurate approximation of the finite system; (iii) We develop a learning algorithm tailored to the challenging class of GXMFGs, where we exploit the hybrid structure caused by the sparse nature of the underlying graphs; (iv) We demonstrate the accuracy of our GXMFG approximation on different examples on both synthetic and empirical networks.
Methoden
Our framework is based on the graph-theoretical concept of graphexes which allow us to introduce sparse network structures into mean field games (GXMFGs). These GXMFGs allow us to efficiently learn approximate equilibria for otherwise intractable large agent systems. Specifically, our learning algorithm exploits the core-periphery structure of the sampled graphs yielding a hybrid approach with a a core and a periphery subsystem.
Ergebnisse
We find that our framework is capable of producing good equilibria in real world networks. Under the separable power law form, for each empirical data set we estimate the power law coefficient. Although this simple estimation yields reasonable results in our evaluation, we believe that developing and applying more complex estimators would also further increase the accuracy of our GXMFG learning method. If data sets contain multiple or directed edges, we substitute them by one undirected edge to obtain simple, undirected graphs. The plots in Figure 2 give a qualitative impression of the algorithmic performance of our approach on real world networks and show that the estimated equilibrium is close to the empirical MF on the real networks.
Diskussion
We have introduced the concept of graphex mean field games. To learn this challenging class of games, we have developed a novel hybrid graphex learning approach to address the high complexity of sparse real world networks. Our empirical examples have shown that learning GXMFGs could be a promising approach to understanding behavior in large and complex agent networks. For future work it would be interesting to develop and use more precise graphex estimators and to apply our setup to various research problems. We hope that our work contributes to the applicability and accuracy of mean field games for real world challenges.
