Anytime-Constrained Equilibria in Polynomial Time
Authors: Jeremy Mcmahan
ICML 2025 | Venue PDF | Archive PDF | Plain Text | 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. |