# Game Transformations That Preserve Nash Equilibria or Best-Response Sets

arXiv: https://arxiv.org/abs/2111.00076 · HTML: https://mlsanity.com/paper/2111.00076/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2021.

## Built on by (most cited first, 5 of 5)

- [Normative Modules: A Generative Agent Architecture for Learning Norms that Supports Multi-Agent Cooperation](https://mlsanity.com/paper/2405.19328/) (2024)
- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value](https://mlsanity.com/paper/2311.00582/) (2023)
- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

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. It is a widely used fact that a positive affine (linear) transformation of the utility payoffs neither changes the best-response sets nor the Nash equilibrium set. We investigate which other game transformations also possess either of the following two properties when being applied to an arbitrary N-player game (N >= 2): (i) The Nash equilibrium set stays the same; (ii) The best-response sets stay the same. 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.