Overview

In the classical discrete Colonel Blotto game -introduced by Borel in 1921- two colonels simultaneously distribute their troops across multiple battlefields. The winner of each battlefield is determined by a winner-take-all rule, independently of other battlefields. In the original formulation, each colonel’s goal is to win as many battlefields as possible. The Blotto game and its extensions have been used in a wide range of applications from political campaign -exemplified by the U.S presidential election- to marketing campaign, from (innovative) technology competition to sports competition. Despite persistent efforts, efficient methods for finding the optimal strategies in Blotto games have been elusive for almost a century -due to exponential explosion in the organic solution space- until Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin developed the first polynomial-time algorithm for this fundamental game-theoretical problem in 2016. In this talk I would briefly talk about their method, and further discuss how one can obtain faster and simpler algorithms, and finally discuss a more general setting of the two-player-multi-battleground game, in which multifaceted resources (troops) may have different contributions to different battle-grounds.