×

zbMATH — the first resource for mathematics

Computation of Stackelberg equilibria of finite sequential games. (English) Zbl 1404.91022
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 201-215 (2015).
Summary: The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader’s choice. We study Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games.
For the entire collection see [Zbl 1326.68026].
MSC:
91A20 Multistage and repeated games
91A65 Hierarchical games (including Stackelberg games)
91A05 2-person games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bosansky, B., Cermak, J.: Sequence-form algorithm for computing stackelberg equilibria in extensive-form games. In: Proceedings of AAAI (2015)
[2] Conitzer, V., Korzhyk, D.: Commitment to correlated strategies. In: Proceedings of AAAI, pp. 632–637 (2011)
[3] Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: Proceedings of ACM-EC, pp. 82–90 (2006) · doi:10.1145/1134707.1134717
[4] De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational Geometry, 2nd edn. Springer, Heidelberg (2000) · Zbl 0939.68134 · doi:10.1007/978-3-662-04245-8
[5] Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gröbner bases. SIAM J. Discrete Math. 6(2), 246–269 (1993) · Zbl 0798.68157 · doi:10.1137/0406019
[6] Letchford, J.: Computational aspects of Stackelberg games. Ph.D. thesis, Duke University (2013)
[7] Letchford, J., Conitzer, V.: Computing optimal strategies to commit to in extensive-form games. In: Proceedings of ACM-EC, pp. 83–92. ACM (2010) · doi:10.1145/1807342.1807354
[8] Letchford, J., MacDermed, L., Conitzer, V., Parr, R., Isbell, C.L.: Computing optimal strategies to commit to in stochastic games. In: Proceedings of AAAI, pp. 1380–1386 (2012)
[9] Paruchuri, P., Pearce, J., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving bayesian stackelberg games. In: Proceedings of AAMAS, pp. 895–902 (2008)
[10] von Stackelberg, H.: Marktform und gleichgewicht. Springer-Verlag (1934)
[11] von Stengel, B., Forges, F.: Extensive-form correlated equilibrium: definition and computational complexity. Math. Oper. Res. 33(4), 1002–1022 (2008) · Zbl 1232.91039 · doi:10.1287/moor.1080.0340
[12] Tambe, M.: Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press, Cambridge (2011) · Zbl 1235.91005 · doi:10.1017/CBO9780511973031
[13] Xu, H., Rabinovich, Z., Dughmi, S., Tambe, M.: Exploring information asymmetry in two-stage security games. In: Proceedings of AAAI (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.