Game Theory – Complete Reference Guide

1. Normal Form Games

Definition

Game with simultaneous moves by all players

Components

Players: $N = \{1, \dots, n\}$

Strategy set: $S_i$ for player $i$

Payoff: $u_i: S_1 \times \cdots \times S_n \to \mathbb{R}$

Matrix Form

$2 \times 2$ representation common:

$$\begin{pmatrix} (u_1^{1,1}, u_2^{1,1}) & (u_1^{1,2}, u_2^{1,2}) \\ (u_1^{2,1}, u_2^{2,1}) & (u_1^{2,2}, u_2^{2,2}) \end{pmatrix}$$

Payoffs ordered: (row player, column player)

2. Dominant Strategies

Strict Dominance

$s_i$ strictly dominates $s_i'$ iff:

$$u_i(s_i, s_{-i}) > u_i(s_i', s_{-i})$$

For ALL $s_{-i} \in S_{-i}$

Weak Dominance

$s_i$ weakly dominates $s_i'$ iff:

$$u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i})$$

Holds for all $s_{-i}$

Strict for at least one $s_{-i}$

Dominant Strategy Equilibrium

Profile where each player plays dominant strategy (if exists)

Rare in practice; when it exists, highly compelling prediction

Weakly dominated ≠ weak equilibrium prediction

3. Nash Equilibrium

Definition

$(s_1^*, \dots, s_n^*)$ is Nash Equilibrium if:

$$u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*)$$

For all players $i$ and all $s_i \in S_i$

Key Insight

No player wants to deviate unilaterally

Mutual best responses

Existence

Nash (1950): Every finite game has mixed NE

But may not exist in pure strategies

4. Mixed Strategies

Definition

$\sigma_i \in \Delta(S_i)$ = probability distribution over $S_i$

$$\sigma_i(s_i) \geq 0, \quad \sum_{s_i} \sigma_i(s_i) = 1$$

Expected Payoff

$$u_i(\sigma_i, \sigma_{-i}) = \sum_{s \in S} u_i(s) \prod_j \sigma_j(s_j)$$

Support

$\text{supp}(\sigma_i) = \{s_i : \sigma_i(s_i) > 0\}$

Indifference Principle

In mixed NE, all strategies in support have equal payoff

Opponent must be indifferent to mix

5. Best Response Functions

Definition

$$BR_i(s_{-i}) = \arg\max_{s_i \in S_i} u_i(s_i, s_{-i})$$

Correspondence

Multivalued if indifference

Nonempty by finiteness

NE Characterization

$(s^*)$ is NE $\Leftrightarrow$ $s_i^* \in BR_i(s_{-i}^*)$ for all $i$

Finding NE

1. Compute $BR_i$ for each player

2. Find intersection of all $BR_i$

BR diagram shows all NE graphically

6. Iterated Elimination

IESDS Process

Iterated Elimination of Strictly Dominated Strategies

Step 1: Remove strictly dominated

Step 2: Update game

Step 3: Repeat

Properties

Order-independent outcome

Removes "irrational" strategies

Rationalizability

Surviving strategies = rationalizable

Can explain actual play

IEWDS (weakly dominated) is order-dependent!

7. Zero-Sum Games

Definition

$\sum_i u_i(s) = 0$ for all strategy profiles $s$

Minimax Theorem

$$\max_{\sigma_1} \min_{\sigma_2} u_1(\sigma_1, \sigma_2) = \min_{\sigma_2} \max_{\sigma_1} u_1(\sigma_1, \sigma_2) = v^*$$

Value of Game

$v^*$ = value of game in mixed NE

Player 1 gets at least $v^*$

Player 2 holds Player 1 to $v^*$

Implications

All NE yield same payoff $v^*$

Rock-paper-scissors: $v^* = 0$

8. Extensive Form Games

Components

Game tree: nodes, edges, terminal nodes

Player labels at decision nodes

Information sets: indistinguishable nodes

Strategies

Complete contingent plan: action for each info set

Reduces to normal form

Information Sets

Perfect info: Each info set is singleton

Imperfect info: Info sets with multiple nodes

Conversion

Extensive $\to$ Normal: Strategy list × Payoff matrix

Important for backward induction

9. Subgame Perfect Equilibrium

Subgame Definition

Game starting from node where info set is singleton

Includes all descendants in tree

SPNE Definition

Strategy profile inducing NE in every subgame

Refinement of NE: SPNE $\subset$ NE

Backward Induction

1. Solve last decision nodes

2. Substitute optimal actions

3. Move backward to earlier nodes

Works for finite perfect-info games

Imperfect info: Cannot always use backward induction

10. Repeated Games

Infinitely Repeated Setup

Play stage game in periods $t = 0, 1, 2, \ldots$

$$U_i = \sum_{t=0}^{\infty} \delta^t u_i(s^t)$$

$\delta \in [0,1]$ = discount factor

Folk Theorem

If $\delta$ sufficiently high, any payoff profile Pareto-dominating one-shot NE can be supported as subgame-perfect equilibrium

Via grim-trigger or other punishments

Trigger Strategies

Grim trigger: Cooperate until deviation, then play punishment forever

Sustains cooperation through threats

11. Bayesian Games

Setup

Players: $N$

Actions: $A_i$ for each player

Types: $T_i$ (private information)

Beliefs: $p_i(t_{-i} | t_i)$

Payoffs: $u_i(a, t_i, t_{-i})$

Bayesian Nash Equilibrium

$$s_i^*(t_i) \in \arg\max_{a_i} \sum_{t_{-i}} u_i(a_i, s_{-i}^*(t_{-i}), t_i, t_{-i}) p_i(t_{-i}|t_i)$$

Interpretation

Type-contingent strategies

Each type plays best response given beliefs

Extends NE to incomplete information

12. Mechanism Design

Setup

Designer chooses outcome function

Players have private types

Goal: Implement desired outcome

Direct Revelation Principle

For any mechanism $M$ implementing $f$, truthful mechanism $M'$ also implements $f$

Agents report types truthfully at equilibrium

Incentive Compatibility

$$u_i(f(t_i, t_{-i}), t_i) \geq u_i(f(t_i', t_{-i}), t_i)$$

For all $t_i, t_i', t_{-i}$

Individual Rationality

$u_i(f(t_i, t_{-i}), t_i) \geq u_i^{\text{outside}}$

Participation constraint

13. Auction Theory

First-Price Sealed-Bid

Highest bid wins; pays own bid

Equilibrium bid: $b(v) = v - \int_0^v \frac{F(x)^{n-1}}{F(v)^{n-1}} dx$

Second-Price (Vickrey)

Highest bid wins; pays second-highest bid

Dominant strategy: Bid truthfully $b(v) = v$

Revenue Equivalence

First-price and second-price yield same expected revenue:

$$E[\text{Revenue}] = (n-1) \int_0^{\infty} [1-F(x)]^n dx$$

For risk-neutral, independent valuations

Vickrey dominant strategy makes it simpler

14. Cooperative Games

Characteristic Function

$v: 2^N \to \mathbb{R}$ assigns value to each coalition

$v(\emptyset) = 0$ (empty set worthless)

$v(N)$ = value of grand coalition

Coalition Formation

Subset $S \subseteq N$ can bind members

Can achieve payoff $v(S)$ jointly

Payoff Allocation

$x \in \mathbb{R}^n$: $x_i \geq 0$, $\sum_i x_i = v(N)$

Superadditivity

$v(S \cup T) \geq v(S) + v(T)$ for disjoint $S, T$

Cooperation beneficial (grand coalition optimal)

15. Shapley Value

Formula

$$\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n-|S|-1)!}{n!}[v(S \cup \{i\}) - v(S)]$$

Interpretation

Average marginal contribution across all orderings

Fair allocation based on contribution

Axioms (Uniqueness)

Efficiency: $\sum_i \phi_i = v(N)$

Symmetry: Equal players $\Rightarrow$ equal shares

Dummy: Non-contributors get 0

Additivity: Linear in game

Unique allocation satisfying all axioms

16. Core

Definition

Allocations no coalition wants to deviate from:

$$C(v) = \{x: \sum_i x_i = v(N), \sum_{i \in S} x_i \geq v(S) \, \forall S\}$$

Stability

Core non-empty $\Rightarrow$ allocation stable

No blocking coalition exists

Conditions

Superadditivity may guarantee non-empty core

Convexity guarantees Shapley in core

Comparison

Core: All players will agree

Shapley: Fair but might not be stable

Shapley value always in core (if non-empty)

17. Bargaining

Nash Bargaining Solution

Two players divide $[0,1]$; disagree get $(d_1, d_2)$

$$\max (x_1 - d_1)(x_2 - d_2) \text{ s.t. } x_1 + x_2 \leq 1$$

Solution

$$x_i^* = d_i + \frac{1-d_1-d_2}{2}$$

Split surplus equally above disagreement

Axioms

Pareto efficiency: Can't improve all

Symmetry: Equal bargaining power

IIA: Irrelevant alternatives don't matter

Scale invariance: Utility units don't matter

Unique solution satisfying all axioms

18. Evolutionary Game Theory

ESS Definition

Evolutionarily Stable Strategy

Strategy $\sigma$ immune to invasion by mutants

ESS Conditions

1. $\sigma$ is NE against itself

2. Against any invader $\sigma' \neq \sigma$: $\sigma$ gets higher payoff

$$u(\sigma, \sigma) \geq u(\sigma', \sigma)$$

$$u(\sigma, \sigma') > u(\sigma', \sigma')$$

Replicator Dynamics

$$\dot{x}_i = x_i[(e_i \cdot A x) - (x \cdot A x)]$$

Strategies with above-average payoff increase

Models natural selection dynamics

19. Prisoner's Dilemma

Payoff Structure

$T > R > P > S$ (Temptation, Reward, Punishment, Sucker)

Both defect is NE

Both cooperate is better for both

Equilibrium

Pure NE: (Defect, Defect)

Defect is dominant strategy

Dilemma

Rational individual play leads to suboptimal collective outcome

Classic tragedy of commons

Applications

Arms races, pollution, cartels, R&D competition

Cooperation possible in repeated games

20. Matching Pennies

Setup

Zero-sum game: Player 1 wants match, Player 2 wants mismatch

Payoff Matrix

Player 1: Heads, Tails

Player 2: Heads, Tails

u₁(H,H) = 1, u₁(H,T) = -1

u₁(T,H) = -1, u₁(T,T) = 1

Mixed NE

$$\sigma_1^* = \sigma_2^* = (0.5, 0.5)$$

Each randomizes 50-50

Value of game: $v^* = 0$

No pure strategy NE exists

21. Battle of the Sexes

Setup

Couple chooses activity: Opera or Fight

Both want to coordinate

Prefer different activities

Pure NE

$(O, O)$: Both go to opera

$(F, F)$: Both go to fight

Mixed NE

Female plays Opera with $p = \frac{3}{5}$

Male plays Opera with $q = \frac{2}{5}$

Interpretation

Asymmetric bargaining power in equilibrium

Three equilibria: payoff vs risk dominance

Illustrates multiplicity and coordination failure

22. Stag Hunt

Setup

Hunt Stag or Hare

Stag requires coordination, pays 4

Hare pays 3 guaranteed

Payoff Structure

$(S, S)$: (4, 4) - both get 4

$(S, H)$: (0, 3) - one gets 0, one gets 3

$(H, H)$: (3, 3) - both get 3

Equilibria

Pure NE: $(S,S)$ and $(H,H)$

$(S,S)$ Pareto-dominant

$(H,H)$ risk-dominant

Dilemma

Trust vs security

Motivation for repeated games / coalition building

23. Chicken

Setup

Two drivers head toward each other

Swerve or Straight

Both Straight = crash (worst)

Payoff Structure

$(S, S)$: (-10, -10) - crash

$(S, Sw)$: (1, 0) - you swerve

$(Sw, Sw)$: (-1, -1) - both swerve

Pure NE

One swerves, one goes straight

Two pure NE (asymmetric)

Mixed NE

$$\sigma^* = (p, 1-p) \text{ with } p = 0.5$$

Each randomizes 50-50

Pre-commitment (credibility) breaks symmetry

24. Coordination Games

Characteristics

Payoffs highest when players choose same action

Multiple pure NE

Players want to coordinate

Payoff Structure

Generic form:

$(A, A)$: $(a, a)$ - both get $a$

$(B, B)$: $(b, b)$ - both get $b$

$(A, B)$: $(0, 0)$ or negative

Solutions

Focal points / Schelling points

Communication / pre-play agreements

Convention or history

Mixed NE

Players randomize, lower payoff

Risk of coordination failure

25. Entry Game

Setup

Incumbent vs Entrant

Entrant: Enter or Stay Out

Incumbent (if entered): Fight or Accommodate

Extensive Form

Entrant moves first

Incumbent observes entry decision

Incumbent responds

Backward Induction

Incumbent's best response to Entry

Entrant predicts incumbent's response

Entrant decides based on prediction

Potential Outcome

Entry deterrence (incumbent fights)

Entry with accommodation (peaceful)

Information asymmetry adds strategic depth

26. Bargaining Solution

Alternating Offers Model

Players alternate proposals; majority voting or accept/reject

$$\delta = \text{discount factor per period}$$

SPE with 2 Players

Player 1 proposes first, offers Player 2:

$$x_2 = \frac{1-\delta}{1+\delta}$$

Player 1 gets: $\frac{1+\delta}{1+\delta} - \frac{1-\delta}{1+\delta} = \frac{2\delta}{1+\delta}$

Interpretation

More patient player gets better deal

First-mover advantage erodes as $\delta \to 1$

Limit as $\delta \to 1$

$$x_1^*, x_2^* \to (0.5, 0.5)$$

Equal split with infinite patience

27. Information & Signaling

Asymmetric Information

One player's type unknown to other

Affects inference and strategic play

Signaling Games

Informed player (sender) moves first; uninformed (receiver) responds

Sender signals type via action choice

Separating Equilibrium

Different types choose different signals

Receiver can infer type perfectly

Pooling Equilibrium

All types choose same signal

Receiver cannot distinguish types

Intuitive Criterion

Off-equilibrium beliefs constrained by credibility

Refinement of Perfect Bayesian Equilibrium

28. Voting Games

Voting Rules

Plurality: Most votes wins

Majority: >50% of votes needed

Unanimity: All must agree

Condorcet's Paradox

Majority preferences can be cyclic

A $\succ$ B, B $\succ$ C, C $\succ$ A

No Condorcet winner exists

Arrow's Impossibility

No voting rule satisfies all desirable axioms:

Unanimity, IIA, non-dictatorship

Strategic Voting

Voters misreport to influence outcome

Depends on voting rule

Mechanism design aims to align incentives

29. Public Goods Game

Setup

Each player contributes $c_i \in [0, w]$ to public pool

Total contribution returned $m \sum_i c_i$

$1 < m < n$ (individual return < 1)

Payoff

$$u_i = (w - c_i) + m \sum_j c_j$$

Equilibrium

Nash: $c_i = 0$ (free riding)

Pareto optimal: $c_i = w$ (full contribution)

Tragedy of Commons

Individual incentives vs collective welfare

Cooperation hard to sustain

Solutions

Punishment of free riders

Repeated interaction

Empirically: Humans cooperate more than predicted

30. Competition Models

Cournot Competition

Firms simultaneously choose quantities $q_i$

$$u_i = q_i [P(Q) - c]$$

$Q = \sum_i q_i$, $P$ = inverse demand

Best Response

$$BR_i(q_{-i}) = \arg\max_{q_i} q_i[P(q_i + Q_{-i}) - c]$$

Bertrand Competition

Firms simultaneously choose prices $p_i$

Lowest price firm captures market

Bertrand Paradox

With 2+ competitors: $p = c$ (marginal cost)

Zero economic profit at NE

Quantity competition (Cournot) allows higher prices

— Game Theory Complete Reference | Formula Index | Topics 1-30 Comprehensive Coverage