Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games

ABSTRACT

Dynamic interaction appears in many real-world scenarios where players are able to observe (perhaps imperfectly) the actions of another player and react accordingly. We consider the baseline representation of dynamic games - the extensive form - and focus on computing Stackelberg equilibrium (SE), where the leader commits to a strategy to which the follower plays a best response. For one-shot games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy space. Our experimental evaluation confirms that we are able to compute SE by considering only a fraction of the strategy space that often leads to a significant speed-up in computation times.

References

1. Branislav Bo'sansk´y, Simina Br^anzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, and Peter Bro Miltersen. 2017. Computation of Stackelberg Equilibria of Finite Sequential Games. ACM Transactions on Economics and Computation 5, 4, Article 23 (Dec. 2017), 24 pages.
2. Branislav Bo'sansk´y, Albert Xin Jiang, Milind Tambe, and Christopher Kiekintveld. 2015. Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.
3. Branislav Bo'sansk´y, Christopher Kiekintveld, Viliam Lis´y, and Michal Pěchouček. 2014. An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information. Journal of Artificial Intelligence Research 51 (2014), 829--866.
4. Branislav Bo'sansk´y and Jiõ´ Cerm´ak. 2015. Sequence-Form Algorithm for Computing Stackelberg - Equilibria in Extensive-Form Games. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. 805--811.
5. Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. 2015. Heads-up limit holdem poker is solved. Science 347, 6218 (2015), 145--149.
6. Karel Durkota, Viliam Lis´y, Christopher Kiekintveld, Branislav Bo'sansk´y, and Michal Pěchouček. 2016. Case Studies of Network Defense with Attack Graph Games. IEEE Intelligent Systems 31, 5 (2016), 24--30.
7. Karel Durkota, Viliam Lis´y, Christopher Kiekintveld, Karel Hor´ak, Branislav Bo'sansk´y, and Tom´a's Pevn´y. 2017. Optimal Strategies for Detecting Data Exfiltration by Internal and External Attackers. In GameSec 2017, LNCS 10575. 171--192.
8. Manish Jain, Erim Kardes, Christopher Kiekintveld, Fernando Ord´onez, and Milind Tambe. 2010. Security Games with Arbitrary Schedules: A Branch and Price Approach.. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence.
9. Manish Jain, Milind Tambe, and Christopher Kiekintveld. 2011. Quality-bounded solutions for finite Bayesian Stackelberg games: Scaling up. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems. 997--1004.
10. Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. 1996. Efficient Computation of Equilibria for Extensive two-person Games. Games and Economic Behavior (1996), 247--259.
11. Christian Kroer, Gabriele Farina, and Tuomas Sandholm. 2018. Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead. In Proceedings of Thirty-Second AAAI Conference on Artificial Intelligence.
12. George Leitmann. 1978. On generalized Stackelberg strategies. Journal of Optimization Theory and Applications 26, 4 (1978), 637--643.
13. Joshua Letchford and Vincent Conitzer. 2010. Computing Optimal Strategies to Commit to in ExtensiveForm Games. In Proceedings of the 11th ACM conference on Electronic commerce. 83--92.
14. H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum. 2003. Planning in the Presence of Cost Functions Controlled by an Adversary. In Proceedings of the International Conference on Machine Learning. 536--543.
15. Matěj Moravč´k, Martin Schmid, Neil Burch, Viliam Lis´y, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. 2017. DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker. Science (2017).
16. Tuomas Sandholm. 2015. Steering evolution strategically: computational game theory and opponent exploitation for treatment planning, drug design, and synthetic biology. In Proceedings of the TwentyNinth AAAI Conference on Artificial Intelligence. AAAI Press, 4057--4061.
17. Marten Van Dijk, Ari Juels, Alina Oprea, and Ronald L Rivest. 2013. FlipIt: The game of stealthy takeover. Journal of Cryptology 26, 4 (2013), 655--713.
18. Ondřej Vaněk. 2013. Computational Methods for Transportation Security. Ph.D. Dissertation. Czech Technical University in Prague.
19. Jir´ Cerm´ak, Branislav Bo'sansk´y, Karel Durkota, Viliam Lis´y, and Christopher Kiekintveld. 2016. Using - Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games. In Proceedings of Thirtieth AAAI Conference on Artificial Intelligence. 439--445.
20. Bernhard von Stengel. 1996. Efficient Computation of Behavior Strategies. Games and Economic Behavior 14 (1996), 220--246.
21. Bernhard von Stengel and Fran¸coise Forges. 2008. Extensive-Form Correlated Equilibrium: Definition and Computational Complexity. Mathematics of Operations Research 33, 4 (2008), 1002--1022.
22. Bernhard von Stengel and Shmuel Zamir. 2004. Leadership with Commitment to Mixed Strategies. Technical Report. CDAM Research Report LSE-CDAM-2004-01.
23. Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. 2016. Signaling in bayesian stackelberg games. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 150--158.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic game theory

      • Exact and approximate computation of equilibria