Operator Splitting for Learning to Predict Equilibria in Convex Games

• URL: http://arxiv.org/abs/2106.00906v4
• Date: Tue, 11 Jun 2024 23:32:53 GMT
• Title: Operator Splitting for Learning to Predict Equilibria in Convex Games
• Authors: Daniel McKenzie, Howard Heaton, Qiuwei Li, Samy Wu Fung, Stanley Osher, Wotao Yin,
• Abstract summary: We introduce Nash Fixed Point Networks (N-FPNs), a class of neural networks that naturally output equilibria. N-FPNs are compatible with the recently developed Jacobian-Free Backpropagation technique for training implicit networks. Our experiments show N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers.
• Score: 26.92001486095397
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Systems of competing agents can often be modeled as games. Assuming rationality, the most likely outcomes are given by an equilibrium (e.g. a Nash equilibrium). In many practical settings, games are influenced by context, i.e. additional data beyond the control of any agent (e.g. weather for traffic and fiscal policy for market economies). Often the exact game mechanics are unknown, yet vast amounts of historical data consisting of (context, equilibrium) pairs are available, raising the possibility of learning a solver which predicts the equilibria given only the context. We introduce Nash Fixed Point Networks (N-FPNs), a class of neural networks that naturally output equilibria. Crucially, N- FPNs employ a constraint decoupling scheme to handle complicated agent action sets while avoiding expensive projections. Empirically, we find N-FPNs are compatible with the recently developed Jacobian-Free Backpropagation technique for training implicit networks, making them significantly faster and easier to train than prior models. Our experiments show N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers.

Related papers

• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  Non-concave games introduce significant game-theoretic and optimization challenges. We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria. We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Multi-Sender Persuasion: A Computational Perspective [41.88812114165843]
  We consider the multi-sender persuasion problem. It is ubiquitous in computational economics, multi-agent learning, and machine learning. We propose a novel differentiable neural network to approximate this game's non-linear and discontinuous utilities.
  arXiv  Detail & Related papers  (2024-02-07T15:50:20Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Scaling Laws Beyond Backpropagation [64.0476282000118]
  We study the ability of Direct Feedback Alignment to train causal decoder-only Transformers efficiently. We find that DFA fails to offer more efficient scaling than backpropagation.
  arXiv  Detail & Related papers  (2022-10-26T10:09:14Z)
• Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers [22.85979978964773]
  Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms. We introduce the Neural Equilibrium solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism.
  arXiv  Detail & Related papers  (2022-10-17T17:00:31Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret [97.73233271730616]
  Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies) DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to an importance sampling term inherited from Monte Carlo CFR (MCCFR) We show that a deep learning version of ESCHER outperforms the prior state of the art -- DREAM and neural fictitious self play (NFSP) -- and the difference becomes dramatic as game size increases.
  arXiv  Detail & Related papers  (2022-06-08T18:43:45Z)
• On the Convergence of Fictitious Play: A Decomposition Approach [17.607284715519587]
  We extend the convergence results of Fictitious Play (FP) to the combinations of such games and beyond. We develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. We analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.
  arXiv  Detail & Related papers  (2022-05-03T13:04:09Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  In large two-player zero-sum imperfect-information games, modern extensions of counterfactual regret minimization (CFR) are currently the practical state of the art for computing a Nash equilibrium. We formalize an online learning setting in which the strategy space is not known to the agent. We give an efficient algorithm that achieves $O(T3/4)$ regret with high probability for that setting, even when the agent faces an adversarial environment.
  arXiv  Detail & Related papers  (2021-03-08T04:03:24Z)

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.