Computing Game Symmetries and Equilibria That Respect Them
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929735113637888 |
|---|---|
| author | Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Sandholm, Tuomas Conitzer, Vincent |
| author_facet | Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Sandholm, Tuomas Conitzer, Vincent |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08905 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing Game Symmetries and Equilibria That Respect Them Tewolde, Emanuel Zhang, Brian Hu Oesterheld, Caspar Sandholm, Tuomas Conitzer, Vincent Computer Science and Game Theory Artificial Intelligence Computational Complexity Multiagent Systems 91A05, 91A06, 91A10, 91A26, 91A35, 91A68, 68Q17, 68Q25, 68T01 I.2; J.4; F.2 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. |
| title | Computing Game Symmetries and Equilibria That Respect Them |
| topic | Computer Science and Game Theory Artificial Intelligence Computational Complexity Multiagent Systems 91A05, 91A06, 91A10, 91A26, 91A35, 91A68, 68Q17, 68Q25, 68T01 I.2; J.4; F.2 |
| url | https://arxiv.org/abs/2501.08905 |