An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games
Abstract
This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in repeated games with discounting. The process starts with a single hypercube approximation of the set of SPE payoff profiles. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any SPE point are gradually withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mixed integer program. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata.
Cite
Text
Burkov and Chaib-draa. "An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games." AAAI Conference on Artificial Intelligence, 2010. doi:10.1609/AAAI.V24I1.7623Markdown
[Burkov and Chaib-draa. "An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games." AAAI Conference on Artificial Intelligence, 2010.](https://mlanthology.org/aaai/2010/burkov2010aaai-approximate/) doi:10.1609/AAAI.V24I1.7623BibTeX
@inproceedings{burkov2010aaai-approximate,
title = {{An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games}},
author = {Burkov, Andriy and Chaib-draa, Brahim},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2010},
pages = {729-736},
doi = {10.1609/AAAI.V24I1.7623},
url = {https://mlanthology.org/aaai/2010/burkov2010aaai-approximate/}
}