Iterative elimination of strictly dominated strategies

The iterative elimination of strictly dominated strategies also iterative elimination of strictly dominated strategies or iterative elimination of strictly dominated strategies is an iterative method in game theory for determining Nash equilibria in games in normal form .

Basics

In order to understand the concept of iterative elimination of the strictly dominated strategies, the nature of a dominated strategy must first be explained. A dominated strategy is a strategy that is of no benefit to the player and is therefore not the best answer to an opponent's strategy. It is dominated by a so-called dominant strategy . Formally, strict dominance can be represented as follows:

Be a two person game with the payoff functions of player 1 and 2 and the strategy rooms and player 1 and 2. Continue to be and possible strategies for player 1 (i.e. ). ${\displaystyle G=\{S_{1},S_{2};u_{1},u_{2}\}}$ ${\displaystyle u_{1},u_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle s_{1}'}$ ${\displaystyle s_{1}''}$ ${\displaystyle s_{1}',s_{1}''\in S_{1}}$

Then is strictly dominated by if: ${\displaystyle s_{1}'}$ ${\displaystyle s_{1}''}$

${\displaystyle u_{1}(s_{1}',s_{2})<u_{1}(s_{1}'',s_{2})}$

for each strategy of the other player. ${\displaystyle s_{2}\in S_{2}}$

The procedure

The iterative elimination of strictly dominated strategies describes the successive elimination of dominated strategies until there are no more dominated strategies. This method enables games to be simplified to their possible realizations, ideally to the extent that only one strategy combination remains. In this way, Nash equilibria can be found in bimatrices. In contrast to the iterative elimination of weakly dominated strategies, the result of the iterative elimination is unambiguous with strict dominance (regardless of the order of elimination). In general, strategies that survive this elimination are called rationalizable strategies.

→ Main article : Rationalizability

application

The iterative elimination of strictly dominated strategies is mainly used in complex matrix games. By highlighting irrelevant or inferior strategies, the dimension of the matrix is ​​simplified so that the game can be handled more easily.

example

The following bimatrix is ​​given

	${\displaystyle y_{1}}$	${\displaystyle y_{2}}$
${\displaystyle x_{1}}$	${\displaystyle 5}$ ${\displaystyle 3}$	${\displaystyle 6}$ ${\displaystyle 6}$
${\displaystyle x_{2}}$	${\displaystyle 4}$ ${\displaystyle 2}$	${\displaystyle 5}$ ${\displaystyle 4}$

, where , represent player 1's strategies and , represent player 2's strategies. We start with player 1. For player 1, the strategy is strictly dominated by the strategy ( is the dominant strategy ). For this reason, the strategy can be deleted and the bimatrix is ​​reduced to: ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

	${\displaystyle y_{1}}$	${\displaystyle y_{2}}$
${\displaystyle x_{1}}$	${\displaystyle 5}$ ${\displaystyle 3}$	${\displaystyle 6}$ ${\displaystyle 6}$

We continue with player 2. From the perspective of player 2, it is strictly dominated by and can therefore be deleted. The following Nash equilibrium remains: ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$

	${\displaystyle y_{2}}$
${\displaystyle x_{1}}$	${\displaystyle 6}$ ${\displaystyle 6}$

Thus, by successively eliminating the dominated strategies, the Nash equilibrium was found. With this method, even complex bimatrices can be reduced to their realizations. ${\displaystyle NGG:(x_{1},y_{2})}$

Individual evidence

1. ↑ Manfred J. Holler, Gerhard Illing: Introduction to Game Theory, p. 105
2. ↑ Florian Bartholomae, Marcus Wiens: Game theory: An application-oriented textbook p. 71

See also

• Solution concept