Constructing small sample spaces satisfying given constraints
Daphne Koller, Nimrod Lvlegiddo
STOC 1993
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 Literature Classification Number: C72. © 1996 Academic Press, Inc.
Daphne Koller, Nimrod Lvlegiddo
STOC 1993
Daphne Koller, Nimrod Megiddo
International Journal of Game Theory
Daphne Koller, Nimrod Megiddo
Games and Economic Behavior
Edith Cohen, Nimrod Megiddo
Mathematical Programming