Loading...
Please wait, while we are loading the content...
Similar Documents
Extensive-Form Game Abstraction With Bounds
| Content Provider | CiteSeerX |
|---|---|
| Author | Kroer, Christian |
| Abstract | Abstraction has emerged as a key component in solving extensive-form games of incomplete information. However, loss-less abstractions are typically too large to solve, so lossy abstraction is needed. All prior lossy abstraction algorithms for extensive-form games either 1) had no bounds on solution quality or 2) depended on specific equilibrium computation ap-proaches, limited forms of abstraction, and only decreased the number of information sets rather than nodes in the game tree. We introduce a theoretical framework that can be used to give bounds on solution quality for any perfect-recall extensive-form game. The framework uses a new notion for mapping abstract strategies to the original game, and it leverages a new equilibrium refinement for analysis. Using this framework, we develop the first general lossy extensive-form game abstrac-tion method with bounds. Experiments show that it finds a lossless abstraction when one is available and lossy abstractions when smaller abstractions are desired. While our framework can be used for lossy abstraction, it is also a powerful tool for lossless abstraction if we set the bound to zero. Prior abstraction algorithms typically operate level by level in the game tree. We introduce the extensive-form game tree isomorphism and action subset selection problems, both important problems for computing abstractions on a level-by-level basis. We show that the former is graph isomorphism complete, and the latter NP-complete. We also prove that level-by-level abstraction can be too myopic and thus fail to find even obvious lossless abstractions. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Extensive-form Game Abstraction Lossy Abstraction Lossless Abstraction Game Tree Solution Quality Extensive-form Game Information Set Graph Isomorphism Level-by-level Abstraction Action Subset Selection Problem Important Problem Prior Abstraction Algorithm Prior Lossy Abstraction Algorithm Abstract Strategy Incomplete Information Perfect-recall Extensive-form Game New Notion Latter Np-complete Loss-less Abstraction Theoretical Framework Specific Equilibrium Computation Ap-proaches New Equilibrium Refinement Level-by-level Basis Original Game Powerful Tool Limited Form Obvious Lossless Abstraction Key Component Extensive-form Game Tree Isomorphism Operate Level |
| Content Type | Text |
