A simple and efficient algorithm to compute epsilon-equilibria of discrete Colonel Blotto games

The Colonel Blotto game is a famous game commonly used to model resource allocation problems in many domains ranging from security to advertising. Two players distribute a fixed budget of resources on multiple battlefields to maximize the aggregate value of battlefields they win, each battlefield being won by the player who allocates more resources to it. Since its introduction in 1921, the continuous version of the game---where players can choose any fractional allocation---has been extensively studied, albeit only with partial results to date. Only very recently, the discrete version---where allocations can only be integers---started to gain traction and algorithms were proposed to compute the equilibrium in polynomial time; but these remain computationally impractical for large (or even moderate) numbers of battlefields. In several important applications, meaningful models naturally have a large number of battlefields; the question of efficiently finding an equilibrium for such cases remains open. In this paper, we propose an algorithm to compute very efficiently an approximate equilibrium for the discrete Colonel Blotto game with many battlefields. Specifically, we propose a strategy (the discrete independently uniform strategy) and show that it is an epsilon-equilibrium. We provide a theoretical bound on the approximation error epsilon as a function of the number of battlefields and players budgets. We also propose an efficient dynamic programming algorithm to compute the best response of a player against an arbitrary set of marginals of the opponent. Using this algorithm, we can then compute for each game instance the actual value of epsilon. We perform numerical experiments that show that the proposed discrete independently uniform strategy provides a good approximation to the equilibrium even for a relatively moderate number of battlefields.