Models and Solutions of Strategic Resource Allocation Problems: Approximate Equilibrium and Online Learning in Blotto Games

Autor: Vu, Dong Quan
Přispěvatelé: Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Université Grenoble Alpes INP (Grenoble INP), Sorbonne Universites, UPMC University of Paris 6, Patrick Loiseau, Alonso Silva
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Computer Science and Game Theory [cs.GT]. Sorbonne Universites, UPMC University of Paris 6, 2020. English
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: