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.
For one-shot games, the problem of computing a Stackelberg equilibrium is polynomial @cite_4 in contrast to the PPAD-completeness of a Nash equilibrium @cite_1 @cite_16 . The situation changes in extensive-form games where Letchford and Conitzer showed @cite_15 that for many cases the problem is NP-hard, while it still remains PPAD-complete for a Nash equilibrium @cite_23 . More specifically, computing Stackelberg equilibria is polynomial only for: games with perfect information with no chance on DAGs where the leader commits to a pure strategy, games with perfect information with no chance on trees. Introducing chance or imperfect information leads to NP-hardness. However, several cases were unexplored by the existing work, namely extensive-form games with perfect information and concurrent moves. We address this subclass in this work.
@cite_4 @cite_1 @cite_23 @cite_15 @cite_16
1971309210 2140790422 2096651633 2055887369 2057913812
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). We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions. A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result — even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known. Computing optimal strategies to commit to in general normal-form or Bayesian games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. In this paper, we extend this line of work to the more general case of commitment in extensive-form games. We show that in some cases, the optimal strategy can be computed in polynomial time; in others, computing it is NP-hard. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: —Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. —The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are PPAD-hard to compute.