Fractional Combinatorial Games on Graphs

Description

De nombreux jeux impliquant deux joueurs dans un graphe ont été étudiés en théorie des graphes, par exemple: Gendarmes et voleur, Ange et Démon, Observeur et surfeur, Dominants universels, etc. Outre la capture d'un fugitif ou la lutte contre le feu, ces jeux ont aussi des applications dans les réseaux de télécommunications car, d'une part, ils permettent de mieux appréhender les structures des réseaux, et d'autre part, ils permettent de modéliser et d'étudier des problèmes de ces réseaux (e.g., problème de cache dans l'internet). Dans tous ces jeux, chaque joueur contrôle des jetons sur les sommets du graphe et selon les jeux, les joueurs peuvent: déplacer des jetons le long des arêtes du graphe, ajouter/supprimer des jetons, etc. Dans ce travail, nous proposons une approche générale en définissant un jeu qui constitue, entre autre, une relaxation fractionnaire de tous les jeux mentionnés ci-dessus. Pour ce jeu générique, nous montrons qu'il existe un algorithme en temps polynomial, en le nombre de sommets du graphe et le nombre de maximum de tours de jeu autorisés, pour décider si un des joueurs a une stratégie gagnante. Entre autre, cet algorithme permet d'avoir une stratégie gagnante, avec forte probabilité, pour le problème de cache.

Abstract

International audience

Additional details