Nash Equilibria via Stochastic Eigendecomposition

• URL: http://arxiv.org/abs/2411.02308v1
• Date: Mon, 04 Nov 2024 17:32:21 GMT
• Title: Nash Equilibria via Stochastic Eigendecomposition
• Authors: Ian Gemp,
• Abstract summary: We show a Nash equilibrium can be approximated with purely calls to parameter, iterative variants of value decomposition and power. We provide pseudocode and experiments demonstrating solving for all equilibria of a general-sum game using only readily available linear algebra tools.
• Score: 4.190518009892366
• License:
• Abstract: This work proposes a novel set of techniques for approximating a Nash equilibrium in a finite, normal-form game. It achieves this by constructing a new reformulation as solving a parameterized system of multivariate polynomials with tunable complexity. In doing so, it forges an itinerant loop from game theory to machine learning and back. We show a Nash equilibrium can be approximated with purely calls to stochastic, iterative variants of singular value decomposition and power iteration, with implications for biological plausibility. We provide pseudocode and experiments demonstrating solving for all equilibria of a general-sum game using only these readily available linear algebra tools.

Related papers

• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  We develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players. In the matrix game setting, the results imply a complexity of $O(epsilon-1)$ to find the Nash distribution. In the game setting, the results also imply a complexity of $O(epsilon-8)$ to find a Nash equilibrium.
  arXiv  Detail & Related papers  (2024-09-02T20:07:25Z)
• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  We consider decentralized learning for zero-sum games, where players only see their information and are to actions and payoffs of the opponent. Previous works demonstrated convergence to a Nash equilibrium in this setting using double time-scale algorithms under strong reachability assumptions. Our contribution is a rational and convergent algorithm, utilizing Tsallis-entropy regularization in a value-iteration-based algorithm.
  arXiv  Detail & Related papers  (2023-12-13T09:31:30Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap.
  arXiv  Detail & Related papers  (2022-08-10T14:21:54Z)
• A Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusion Problems [17.597000481404883]
  We study monotone inclusion problems, which widely appear in machine learning applications. Our algorithm attains $epsilon$ norm of the operator with $mathcalO(frac1epsilon3)$ operator evaluations.
  arXiv  Detail & Related papers  (2022-03-17T16:48:57Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria.
  arXiv  Detail & Related papers  (2021-05-27T06:10:24Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

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.