Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games
Abstract
Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.
Cite
Text
Cermak et al. "Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10045Markdown
[Cermak et al. "Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/cermak2016aaai-using/) doi:10.1609/AAAI.V30I1.10045BibTeX
@inproceedings{cermak2016aaai-using,
title = {{Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games}},
author = {Cermak, Jiri and Bosanský, Branislav and Durkota, Karel and Lisý, Viliam and Kiekintveld, Christopher},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {439-445},
doi = {10.1609/AAAI.V30I1.10045},
url = {https://mlanthology.org/aaai/2016/cermak2016aaai-using/}
}