Learning Graphon Mean Field Games and Approximate Nash Equilibria

• URL: http://arxiv.org/abs/2112.01280v1
• Date: Mon, 29 Nov 2021 16:16:11 GMT
• Title: Learning Graphon Mean Field Games and Approximate Nash Equilibria
• Authors: Kai Cui, Heinz Koeppl
• Abstract summary: We propose a novel discrete-time formulation for graphon mean field games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution. We successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents.
• Score: 33.77849245250632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of a broad class of dynamical sequential games with large numbers of agents. So far, results have been largely limited to graphon mean field systems with continuous-time diffusive or jump dynamics, typically without control and with little focus on computational methods. We propose a novel discrete-time formulation for graphon mean field games as the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side, we provide general learning schemes for graphon mean field equilibria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. By repeatedly finding a regularized optimal control solution and its generated mean field, we successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents. Empirically, we are able to demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph or system size grows, verifying our theory. More generally, we successfully apply policy gradient reinforcement learning in conjunction with sequential Monte Carlo methods.

Related papers

• Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithm [14.647775453098513]
  We prove the existence and uniqueness of the graphon equilibrium with mild assumptions, and show that this equilibrium can be used to construct an approximate solution for finite player game on networks. An online oracle-free learning algorithm is developed to solve the equilibrium numerically, and sample complexity analysis is provided for its convergence.
  arXiv  Detail & Related papers  (2024-05-08T04:44:16Z)
• A Deep Learning Method for Optimal Investment Under Relative Performance Criteria Among Heterogeneous Agents [2.330509865741341]
  Graphon games have been introduced to study games with many players who interact through a weighted graph of interaction. We focus on a graphon game for optimal investment under relative performance criteria, and we propose a deep learning method.
  arXiv  Detail & Related papers  (2024-02-12T01:40:31Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  We show how graph diffusion equations extrapolate and generalize in the presence of varying graph topologies. We propose a novel graph encoder backbone, Advective Diffusion Transformer (ADiT), inspired by advective graph diffusion equations.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• Beyond spectral gap (extended): The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. Current theory does not explain that collaboration enables larger learning rates than training alone. This paper aims to paint an accurate picture of sparsely-connected distributed optimization.
  arXiv  Detail & Related papers  (2023-01-05T16:53:38Z)
• Learning Sparse Graphon Mean Field Games [26.405495663998828]
  Graphon mean field games (GMFGs) enable the scalable analysis of MARL problems that are otherwise intractable. Our paper introduces a novel formulation of GMFGs, called LPGMFGs, which leverages the graph theoretical concept of $Lp$ graphons. This especially includes power law networks which are empirically observed in various application areas and cannot be captured by standard graphons.
  arXiv  Detail & Related papers  (2022-09-08T15:35:42Z)
• Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. This paper aims to paint an accurate picture of sparsely-connected distributed optimization when workers share the same data distribution. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies.
  arXiv  Detail & Related papers  (2022-06-07T08:19:06Z)
• Hypergraphon Mean Field Games [27.56570458658299]
  We propose an approach to modelling large-scale multi-agent dynamical systems using the theory of mean-field games. We obtain limiting descriptions for large systems of non-linear, weakly-interacting dynamical agents. On the theoretical side, we prove the well-foundedness of the resulting hypergraphon mean field game. On the applied side, we extend numerical and learning algorithms to compute the hypergraphon mean field equilibria.
  arXiv  Detail & Related papers  (2022-03-30T11:57:16Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Approximating Nash Equilibrium in Random Graphical Games [3.42658286826597]
  Nash equilibrium in multi-agent games is a longstanding challenge at the interface of game theory and computer science. We provide a quasipolynomial time approximation scheme (QPTAS) for computing an epsilon approximate nash equilibrium of polymatrix games on random graphs with edge density greater than poly(k, 1/epsilon, ln(N))$ with high probability. With the same runtime we can compute an epsilon-approximate Nash equilibrium that epsilon-approximates the maximum social welfare of any nash equilibrium of the game.
  arXiv  Detail & Related papers  (2021-12-07T01:40:20Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• Graph Classification by Mixture of Diverse Experts [67.33716357951235]
  We present GraphDIVE, a framework leveraging mixture of diverse experts for imbalanced graph classification. With a divide-and-conquer principle, GraphDIVE employs a gating network to partition an imbalanced graph dataset into several subsets. Experiments on real-world imbalanced graph datasets demonstrate the effectiveness of GraphDIVE.
  arXiv  Detail & Related papers  (2021-03-29T14:03:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.