Introduction to Game Theory

Game theory models decision making between 2 or more competing agents, called players.

Zero Sum Games

A game is zero sum iff the sum of all players’ payoffs is 0 for every outcome.

One player’s gain equals the other’s loss.

Two-Person Matrix Games

A 2-person matrix game is represented by a payoff matrix $A$, where $A_{ij}$ is the payoff to the row player when the row player picks strategy $i$ and the column player picks strategy $j$.

• Pure strategy
  A player always picks the same single strategy.
• Mixed strategy
  A player picks among strategies according to a probability distribution.

Maximin and Minimax

• Maximin value
  The row player picks the strategy whose worst-case payoff is largest, $\underline{v} = \max_i \min_j A_{ij}$.
• Minimax value
  The column player picks the strategy whose best-case payoff to the row player is smallest, $\overline{v} = \min_j \max_i A_{ij}$.

$\underline{v} \le \overline{v}$ holds for every matrix game.

Saddle Point

A saddle point is a pure strategy pair where neither player benefits from unilaterally changing strategy.

• A saddle point exists iff $\underline{v} = \overline{v}$.
• The entry $A_{ij}$ at a saddle point is simultaneously the minimum of its row and the maximum of its column.
• The common value $v = \underline{v} = \overline{v}$ is the value of the game.

Dominance

Strategy $i$ dominates strategy $k$ for the row player iff $A_{ij} \ge A_{kj}$ for every column $j$.

• A dominated strategy is never played in optimal play.
• Deleting dominated rows and columns reduces the matrix without changing the value of the game.

Mixed Strategy Solution

When no saddle point exists, optimal play requires mixed strategies. Each player randomizes so the opponent gains nothing from knowing the distribution.

For a $2 \times 2$ matrix $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ with no saddle point:

Here:

• $p$: probability the row player picks row 1
• $q$: probability the column player picks column 1
• $v$: value of the game