@InProceedings{BBDHx18,
  author = { Soheil Behnezhad and Avrim Blum and Mahsa Derakhshan and MohammadTaghi Hajiaghayi
             and Mohammad Mahdian and Christos H. Papadimitriou and Ronald L. Rivest and
             Saeed Seddighin and Philip B. Stark },
  title = { From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games },
  booktitle = { Proceedings SODA'18 },
  date = { 2018-01-07 },
  eventdate = { 2018-01-07/2018-01-10 },
  venue = { New Orleans, Louisiana },
  urla = { <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.148">conference</a> },                  
  abstract = { Mixed strategies are often evaluated based on the
                  expected payoff that they guarantee. This is not
                  always desirable. In this paper, we consider games
                  for which maximizing the expected payoff deviates
                  from the actual goal of the players. To address this
                  issue, we introduce the notion of a (u,p)-maxmin
                  strategy which ensures receiving a min- imum utility
                  of u with probability at least p. We then give
                  approximation algorithms for the problem of finding
                  a (u,p)-maxmin strategy for these games. We consider
                  the classic Colonel Blotto game. Two colonels divide
                  their troops among a set of battlefields. Each
                  battlefield is won by the colonel that puts more
                  troops in it. The payoff of each colonel is the
                  weighted number of battlefields that she wins. The
                  Colonel Blotto game has found applications in the
                  analysis of many different forms of competition:
                  from sports to advertisement, to politics. We show
                  that if we maximize the expected payoff of a player,
                  it does not nec- essarily maximize the winning
                  probability of that player for certain applications
                  of Colonel Blotto. We give an exact algorithm for a
                  natural variant of the continuous version of this
                  game. More generally, we provide constant and log-
                  arithmic approximation algorithms that approximate
                  the optimal strategies of the players in this game
                  when the goal of the players is to win a race rather
                  than maximizing the expected payoff.  
}
}