Game Transformations That Preserve Nash Equilibria or Best-Response Sets
Authors: Emanuel Tewolde, Vincent Conitzer
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we investigate under which conditions normal-form games are (guaranteed to be) strategically equivalent. First, we show for N-player games (N 3) that (A) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that (B) it is co-NP-hard to decide whether two games have the same best-response sets. Combining that with known results from the literature, we move our attention to equivalence-preserving game transformations. ... For game transformations that operate player-wise and strategy-wise, we prove that (i) implies (ii) and that transformations with property (ii) must be positive affine. The resulting equivalence chain highlights the special status of positive affine transformations among all the transformation procedures that preserve key game-theoretic characteristics. |
| Researcher Affiliation | Academia | Emanuel Tewolde and Vincent Conitzer Foundations of Cooperative AI Lab (FOCAL) Computer Science Department, Carnegie Mellon University, USA emanueltewolde@cmu.edu, conitzer@cs.cmu.edu |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any information or links regarding open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets, therefore no information about public dataset availability for training is present. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments, thus no specific experimental setup details are provided. |