Models and Solutions of Strategic Resource Allocation Problems: Approximate Equilibrium and Online Learning in Blotto Games
Modèles et Solutions de Problèmes d'Allocation de Ressources Stratégiques : Équilibre Approximatif et Apprentissage en Ligne dans les Jeux de Blotto
Résumé
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. Our second main contribution is a set of novel regret-minimization algorithms for online shortest path problems under several feedback settings that provide significant improvements in regret guarantees and running time in comparison with existing solutions.
Dans cette thèse, nous étudions les jeux d'allocation de ressources généralement définis comme des problèmes d'allocation de ressources impliquant des interactions entre des décideurs compétitifs. Nous nous concentrons principalement sur le jeu Colonel Blotto (jeu CB). Dans ce jeu, deux joueurs compétitifs, chacun ayant un budget fixe, distribuent simultanément leurs ressources vers n champs de bataille. Chaque joueur évalue chaque champ de bataille avec une certaine valeur. Dans chaque champ de bataille, le joueur qui a l'allocation la plus élevée gagne la valeur correspondante. Le gain de chaque joueur est égal ses gains cumulés sur tous les champs de bataille.
Nous modélisons plusieurs variantes et extensions du jeu CB comme jeux d'informations complètes à un coup. Notre première contribution est une classe d'équilibres approximatifs dans ces jeux tel que l'erreur d'approximation est bien contrôlée. Deuxièmement, nous modélisons les jeux d'allocation de ressources avec des structures combinatoires comme des problèmes d'apprentissage en ligne pour étudier des situations impliquant des jeux séquentiels et des informations incomplètes. Nous établissons une connexion entre ces jeux et les problèmes de chemin le plus court en ligne (OSP). Nous proposons nouveaux algorithmes d’OSP sous plusieurs paramètres de feedback qui améliorent des garanties de regret et du temps d'exécution.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...