0937e642_Game_Theory_Discussion_Group__Title_and_abstract
[Date/Time] October 19, 2004 5:30 -- 7:00 PM [Location] Wean 4625 [Speaker] Andrew Gilpin [Title and abstract] 
Computing equilibria in large imperfect information games A fundamental problem in game theory and artificial intelligence is computing an equilibrium in an extensive form game. In this paper, we study ways of extending previous work on equilibrium computation to games with a large representation. We introduce an automatic way of reducing an extensive form game to a smaller representation which results in faster solution times with standard equilibrium finding algorithms. We describe game transformations from a theoretical point of view and discuss desiderata of a game transformation that we consider necessary for an application of game transformations. We introduce the notion of an extensive game isomorphism and the related notion of the subgame isomorphic game abstraction transformation. We prove that a Nash equilibrium in the smaller, abstracted game can be easily converted to a Nash equilibrium in the original game, thus demonstrating the power and efficacy of our method. We present experimental results for a class of poker games, and we find an equilibrium for the largest poker games to date. We also present an algorithm, GameShrink, which provides an efficient method of performing the subgame isomorphic game abstraction transformations. Finally, we conclude with game approximation methods that do not support equilibrium preservation, but nevertheless result in strategies that work well in practice. In this talk, I will briefly review games in extensive form. I will also survey previous work including the sequence form representation of a game in extensive form as well as methods for computing equilibria in two-player zero-sum games. Thus, there is no necessary background for this talk.
Game Theory Discussion Group
Title and abstract