Computing Game Symmetries and Equilibria That Respect Them
Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of identifying and using symmetries... 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... 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... Finally, we present polynomial-time methods for the special cases... |
| Researcher Affiliation | Collaboration | Emanuel Tewolde1,2, Brian Hu Zhang1, Caspar Oesterheld1,2 Tuomas Sandholm1,3,4,5, Vincent Conitzer1,2 1Carnegie Mellon University 2Foundations of Cooperative AI Lab (FOCAL) 3Strategy Robot, Inc. 4Strategic Machine, Inc. 5Optimized Markets, Inc. EMAIL |
| Pseudocode | No | The paper describes methods and concepts in prose and mathematical notation, but does not include any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain an explicit statement or a link indicating that source code for the described methodology is being released or made publicly available. |
| Open Datasets | No | The paper uses well-known examples from game theory (e.g., Prisoner's Dilemma, Matching Pennies, Rock-Paper-Scissors) for illustrative purposes, but it does not describe or use any empirical datasets for experimental evaluation, nor does it provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving datasets, thus there is no information provided regarding dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity and algorithm design. It does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper discusses various theoretical algorithms and complexity classes but does not mention specific software dependencies with version numbers used for implementing or reproducing the work described. |
| Experiment Setup | No | The paper presents theoretical results concerning game symmetries and their computational complexity. It does not include any experimental setup details such as hyperparameters or training configurations. |