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..
The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Authors: Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first show that computing ϵ-Nash equilibria in 3-player adversarial team games wherein a team of 2 players competes against a single adversary is CLS-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from symmetric ϵ-Nash equilibria in symmetric, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry without disturbing the structure of the game. Moreover, we establish that computing symmetric (first-order) equilibria in symmetric min-max optimization is PPAD-complete, even for quadratic functions. Building on this reduction, we show that computing symmetric ϵ-Nash equilibria in symmetric, 6-player (3 vs. 3) team zero-sum games is also PPAD-complete, even for ϵ = poly(1/n). Finally, we prove that computing a non-symmetric poly(1/n)-equilibrium in symmetric min-max optimization is FNP-hard. |
| Researcher Affiliation | Collaboration | Ioannis Anagnostides1, Ioannis Panageas2, Tuomas Sandholm1,3, and Jingming Yan2 1Carnegie Mellon University 2University of California, Irvine 3Strategy Robot, Inc. 3Strategic Machine, Inc. 3Optimized Markets, Inc. EMAIL, EMAIL |
| Pseudocode | No | The paper describes mathematical reductions and proofs for complexity results, but it does not include any structured pseudocode or algorithm blocks. Methodologies are explained through textual descriptions and mathematical formulations. |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code, nor does it provide links to any code repositories. |
| Open Datasets | No | The paper is theoretical, focusing on complexity results in min-max optimization and game theory. It does not involve any empirical experiments, and therefore, no datasets are used or made publicly available. |
| Dataset Splits | No | The paper is a theoretical work on complexity analysis and does not involve empirical experiments with datasets. Therefore, there are no dataset splits (e.g., training, validation, test) described. |
| Hardware Specification | No | This is a theoretical paper focusing on complexity results. It does not describe any experiments that would require specific hardware, and thus, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on complexity analysis and proofs. It does not mention any software dependencies, tools, or libraries with specific version numbers that would be required to replicate experimental results. |
| Experiment Setup | No | The paper is theoretical, presenting complexity results and proofs. It does not include any empirical experiments, and therefore, there are no experimental setup details, hyperparameters, or training configurations described. |