Game Theory 101: Strategy Dominance

August 29, 2023

2 months ago, I had the opportunity to study Game Theory at Seoul National University over the summer, and it was a blast. While game theory is not exactly a software/tech-centric topic, I found it to be a refreshing pursuit that still maintains some links to my main area of study, Computer Science. This blog series highlights some of the important concepts that I learnt as well as my own experimentation/creations that overlap software and game theory.

Games in Game Theory

In Game Theory, there are 3 main components of a game that need to be defined, which are:

Players: Entities playing the game against each other
Strategies: The course of actions that players can take
Utility/Payoff: What players get in the outcome of the game

In normal-form games, these 3 can be modelled using a matrix.

Prisoners' Dilemma

Let us consider the simple game, Prisoners' Dilemma where there are 2 players (P1, P2) with 2 strategies, and both players play simultaneously. Each player can choose to Defect (D) or Cooperate (C), and the utility of each player is dependent on what both players played. There are 4 outcomes (4 possible combinations of what P1 and P2 plays), and we represent the game matrix as such:

Player 1

Player 2

	D	C
D	1,1	3,-1
C	-1,3	2,2

The rows represent the strategies that P1 can play, while the columns represent the strategies that P2 can play.

When both players play D, the outcome is (1,1), which means P1 gets 1 and P2 gets 1 utility. If P1 plays D and P2 plays C, the outcome is (3,-1), which means P1 gets 3 while P2 gets -1 utility.

The utility of a Player i, $u_{i}$ can be formally denoted as:

u_{i}(s_{i}, s_{-i})

Where $s_{i}$ is the strategy player i plays, and $s_{-i}$ is the strategies played by all other players except player i. For example,

u_{1}(D, C) = 3

In game theory, a common assumption is that players are rational; a player is rational if he is motivated by maximizing his own utility $u$ .

Dominance

Not all strategies are equal; some are better than others. One way we can quantify this is through the concept of dominance. There are two types of dominace, strict dominance and weak dominance.

Strict Dominance

Strategy $s_{i}$ strictly dominates $s_{i}'$ if and only if:

u_{i}(s_{i}, s_{-i}) > u_{i}(s_{i}', s_{-i}) \text{ for all values of $s_{-i}$.}

This means that no matter what strategies that our opponents play ( $s_{-i}$ ), playing $s_{i}$ will yield player i a strictly better utility than playing $s_{i}'$ .

Rationally, we would want to maximize the utility and therefore there is no incentive to play $s_{i}'$ over $s_{i}$ under any circumstances. It is never rationalizable to play a strictly dominated strategy.

Weak Dominance

Strategy $s_{i}$ weakly dominates $s_{i}'$ if and only if:

u_{i}(s_{i}, s_{-i}) \geq u_{i}(s_{i}', s_{-i}) \text{ for all values of $s_{-i}$.}

This means there are some scenarios where $s_{i}$ yields higher utility than $s_{i}'$ , and some scenarios where the utility of playing $s_{i}$ and $s_{i}'$ are equal (But no scenario where utility of playing $s_{i}$ is less than $s_{i}'$ ).

It is still rational to play weakly dominated strategies, as there may be some scenarios where it a weakly dominated strategy is a best response (and hence part of a Nash Equilibrium), but that is a topic for another post.

Iterative Elimination of Strictly Dominated Strategies

Since we have established that it is never rationalizable to play strictly dominated strategies, we can eliminate them from the entire game (i.e. do not consider them at all).

Once we eliminate strictly domianted strategies, we will have a reduced game with less rows/columns, and we can once again check for strictly dominated strategies and continue to eliminate them until there are none left. This process is called Iterative Elimination of Strictly Dominated Strategies.

For example, in Prisoners' Dilemma, we can see that D strictly dominates C:

When $s_{-1} = C$ ,

u_1(D, C) = 3\newline u_1(C, C) = 2\newline u_1(D, C) > u_1(C, C)

When $s_{-1} = D$ ,

u_1(D, D) = 1\newline u_1(C, D) = -1\newline u_1(D, D) > u_1(C, D)

Therefore,

u_1(D, s_{-1}) > u_1(C, s_{-1}) \text{ for all values of $s_{-1}$}

and hence strategy D strictly dominates C for player 1. The reduced game now takes the form:

	D	C
D	1,1	3,-1

Now we can check if D strictly dominates C for player 2 as well:

When $s_{-2} = D$ ,

u_2(D, D) = 1\newline u_2(C, D) = -1\newline u_2(D, D) > u_2(C, D)

Therefore in this reduced game, D strictly dominates C for player 2. Hence we are left with the game:

	D
D	1,1

In Prisoners' Dilemma, the only rationalizable strategy for both players is to defect and play D. This outcome of the game (D, D) also happens to be the Nash Equilibrium, which is a topic for future discussion.

Order of elimination does not matter

In iterative elimination of strictly dominated strategies, the order in which we eliminate the strategies does not matter. In Prisoners' Dilemma, we could have eliminated C for player 2 first followed by C for player 1 and get the same reduced final game.

We need to show that an elimination of a strictly dominated strategy does not change the dominance relationship between the remaining strategies.

We will consider two cases, first where eliminating a strategy of player i does not change the dominance relationship of his own strategies, and second where eliminating a strategy of another player does not change the dominance relationship of player i's strategies.

Case 1

Suppose player i has strategies A, B, C with the following dominance relationships:

A strictly dominates B
B strictly dominates C

One might think that if we eliminate B before C, we will not be able to eliminate C. However, consider:

u_i(A, s_{-i}) > u_i(B, s_{-i}) \text{ for all values of $s_{-i}$}\newline u_i(B, s_{-i}) > u_i(C, s_{-i})\text{ for all values of $s_{-i}$}

and hence,

u_i(A, s_{-i}) > u_i(C, s_{-i})\text{ for all values of $s_{-i}$}

This means that strict dominance is transitive, i.e. if A SD'es B and B SD'es C, A must SD'es C. Therefore, it does not matter if we eliminate strategy B or C of player i first, as the remaining strategy is still SD'ed by A and will get eliminated.

Case 2

Suppose we have the payoff vectors, $v_i$ and $v_i$ ' in response to playing $s_i$ and $s_i'$ respectively against n different strategies by the opponent:

v_i = (u_1, u_2, u_3, \dots, u_n) \newline v_i' = (u_1', u_2', u_3', \dots, u_n')\newline

Where $u_i$ and $u_i'$ are utilities for playing $s_i$ and $s_i'$ against the $i^{th}$ strategy by the opponent.

Suppose $s_i$ strictly dominates $s_i'$ , then:

u_1 > u_1'\newline u_2 > u_2'\newline \vdots\newline u_n > u_n'

Suppose now that we eliminate the $i^{th}$ strategy (which can be any value from 1 to n) from the opponent due to the fact that it was strictly dominated. Now, the new values of $v_i$ and $v_i'$ in the reduced game takes the form:

v_i = (u_1, u_2, u_3, \dots, u_{i-1}, u_{i+1}, \dots, u_n) \newline v_i' = (u_1', u_2', u_3', \dots, u_{i-1}, u_{i+1}, \dots, u_n')\newline

Since all values in $v_i$ and $v_i'$ remain the same with the exception of $u_i$ which no longer exists, we conclude from the previous expression that $s_i$ still strictly dominates $s_i'$ . Hence elimination of an opponent's strategy does not affect the dominance relationship of our current strategies.

There are much more mathematical and formal proofs out there, but this is sufficient for us to get an intuition of why order does not matter.

Creating a Program to perform Iterative Elimination

It is clear to see from the above that given an input matrix, we can create a program that performs iterative elimination of strictly dominated strategies and return a reduced game matrix. The steps roughly correspond in this manner:

With the input matrix, check player 1's strategies against each other, and remove all $s_i'$ where $v_i$ for some strategy $s_i$ is greater than $v_i'$ . In a programming context, this corresponds to a row-wise comparison of the matrix and removing any rows where there exists another row whose values at all indices are greater.
With the previous result as the input matrix, check player 2's strategies against each other, and remove all $s_i'$ where $v_i$ for some strategy $s_i$ is greater than $v_i'$ . In a programming context, this corresponds to a column-wise comparison of the matrix and removing any columns where there exists another column whose values at all indices are greater.

I have made a short program in Python using Jupyter Notebook demonstrating this which can be found here. This method yields the same result even in larger games with larger matrices.

Closing Thoughts

We have discussed some basic terminology as well as how we can notate simple games using matrices. We also explored the concept of dominance to quantify how certain strategies are better than others, and how it is never rationalizable to choose strictly dominated strategies.

The technique of Iterative Elimination of Strictly Dominated strategies highlighted here can reduce the game to a smaller number of outcomes, which can empower us to make better decisions for certain games.

Other topics that will be explored in the future inlude best responses as well the Nash Equilibrium. Stay tuned!