Algorithmes sains dans les jeux à information imparfaite

Résumé : La recherche a joué un rôle fondamental dans la recherche sur les jeux informatiques depuis le tout début. Et si la recherche en ligne a été couramment utilisée dans les jeux à information parfaite comme les échecs et le go, les méthodes de recherche en ligne pour les jeux à information imparfaite n'ont été introduites que relativement récemment. Cet article aborde la question de savoir quel est un bon algorithme en ligne dans un contexte d'information imparfaite pour les jeux à somme nulle à deux joueurs. Nous soutenons que les définitions de l'exploitabilité et des équilibres epsilon-Nash à stratégie fixe sont mal adaptées pour mesurer la performance d'un algorithme en ligne dans le pire des cas. Nous formalisons donc l'epsilon-soundness, un concept qui relie la performance la plus défavorable d'un algorithme en ligne à la performance d'un équilibre epsilon-Nash. Notre définition de la solidité et la hiérarchie de cohérence fournissent enfin des outils appropriés pour analyser les algorithmes en ligne dans les jeux d'information imparfaite répétés. Nous examinons ainsi certains des algorithmes en ligne précédents sous un jour nouveau, apportant de nouvelles perspectives sur leurs garanties de performance dans le pire des cas.