Paper Info
Title
Abstraction pathologies in extensive games
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.
Year
DOI
Venue
2009
10.5555/1558109.1558119
AAMAS (2)
Keywords
Field
DocType
larger game,extensive game,large extensive game,strong strategy,full game,larger abstract game,standard approach,extensive game solver,abstraction pathology,small game,abstract game,equilibrium,economics,game theory,abstraction
Combinatorial game theory,Game mechanics,Computer science,Simulations and games in economics education,Repeated game,Game theory,Artificial intelligence,Normal-form game,Sequential game,Non-cooperative game
Conference
Citations 
PageRank 
References 
39
2.08
10
Authors
4
Name
Order
Citations
PageRank
Kevin Waugh121715.18
David Schnizlein2825.31
Michael H. Bowling32460205.07
D. Szafron41579210.88