On Stackelberg mixed strategies

It is sometimes the case that one solution concept in game theory is equivalent to applying another solution concept to a modified version of the game. In such cases, does it make sense to study the former separately (as it applies to the original representation of the game), or should we entirely subordinate it to the latter? The answer probably depends on the particular circumstances, and indeed the literature takes different approaches in different cases. In this article, I consider the specific example of Stackelberg mixed strategies. I argue that, even though a Stackelberg mixed strategy can also be seen as a subgame perfect Nash equilibrium of a corresponding extensive-form game, there remains significant value in studying it separately. The analysis of this special case may have implications for other solution concepts.

1. One line of work concerns settings where there are many selfish followers and a single benevolent leader, for example a party that “owns” the system and controls part of the activity in it, who acts to optimize some system-wide objective. See, e.g., Roughgarden (2004). In this article I will not assume that the leader is benevolent.

2. Note that player 1 merely stating that she will play D, without any commitment, will not work: she would always have an incentive to back out and play U after all, to collect an additional 1 unit of utility, regardless of what player 2 plays. Player 2 will anticipate this and play L anyway.

3. Schelling (1960) similarly suggests that, by the time we have incorporated aspects such as commitment moves into a standard game-theoretic representation of the game at hand, we have abstracted away these issues and are at some level not really studying them anymore.

4. It is easy to be misled by Fig. 3 into thinking that it does make this fairly obvious, due to the natural ordering of the mixed strategies from left to right. However, this is an artifact of the fact that there are only two pure strategies for player 1 in the original game. If there were three pure strategies, it would not be possible to order the mixed strategies so naturally from left to right. We could in principle visualize the resulting tree in three dimensions instead of two. For more pure strategies, this of course becomes problematic. More importantly, such visualizations are technically not part of the extensive form. The extensive form only specifies a set of actions for each node, and no ordering, distance function, or topology on them. Such are only added when we draw the tree on a piece of paper (or in three dimensions, etc.).

5. Constant-sum games, in which \(u_1(s_1,s_2)+u_2(s_1,s_2)=c\) for some constant c, are effectively equivalent.

6. In fact, he pointed out that there was a case in which his reduction from linear programs to zero-sum games does not work; this gap was later filled by Adler (2013).

7. Papadimitriou (1994) introduced the class PPAD. Daskalakis and Papadimitriou (2005) showed that the problem is PPAD-hard for three players; Chen and Deng (2005) then obtained the stronger result that it is PPAD-hard even for two players. Etessami and Yannakakis (2010) proved that with three or more players, the problem of computing an exact Nash equilibrium, rather than an \(\epsilon \)-equilibrium, is FIXP-complete.

8. An exception is, of course, if we play against an exploitable non-game-theoretic player, such as one who always plays Scissors.

9. For a study of how much it can help, see Letchford et al. (2014).

10. All of this is easily generalized to n players, but for simplicity I will stick to two players here.

11. The notation here is a bit nonstandard: in isolation, it would be more natural to use \(A_i\) to denote the set of actions and \(S_i\) to denote the set of pure strategies, i.e., mappings from signals to actions. However, in order to make the comparison to other concepts easier, it will help to stick to using \(s_i\) for the rows and columns of the game.

12. Nash equilibria of a game with private information are often referred to as Bayes-Nash equilibria.

13. It could be argued that the analogy is imperfect because in the Stackelberg version of the argument, the game is modified to a single (two-stage) game, whereas in the correlated equilibrium version of the argument, two different correlated equilibria potentially require different ways of modifying the game, extending them with different signaling schemes. It is not entirely clear to me how significant this distinction is. In any case, if two correlated equilibria require different signaling schemes, then consider a new, joint signaling scheme where each player receives the signals from both signaling schemes, with the signals drawn independently across the two schemes. Then, both correlated equilibria are (Bayes-)Nash equilibria of the game with the joint signaling scheme (with the players simply ignoring the part of the signal that corresponds to the other equilibrium). Taking this to the limit, we may imagine a single, universal signaling scheme such that all correlated equilibria of interest are Nash equilibria of the game with this universal signaling scheme.

I thank the LOFT and Synthese reviewers for helpful feedback, and ARO and NSF for support under Grants W911NF-12-1-0550, W911NF-11-1-0332, IIS-0953756, CCF-1101659, CCF-1337215, and IIS-1527434.

Authors and Affiliations

1. Duke University, Box 90129, Durham, NC, 27708, USA

   Vincent Conitzer

Corresponding author

Correspondence to Vincent Conitzer.

Reprints and permissions