In this thesis, we investigate resource allocation games, broadly defined as resource allocation problems involving interactions between competitive decision makers. We primarily focus on the Colonel Blotto game (CB game). In the CB game, two competitive players, each having a fixed budget, simultaneously distribute their resources toward n battlefields. Each player evaluates each battlefield with a certain value. In each battlefield, the player who has the higher allocation wins and gains the corresponding value. Each player's payoff is her aggregate gains from all the battlefields.
First, we model several variants of the CB game and their extensions as one-shot complete-information games and analyze players' strategic behaviors. Our first main contribution is a class of approximate equilibria in these games for which we prove that the approximation error can be well-controlled. Second, we model resource allocation games with combinatorial structures as online learning problems to study situations involving sequential plays and incomplete information. We make a connection between these games and online shortest path problems (OSP). Our second main contribution is a set of novel regret-minimization algorithms for OSP under several feedback settings that provide significant improvements in regret guarantees and running time in comparison with existing solutions.
