Lecture 14: Zero-Sum Games

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.