Tehran Institute for Advanced Studies (TEIAS)

/ Polynomial-Time Algorithms for Colonel Blotto __ Sina Dehghani


Polynomial-Time Algorithms for Colonel Blotto

June 21, 2021
(31 Khordad, 1400)



This Talk is online

Registration Deadline

June 20, 2021

You may need a VPN to start the talk.


Dr. Sina Dehghani

Post-Doctoral Research Fellow at the IPM


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.


Sina Dehghani is a post-doctoral research fellow at the Institute for Research in Fundamental Sciences (IPM). Prior to that he was a PhD student of Computer Science Department at the University of Maryland at College Park under the supervision of Prof. MohammadTaghi Hajiaghayi. He finished his undergraduate studies at Sharif University of Technology.