Synthesis for Games of Imperfect Information under Full-Information Protocols
Lundi 7 juillet 2025 à 14h00
ENS Paris-Saclay, Salle 1B36
Résumé : Différents modèles peuvent être utilisés pour représenter des programmes, pour vérifier s’ils sont corrects, ou mieux pour en synthétiser à partir d’une spécification. Nous modélisons ici un programme par un joueur affrontant un environnement. Construire un programme correct revient alors à synthétiser une stratégie gagnante dans ce jeu, c’est à dire un comportement qui assure de vérifier la condition de victoire quel que soit le comportement de l’environnement.
Nous introduisons un nouveau type de jeu dans lesquels le joueur obtient une information imparfaite en communiquant avec des observateurs passifs, via un full-information protocol. Contrairement au modèle classique on peut obtenir en un instant une quantité non bornée d'information.
Nous proposons une méthode pour synthétiser des stratégies pures et randomisées dans ces jeux, applicable dès qu'un morphisme information-commutant peut être construit.
The defense will be in English
Jury:
- Christel BAIER, Technische Universität Dresden, Rapportrice et examinatrice,
- Blaise GENEST, CNRS, National University of Singapore, Rapporteur et examinateur,
- Véronique BRUYÈRE, Université de Mons, Examinatrice,
- Jean GOUBAULT-LARRECQ, ENS Paris-Saclay Examinateur
- Nir PITERMAN, Chalmers University of Technology Gothenburg, Examinateur
- Laurent DOYEN, CNRS, Directeur
- Dietmar BERWANGER, CNRS, Co-encadrant.