Game Theory — Mathematics Knowledge System

Overview

Game theory is the mathematical study of strategic interaction among rational decision-makers. It models situations — called games — where the outcome for each participant depends on the choices of all participants. Originally developed to analyse economic competition, it now pervades biology (evolutionary game theory), computer science (algorithmic game theory), political science, and philosophy. The central solution concept is the Nash equilibrium, though many other refinements and extensions exist.

Intuition

Think of two firms setting prices simultaneously. Each firm's profit depends on both its own price and the competitor's price. A Nash equilibrium is a pair of prices where neither firm wants to deviate unilaterally — given what the opponent does, each is doing the best they can. Game theory formalises this notion of mutual best response and determines when such stable outcomes exist.

Formal Definition

Definition

A finite normal-form game is defined by a set of players, a strategy set for each player, and a payoff function for each player.

G = (N, (S_i)_{i \in N}, (u_i)_{i \in N})

Normal-form game

N = \{1, 2, \ldots, n\} \text{ (players)},\quad S_i \text{ (strategy set of player } i\text{)},\quad u_i : S_1 \times \cdots \times S_n \to \mathbb{R}

Components

\sigma_i \in \Delta(S_i) = \left\{ p \in \mathbb{R}^{|S_i|} : p_s \geq 0,\; \sum_{s \in S_i} p_s = 1 \right\}

Mixed strategy (probability distribution over pure strategies)

U_i(\sigma) = \sum_{s \in S} u_i(s) \prod_{j \in N} \sigma_j(s_j)

Expected payoff under mixed strategy profile σ

Notation

Notation	Meaning
$N$	Set of players
$S_i$	Pure strategy set of player i
$u_i$	Payoff function of player i
$\sigma_i$	Mixed strategy of player i
$\Delta(S_i)$	Simplex of probability distributions over Sᵢ

Theorems

Theorem 1: Minimax Theorem (von Neumann, 1928)

\max_{\sigma_1} \min_{\sigma_2} u_1(\sigma_1, \sigma_2) = \min_{\sigma_2} \max_{\sigma_1} u_1(\sigma_1, \sigma_2)

Theorem 2: Nash's Existence Theorem

\text{Every finite normal-form game has at least one Nash equilibrium in mixed strategies}

Theorem 3: Dominant Strategy Elimination

\text{Iterative elimination of strictly dominated strategies preserves Nash equilibria}

Worked Examples

1
Check player 1's best response: if player 2 plays D, player 1 gets 1 from D vs 0 from C → D is better. If player 2 plays C, player 1 gets 3 from D vs 2 from C → D is still better.
$u_1(D, s_2) > u_1(C, s_2) \text{ for all } s_2$
2
D strictly dominates C for player 1 (and by symmetry for player 2).
$\text{D is a strictly dominant strategy}$
3
The unique Nash equilibrium is (D, D) with payoffs (1, 1), even though (C, C) gives (2, 2).
$(s_1^*, s_2^*) = (D, D)$

✓ Answer

Unique Nash equilibrium: (Defect, Defect) with payoffs (1, 1).

Practice Problems

Mediumfree response

Identify all Nash equilibria (pure and mixed) in the Battle of the Sexes game.

Common Mistakes

Common Mistake

Nash equilibrium always gives the socially optimal outcome

The Prisoner's Dilemma shows NE can be socially suboptimal — (D, D) is the unique NE yet (C, C) is Pareto superior.

Common Mistake

A dominant strategy equilibrium and a Nash equilibrium are different concepts

Any dominant strategy equilibrium is a Nash equilibrium. The converse is false: most NE are not dominant strategy equilibria.

Quiz

The minimax theorem applies to which class of games?

All cooperative gamesFinite two-player zero-sum gamesAny game with more than two playersGames with continuous strategy spaces only

A mixed strategy Nash equilibrium requires each player to:

Always play the same strategyBe indifferent among all strategies in their supportMaximise payoff against the worst-case opponentPlay the strategy that maximises expected payoff regardless of the opponent

Historical Background

The formal mathematical theory of games was founded by John von Neumann and Oskar Morgenstern in their 1944 monograph 'Theory of Games and Economic Behavior'. Von Neumann had already proved the minimax theorem for zero-sum games in 1928. John Nash's 1950 doctoral thesis generalised equilibrium to non-zero-sum games, earning him the 1994 Nobel Prize in Economics. Subsequent decades saw extensions to cooperative games, repeated games, evolutionary dynamics, and mechanism design.

1928
Von Neumann proves the minimax theorem for zero-sum games
John von Neumann
1944
Von Neumann and Morgenstern publish 'Theory of Games and Economic Behavior'
John von Neumann, Oskar Morgenstern
1950
Nash introduces Nash equilibrium for non-cooperative games
John Nash
1994
Nash, Harsanyi, and Selten awarded Nobel Prize in Economics for game theory
John Nash, John Harsanyi, Reinhard Selten

Summary

A normal-form game specifies players, strategy sets, and payoff functions.
A Nash equilibrium is a strategy profile where no player benefits from unilateral deviation.
Every finite game has at least one Nash equilibrium in mixed strategies (Nash 1950).
Zero-sum games are solved by the minimax theorem; optimal strategies are LP solutions.
Dominant strategy elimination simplifies games and preserves Nash equilibria.

References

Bookvon Neumann, J. & Morgenstern, O. — Theory of Games and Economic Behavior (1944), Princeton University Press
BookOsborne, M.J. & Rubinstein, A. — A Course in Game Theory (1994), MIT Press
BookMaschler, M., Solan, E. & Zamir, S. — Game Theory (2013), Cambridge University Press
WebsiteWikipedia — Game theory
WebsiteMathWorld — Game Theory