Computation of Stackelberg equilibria of finite sequential games

DOI10.1007/978-3-662-48995-6_15MaRDI QIDQ3460789zbMATH OpenOpenAlexFDO

Authors Branislav Bošanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1507.07677

zbMATH Keywords

computational complexityfinite sequential gamesStackelberg equilibria

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Multistage and repeated games (91A20) Hierarchical games (including Stackelberg games) (91A65)

Abstract: The Stackelberg equilibrium solution concept describes optimal strategies to commit to: Player 1 (termed the leader) publicly commits to a strategy and Player 2 (termed the follower) plays a best response to this strategy (ties are broken in favor of the leader). We study Stackelberg equilibria in finite sequential games (or extensive-form games) and provide new exact algorithms, approximate algorithms, and hardness results for several classes of these sequential games.

Recommendations

• Sequential Stackelberg equilibria in two-person games
• Computing Stackelberg equilibria of large general-sum games
• On-line computation of Stackelberg equilibria with synchronous parallel genetic algorithms
• Computing a pessimistic Stackelberg equilibrium with multiple followers: the mixed-pure case
• Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games

Cites work

• Extensive-form correlated equilibrium: definition and computational complexity
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Security and Game Theory

Cited in

(17)

• A constructive approach to sequential Nash equilibria
• Sequential Stackelberg equilibria in two-person games
• The Stackelberg equilibrium for one-sided zero-sum partially observable stochastic games
• Committing to correlated strategies with multiple leaders
• A Markovian Stackelberg game approach for computing an optimal dynamic mechanism
• Computing Stackelberg equilibria of large general-sum games
• Computing a pessimistic Stackelberg equilibrium with multiple followers: the mixed-pure case
• A Stackelberg equilibrium for a missile procurement problem
• Game theory on the blockchain: a model for games with smart contracts
• Learning and approximating the optimal strategy to commit to
• Optimally Deceiving a Learning Leader in Stackelberg Games
• On Stackelberg mixed strategies
• An Algorithmic Equilibrium Solution for n-Person Dynamic Stackelberg Difference Games with Open-Loop Information Pattern
• Repeated sequential prisoner's dilemma: the Stackelberg variant
• Watch and learn: optimizing from revealed preferences feedback
• Optimal private payoff manipulation against commitment in extensive-form games
• On-line computation of Stackelberg equilibria with synchronous parallel genetic algorithms

This page was built for publication: Computation of Stackelberg equilibria of finite sequential games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460789)