Ingame theory, amax-dominated strategy is astrategy that is never abest response to any possiblestrategy profile of the other players. This means there is no situation in which the strategy is optimal to play, even if it is not strictly worse than another strategy in every case.

The concept generalizes the notion of astrictly dominated strategy, which is a strategy that always yields a lower payoff than some other strategy, no matter what the other players do. Every strictly dominated strategy is max-dominated, but not every max-dominated strategy is strictly dominated. For example, suppose strategy A gives the same payoff as another strategy B against some opponent choices, but never gives a higher payoff than B—and is strictly worse in some cases. In this case, A is never a best response, so it is max-dominated, even though it is not strictly dominated.

A strategy${\displaystyle s_i\in S_i}$ of player${\displaystyle i}$ ismax-dominated if for every strategy profile of the other players${\displaystyle s_{-i}\in S_{-i}}$ there is a strategy${\displaystyle s_i^{\mathrm{\prime }}\in S_i}$ such that${\displaystyle u_i(s_i^{\mathrm{\prime }},s_{-i})>u_i(s_i,s_{-i})}$. This definition means that${\displaystyle s_i}$ is not abest response to anystrategy profile${\displaystyle s_{-i}}$, since for every such strategy profile there is another strategy${\displaystyle s_i^{\mathrm{\prime }}}$ which gives higher utility than${\displaystyle s_i}$ for player${\displaystyle i}$.

If a strategy${\displaystyle s_i\in S_i}$ isstrictly dominated by strategy${\displaystyle s_i^{\mathrm{\prime }}\in S_i}$ then it is also max-dominated, since for every strategy profile of the other players${\displaystyle s_{-i}\in S_{-i}}$,${\displaystyle s_i^{\mathrm{\prime }}}$ is the strategy for which${\displaystyle u_i(s_i^{\mathrm{\prime }},s_{-i})>u_i(s_i,s_{-i})}$.

Even if${\displaystyle s_i}$ is strictly dominated by a mixed strategy it is also max-dominated.

A strategy${\displaystyle s_i\in S_i}$ of player${\displaystyle i}$ isweakly max-dominated if for every strategy profile of the other players${\displaystyle s_{-i}\in S_{-i}}$ there is a strategy${\displaystyle s_i^{\mathrm{\prime }}\in S_i}$ such that${\displaystyle u_i(s_i^{\mathrm{\prime }},s_{-i})\ge u_i(s_i,s_{-i})}$. This definition means that${\displaystyle s_i}$ is either not abest response or not the onlybest response to anystrategy profile${\displaystyle s_{-i}}$, since for every such strategy profile there is another strategy${\displaystyle s_i^{\mathrm{\prime }}}$ which gives at least the same utility as${\displaystyle s_i}$ for player${\displaystyle i}$.

If a strategy${\displaystyle s_i\in S_i}$ isweakly dominated by strategy${\displaystyle s_i^{\mathrm{\prime }}\in S_i}$ then it is alsoweakly max-dominated, since for every strategy profile of the other players${\displaystyle s_{-i}\in S_{-i}}$,${\displaystyle s_i^{\mathrm{\prime }}}$ is the strategy for which${\displaystyle u_i(s_i^{\mathrm{\prime }},s_{-i})\ge u_i(s_i,s_{-i})}$.

Even if${\displaystyle s_i}$ is weakly dominated by a mixed strategy it is also weakly max-dominated.

A game${\displaystyle G}$ is said to bemax-solvable if byiterated elimination of max-dominated strategies only one strategy profile is left at the end.

More formally we say that${\displaystyle G}$ is max-solvable if there exists a sequence of games${\displaystyle G_0,...,G_r}$ such that:

• ${\displaystyle G_0=G}$
• ${\displaystyle G_{k+1}}$ is obtained by removing a single max-dominated strategy from the strategy space of a single player in${\displaystyle G_k}$.
• There is only one strategy profile left in${\displaystyle G_r}$.

Obviously every max-solvable game has a unique pureNash equilibrium which is the strategy profile left in${\displaystyle G_r}$.

As in the previous part one can define respectively the notion ofweakly max-solvable games, which are games for which a game with a single strategy profile can be reached by eliminating weakly max-dominated strategies. The main difference would be that weakly max-dominated games may have more than one pureNash equilibrium, and that the order of elimination might result in different Nash equilibria.

The prisoner's dilemma is an example of a max-solvable game (as it is also dominance solvable). The strategy cooperate is max-dominated by the strategy defect for both players, since playing defect always gives the player a higher utility, no matter what the other player plays. To see this note that if the row player plays cooperate then the column player would prefer playing defect and go free than playing cooperate and serving one year in jail. If the row player plays defect then the column player would prefer playing defect and serve three years in jail rather than playing cooperate and serving five years in jail.

In any max-solvable game, best-reply dynamics ultimately leads to the unique pureNash equilibrium of the game. In order to see this, all we need to do is notice that if${\displaystyle s_1,s_2,s_3,...,s_k}$ is an elimination sequence of the game (meaning that first${\displaystyle s_1}$ is eliminated from the strategy space of some player since it is max-dominated, then${\displaystyle s_2}$ is eliminated, and so on), then in the best-response dynamics${\displaystyle s_1}$ will be never played by its player after one iteration of best responses,${\displaystyle s_2}$ will never be played by its player after two iterations of best responses and so on. The reason for this is that${\displaystyle s_1}$ is not a best response to any strategy profile of the other players${\displaystyle s_{-i}}$ so after one iteration of best responses its player must have chosen a different strategy. Since we understand that we will never return to${\displaystyle s_1}$ in any iteration of the best responses, we can treat the game after one iteration of best responses as if${\displaystyle s_1}$ has been eliminated from the game, and complete the proof by induction.

It may come by surprise then that weakly max-solvable games do not necessarily converge to a pureNash equilibrium when using thebest-reply dynamics, as can be seen in the game on the right. If the game starts of the bottom left cell of the matrix, then the following best replay dynamics is possible: the row player moves one row up to the center row, the column player moves to the right column, the row player moves back to the bottom row, the column player moves back to the left column and so on. This obviously never converges to the unique pure Nash equilibrium of the game (which is the upper left cell in thepayoff matrix).

• Dominance (game theory)

• Nisan, Noam; Schapira, Michael; Zohar, Aviv (2009),Asynchronous best reply dynamics, Berlin: Springer-Verlag, archived fromthe original on 2003-04-17. Asynchronous best-reply dynamics.[1].

• Strategy (game theory)

• Articles with short description
• Short description matches Wikidata