REPRESENTATIONS AND SOLUTIONS FOR GAME-THEORETIC PROBLEMS

A system with multiple interacting agents (whether artificial or human ) is often best analyzed using game-theoretic tools. Unfortunately, wh ile the formal foundations are well-established, standard computationa l techniques for game-theoretic reasoning are inadequate for dealing w ith realistic games, This paper describes the Gala system, an implemen ted system that allows the specification and efficient solution of lar ge imperfect information games. The system contains the first implemen tation 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 jus t in theory. It therefore allows the solution of games that are orders of magnitude larger than were previously possible. The system also pr ovides a new declarative language for compactly and naturally represen ting games by their rules. As a whole, the Gala system provides the ca pability for automated game-theoretic analysis of complex real-world s ituations. (C) 1997 Elsevier Science B.V.