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 [1].
The Complexity of Two-Team Polymatrix Games with Independent Adversaries
Authors: Alexandros Hollender, Gilbert Maystre, Sai Ganesh Nagarajan
ICLR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is to prove that the two-team version remains hard, namely it is CLS-hard. Furthermore, we show that this lower bound is tight for the setting where one of the teams consists of multiple independent adversaries. On the way to obtaining our main result, we prove hardness of finding any stationary point in the simplest type of non-convexconcave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions. |
| Researcher Affiliation | Academia | Alexandros Hollender University of Oxford EMAIL Gilbert Maystre EPFL EMAIL Sai Ganesh Nagarajan Zuse Institute Berlin EMAIL |
| Pseudocode | No | The paper primarily presents mathematical proofs, theorems, and complexity analysis. It does not contain any structured pseudocode blocks or algorithms. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available or released. |
| Open Datasets | No | The paper is theoretical, focusing on computational complexity and proofs for game theory models, and does not involve experiments using datasets. |
| Dataset Splits | No | As the paper focuses on theoretical complexity analysis and does not report experimental results from datasets, no dataset splits are provided. |
| Hardware Specification | No | The paper is a theoretical work on computational complexity and does not describe any experimental setup or hardware used for computations. |
| Software Dependencies | No | The paper focuses on theoretical aspects of game complexity and does not mention any specific software dependencies or versions used for experimental work. |
| Experiment Setup | No | As a theoretical paper, it does not include details on experimental setup such as hyperparameters or training configurations. |