The competition between the Republican and the Democrat nominees in the U.S presidential election is known as Colonel Blotto in game theory. In the classical Colonel Blotto game -- introduced by Borel in 1921 -- two colonels simultaneously distribute their troops across multiple battlefields. The outcome of each battlefield is determined by a winner-take-all rule, independently of other battlefields. In the original formulation, the goal of each colonel is to win as many battlefields as possible. The Colonel Blotto game and its extensions have been used in a wide range of applications from political campaigns (exemplified by the U.S presidential election) to marketing campaigns, from (innovative) technology competitions, to sports competitions. For almost a century, there have been persistent efforts for finding the optimal strategies of the Colonel Blotto game, however it was left unanswered whether the optimal strategies are polynomially tractable. In this thesis, we present several algorithms for solving Blotto games in polynomial time and will discuss their applications in practice.
 

Examining Committee: 

 

                          Chair:               Dr. MohammadTaghi Hajiaghayi
                          Dean's rep:      Dr. Laurence M. Ausubel
                          Members:        Dr. John Dickerson
                                                    Dr. William Gasarch
                                                    Dr. Shang-Hua Teng                                                     
                                                    Dr. Christos Papadimitriou