Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Computing Game Symmetries and Equilibria That Respect Them
Authors: Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer
AAAI 2025 | Venue PDF | 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. |