Les jeux et les graphes

L'objectif de ce manuel collaboratif est de présenter l'état de l'art sur les jeux sur graphes, qui font partie d'un sujet de recherche plus large appelé théorie des jeux. Les jeux sur graphes sont le domaine des jeux dont les règles et l'évolution sont représentées par un graphe.

Nous nous concentrons principalement sur les jeux à durée infinie, mais leur étude est liée aux jeux à durée finie. Ils constituent un modèle de premier plan dans deux domaines connexes : d’une part la théorie des automates et la logique, et d’autre part la vérification et la synthèse de programmes. Certains de ces modèles ont été introduits et étudiés dans des communautés de recherche voisines, telles que l'optimisation et l'apprentissage par renforcement.
Ce livre ne prétend pas donner un exposé complet de tous les résultats ou modèles existants dans la littérature, ce qui est quasiment impossible pour deux raisons : la richesse des résultats existants et le flux constant de nouveaux résultats. L'objectif principal de ce livre est algorithmique : construire des algorithmes efficaces pour analyser différents types de jeux.

En savoir plus, ici.