Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria
Authors: Fivos Kalogiannis, Ioannis Panageas
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The proof relies on the fact that zero-sum polymatrix Markov games with a switching controller have the following important property: the marginals of a coarse-correlated equilibrium constitute a Nash equilibrium (see Section 3.2). We refer to this phenomenon as equilibrium collapse. This property was already known for zero-sum polymatrix normal-form games by Cai et al. (2016) and our results generalize the aforementioned work for Markov games. As a corollary, we get that any algorithm in the literature that guarantees convergence to approximate coarse-correlated equilibria Markovian policies e.g., (Daskalakis et al., 2022) can be used to get approximate Nash equilibria. |
| Researcher Affiliation | Academia | Fivos Kalogiannis Department of Computer Science University of California, Irvine Irvine, CA fkalogia@uci.edu Ioannis Panageas Department of Computer Science University of California, Irvine Irvine, CA ipanagea@ics.uci.edu |
| Pseudocode | Yes | Algorithm 1 SPo CMAR (Daskalakis et al., 2022) and Algorithm 2 Est Visitation are provided in Appendix D. |
| Open Source Code | No | The paper refers to algorithms from other papers but does not state that the authors are providing open-source code for their own work or methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithms. It does not mention specific software dependencies or versions for implementation. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore, no experimental setup details like hyperparameters or training settings are provided. |