Representations and Solutions for Game-Theoretic Problems (1997)by D. Koller and A. Pfeffer
A system with multiple interacting agents (whether artificial or human) is often best analyzed using game-theoretic tools. Unfortunately, while the formal foundations are well-established, standard computational techniques for game-theoretic reasoning are inadequate for dealing with realistic games. This paper describes the Gala system an implemented system that allows the specification and efficient solution of large imperfect information games. The system contains the first implementation of a recent algorithm, due to Koller, Megiddo, and von Stengel. Experimental results from the system demonstrate that the algorithm is exponentially faster than the standard algorithm in practice, not just in theory. It therefore allows the solution of games that are orders of magnitude larger than were previously possible. The system also provides a new declarative language for compactly and naturally representing games by their rules. As a whole, the Gala system provides the capability for automated game-theoretic analysis of complex real-world situations.
D. Koller and A. Pfeffer (1997). "Representations and Solutions for Game-Theoretic Problems." Artificial Intelligence, 94(1), 167-215.
Full version of paper in IJCAI '95.
author = "D. Koller and A. Pfeffer",
title = "Representations and Solutions for Game-Theoretic
journal = "Artificial Intelligence",
volume = "94",
number = "1",
pages = "167--215",
year = "1997",
note = "Full version of paper in IJCAI '95",