Are Equivariant Equilibrium Approximators Beneficial?

• URL: http://arxiv.org/abs/2301.11481v2
• Date: Thu, 27 Apr 2023 12:54:51 GMT
• Title: Are Equivariant Equilibrium Approximators Beneficial?
• Authors: Zhijian Duan, Yunxuan Ma, Xiaotie Deng
• Abstract summary: We theoretically characterize benefits and limitations of equivariant equilibrium approximators. For the benefits, we show that they enjoy better generalizability than general ones and can achieve better approximations when the payoff distribution is permutation-invariant. For the limitations, we discuss their drawbacks in terms of equilibrium selection and social welfare.
• Score: 3.947165805405381
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, remarkable progress has been made by approximating Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE) through function approximation that trains a neural network to predict equilibria from game representations. Furthermore, equivariant architectures are widely adopted in designing such equilibrium approximators in normal-form games. In this paper, we theoretically characterize benefits and limitations of equivariant equilibrium approximators. For the benefits, we show that they enjoy better generalizability than general ones and can achieve better approximations when the payoff distribution is permutation-invariant. For the limitations, we discuss their drawbacks in terms of equilibrium selection and social welfare. Together, our results help to understand the role of equivariance in equilibrium approximators.

Related papers

• Approximate Equivariance in Reinforcement Learning [35.04248486334824]
  Equivariant neural networks have shown great success in reinforcement learning. In many problems, only approximate symmetry is present, which makes imposing exact symmetry inappropriate. We develop approximately equivariant algorithms in reinforcement learning.
  arXiv  Detail & Related papers  (2024-11-06T19:44:46Z)
• Machine learning in and out of equilibrium [58.88325379746631]
  Our study uses a Fokker-Planck approach, adapted from statistical physics, to explore these parallels. We focus in particular on the stationary state of the system in the long-time limit, which in conventional SGD is out of equilibrium. We propose a new variation of Langevin dynamics (SGLD) that harnesses without replacement minibatching.
  arXiv  Detail & Related papers  (2023-06-06T09:12:49Z)
• Bayes correlated equilibria and no-regret dynamics [9.89901717499058]
  This paper explores equilibrium concepts for Bayesian games, which are fundamental models of games with incomplete information. We focus on communication equilibria, which can be realized by a mediator who gathers each player's private information and then sends correlated recommendations to the players. We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight up to a multiplicative constant.
  arXiv  Detail & Related papers  (2023-04-11T06:22:51Z)
• Observable Perfect Equilibrium [0.4895118383237099]
  We define a new equilibrium refinement concept for extensive-form games called observable perfect equilibrium. We prove that observable perfect equilibrium is always guaranteed to exist. We expect observable perfect equilibrium to be a useful equilibrium refinement concept for modeling many important imperfect-information games of interest in artificial intelligence.
  arXiv  Detail & Related papers  (2022-10-29T06:07:29Z)
• Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
  A deep equilibrium model (DEQ) is implicitly defined through an equilibrium point of an infinite-depth weight-tied model with an input-injection. Instead of infinite computations, it solves an equilibrium point directly with root-finding and computes gradients with implicit differentiation. We propose a novel probabilistic framework to overcome the technical difficulty in the non-asymptotic analysis of infinite-depth weight-tied models.
  arXiv  Detail & Related papers  (2022-05-27T08:00:13Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• On the Nash equilibrium of moment-matching GANs for stationary Gaussian processes [2.25477613430341]
  We show that the existence of consistent Nash equilibrium depends crucially on the choice of the discriminator family. We further study the local stability and global convergence of gradient descent-ascent methods towards consistent equilibrium.
  arXiv  Detail & Related papers  (2022-03-14T14:30:23Z)
• Optimization Induced Equilibrium Networks [76.05825996887573]
  Implicit equilibrium models, i.e., deep neural networks (DNNs) defined by implicit equations, have been becoming more and more attractive recently. We show that deep OptEq outperforms previous implicit models even with fewer parameters.
  arXiv  Detail & Related papers  (2021-05-27T15:17:41Z)
• 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)
• Universal Quantum Fluctuation-Dissipation Relation for Systems Far From Equilibrium [3.0965505512285967]
  We present a general nonequilibrium Fluctuation-Dissipation Theorem (FDT) for quantum Markovian processes where the detailed-balance condition is violated. Apart from the fluctuations, the relaxation involves extra correlation that is governed by the quantum curl flux emerged in the far-from-equilibrium regime. Our results have the advantage of and exceed the scope of the fluctuation-dissipation relation in the perturbative and near equilibrium regimes.
  arXiv  Detail & Related papers  (2021-01-28T06:12:08Z)
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
  We show that an optimal correlated equilibrium can be computed in time in two-player games with public chance moves. This results in the biggest positive complexity result surrounding extensive-form correlation in more than a decade.
  arXiv  Detail & Related papers  (2020-09-09T14:51:58Z)

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.