Game theory Study Guide

📖 Core Concepts Game Theory – mathematical study of strategic interaction among rational decision‑makers. Players, Actions, Payoffs, Information (PAPI) – the four elements needed to specify any game. Strategic (Normal) Form – payoff matrix for simultaneous‑move games. Extensive Form – game tree for sequential moves; solved by backward induction. Zero‑Sum vs. Non‑Zero‑Sum – total payoff sums to zero in the former; both players can gain in the latter. Cooperative vs. Non‑Cooperative – binding contracts allowed vs. only self‑enforcing threats. Nash Equilibrium (NE) – a profile of strategies where no player can profit by deviating unilaterally. Mixed‑Strategy NE – players randomize; each opponent’s pure strategies become indifferent. Subgame Perfect Equilibrium (SPE) – NE applied to every subgame; eliminates non‑credible threats. Evolutionarily Stable Strategy (ESS) – a strategy that cannot be invaded by a small mutant population; a refinement of NE for evolutionary games. Core & Shapley Value – cooperative‑game allocations: the core blocks any improving coalition; the Shapley value gives each player a fair share based on marginal contributions. --- 📌 Must Remember Minimax Theorem (von Neumann, 1928): $$\max{\sigma1}\min{\sigma2} u1(\sigma1,\sigma2)=\min{\sigma2}\max{\sigma1} u1(\sigma1,\sigma2)$$ Guarantees a value and optimal mixed strategies in finite zero‑sum games. Nash Existence (1950) – Every finite (non‑cooperative) game has at least one mixed‑strategy NE. Dominant Strategy – a strategy that yields a higher payoff regardless of opponents’ actions. Best‑Response – the strategy that maximizes a player’s payoff given opponents’ strategies. Trembling‑Hand Perfection – equilibrium must survive arbitrarily small “mistakes” (trembles). Bayesian Games – incorporate beliefs \(pi(\theta{-i})\) over unknown opponent types; equilibrium = Bayesian Nash Equilibrium. Folk Theorem – in infinitely repeated games, virtually any feasible payoff vector that gives each player more than their minmax payoff can be sustained as an equilibrium. Vickrey Auction – second‑price sealed‑bid; truthful bidding is a dominant strategy. --- 🔄 Key Processes Backward Induction (Extensive Form) Start at terminal nodes → compute payoffs. Move up one decision node: choose the action with the highest payoff for the mover. Continue until reaching the root; the resulting strategy profile is the SPE. Finding a Mixed‑Strategy NE (2×2 example) Let player 1 mix with probability \(p\) on \(A\), \(1-p\) on \(B\). Compute opponent’s expected payoff for each of their pure actions as functions of \(p\). Set them equal → solve for \(p\). Repeat for the other player. Computing the Shapley Value For each player \(i\), sum over all coalitions \(S\) not containing \(i\): $$\phii = \sum{S\subseteq N\setminus\{i\}} \frac{|S|!\,(|N|-|S|-1)!}{|N|!}\,[v(S\cup\{i\})-v(S)]$$ \(v(\cdot)\) = characteristic function value of a coalition. Bayesian Nash Equilibrium Write each type’s expected payoff using beliefs. Derive best‑response functions for each type. Solve the system of best‑responses simultaneously. --- 🔍 Key Comparisons Cooperative vs. Non‑Cooperative → binding contracts vs. self‑enforcing threats. Symmetric vs. Asymmetric → identical payoffs & strategies vs. player‑specific payoff matrices. Zero‑Sum vs. Non‑Zero‑Sum → one winner/one loser vs. possibility of mutual gain. Simultaneous vs. Sequential → normal‑form matrix vs. extensive‑form tree. Perfect vs. Imperfect Information → all moves observed vs. hidden actions (information sets). Pure‑Strategy NE vs. Mixed‑Strategy NE → deterministic choices vs. randomization to make opponents indifferent. Subgame Perfect vs. Nash → Nash in every subgame vs. Nash only overall. --- ⚠️ Common Misunderstandings “Nash = dominant strategy.” Only when a dominant strategy exists does it coincide with NE. “Mixed strategies are used only when players are irrational.” They are rational best‑responses when no pure NE exists. “The core always exists.” The core may be empty; existence depends on the game’s payoff structure. “ESS is always a pure strategy.” ESS can be mixed; it must satisfy both Nash and stability conditions. “Backward induction works with imperfect information.” It requires perfect information; with imperfect info we use subgame perfection and beliefs. --- 🧠 Mental Models / Intuition Best‑Response Curve – picture each player’s optimal action as a function of the opponent’s choice; NE is the intersection. Indifference Principle – in mixed NE, opponents must be indifferent among the pure actions they randomize over. “Threat Credibility” – SPE eliminates threats that would not be rational to carry out when the time comes. Population View (ESS) – imagine a large population playing the same game; a strategy that resists invasion is an ESS. --- 🚩 Exceptions & Edge Cases Multiple Nash Equilibria – coordination games (e.g., Battle of the Sexes) have several; equilibrium selection criteria (risk dominance, payoff dominance) may be required. Trembling‑Hand Perfection can rule out equilibria that rely on non‑credible off‑path actions. Empty Core – some cooperative games (e.g., the glove game with unequal contributions) have no allocation that no coalition can improve upon. Mixed‑Strategy ESS – a mixed strategy can be evolutionarily stable even when no pure ESS exists. --- 📍 When to Use Which Normal Form – simultaneous decisions, no timing information needed. Extensive Form + Backward Induction – sequential moves with perfect information. Bayesian Game Framework – any game where players lack knowledge of others’ payoffs/types. Correlated Equilibrium – when a public randomizing device (e.g., traffic lights) can improve payoffs beyond Nash. Shapley Value – fair division problems in cooperative settings with a known characteristic function. Core Analysis – check for stability of coalition allocations; use when binding agreements are enforceable. ESS Analysis – biological or cultural evolution contexts where strategies replicate over generations. --- 👀 Patterns to Recognize Dominant‑Strategy Pattern – a row/column that yields the highest payoff regardless of opponent’s move → equilibrium is immediate. Zero‑Sum Symmetry – matrix is anti‑symmetric; look for minimax values. “Chicken” Payoff Structure – high payoff for unilateral aggression, very low for mutual aggression → indicates potential mixed NE. Repeated‑Game Incentive – presence of future rounds often turns a one‑shot defection‑dominated game into a cooperative outcome (folk theorem). Information Set Clustering – in imperfect‑information trees, nodes in the same information set imply the same strategy must be used. --- 🗂️ Exam Traps Confusing “Best Response” with “Dominant Strategy.” The former depends on opponent’s strategy; the latter does not. Ignoring Off‑Path Beliefs in extensive‑form games → can mistakenly accept a non‑credible threat as SPE. Miscalculating Mixed‑Strategy Probabilities – forgetting to set opponent’s expected payoffs equal. Assuming the Core ≠ Empty – many textbook examples have an empty core; always verify feasibility. Treating ESS as Always Pure – some ESS are mixed; check the stability condition \(\pi(s,s) > \pi(t,s)\) for all mutants \(t\neq s\). Overlooking Bayesian Updating – in Bayesian games, equilibrium strategies must incorporate correct posterior beliefs after observing signals. ---