Abstraction Pathologies in Extensive Games

Kevin Waugh, Dave Schnizlein, Michael Bowling, and Duane Szafron. Abstraction Pathologies in Extensive Games. In Proceedings of the Eighth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 781–788, 2009.

Download

[PDF] 

Abstract

Extensive games can be used to model many scenarios in which multiple agents interact with an environment. There has been considerable recent research on finding strong strategies in very large, zero-sum extensive games. The standard approach in such work is to employ abstraction techniques to derive a more tractably sized game. An extensive game solver is then employed to compute an equilibrium in that abstract game, and the resulting strategy is presumed to be strong in the full game. Progress in this line of research has focused on solving larger abstract games, which more closely resemble the full game. However, there is an underlying assumption that by abstracting less, and solving a larger game, an agent will have a stronger strategy in the full game. In this work we show that this assumption is not true in general. Refining an abstraction can actually lead to a weaker strategy. We show examples of these abstraction pathologies in a small game of poker that can be analyzed exactly. These examples show that pathologies arise when abstracting both chance nodes as well as a player's actions. In summary, this paper shows that the standard approach to finding strong strategies for large extensive games rests on shaky ground.

Errata

There were incorrect values in Table 3 of the original paper appearing in the AAMAS proceedings. This version has been corrected. The new values do not change the conclusions drawn.

BibTeX

@InProceedings(09aamas-abstraction,
  Title = "Abstraction Pathologies in Extensive Games",
  Author = "Kevin Waugh and Dave Schnizlein and Michael Bowling and Duane Szafron",
  Booktitle = "Proceedings of the Eighth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)",
  Year = "2009",
  Pages = "781--788",
  AcceptRate = "22\%",
  AcceptNumbers = "132 of 591"
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:28