Game Theory — Foundations¶

Job: Define noncooperative games and Nash equilibrium; prove existence in the finite case; treat zero-sum duality and extensive-form perfection; orient cooperative and incomplete-information layers.

Core¶

Normal form and mixed strategies¶

Normal-form game: finite player set \(I\), strategy sets \(S_i\), payoffs \(u_i:\prod S_j\to\mathbb{R}\). Mixed strategy \(\sigma_i\in\Delta(S_i)\); expected payoff multilinear extension \(u_i(\sigma)\).

Best reply: \(BR_i(\sigma_{-i})=\arg\max_{\sigma_i}u_i(\sigma_i,\sigma_{-i})\). Pure best replies suffice as extreme points when checking NE.

Nash equilibrium: \(\sigma^*\) with $$ u_i(\sigma_i^,\sigma_{-i}^)\ge u_i(s_i,\sigma_{-i}^*)\quad\forall s_i\in S_i,\ \forall i $$ (equivalently: no profitable unilateral deviation). Pure NE is the special case \(\sigma_i\) Dirac.

Nash's theorem. Every finite strategic-form game has at least one mixed-strategy Nash equilibrium. Proof: best-reply correspondence \(BR:\prod\Delta(S_i)\rightrightarrows\prod\Delta(S_i)\) is uhc with nonempty convex values \(\Rightarrow\) Kakutani fixed point.

Zero-sum and dominance¶

Two-player zero-sum: \(u_2=-u_1\). Value $$ v=\max_{\sigma_1}\min_{\sigma_2}u_1(\sigma)=\min_{\sigma_2}\max_{\sigma_1}u_1(\sigma) $$ (von Neumann minmax). Equilibrium strategies solve dual LPs; exploitability = gap to value. Saddle point \(\Leftrightarrow\) NE.

Dominance: strictly dominated strategies unused in any NE; iterated elimination of strictly dominated strategies (IESDS) is order-independent and preserves the NE set. Weak dominance is order-dependent.

Potential / congestion games (pointer): exact potential \(\Phi\) with \(\Delta u_i=\Delta\Phi\) \(\Rightarrow\) pure NE exist (finite improvement property on finite strategy sets).

Extensive form¶

Game tree, information sets, perfect/imperfect information, perfect/imperfect recall. Behavioral strategies vs mixed: Kuhn — equivalent under perfect recall.

SPNE: NE of every subgame; backward induction in finite perfect-information games of perfect recall (Zermelo). Sequential equilibrium / perfect Bayesian (pointer): beliefs on information sets + sequential rationality; Kreps–Wilson consistency.

Repeated games (pointer): folk theorems — patient discounting sustains cooperative payoff vectors as SPNE outcomes under observability hypotheses.

Incomplete information and mechanisms¶

Harsanyi: types \(\theta_i\) with common prior; payoffs \(u_i(s,\theta)\); Bayesian NE = NE of the expanded game. Revelation principle: any BNE outcome of a mechanism is achievable by a direct mechanism where truth-telling is BNE. Incentive compatibility + individual rationality constrain implementable social choice (Myerson).

Cooperative one-liners¶

TU game \((N,v)\), \(v:2^N\to\mathbb{R}\), \(v(\emptyset)=0\). Core: allocations \(x\) with \(\sum x_i=v(N)\) and \(\sum_{i\in S}x_i\ge v(S)\) all \(S\). Shapley value $$ \phi_i(v)=\sum_{S\not\ni i}\frac{|S|!(n-|S|-1)!}{n!}\bigl(v(S\cup{i})-v(S)\bigr) $$ — unique linear symmetric dummy-efficient marginal-contribution solution.

Equilibrium refinements and dynamics (pointer)¶

Trembling-hand perfect, proper, ESS (Maynard Smith). Learning: fictitious play converges in zero-sum / potential classes but not always (Shapley cycles). Correlated equilibrium (Aumann): public signals can Pareto-improve NE.

See it¶

Matching pennies: \(S_1=S_2=\{H,T\}\), \(u_1=1\) on mismatch, \(-1\) on match. Unique NE: both mix \((1/2,1/2)\), value \(0\). No pure NE — mixed strategies essential.

Prisoner's dilemma: unique NE mutual defect, Pareto-dominated by cooperate — equilibrium \(\neq\) social optimum; mechanism/repeated-game structure needed to restore cooperation.

Battle of the sexes: two pure NE + one mixed; selection needs refinement or correlating device.

Check¶

Sketch why pure-strategy NE need not exist.

Matching pennies: for any pure profile, one player wants to deviate. Finite games still have mixed NE by Nash.

Does NE uniqueness hold?

No. Coordination games have multiple pure NE (and mixed). Selection: risk-dominance, trembling-hand perfection, ESS, public randomization (correlated eq.).

State minmax equality hypotheses for zero-sum.

Finite pure strategy sets (or compact convex mixed sets with continuous quasiconcave/quasiconvex payoffs — Sion): \(\max\min=\min\max\). Without quasiconcavity, gaps can appear.

Pitfalls¶

• NE is not a dynamics: learning / best-reply need not converge.
• Correlated equilibrium can Pareto-dominate NE via public signals.
• Continuous games need quasiconcavity / compactness (Glicksberg); discontinuous payoffs need Reny-type existence.
• Imperfect recall breaks Kuhn’s equivalence; “absentmindedness” puzzles.
• Common prior assumption is substantive in Bayesian games (no-trade theorems).

Refs¶

Osborne–Rubinstein; Fudenberg–Tirole; Myerson; von Neumann–Morgenstern; Nisan et al. (algorithmic GT); Maschler–Solan–Zamir.

Next¶

Index · Optimization · Dynamical systems · Probability · Linear algebra