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..
Anytime-Constrained Equilibria in Polynomial Time
Authors: Jeremy Mcmahan
ICML 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a comprehensive theory of anytime-constrained MGs, which includes (1) a computational characterization of feasible policies, (2) a fixedparameter tractable (FPT) (Downey and Fellows, 2012) algorithm for computing subgame-perfect ACE, and (3) a polynomial time algorithm for computing approximately feasible subgame-perfect ACE. Given our hardness results, our algorithmic guarantees are the best possible in the worst case. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Wisconsin Madison, Wisconsin, USA. Correspondence to: Jeremy Mc Mahan <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Feasibility Algorithm 2 Reduction Algorithm 3 Constrained Solver Algorithm 4 Approximation |
| Open Source Code | No | The paper does not provide any explicit statement about releasing code, a link to a code repository, or mention of code in supplementary materials. |
| Open Datasets | No | The paper is theoretical, focusing on mathematical models (constrained Markov games) and algorithms. It does not involve empirical evaluation on specific datasets, therefore no open datasets are used or provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets. Therefore, there is no mention of dataset splits such as training, validation, or test sets. |
| Hardware Specification | No | The paper is theoretical, focusing on algorithms and proofs for anytime-constrained Markov games. It does not describe any experiments that would require specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper mentions the need for a 'polynomial-time linear-program feasibility solver' as part of its algorithmic framework but does not specify any particular software, library, or their version numbers (e.g., Python, PyTorch, CPLEX, Gecode with versions). |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design, proofs, and computational complexity for anytime-constrained Markov games. It does not describe any experimental evaluations, and therefore, no experimental setup details, hyperparameters, or training configurations are provided. |