# Lecture 3: Nash Equilibria CSCE 631-D: Intelligent Agents, Computational Game Solving | Fall 2026 | Alan Kuhnle, Texas A&M University **Accessibility and use note.** These notes are the accessible companion to the Lecture 3 Beamer slide deck. They follow the slide deck in order, with one heading per slide and one section heading per deck section. Every payoff matrix is reproduced as prose claims (one per table row) so that the content is fully accessible to screen-reader users and to students viewing the notes asynchronously without the PDF. Equations are explained in words alongside their symbolic form. No prior viewing of the Beamer slides is required; these notes are self-contained for learning. --- ## Overview ### Slide 1 -- Title Lecture 3: Nash Equilibria. CSCE 631-D: Intelligent Agents, Computational Game Solving. Instructor: Alan Kuhnle, Texas A&M University. Fall 2026. ### Slide 2 -- Today's Plan This lecture covers six topics: best responses, Nash equilibrium (definition and existence), computing Nash equilibria in two-by-two games, maxmin strategies, the minimax theorem for zero-sum games, and properties of Nash equilibria. The lecture closes with a comprehensive three-by-three worked example. Two agent-thread stops appear in this lecture. First, the concept of empirical best response among a finite set of prompt policies (Slide 5). Second, the sensitivity of equilibrium conclusions to payoff estimation error in games whose payoffs are estimated from sampled LLM interactions (Slide 18). ## Best Responses ### Slide 3 -- Best Response A best response is the strongest strategy a player can choose when the other players' strategies are fixed. Formally, given a mixed-strategy profile sigma_{-i} of all players except player i, a strategy sigma_i^* is a best response to sigma_{-i} if it achieves the highest possible expected payoff for player i among all mixed strategies available to that player. In symbols: > u_i(sigma_i^*, sigma_{-i}) >= u_i(sigma_i, sigma_{-i}) for all sigma_i in Delta(S_i), where Delta(S_i) denotes the set of all probability distributions (mixed strategies) over player i's pure-strategy set S_i, and u_i denotes player i's expected payoff function. The best-response set (also called the best-response correspondence) collects every strategy that achieves this maximum: > BR_i(sigma_{-i}) = argmax over sigma_i in Delta(S_i) of u_i(sigma_i, sigma_{-i}). A key observation: because expected payoff u_i is linear in sigma_i (it is a weighted sum of pure-strategy payoffs), a best response can always be found among the pure strategies. The best-response set always contains at least one pure strategy. Intuitively, the maximum of a linear function over a simplex is always attained at a vertex of the simplex. ### Slide 4 -- Best Response: Example Consider Battle of the Sexes, a coordination game between two players who prefer different activities but prefer coordination to miscoordination. The payoff matrix has two rows (Opera, Football) and two columns (Opera, Football). Row player is Player 1 and column player is Player 2. Prose claims for each row of the payoff matrix: - When both choose Opera, payoffs are (3, 2): Player 1 receives 3 and Player 2 receives 2. - When Player 1 chooses Opera and Player 2 chooses Football, payoffs are (0, 0): both receive 0. - When Player 1 chooses Football and Player 2 chooses Opera, payoffs are (0, 0): both receive 0. - When both choose Football, payoffs are (2, 3): Player 1 receives 2 and Player 2 receives 3. Let q denote the probability that Player 2 plays Opera (so Player 2 plays Football with probability 1 minus q). Player 1's expected payoff from each pure strategy is: - Playing Opera: u_1(Opera, q) = 3q. Player 1 receives 3 when both choose Opera, 0 otherwise. - Playing Football: u_1(Football, q) = 2(1 - q). Player 1 receives 2 when both choose Football, 0 otherwise. Player 1's best response depends on q: - If q > 2/5, then 3q > 2(1 - q), so Opera is the unique best response. - If q < 2/5, then 3q < 2(1 - q), so Football is the unique best response. - If q = 2/5, the two payoffs are equal (both equal 6/5), so every mixture of Opera and Football is a best response. The breakpoint q = 2/5 is found by solving 3q = 2(1 - q), which gives 5q = 2. ### Slide 5 -- Best Response Among Prompt Policies This slide connects the formal best-response concept to the course's agent thread. In the LLM-agent setting, a "strategy" is a prompt or scaffold policy: a system prompt, model configuration, and any surrounding workflow. To find a best response, fix the opponent's prompt policy and search over your own finite set of candidate policies for the one with the highest estimated payoff. Concrete example: suppose you have three candidate negotiation prompts (Aggressive, Reciprocal, Conciliatory) and your opponent uses a fixed "cooperative" policy. You estimate payoffs by running N = 30 sampled interactions per prompt policy and computing the mean payoff for each. Prose claims for each row of the estimated-payoff table: - Aggressive prompt: estimated payoff 2.4 with a 95% confidence interval of plus or minus 0.3. - Reciprocal prompt: estimated payoff 3.1 with a 95% confidence interval of plus or minus 0.2. - Conciliatory prompt: estimated payoff 2.8 with a 95% confidence interval of plus or minus 0.4. The empirical best response is Reciprocal, because it has the highest estimated payoff (the argmax row). This is the agent-world meaning of "best response" used throughout the semester: a finite policy search over estimated payoffs. ## Nash Equilibrium ### Slide 6 -- Nash Equilibrium: Definition A Nash equilibrium, introduced by John Nash in 1950, is a strategy profile in which every player is simultaneously playing a best response to the other players' strategies. Formally, a mixed-strategy profile sigma^* = (sigma_1^*, ..., sigma_n^*) is a Nash equilibrium if for every player i in the player set N: > u_i(sigma_i^*, sigma_{-i}^*) >= u_i(sigma_i, sigma_{-i}^*) for all sigma_i in Delta(S_i). Here sigma_{-i}^* denotes the equilibrium strategies of all players other than i. Equivalently, sigma_i^* belongs to BR_i(sigma_{-i}^*) for every player i: each player's equilibrium strategy is a best response to the equilibrium strategies of the others. Interpretation: a Nash equilibrium is a strategy profile from which no player has an incentive to unilaterally deviate. If all players are at a Nash equilibrium, no single player can improve their payoff by changing their own strategy alone. A Nash equilibrium is a fixed point of the best-response correspondence: applying the best-response map to the profile returns the same profile. ### Slide 7 -- Pure-Strategy Nash Equilibrium A pure-strategy Nash equilibrium (PSNE) is a Nash equilibrium in which every player plays a single pure strategy with no mixing. Formally, a strategy profile s^* = (s_1^*, ..., s_n^*) in the pure-strategy space S is a PSNE if for every player i and every alternative pure strategy s_i in S_i: > u_i(s_i^*, s_{-i}^*) >= u_i(s_i, s_{-i}^*). To find PSNE in a payoff matrix, check each cell to see whether each player's strategy in that cell is a best response to the other player's strategy. A useful method is to underline each player's best-response payoff in each column (for the row player) and each row (for the column player). A cell where all players' payoffs are underlined is a PSNE. ### Slide 8 -- Finding PSNE: Prisoner's Dilemma The Prisoner's Dilemma has two players, each choosing between Cooperate and Defect. Prose claims for each row of the payoff matrix: - When both cooperate, payoffs are (-1, -1). - When Player 1 cooperates and Player 2 defects, payoffs are (-3, 0). Player 2's payoff 0 is underlined (best response). - When Player 1 defects and Player 2 cooperates, payoffs are (0, -3). Player 1's payoff 0 is underlined (best response). - When both defect, payoffs are (-2, -2). Both payoffs are underlined (both are best responses). Best-response analysis: - Row player's best response to Cooperate (column): Defect, because 0 > -1. - Row player's best response to Defect (column): Defect, because -2 > -3. - Column player's analysis is symmetric: Defect is the best response to both Cooperate and Defect. The unique PSNE is (Defect, Defect) with payoff (-2, -2). This is the only cell where both players' payoffs are underlined. ### Slide 9 -- Finding PSNE: Battle of the Sexes Prose claims for each row of the payoff matrix with underlined best responses: - (Opera, Opera): payoffs (3, 2). Both payoffs are underlined. Player 1's 3 is the best response to column Opera; Player 2's 2 is the best response to row Opera. - (Opera, Football): payoffs (0, 0). Neither is underlined. - (Football, Opera): payoffs (0, 0). Neither is underlined. - (Football, Football): payoffs (2, 3). Both payoffs are underlined. Player 1's 2 is the best response to column Football; Player 2's 3 is the best response to row Football. There are two PSNE: (Opera, Opera) with payoff (3, 2) and (Football, Football) with payoff (2, 3). Neither off-diagonal cell is a Nash equilibrium because in each, at least one player wants to switch to match the other's choice. A natural question: is there also a mixed Nash equilibrium? Yes. It is computed later in this lecture (Slide 15). ### Slide 10 -- Finding PSNE: Matching Pennies Matching Pennies is a two-player zero-sum game. Each player simultaneously shows Heads or Tails. Player 1 wins if the choices match; Player 2 wins if they differ. Prose claims for each row of the payoff matrix: - (Heads, Heads): payoffs (1, -1). Only Player 1's payoff is underlined (1 is the row player's best response to Heads). - (Heads, Tails): payoffs (-1, 1). Only Player 2's payoff is underlined (1 is the column player's best response to row Heads). - (Tails, Heads): payoffs (-1, 1). Only Player 2's payoff is underlined (1 is the column player's best response to row Tails). - (Tails, Tails): payoffs (1, -1). Only Player 1's payoff is underlined (1 is the row player's best response to Tails). No cell has both players' payoffs underlined. No pure-strategy Nash equilibrium exists. This is the motivating example for mixed strategies: Nash's theorem guarantees that a mixed Nash equilibrium exists even when no pure-strategy equilibrium does. ## Nash's Existence Theorem ### Slide 11 -- Nash's Existence Theorem (1950) Nash's theorem states that every finite game (finitely many players, each with finitely many pure strategies) has at least one mixed-strategy Nash equilibrium. The proof idea uses Kakutani's fixed-point theorem. Define the best-response correspondence BR that maps each strategy profile to the set of best-response profiles. The domain of BR is the product of simplices (one per player), which is compact and convex. The correspondence BR is upper-hemicontinuous and has convex values. By Kakutani's theorem, BR has a fixed point. A fixed point of BR is exactly a Nash equilibrium. This is a pure existence result. It does not say: - How many Nash equilibria exist. - How to compute one efficiently. - Which Nash equilibrium is "the right one" when multiple exist (the equilibrium selection problem). ### Slide 12 -- Kakutani's Fixed-Point Theorem Kakutani's fixed-point theorem (1941) provides the mathematical foundation for Nash's existence proof. The theorem states: let X be a compact and convex subset of R^n, and let F be an upper-hemicontinuous correspondence from X to X with nonempty, convex values. Then F has a fixed point: there exists x^* in X such that x^* belongs to F(x^*). **Detailed walkthrough of the fixed-point argument.** The proof that Nash equilibria exist applies Kakutani's theorem to the best-response correspondence BR defined on the product of strategy simplices. Each of the four conditions must hold. *Condition 1: the domain is compact and convex.* Each player i's mixed-strategy set Delta(S_i) is the probability simplex over S_i. A probability simplex is a compact convex subset of Euclidean space: compact because it is closed and bounded, convex because any weighted average of probability distributions is a probability distribution. The product of these simplices across all players is again compact (by the finite product of compact sets) and convex (a product of convex sets is convex). This product is the domain X on which the best-response correspondence acts. *Condition 2: the best-response set is nonempty.* For each player i, the expected payoff function u_i(sigma_i, sigma_{-i}) is a continuous function of sigma_i on the compact set Delta(S_i). By the extreme value theorem, a continuous function on a compact set attains its maximum. Therefore BR_i(sigma_{-i}) is nonempty for every opponent profile sigma_{-i}: at least one best response always exists. *Condition 3: the best-response set is convex.* Suppose sigma_i and sigma_i' are both best responses for player i against sigma_{-i}, both achieving the maximum payoff value v. Take any convex combination: lambda * sigma_i + (1 - lambda) * sigma_i' for lambda in [0, 1]. By linearity of u_i in sigma_i, the payoff of this mixture is lambda * v + (1 - lambda) * v = v, which is still the maximum. Therefore the mixture is also a best response, and the best-response set is convex. *Condition 4: the correspondence is upper-hemicontinuous.* Upper-hemicontinuity means: if a sequence of opponent profiles sigma_{-i}^k converges to sigma_{-i}, and a corresponding sequence of best responses sigma_i^k converges to sigma_i, then sigma_i belongs to BR_i(sigma_{-i}). This follows from continuity of u_i. In the limit, the payoff inequality is preserved: u_i(sigma_i, sigma_{-i}) >= u_i(sigma_i', sigma_{-i}) for all sigma_i', because each inequality u_i(sigma_i^k, sigma_{-i}^k) >= u_i(sigma_i', sigma_{-i}^k) passes to the limit by continuity. Since all four conditions hold, Kakutani's theorem guarantees a fixed point of the joint best-response correspondence. At this fixed point, every player's strategy is a best response to the others, which is precisely a Nash equilibrium. ## Computing NE in 2 x 2 Games ### Slide 13 -- The Indifference Principle The indifference principle is the main analytical tool for computing mixed Nash equilibria. The theorem states: let sigma^* be a Nash equilibrium. For each player i, every pure strategy in the support of sigma_i^* (the set of pure strategies played with positive probability) yields the same expected payoff against sigma_{-i}^*. Every pure strategy outside the support yields a weakly lower expected payoff. Proof: suppose two pure strategies s_i and s_i' are both in the support of sigma_i^*, but u_i(s_i, sigma_{-i}^*) is strictly greater than u_i(s_i', sigma_{-i}^*). Then player i could increase their expected payoff by shifting probability from s_i' to s_i. This contradicts the assumption that sigma_i^* is a best response. Therefore all strategies in the support must yield equal payoff. If any strategy outside the support yielded strictly higher payoff, player i would want to add it to the mixture, again contradicting best response. This principle transforms the problem of finding mixed Nash equilibria into a system of linear equations: set the payoffs of all supported strategies equal and solve for the mixing probabilities. ### Slide 14 -- Support Enumeration Method (Preview) The support enumeration method finds all Nash equilibria of a two-player game by systematically trying every possible pair of supports. This is a preview; the full algorithm and its complexity analysis appear in Module 2, Lecture 5. The algorithm proceeds as follows. For each pair of support sets (T_1 subset of S_1, T_2 subset of S_2): (a) Solve the indifference equations: for each player i, all pure strategies in T_i must yield equal expected payoff against the opponent's mixture. (b) Check nonnegativity: the solution must assign nonnegative probability to each strategy in the support, sigma_i(s_i) >= 0 for all s_i in T_i. (c) Check the best-response condition: no pure strategy outside T_i yields a strictly higher payoff than the strategies in T_i. Collect all valid solutions. For a 2 x 2 game, there are at most 3 x 3 = 9 possible support pairs, but in practice one checks the full-support case (T_1 = S_1, T_2 = S_2) plus any PSNE found by the underlining method. The general algorithm enumerates exponentially many support pairs. ### Slide 15 -- Example: Mixed NE in Battle of the Sexes This slide computes the mixed Nash equilibrium of Battle of the Sexes using the indifference principle. Let p denote the probability that Player 1 plays Opera and q denote the probability that Player 2 plays Opera. Prose claims for each row of the payoff matrix with mixing probabilities: - (Opera played with probability p, Opera played with probability q): payoffs (3, 2). - (Opera played with probability p, Football played with probability 1-q): payoffs (0, 0). - (Football played with probability 1-p, Opera played with probability q): payoffs (0, 0). - (Football played with probability 1-p, Football played with probability 1-q): payoffs (2, 3). Player 1 must be indifferent between Opera and Football (given Player 2's mixing probability q): - Expected payoff from Opera = 3q + 0(1 - q) = 3q. - Expected payoff from Football = 0(q) + 2(1 - q) = 2(1 - q). - Setting equal: 3q = 2(1 - q). This gives 3q = 2 - 2q, so 5q = 2, hence q = 2/5. Player 2 must be indifferent between Opera and Football (given Player 1's mixing probability p): - Expected payoff from Opera = 2p + 0(1 - p) = 2p. - Expected payoff from Football = 0(p) + 3(1 - p) = 3(1 - p). - Setting equal: 2p = 3(1 - p). This gives 2p = 3 - 3p, so 5p = 3, hence p = 3/5. The mixed Nash equilibrium is sigma_1 = (3/5, 2/5) for Player 1 (Opera with probability 3/5) and sigma_2 = (2/5, 3/5) for Player 2 (Opera with probability 2/5). Expected payoffs at this equilibrium: u_1 = 3 * (2/5) = 6/5 = 1.2, and u_2 = 2 * (3/5) = 6/5 = 1.2. In total, Battle of the Sexes has three Nash equilibria: two pure ((Opera, Opera) and (Football, Football)) and one mixed. ### Slide 16 -- Example: NE of Matching Pennies (Recap) Matching Pennies revisited with the indifference principle. Let p denote Player 1's probability of Heads and q denote Player 2's probability of Heads. Prose claims for each row of the payoff matrix with mixing probabilities: - (Heads with probability p, Heads with probability q): payoffs (1, -1). - (Heads with probability p, Tails with probability 1-q): payoffs (-1, 1). - (Tails with probability 1-p, Heads with probability q): payoffs (-1, 1). - (Tails with probability 1-p, Tails with probability 1-q): payoffs (1, -1). Player 1's indifference condition: - Expected payoff from Heads = q(1) + (1 - q)(-1) = 2q - 1. - Expected payoff from Tails = q(-1) + (1 - q)(1) = 1 - 2q. - Setting equal: 2q - 1 = 1 - 2q, so 4q = 2, hence q = 1/2. Player 2's indifference condition (Player 2 wants mismatches): - Expected payoff from Heads = p(-1) + (1 - p)(1) = 1 - 2p. - Expected payoff from Tails = p(1) + (1 - p)(-1) = 2p - 1. - Setting equal: 1 - 2p = 2p - 1, so 4p = 2, hence p = 1/2. The unique Nash equilibrium is sigma_1 = sigma_2 = (1/2, 1/2), and the value of the game is 0 for both players. An important observation: in the mixed Nash equilibrium, each player is indifferent between their pure strategies. The mixing probabilities are determined by the opponent's indifference condition, not the player's own preferences. Player 1's mixing probability p = 1/2 is the value that makes Player 2 indifferent. Player 2's mixing probability q = 1/2 is the value that makes Player 1 indifferent. ### Slide 17 -- How Many Nash Equilibria? A theorem due to Wilson (1971) and Harsanyi (1973) states that for "generic" games (games whose payoffs are in general position, with no special algebraic relationships among payoff values), the number of Nash equilibria is finite and odd. Examples from this lecture: - Prisoner's Dilemma: 1 Nash equilibrium (pure). - Matching Pennies: 1 Nash equilibrium (mixed). - Battle of the Sexes: 3 Nash equilibria (2 pure + 1 mixed). - Coordination game: 3 Nash equilibria. All counts are odd, consistent with the theorem. Non-generic games can have a continuum of Nash equilibria. Games with payoff ties, for example, can produce infinitely many equilibria. For n x n games, the maximum number of Nash equilibria can be exponential in n. ## Equilibria of Estimated Games ### Slide 18 -- NE of an Estimated Game This slide connects Nash equilibrium analysis to the empirical payoff matrices that arise when estimating games from LLM agent interactions. This is the core analytical setting of PA1. Consider the representative output in Lecture 2's expected demo transcript, based on N = 30 sampled LLM interactions per cell. These values are illustrative until the instructor performs the live run; after that run, this worked example should be updated with the recorded means and confidence intervals. Prose claims for each row of the estimated payoff matrix: - (Cooperate, Cooperate): both players' estimated payoff is 2.83 with a 95% confidence interval of plus or minus 0.24. - (Cooperate, Defect): Player 1's estimated payoff is 0.47 with a 95% confidence interval of plus or minus 0.30; Player 2's estimated payoff is 4.60 with a 95% confidence interval of plus or minus 0.31. - (Defect, Cooperate): Player 1's estimated payoff is 4.60 with a 95% confidence interval of plus or minus 0.31; Player 2's estimated payoff is 0.47 with a 95% confidence interval of plus or minus 0.30. - (Defect, Defect): both players' estimated payoff is 1.07 with a 95% confidence interval of plus or minus 0.12. **Point-estimate analysis.** Using the point estimates alone, Defect is strictly dominant for both players. For Player 1: against Cooperate, Defect gives 4.60 versus 2.83 for Cooperate; against Defect, Defect gives 1.07 versus 0.47 for Cooperate. Player 2's analysis is symmetric. The unique Nash equilibrium is (Defect, Defect). **Sensitivity analysis (worked perturbation).** Push every comparison as far as the marginal confidence intervals allow in favor of Cooperate: use Cooperate's upper endpoint and Defect's lower endpoint. Against an opponent who Cooperates, Cooperate can be as high as 2.83 + 0.24 = 3.07, while Defect can be as low as 4.60 - 0.31 = 4.29. Defect still wins by 1.22. Against an opponent who Defects, Cooperate can be as high as 0.47 + 0.30 = 0.77, while Defect can be as low as 1.07 - 0.12 = 0.95. Defect still wins by 0.18. By symmetry, the same comparisons hold for Player 2. Therefore Defect remains strictly dominant and (Defect, Defect) remains the unique Nash equilibrium throughout these marginal intervals. This is the core question of PA1: how sensitive are your equilibrium conclusions to the estimation error inherent in payoffs derived from sampled LLM interactions? Here the conclusion is robust, but another estimated game may change equilibrium when its payoff intervals overlap. Marginal intervals alone do not define a simultaneous confidence region; a full PA1 analysis should state the uncertainty model used for joint perturbations. ## Maxmin Strategies ### Slide 19 -- Maxmin Strategy The maxmin value captures the idea of playing it safe. Player i's maxmin value, denoted v_bar_i, is the highest expected payoff that player i can guarantee regardless of what the other players do. Formally: > v_bar_i = max over sigma_i in Delta(S_i) of [ min over sigma_{-i} in Delta(S_{-i}) of u_i(sigma_i, sigma_{-i}) ]. A strategy sigma_i^* that achieves this maximum is called a maxmin strategy for player i. Interpretation: the maxmin strategy is the safest strategy available. It maximizes player i's payoff under worst-case opponent behavior. The value v_bar_i is also called the security level of player i: the payoff that player i can guarantee regardless of what the other players choose to do. ### Slide 20 -- Minmax Strategy The minmax value against player i measures the minimum payoff that the other players can force upon player i. Formally: > v_underbar_i = min over sigma_{-i} in Delta(S_{-i}) of [ max over sigma_i in Delta(S_i) of u_i(sigma_i, sigma_{-i}) ]. For any game, the maxmin value is at most the minmax value: v_bar_i <= v_underbar_i. The max player moves first in the maxmin formulation and thus has less information than in the reversed (minmax) order, so the inequality max-min <= min-max always holds. Equality holds for two-player zero-sum games, as established by von Neumann's minimax theorem (Slide 22). ### Slide 21 -- Maxmin Example: Battle of the Sexes This slide computes Player 1's maxmin strategy in Battle of the Sexes, considering only Player 1's payoffs. Prose claims for each column of Player 1's payoff matrix: - Against column Opera: Player 1 receives 3 from playing Opera and 0 from playing Football. - Against column Football: Player 1 receives 0 from playing Opera and 2 from playing Football. Let p denote the probability that Player 1 plays Opera. The worst-case payoff for each opponent response is: - If the opponent plays Opera: Player 1's payoff is 3p. - If the opponent plays Football: Player 1's payoff is 2(1 - p). The worst-case payoff across opponents is min{3p, 2(1 - p)}. This minimum equals 3p when p <= 2/5 and equals 2(1 - p) when p >= 2/5. To maximize the worst-case payoff, set the two expressions equal: 3p = 2(1 - p). Solving: 3p = 2 - 2p, so 5p = 2, hence p = 2/5. The maxmin value is v_bar_1 = 3(2/5) = 6/5 = 1.2. The maxmin strategy is sigma_1 = (2/5, 3/5): play Opera with probability 2/5 and Football with probability 3/5. Note that the maxmin strategy (2/5, 3/5) differs from the Nash equilibrium strategy sigma_1 = (3/5, 2/5). In general-sum games, the maxmin strategy and the Nash equilibrium strategy are not the same. In zero-sum games, they coincide. ## Minimax Theorem for Zero-Sum Games ### Slide 22 -- Von Neumann's Minimax Theorem Von Neumann's minimax theorem (1928) is one of the foundational results of game theory. It states: in any finite two-player zero-sum game with payoff matrix A (an m x n real matrix, giving Player 1's payoffs), the maxmin value equals the minmax value: > max over sigma_1 in Delta_m of [ min over sigma_2 in Delta_n of sigma_1^T A sigma_2 ] = min over sigma_2 in Delta_n of [ max over sigma_1 in Delta_m of sigma_1^T A sigma_2 ] = v^*. Here Delta_m and Delta_n are the probability simplices of dimensions m and n. The expression sigma_1^T A sigma_2 is the bilinear expected payoff: Player 1's row-mixture times the payoff matrix times Player 2's column-mixture. The common value v^* is called the value of the game. This is a deep result. In general, the inequality max-min <= min-max is strict. Equality requires the zero-sum structure, or more precisely, the saddle-point structure of bilinear functions over compact convex sets. ### Slide 23 -- Proof Sketch (via LP Duality) **Full prose proof sketch.** The minimax theorem can be proved using linear programming duality. Player 1's problem is to choose a mixed strategy sigma_1 to maximize the worst-case expected payoff against Player 2. The inner minimization over Player 2's mixed strategy sigma_2 can be simplified. Because the payoff sigma_1^T A sigma_2 is linear in sigma_2, the minimum over the simplex Delta_n is achieved at a vertex (a pure strategy). The j-th pure strategy of Player 2 yields payoff equal to the j-th component of A^T sigma_1. Therefore the minimum over all mixed strategies equals the minimum over pure strategies: > min over sigma_2 in Delta_n of sigma_1^T A sigma_2 = min over j in {1, ..., n} of (A^T sigma_1)_j. Player 1's problem becomes: maximize v subject to (A^T sigma_1)_j >= v for all j in {1, ..., n}, and sigma_1 in Delta_m. This is a linear program (LP). The decision variables are sigma_1 (the m mixing probabilities) and v (the guaranteed payoff level). The constraints require that every column of A, when weighted by sigma_1, yields at least v. Player 2's problem is the mirror image: minimize w subject to (A sigma_2)_i <= w for all i in {1, ..., m}, and sigma_2 in Delta_n. Player 2 seeks to minimize the maximum payoff that Player 1 can achieve. These two linear programs are duals of each other. Both are feasible (uniform mixtures satisfy the constraints for finite v and w) and bounded. By strong LP duality, their optimal values coincide: v^* = w^*. This proves the minimax theorem: the maximum of the minimum payoff equals the minimum of the maximum payoff. The LP formulation also shows that computing Nash equilibria in two-player zero-sum games reduces to solving a linear program, which runs in polynomial time. ### Slide 24 -- Consequences for Zero-Sum Games The minimax theorem yields three equivalent characterizations of equilibrium play in two-player zero-sum games. 1. The strategy pair (sigma_1^*, sigma_2^*) is a Nash equilibrium. 2. sigma_1^* is a maxmin strategy for Player 1 and sigma_2^* is a minmax strategy for Player 2. 3. The pair (sigma_1^*, sigma_2^*) is a saddle point: for all sigma_1 and sigma_2, sigma_1^T A sigma_2^* <= (sigma_1^*)^T A sigma_2^* <= (sigma_1^*)^T A sigma_2. Key implications: - All Nash equilibria yield the same payoff: v^* for Player 1 and -v^* for Player 2. The value of the game is unique. - Nash equilibrium strategies are interchangeable. If (sigma_1, sigma_2) and (sigma_1', sigma_2') are both Nash equilibria, then (sigma_1, sigma_2') is also a Nash equilibrium. Players can independently choose any equilibrium strategy without coordinating. - Computing a Nash equilibrium is equivalent to solving an LP, which runs in polynomial time. ### Slide 25 -- NE vs. Maxmin in General-Sum Games In general-sum games, the convenient properties of zero-sum games break down. Prose claims for each row of the comparison table: - Nash equilibrium payoff unique? In zero-sum games, yes. In general-sum games, no (Battle of the Sexes has three NE with different payoffs). - NE equals maxmin? In zero-sum games, yes. In general-sum games, not in general (the Battle of the Sexes example on Slide 21 showed the maxmin strategy (2/5, 3/5) differs from the NE strategy (3/5, 2/5)). - NE strategies interchangeable? In zero-sum games, yes. In general-sum games, no. - Computable in polynomial time? In zero-sum games, yes (via LP). In general-sum games, the problem is PPAD-complete. The minimax theorem makes zero-sum games the tractable special case. Most of the computational difficulty in algorithmic game theory comes from general-sum games. ## Properties of Nash Equilibria ### Slide 26 -- NE and Pareto Optimality Nash equilibria need not be Pareto-optimal. A strategy profile is Pareto-optimal if no other profile makes every player at least as well off and at least one player strictly better off. In the Prisoner's Dilemma, (Defect, Defect) is the unique NE with payoff (-2, -2). But (Cooperate, Cooperate) gives (-1, -1), which Pareto-dominates it: both players are strictly better off cooperating. The NE is inefficient. The Price of Anarchy (PoA), introduced by Koutsoupias and Papadimitriou (1999), quantifies this efficiency loss: > PoA = (worst NE social cost) / (optimal social cost). PoA is always ≥ 1; a value of 1 means every Nash equilibrium is fully efficient, larger values indicate greater inefficiency. The Price of Anarchy is a central concept in algorithmic game theory for measuring the cost of selfish, uncoordinated behavior. ### Slide 27 -- Multiple Equilibria and Selection When a game has multiple Nash equilibria, which should players select? This is the equilibrium selection problem. Several refinement concepts address it. Pareto-dominant NE: select the Nash equilibrium that Pareto-dominates all others, if one exists. Risk-dominant NE: select the "safer" equilibrium, the one with the larger basin of attraction under best-response dynamics (Harsanyi and Selten, 1988). Focal points: Schelling (1960) argued that cultural or contextual salience can cause players to coordinate on a particular equilibrium even without communication. Correlated equilibrium: a convex relaxation that encompasses all Nash equilibria, computed via LP (covered in Lecture 4). Trembling-hand perfect NE: an equilibrium robust to small perturbations in strategy choices. Which equilibrium do LLM agents select? Because LLM agents share training data and similar architectures, they may have implicit focal points in Schelling's sense. Two independently deployed LLM agents may coordinate on the same Nash equilibrium without explicit communication, because their shared pretraining creates common expectations about "default" behavior. This is an empirical selection question that students can test in PA1's coordination game. ### Slide 28 -- Existence vs. Computation Nash's existence theorem is topological: Kakutani's fixed-point theorem guarantees that at least one Nash equilibrium exists, but says nothing about how to find one efficiently. The computational complexity of finding Nash equilibria varies by game class: - Two-player zero-sum games: solvable in polynomial time via linear programming. - Two-player general-sum games: computing any Nash equilibrium is PPAD-complete (Chen and Deng, 2006; Daskalakis, Goldberg, and Papadimitriou, 2006). - n-player games: also PPAD-complete or harder. PPAD stands for "Polynomial Parity Argument on Directed graphs." It is a complexity class that captures search problems where a solution is guaranteed to exist by a parity argument (any directed graph with a source must have another endpoint) but finding one may be hard. Module 2 covers the algorithms (support enumeration, Lemke-Howson, LP for zero-sum) and the precise complexity landscape. ## Comprehensive Example: A 3 x 3 Game ### Slide 29 -- A 3 x 3 Game This slide presents a larger worked example. Player 1 chooses among T (top), M (middle), or B (bottom). Player 2 chooses among L (left), C (center), or R (right). Prose claims for each row of the payoff matrix: - (T, L): payoffs (3, 1). Player 1 receives 3, Player 2 receives 1. - (T, C): payoffs (0, 2). Player 1 receives 0, Player 2 receives 2. - (T, R): payoffs (1, 0). Player 1 receives 1, Player 2 receives 0. - (M, L): payoffs (1, 2). Player 1 receives 1, Player 2 receives 2. - (M, C): payoffs (2, 1). Player 1 receives 2, Player 2 receives 1. - (M, R): payoffs (3, 0). Player 1 receives 3, Player 2 receives 0. - (B, L): payoffs (0, 3). Player 1 receives 0, Player 2 receives 3. - (B, C): payoffs (1, 0). Player 1 receives 1, Player 2 receives 0. - (B, R): payoffs (2, 2). Player 1 receives 2, Player 2 receives 2. Step 1: find pure-strategy Nash equilibria by computing best responses. Player 1's best responses (maximizing Player 1's payoff for each column): against L, T is best (payoff 3); against C, M is best (payoff 2); against R, M is best (payoff 3). Player 2's best responses (maximizing Player 2's payoff for each row): against T, C is best (payoff 2); against M, L is best (payoff 2); against B, L is best (payoff 3). No cell has both players playing a best response simultaneously. For example, (T, L) has Player 1 best-responding but Player 2 prefers C against T. Similarly, (M, L) has Player 2 best-responding but Player 1 prefers T against L. No pure-strategy Nash equilibrium exists. ### Slide 30 -- Finding Mixed NE in the 3 x 3 Game To find a mixed Nash equilibrium, guess a support pair and solve the indifference equations. Try Player 1 mixing over {T, M} (with probabilities p and 1 - p, zero weight on B) and Player 2 mixing over {L, C} (with probabilities q and 1 - q, zero weight on R). Player 1's indifference condition (expected payoff from T equals expected payoff from M, given Player 2 plays L with probability q and C with probability 1 - q): - u_1(T) = 3q + 0(1 - q) = 3q. - u_1(M) = 1(q) + 2(1 - q) = 2 - q. - Setting equal: 3q = 2 - q, so 4q = 2, hence q = 1/2. Player 2's indifference condition (expected payoff from L equals expected payoff from C, given Player 1 plays T with probability p and M with probability 1 - p): - u_2(L) = 1(p) + 2(1 - p) = 2 - p. - u_2(C) = 2p + 1(1 - p) = p + 1. - Setting equal: 2 - p = p + 1, so 1 = 2p, hence p = 1/2. Verification that strategies outside the support are not profitable deviations: - Player 1 considers B: u_1(B, sigma_2) = 0(1/2) + 1(1/2) = 1/2. The equilibrium payoff is u_1 = 3(1/2) = 3/2. Since 1/2 < 3/2, B is not a profitable deviation. - Player 2 considers R: u_2(sigma_1, R) = 0(1/2) + 0(1/2) = 0. The equilibrium payoff is u_2 = 2 - 1/2 = 3/2. Since 0 < 3/2, R is not a profitable deviation. The Nash equilibrium is sigma_1 = (1/2, 1/2, 0) and sigma_2 = (1/2, 1/2, 0), with expected payoff (3/2, 3/2). ## Summary ### Slide 31 -- Summary This lecture covered six core concepts. Best response: the optimal strategy given the opponents' play. In the LLM-agent context, a best response is found by finite search over prompt policies using estimated payoffs. Nash equilibrium: a strategy profile of mutual best responses. Every finite game has at least one mixed Nash equilibrium (Nash, 1950). The existence proof relies on Kakutani's fixed-point theorem. Indifference principle: in a Nash equilibrium, all pure strategies in the support yield equal expected payoff. This is the key tool for computing mixed Nash equilibria analytically. Maxmin and minimax: the maxmin value is a player's security level, the payoff guaranteed under worst-case opponent play. In zero-sum games, the maxmin value equals the minmax value (von Neumann's minimax theorem, 1928). In general-sum games, the maxmin strategy and the Nash equilibrium strategy can differ. Computing NE: polynomial time for zero-sum games (via LP); PPAD-complete for general-sum games. Algorithms are the focus of Module 2. Estimated games: equilibrium conclusions can be sensitive to payoff estimation error. Confidence intervals from sampled LLM play propagate into equilibrium structure, potentially changing which equilibria exist or which strategies are dominant. This sensitivity is the central analytical question of PA1. ## References and forward links **Primary references cited in this lecture:** - Nash, J. (1950). Equilibrium points in n-person games. *Proceedings of the National Academy of Sciences*, 36(1), 48--49. - Kakutani, S. (1941). A generalization of Brouwer's fixed point theorem. *Duke Mathematical Journal*, 8(3), 457--459. - Von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. *Mathematische Annalen*, 100(1), 295--320. - Wilson, R. (1971). Computing equilibria of n-person games. *SIAM Journal on Applied Mathematics*, 21(1), 80--87. - Harsanyi, J. C. (1973). Oddness of the number of equilibrium points: a new proof. *International Journal of Game Theory*, 2(1), 235--250. - Koutsoupias, E. and Papadimitriou, C. (1999). Worst-case equilibria. *STACS 1999*, 404--413. - Schelling, T. C. (1960). *The Strategy of Conflict*. Harvard University Press. - Harsanyi, J. C. and Selten, R. (1988). *A General Theory of Equilibrium Selection in Games*. MIT Press. - Chen, X. and Deng, X. (2006). Settling the complexity of two-player Nash equilibrium. *FOCS 2006*. - Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. (2006). The complexity of computing a Nash equilibrium. *STOC 2006*. **Textbook:** - Shoham, Y. and Leyton-Brown, K. *Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations*. Chapter 3 (Normal-Form Games). **Forward links within the course:** - Module 2, Lecture 5 covers support enumeration and Lemke-Howson in full algorithmic detail. - Module 2, Lecture 6 covers PPAD-completeness, approximate Nash equilibria, and the corrected complexity landscape for structured games. - Module 2, Lecture 7 derives the zero-sum LP formulation computationally and introduces Gambit (https://www.gambit-project.org). - Module 2, Lecture 8 introduces correlated equilibrium computation (LP), coarse correlated equilibrium, safe best response (Ganzfried and Sandholm, 2015), and empirical game-theoretic analysis (Wellman, 2006). - Module 3 covers regret minimization and convergence to coarse correlated equilibrium. - PA1 (due Week 3) asks students to estimate empirical payoff matrices from LLM agent interactions and perform Nash equilibrium and sensitivity analysis on the estimated games.