• Overview
• Details
• Exercises

Game theory studies strategic interaction among rational agents. A Nash equilibrium is an action profile where no player can improve their payoff by unilaterally deviating. We review normal-form games, best responses, existence theorems, and examples (Prisoner’s Dilemma, Matching Pennies, Coordination), plus computational notes.

• Normal-form games: Players, strategy sets, payoff matrices; best-response correspondences.
• Pure vs mixed strategies: Mixed strategies as distributions over actions; expected payoffs.
• Nash equilibrium (NE): Fixed point of best responses. Existence in finite games (Nash’s theorem via Brouwer/Kakutani).
• Examples: Prisoner’s Dilemma (dominant strategies), Matching Pennies (no pure NE; mixed), Coordination (multiple equilibria, risk vs payoff dominance).
• Potential games and congestion games: Existence of pure NE via potential function; Rosenthal potential (high level).
• Refinements: Subgame-perfect equilibrium in extensive-form games (sketch), trembling-hand perfection (mention).
• Computation: 2-player zero-sum via linear programming (minimax); general-sum is PPAD-complete (high level).

1. Find all pure-strategy Nash equilibria of a 2x2 coordination game with two identical payoff diagonals; discuss risk vs payoff dominance.
2. Compute the mixed-strategy equilibrium of Matching Pennies; derive probabilities by equalizing expected payoffs.
3. Formulate a zero-sum bimatrix game as a linear program (row player) and solve for the value; relate to the column player’s dual.