UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Bandit models and Blotto games

Thomas, C.D.; (2011) Bandit models and Blotto games. Doctoral thesis, UCL (University College London). Green open access

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1041Kb

Abstract

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.

Type:Thesis (Doctoral)
Title:Bandit models and Blotto games
Open access status:An open access version is available from UCL Discovery
Language:English
UCL classification:UCL > School of Arts and Social Sciences > Faculty of Social and Historical Sciences > Economics

View download statistics for this item

Archive Staff Only: edit this record