Game Theory

Job: model strategic interaction; characterize equilibria and refinements for noncooperative and cooperative games; link to optimization, probability, and learning dynamics.

Core

A game is a rule for payoffs as functions of multi-agent actions. Solution concepts (Nash, SPNE, correlated eq., core, Shapley) select strategy profiles with stability or axiomatic properties. Finite games always have mixed NE (Nash); structure (zero-sum, potential, supermodular) yields sharper predictions.

Layer Content
Normal form pure/mixed strategies; best replies; NE
Zero-sum von Neumann minmax; LP duality
Extensive form trees, information sets; SPNE; sequential eq.
Incomplete info Harsanyi types; Bayesian NE; mechanisms
Cooperative TU games; core; Shapley value
Dynamics best-reply / fictitious play; ESS (pointer)

Reading map

Page Focus
Foundations normal/extensive form; Nash thm; zero-sum; dominance; cooperative pointer
Mechanism Design revelation principle, Myerson optimal auction, VCG, Maskin, Arrow
Repeated & Folk discount \(\delta\), folk theorem, grim trigger, stochastic Shapley, APS
Learning & No-Regret no-regret→correlated Aumann, fictitious play, replicator/ESS
Cooperative & Combinatorial core/Shapley, Nash bargaining, Gale–Shapley matching, PPAD

Dependency order

  1. Convex analysis / fixed points (Kakutani) + multilinear algebra on mixed strategies
  2. Probability for mixed strategies and Bayesian games
  3. Foundations
  4. Optimization (LP duality, variational inequalities)
  5. Learning / dynamical systems for evolutionary and online play

Where it appears

  • Optimization: saddle points, KKT, variational inequalities
  • Probability: mixed strategies; common prior
  • Economics / CS: auctions, mechanism design, algorithmic GT
  • Multi-agent RL: equilibrium concepts vs empirical play

Signature results

Result Content
Nash existence finite games \(\Rightarrow\) mixed NE (Kakutani on best-reply)
von Neumann two-player zero-sum: \(\max\min=\min\max\)
Zermelo / backward induction finite perfect-info games: pure SPNE
Kuhn perfect recall \(\Rightarrow\) behavioral \(\leftrightarrow\) mixed
Revelation principle focus on direct incentive-compatible mechanisms

See it

Matching pennies. Unique NE is both mix \((1/2,1/2)\); value \(0\). No pure NE. Illustrates why mixed strategies are not a “tie-break” ornament but the existence vehicle for competitive games.

Prisoner's dilemma. Unique NE is mutual defect, Pareto-dominated by mutual cooperate — equilibrium \(\neq\) group optimality; repeated games / folk theorems restore cooperation under patient discounting (pointer).

Check

Sketch Nash existence for finite games.

Mixed strategy profiles form a simplex product (compact convex). Best-reply correspondence is nonempty, convex-valued, upper hemicontinuous \(\Rightarrow\) Kakutani fixed point \(=\) NE.

Why need refinements of NE in extensive form?

NE can rely on non-credible threats off the path of play. SPNE (and sequential/perfect Bayesian refinements under imperfect info) require optimality in every subgame / consistent beliefs.

Pitfalls

  • NE is static: best-reply dynamics need not converge (Shapley cycles).
  • Multiple equilibria: coordination games; selection criteria (risk-dominance, trembling-hand, ESS).
  • Correlated equilibrium can improve on NE via public randomization (Aumann).
  • Continuous games need quasiconcavity/compactness (Glicksberg); discontinuous payoffs need Reny-type theorems.

Refs

Osborne–Rubinstein; Fudenberg–Tirole; Myerson; von Neumann–Morgenstern; Nisan et al., Algorithmic Game Theory.

Next

Foundations · Optimization · Probability · Dynamical systems · Linear algebra · Mechanism Design · Repeated & Folk · Learning & No-Regret · Cooperative & Combinatorial