Prendre de bonnes décisions
dans des environnements multiagents est une tâche difficile dans la
mesure où la présence de plusieurs décideurs implique des conflits
d'intérêts, un manque de coordination, et une multiplicité de
décisions possibles. Si de plus, les décideurs interagissent
successivement à travers le temps, ils doivent non seulement décider
ce qu'il faut faire actuellement, mais aussi comment leurs décisions
actuelles peuvent affecter le comportement des autres dans le futur.
La théorie des jeux est un outil mathématique qui vise à modéliser
ce type d'interactions via des jeux stratégiques à plusieurs
joueurs. Des lors, les problèmes de décision multiagent sont souvent
étudiés en utilisant la théorie des jeux. Dans ce contexte, et si on
se restreint aux jeux dynamiques, les problèmes de décision
multiagent complexes peuvent être approchés de façon algorithmique.
La contribution de cette thèse est triple. Premièrement, elle
contribue à un cadre algorithmique pour la planification distribuée
dans les jeux dynamiques non-coopératifs. La multiplicité des plans
possibles est à l'origine de graves complications pour toute
approche de planification. Nous proposons une nouvelle approche
basée sur la notion d'apprentissage dans les jeux répétés. Une telle
approche permet de surmonter lesdites complications par le biais de
la communication entre les joueurs.
Nous proposons ensuite un algorithme d'apprentissage pour les jeux
répétés en ``self-play''. Notre algorithme permet aux joueurs de
converger, dans les jeux répétés initialement inconnus, vers un
comportement conjoint optimal dans un certain sens bien défini, et
ce, sans aucune communication entre les joueurs.
Finalement, nous proposons une famille d'algorithmes de résolution
approximative des jeux dynamiques et d'extraction des stratégies des
joueurs. Dans ce contexte, nous proposons tout d'abord une méthode
pour calculer un sous-ensemble non vide des équilibres approximatifs
parfaits en sous-jeu dans les jeux répétés. Nous montrons ensuite
comment nous pouvons étendre cette méthode pour approximer tous les
équilibres parfaits en sous-jeu dans les jeux répétés, et aussi
résoudre des jeux dynamiques plus complexes. / Making good decisions in
multiagent environments is a hard problem in the sense that the
presence of several decision makers implies conflicts of interests,
a lack of coordination, and a multiplicity of possible decisions.
If, then, the same decision makers interact continuously through
time, they have to decide not only what to do in the present, but
also how their present decisions may affect the behavior of the
others in the future.
Game theory is a mathematical tool that aims to model such
interactions as strategic games of multiple players. Therefore,
multiagent decision problems are often studied using game theory. In
this context, and being restricted to dynamic games, complex
multiagent decision problems can be algorithmically approached.
The contribution of this thesis is three-fold. First, this thesis
contributes an algorithmic framework for distributed planning in
non-cooperative dynamic games. The multiplicity of possible plans is
a matter of serious complications for any planning approach. We
propose a novel approach based on the concept of learning in
repeated games. Our approach permits overcoming the aforementioned
complications by means of communication between players.
We then propose a learning algorithm for repeated game self-play.
Our algorithm allows players to converge, in an initially unknown
repeated game, to a joint behavior optimal in a certain,
well-defined sense, without communication between players.
Finally, we propose a family of algorithms for approximately solving
dynamic games, and for extracting equilibrium strategy profiles. In
this context, we first propose a method to compute a nonempty subset
of approximate subgame-perfect equilibria in repeated games. We then
demonstrate how to extend this method for approximating all
subgame-perfect equilibria in repeated games, and also for solving
more complex dynamic games.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QQLA.2011/28028 |
| Date | 03 1900 |
| Creators | Burkov, Andriy |
| Contributors | Chaib-draa, Brahim, Marchand, Mario |
| Publisher | Université Laval |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Rights | © Andriy Burkov, 2011 |
Page generated in 0.0022 seconds