Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games
| Autor: | Jiri Cermak, Branislav Bosansky, Karel Durkota, Viliam Lisy, Christopher Kiekintveld |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Proceedings of the AAAI Conference on Artificial Intelligence. 30 |
| ISSN: | 2374-3468 2159-5399 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|