My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Efficient Computation of Equilibria for Extensive Two-Person Games (1996)

by D. Koller, N. Megiddo, and B. von Stengel


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, 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.

Download Information

D. Koller, N. Megiddo, and B. von Stengel (1996). "Efficient Computation of Equilibria for Extensive Two-Person Games." Games and Economic Behavior, 14(2). pdf ps.gz

Bibtex citation

@article{Koller+al:GEB96,
  author =       "D. Koller and N. Megiddo and B. {von Stengel}",
  title =        "Efficient Computation of Equilibria for Extensive
                 Two-Person Games",
  journal =      "Games and Economic Behavior",
  volume =       "14",
  number = 2,
  year =         "1996",
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal