• Home
  • Page : 'emploi' inconnue (menus.php)

 Thesis : Calculer le joueur parfait pour des jeux multijoueurs ou à connaissances incomplètes

PhD school thesis
Dans le contexte de la résolution des jeux, la plupart des jeux résolus sont des jeux à deux joueurs et à connaissances complètes (c’est-à-dire que chaque joueur dispose des mêmes informations, et de toutes les informations). Le but de la thèse est de relaxer ces deux hypothèses en préservant des propriétés de résolution forte:
1. En premier lieu, l’étude portera sur la résolution des jeux multijoueurs [14] (c’est à dire, à plus de deux joueurs). Un bon jeu candidat déjà étudié pour deux joueurs, mais dont la véritable version est prévue pour trois ou quatre joueurs est par exemple Blokus. Si la résolution exacte s’avère impossible, on s’intéressera à l’étude des coalitions possibles, c’est-à-dire la possibilité pour un sous-ensemble des joueurs de s’allier contre un autre (ou un groupe d’autres), et à l’inverse de la possibilité de sabotage, c’est-à-dire la possibilité pour un joueur de ne pas jouer de manière optimal pour privilégier systématiquement l’issue d’une partie. Il est probable que les raisonnements habituellement fait en algorithmique distribuée, et en particulier l’étude des problèmes impliquant des participants Byzantins (qui peuvent avoir un comportement arbitraire) seront utile au développement des solutions ou des résultats d’impossibilité [17,18].
2. En second lieu, la thèse se focalisera sur les jeux à connaissances incomplètes (c’est-à-dire que certaines informations peuvent être inconnues soit des deux joueurs, soit d’un sous-ensemble d’entre eux). Dans la plupart des cas, aucune stratégie déterministe ne peut ètre optimale, et il devient nécessaire pour les joueurs d’adopter des stratégies probabilistes afin de maximiser leurs chances de gagner. Si la notion d’équilibre de Nash n’est pas un concept récent (proposée dans les années 1950, elle a été largement étudiée en théorie des jeux et en économie). Pourtant, elle a rarement été appliquée en pratique (à l’exception notable de [12,13]) pour résoudre des jeux véritables. Sur la base de ces observations, la question scientifique clé que nous étudierons se résume à :
(a) Comment résoudre exactement des jeux avec des informations cachées ? et
(b) Comment mettre en œuvre efficacement l’algorithme correspondant?
3. Enfin, le but ultime serait de combiner les deux stratégies précédentes pour des jeux multijoueurs et à connaissances incomplètes. Il est probable qu’il faudra combiner une approche distribuée et des équilibres de Nash [15,16].

Ce projet de recherche doctoral fait l’objet d’une demande de financement auprès de « Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE) », le candidat retenu par son porteur devra donc participer au concours correspondant (prévoir un dossier et une audition) en vue d’obtenir le financement effectif.

More details here

Contact :Sébastien Tixeuil, François Bonnet