Algorithmic Game Theory: Equilibrium Computation for Two-Player Games in Strategic and Extensive Form

Abstract We explain algorithms for computing Nash equilibria of two-player games given in strategic form or extensive form. The strategic form is a table that lists the players' strategies and resulting payoffs. The “best response” condition states that in equilibrium, all pure strategies in the support of a mixed strategy must get maximal, and hence equal, payoff. The resulting equations and inequalities define polytopes, whose “completely labeled” vertex pairs are the Nash equilibria of the game. The Lemke–Howson algorithm follows a path of edges of the polytope pair that leads to one equilibrium. Extensive games are game trees, with information sets that model imperfect information of the players. Strategies in an extensive game are combinations of moves, so the strategic form has exponential size. In contrast, the linear-sized sequence form of the extensive game describes sequences of moves and how to randomize between them. Introduction A basic model in noncooperative game theory is the strategic form that defines a game by a set of strategies for each player and a payoff to each player for any strategy profile (which is a combination of strategies, one for each player). The central solution concept for such games is the Nash equilibrium , a strategy profile where each strategy is a best response to the fixed strategies of the other players. In general, equilibria exist only in mixed (randomized) strategies, with probabilities that fulfill certain equations and inequalities.