PhD Defense: Campaigning via LPS: Solving Blotto and Beyond

Saeed Seddighin
05.02.2019 11:00 to 13:00
IRB 5107

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