Games and Economic Behavior · 1996 · 224 citations · 14 references
The Nash equilibria of a two‑person, non‑zero‑sum game are solutions of a linear complementarity problem, yet the classical normal form is often exponentially large, whereas perfect‑recall games admit a linear‑sized sequence form. The authors first convert the extensive‑form game to a strategic description, such as the normal form, to apply the LCP framework. For the resulting small LCP, the authors show that an equilibrium can be found efficiently using Lemke's algorithm, a generalization of the Lemke–Howson method. Journal of Economic Literature Classification Number: C72.
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, the game must first be converted 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. If the game has perfect recall, a linear-sized strategic description is the sequence form. For the resulting small LCP, we show that an equilibrium is found efficiently by Lemke's algorithm, a generalization of the Lemke–Howson method.Journal of Economic LiteratureClassification Number: C72.
14