Game Transformations That Preserve Nash Equilibria or Best-Response Sets

In the full version of this paper, we investigate under which conditions normal-form games are (guaranteed) to be strategically equivalent. First, we show for 𝑁-player games (𝑁 ≥ 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. We then turn 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 bestresponse 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 𝑁-player game (𝑁 ≥ 2): (i) The Nash equilibrium set stays the same; (ii) The bestresponse sets stay the same. For game transformations that operate player-wise and strategywise, 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 gametheoretic characteristics.