A Unified Framework for Extensive-Form Game Abstraction with Bounds
Authors: Christian Kroer, Tuomas Sandholm
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we present a unified framework for analyzing abstractions that can express all types of abstractions and solution concepts used in prior papers with performance guarantees while maintaining comparable bounds on abstraction quality. Moreover, our framework gives an exact decomposition of abstraction error in a much broader class of games, albeit only in an ex-post sense, as our results depend on the specific strategy chosen. Nonetheless, we use this ex-post decomposition along with slightly weaker assumptions than prior work to derive generalizations of prior bounds on abstraction quality. We also show, via counterexample, that such assumptions are necessary for some games. Finally, we prove the first bounds for how -Nash equilibria computed in abstractions perform in the original game. All our results apply to general-sum n-player games. |
| Researcher Affiliation | Academia | Christian Kroer Computer Science Department Pittsburgh, PA 15213 ckroer@cs.cmu.edu Tuomas Sandholm Computer Science Department Pittsburgh, PA 15213 sandholm@cs.cmu.edu |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. It presents mathematical definitions, lemmas, and theorems. |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments that use datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup requiring specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not list any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |