Title: Extended Formulations for the Colonel Blotto Game
| Speaker: | Ian DeHaan |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Suppose you want to replace Doug Ford as premier. To beat him, you need to win as many seats as possible. You have some finite amount of resources to allocate across all seats - if you spend more on a seat than Ford does, you will win that seat. How should you allocate your resources to maximize your expected number of seats? The Colonel Blotto game, introduced in 1921 by Borel, models situations like these.
This week we will look at the paper "Fast and Simple Solutions of Blotto Games" by Behnezhad et al. We will see a natural representation of the strategy space for the Colonel Blotto game as a polytope, and a way to transform it into a higher dimensional space with a polynomial number of facets. Finally, we will see that this representation is asymptotically optimal using the rectangle covering bound seen in previous talks.