From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

By AmirMahdi Ahmadinejad, Sina Dehghani, M. Hajiaghayi, Brendan Lucier, Hamid Reza Mahini, Saeed Seddighin. 2016

78 citations recorded by the source corpus.

We study the problem of computing Nash equilibria of zero-sum games.Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, toadvertisement, to sports.However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible.Indeed, despite its importance, only few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied.

Subfields: Computer Networks and Communications, Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

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

In Computer Networks and Communications

1. Simon Lacoste-Julien
2. Tony Jebara
3. Gauthier Gidel

In Economics and Econometrics

1. Simon Lacoste-Julien
2. Gauthier Gidel

In Management Science and Operations Research

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Tony Jebara

In Game & Decision Theory

1. Simon Lacoste-Julien
2. Gauthier Gidel

Citations in the corpus

• Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “However, in situations such as the Colonel Blotto game or the Matching Duel (Ahmadinejad et al., 2016), the strategy space is intractably large and defined by an exponential number of linear constraints.”