Les jeux sur les graphes

Qu'est-ce que c'est?

Comme vous pouvez l'imaginer, ce sont des jeux au sens le plus classique: deux joueurs interagissent selon des règles bien définies, jusqu'à ce qu'un des deux joueurs soit déclaré vainqueur.

Le plateau de jeu, nommé arène, est de manière générale un graphe, moralement ''des points avec des flèches'', comme par exemple le dessin à droite. Dans ce dessin, il y a sept sommets (qui sont soit des cercles soit des carrés), et quelques arêtes, c'est-à-dire des flèches d'un sommet à un autre.
Les règles sont très simples : un jeton est initialement placé sur un sommet, puis est déplacé de sommets en sommets par les joueurs, le long des arêtes. Si le jeton se trouve dans un cercle, alors c'est à Eve de jouer : elle choisit une flèche et envoie le jeton vers le sommet qu'elle pointe, et symétriquement si le jeton est dans un carré, alors c'est à Adam de jouer.
Eve a un objectif, par exemple atteindre chaque sommet au moins une fois, et Adam doit l'empêcher d'atteindre cet objectif (remarquez que les objectifs sont antagonistes et différents pour les deux joueurs).

Pour résumer, un jeu est décrit par une arène, un sommet initial et une condition de gain, qu'Eve essaye d'atteindre tandis qu'Adam veut l'en empêcher. Les questions naturelles sont alors: qui gagne? Comment décrire simplement une stratégie gagnante?

Pourquoi ces jeux?

Il y a plusieurs motivations pour étudier ces jeux. En voici quelques unes :

- Synthèse de contrôleur : Pour faire court, les jeux sur les graphes sont un modèle naturel des systèmes ouverts que l'on rencontre en informatique.
Cela signifie que beaucoup de problèmes qui se posent autant en informatique théorique qu'en pratique peuvent être formulés avec des jeux.
Supposons que l'on veuille gérer un serveur web, c'est-à-dire un système capable d'interagir avec plusieurs utilisateurs. Un tel système doit pouvoir traiter des demandes (par exemple des utilisateurs qui recherchent des données) de manière intelligente; en d'autres termes, il doit utiliser une bonne stratégie pour conserver les requêtes et y répondre efficacement.
Le graphe permet de décrire toutes les interactions possibles entre les utilisateurs et le serveur. Eve représente le serveur web : elle doit le maintenir et assurer son bon fonctionnement. Son adversaire, Adam, représente tous les évènements imprévisibles qui peuvent arriver.
Dans ce contexte, la question de gérer un serveur web nécessite de bien comprendre les jeux obtenus : Eve peut-elle gagner ? De quelles ressources a t-elle besoin pour cela ?

- Jeux et automates : Les jeux sont un outil très puissant pour étudier les automates, et ont été très largement étudié dans ce cadre. Un exemple canonique est la complémentation des automates d'arbres : étant donné un automate d'arbre, construire un automate acceptant exactement les arbres qui ne sont pas acceptés. Etant donné un automate d'arbre et un arbre, on définit un jeu dans lequel Eve gagne si et seulement si l'arbre est accepté par l'automate. En étudiant ce jeu de près, on montrer que lorsqu'Adam gagne, il a une stratégie très simple. Il s'ensuit que pour reconnaître le complément du language, on construit un automate qui cherche une stratégie gagnante pour Adam dans ce jeu, ce qui montre que l'arbre n'est pas accepté.

- Jeux et logique : Les jeux sont (aussi) un outil très puissant pour étudier la logique. Des exemples très importants sont les jeux de satisfaisabilité : étant donné une formule logique, on définit un jeu où Eve gagne si et seulement si la formule est satisfaisable. Ici également, les stratégies gagnantes sont des objets naturels puisqu'ils décrivent ''comment'' la formule est satisfaite.

- Théorie des jeux : La théorie des jeux est développée depuis des décennies par les informaticiens, mathématiciens, biologistes, économistes...