# Lecture 14: Zero-Sum Games Source: https://www.youtube.com/watch?v=o6blhvYXfq4 Recap page: https://rapidrecap.app/video/o6blhvYXfq4 Generated: 2025-12-17T16:37:18.173+00:00 --- ## Quick Overview The lecture defines a two-player zero-sum game using a payoff matrix C, where the entry Cij represents the payment from the column player (Bob) to the row player (Alice), and establishes that every such game possesses a mixed Nash equilibrium, proven via von Neumann's min-max theorem derived from linear programming duality. **Key Points:** - A two-player zero-sum game involves a row player (Alice) with m strategies and a column player (Bob) with n strategies, defined by an m by n payoff matrix C, where Cij is the net payment from Bob to Alice. - The simple 'matching pennies game' (payoff matrix [1, -1; -1, 1]) has no pure Nash equilibrium because any announced strategy combination leads one player to have an incentive to deviate. - A mixed Nash equilibrium involves strategies x and y belonging to delta m and delta n, respectively, representing probability distributions over the players' pure strategies, with the condition that no player has a positive incentive to deviate. - Von Neumann's min-max theorem states that for any zero-sum game, the max over x of the min over y of x transpose Cy equals the min over y of the max over x of x transpose Cy, establishing the value lambda star. - Every two-player zero-sum game is guaranteed to have a mixed Nash equilibrium, derived from the optimal strategies (x* and y*) found in the max-min and min-max formulations of the game value. - The proof of the min-max theorem relies on showing that the LPs corresponding to the two scenarios (row player commits first vs. column player commits first) are duals of each other and both are feasible, thus strong duality holds. - For the lecture's 3x3 example game, the game value (lambda star) is 1/3, and the optimal mixed strategies are x* = [5/9, 0, 4/9] and y* = [0, 2/3, 1/3], illustrating how LP solutions reveal optimal play where pure strategies fail. **Context:** Ankur Moitra introduces the concept of zero-sum games, specifically focusing on two-player games defined by a payoff matrix C that dictates the net transfer of money between the row player (Alice) and the column player (Bob). The lecture contrasts simple, intuitive games like 'matching pennies' with more complex scenarios, demonstrating that while pure Nash equilibria are easy to analyze, they do not always exist, necessitating the introduction of mixed Nash equilibria which involve randomization over strategies. ## Detailed Analysis The lecture systematically builds the framework for analyzing zero-sum games, starting with the definition involving an m x n payoff matrix C, where Cij is the amount Alice receives from Bob. The insufficiency of pure Nash equilibria is shown using the matching pennies example, where deviation incentives always exist. The solution is extended to mixed Nash equilibrium, where players select probability distributions x in delta m and y in delta n. The condition for no incentive to deviate is mathematically translated into linear inequalities, noting that checking deviation against pure strategies suffices due to linearity (a concept linked to weak duality). The core result is von Neumann's min-max theorem, which asserts the equality between maximizing the guaranteed minimum payoff (max over x, min over y of x transpose Cy) and minimizing the maximum expected loss (min over y, max over x of x transpose Cy), establishing the game value lambda star. This theorem is proven by showing the two corresponding LPs are duals; feasibility in both guarantees strong duality, thus proving the theorem. A direct corollary is that every two-player zero-sum game possesses a mixed Nash equilibrium (x*, y*), derived from the optimal solutions of the min-max formulations. This framework is then applied to a 3x3 example matrix where lambda star = 1/3, and the optimal strategies x* and y* are calculated, showing that irrational play (like playing strategy 2 for Alice) is eliminated, and complementary slackness explains why certain pure strategies are never played in equilibrium. ### Two-Player Zero-Sum Game Components - Row player Alice (m strategies) - Column player Bob (n strategies) - Payoff matrix C where Cij is payment from Bob to Alice - Zero sum means wins and losses add to 0 ### Pure Nash Equilibrium Definition - A pair (i, j) where row player has no incentive to deviate if for all i prime, C(i prime)j <= Cij - Column player has no incentive if for all j prime, Cij prime >= Cij - Matching pennies lacks a pure Nash equilibrium ### Mixed Nash Equilibrium - Strategies are probability distributions x in delta m and y in delta n (non-negative entries summing to 1) - No incentive to deviate means expected payoff from deviating to any pure strategy is not strictly better than the expected payoff from the mixed strategy ### Von Neumann's Min-Max Theorem - lambda star = max_x min_y (x'Cy) = min_y max_x (x'Cy) - Equivalence of pre-committing strategies, overcoming the ordering advantage seen in deterministic games ### Proof Strategy using LP Duality - The max-min scenario (Scenario 2, primal P) and min-max scenario (Scenario 1, dual D) are formulated as dual LPs - Since both are feasible (any distribution yields a finite lambda), strong duality holds, proving the theorem ### Existence of Mixed Nash Equilibrium - Every zero-sum game has a mixed Nash equilibrium derived from the optimal strategies x* and y* in the min-max and max-min formulations, respectively - Complementary slackness links the optimal strategies to zero slack in the dual constraints ### Application to 3x3 Example - Game value lambda star is 1/3 - Optimal row strategy x* = [5/9, 0, 4/9] - Optimal column strategy y* = [0, 2/3, 1/3] - The optimal strategy dictates never playing strategy a2 (for Alice) or b1 (for Bob)