Strategies in Sabotage Games: Temporal and Epistemic Perspectives

1. Problématique

Les jeux de sabotage modélisent des situations où un agent (le « coureur ») tente d'atteindre un état objectif dans un graphe dynamique, tandis qu'un adversaire (le « démon » ou « bloqueur ») tente de l'en empêcher en supprimant des arêtes du graphe à chaque tour.
Bien que ces jeux aient été traditionnellement analysés via la Logique Modale de Sabotage (SML), cette approche présente des limites :

• Elle ne capture pas naturellement les aspects temporels (évolution du jeu dans le temps).
• Elle ne gère pas bien les mouvements simultanés (jeux concurrents).
• Elle ne traite pas explicitement de l'incertitude épistémique (ce que les joueurs savent ou ne savent pas sur l'état du jeu).

L'objectif de l'article est de fournir un cadre logique unifié pour analyser ces jeux en intégrant la dimension temporelle et épistémique, en utilisant la Logique Temporelle Alternée (ATL et ATL)*.

2. Méthodologie

Les auteurs reconstruisent les jeux de sabotage dans le cadre de la logique ATL* (Alternating-time Temporal Logic star), qui permet de quantifier sur les stratégies des coalitions d'agents et d'exprimer des propriétés temporelles complexes.

A. Modélisation des Structures de Jeu
Les auteurs définissent trois types de structures de jeux de sabotage basées sur un graphe $G=(V, E)$ :

1. Tour par tour (Turn-based - tb) : Les joueurs agissent séquentiellement. Le démon supprime une arête, puis le coureur se déplace.
2. Concurrent (Concurrent - con) : Les joueurs choisissent leurs actions simultanément. Si le coureur choisit une arête que le démon choisit de supprimer, l'action est annulée (cancellation).
3. Général (General - gen) : Une structure flexible permettant des séquences de mouvements variées (tour par tour, simultané, ou inactivité), utilisant un symbole « skip » pour modéliser les tours où un joueur ne fait rien.

B. Définition des Jeux
Deux variantes de jeux sont étudiées :

• Jeux de Sabotage de Récupérabilité (RSG) : Le coureur gagne s'il atteint un sommet objectif $v_g$.
• Jeux de Sabotage de Vivacité (LSG) : Le coureur gagne s'il parvient à rester « en vie » (c'est-à-dire avoir une arête sortante disponible) pendant au moins $b$ tours, sans nécessairement atteindre un objectif spécifique.

C. Intégration Épistémique
Pour traiter l'incertitude, les auteurs étendent le modèle vers ATEL (Alternating-time Temporal Epistemic Logic). Ils introduisent des relations d'accessibilité ($\sim_i$) pour chaque agent, définissant les états du jeu qu'un agent ne peut pas distinguer les uns des autres (information imparfaite).

3. Contributions Clés

1. Cadre Logique Unifié (ATL) :*

   • Les auteurs montrent comment exprimer l'existence de stratégies gagnantes pour le coureur et le démon directement dans le langage ATL*.
   • Pour les RSG, la condition de victoire du coureur s'exprime par $\langle\langle \{r\} \rangle\rangle \mathbf{F}g$ (le coureur a une stratégie pour atteindre $g$ éventuellement).
   • Pour les LSG, ils introduisent un opérateur « until » paramétré ($\mathbf{U}_i$) pour exprimer la capacité du coureur à survivre pendant un nombre spécifique de tours : $\langle\langle \{r\} \rangle\rangle \top \mathbf{U}_{2b} (\mathbf{X}\top)$.

2. Analyse des Jeux Concurrents vs Tour par Tour :

   • L'article démontre que les jeux concurrents limitent davantage le pouvoir du coureur (une action peut être annulée par le démon).
   • Ils établissent que l'existence d'une stratégie gagnante conjointe (coalition coureur+démon) dans un jeu concurrent implique son existence dans un jeu tour par tour, mais l'inverse n'est pas vrai.

3. Lien avec la Théorie des Graphes (Coupe Minimale Dynamique) :

   • Une contribution majeure est la connexion entre les stratégies de sabotage et le problème de la coupe minimale $s-t$.
   • Les auteurs distinguent la coupe minimale statique (théorème de Menger) de la coupe minimale dynamique. Dans un jeu dynamique, le coureur peut « échapper » à une coupe statique en se déplaçant entre les tours du démon.
   • Ils définissent la coupe dynamique minimale comme le nombre minimal de tours nécessaires pour que le démon puisse garantir que le coureur ne puisse plus atteindre l'objectif, exprimé logiquement via ATL*.

4. Jeux de Sabotage Angéliques :

   • Extension du modèle pour inclure un troisième agent (un « constructeur » ou « ange ») capable d'ajouter des arêtes, permettant d'étudier des jeux infinis et des propriétés de récurrence (ex: atteindre l'objectif infiniment souvent).

5. Dimension Épistémique :

   • L'article illustre comment l'information imparfaite affecte les stratégies. Un agent peut posséder une stratégie gagnante (dans un sens objectif) mais ne pas le savoir, ou ne pas pouvoir l'exécuter car il ne peut pas distinguer l'état actuel du jeu.
   • Ils soulignent la nécessité d'ajuster la sémantique des stratégies pour tenir compte des « états de croyance » des agents (stratégies uniformes sur les états indiscernables).

4. Résultats Principaux

• Impossibilité de victoire dans les RSG tour par tour simples : Sauf si le coureur commence à la cible ou si la cible est à une seule étape, le démon a toujours une stratégie gagnante dans un graphe simple (non multi-graphe) en tour par tour. Le démon peut toujours supprimer l'arête menant à la cible juste avant que le coureur n'y arrive.
• Avantage du démon dans les jeux concurrents : Dans les jeux concurrents, le démon peut annuler le mouvement du coureur en choisissant la même arête, empêchant ainsi tout progrès vers l'objectif.
• Avantage du coureur dans les jeux de vivacité (LSG) : Paradoxalement, la capacité du démon à annuler les mouvements (en choisissant la même arête) devient un avantage pour le coureur dans les jeux de vivacité, car cela empêche le coureur d'être bloqué (il reste sur place avec des arêtes disponibles).
• Différence Coupe Statique vs Dynamique : L'exemple 3.20 montre qu'une coupe statique de taille 2 peut être insuffisante pour gagner un jeu dynamique si le coureur peut se déplacer vers un sous-graphe nécessitant une coupe de taille 3. La logique ATL* permet de capturer cette complexité temporelle.
• Limites de la connaissance : L'exemple 4.2 montre qu'avec une information imparfaite, un agent peut avoir une stratégie gagnante théorique mais ne pas pouvoir l'appliquer en pratique car il ne sait pas dans quel état du jeu il se trouve.

5. Signification et Perspectives

Signification :
Ce travail est significatif car il comble le fossé entre la logique modale de sabotage (SML) et la logique temporelle stratégique (ATL*). Il offre un langage formel puissant pour raisonner sur :

• La dynamique des graphes (changements structurels).
• Les propriétés temporelles complexes (vivacité, sécurité, récurrence).
• L'interaction entre la structure du graphe et les stratégies des agents.
• L'impact de l'information imparfaite sur la capacité stratégique.

Perspectives Futures :
Les auteurs suggèrent plusieurs axes de recherche futurs :

• Étendre les jeux à plusieurs coureurs et objectifs distribués.
• Approfondir le lien avec la théorie des graphes algorithmique, notamment les problèmes de flux maximum et de coupes minimales dynamiques.
• Développer davantage la dimension épistémique, notamment en comparant les stratégies basées sur la position (positional) et celles basées sur la mémoire (memory-based) dans des contextes d'information imparfaite.
• Explorer les jeux infinis et les jeux angéliques plus complexes.

En résumé, cet article propose une refonte fondamentale de l'analyse des jeux de sabotage, passant d'une logique statique à un cadre temporel et épistémique dynamique, permettant une modélisation plus fidèle des systèmes réels complexes où l'information et le temps jouent un rôle crucial.