Abstract. The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, it is rst necessary to convert the game to a strategic description such as the normal form. The classical normal form, however, is often exponentially large in the size of the game tree. In this paper we suggest an alternative approach, based on the sequence form of the game. For a game with perfect recall, the sequence form is a linear sized strategic description, which results in an LCP of linear size. For this LCP, w e show that an equilibrium is found by Lemke's algorithm, a generalization of the Lemke-Howson method.
REF present an LP whose size is linear in the size of the game tree.
Efficient computation of equilibria for extensive two-person games
GAMES AND ECONOMIC BEHAVIOR
Mathematics