Introduction to Game Theory

Introduction

Game theory studies strategic interaction among rational agents whose outcomes depend on the actions of others. A game specifies players, available strategies, and payoffs determined by the joint strategy profile. The central objective is to predict stable outcomes under rational behavior.

Game theory applies broadly across economics, political science, biology, computer science, and philosophy.

Basic Definitions

A strategic-form (normal-form) game consists of:

• A finite set of players N={1,…,n}.

• Strategy sets (S_i) for each player i.

• Payoff functions (u_i):(S_1)×⋯×(S_n)→R.

A strategy profile is s=((s_1),…,(s_n)). Write (s_−i) for the strategies of all players except i.

Two-Player Games

For two players with finite strategies, payoffs are represented by matrices. Entry (a_i*j) is Player 1’s payoff when strategies (i,j) are chosen; (b_i*j) is Player 2’s payoff.

Classic Examples

Prisoner’s Dilemma

Each player chooses Cooperate or Defect.

• (C,C): (3,3)

• (D,D): (1,1)

• (D,C): (5,0)

• (C,D): (0,5)

Defection strictly dominates cooperation for both players. The unique Nash equilibrium is (D,D), which is Pareto inefficient relative to (C,C).

Matching Pennies

Players choose Heads or Tails.

• Match: Player 1 wins (+1)

• Mismatch: Player 2 wins (+1)

This is zero-sum. No pure equilibrium exists; the unique equilibrium is both players randomizing uniformly.

Dominant Strategies

Strategy (s_i) strictly dominates (s_i)′ if (u_i)((s_i),(s_−i))>(u_i)((s_i)′,(s_−i)) for all (s_−i).

Rational players never use strictly dominated strategies.

Nash Equilibrium

A profile (s^∗) is a Nash equilibrium if (u_i)((s_i^∗),(s_−i^∗))≥(u_i)((s_i),(s_−i^∗)) for all iand all (s_i).

Each strategy is a best response to the others. No unilateral deviation improves payoff.

Mixed Strategies

A mixed strategy is a probability distribution over pure strategies. Expected payoffs are computed as:

(U_i)((σ_1),…,(σ_n))=(∑_^)((∏_j=1^n)((σ_j)((s_j))))*(u_i)(s).

Nash’s Theorem

Every finite game has at least one mixed-strategy Nash equilibrium. Existence follows from fixed point arguments (Kakutani’s theorem).

Zero-Sum Games

A two-player game is zero-sum if (u_1)(s)+(u_2)(s)=0.

Represent with a single matrix A for Player 1.

Minimax Theorem

max(min((U_1)))=min(max((U_1)))=v.

Player 1 guarantees at least v; Player 2 limits Player 1 to at most v. This yields a complete solution for zero-sum games.

Coordination Games

Players benefit from matching strategies. Multiple equilibria typically exist, raising equilibrium selection issues.

Example: Battle of the Sexes.

Pareto Efficiency

Profile s is Pareto efficient if no s′ satisfies (u_i)(s′)≥(u_i)(s) for all i, with strict inequality for at least one i.

Nash equilibria need not be Pareto efficient.

Extensive Form Games

Sequential games are represented as trees. A strategy specifies actions at all decision nodes, even off-path ones.

Subgame Perfect Equilibrium

Refines Nash equilibrium by requiring optimal play in every subgame.

Backward Induction

Solve finite perfect-information games from terminal nodes backward.

Applications

• Economics: Oligopoly, auctions, mechanism design.

• Biology: Evolutionarily stable strategies.

• Computer science: Algorithmic game theory, complexity of equilibrium computation.

• Political science: Voting, coalition formation, international strategy.

Computing Mixed Equilibria

In two-player games, use the indifference principle: each player mixes so the opponent is indifferent among strategies in support.

For zero-sum games, compute equilibria via linear programming.

For general games, algorithms such as support enumeration and Lemke–Howson apply. Computing equilibria is PPAD-complete in general.

Summary

Game theory formalizes strategic interaction through players, strategies, and payoffs. The central prediction concept is Nash equilibrium. Mixed strategies ensure existence in finite games. Zero-sum games are characterized by the minimax theorem. Sequential games require subgame refinement.

The framework explains both cooperative coordination and inefficient conflict outcomes, and it underlies modern economic, biological, and computational modeling.