Computing Game Symmetries and Equilibria That Respect Them

• URL: http://arxiv.org/abs/2501.08905v1
• Date: Wed, 15 Jan 2025 16:15:16 GMT
• Title: Computing Game Symmetries and Equilibria That Respect Them
• Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer,
• Abstract summary: We study the computational of identifying and using symmetries in games. We find a strong connection between game symmetries and graph automorphisms. We show that finding a Nash equilibrium that respects a given set of symmetries is exactly as hard as Brouwer fixed point and gradient descent problems.
• Score: 77.72705755558839
• License:
• Abstract: Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways. Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively -- that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.

Related papers

• Non-invertible SPT, gauging and symmetry fractionalization [2.541410020898643]
  We construct the lattice models for the phases of all the symmetries in the Rep($Q_8$) duality web. We show that these interplay can be explained using the symmetry fractionalization in the 2+1d bulk SET.
  arXiv  Detail & Related papers  (2024-05-24T21:35:55Z)
• A Generative Model of Symmetry Transformations [44.87295754993983]
  We build a generative model that explicitly aims to capture the data's approximate symmetries. We empirically demonstrate its ability to capture symmetries under affine and color transformations.
  arXiv  Detail & Related papers  (2024-03-04T11:32:18Z)
• Equivariant Symmetry Breaking Sets [0.6475999521931204]
  Equivariant neural networks (ENNs) have been shown to be extremely effective in applications involving underlying symmetries. We propose a novel symmetry breaking framework that is fully equivariant and is the first which fully addresses spontaneous symmetry breaking.
  arXiv  Detail & Related papers  (2024-02-05T02:35:11Z)
• Learning Layer-wise Equivariances Automatically using Gradients [66.81218780702125]
  Convolutions encode equivariance symmetries into neural networks leading to better generalisation performance. symmetries provide fixed hard constraints on the functions a network can represent, need to be specified in advance, and can not be adapted. Our goal is to allow flexible symmetry constraints that can automatically be learned from data using gradients.
  arXiv  Detail & Related papers  (2023-10-09T20:22:43Z)
• Symmetry Induces Structure and Constraint of Learning [0.0]
  We unveil the importance of the loss function symmetries in affecting, if not deciding, the learning behavior of machine learning models. Common instances of mirror symmetries in deep learning include rescaling, rotation, and permutation symmetry. We show that the theoretical framework can explain intriguing phenomena, such as the loss of plasticity and various collapse phenomena in neural networks.
  arXiv  Detail & Related papers  (2023-09-29T02:21:31Z)
• Towards fully covariant machine learning [0.0]
  In machine learning, the most visible passive symmetry is the relabeling or permutation symmetry of graphs. We discuss dos and don'ts for machine learning practice if passive symmetries are to be respected.
  arXiv  Detail & Related papers  (2023-01-31T16:01:12Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Quantum Mechanics as a Theory of Incompatible Symmetries [77.34726150561087]
  We show how classical probability theory can be extended to include any system with incompatible variables. We show that any probabilistic system (classical or quantal) that possesses incompatible variables will show not only uncertainty, but also interference in its probability patterns.
  arXiv  Detail & Related papers  (2022-05-31T16:04:59Z)
• 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)
• Quantifying Algebraic Asymmetry of Hamiltonian Systems [0.0]
  We study the symmetries of a Hamiltonian system by investigating the asymmetry of the Hamiltonian with respect to certain algebras. The asymmetry of the $q$-deformed integrable spin chain models is calculated.
  arXiv  Detail & Related papers  (2020-01-08T08:12:20Z)

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.