Computing the optimal strategy to commit to

By Vincent Conitzer, Tuomas Sandholm. ACM Conference on Economics and Computation, 2006

602 citations recorded by the source corpus.

In multiagent systems, strategic settings are often analyzed under the assumption that the players choose their strategies simultaneously. However, this model is not always realistic. In many settings, one player is able to commit to a strategy before the other player makes a decision. Such models are synonymously referred to as leadership, commitment, or Stackelberg models, and optimal play in such models is often significantly different from optimal play in the model where strategies are selected simultaneously.The recent surge in interest in computing game-theoretic solutions has so far ignored leadership models (with the exception of the interest in mechanism design, where the designer is implicitly in a leadership position). In this paper, we study how to compute optimal strategies to commit to under both commitment to pure strategies and commitment to mixed strategies, in both normal-form and Bayesian games. We give both positive results (efficient algorithms) and negative results (NP-hardness results).

Subfields: Management Science and Operations Research, Sociology and Political Science, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/7b3a3c7ac077474064e40b7baa5479ce2f36d4ea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Sociology and Political Science

In Statistical and Nonlinear Physics

Citations in the corpus

Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport (2008, methodology): “In particular, the main contribution of our paper is mapping the problem of security scheduling as a Bayesian Stackelberg game [4] and solving it via the fastest optimal algorithm for such games, addressing the first two challenges.”
From physical security to cybersecurity (2015, background): “Conitzer and Sandholm [15] provided the first complexity results and algorithms for computing optimal commitment strategies in Bayesian Stackelberg games, including both pure and mixed-strategy commitments.”
Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness (2011, methodology): “…a Stackelberg game frame-c work to model interactions between the security forces and attackers and to compute strategies for the security forces (Conitzer & Sandholm, 2006; Paruchuri et al., 2008; Kiekintveld et al., 2009; Basilico, Gatti, & Amigoni, 2009; Letchford, Conitzer, & Munagala, 2009;…”
Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games (2008, methodology): “DOBSS’s other main competitor is the multiple LPs method introduced by [5] to compute optimal leader strategies for non-Bayesian games.”
Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, background): “Such an equilibrium is called a Stackelberg Equilibrium (Conitzer and Sandholm, 2006).”
Protecting Moving Targets with Multiple Mobile Resources (2013, background): “…simultaneously, because the attacker can observe the defender’s daily schedules, any deterministic schedule by the defender can be exploited by the attacker (Paruchuri, Tambe, Ordóñez, & Kraus, 2006; Kiekintveld, Islam, & Kreinovich, 2013; Vorobeychik & Singh, 2012; Conitzer & Sandholm, 2006).”