  The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied
game theory classic. Two colonels each have a pool of troops that they divide
simultaneously among a set of battlefields. The winner of each battlefield is
the colonel who puts more troops in it and the overall utility of each colonel
is the sum of weights of the battlefields that s/he wins. Over the past
century, the Colonel Blotto game has found applications in many different forms
of competition from advertisements to politics to sports.
  Two main objectives have been proposed for this game in the literature: (i)
maximizing the guaranteed expected payoff, and (ii) maximizing the probability
of obtaining a minimum payoff $u$. The former corresponds to the conventional
utility maximization and the latter concerns scenarios such as elections where
the candidates' goal is to maximize the probability of getting at least half of
the votes (rather than the expected number of votes). In this paper, we
consider both of these objectives and show how it is possible to obtain
(almost) optimal solutions that have few strategies in their support.
  One of the main technical challenges in obtaining bounded support strategies
for the Colonel Blotto game is that the solution space becomes non-convex. This
prevents us from using convex programming techniques in finding optimal
strategies which are essentially the main tools that are used in the
literature. However, we show through a set of structural results that the
solution space can, interestingly, be partitioned into polynomially many
disjoint convex polytopes that can be considered independently. Coupled with a
number of other combinatorial observations, this leads to polynomial time
approximation schemes for both of the aforementioned objectives.
