MIT Department of Electrical Engineering & Computer Science

DATE: MONDAY, MARCH 20, 1995

TIME: Refreshments at 2:45
TALK AT 3:00

PLACE: NE43-518

Practical Solutions to Game Theoretic Problems

Daphne Koller
U.C. Berkeley

Many situations where a number of agents interact strategically can be naturally described as multi-player games. These include real-world problems such as bidding on oilfield drilling rights, as well as many important problems in computer science such as load sharing in a distributed system or coordinating the goals and actions of multiple agents on a factory floor. The representation as a game allows one to reason formally about the situation using established techniques from the discipline of game theory. In particular, the game-theoretic notion of a solution to a game often helps in designing mechanisms for dealing with the original situation. But while the formal notion of `solution' is well-established, standard techniques for solving games are computationally impractical for most realistic games.

In this talk, I describe a new framework for specifying and solving games. In particular, I will present a new paradigm for solving games of incomplete information, where randomized strategies are typically needed in order to play the game optimally. I demonstrate algorithms for solving such games that are exponentially faster than the standard ones, and present experimental results showing that these algorithms are faster in practice, as well as in theory. These algorithms allow the solution of games that are orders of magnitude larger than are currently possible. I then describe the Gala system, which allows very large games to be easily specified and solved. The system allows a concise and simple specification of games using a declarative knowledge- representation language designed particularly for games. These results, and their implementation within the Gala system, make game theory a practical tool for analyzing strategic interaction.

Parts of this research are joint work with Nimrod Megiddo, Avi Pfeffer, and Bernhard von Stengel.

HOST: Prof. G. Sussman