Game Transformations That Preserve Nash Equilibria or Best-Response Sets

1 Introduction

1.1 Motivation

When faced with a strategic interaction with other agents, it can be computationally useful for AI systems - as we will discuss further down - to detect when the current situation can be treated in the same way as another strategic game that has already been dealt with in the past. This problem can also be critical for the robustness and generalizability of our AI systems. AI agents will often need to act in new environments, possibly with multiple equilibria, and yet be predictable to each other and to us to avoid bad outcomes. Recognizing a new environment as strategically equivalent to a previously encountered one can help tremendously with this, providing a precedent for action that ensures that everyone's expectations on behavior are well calibrated. Oesterheld and Conitzer [2022], for example, build on that in order to achieve Pareto-improved outcomes in games played by AI representatives (where games can be transformed by reprogramming the AIs' rewards).

∗An earlier extended abstract of this paper can be found in the Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024).

Not least for these various reasons, even the simplest class of games - 2-player normal-form with 2 actions per player - has been studied extensively in order to obtain a complete taxonomy for them; see for example [Robinson and Goforth, 2005; Rapoport et al., 1976; Borm, 1987]. With it, it is easy to recognize when a 2 × 2 game contains traits of competition, cooperation, coordination, etc. [Bruns and Kimmich, 2021]. Such interpretation tools are also being developed for more complex strategic situations [Marris et al., 2023], but this still remains an important venue of further research. One challenge is that larger games become prohibitively complex to compare directly: Du [2008] show that deciding whether two 2-player normal-form games share Nash equilibria is a computationally hard task. We will show in Section 3 that this task is also computationally hard for the case of best response sets and at least three players.

One classic tool that emerged in the beginnings of game theory has been to transform a given game into other strategically equivalent games that are easier to analyze [von Neumann and Morgenstern, 1944]. Positive affine (linear) transformations (PATs) have been particularly useful in that regard [Aumann, 1961; Adler et al., 2009]. To illustrate PATs, consider any 2-player normal-form game in which the players' utilities are measured in dollars. Then, the best-response strategies of player 1 do not change if her utility payoffs are multiplied by a factor of 5. Moreover, they also do not change if 10 dollars are added to all outcomes that involve player 2 playing his, say, third strategy. More generally, PATs have the power to rescale the utility payoffs of each player and to add constant terms to the utility payoffs of a player i for each strategy choice k-i of her opponents.

Through leveraging PATs, previous work significantly extended the applicability of efficient Nash equilibrium solvers [von Neumann, 1928; Dantzig, 1951; Adler, 2013; Adsul et al., 2021] to classes beyond those of zero-sum and rank-1 games 1 [Moulin and Vial, 1978; Kontogiannis and Spirakis, 2012; Heyman and Gupta, 2023].

PATs are also popular in mechanism design and ecommerce: Affine maximizer auctions are PAT transformations of the classic VCG mechanism, and as such, inherit strategy-proofness and individual rationality by the strategypreserving nature of PATs. They play a key role in finding revenue-maximizing mechanisms (both with classical optimizers [Likhodedov and Sandholm, 2004] and deep learning [Curry et al., 2023; Curry et al., 2024], and in improving welfare in redistribution mechanisms [Guo and Conitzer, 2010] and advertisement auctions [Deng et al., 2021].

The versatility of PATs is based on their well-known property that they do not change preferences, best responses, or Nash equilibria, when being applied to an arbitrary game. In a very precise sense, PATs are also the only game transformations that do not change preferences; cf. Section 7. The main result in this paper addresses the question of whether there are other (efficiently computable) game transformations that do not change best responses or Nash equilibria.

1.2 Overview

Sections 2 and 4 provide some background on game-theoretic concepts that are relevant to understanding and deriving our main results. In Section 3, we develop computational hardness results for deciding whether a strategy in a game ever constitutes a best response and for deciding whether two games have the same best-response sets. We believe these results are of independent interest. However, they are also important for Section 5, in which we discuss why we will henceforth restrict our attention to game transformations that transform utilities player-wise and strategy-wise (called separability). In Section 6, we proceed to characterize all separable game transformations that preserve the Nash equilibrium set - or, alternatively, the best response sets - when being applied to an arbitrary N-player game. Last but not least, Section 7 puts our results into context with further related work.

To illustrate the insights of Section 6 on an example, consider HEx that takes any 2-player 2 × 2 normal-form game with payoff matrices

and transforms it into the game HEx(A,B) := (A′ ,B′ ) that is defined as

As one can see with the sign function in B′ , it is noteworthy to highlight that our notion of a game transformation allows for non-continuous functions. With Theorem 2, we will show that there must exist 2×2 games ( ¯ A, ¯B) for whichHEx does not preserve their Nash equilibrium set or - respectively

1 A 2-player game, represented by its payoff matrices A,B ∈ Rm×n , is said to have rank 1 if rank(A+B) = 1.

- their best-response sets. More generally, we derive that universally preserving the Nash equilibrium set implies that the best-response sets always have to be preserved as well; and that the latter property is only satisfied by game transformations H with the very restricted structure of a PAT. In the example of HEx, each transformation map within it singlehandedly already violates a PAT structure.

Full proofs for statements in this paper can be found in the full version of this paper.

2 Normal-FormGames

Notation-wise, we denote [n] := {1, . . . , n} for any n ∈ N. A normal-form multiplayer game G specifies

• (a) the number of players N ∈ N,N ≥ 2,
• (b) a set of pure strategies Si = [mi] for each player i where mi ∈ N, mi ≥ 2, and
• (c) the utility payoffs for each player i given as a function ui : S1 × . . . ×SN →R.

Denote the set of strategy profiles in G as S := S1 ×. . .×SN . Throughout this paper, all considered multiplayer games shall have the same number of players N and the same set of strategy profiles S. Hence, any game G will be determined by its utility functions {ui}i∈[N]. The players choose their strategies simultaneously and they cannot communicate with each other. A utility function ui can be summarized by its pure strategy outcomes for player i, captured as an N-dimensional tensor or array {ui(k)}k∈S .

As usual, we allow the players to randomize over their pure strategies, called mixed strategies. Then, player i's strategy space extends to the set of probability distributions ∆(Si ) := {si = (sik )k ∈ Rmi ≥0 : ∑k∈[mi] sik = 1} over Si . A tuple s = (s1 , . . . , sN ) ∈ ∆(S1 ) × . . . × ∆(SN ) =: ∆(S) is called a mixed strategy profile 2 in G. The utility payoff of player i under profile s is defined as the player's utility payoff in expectation ui(s) := ∑k∈S s1k1 · . . . · sNkN · ui(k). The goal of each player is to maximize her utility.

We will abbreviate with S-i the set that consists of all possible pure strategy choices k-i = (k1, . . . , ki-1, ki+1, . . . , kN) of the opponent players (resp. ∆(S-i ) for the set of mixed strategy choices s-i = (s1 , . . . , si-1 , si+1 , . . . , sN )). We will also use ui(ki, k-i) instead of ui(k) to stress how player i can only influence her own strategy when it comes to her payoff (resp. ui(si , s-i ) instead of ui(s)).

Definition 2.1. The best-response set of player i to the opponents' strategy choices s-i is defined as

Best-response strategies capture the idea of optimal play against the other player's strategy choices. The most popular equilibrium concept in non-cooperative games is based on best responses.

2 Not to be confused with a correlated strategy: In our notation, ∆(S) itself is not a simplex of high dimension but only the product of N lower-dimensional simplices.

Definition 2.2. A strategy profile s ∈ ∆(S) to a game G = {ui}i∈[N] is called a Nash equilibrium if for every player i ∈ [N] we have si ∈ BRui (s-i ).

By a result of Nash [1950], any such multiplayer game G admits at least one Nash equilibrium.

3 Decision Problems about Best Responses

In this section we show that two decision problems about best responses are hard for N-player games, when N ≥ 3. To our knowledge, these results are novel.

For computational problems involving N-player games G with strategy sets (Si )i∈[N] and utility functions (ui)i∈[N], we are interested in their computational complexities in terms of |S| and the binary encoding of all utility payoffs (ui(s))s∈S,i∈[N]. For that, we require that utility payoffs take on rational values only.

First, we consider the problem of deciding whether a mixed strategy of a player is ever a best response to some mixed strategy profile of the opponent players. In its computationally easiest form, we may formulate it as the following.

Definition 3.1 (CHECKIFEVERBR). Given a 3-player normal-form game, do there exist mixed strategies r ∈ ∆(S2 ) of PL2 and s ∈ ∆(S3 ) of PL3 such that pure strategy 1 of PL1 is a best response to (r, s)?

This is different from determining the best responses of a player to a given strategy profile of the opponents, a task that can be solved in polynomial time. Our problem is related to rationalizable strategies [Bernheim, 1984; Pearce, 1984] - a concept that is based on the idea that a rational player can and should eliminate any strategy that is not a best response to some belief over what her opponents may play.

Proposition 3.2. CHECKIFEVERBR is NP-hard.

The analogous formulation of CHECKIFEVERBR for the case of 2-player games can be efficiently decided by solving a system of linear (in-)equalities. We can recover polynomialtime solvability for many-player games if we allow the opponents to play in a coordinated fashion (cf. correlated strategies). On a related note, Pearce [1984][Lemma 3] shows that a strategy s∗ is a best response to some correlated strategy of the opponents if and only if s∗ is not strictly dominated by a mixed strategy.

We prove Proposition 3.2 by a reduction from the Balanced Complete Bipartite Subgraph problem. This decision problem asks whether a given weighted bipartite graph G = (V ∪W, E) has subsets V ∗ ⊆ V and W ∗ ⊆ W of given size K ∈ N that are fully connected, that is, (v,w) ∈ E for all v ∈ V ∗ ,w ∈ W ∗ . This problem is known to be NPcomplete [Garey and Johnson, 1990][GT24].

Proof sketch of Proposition 3.2. Given an instance G = (V ∪ W, E) and K of the Balanced Complete Bipartite Subgraph problem, construct a three player game where PL2 has strategy set V and PL3 has strategy set W. PL1 will have the following strategies: Strategy "1" which will be the subject of interest in CHECKIFEVERBR, one strategy for each node in G, and one strategy for each edge (v, w) ∈ V ×W that is not present in G. The utility payoffs of PL1 will be carefully constructed such that strategy 1 is a best response to mixed strategies (r, s) of PL2 and PL3 if and only if the support of r and s form subsets V ∗ and W ∗ that make a balanced complete bipartite subgraph of G. To that end, we make strategy v (resp. w) of PL1 very attractive for PL1 in the case that PL2 (resp. PL3) plays their corresponding strategy v (resp. w) with too much probability. Moreover, we make a strategy (v,w) /∈ E of PL1 very attractive for PL1 in the case that PL2 and PL3 both play their corresponding strategies v and w with any significant probability at all. Intuitively, these two conditions accomplish that in any potential certificate (r, s), PL2 and PL3 will mix over at least K strategies and, moreover, they will only put non-negligible weight on strategies v and w if (v, w) ∈ E.

Based on the hardness of CHECKIFEVERBR, we can prove co-NP-hardness of deciding best-response equivalence.

Definition 3.3 (CHECKIFSAMEBRS). Given two 3-player normal-form games with strategy set S1 × S2 × S3 , do they have the same best-response sets?

Theorem 1. CHECKIFSAMEBRS is co-NP-hard.

Proof sketch. Given a game instance G of CHECKIFEVERBR, construct another game G′ by changing the utility that PL1 receives from playing strategy 1 to something worse than the lowest payoff present in G. If a best-response set changed from G to G′ , then it must also be the case that strategy 1 for PL1 was added or removed from that best-response set. The former cannot happen because strategy 1 is strictly dominated for PL1 in G′ which prevents it from ever being a best response. Thus, G and G′ will have the same bestresponse sets if and only if strategy 1 is never a best-response strategy in G.

Together with prior work found in the literature, Theorem 1 will guide us in the next sections when it comes to the types of game transformations that we may consider for preserving key game-theoretic characteristics. We believe, however, that Proposition 3.2 and Theorem 1 are also of independent interest for algorithmic game theory and AI research.

4 Preliminaries on Game Transformations

4.1 Positive Affine Transformations

The following lemma (or restricted versions of it) is a wellknown result for 2-player games. 3 Here, the notation 1n ∈ Rn stands for the vector with all ones as its entries.

Lemma 4.1. Let (A,B) be an m1 × m2 bimatrix game and take arbitrary scalars α1, α2 > 0 and vectors c1 ∈ Rm2 , c2 ∈ Rm1 . Define

Then (A′ ,B′ ) has the same best-response sets as (A,B). Thus, both games have the same Nash equilibrium set.

3 See Heyman and Gupta [2023][Lemma 2.1], Maschler et al. [2013][Theorem 5.35], [Moulin and Vial, 1978][Theorem 1], Harsanyi and Selten [1988][Chapter 3] or Bas¸ar and Olsder [1998][Proposition 3.1].

The game transformations in Lemma 4.1 are called (2player) positive affine transformations (PATs). An explicit example of a 2-player PAT is one that transforms a 2 × 2 game (A,B) into

The intuition behind Lemma 4.1 is as follows: PL1 wants to maximize her utility given the strategy of PL2. A positive rescaling of u1 will change the utility payoffs but not the utility-maximizing strategies. The same holds true if we add utility payoffs to u1 that are only dependent on the strategy choice of her opponent PL2, because that would make a constant shift in terms of the decision variables of PL1. Let us generalize PATs to multiplayer games.

Definition 4.2. A positive affine transformation (PAT) specifies for each player i a scaling parameter αi ∈ R, αi > 0, and translation constants C i := (cik-i )k-i∈S-i for each choice of pure strategies from the opponents. The PAT HPAT = {αi ,C i}i∈[N] then takes any game G = {ui}i∈[N] as an input and returns the transformed game HPAT(G) = {u′i }i∈[N] with utility functions

Multiplayer PATs also preserve the best-response sets and Nash equilibrium set, which we prove in the full version of this paper for completeness.

Lemma 4.3. Take a PAT HPAT = {αi ,C i}i∈[N] and any game G = {ui}i∈[N]. Then, the transformed game HPAT(G) = {u′i }i∈[N] has the same best-response sets as the original game G. Consequently, HPAT(G) also has the same Nash equilibrium set as G.

PATs have found much success as a tool for simplifying a given game precisely because of this property. We want to investigate which other game transformations also preserve the best-response sets or the Nash equilibrium set. If we found more of these transformations, we could use them to, e.g., further increase the class of efficiently solvable games.

4.2 Separable Game Transformations

In this paper, we will focus on the following space of game transformations. We discuss in Section 5 why this forms a maximally large search space within which we may still reasonably hope to find game transformation that are equivalence-preserving and efficiently computable.

Definition 4.4. A separable game transformation H = {Hi }i∈[N] specifies for each player i a collection of functions Hi := {hik : R → R}k∈S , indexed by the different pure strategy profiles k.

The transformation H can then be applied to any N-player game G = {ui}i∈[N] with strategy set S to construct the transformed game H(G) = {Hi (ui)}i∈[N] where Hi (ui) : S →R, k ↦→ hik (ui(k)).

Observe that the utility payoff of player i in the transformed game H(G) from the pure strategy outcome k is only a function of the utility payoff from that same player in that same pure strategy outcome of the original game G.

We extend the utility functions Hi (ui) to mixed strategy profiles s ∈ ∆(S) as usual through Hi (ui)(s) := ∑k∈S s1k1 · . . . · sNkN · hik (ui(k)). To simplify future notation, we will often use hiki,k-i to refer

to hik .

Remark 4.5. A multiplayer positive affine transformation HPAT = {αi ,C i}i∈[N] makes a separable game transformation H = {Hi }i∈[N] by setting

In the following Definitions 4.6 and 4.7, we define the universally preserving characteristics that we are interested in.

Definition 4.6. Let H = {Hi }i∈[N] be a separable game transformation. Then we say that H universally preserves Nash equilibrium sets if for all games G = {ui}i∈[N] the transformed game H(G) = {Hi (ui)}i∈[N] has the same Nash equilibrium set as G.

Definition 4.7. Let map Hi come from a separable game transformation H. Then we say that Hi universally preserves best responses if for all utility functions ui : S → R and for all opponents' strategy choices s-i ∈ ∆(S-i ):

Lemma 4.3 states that the maps Hi of a PAT universally preserve best responses. Note, moreover, that by definition of a Nash equilibrium, a game transformation H = {Hi }i∈[N] will universally preserve Nash equilibrium sets if for every player i the map Hi universally preserves best responses. Therefore, being a PAT implies Definition 4.7 implies Definition 4.6. In Section 6 we will show the reverse implication chain for game transformations that are separable.

5 Discussion of Restrictions

The space of separable game transformations forms a vast landscape in which we may search for universally preserving transformations. This can be seen from the game transformation example HEx of Section 1.2. However, one might still ask why this paper does not expand its attention to non-separable game transformations. We will discuss that in this section.

For example, consider a game transformation that introduces or removes duplicate strategies or dummy players. Note that this would require the transformations to have the power to change the strategy sets and player set. Nonetheless, these specific examples are well-behaved in the sense that they alter the Nash equilibrium set (or best responses) in an easily describable manner. Abdou et al. [2022], for example, managed to characterize how selected examples of these transformations interact with various methods of decomposing a game. Transformations that change the strategy sets and player set also appear in the literature under the term Nash homomorphism, and they have been of use for complexity-theoretic studies, e.g., of win-lose games [Abbott et al., 2005] or ranking games [Brandt et al., 2006]. Suffice to say, once we allow for game transformations to arbitrarily change the game structure, i.e. the player set and strategy sets, it is not straightforward to define anymore under what conditions two games of different game structure should be considered "strategically equivalent". This makes such general game transformations prohibitively complex (or impossible) to analyze beyond a case by case basis. Therefore, and in accordance with most of the literature on strategic equivalence between games [Moulin and Vial, 1978; Morris and Ui, 2004; Du, 2008; Liu, 1996], we restrict our attention to games whose game structures are directly comparable.

Indeed, game transformations that preserve the player set and the strategy sets form an interesting search space because Definitions 4.6 and 4.7 can be directly extended to it and because within that search space, some of our following results will not hold true anymore. Compare the Prisoner's Dilemma with the Quality game, as presented by von Stengel [2022]:

Both games have the same unique Nash equilibrium, namely, where PL1 plays the bottom row and PL2 plays the right column. But the best response of PL2 to PL1 playing the top row is different in the two games. This example illustrates the fact that strictly dominated strategies will never be a best response, and so they will never appear in a Nash equilibrium (nor in a best-response set). Therefore, we can think of a game transformation procedure that iteratively detects strictly dominated strategies and sets their payoffs to a large negative number. This transformation universally preserves Nash equilibria, but it does not universally preserve best-response sets. Note that this game transformation is not separable because its maps hik now need to take all utility payoffs of the game into consideration, and not only what utility player i receives from strategy profile k.

In a similar fashion, one may think of best-responsepreserving transformations that are not PATs. This was studied extensively by Liu [1996], who discusses the following example of 3 × 2 payoff matrices of PL1 in 2-player games:

As visualized by Figure 1, the best responses of PL1 to any mixed strategy of PL2 are the same in A and A′ . However, A′ cannot be obtained from A through a PAT: If there were such a PAT, then the payoff from profile (2, 1) requires a shift of c11 = 2. Hence, the payoff from profile (1, 1) requires a scaling of α1 = 23 . But these components of a positive affine transformation do not work out for the payoff from profile (3, 1), leaving us with a contradiction.

Liu [1996] develops a polynomial-time method, called biaffine transformation, that determines whether two 2-player normal-form games have the same best-response sets. The procedure detects which strategies and strategy pairs are essential, and derives that only the essential pairs need to be in a positive affine relationship. Hence, the method includes PATs, but it is also more powerful than that. Liu's dissertation (1995) extends those ideas to N-player games (N ≥ 3). But in N-player games, the method downgrades to a sufficient condition: Two N-player games (N ≥ 3) may have the same best-response sets while not being a quasi-affine transformation of each other. Furthermore, their method becomes computationally inefficient. In fact, we have shown in Section 3 more generally that determining whether two 3-players games have the same BR sets is co-NP-hard.

Liu concludes with an immediate open problem for future work: to characterize games with the same Nash equilibria. To that end, Du [2008] proves that it is NP-complete to decide whether two 2-player games share a common Nash equilibrium, and that it is co-NP-hard to decide whether two 2player games have the same Nash equilibrium set.

In light of these negative results about characterizing bestresponse equivalence and Nash equilibrium equivalence in full generality - assuming the well-accepted complexity belief co-NP ̸= P - we restrict our focus to a subclass of equivalence-preserving transformations based on separability. We argue that among naturally defined subclasses, separable game transformations constitute a maximal subclass for which it is still open whether it contains tractable and equivalence-preserving transformations aside from PATs.

6 Transformations that Preserve Nash Equilibrium Sets or Best-Response Sets

To our knowledge, the results of this section are all novel unless explicitly stated otherwise. They can be summarized in the following statement.

Theorem 2. Let H = {Hi }i∈[N] be a separable game transformation. Then:

H universally preserves Nash equilibrium sets (i)

Lemma 4.3 gives (iii) =⇒ (i), and so the novel part of Theorem 2 is the implication chain (i) =⇒ (ii) =⇒ (iii). The key property that enables us to develop this chain is that we require the separable game transformations H = {Hi }i∈[N] to be universally applicable, no matter the game G = {ui}i∈[N] we have at hand.

We shall state two algorithmic consequences of Theorem 2.

Corollary 6.1. Given two normal-form games, we can decide within polynomial time whether one is a transform of the other through an equivalence-preserving separable game transformation.

This is because deciding whether a game is a PAT transform of another reduces to solving a linear (in-)equation system for the variables {αi ,C i }i∈[N]. A case distinction is needed for solution points that take on values αi = 0.

Corollary 6.2. Given a 2-player normal-form game G, we can find a transform G′ of it (if it exists) via an equivalencepreserving separable game transformation, such that G′ is a zero-sum or rank-1 game. With that, a Nash equilibrium for G can be computed subsequently. Both take polynomial time.

This follows from the results in [Heyman and Gupta, 2023; Adsul et al., 2021].

Before tackling Theorem 2, let us characterize a special property that a game transformation can satisfy in which the strategy choice of player i does not influence the map that is being used to transform her utilities.

Definition 6.3. Let map Hi come from a separable game transformation H. Then we say that Hi only depends on the strategy choices of the opponents if for all pure strategy choices k-i ∈ S-i of the opponents, we have the map identities hi1,k-i = . . . = himi,k-i : R→R.

Next, we can show (i) =⇒ (ii).

Proposition 6.4. Let H = {Hi }i∈[N] be a separable game transformation that universally preserves Nash equilibrium sets and consider the map Hi of a player i. Then Hi only depends on the strategy choices of the opponents. Furthermore, Hi universally preserves best responses.

Proof sketch.

1. Such a universally preserving transformation H should in particular not change the Nash equilibrium set for a trivial game in which all players receive the same constant utility z ∈ R from all strategy profiles. In such a game, the whole strategy set S will make the Nash equilibrium set. For that to also be the case in the transformed game, we show for every player i, that the transformations maps hi1,k-i , . . . , himi,k-i must all evaluate the same on any input value z.
2. Let ui be an arbitrary utility function of player i. Complete ui to a full game G by setting the utilities of all other players to the constant payoff of 0. This makes any strategy sj of another player j ̸= i always a best-response strategy in G. We can then show that this must also hold in the transformed game H(G), using the first conclusion. Therefore, we get the following equivalence chain:
3. (a) a strategy si of player i is a best response to a profile s-i of the opponent players and with respect to ui if and only if
4. (b) (si , s-i ) is a Nash equilibrium of G if and only if
5. (c) (si , s-i ) is a Nash equilibrium of H(G) if and only if
6. (d) si a best response to s-i with respect to Hi (ui).

The first conclusion captures the intuition that if the maps hik from Hi would depend on the strategy choice of player i, then in the transformed game H(G), player i may need to adjust her strategy choice to those hik that map payoffs to high values. This would affect the strategic decision making of player i and therefore the Nash equilibrium set. Similar reasoning provides us with a related (but independent) result:

Lemma 6.5. If mapHi universally preserves best responses, then Hi only depends on the strategy choices of the opponents.

Due to Proposition 6.4, we can transition to the analysis of transformation maps Hi that universally preserve best responses. Thus from now on, our results also become relevant to game theory research that focuses on best-response sets, such as best-response dynamics or fictitious play.

Proposition 6.4 moreover allows us to restrict our analysis to the map H1 for PL1 w.l.o.g. because any results for H1 will analogously also hold for maps H2 , . . . ,H N . By Lemma 6.5, we can also drop the dependence of H1 on k1 and write H1 := {h1k-1 : R→R}k-1∈S-1 .

For each pure-strategy map h1k-1 we introduce its distance distortion function which takes two utility values and measures their distance after a h1k-1 -transformation:

The following lemma reveals an important preliminary observation on how the distance distortion functions ∆h1k-1 relate to each other. It highlights how the distorted utility distances are connected upon a strategy change of a player j ̸= 1 from, e.g., some pure strategy kj ̸= 1 to their first pure strategy 1 ∈ [mj]. It is again crucial that H1 preserves best responses universally in order to deduce these global properties of and connections between the maps within H1 .

Lemma 6.6. Suppose transformation map H1 universally preserves best responses. Take a player j ∈ [N] \ {1} and profile k-1 ∈ S-1 with kj ̸= 1. Define k′-1 ∈ S-1 to be the same as k-1 except for player j's choice which shall be set to k′j = 1. Then, for all z, z′ ,w,w′ ∈ R:

Proof sketch. Construct a utility function u1 for each set of values for j, k-1, z, z′ , w, and w′ . Namely, set u1(1, k-1) := z and u1(1, k′-1 ) := w′ , and for all strategies l ∈ [m1] \ {1} set u1(l, k-1) := w and u1(l, k′-1 ) := z′ . Observe that uniformly randomizing over k-1 and k′-1 not only makes a correlated strategy of the opponents, but also a valid mixed strategy profile. Hence, the left hand side of the equivalence can be reinterpreted as strategy 1 ∈ [m1] performing better for player 1 than any other of her strategies l ∈ [m1] \ {1} if player j uniformly mixes over strategies kj and k′j and if all other players r /∈ {1, j} play their respective strategy kr ∈ [mr]. We then derive the equivalence by using that H1 preserves strategy 1 being such a best response and by using Lemma 6.5.

Next, observe that by definition, these distance distortion functions are skew-symmetric, that is, ∀ z, w ∈ R :

With the following lemma, we further tighten the connection between the pure-strategy maps h1k-1 through their distance distortion functions. Last but not least, we shine some light on how those maps h1k-1 behave individually in the subsequent lemma.

Lemma 6.7. If mapHi universally preserves best responses, then the pure-strategy maps in H1 equally distort distances. That is, ∀k-1 ∈ S-1 : ∆h1k-1 = ∆h11-1 , where 1-1 := (1, . . . , 1) ∈ S-1 .

Proof sketch. Make iterative use of Lemma 6.6 for all other players j ̸= 1, and make use of the skew-symmetry.

Lemma 6.8. If mapHi universally preserves best responses, then for all k-1 ∈ S-1 :

1. map h1k-1 is strictly increasing, and
2. map h1k-1 distorts distances independently of their reference points:

Proof sketch. For the first conclusionmake use of Lemma 6.6 for values z′ = w′ , and of Lemma 6.7. For the second conclusion, utilize skew-symmetry together with the same two lemmata.

With Lemmata 6.7 and 6.8, we can finally show that positive affine transformations are the only game transformations that universally preserve best responses. Intuitively speaking, the second conclusion of Lemma 6.8 states that taking a step of length λ in the domain space consistently maps to taking a step of some other length in the range space, independently of the base point z from which we take such a step.

This brings us to two known results from the analysis literature. Recall that a function h : R → R is called linear if there exists some a ∈ R such that ∀z ∈ R : h(z) = az. A function h : R → R is said to be additive if it satisfies ∀x, y ∈ R : h(x+ y) = h(x) +h(y).

Lemma 6.9 ([Darboux, 1875; Reem, 2017]). If a map h : R→R is monotone and additive, then it is also linear.

Corollary 6.10. Let h : R → R be monotone and satisfy for all z, z′ , λ ∈ R : h(z + λ) - h(z) = h(z′ + λ) - h(z′ ). Then h is affine linear, i.e., there exist some a, c ∈ R such that for all ∀z ∈ R : h(z) = az + c.

This brings us to the completion of this section.

Proof sketch of Theorem 2.

Implication (iii) =⇒ (i) follows from Lemma 4.3, and implication (i) =⇒ (ii) follows from Proposition 6.4. For (ii) =⇒ (iii), recall that by symmetry, our results for H1 hold analogously for all maps Hi . By Lemmata 6.5 and 6.8, the maps hik = hik-i satisfy the conditions of Corollary 6.10. Thus, there exist parameters aik-i , cik-i ∈ R for each k-i ∈ S-i such that ∀z ∈ R : hik-i (z) = aik-i · z + cik-i .

Lemma 6.7 implies aik-i = ai1-i for all k-i ∈ S-i . Therefore, we only have to keep track of one scaling parameter αi for all the maps within Hi . With the first conclusion of Lemma 6.8, we obtain αi > 0. Putting everything together, we have shown that H = (H1 , . . . ,H N ) makes a positive affine transformation.

Theorem 2 gives two novel equivalent characterizations of PATs that highlight their special status among game transformations: PATs are the only separable game transformations that always preserve the Nash equilibrium set or, respectively, the best-response sets.

One way to circumvent this result is to focus on game transformations that we only care to apply on particular subclasses of N-player games. Preferably, the game properties defining such a subclass would be generic enough to still contain "most" games. On the other hand, one may instead also consider non-separable game transformations as discussed in Section 5.

7 Further Related Literature

Much work has gone into identifying when two games can be considered strategically equivalent.

Strategic similarity, for example, is an important aspect of Potential Games (cf. Monderer and Shapley [1996]). Morris and Ui [2004] noted that a game G is a weighted potential game if and only if it is the PAT transformation of an identical interest game 4 . They also characterized when two given games are best-response equivalent, better-response equivalent or von Neumann-Morgenstern equivalent. The former and latter are directly tied to our concepts of preserving bestresponse sets and to PATs. Unfortunately, we were not able to base the second part of Theorem 2 on the insights from Morris and Ui because their characterization for best-response equivalence only holds for games that satisfy specific properties.

4 Identical interest game: Given an action profile s, each player shall receive the same utility from s.

Hammond [2005] described that the strategic decisionmaking in a game in mixed strategies does not depend on the player's numerical utility values, but solely on the preferences that the utility functions induce over the strategies. In the full version of this paper, we give some further background on utility theory in order to put Hammond's work into our context. Using the Expected Utility Theorem - cf., e.g., MasColell et al. [1995] - Hammond deduced that utility functions that induce the same preferences can only differ up to a positive affine transformation. Note that the property of preserving the player's preferences is, in general, strictly harder to satisfy than preserving best responses (and, hence, Nash equilibria). Thus, our Theorem 2 generalizes their result to the broader question of strategic equivalence.

Moving to more broadly related work, Gabarr´o et al. [2011; 2013] gave several complexity-theoretic results for the problem of deciding whether two pure strategy games are isomorphic w.r.t. a notion of game transformation that can help us understand the symmetries within a game [Harsanyi and Selten, 1988, Chapter 3]. McKinsey [1951] and Chang and Tijs [2006] studied two notions of game equivalency specific to cooperative games.

Finally, there are other lines of related research that work more explicitly with different notions of transforming a game and preserving strategic features [Thompson, 1952; Kohlberg and Mertens, 1986; Elmes and Reny, 1994; Casajus, 2003; Pottier and Nessah, 2014; Wu et al., 2022].

8 Conclusion

In this paper, we first gave hardness results about deciding whether a strategy constitutes a best response or whether two games have the same best-response sets. Next, we introduced separable game transformations for multiplayer games, and define the properties (i) universally preserving Nash equilibrium sets and (ii) universally preserving best responses. It is well-known that PATs universally preserve Nash equilibrium sets. We showed that separable game transformations which universally preserve Nash equilibrium sets also universally preserve best responses. In the subsequent results, we derived further that if a separable game transformation universally preserves best responses then it is a positive affine transformation.

When faced with a strategic interaction it can be highly beneficial to consider equivalent variations of it that are easier to analyze. In this paper, we shed light on why PATs have become the go-to transformation method for that purpose, reinforcing their standing as the standard off-the-shelf approach. The current literatures on game theory and on decision making in AI are lacking methods to detect or generate strategically equivalent games, and we hope that our results can serve as guidance to the development of any such detection or generation toolkit.

Acknowledgments

We want to thank Sebastian van Strien for the valuable discussions related to this project and to thank Bernhard von Stengel whose feedback inspired the development of Sections 4 and 6. We are also grateful to Vojtˇech Kovaˇr´ık, Rinor Cakaj, and the anonymous reviewers for their valuable improvement suggestions for this paper. Finally, we thank the Cooperative AI Foundation, Polaris Ventures (formerly the Center for Emerging Risk Research) and Jaan Tallinn's donor-advised fund at Founders Pledge for financial support.