14:00
15:00

Dans cette thèse, nous étudions la complexité du calcul des stratégies optimales dans les jeux à somme nulle à deux joueurs avec une information imparfaite. Dans les jeux à information imparfaite, les joueurs n'ont qu'une connaissance partielle de leur position dans le jeu. Cela rend la tâche de calcul des stratégies optimales difficile, en particulier lorsque les joueurs oublient les informations précédemment acquises. Pour mieux justifier cette difficulté, nous considérons des jeux à somme nulle à deux joueurs avec des informations imparfaites modélisées sous la forme extensive et nous présentons plusieurs nouveaux résultats de complexité sur le calcul de la valeur maxmin pour différentes classes d'informations imparfaites. Pour les bornes inférieures, nous considérons des problèmes tels que le problème de la somme de la racine carrée ainsi que des classes de complexité qui impliquent le calcul sur les réels, plus précisément la théorie existentielle des réels (ETR) et d'autres fragments de la théorie du premier ordre des réels (FOT(R)).
En revanche, nous identifions une nouvelle classe de jeux à mémoire imparfaite pour lesquels les stratégies optimales peuvent être calculées efficacement.
Dans le but d'étudier théoriquement les enchères au bridge, nous proposons également un nouveau modèle d'étude des enchères au bridge. Nous faisons quelques observations initiales pour la classe des jeux de bridge à 2 joueurs avec une seule couleur sur ce modèle et nous traçons la voie pour des recherches futures.

Amphi LaBRI