Bandit models and Blotto games

In this thesis we present a new take on two classic problems of game theory: the "multiarmed bandit" problem of dynamic learning, and the "Colonel Blotto" game, a multidi- mensional contest. In Chapters 2-4 we treat the questions of experimentation with congestion: how do players search and learn about options when they are competing for access with other players? We consider a bandit model in which two players choose between learning about the quality of a risky option (modelled as a Poisson process with unknown arrival rate), and competing for the use of a single shared safe option that can only be used by one agent at the time. We present the equilibria of the game when switching to the safe option is irrevocable, and when it is not. We show that the equilibrium is always inefficient: it involves too little experimentation when compared to the planner solution. The striking equilibrium dynamics of the game with revocable exit are driven by a strategic option-value arising purely from competition between the players. This constitutes a new result in the bandit literature. Finally we present extensions to the model. In particular we assume that players do not observe the result of their opponent's experimentation. In Chapter 5 we turn to the n-dimensional Blotto game and allow battlefields to have different values. We describe a geometrical method for constructing equilibrium distribution in the Colonel Blotto game with asymmetric battlfield values. It generalises the 3-dimensional construction method first described by Gross and Wagner (1950). The proposed method does particularly well in instances of the Colonel Blotto game in which the battlefield weights satisfy some clearly defined regularity conditions. The chapter also explores the parallel between these conditions and the integer partitioning problem in combinatorial optimisation.