<figure><img src="image_1.png" /></figure>

HAL
open science

# Modélisation logique de l'intentionnalité dans les jeux épistémiques

Alix Goudyme

► To cite this version:

Alix Goudyme. Modélisation logique de l'intentionnalité dans les jeux épistémiques. Informatique [cs]. Université d'Artois, 2022. Français. NNT: tel-04296665

HAL Id: tel-04296665

https://theses.hal.science/tel-04296665

Submitted on 20 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Modélisation logique de l'intentionnalité dans les jeux épistémiques

## THÈSE

présentée et soutenue publiquement le 16 juin 2022
en vue de l'obtention du

Doctorat de l'Université d'Artois
(Specialité Informatique)

par

Alix Goudyme

## Composition du jury

<table><tr><td>Président :</td><td>Gilles Audemard</td><td>Professeur des universités, Université d'Artois</td></tr><tr><td rowspan="4">Encadrants :</td><td>Salem Benferhat</td><td>Professeur des universités, Université d'Artois</td></tr><tr><td>Nathalie Chetcuti-Sperandio</td><td>Maître de conférences, Université d'Artois</td></tr><tr><td>Sylvain Lagrue</td><td>Professeur des universités, Université de Technologie de Compiègne</td></tr><tr><td>Tiago de Lima</td><td>Maître de conférences, Université d'Artois</td></tr><tr><td rowspan="2">Rapporteurs :</td><td>Frédéric Maris</td><td>Maître de conférences, Université de Toulouse III Paul Sabatier</td></tr><tr><td>Odile Papini</td><td>Professeur des universités, Université d'Aix-Marseille</td></tr><tr><td>Examinateur :</td><td>Thomas Polacsek</td><td>Ingénieur de recherche, ONERA</td></tr></table>
Mise en page avec memcril (B. Mazure, CRIL) et thloria (D. Roegel, LORIA).
Remerciements

Je tiens à remercier mes encadrants Nathalie Chetcuti-Sperandio, Tiago de Lima et Sylvain Lagrue, je n'aurais pas pu avoir de meilleurs encadrants.

Je remercie également Frédéric Maris et Odile Papini pour les commentaires et les améliorations proposées.

J'aimerais aussi remercier le laboratoire du CRIL, les collègues et notamment mes camarades Anasse et Hugues sans qui tout aurait été différent.

Et enfin, évidemment, je remercie aussi ma famille, ma mère, mon père, qui m'ont soutenu et permis d'arriver jusque là.
# Table des matières

Table des figures viii

Introduction générale 1

## Partie I État de l'art

Chapitre 1 Logique épistémique 4

1.1 Logique modale 4

1.1.1 Syntaxe 4

1.1.2 Interprétation 5

1.1.3 Modèle de Kripke 6

1.2 Logique épistémique 7

1.2.1 Présentation 7

1.2.2 Système KD45 8

1.2.3 Système S5 9

1.2.4 Connaissance commune 11

1.3 Logique épistémique dynamique 12

1.3.1 Présentation 12

1.3.2 Annonce publique 13

1.3.3 Action Publique 15

1.3.4 Action semi-privée ou indiscernable 16

1.3.5 Réalité 21

1.4 ESTS - Epistemic State Transition System 21
<table><tr><td>1.4.1 Présentation</td><td>21</td></tr><tr><td>1.4.2 Exemple</td><td>22</td></tr><tr><td>1.4.3 Différences entre modèle DEL et modèle ESTS</td><td>23</td></tr><tr><td><strong>Chapitre 2 Intention</strong></td><td><strong>24</strong></td></tr><tr><td>2.1 Thèse d'asymétrie de Bratman</td><td>24</td></tr><tr><td>2.1.1 Théorie désir-croyance</td><td>24</td></tr><tr><td>2.1.2 Thèse d'asymétrie</td><td>25</td></tr><tr><td>2.1.3 Effet secondaire</td><td>25</td></tr><tr><td>2.1.4 Remarques</td><td>25</td></tr><tr><td>2.2 Cohen et Levesque</td><td>26</td></tr><tr><td>2.2.1 Présentation</td><td>26</td></tr><tr><td>2.2.2 Propriétés</td><td>28</td></tr><tr><td>2.3 Rao et Georgeff et la logique BDI</td><td>28</td></tr><tr><td>2.3.1 Présentation</td><td>28</td></tr><tr><td>2.3.2 Axiomes</td><td>30</td></tr><tr><td>2.3.3 Thèse d'asymétrie</td><td>30</td></tr><tr><td>2.3.4 Effet secondaire</td><td>31</td></tr><tr><td>2.4 Idée de Shoham</td><td>32</td></tr><tr><td>2.4.1 Présentation</td><td>32</td></tr><tr><td>2.4.2 Logique</td><td>33</td></tr><tr><td>2.5 Idée de Roy</td><td>34</td></tr><tr><td>2.6 Conclusion</td><td>34</td></tr></table>

## Partie II Modélisation de l'intention

<table><tr><td><strong>Chapitre 3 Première modélisation</strong></td><td><strong>36</strong></td></tr><tr><td>3.1 Présentation</td><td>36</td></tr><tr><td>3.1.1 Premier principe</td><td>36</td></tr><tr><td>3.1.2 Deuxième principe</td><td>36</td></tr><tr><td>3.1.3 Troisième principe</td><td>37</td></tr><tr><td>3.2 Définitions</td><td>37</td></tr></table>
<table><tr><td>3.3</td><td>Calcul de l'intention</td><td>39</td></tr><tr><td>3.3.1</td><td>Exemple</td><td>39</td></tr><tr><td>3.3.2</td><td>Définitions</td><td>46</td></tr><tr><td>3.4</td><td>Propriétés</td><td>47</td></tr><tr><td>3.4.1</td><td>Opérateur</td><td>47</td></tr><tr><td>3.4.2</td><td>Extension de DEL</td><td>48</td></tr><tr><td>3.4.3</td><td>Principes</td><td>48</td></tr><tr><td>3.4.4</td><td>Propositions</td><td>49</td></tr><tr><td>3.5</td><td>Limitations</td><td>55</td></tr></table>

## Chapitre 4 Deuxième modélisation 56

<table><tr><td>4.1</td><td>Hanabi</td><td>56</td></tr><tr><td>4.1.1</td><td>Présentation</td><td>56</td></tr><tr><td>4.1.2</td><td>Règles du jeu</td><td>57</td></tr><tr><td>4.1.3</td><td>Simplification et logique épistémique</td><td>57</td></tr><tr><td>4.2</td><td>Action indéterminée</td><td>58</td></tr><tr><td>4.3</td><td>Utilité</td><td>61</td></tr><tr><td>4.3.1</td><td>Présentation</td><td>62</td></tr><tr><td>4.3.2</td><td>Définitions</td><td>64</td></tr><tr><td>4.3.3</td><td>Remarques</td><td>65</td></tr><tr><td>4.4</td><td>Intention</td><td>65</td></tr><tr><td>4.4.1</td><td>Meilleures actions</td><td>65</td></tr><tr><td>4.4.2</td><td>Premier exemple</td><td>67</td></tr><tr><td>4.4.3</td><td>Deuxième exemple</td><td>72</td></tr><tr><td>4.4.4</td><td>Définition</td><td>72</td></tr><tr><td>4.5</td><td>Propriétés</td><td>73</td></tr><tr><td>4.5.1</td><td>Opérateur</td><td>73</td></tr><tr><td>4.5.2</td><td>Extension de DEL</td><td>73</td></tr><tr><td>4.5.3</td><td>Propositions</td><td>73</td></tr><tr><td>4.6</td><td>Limitations</td><td>74</td></tr></table>

## Chapitre 5 ESTS et intention 75

<table><tr><td>5.1</td><td>Définitions</td><td>75</td></tr><tr><td>5.2</td><td>Contraintes</td><td>77</td></tr><tr><td>5.3</td><td>Utilité</td><td>78</td></tr><tr><td>5.3.1</td><td>Présentation</td><td>78</td></tr><tr><td>5.3.2</td><td>Exemple d'utilité</td><td>79</td></tr></table>
<table><tbody><tr><td>5.4</td><td>Intention</td><td>80</td></tr><tr><td>5.4.1</td><td>Rappel</td><td>80</td></tr><tr><td>5.4.2</td><td>Définitions</td><td>80</td></tr><tr><td>5.4.3</td><td>Exemple</td><td>82</td></tr><tr><td>5.5</td><td>Définition d'un premier opérateur d'intention</td><td>86</td></tr><tr><td>5.5.1</td><td>Définition</td><td>86</td></tr><tr><td>5.5.2</td><td>Propositions</td><td>86</td></tr><tr><td>5.6</td><td>Définition d'un deuxième opérateur d'intention</td><td>87</td></tr><tr><td>5.6.1</td><td>Définition</td><td>87</td></tr><tr><td>5.6.2</td><td>Propositions</td><td>88</td></tr><tr><td>5.7</td><td>Limitation</td><td>89</td></tr><tr><td colspan="2"><strong>Chapitre 6 Conclusion et Perspectives</strong></td><td><strong>90</strong></td></tr><tr><td>6.1</td><td>Conclusion</td><td>90</td></tr><tr><td>6.2</td><td>Perspectives</td><td>91</td></tr><tr><td>6.2.1</td><td>Calcul de l'intention</td><td>91</td></tr><tr><td>6.2.2</td><td>Formalisme</td><td>93</td></tr><tr><td>6.2.3</td><td>Validation et utilisation</td><td>94</td></tr></tbody></table>

Annexes

Annexe A

Démonstrations de la partie 1

<table><tbody><tr><td>A.1</td><td>Démonstration des axiomes D et 4</td><td>97</td></tr></tbody></table>

Annexe B

Démonstrations et exemples de la partie 2

<table><tbody><tr><td>B.1</td><td>Utilité du joueur 2 dans l'exemple simplifié de hanabi</td><td>99</td></tr><tr><td>B.2</td><td>Exemple théorique de la section 4.4.3</td><td>100</td></tr><tr><td>B.3</td><td>Démonstrations des propositions de la deuxième modélisation</td><td>103</td></tr><tr><td>B.3.1</td><td>Lemmes</td><td>103</td></tr><tr><td>B.3.2</td><td>Démonstrations</td><td>105</td></tr></tbody></table>
<table><tr><td>B.4</td><td>Démonstrations des propositions de la première définition de la modélisation ESTS</td><td>108</td></tr><tr><td>B.4.1</td><td>Lemmes</td><td>108</td></tr><tr><td>B.4.2</td><td>Démonstrations</td><td>109</td></tr><tr><td>B.5</td><td>Démonstrations des propositions de la deuxième définition de la modélisation ESTS</td><td>112</td></tr><tr><td>B.5.1</td><td>Lemmes</td><td>112</td></tr><tr><td>B.5.2</td><td>Démonstrations</td><td>113</td></tr><tr><td>B.5.3</td><td>Propositions 5</td><td>116</td></tr><tr><td>B.6</td><td>Exemple limitation des modèles d'évènements les plus utiles</td><td>118</td></tr></table>

**Bibliographie**

121
Table des figures

<table><tr><td>1.1</td><td>Modèle de Kripke</td><td>6</td></tr><tr><td>1.2</td><td>Exemple de modèle dans le système KD45</td><td>8</td></tr><tr><td>1.3</td><td>Exemple de modèle dans le système S5</td><td>10</td></tr><tr><td>1.4</td><td>État épistémique initial du Muddy children puzzle</td><td>12</td></tr><tr><td>1.5</td><td>Modèle épistémique après l'annonce de la personne extérieure</td><td>14</td></tr><tr><td>1.6</td><td>Modèle épistémique après les deux annonces publiques</td><td>15</td></tr><tr><td>1.7</td><td>Effet d'une action</td><td>16</td></tr><tr><td>1.8</td><td>Modèle épistémique de l'état initial du cluedo</td><td>17</td></tr><tr><td>1.9</td><td>Modèle d'évènement de l'action « regarder la troisième carte »</td><td>19</td></tr><tr><td>1.10</td><td>Le modèle épistémique et le modèle d'évènement à croiser</td><td>20</td></tr><tr><td>1.11</td><td>Le modèle épistémique produit et le modèle épistémique résultant</td><td>20</td></tr><tr><td>1.12</td><td>ESTS du cluedo simplifié</td><td>23</td></tr><tr><td>3.1</td><td>Représentation DEL du premier exemple</td><td>40</td></tr><tr><td>3.2</td><td>Représentation DEL du deuxième exemple</td><td>41</td></tr><tr><td>3.3</td><td>Représentation DEL du troisième exemple</td><td>42</td></tr><tr><td>3.4</td><td>Représentation DEL du quatrième exemple</td><td>44</td></tr><tr><td>3.5</td><td>Exemple pour la proposition 1.5</td><td>53</td></tr><tr><td>3.6</td><td>Exemple pour la proposition 1.7</td><td>53</td></tr><tr><td>4.1</td><td>Modèle épistémique du jeu simplifié Hanabi</td><td>58</td></tr><tr><td>4.2</td><td>Effet de l'action c<sup>i</sup><sub>13</sub></td><td>59</td></tr><tr><td>4.3</td><td>Effets des actions du joueur 2 dans le cas où le joueur 1 pense que w<sub>1</sub> est le monde réel.</td><td>63</td></tr><tr><td>4.4</td><td>États possibles du jeu Hanabi pour les trois premiers tours lorsque le joueur 1 commence par défausser</td><td>68</td></tr><tr><td>4.5</td><td>États possibles du jeu Hanabi pour les trois premiers tours lorsque le joueur 1 commence par poser</td><td>70</td></tr><tr><td>4.6</td><td>États possibles du jeu Hanabi pour les trois premiers tours lorsque le joueur 1 commence par donner un indice</td><td>71</td></tr><tr><td>5.1</td><td>Exemple de deux modèles ESTS pointés, celui de gauche ne vérifie pas la contrainte d'exécutabilité, celui de droite si</td><td>77</td></tr><tr><td>5.2</td><td>Exemple de deux modèles ESTS pointés, celui de gauche ne vérifie pas la contrainte de pouvoir-jouer, celui de droite si</td><td>78</td></tr><tr><td>5.3</td><td>États possibles du jeu Hanabi pour les trois premiers tours.</td><td>84</td></tr><tr><td>5.4</td><td>Valeurs et scores maximaux accessibles des états possibles du jeu Hanabi pour les trois premiers tours.</td><td>85</td></tr></table>
<table><tr><td>5.5</td><td>Exemple de deux modèles ESTS différents mais présentant les mêmes caractéristiques épistémiques</td><td>89</td></tr><tr><td>B.1</td><td>Modèle épistémique du jeu simplifié hanabi</td><td>99</td></tr><tr><td>B.2</td><td>L'ensemble des modèles possibles pour le joueur 1 des deux premiers tours du deuxième exemple</td><td>101</td></tr><tr><td>B.3</td><td>Contre exemple pour l'effet secondaire</td><td>106</td></tr><tr><td>B.4</td><td>Contre exemple pour l'effet secondaire</td><td>110</td></tr><tr><td>B.5</td><td>Contre exemple pour l'axiome K</td><td>116</td></tr><tr><td>B.6</td><td>Contre-exemple pour l'axiome C</td><td>118</td></tr><tr><td>B.7</td><td>L'ensemble des modèles possibles du jeu</td><td>119</td></tr><tr><td>B.8</td><td>L'ensemble des modèles possibles les plus utiles du jeu</td><td>120</td></tr></table>
# Introduction générale

## Présentation du sujet

Le concept de l'intention et son lien avec ce qu'un agent sait ou connaît est un concept important en Philosophie, en Logique et en Intelligence Artificielle [Bra87, RG98] et peut être trouvé dans de nombreuses applications tels la négociation, le droit ou encore l'argumentation. Nous nous intéressons dans ce sujet plus particulièrement au concept d'intention dans le cadre des jeux. L'univers du jeu fournit un environnement maîtrisé mais néanmoins suffisamment riche pour tester les différentes méthodes qui pourront être développées. Nous restreignons l'objet d'étude aux jeux à information incomplète et potentiellement asymétrique (jeu où les joueurs n'ont pas les mêmes buts ou les mêmes règles). Dans ces jeux, la prise en compte des croyances des joueurs est cruciale pour être capable de bien jouer.

Un jeu dans lequel les joueurs doivent prendre en compte les croyances des autres joueurs est appelé jeu épistémique. Des exemples connus de ce type de jeu sont Cluedo<fnref n="1" />, les 7 Familles<fnref n="2" />, M. Jack<fnref n="3" /> (asymétrique), ainsi que le jeu coopératif Hanabi<fnref n="4" />. La représentation de tels jeux peut être faite au moyen de langages génériques tels que GDL-III [Thi17] et Epistemic-GDL [JZPZ16, JZPZ21]. Les coups choisis par certains joueurs peuvent dévoiler certaines intentions. Par exemple, dans le jeu Hanabi, lorsqu'un joueur donne l'indice « tu as la carte 3 » à un autre joueur, cela peut indiquer qu'il cherche à ce que cette carte soit jouée [EMAC17]. Ou bien dans un jeu tel que la dame de pique, lorsqu'un joueur joue consécutivement des cartes piques, il cherche sans doute à « faire tomber » la dame de pique.

## Objectifs

Il est potentiellement très coûteux de détecter l'intention des autres joueurs. Lors d'une partie en direct, le temps imparti à chaque joueur pour prendre une décision est souvent très court et il peut être délicat de prendre en compte à la fois les croyances et les intentions des autres joueurs. En revanche, il est beaucoup plus envisageable d'étudier le jeu des différents joueurs hors-ligne et de disséquer quelles étaient les intentions d'un joueur à un moment donné de la partie. Cela peut permettre par exemple de remettre en cause certains mauvais coups ou encore d'expliquer les meilleurs. L'aspect logique permet une meilleure explicabilité des coups des différents joueurs.

L'objectif de ce travail est de déterminer l'intention d'un joueur à un moment donné d'une partie, à partir des connaissances qu'il possède sur l'état du monde, des actions à sa disposition et des actions qu'il a finalement exécutées.

<footnote n="1">1. https://fr.wikipedia.org/wiki/Cluedo</footnote>

<footnote n="2">2. https://fr.wikipedia.org/wiki/7_familles</footnote>

<footnote n="3">3. https://fr.wikipedia.org/wiki/Mr._Jack_(jeu_de_société)</footnote>

<footnote n="4">4. https://fr.wikipedia.org/wiki/Hanabi_(jeu)</footnote>
## Positionnement

Afin de représenter les connaissances d'un joueur sur l'état du monde nous avons choisi la logique épistémique. Celle-ci a pour but de représenter les connaissances d'un ensemble d'agents et non seulement les connaissances sur le monde tel qu'il est mais aussi les connaissances sur les connaissances des autres agents. Par ailleurs il existe une version dynamique de la logique épistémique. Celle-ci propose une gestion des évènements du monde qui le changent et qui changent également les connaissances qu'ont les agents sur le monde. Elle semble donc parfaitement adaptée pour ce travail puisque dans un jeu, un joueur choisit ses actions non seulement d'après ce qu'il connaît du jeu mais aussi en prenant en compte ce que les autres joueurs pourraient faire.

## Travail produit

Nous avons pu définir différents opérateurs d'intentions permettant de vérifier si l'agent avait bien l'intention d'obtenir une propriété considérée. Ces opérateurs ont pour caractéristique de ne pas être donnés mais d'être obtenus après l'analyse des états épistémiques des jeux. Ces opérateurs vérifient plusieurs propriétés communes à différentes théories de l'intention dont celle de la thèse d'asymétrie de Bratman [Bra87].

## Plan de thèse

Ce document commencera par une présentation de la logique épistémique dynamique ainsi que d'autres formalismes sur lesquels nous nous appuierons pour développer notre travail. Il se poursuivra par une présentation de différentes théories déjà existante modélisant l'intention.

Dans la deuxième partie, nous proposerons tout d'abord une modélisation de l'intention formée à partir de la logique épistémique dynamique. Cette modélisation posera les bases de la définition d'une intention mais aura comme défaut de représenter les autres joueurs comme des joueurs aléatoires et de ne gérer qu'une petite partie des actions possibles dans un jeu.

Nous présenterons ensuite une amélioration de cette modélisation afin de gérer un plus grand nombre d'actions. Mais surtout, cette deuxième modélisation apportera une évolution de l'étude de l'intention des agents : les actions des autres joueurs ne seront plus considérées comme aléatoires. Pour cela, nous introduirons une valeur appelée *utilité* représentant la préférence des joueurs concernant leurs actions.

Enfin une troisième modélisation utilisant les Epistemic State Transition Systems permettra un formalisme plus simple, et surtout la définition d'un opérateur d'intention. Cet opérateur d'intention nous permettra de comparer certains de nos résultats avec des propriétés de précédentes modélisations de l'intention.
Première partie

État de l'art
# 1

# Logique épistémique

## 1.1 Logique modale

### 1.1.1 Syntaxe

La logique modale est une extension de la logique propositionnelle avec des connecteurs pour exprimer la possibilité et la nécessité [FC12, BDRV01, BVBW06, CH96]. Une proposition peut être simplement possible ou alors tout à fait nécessaire. Les connecteurs sont résumés dans le tableau suivant :

<table><thead><tr><th>nom</th><th>arité</th><th>symbole</th></tr></thead><tbody><tr><td>vrai</td><td>0</td><td>⊤</td></tr><tr><td>faux</td><td>0</td><td>⊥</td></tr><tr><td>négation</td><td>1</td><td>¬</td></tr><tr><td>conjonction</td><td>2</td><td>∧</td></tr><tr><td>disjonction</td><td>2</td><td>∨</td></tr><tr><td>implication</td><td>2</td><td>→</td></tr><tr><td>équivalence</td><td>2</td><td>↔</td></tr><tr><td>possibilité</td><td>1</td><td>◇</td></tr><tr><td>nécessité</td><td>1</td><td>□</td></tr></tbody></table>

Les raisonnements de la logique modale s'effectuent sur des formules. Celles-ci se construisent de la façon suivante :

1. Si $p$ est une variable propositionnelle alors $p$ est une formule.

2. Si $\phi$ et $\psi$ sont des formules alors $⊤, \bot, \neg\phi, \phi \wedge \psi, \phi \vee \psi, \phi \rightarrow \psi, \phi \leftrightarrow \psi, \Box\phi, \Diamond\phi$ sont des formules.

3. Les formules ne peuvent être créées par ces deux façons.

4. Des parenthèses peuvent être utilisées pour fixer la portée d'un connecteur ou simplement pour plus de compréhension.

**Définition 1 (Formule du langage)** Soit $\mathbb{P}$ l'ensemble des variables propositionnelles et $p \in \mathbb{P}$, on ap-
pelle $\mathbb{L}(\mathbb{P})$ ensemble des formules du langage (ou simplement langage) toute formule se construisant à
l'aide de la grammaire suivante :

$$ \phi ::= \top | \bot | p | \neg\phi | \phi \wedge \phi | \phi \vee \phi | \phi \rightarrow \phi | \phi \leftrightarrow \phi | \Diamond\phi | \Box\phi $$
On aimerait attacher à chaque connecteur une signification afin de pouvoir donner un sens à chaque
formule. Voici un exemple de ce qu'on aimerait obtenir :

— $\neg\phi$ signifie "non-$\phi$"

— $\phi \wedge \psi$ signifie $\phi$ et $\psi$.

— $(\phi \wedge \psi) \rightarrow \omega$ signifie "si $\phi$ et $\psi$ alors $\omega$"

— $\diamond\neg(\phi \leftrightarrow \psi)$ signifie "il est possible que $\phi$ et $\psi$ ne soient pas équivalents"

— $\neg\Box(\phi \leftrightarrow \psi)$ signifie "il n'est pas nécessaire que $\phi$ et $\psi$ soient équivalents"

1.1.2 Interprétation

Dans le cadre de la logique propositionnelle, une interprétation associe à chaque formule une valeur
de vérité : vrai ou faux.

**Définition 2 (Interprétation)** Soit $\mathbb{P}$ l'ensemble des variables propositionnelles, on appelle interprétation une fonction de $\mathbb{P}$ vers $\{\text{vrai,faux}\}$. Par continuité, on appelle également interprétation la fonction de $\mathbb{L}(\mathbb{P})$ vers $\{\text{vrai,faux}\}$.

En logique propositionnelle on utilise l'interprétation vérifiant les règles suivantes :

— $\top$ est vrai.

— $\bot$ est faux.

— si $p$ est une variable propositionnelle alors $p$ est vrai si et seulement si l'interprétation de $p$ est
vraie.

— si $\phi$ est une formule alors $\neg\phi$ est vrai si et seulement si $\phi$ est faux.

— si $\phi$ et $\psi$ sont des formules alors $\phi \wedge \psi$ est vrai si et seulement si $\phi$ et $\psi$ sont vrais.

— si $\phi$ et $\psi$ sont des formules alors $\phi \vee \psi$ est vrai si et seulement si $\phi$ est vrai ou $\psi$ est vrai.

— si $\phi$ et $\psi$ sont des formules alors $\phi \rightarrow \psi$ est vrai si et seulement si lorsque $\phi$ est vrai alors $\psi$ est vrai.

— si $\phi$ et $\psi$ sont des formules alors $\phi \leftrightarrow \psi$ est vrai si et seulement si $\phi$ et $\psi$ sont tous les deux vrais ou tous les deux faux.

On appelle alors *modèle* de $\phi$ une interprétation qui rend la formule $\phi$ vraie et on dit que l'interprétation falsifie la formule si elle la rend fausse. Par exemple la formule $p$ ou $q$ a pour modèle l'interprétation où ($p = \text{vrai}, q = \text{faux}$). Deux autres modèles possibles sont les interprétations où ($p = \text{vrai}, q = \text{vrai}$) et ($p = \text{faux}, q = \text{vrai}$). À l'inverse l'interprétation où ($p = \text{faux}, q = \text{faux}$) falsifie la formule.

Du point de vue des formules, une formule est dite *satisfiable* s'il existe au moins une interprétation
qui la rend vraie. Dans le cas contraire, elle est dite *insatisfiable*. Si toutes les interprétations rendent la
formule vraie, on dit alors que la formule est *valide* ou également que c'est une *tautologie* notée $\models \phi$
(par exemple, « $p \vee \neg p$ » est une tautologie).

Si $\phi$ et $\psi$ sont des formules et si tous les modèles de $\phi$ sont aussi modèles de $\psi$ alors on dit que $\psi$ est une conséquence logique de $\phi$ noté $\phi \models \psi$. Si de plus $\psi \models \phi$, alors on dit que $\phi$ et $\psi$ sont logiquement équivalents, noté $\phi \equiv \psi$.

La logique modale et la logique propositionnelle partagent les mêmes règles pour ce qu'elles ont en
commun. Mais pour les connecteurs $\Box$ et $\Diamond$, que veut dire "il est possible que $\phi$ soit vrai" ?
## 1.1.3 Modèle de Kripke

Une des sémantiques les plus utilisées pour la logique modale est celle proposée par Saul Kripke [Kri59]. Un modèle de Kripke se base sur la notion de mondes possibles. On va noter chaque monde par $w_n$ (où $n$ est un entier naturel), on note $W$ l'ensemble des mondes et enfin on rappelle que $\mathbb{P}$ est l'ensemble des propositions.

Un cadre de Kripke est défini comme l'ensemble formé de $W$ et de $R$, où $R$ est une relation binaire sur $W$. Cette relation est appelée relation d'accessibilité et définit les mondes accessibles depuis chacun des mondes. Un cadre de Kripke est souvent représenté sous forme de graphe orienté où les sommets sont les mondes et les arêtes relient les mondes accessibles.

**Définition 3 (modèle de Kripke)** Soit $W$ un ensemble de mondes, soit $R$ une relation binaire sur $W$ appelée relation d'accessibilité, soit $\pi$ une fonction de $\mathbb{P}$ vers $2^W$ appelée fonction de valuation, on appelle modèle de Kripke le triplet $M = (W, R, \pi)$.

<figure><img src="image_3.png" /><figcaption>FIGURE 1.1 – Modèle de Kripke</figcaption></figure>

Nous pouvons voir un exemple de modèle de Kripke sur la figure 1.1. Il y a 4 mondes dans ce modèle de Kripke, on peut voir que $w_1$ contient $p$, cela signifie que $w_1 \in \pi(p)$. Concernant les autres mondes : $w_2$ contient $q$, $w_3$ contient $p$ et $q$ et $w_4$ ne contient ni $p$ ni $q$. Le monde $w_1$ est relié au monde $w_2$, le monde $w_2$ est relié aux mondes $w_3$ et $w_4$, le monde $w_3$ est relié aux mondes $w_1$ et $w_2$ et le monde $w_4$ n'est relié a aucun monde. Ce modèle de Kripke est représenté par le triplet $(W, R, \pi)$ où $W = \{w_1, w_2, w_3, w_4\}, R = \{(w_1, w_2), (w_2, w_3), (w_2, w_4), (w_3, w_1), (w_3, w_2)\}$ et $\pi = \{p \to \{w_1, w_3\}, q \to \{w_2, w_3\}\}$. On peut noter la relation $(w_1, w_2) \in R$ comme $w_1 Rw_2$.

La sémantique de la logique modale au sein d'un modèle de Kripke $M = (W, R, \pi)$ est régie par ces 10 règles :

1. $\models_{w_j} M \top$

2. $\not\models_{w_j} M \bot$

3. $\models_{w_j} p$ si et seulement si $w_j \in \pi(p)$

4. $\models_{w_j} \neg \psi$ si et seulement si $\not\models_{w_j} M \psi$

5. $\models_{w_j} \phi \wedge \psi$ si et seulement si $\models_{w_j} M \phi$ et $\models_{w_j} M \psi$

6. $\models_{w_j} \psi \vee \phi$ si et seulement si $\models_{w_j} M \psi$ ou $\models_{w_j} M \phi$ ou les deux

7. $\models_{w_j} \psi \rightarrow \phi$ si et seulement si $\models_{w_j} M \psi$ implique $\models_{w_j} M \phi$

8. $\models_{w_j} \psi \leftrightarrow \phi$ si et seulement si $\models_{w_j} M \phi$ et $\models_{w_j} M \psi$ ou bien $\not\models_{w_j} M \phi$ et $\not\models_{w_j} M \psi$
9. $\models_{w_j}^M \Box \psi$ si pour tous les mondes $w_i$ de $M$ si nous avons $w_j R w_i$ alors nous avons $\models_{w_i}^M \psi$

10. $\models_{w_j}^M \Diamond \psi$ si pour au moins un monde $w_i$ de $M$ on a $w_j R w_i$ on a $\models_{w_i}^M \psi$

Exemples avec le symbole $\Box$ :

— $\models_{w_j}^M \Box (\psi \wedge \phi)$ signifie que tous les mondes reliés à $w_j$ vérifient $\phi$ et $\psi$.

— $\models_{w_j}^M \Box \psi$ n'implique pas $\models_{w_j}^M \Box \Box \psi$, en effet même si tous les mondes qui sont reliés à $w_j$ vérifient $\psi$, il n'est pas certain que tous les mondes reliés aux mondes reliés à $w_j$ vérifient $\psi$. Par exemple dans le figure 1.1 $\models_{w_1}^M \Box Q$ mais on a pas $\models_{w_1}^M \Box \Box Q$ puisque le monde $w_2$ auquel est lié $w_1$ ne vérifie pas $\models_{w_2}^M \Box Q$.

On remarque que la sémantique de la logique propositionnelle s'applique au sein de chaque monde. Les formules sont soit vraies soit fausses au sein de chaque monde. Il est aussi possible de définir la validité d'une formule. En effet, si une formule est vraie dans tous les mondes du modèle, elle est dite *valide dans le modèle de Kripke* (par exemple si tous les mondes de la figure 1 contenaient $p$ alors $p$ serait valide dans ce modèle). Si une formule est valide dans tous les modèles possibles alors elle est dite *valide*, ce type de formule est soit une tautologie, soit un axiome (ou un théorème).

Par simplicité on dit parfois que la proposition $p$ est vraie dans le monde $w_i$ si le monde $w_i$ appartient à $\pi(p)$. Réciproquement, on dit que la proposition $p$ est fausse dans le monde $w_i$ si le monde $w_i$ n'appartient pas à $\pi(p)$. Et par continuité on dit que la formule $\psi$ est vraie dans le monde $w_i$ si $\models_{w_i}^M \psi$, et que la formule est fausse dans le monde $w_i$ si ce n'est pas le cas.

Le système axiomatique qui suit est correct et complet pour la sémantique présente. Ceci veut dire que l'ensemble des formules valides que l'on peut déduire de ces axiomes et règles d'inférences est le même que celui obtenu avec la sémantique présentée. Ainsi une logique modale est dite *normale* si elle admet :

1. la règle de nécessitation RN : $\Box \psi \rightarrow \psi$, si $\psi$ est valide alors $\Box \psi$ est valide.

2. la règle de Modus Ponens MP : $\frac{\psi \rightarrow \phi, \psi}{\phi}$, si $\psi$ implique $\phi$ et que $\psi$ est vrai alors $\phi$ est vrai.

3. les tautologies de la logique propositionnelle

4. l'axiome de distribution de Kripke K : $\Box (\psi \rightarrow \phi) \rightarrow (\Box \psi \rightarrow \Box \phi)$, distributivité de $\Box$

5. l'axiome Df : $\neg \Box \neg \psi \leftrightarrow \Box \psi$ liant $\Diamond$ et $\Box$, s'il n'existe pas de contre-exemple à $\psi$ alors $\psi$ est nécessaire.

Les logiques présentées dans la suite seront des extensions de cette logique.

# 1.2 Logique épistémique

## 1.2.1 Présentation

La logique épistémique est un type de logique modale qui traite la notion de connaissance et de croyance des agents [FHMV03, MH95, vvHK15]. L'agent croit certaines choses mais n'a pas d'information sur d'autres, il imagine alors plusieurs mondes possibles. Chacun de ces mondes représente ce que l'agent pense être possible et l'ensemble des mondes représente ce qu'il croit. Par exemple s'il pense que $p$ peut être vrai alors au moins un monde qu'il imagine possède $p$. Si tous les mondes qu'il imagine possèdent $p$ alors il croit que $p$ est vrai.

La modélisation de ces notions utilise le connecteur $\Box$, remplacé par la lettre $B$ signifiant « croit » ($B$ pour « Belief »). Par exemple $\models_{w_1}^M Bp$ signifie que dans le monde $w_1$, l'agent croit que $p$ est vrai. Cette formule est vraie si pour tout monde $w_j$ tel que $w_1 R w_j$ on a $\models_{w_j}^M p$.
Lorsqu'il y a plusieurs agents, pour les différencier, on associe à chacun d'entre eux un opérateur de croyance ainsi qu'une relation d'accessibilité. Appelons $N$ l'ensemble des agents. Pour chaque agent $\alpha$ nous utilisons un opérateur de croyance que l'on peut noter $B_\alpha$ (où $\alpha$ fait référence à l'agent $\alpha$). L'opérateur $\diamond$ est souvent remplacé par $\hat{B}_\alpha$ (pour rappel il peut s'écrire comme $\neg \Box \neg$). Nous introduisons également pour chaque agent une relation binaire $R_\alpha$. La relation $R_\alpha$ lie alors des mondes indistinguishables pour l'agent $\alpha$, c'est-à-dire ceux dont les propositions communes sont sues par l'agent $\alpha$. La sémantique de la logique modale ne change pas pour la logique épistémique sauf pour les règles 9 et 10 qui deviennent simplement :

$$ \models_{w_j}^{M} B_{\alpha} \psi \text{ si pour tous les mondes } w_i \text{ de } M, \text{ si nous avons } w_j R_{w_i} \text{ alors nous avons } \models_{w_i}^{M} \psi $$

$$ \models_{w_j}^{M} \hat{B}_{\alpha} \psi \text{ si pour au moins un monde } w_i \text{ de } M \text{ tel que } w_j R_{\alpha} w_i \text{ on a } \models_{w_i}^{M} \psi $$

Enfin, les raisonnements des agents peuvent s'effectuer sur les connaissances des autres agents. En d'autres termes, les agents ont des croyances sur les croyances des autres agents. Et pour aller plus loin, ils peuvent alors imaginer des mondes qu'ils savent faux, mais qui sont potentiellement vrais pour d'autres agents.

Par exemple $B_1B_2p \wedge \neg B_2B_1B_2p$ signifie que l'agent 1 croit que l'agent 2 croit $p$ mais que l'agent 2 ne croit pas que l'agent 1 croit que l'agent 2 croit $p$. Dans la partie sur la logique épistémique dynamique, des modèles de Kripke représentant ce type de formule seront montrés.

## 1.2.2 Système KD45

### Exemple

La logique épistémique présente deux familles d'axiomes fréquemment utilisés, le système S5 que nous verrons par la suite et le système KD45. Ce dernier traite de croyance et non pas de connaissance. En d'autres termes ce que l'agent pense pourrait finalement se révéler être faux.

<figure><img src="image_4.png" /><figcaption>FIGURE 1.2 – Exemple de modèle dans le système KD45</figcaption></figure>

Imaginons la situation suivante : une personne se lève le matin, ses volets sont fermés, elle a entendu la veille que ce jour il y aurait du brouillard et qu'il pleuvrait peut-être. Elle croit donc qu'il y a du brouillard et elle pense possible qu'il pleuve. Elle imagine donc deux mondes : dans ces deux mondes il y a du brouillard, et dans l'un d'entre eux il pleut. Cependant en réalité, il n'y a pas de brouillard et il pleut.
La modélisation de cet exemple est présentée dans la figure 1.2 sous la forme d'un graphe de Kripke. La proposition *p* signifie « il pleut », la proposition *b* signifie « il y a du brouillard ». Il y a trois mondes : *w*₁, *w*₂ et *w*₃. Le monde *w*₁ possède un double cerclage, car il représente le monde réel dans lequel il pleut et où il n'y a pas de brouillard. Le monde *w*₂ est lié à lui-même et au monde *w*₃, cela signifie que dans le cas où le monde réel serait le monde *w*₂, l'agent envisagerait les mondes *w*₂ et *w*₃ comme possibles. On peut effectuer le même raisonnement pour le monde *w*₃.

À l'inverse les mondes $w_2$ et $w_3$ ne sont pas liés au monde $w_1$ signifiant que dans le cas où le monde réel serait le monde $w_2$ ou $w_3$, le monde $w_1$ ne serait pas considéré comme possible. De plus le monde $w_1$ n'est pas lié à lui-même, signifiant qu'il n'est pas considéré comme possible par l'agent. Cependant celui-ci est lié aux mondes $w_2$ et $w_3$ indiquant que dans le cas où $w_1$ est le monde réel, ce qui est le cas, ces deux mondes sont considérés comme possibles.

Au final on a donc représenté l'exemple dans lequel le monde réel où il pleut n'est pas envisagé, d'où le terme de croyance « fausse ». Les seuls mondes envisagés sont ceux où il y a du brouillard et où il est possible qu'il pleuve.

### Axiomes

Formellement afin de pouvoir raisonner sur les croyances, on doit ajouter à la logique modale normale trois axiomes qui donnent son nom au système KD45 :

- (rappel) axiome K : $B_\alpha(\psi \to \phi) \to (B_\alpha\psi \to B_\alpha\phi)$

- axiome D : $B_\alpha\psi \to \neg B_\alpha\neg\psi$

- axiome 4 : $B_\alpha\psi \to B_\alpha B_\alpha\psi$

- axiome 5 : $\neg B_\alpha\psi \to B_\alpha(\neg B_\alpha\psi)$

L'axiome K est le même que vu précédemment. Il stipule que si un agent croit que $\psi$ implique $\phi$ alors s'il croit $\psi$, il croit $\phi$.

L'axiome D stipule que si un agent croit $\psi$ alors il ne croit pas que $\psi$ est faux. On peut remarquer que cet axiome n'est pas vrai dans toutes les logiques normales, par exemple on pourrait imaginer un système dans lequel des mondes ne sont reliés à aucun autre. Dans ce cas, on aurait, par définition de $B_\alpha$, $B_\alpha\psi$ et $B_\alpha\neg\psi$ vrai.

L'axiome 4 dit que si l'agent croit $\psi$ alors il croit qu'il croit $\psi$.

Enfin l'axiome 5 stipule que si l'agent ne croit pas $\psi$ alors il croit qu'il ne croit pas $\psi$.

Ce système d'axiomes régule en somme les relations d'accessibilité [HM92]. Dans le système KD45, chaque relation $R_\alpha$ liant les mondes possède les propriétés suivantes : sérialité, transitivité et euclidianité. La relation est *sérielle* : chaque monde est relié à au moins un autre. La relation est *transitive* : si $w_1 R_\alpha w_2$ et $w_2 R_\alpha w_3$ alors $w_1 R_\alpha w_3$. Enfin la relation est *euclidienne* : si $w_1 R_\alpha w_2$ et $w_1 R_\alpha w_3$ alors $w_2 R_\alpha w_3$.

### 1.2.3 Système S5

#### Présentation

Le système S5 traite de croyances qui ne sont que "vraies", on parle alors de connaissances et c'est le système dans lequel se place cette thèse. Le système S5 est moins expressif que le système KD45, par exemple on ne peut pas représenter l'exemple précédent, mais il est plus simple et surtout suffisant pour la modélisation de jeux.

En effet dans un jeu, l'environnement est contrôlé et donc toutes les connaissances sont « vraies », même lorsque le jeu laisse la possibilité aux joueurs de mentir. Dans ce cas la possibilité de mensonge est prise en compte et on a donc deux mondes possibles envisagés, celui où il y a eu mensonge et celui où
il n'a pas eu lieu. La seule façon de sortir du système S5 serait alors de tricher, ce que nous ne prendrons pas en compte.

Étant donné que l'on traite de connaissance, le connecteur « croire » *B* est remplacé par le connecteur « savoir » *K* (*K* pour « Know »).

## Exemple

Comme déjà mentionné, l'exemple précédent de l'homme qui envisage la météo du jour n'est pas modélisable dans le système S5. On pourrait le modifier légèrement afin qu'il le soit. Il suffit que la personne envisage qu'il y ait du brouillard, ou qu'il pleuve ou bien les deux. On aurait alors trois mondes possibles reliés entre eux et reliés à eux même, l'un d'entre eux étant le monde réel.

Cependant les exemples de la vie réelle ne sont pas les meilleurs pour le système S5 puisque la vie n'est pas un environnement contrôlé. Quand bien même la météo prévoirait une journée ensoleillée ou nuageuse le lendemain, nous ne serions pas à l'abri d'une averse. L'exemple que je vais présenter est issu d'un jeu, donc venant d'un environnement contrôlé.

Imaginons un jeu composé de trois cartes, A,B et C, l'une d'entre elles est distribuée à une personne. Cette personne n'a pas encore pu retourner la carte, elle imagine donc trois mondes possibles, un monde où elle a la carte A, un monde où elle a la carte B et un monde où elle a la carte C.

<figure><img src="image_5.png" /><figcaption>FIGURE 1.3 – Exemple de modèle dans le système S5</figcaption></figure>

Cet exemple est présenté dans la figure 1.3. Dans cet exemple nous avons trois mondes possibles reliés entre eux et reliés à eux-mêmes. Ils sont donc tous envisagés comme possibles par l'agent et semblent équivalents pour lui.

Le monde $w_1$ est représenté par un double cerclage, c'est donc le monde réel dans lequel le joueur a reçu la carte A. Ceci n'est pas un élément connu du joueur, uniquement du maître du jeu, être omniscient. Cela permet simplement de mieux visualiser la modélisation et lors des prochains exemples plus complexes, de mieux visualiser l'état des connaissances de chacun des joueurs.

## Axiomes

Le système S5 est un système normal auquel on ajoute deux axiomes :

- (rappel) axiome K : $K_\alpha(\psi \to \phi) \to (K_\alpha\psi \to K_\alpha\phi)$

- axiome 5 : $\neg K_\alpha\psi \to K_\alpha(\neg K_\alpha\psi)$

- axiome T : $K_\alpha\psi \to \psi$
L'axiome T exprime le fait que ce qui est su est vrai. La signification des axiomes K et 5 change un peu. L'axiome K dit que si l'agent sait que $\psi$ implique $\phi$ alors s'il sait $\psi$, il sait $\phi$. L'axiome 5 exprime le fait que si l'agent ne sait pas, alors il sait qu'il ne sait pas. De ces trois axiomes on peut déduire les axiomes D et 4 du système précédent (voir annexe A.1). On parlera alors de théorèmes D et 4 plutôt que d'axiomes D et 4.

Ainsi le théorème D signifie ici que si l'agent sait A alors il ne sait pas que A est faux. Le théorème 4 stipule simplement que l'agent sait ce qu'il sait.

Dans ce système, $R_\alpha$ liant les mondes possède les propriétés suivantes : sérielle, transitive, euclidienne, réflexive et symétrique. La réflexivité implique que chaque monde est lié à lui-même. La symétrie indique que si $w_1 R_\alpha w_2$ alors $w_2 R_\alpha w_1$. En d'autres termes, dans le modèle de Kripke associé au système S5, chaque arête est orientée dans les deux sens, les sommets reliés à un sommet commun forment une clique et enfin chaque sommet se pointe lui-même.

### Langage

On définit le langage $\mathbb{L}$ dans ce système comme l'ensemble des formules $\phi$ définies par la grammaire suivante en BNF :

$$ \phi ::= \top \mid p \mid \neg \phi \mid \phi \lor \phi \mid \phi \land \phi \mid \phi \rightarrow \phi \mid \phi \leftrightarrow \phi \mid K_{\alpha} \phi $$

### 1.2.4 Connaissance commune

La notion de connaissance (ou croyance commune suivant le système dans lequel on se place) est assez importante et est très souvent introduite en prenant l'exemple du code de la route [Lew69]. Supposons que l'on ait une route avec deux voitures A et B roulant dans des sens opposés. A priori, tout se passe bien si A sait qu'on roule à droite et que B sait qu'on roule à droite. Mais si A ne sait pas que B sait qu'on roule à droite, il pourrait décider de rouler à gauche dans l'idée de potentiellement éviter B. Il faut donc que A sache que B sait qu'on roule à droite, et réciproquement.

Mais il faut aussi que B sache que A sait que B roule à droite, sinon B pourrait décider de rouler à gauche en pensant que A pourrait avoir l'idée de rouler à gauche pour l'éviter. Donc il faut que B sache que A sait que B sait qu'on roule à droite. Et ainsi de suite...

Pour définir ce qu'est une connaissance commune, prenons un groupe d'agents G et commençons par définir $E_G^1(p) = \bigwedge_{\alpha \in G} K_\alpha p$ signifiant : "tous les agents dans le groupe G savent p". Par continuité $E_G^2(p) = E_G^1(E_G^1(p))$ signifiant tous les agents dans le groupe G savent que tout le monde dans le groupe G sait p.

La connaissance commune de p dans un groupe G noté $C_G(p)$ est définie comme :

$C_G(p)$ est vrai si et seulement si $E_G^k(p)$ est vrai pour $k$ allant de 1 à l'infini.

Afin d'inclure la connaissance commune dans la logique modale, on se doit de rajouter une règle à la sémantique. Tout d'abord, introduisons la notion de *G-atteignable*. Un monde $w_i$ est G-atteignable en une étape par un monde $w_j$ si la relation d'un agent du groupe G relie ces deux mondes. Il est G-atteignable en 2 étapes si les deux mondes ont en commun un monde G-atteignable en une étape. On peut continuer ainsi pour 3, 4,..., n étapes. Finalement, un monde $w_i$ est G-atteignable depuis un monde $w_j$ s'il existe $k$ tel que $w_i$ soit G-atteignable par $w_j$ en $k$ étapes. On peut à présent rajouter une règle à la sémantique :

$$ \models_{w_i}^{M} C_G(\phi) \text{ si et seulement si } \models_{w_j}^{M} \phi \text{ pour tous les mondes } w_j \text{ qui sont G-atteignables depuis } w_i. $$

Un exemple de connaissance commune sera présenté dans la section suivante.
## 1.3 Logique épistémique dynamique

### 1.3.1 Présentation

Pour introduire la logique épistémique dynamique (ou DEL pour « Dynamic Epistemic Logic »), nous allons utiliser le système S5 et continuer avec un exemple de connaissance commune. Cet exemple est connu sous le nom de « muddy children puzzle » et possède plusieurs variantes. Nous allons étudier l'une d'entre elles. Deux joueurs sont dans une même salle, ils peuvent se voir, mais pas communiquer entre eux. Une personne extérieure entre et colle sur le front de chaque participant un papier sur lequel est écrit « propre » ou bien « sale ». Le but du jeu est de savoir si l'on est propre ou sale.

Considérons le cas où la personne extérieure a collé le mot « sale » sur les deux participants. Le joueur 1 voit le front du joueur 2, il sait que le front du joueur 2 est sale. Mais il ne sait pas si lui-même est sale. Il imagine alors deux mondes possibles, le monde où il est propre et celui où il est sale. Le joueur 2 se fait la même réflexion. Le problème est représenté dans le modèle de Kripke de la figure 1.4. On définit les propositions S1 pour « le joueur 1 est sale » et S2 pour « le joueur 2 est sale ».

Il est important de noter qu'en logique épistémique un modèle de Kripke est aussi appelé *modèle épistémique* ou bien encore *état épistémique*.

Ce problème traite de connaissance vraie, il est donc étudié dans le système S5. Pour rappel dans ce système chaque lien est à double sens et les mondes sont aussi reliés à eux-mêmes. Étant donné que ces caractéristiques sont intrinsèques au système S5, elles peuvent parfois ne pas être représentées dans les schémas.

<figure><img src="image_6.png" /><figcaption>FIGURE 1.4 – État épistémique initial du Muddy children puzzle</figcaption></figure>

On va s'attarder à expliquer ce graphe avant de continuer l'exemple. Le monde réel est ici $w_1$ (représenté par le double cerclage) où les deux personnes sont sales. Dans ce problème, les mondes $w_1$ et $w_2$ sont équivalents pour le joueur 1 : il sait que le joueur 2 est sale, mais ne connaît pas son propre état. Par contre, ces deux mondes ne sont pas équivalents pour le joueur 2, car lui connaît l'état du joueur 1. Les deux mondes $w_1$ et $w_2$ sont donc reliés par la relation $R_1$ mais pas par la relation $R_2$.

Ainsi, le monde $w_1$ est relié au monde $w_1$ et au monde $w_2$ par la relation $R_1$. Le monde $w_1$ et $w_2$ ont en commun l'état sale du joueur 2 et n'ont pas en commun l'état du joueur 1. De cette manière on modélise les connaissances du joueur 1 dans le monde $w_1$. Encore une fois, ce que les mondes reliés
ont en commun sont les certitudes qu'a le joueur, et ce qu'ils n'ont pas en commun représente ce que le joueur pense simplement possible.

Enfin, on pourrait se demander pourquoi le monde $w_4$ où les deux ne sont pas sales est envisagé. En effet, a priori les deux joueurs voyant le mot « sale » sur le front de l'autre joueur, savent qu'au moins un joueur est sale. Mais pour le joueur 1, ne connaissant pas son état, il peut penser qu'il est propre, c'est-à-dire qu'il se trouve dans le monde $w_2$. Dans ce cas, il imagine que le joueur 2 voit sur son front qu'il est propre. Il imagine alors que le joueur 2 imagine qu'il y a deux mondes possibles, le monde $w_2$ et le $w_4$ où ils sont tous les deux propres.

On peut continuer avec la même réflexion, le joueur 1 peut imaginer que le joueur 2 imagine que les mondes $w_4$ et $w_3$ sont équivalents pour le joueur 1. Et ainsi de suite. On est donc capable de représenter des connaissances sur les connaissances avec ce graphe.

Il est également possible de rendre compte des connaissances des joueurs sous forme de formules. Voici une partie de ce que sait le joueur 1 dans le monde réel (ce qui est également vrai en remplaçant joueur 1 par joueur 2) :

1. $|_{w_1}^M K_1 S2$, le joueur 1 sait que le joueur 2 est sale. En effet, le monde $w_1$ est relié par $R_1$ aux mondes $w_1$ et $w_2$ dans lesquels le joueur 2 est sale.

2. $|_{w_1}^M \neg K_1 S1$, le joueur 1 ne sait pas qu'il est sale puisque le monde $w_1$ est relié par $R_1$ au monde $w_2$ dans lequel il n'est pas sale.

3. $|_{w_1}^M \neg K_1 \neg S1$, le joueur 1 ne sait pas qu'il est propre, puisque le monde $w_1$ est relié par $R_1$ au monde $w_1$ dans lequel il est sale.

4. $|_{w_1}^M K_1(\neg K_2 S1 \land K_2 \neg S1)$ le joueur 1 sait que le joueur 2 sait l'état du joueur 1, sale ou pas sale. En effet le monde $w_1$ est relié par $R_1$ aux mondes $w_1$ et $w_2$. Or le monde $w_1$ est relié par $R_2$ aux mondes $w_1$ et $w_3$ dans lesquels $S1$ est vrai, donc on a $|_{w_1}^M K_2 S1$. Par ailleurs, $w_2$ est relié par $R_2$ aux mondes $w_2$ et $w_4$ dans lesquels $\neg S1$ est vraie, on a donc $|_{w_2}^M K_2 \neg S1$.

5. $|_{w_1}^M K_1(\neg K_2 S2 \land \neg K_2 \neg S2)$ le joueur 1 sait que le joueur 2 ne connaît pas son état. En effet, le monde $w_1$ est relié par $R_1$ aux mondes $w_1$ et $w_2$. Or le monde $w_1$ est relié par $R_2$ aux mondes $w_1$ et $w_3$ dans lesquels la valeur pour $S2$ est différente, donc on a $|_{w_1}^M \neg K_2 S2$ et $|_{w_1}^M \neg K_2 \neg S2$. Par ailleurs, $w_2$ est relié par $R_2$ aux mondes $w_2$ et $w_4$ dans lesquels la valeur pour $S2$ est différente, on a donc $|_{w_2}^M \neg K_2 S2$ et $|_{w_2}^M \neg K_2 \neg S2$.

Parmi les formules présentées, les formules 2 à 5 sont des connaissances communes aux deux joueurs. Dans cet exemple, tous les mondes sont G-atteignables par le groupe G formé des deux joueurs. Par exemple, la formule $\neg K_1 S1$ est vraie dans tous les mondes, donc dans tous les mondes G-atteignables depuis le monde $w_1$. Nous pouvons donc affirmer $|_{w_i}^M C_G(\neg K_1 S1)$. Le fait que le joueur 1 ne sache pas s'il est sale est bien une connaissance commune. À l'inverse, la formule $K_1 S2$ n'est pas vraie dans les mondes $w_3$ et $w_4$ qui sont G-atteignables depuis le monde $w_1$. Donc nous n'avons pas $|_{w_i}^M C_G(K_1 S2)$. Et en effet, ce n'est pas une connaissance commune.

On remarque ici la puissance du modèle de Kripke. En effet, même s'il paraît simple, avec un graphe de seulement quatre mondes avec quatre arêtes, l'ensemble des connaissances de chaque joueur sur l'état du jeu peut être représenté. Le nombre de formules que l'on peut extraire est d'ailleurs infini.

1.3.2 Annonce publique

Pour rappel, le but du Muddy children puzzle pour le joueur est de savoir s'il est sale ou propre. Dans l'état actuel des choses, les deux joueurs ne connaissent pas la réponse. La suite du jeu demande l'intervention d'un évènement extérieur, ce que nous allons voir tout de suite en introduisant la partie dynamique de cette logique.
La personne extérieure annonce publiquement que au moins un des deux joueurs est sale. Il faut donc mettre à jour les connaissances des joueurs. Même si les joueurs savaient déjà tous les deux qu'au moins l'un d'entre eux était sale, ce n'était pas une connaissance commune. C'est à présent le cas et c'est ce que les annonces publiques apportent : des connaissances communes.

L'annonce publique [Pla07] est la plus simple des annonces à traiter. En effet, tous les joueurs apprennent la même chose et ils le savent. Dans l'exemple traité ici la connaissance commune acquise est qu'au moins un des deux est sale : $S1 \lor S2$. Nous allons donc retirer les mondes pour lesquels cette formule est fausse : le monde $w_4$. En effet, les joueurs ne peuvent plus imaginer un monde où cette connaissance est fausse ou même imaginer que l'autre joueur puisse l'imaginer (voir figure 1.5).

<figure><img src="image_7.png" /><figcaption>FIGURE 1.5 – Modèle épistémique après l'annonce de la personne extérieure</figcaption></figure>

Pour autant, les deux joueurs ne connaissent pas encore la réponse. Chacun imagine deux mondes équivalents où la réponse est différente. Pour continuer le jeu, il faut faire appel à une deuxième annonce publique : « est-ce que l'un de vous deux connaît son état ? » et les deux joueurs répondent « non ». La connaissance commune acquise est ainsi celle-ci : $\neg K_1 S1 \land \neg K_2 S2$.

On va mettre à jour les connaissances des joueurs. Le joueur 1 sait que le joueur 2 ne connaît pas son état. Or le monde $w_2$ n'est relié avec aucun autre monde pour le joueur 2, c'est-à-dire que dans le monde $w_2$, le joueur 2 connaît son état. Ce monde n'est donc plus envisageable pour le joueur 1, il faut donc le supprimer. Le joueur 2 effectue la même réflexion pour le monde $w_3$ et le joueur 1. En somme, il faut retirer les mondes qui ne sont pas équivalents par rapport à d'autres. Et finalement, le modèle épistémique ne contient plus qu'un seul monde et les deux joueurs connaissent leur état (voir figure 1.6).

Formellement, on applique des restrictions au modèle épistémique. Soit $M = (W, R = \{R_1, R_2\}, \pi)$ un modèle épistémique, on définit la restriction de $M$ par $p$ comme $M^p = (W^p, R^p = \{R_1^p, R_2^p\}, \pi^p)$ où

— $W^p = \{w_i \in W \text{ tel que } \models_{w_i}^M p\}$ restriction à l'ensemble des mondes où $p$ est vrai

— $R_\alpha^p = R_\alpha \cap (W^p \times W^p)$ restrictions des relations aux mondes de $W^p$

— $\pi^p = \pi|_{W^p}$ restriction de la valuation aux mondes de $W^p$

Pour l'exemple on avait donc $M$, puis $M^{S1 \lor S2}$ et enfin $(M^{S1 \lor S2})^{-K_1 S1 \land \neg K_2 S2}$
<figure><img src="image_8.png" /><figcaption>FIGURE 1.6 – Modèle épistémique après les deux annonces publiques</figcaption></figure>

### 1.3.3 Action Publique

L'annonce publique est en fait un type particulier d'action [DHK05] de la logique épistémique dynamique. De manière générale les actions permettent de décrire des changements de l'état du jeu et pas seulement de l'état des connaissances. Par exemple, les actions permettent de représenter la pioche d'une carte ou bien l'ouverture d'une porte. L'action part d'un modèle vers un autre modèle. Elle se compose d'une précondition et d'une postcondition. Elle fonctionne de la manière suivante : chaque monde du modèle vérifiant la précondition est modifié par la postcondition, les autres mondes sont supprimés et les liens entre les mondes restants sont conservés.

Prenons l'exemple précédent légèrement modifié. Le joueur 1 sait qu'il est sale, le joueur 2 est sale, mais ne connaît pas son état. On définit les propositions $S1$ pour « le joueur 1 est sale » et $S2$ pour « le joueur 2 est sale ». De plus, pour simplifier, on marque $\neg S1$ lorsque $S1$ est faux dans le monde (formellement lorsque le monde ne fait pas partie de $\pi(S1)$). L'action est la suivante : on annonce au joueur 2 qu'il est sale et on rend le joueur 1 propre. La précondition est donc la formule $S2$. La postcondition est la suivante : $post(S1) = \neg S1, post(S2) = S2$.

Le résultat est donc un modèle ne contenant qu'un monde où les deux joueurs connaissent leur état, le joueur 1 est propre et le joueur 2 est sale.

Formellement, la précondition est une formule du langage. La postcondition est normalement elle aussi une formule du langage, mais ici on utilisera une simplification suffisante qu'est une fonction de $\mathbb{P}$ vers $\{\top, \bot, p, \neg p\}$. La signification de la postcondition est la suivante $post(p) = p$ signifie que l'on ne change pas la valeur de la proposition $p, post(p) = \neg p$ signifie qu'on inverse la valeur de $p, post(p) = \top$ signifie que la proposition devient vraie, $post(p) = \bot$ signifie que la proposition devient fausse.

**Définition 4 (Action)** Soit $\mathbb{P}$ un ensemble de propositions, soit pre une formule du langage $\mathbb{L}$, soit post une fonction de $\mathbb{P}$ vers $\{\top, \bot, p, \neg p\}$, on définit une action $a$ comme le couple $a = (pre, post)$.

Lorsqu'une action est effectuée, la modélisation de l'évolution de l'état épistémique ressemble à celle de l'annonce publique.

**Définition 5 (Exécution d'une action)** Soit $A$ un ensemble d'actions possibles sur $\mathbb{P}$, soit $M = (W, R, \pi)$ un modèle épistémique. L'exécution de l'action $a$, élément de $A$, dans $M$ donne le modèle $M|_a = (W|_a, R|_a, \pi|_a)$ où :

- $W|_a = \{w_i \in W \text{ tel que } \models_{w_i}^{M} \text{pre}(a)\}$ restriction à l'ensemble des mondes vérifiant la précondition de $a$.

- $R|_a = R \cap (W_a \times W_a)$ restriction des relations aux mondes de $W|_a$.
<figure><img src="image_9.png" /><figcaption>FIGURE 1.7 – Effet d’une action</figcaption></figure>

$$
\begin{equation*}
- \pi_{|a}(p) = W_{|a} \cap \left\{
\begin{array}{ll}
W & \text{si } \mathrm{post}(a)(p) = \top \\
\emptyset & \text{si } \mathrm{post}(a)(p) = \bot \\
\pi(p) & \text{si } \mathrm{post}(a)(p) = p \\
W \setminus \pi(p) & \text{si } \mathrm{post}(a)(p) = \neg p
\end{array}
\right.
\quad \text{restriction de la valuation aux mondes de} \\
M_{|a} \text{ et réaffectation de la valeur des variables propositionnelles}
\end{equation*}
$$

1.3.4 Action semi-privée ou indiscernable

Présentation

Il existe un autre type d'action : les actions dites semi-privées ou indiscernables [BMS98, BMH05].
L'action est visible de tous, mais ses effets peuvent ne pas être connus de tous comme par exemple la
pioche d'une carte par un joueur. Les actions semi-privées suffisent pour décrire tous les évènements de
n'importe quel jeu.

Il existe aussi des actions dites privées. Elles permettent même de décrire des évènements qui ne sont pas connus de tous, des évènements effectués en secret, comme une triche (par exemple le fait de sortir un as de sa poche). Cependant, ces évènements privés sortent du cadre des jeux et sortent du cadre du système S5, ils ne seront donc pas étudiés.

Exemple

Pour expliciter ce type d'action, prenons en exemple une variante très simplifiée du cluedo [vD01].
Dans le jeu, il y a trois cartes (A, B et C) et deux joueurs (1 et 2). Un croupier distribue une carte à chaque
joueur et laisse face retournée la troisième carte. Le but du jeu est de savoir quelle est la carte retournée.
Pour fixer le jeu, le joueur 1 a la carte A, le joueur 2 a la carte B et donc la troisième carte est C. Sous la
forme d'un modèle épistémique l'état actuel du jeu est présenté en figure 1.8. Dans le modèle présenté,
chaque lien est à double sens et chaque monde est relié a lui-même pour chaque relation.
<figure><img src="image_10.png" /><figcaption>FIGURE 1.8 – Modèle épistémique de l'état initial du cluedo</figcaption></figure>

Le monde réel est le monde $w_1$. Dans ce monde $w_1$, le joueur 1 imagine deux mondes, celui où le joueur 2 a la carte B (le monde $w_1$) et celui où le joueur 2 a la carte C (le monde $w_2$). Ce même joueur 1 présume que si le monde $w_2$ est le monde réel, alors le joueur 2 imagine deux mondes possibles : le monde $w_2$ et le monde $w_3$. En poursuivant sa réflexion, le joueur 1 se dit que si le joueur 2 imagine le monde $w_3$ comme le monde réel alors ce même joueur 2 doit imaginer que le joueur 1 se dit que le monde $w_3$ et le monde $w_4$ sont possibles. On peut de cette manière continuer le raisonnement pour décrire le modèle épistémique.

Une autre manière d'expliquer ce modèle serait la suivante : le joueur 1 imagine qu'il y a deux mondes possibles, les mondes $w_1$ et $w_2$. Le joueur 1 envisage alors deux cas de figure pour le joueur 2 : soit le joueur 2 imagine comme possibles les mondes $w_1$ et $w_6$, soit il imagine comme possibles les mondes $w_2$ et $w_3$.

## Modèle d'évènement

Si l'on reprend l'exemple du Cluedo simplifié, une action disponible pour le joueur 1 est de regarder la troisième carte sans que le joueur 2 ne voit la carte. De manière générale, sans connaissance de la disposition des cartes, il y a trois possibilités : que la carte soit un A, un B ou un C. Après cette action, le joueur 1 connaîtra donc l'état du jeu et le joueur 2 le saura.

La mise à jour des connaissances est plus difficile que pour une action publique. En effet il faut ici
combiner trois actions : celle où le joueur 1 voit la carte A (action *a*), celle où il voit la carte B (action *b*) et celle où il voit la carte C (action *c*).

Le croupier autorise le joueur 1 à regarder la troisième carte. Le joueur 1 regarde la troisième carte, le joueur 2 voit que le joueur 1 regarde la troisième carte. Le joueur 1 connaît donc l'état du jeu et le joueur 2 envisage deux possibilités : le joueur 1 a vu que la troisième carte est A ou le joueur 1 a vu que la troisième carte est C.

La précondition de l'action *a* est $pre(a) = (T : A)$, en effet pour que le joueur 1 voit la carte A, il faut que la carte A soit sur la table. De manière analogue, la précondition de l'action *b* est $pre(b) = (T : B)$ et celle de l'action *c* est $pre(c) = (T : C)$.

Les postconditions sont elles très simples puisque rien ne change. Pour chaque proposition *p* on a simplement $post(a)(p) = post(b)(p) = post(c)(p) = p$, c'est-à-dire qu'on ne change pas la valeur des propositions.

Ensuite, il nous faut assembler ces trois actions. Pour cela nous allons utiliser un système analogue au système S5. Le lecteur attentif pourrait argumenter que le joueur 2 ne peut pas imaginer que le joueur 1 puisse voir la carte que lui-même tient en main, c'est-à-dire la carte B. Cependant, cet aspect du raisonnement est déjà pris en compte par le modèle épistémique et d'autre part, la prendre en compte dans le modélisation de l'action serait sur-contraindre cette action. L'idée est en fait de modéliser l'action générale « regarder la carte sur la table » et ce, peu importe la configuration du jeu. Le fait que le joueur 2 sait que le joueur 1 ne pourra pas voir la carte B est une conséquence de ses connaissances. En effet on pourrait imaginer le même jeu avec les cartes en double et dans ce cas, une carte B pourrait être à la fois sur la table et dans la main du joueur 2.

Pour le joueur 2 les trois actions sont indiscernables l'une de l'autre. On va donc lier ces trois actions par une relation d'équivalence pour le joueur 2. À l'inverse, pour le joueur 1 les trois actions sont discernables, puisqu'il voit quelle carte lui est montrée, il n'y aura donc pas de lien d'équivalence pour le joueur 1.

Chaque action est également liée à elle-même. C'est la différence avec une action privée. En effet si l'action n'était pas liée à elle-même cela signifierait qu'elle ne serait pas envisagée comme possible quand elle serait jouée. Elle serait donc considérée comme une action secrète (ou non prévue par le jeu).

L'évènement dans sa globalité est représenté sous la forme d'un modèle d'évènement. Un modèle d'évènement *E* est formé d'un ensemble d'actions et des relations d'accessibilité qui les unissent.

**Définition 6 (modèle d'évènement)** Soit $A^e = \{a_i\}_{0 \ge i \ge k}$ un ensemble d'actions, soit $R^e = \{R_\alpha^e\}_{\alpha \in N}$ un ensemble de relations binaires sur $A^e$ dites relations d'accessibilité, on définit le modèle d'évènement *E* comme le couple $E = (A^e, R^e)$.

Le modèle d'évènement de l'évènement « regarder la troisième carte » est présenté dans la figure 1.9. De la même façon que pour le modèle épistémique, on représente l'action réellement effectuée par un double cerclage. Dans un modèle d'évènement du système S5, les relations d'accessibilité sont des relations d'équivalence (réflexives, symétriques, transitives).

Dans la figure 1.10, à gauche se trouve le modèle épistémique *M* et à droite le modèle d'évènement *E*. Le produit de ces deux graphes s'effectue en deux étapes et donne le modèle épistémique produit $M \otimes E$.

## Modèle épistémique produit

La première étape consiste à déterminer l'ensemble des mondes possibles. Pour chacune des actions on va garder les mondes vérifiant leur précondition et on va modifier ces mondes suivant leur postcondition. La deuxième étape consiste à déterminer les liens entre les mondes. Deux mondes sont liés par une
<figure><img src="image_11.png" /><figcaption>FIGURE 1.9 – Modèle d’évènement de l’action « regarder la troisième carte ».</figcaption></figure>

relation $R_\alpha$ si d'une part, les mondes dont ils sont originaires sont liés par la relation $R_\alpha$ et si les actions qui les ont produits sont liées par la relation $R_\alpha^e$. (Il ne faut pas oublier que les mondes et les actions sont aussi reliés à eux-mêmes).

**Définition 7 (modèle épistémique produit)** Soit $M = (W, R, \pi)$ un modèle épistémique, soit

$E = (A^e, R^e)$ un modèle d'évènement tel que $|R| = |R^e| = N$, on appelle modèle épistémique produit le triplet $M \otimes E = (W^\otimes, R^\otimes, \pi^\otimes)$ où :

$$— W^\otimes = \{(w, a) \in W \times A^e \text{ tel que } \models_w^{\otimes} \text{ pre}(a)\}$$

$$— R^\otimes = \{R_\alpha^\otimes\}_{\alpha \in N} \text{ où } \forall (w, a), (w', a') \in W \times A^e, (w, a) R_\alpha^\otimes (w', a') \text{ si et seulement si } w R_\alpha w' \text{ et } a R_\alpha^e a'$$

$$— \pi^\otimes(p) = \{(w, a) \in W \times A^e \text{ tel que } w \in \pi|_a(p)\}$$

Dans la figure 1.11, le modèle épistémique produit $M \otimes E$ se trouve à gauche. Les mondes $w_1 \otimes c$ et $w_4 \otimes c$ sont issus de l'action $c$. Les mondes $w_2 \otimes b$ et $w_5 \otimes b$ sont issus de l'action $b$. Les mondes $w_3 \otimes a$ et $w_6 \otimes a$ sont issus de l'action $a$. Un lien $R_2$ relie les mondes $w_1 \otimes c$ et $w_6 \otimes a$ puisque les deux mondes $w_1$ et $w_6$ étaient reliés par $R_2$, de même que les actions $a$ et $c$. À l'inverse, il n'y pas de lien $R_1$ entre $w_3 \otimes a$ et $w_4 \otimes c$ même si les mondes $w_3$ et $w_4$ en possèdent un, car les actions $a$ et $c$ ne sont pas liées par la relation $R_1$.

## Exécution d'un évènement

Ce modèle épistémique produit $M \otimes E$ est renommé modèle épistémique $M|_E$ pour plus de simpli-cité. Celui-ci est présenté à droite dans la figure 1.11.

L'explication de ce modèle est donc un peu plus complexe. Après que le joueur 1 a regardé la carte, il n'a plus de doute sur l'état du jeu et le joueur 2 le sait. Cependant le joueur 2 ne sait toujours pas quelle est la carte sur la table, soit A, soit C. Et sa réflexion s'arrête là. En effet, il y a la connaissance commune que le joueur 1 n'a plus de doute et que le joueur 2 hésite entre les cartes A et C. Cet état de connaissance est représenté par les mondes $w_1, w_6$ et la relation $R_2$ qui les unit.

D'un autre côté, les mondes $w_2, w_3, w_4, w_5$ ne sont pas reliés au monde réel, ce sont des mondes hypothétiques. Ils ne représentent pas l'état des connaissances des joueurs dans la réalité. Cependant, ils ne sont pas invraisemblables, si le monde réel était le monde $w_2$ (ou $w_3, w_4, w_5$), ils représenteraient bien l'état des connaissances après l'évènement.
<figure><img src="image_12.png" /><figcaption>FIGURE 1.10 – Le modèle épistémique et le modèle d’évènement à croiser</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>FIGURE 1.11 – Le modèle épistémique produit et le modèle épistémique résultant</figcaption></figure>
On remarque alors qu'une action publique est un évènement semi-privé particulier n'ayant qu'une seule action possible. Afin de généraliser l'étude, on ne gardera donc que le modèle d'évènement pour représenter tous les actions/évènements du jeu.

### 1.3.5 Réalité

La notion de monde réel et sa représentation par un double cerclage ont été mentionnées à plusieurs reprises. Ceci permet de mieux situer l'état actuel des connaissances des agents sur l'état du monde.

On notera $M^{w_1}$ ou $(M, w_1)$ lorsque le monde réel du modèle épistémique $M$ est le monde $w_1$ et $E^{a_1}$ ou $(E, a_1)$ lorsque l'action réelle de l'évènement est l'action $a_1$, et par extension, $M \otimes E^{w_1, a_1}$ ou $(M \otimes E, w_1, a_1)$ lorsque le monde et l'action réels sont $w_1$ et $a_1$.

De plus, pour simplifier, on ne gardera en général que les mondes N-atteignables depuis le monde réel (l'ensemble des mondes accessibles directement et indirectement depuis le monde réel). En effet, un monde inaccessible depuis le monde réel ne représente pas les connaissances des joueurs sur l'état actuel du jeu. Ces mondes inaccessibles représentent des états de jeu hypothétiques. Pour ajouter un argument en faveur de la suppression des mondes inatteignables à partir du monde réel, signalons qu'aucune action, qu'elle soit publique ou semi-privée (ou même privée) ne permet de reconnecter un monde qui ne l'était plus. Ces mondes déconnectés ne représenteront donc plus l'état des connaissances des joueurs quel que soit le moment ultérieur du jeu.

## 1.4 ESTS - Epistemic State Transition System

### 1.4.1 Présentation

Les ESTS sont d'autres modèles de représentation des connaissances utilisés par l'Epistemic GDL [JZPZ16, JZPZ21] qui peuvent servir à représenter les jeux. La structure de modélisation est différente, tournée vers la dynamique du jeu. Tout d'abord, afin de fixer les idées, on va signer un jeu par un ensemble de propositions $\mathbb{P}$, un ensemble d'actions $\mathcal{A}$ et un ensemble de joueurs $\mathcal{N}$.

**Définition 8 (Signature de Jeu)** Soit un ensemble de propositions $\mathbb{P}$, un ensemble d'actions $\mathcal{A}$ et un ensemble de joueurs $\mathcal{N}$. On appelle signature de jeu le triplet $J = (\mathbb{P}, \mathcal{A}, \mathcal{N})$

Avec DEL, les actions sont représentées par des transitions entre modèles, chaque modèle représentant un état épistémique du jeu. Avec ESTS les transitions sont incluses dans le modèle, un modèle ESTS représentant donc le jeu entier.

Un ESTS $\mathcal{M}$ est comme pour la logique épistémique dynamique (DEL) un ensemble de mondes $\mathcal{W}$, un ensemble $\mathcal{R}$ de relations d'accessibilité et une fonction $\pi$ de valuation. Cependant il nous faut rajouter $\delta$ une fonction partielle de $\mathcal{W} \times \mathcal{A}$ vers $\mathcal{W}$ dite *fonction de transition*. Cette fonction $\delta$ représente les transitions entre les mondes, chaque action agissant directement sur les mondes et non pas sur les modèles entiers.

**Définition 9 (ESTS)** Soit une signature de jeu $J = (\mathbb{P}, \mathcal{A}, \mathcal{N})$, soit un ensemble de mondes $\mathcal{W}$, un ensemble de relations d'équivalence $R = \{R_\alpha\}_{\alpha \in \mathcal{N}}$, une fonction de valuation $\pi$ de $\mathbb{P}$ vers $\mathcal{W}$, et une fonction partielle $\delta$ dite de transition de $\mathcal{W} \times \mathcal{A}$ vers $\mathcal{W}$. On appelle ESTS le quadruplet $\mathcal{M} = (\mathcal{W}, \mathcal{R}, \delta, \pi)$.

Les relations entre les mondes sont des relations d'équivalence, nous sommes donc dans le système S5.
À la différence de l'ensemble des mondes W d'un modèle DEL qui contient l'ensemble des mondes imaginables de l'état courant, l'ensemble des mondes W d'un modèle ESTS contient tous les mondes imaginables du jeu entier.

La représentation visuelle d'un modèle ESTS serait un graphe multidimensionnel, chaque étage re-
présentant un état du jeu et les transitions entre les étages étant les actions.

Étant donné que l'ESTS représente l'ensemble des états possibles d'un jeu, on appelle *histoire* un ensemble de transitions effectuées depuis un monde jusqu'à un autre monde. Une histoire peut, par exemple, représenter la succession des étapes qui se sont réellement déroulées pendant la partie, depuis le début jusqu'à la fin. Comme pour le monde réel dans les modèles DEL, l'histoire d'un ESTS nous permet de nous placer au sein du modèle.

**Définition 10 (histoire)** *Soit un ESTS $\mathbb{M} = (W, R, \delta, \pi)$, on appelle histoire $h$ une séquence finie ($w_1, a_1, w_2, ..., a_{n-1}, w_n$) où chaque $w_k \in W$ et pour $k$ allant de 1 à $n-1$ $\delta(w_k, a_k) = w_{k+1}$.*

1.4.2 Exemple

A titre d'illustration, nous allons reprendre l'exemple précédent du cluedo simplifié : il y a deux joueurs, trois cartes A,B,C, le joueur 1 reçoit la carte A, le joueur 2 reçoit la carte B et sur la table reste la carte C face retournée. Le but initial est de savoir quelle est la carte retournée. Il n'y a qu'une action possible, celle où le croupier autorise le joueur 1 à regarder la carte retournée. En DEL il était nécessaire d'avoir plusieurs actions, suivant la carte se trouvant sur la table pour définir l'évènement "regarder la carte". Ici, l'action n'est que mentionnée, elle est représentée uniquement par des transitions entre mondes. C'est comme si l'action avait des effets différents suivant le monde d'origine. En quelque sorte on se passe de la procédure de création du modèle d'évènement pour ne garder que le nom de cet événement. Notons $r$ l'action de regarder la carte, nous avons donc la signature de jeu $J = (\mathbb{P}, \{r\}, \{1, 2\})$.

Pour rappel de l'exemple de la section 1.3.4, de manière générale, dans un jeu de cluedo simplifié, l'action de « regarder la carte sur la table » conduit le joueur à voir soit la carte A, soit la carte B, soit la carte C, suivant la carte effectivement retournée. La modélisation de ce jeu est présentée en figure 1.12.

Les mondes 01 à 06 représentent l'état des connaissances au début du jeu et les mondes 11 à 16 représentent l'état des connaissances après l'événement où le joueur 1 regarde la carte retournée. On peut remarquer que la représentation des actions ne fait pas appel aux modèles d'évènement, une action reliant directement un monde à un autre. Nous avons donc $\delta(w_{01}, r) = w_{11}$, $\delta(w_{02}, r) = w_{14}$, $\delta(w_{03}, r) = w_{13}$, $\delta(w_{04}, r) = w_{16}$, $\delta(w_{05}, r) = w_{15}$, $\delta(w_{06}, r) = w_{12}$.

L'explication des mondes 01 à 06 et des relations a déjà été donnée dans la sous-section 1.3.4. Le monde réel étant le monde $w_{01}$, dans celui-ci le joueur 2 imagine que la carte retournée est soit la carte A, soit la carte C. L'action du joueur 1 de regarder la carte nous amène vers un monde où le joueur 1 sait quelle est la carte retournée, mais où le joueur 2 lui ne le sait pas. Ce fait est représenté par les mondes $w_{11}$, $w_{12}$ et par le lien d'équivalence du joueur 2 qui les relie. Si le monde réel était le monde $w_{06}$, le joueur 2 aurait les mêmes suppositions et l'action de regarder nous amènerait vers le monde $w_{12}$ où le joueur 1 sait quelle est la carte retournée et le joueur 2 hésite entre la carte A et la carte C. Ce résultat est identique à l'exemple de la section 1.3.4 en DEL.

Les mondes 13 à 16 sont issus des mondes 02 à 05. Par exemple si le monde $w_{02}$ était le monde réel, le joueur 2 imaginerait que la carte retournée est soit B, soit A. L'action de regarder nous amènerait donc vers le monde $w_{14}$ où le joueur 1 sait que la carte retournée est B, mais le joueur 2 ne saurait toujours pas si la carte est A ou B.

L'histoire de ce modèle est $h = (w_{01}, r, w_{11})$ : le monde réel initial était le monde $w_{01}$, l'action $r$ a été effectuée et l'on s'est ensuite retrouvé dans le monde $w_{11}$. Ces mondes sont distingués par des
<figure><img src="image_14.png" /><figcaption>FIGURE 1.12 – ESTS du cluedo simplifié</figcaption></figure>

doubles cerclages, ils représentent les mondes réellement atteints dans le jeu. La transition réellement effectuée est elle aussi figurée différemment.

Comme pour l'exemple en DEL, il n'y a bien qu'un seul monde connecté au monde réel après l'action de regarder du joueur 1. En effet, après l'action, les deux joueurs savent que le joueur 1 connaît la carte retournée, mais le joueur 2 ne sait pas si la carte est A ou C.

### 1.4.3 Différences entre modèle DEL et modèle ESTS

Les modèles DEL et ESTS semblent redondants, cependant on notera que les actions ne sont pas décrites dans ESTS, elles ne sont que mentionnées. Cela simplifie la représentation de l'état des connaissances et ne nous empêche pas de raisonner sur ceux-ci. D'un autre côté la modélisation des évènements en DEL nous permet de mieux comprendre les transitions entre les états de connaissances des agents.
Plusieurs modélisations de l'intention ont déjà été faites. Elles ont en commun d'intégrer l'intention comme paramètre de leur logique là où nous aimerions extraire cette intention de l'étude des cas.

## 2.1 Thèse d'asymétrie de Bratman

L'un des travaux de référence sur l'intention est proposé par Michael Bratman, un philosophe américain, dans son livre « Intention, Plans, and Practical reasons » [Bra87].

### 2.1.1 Théorie désir-croyance

Dans ce livre, le propos de Bratman commence par la théorie désir-croyance. Chaque agent ayant un ensemble de désirs contradictoires ou non entre eux, la théorie désir-croyance explique l'action d'un agent comme étant guidée par le désir le plus fort. Cependant l'auteur y montre des limites : son idée est qu'un désir n'est qu'un sentiment là où une intention est un engagement.

Par exemple 5, l'envie d'aller à Boston ne peut expliquer à elle seule le fait que je réserve un taxi pour aller à l'aéroport. L'intention d'y aller implique elle que je conçoive un plan pour m'y rendre, celui-ci expliquant alors pourquoi je choisis d'appeler un taxi. D'un autre côté, il semble acceptable pour un agent d'avoir un ensemble de désirs contradictoires. Par exemple, je désire aller à Boston et faire une croisière jusqu'à Hawaï. A contrario, on ne peut pas à la fois avoir l'intention de prendre l'avion pour Boston demain tout en ayant l'intention de monter sur le bateau demain. Bratman souhaite ainsi montrer le besoin de cohérence des intentions entre elles.

Par la suite, il propose comme exemple 6, celui du débat Mondale-Reagan lors de la présidentielle américaine de 1984. Il simplifie la représentation de ce débat en expliquant que Mondale aura deux actions possibles au milieu du débat, parler du système de défense Star-Wars ou parler de la situation au Moyen-Orient. Il explique que Mondale choisi avant le débat qu'il parlerait du système Star-Wars, que pendant le débat, ses désirs ont changé et qu'il préférerait à présent parler du Moyen-Orient. Cependant, ce désir étant en contradiction avec son intention initiale, il parlera tout de même du système Star-Wars. Par cet exemple, Bratman souhaite montrer d'une part que le désir le plus grand n'explique pas forcément le choix d'un agent et d'autre part que l'intention possède une certaine forme d'inertie.

<footnote n="5">5. Section 1.2 du livre [Bra87]</footnote>

<footnote n="6">6. Section 2.5 du livre [Bra87]</footnote>
2.1.2 Thèse d'asymétrie

Après avoir discuté de la relation qu’il existe entre les désirs et les intentions, Bratman en vient à la relation entre les croyances et les intentions. En partant de l’idée que lorsqu’un agent a l’intention de A alors il doit croire que A sera dans le futur, il fait remarquer que cette règle n’est pas absolue. Il prend l’exemple<fnref n="7" /> d’un homme souhaitant déplacer un arbre couché dans son allée. Celui-ci a l’intention de le déplacer le matin et dans le cas où il n’y arrive pas, d’appeler des professionnels pour le faire l’après-midi. Ainsi même s’il a l’intention de déplacer l’arbre le matin, il n’a pas de certitude quant au fait que l’arbre sera déplacé.

D'un autre côté, Bratman affirme que lorsqu'un agent a l'intention de A alors il ne doit pas croire
que A est impossible. Et c'est ce qu'il appelle la thèse d'asymétrie :

L'intention de faire A fournit normalement à l'agent une raison de croire qu'il va faire A. Mais il n'y a pas besoin d'être irrationnel pour avoir l'intention de faire A et pourtant ne pas croire qu'on le fera. En revanche, il est généralement irrationnel davoir l'intention de faire A en croyant qu'on ne fera pas A. Car il y a une exigence révocable que ses intentions soient en cohérence avec ses croyances. [Bra87, section 3.4.2]<fnref n="8" />

Pour Bratman l'incomplétude entre intention et croyance (le fait d'avoir l'intention de A sans croire que A adviendra) est plus rationnel que l'incohérence entre l'intention et la croyance (le fait d'avoir l'intention de A en croyant A impossible). Il justifie cela en poursuivant l'exemple de l'arbre couché dans l'optique contraire, celle de l'incohérence entre intention et croyance.

Supposons que l’agent ait l’intention de déplacer l’arbre le matin, mais qu’il croit que puisque celui-ci est trop lourd, il ne pourra pas le faire. Il doit donc remplir le reste de son plan pour la journée en conséquence. Il planifie sur la base de ses croyances, y compris sa conviction que (malgré ses efforts) l’arbre sera toujours là l’après midi. Il ajoute donc une intention d’avoir les professionnels pour déplacer l’arbre l’après-midi. Ainsi son plan pour la journée comprend : déplacer l’arbre le matin et demander aux professionnels de déplacer l’arbre l’après-midi. Mais cela peut sembler irrationnel d’avoir l’intention de déplacer l’arbre deux fois.

2.1.3 Effet secondaire

Bratman discute par la suite de ce qu’il appelle des *package deals* (Un ensemble de propriétés venant ensemble). Il affirme alors qu’il semble rationnel d’avoir à la fois l’intention d’obtenir une partie des propriétés sans avoir l’intention d’obtenir l’autre partie. Il prend l’exemple<fnref n="9" /> de militaires devant bombarder un dépôt de munitions dans le but d’affaiblir l’ennemi, sachant que ce bombardement tuera au passage des enfants. Il affirme que ce n’est pas irrationnel pour les militaires de ne pas avoir l’intention de les tuer quand bien même ils ont l’intention de bombarder le dépôt de munitions.

2.1.4 Remarques

Dans son livre, Bratman propose beaucoup d'idées qui n'ont pas été présentées ici. Il parle de la notion de plan et stipule que ceux-ci ont pour briques élémentaires des intentions. Il discute également de révisions d'intention. Celles-ci pouvant avoir lieu tout au long du temps, il cherche à en définir les modalités. Ces développements sont moins pertinents pour cette thèse puisque nous cherchons à déterminer l'intention d'un joueur à un moment précis du jeu après le déroulement de celui-ci.

<footnote n="7">7. section 3.4.2 du livre [Bra87]</footnote>

<footnote n="8">8. traduction faite par l'auteur</footnote>

<footnote n="9">9. section 10.2 du livre [Bra87]</footnote>
## 2.2 Cohen et Levesque

### 2.2.1 Présentation

Cohen et Levesque, dans leur papier « Intention is choice with commitment » (l'intention est un choix avec engagement) [CL90] proposent une modélisation de l'équilibre qu'il y a entre les croyances, les buts, les actions et les intentions d'un agent. Ils s'appuient sur les idées de Bratman.

Cette modélisation se construit sur un mélange entre une logique temporelle et une logique épisté-mique appelée linear-PDL (linear propositional dynamic logic). Elle se base sur 4 principaux opérateurs modaux que sont BEL, GOAL, HAPPENS et DONE. L'opérateur BEL décrit ce qui est cru, l'opérateur GOAL ce qui est cherché, l'opérateur HAPPENS l'événement qui sera exécuté et l'opérateur DONE l'événement qui vient d'être exécuté.

La syntaxe de leur logique est la suivante :

- `<Action - var >::= a, b, ...`

- `<Agent - var >::= x, y, ...`

- `<Regular - var >::= i, j, ...`

- `<Variable >::=< Action - var > | <Agent - var> | <Regular - var >`

- `<Pred - symbol >::= un prédicat p, q,...`

- `<Pred >::= (<Pred - symbol ><Variable >₁,..., <Variable>ₙ)`

- `<Wff >::=< Pred > |¬ <Wff> | <Wff> ∨ <Wff> |∃ <Variable ><Wff> | <Variable >=< Variable > |(<HAPPENS <Action - expression >)|(<DONE <Action - expression >)|(<AGT <Agent - var ><Action - var >)|(<BEL <Agent - var ><Wff>)|(<GOAL <Agent - var ><Wff>)| <time - proposition> | <Action - var >>><Action - var >`

- `<date >::= une date`

- `<Time - proposition >::=< date >`

- `<Action - expression >::=< Action - var > | <Action - expression >; <Action - expression > | <Action - expression > || <Action - expression > | <Wff >?| <Action - expression >*`

Un aperçu de la sémantique est la suivante :

- `<Variable >=< Variable >`

- `(HAPPENS <Actions - expression>) : <Action-expression> se produit juste après`

- `(DONE <Actions - expression>) : <Action-expression> vient juste de se produire`

- `(AGT <Agent - var ><Action - var>) : <Agent-var> est le seul agent de <Action-var>`

- `(BEL <Agent - var ><Wff>) : <Wff> fait partie des croyances de <Agent-var>`

- `(GOAL <Agent - var ><Wff>) : <Wff> fait partie des buts de <Agent-var>`

- `<Action - expression >; <Action - expression > : actions séquentielles`

- `<Action - expression > || <Action - expression > : action à choix non déterministe`

- `<Wff >? : test action`

- `<Action - expression >* : action itérative`
Un modèle $\mathcal{M}$ est un n-uplet $\mathcal{M} = (\Theta, P, E, Agt, T, B, G, \Phi)$. $\Theta$ est un ensemble, $P$ un ensemble d'agents, $E$ un ensemble d'événements élémentaires, $Agt \in [E \to P]$ spécifie l'agent d'un évènement, $T \subseteq [Z \to E]$ est un ensemble de chemins possibles d'événements (ou de mondes) spécifiés comme une fonction des entiers vers les éléments de $E$, $B \subseteq T \times P \times Z \times T$ la relation d'accessibilité des croyances, $G \subseteq T \times P \times Z \times T$ la relation d'accessibilité des buts.

Cohen et Levesque définissent alors $D = \Theta \cup P \cup E^*$ le domaine de quantification (où $E^*$ signifie qu'un ensemble d'évènement peut se produire en chaine). On peut alors quantifier sur les choses, les agents, les séquences d'événements élémentaires. Ainsi $\Phi \subseteq [Pred^k \times T \times Z \times D^k]$. Et ils définissent aussi $AGT \subseteq E^* \times P$, où $x \in AGT[e_1, ..., e_n]$ si, et seulement si, il existe $i$ tel que $x = Agt(e_i)$.

Soit un modèle $\mathcal{M}$, $\sigma$ un ensemble d'évènements, $n$ un entier, $v$ un ensemble d'éléments de $D$ et si $v \in [\text{Var} \to D]$ alors $v_d^x$ est la fonction qui associe $d$ à $x$ et que l'on notera $v$. On va à présent donner la signification de la satisfaction de la formule $\alpha$ par le quadruplet $(M, \sigma, v, n)$ que l'on note $M, \sigma, v, n \models \alpha$. Étant donné que des formules impliquent des actions on note $M, \sigma, v, n[a]m$ lorsque l'expression $a$ est vérifié entre les points de repères $n$ et $m$.

Ainsi la sémantique est alors :

- $M, \sigma, v, n \models P(x_1, ..., x_k)$ si et seulement si $\langle v(x_1), ..., v(x_k) \rangle \in \Phi[P, \sigma, n]$.

- $M, \sigma, v, n \models \neg \alpha$ ssi $M, \sigma, v, n \models \alpha$

- $M, \sigma, v, n \models \alpha \lor \beta$ ssi $M, \sigma, v, n \models \alpha$ ou $M, \sigma, v, n \models \beta$

- $M, \sigma, v, n \models \exists x \alpha$ ssi $\exists d \in D$ tel que $M, \sigma, v_d^x, n \models \alpha$

- $M, \sigma, v, n \models (x_1 = x_2)$ ssi $v(x_1) = v(x_2)$

- $M, \sigma, v, n \models \langle \text{Time-proposition} \rangle$ ssi $v(\langle \text{Time-proposition} \rangle) = n$

- $M, \sigma, v, n \models e_1 \le e_2$ ssi $v(e_1)$ est une sous-séquence initiale de $v(e_2)$ (par exemple lorsque $v(e_1) = a_1 a_2$ et $v(e_2) = a_1 a_2 a_3$)

- $M, \sigma, v, n \models (AGT \ x \ e)$ ssi $AGT[v(e)] = \{v(x)\}$

- $M, \sigma, v, n \models (HAPPENS \ a)$ ssi $\exists m \ge n$ tel que $M, \sigma, v, n[[a]]m$

- $M, \sigma, v, n \models (\text{DONE} \ a)$ ssi $\exists m \le n$ tel que $M, \sigma, v, m[[a]]n$

- $M, \sigma, v, n \models (\text{BEL} \ x \ \alpha)$ ssi $\forall \sigma^* \text{ tel que } \langle \sigma, n > B[v(x)]\sigma^* \text{ on a } M, \sigma^*, v, n \models \alpha$. Au temps $n$, l'agent croit $\alpha$ s'il pense que $\alpha$ est vrai dans tous les mondes accessibles par B.

- $M, \sigma, v, n \models (\text{GOAL} \ x \ \alpha)$ ssi $\forall \sigma^* \text{ tel que } \langle \sigma, n > G[v(x)]\sigma^* \text{ on a } M, \sigma^*, v, n \models \alpha$. Au temps $n$, l'agent a pour but $\alpha$ si $\alpha$ est vrai dans tous les mondes accessibles par G.

- $M, \sigma, v, n[[e]]n + m$ ssi $v(e) = e_1 e_2 ... e_m$ et $\sigma(n + i) = e_i$ pour $i \in [1; m]$

- $M, \sigma, v, n[[a; b]]m$ ssi $\exists k \in [n; m]$ tel que $M, \sigma, v, n[[a]]k$ et $M, \sigma, v, k[[b]]m$

- $M, \sigma, v, n[[\alpha?]]n$ ssi $M, \sigma, v, n \models \alpha$

- $M, \sigma, v, n \models \Diamond \alpha$ ssi $\exists x$ tel que $M, \sigma, v, n \models (HAPPENS \ x; a?)$

- $M, \sigma, v, n \models \Box \alpha$ ssi $M, \sigma, v, n \models \neg \Diamond \alpha$

Cohen et Levesque ajoutent à cela deux contraintes sur les modèles. La première porte sur la nature des relations B et G. La relation B est euclidienne, transitive et sérielle, elle vérifie donc les axiomes KD45. La relation G est simplement sérielle.

La deuxième contrainte porte sur le lien entre les relations B et G. Formellement $\forall \sigma, \sigma^*$ si $\langle \sigma, n > G[p]\sigma^*$ alors $\langle \sigma, n > B[p]\sigma^* \text{, en d'autres termes } G \subseteq B$. Cela signifie simplement que les buts d'un agent sont forcément crus possibles. L'agent ne peut avoir un objectif qu'il considère impossible. C'est ce que Cohen et Levesque appellent la contrainte de réalisme.
### 2.2.2 Propriétés

Quelques propriétés des opérateurs BEL et GOAL sont montrées :

$$ \begin{align*} & \models (\mathit{BEL} \alpha \phi) \rightarrow (\mathit{GOAL} \alpha \phi) \\ & \models ((\mathit{GOAL} \alpha \phi) \land (\mathit{BEL} \alpha \phi \rightarrow \psi)) \rightarrow (\mathit{GOAL} \alpha \psi) \end{align*} $$

La première propriété signifie simplement que lorsqu'un agent $\alpha$ croit que $\phi$ sera toujours vraie alors $\phi$ fait obligatoirement partie des buts de l'agent. La deuxième propriété traite les effets secondaires : si obtenir $\phi$ fait partie de mes buts et qu'avoir $\phi$ implique d'avoir $\psi$ alors $\psi$ fait aussi partie de mes buts.

La modélisation de l'intention se base en grande partie sur l'opérateur GOAL. Plus précisément sur une version modifiée appelée P-GOAL pour « Persistant GOAL » (but persistant). Cet opérateur P-GOAL cherche à décrire les objectifs qui seront poursuivis tant que ceux-ci ne sont pas atteints ou qu'ils sont considérés comme inatteignables. Une des principales différences avec l'opérateur GOAL est que lorsqu'on a déjà une propriété $\phi$ alors celle-ci peut être un but, mais ne peut pas être un but persistant, puisque, par définition, un but persistant s'arrête lorsqu'on atteint notre objectif.

La définition formelle de l'intention selon Cohen et Levesque est la suivante :

$$ (\mathit{INTEND} x a) = (P - \mathit{GOAL} x [\mathit{DONE} x (\mathit{BEL} x (\mathit{HAPPENS} a))?; a]) $$

L'explication formelle obligerait de présenter leur papier dans son entièreté. De manière plus légère, Cohen et Levesque définissent l'intention d'obtenir $\phi$ par un agent $\alpha$ comme le but persistant de se retrouver dans un monde dans lequel l'agent pense pouvoir effectuer l'action amenant $\phi$.

Un des résultats les plus intéressants est la propriété sur les effets secondaires :

$$ \models((\mathit{INTEND} \alpha \phi) \land (\mathit{BEL} \alpha \Box(\phi \rightarrow \psi))) \rightarrow (\mathit{INTEND} \alpha \psi) $$

L'opérateur $\Box$ signifie que la formule $\phi \rightarrow \psi$ est maintenant vrai lors du reste du cours des évènements.

Cette propriété stipule que même si l'on a l'intention d'avoir $\phi$ et que l'on croit que $\phi$ implique $\psi$ on n'a pas obligatoirement l'intention d'obtenir $\psi$. Ce résultat était déjà présent dans le livre de Bratman. Pour le justifier les auteurs proposent l'exemple d'un homme qui a une rage de dent et qui se rend chez le dentiste afin de se faire soigner. Cet homme pense que l'opération va lui faire subir une douleur atroce. Il a l'intention d'être guéri sans pour autant avoir l'intention d'avoir mal.

## 2.3 Rao et Georgeff et la logique BDI

Rao et Georgeff dans leur papier « Decision procedures for BDI logics » (Procédures de décision pour les logiques BDI) [RG98] proposent eux aussi un formalisme pour la théorie *Belief, Desire, Intention* (croyance, désir, intention) du philosophe Michael Bratman [Bra87].

### 2.3.1 Présentation

La logique proposée par Rao et Georgeff se base sur CTL (Computation Tree Logic) une logique dite de *branching-time* (logique temporelle à ramification) à laquelle ils ajoutent les opérateurs BEL, DES, INTEND pour les croyances, le désir et l'intention.

Dans cette logique, un modèle est composé d'un ensemble de mondes divisés suivant leur instant temporel. Chaque monde à l'instant $t$ possède un seul monde précédent à l'instant $t-1$ et un ou plusieurs mondes suivants à l'instant $t+1$.
Rao et Georgeff distinguent deux types de formules, les formules états et les formules chemins. Les formules états sont vérifiées (ou non) par un monde dans un état donné. Les formules chemins sont quant à elles vérifiées par un chemin d'instants d'un monde :

— (S1) chaque proposition *p* est une formule état

— (S2) si $\phi$ et $\psi$ sont des formules états alors $\neg\phi$ et $\phi \land \psi$ sont des formules états.

— (S3) si $\phi$ est une formule chemin alors $A\phi$ et $E\phi$ sont des formules états.

— (S4) si $\phi$ est une formule état alors $BEL(\phi)$, $DES(\phi)$, $INTEND(\phi)$ sont des formules états

— (P1) chaque formule état est aussi une formule chemin

— (P2) si $\phi$ et $\psi$ sont des formules chemins alors $\neg\phi$ et $\phi \land \psi$ sont des formules chemins.

— (P3) si $\phi$ et $\psi$ sont des formules chemins alors $X\phi$ et $\phi U \psi$ sont des formules chemins.

L'opérateur $A$ représente « il est inévitable », $E$ pour « il est possible », $X$ pour « juste après » et $U$ pour « jusqu'à ».

Comme déjà mentionné, un modèle de cette logique est composé d'un ensemble de mondes $W$, qui est lui-même décomposé en sous-ensembles, chaque sous-ensemble $S_w$ représentant tous les états d'un même monde $w \in W$. On note $R$ la relation qui associe à chaque état d'un monde, l'état suivant. La fonction de valuation qui associe à chaque triplet (proposition, monde, état)=(p,w,s) une valeur $\{vrai, faux\}$ est notée $L$. Enfin on note $B, D, I$ les relations binaires sur $W \times S \times W$, où $S$ est l'ensemble des états, qui servent à représenter les croyances, les désirs et l'intention. Ces relations ne lient que des mondes dans le même état. Un modèle $M$ est alors le n-uplet $M = (W, \{S_w, w \in W\}, \{R_w, w \in W\}, L, B, D, I)$. On note $(w_{s0}, w_{s1}, ...)$ un chemin d'instants d'un monde $w$.

La sémantique de cette logique pour les formules états est alors la suivante :

— $M, w_s \models \phi$ si et seulement si $L(\phi, w, s) = true$

— $M, w_s \models \neg\phi$ si et seulement si $M, w_s \not\models \phi$

— $M, w_s \models \phi \land \psi$ si et seulement si $M, w_s \models \phi$ et $M, w_s \models \psi$

— $M, w_{s0} \models E\phi$ si et seulement s'il existe un chemin $(w_{s0}, w_{s1}, ...)$ tel que $M, (w_{s1}, ...) \models \phi$

— $M, w_{s0} \models A\phi$ si et seulement si pour tous les chemins $(w_{s0}, w_{s1}, ...)$ on a $M, (w_{s1}, ...) \models \phi$

— $M, w_s \models BEL(\phi)$ si et seulement si $\forall v \in W$ tel que $(w, s, v) \in B$ on a $M, v_s \models \phi$

— $M, w_s \models DES(\phi)$ si et seulement si $\forall v \in W$ tel que $(w, s, v) \in D$ on a $M, v_s \models \phi$

— $M, w_s \models INTEND(\phi)$ si et seulement si $\forall v \in W$ tel que $(w, s, v) \in I$ on a $M, v_s \models \phi$

La sémantique pour les formules chemins est la suivante :

— $M, (w_{s0}, w_{s1}, ...)$ $\models \phi$ si et seulement si $M, w_{s0} \models \phi$

— $M, (w_{s0}, w_{s1}, ...)$ $\models \neg\Phi$ si et seulement si $M, w_{s0} \models\neg\Phi$

— $M, (w_{s0}, w_{s1}, ...)$ $\models \Phi \land \Psi$ si et seulement si $M, (w_{s0}, w_{s1}, ...)$ $\models \Phi$ et $M, (w_{s0}, w_{s1}, ...)$ $\models \Psi$

— $M, (w_{s0}, w_{s1}, ...)$ $\models X\Phi$ si et seulement si $M, w_{s1} \models \Phi$

— $M, (w_{s0}, w_{s1}, ...)$ $\models \Phi U \Psi$ si et seulement si :

— il existe $k \ge 0$ tel que $M, (w_{sk}, ...)$ $\models \Psi$ et $\forall j \in [0; k]$ on a $M, (w_{sj}, ...)$ $\models \Phi$

— ou si $\forall j \ge 0$ on a $M, (w_{sj}, ...)$ $\models \Phi$
## 2.3.2 Axiomes

Rao et Georgeff proposent différents ensembles de contraintes pour leur logique. Le premier ensemble qu'ils appellent BDI-B1, impose que les relations B,D,I respectent l'axiome K. Pour rappel l'axiome K est le suivant (en utilisant l'opérateur BEL comme exemple) :

— Axiome K : $(BEL(\phi) \land BEL(\phi \rightarrow \psi)) \rightarrow BEL(\psi)$

Le deuxième ensemble de contraintes qu'ils appellent BDI-B2 impose que la relation B vérifie les axiomes K, D, 4, 5 et que les relations D et I vérifient les axiomes K et D. L'axiome D exprime la cohérence des opérateurs. Les axiomes 4 et 5, pour l'opérateur BEL ci-dessous, représentent l'introspection positive et négative d'un agent envers ses croyances. Pour rappel les axiomes D, 4, 5 sont les suivants (en utilisant l'opérateur BEL comme exemple) :

— Axiome D : $BEL(\phi) \rightarrow \neg BEL(\neg \phi)$

— Axiome 4 : $BEL(\phi) \rightarrow BEL(BEL(\phi))$

— Axiome 5 : $\neg BEL(\phi) \rightarrow BEL(\neg BEL(\phi))$

Le troisième ensemble de contraintes que Rao et Georgeff appellent BDI-S3, la contrainte de réalisme forte, reprend les contraintes BDI-B2 et impose en plus que les intentions fassent partie des désirs et que les désirs fassent partie des mondes possibles. Un agent qui a l'intention de quelque chose en a alors forcément le désir et ce qu'il désire fait forcément partie de ce qu'il croit possible. Cela représente un agent ultra-prudent. Les axiomes vérifiés sont les suivants :

— Axiome ID-SA : $INTEND(\phi) \rightarrow DES(\phi)$

— Axiome DB-SA : $DES(\phi) \rightarrow BEL(\phi)$

Le quatrième ensemble est appelé BDI-R3, contrainte de réalisme et reprend les contraintes BDI-B2. À l'inverse de la logique BDI-S3, ce qui est possible fait partie des désirs, et ce qui est désiré fait partie des intentions. Un agent désire tout ce qui est possible et a l'intention de tout ce qu'il désire. Cela représente un agent ultra-enthousiaste. Les axiomes vérifiés sont les suivants :

— Axiome ID-RA : $DES(\phi) \rightarrow INTEND(\phi)$

— Axiome DB-RA : $BEL(\phi) \rightarrow DES(\phi)$

Enfin le cinquième ensemble est appelé BDI-W3, contrainte de réalisme faible, et reprend les contraintes BDI-B2. Dans cette logique, un agent n'a pas l'intention de ce qu'il ne désire pas, il n'a pas l'intention de ce qu'il croit impossible et ne désire pas ce qu'il pense impossible. Cela représente un agent qui serait ni trop prudent, ni trop enthousiaste. Les axiomes vérifiés sont les suivants :

— Axiome ID-WA : $INTEND(\phi) \rightarrow \neg DES(\neg \phi)$

— Axiome ID-WA : $INTEND(\phi) \rightarrow \neg BEL(\neg \phi)$

— Axiome ID-WA : $DES(\phi) \rightarrow \neg BEL(\neg \phi)$

## 2.3.3 Thèse d'asymétrie

Dans leur travail, Rao et Georgeff reprennent la thèse d'asymétrie de Bratman et l'étendent. Pour rappel, la thèse d'asymétrie de Bratman est la suivante :

— AT1 : $\models INTEND(\phi) \rightarrow \neg BEL(\neg \phi)$

— AT2 : $\models INTEND(\phi) \rightarrow BEL(\phi)$
La propriété AT1 est appelée intention-croyance cohérence et stipule qu’un agent ne peut pas avoir l’intention de quelque chose tout en croyant que cela n’arrivera pas. La propriété AT2 est l’incomplétude intention-croyance et désigne le fait qu’un agent peut tout à fait avoir l’intention de quelque chose sans croire que cela arrivera.

Rao et Georgeff étendent une première fois la thèse d'asymétrie avec l'incomplétude croyance-intention, c'est-à-dire le fait de croire que quelque chose arrivera sans en avoir l'intention.

— AT3 : $\Vdash BEL(\phi) \rightarrow INTEND(\phi)$

Ils proposent ensuite d'autres extensions de la thèse d'asymétrie en demandant à ce que l'intention et le désir, mais aussi le désir et les croyances vérifient les propriétés analogues de cohérence et d'incomplétude :

— AT4 : $\models INTEND(\phi) \rightarrow \neg DES(\neg \phi)$

— AT5 : $\Vdash INTEND(\phi) \rightarrow DES(\phi)$

— AT6 : $\Vdash DES(\phi) \rightarrow INTEND(\phi)$

— AT7 : $\models DES(\phi) \rightarrow \neg BEL(\neg \phi)$

— AT8 : $\Vdash DES(\phi) \rightarrow BEL(\phi)$

— AT9 : $\Vdash BEL(\phi) \rightarrow DES(\phi)$

La quatrième propriété stipule qu’un agent ne peut avoir l’intention de ce qu’il ne désire pas. La cinquième indique qu’avoir l’intention de $\phi$ n’implique pas que l’on désire $\phi$ et la sixième dit que désirer $\phi$ n’implique pas que l’on ait l’intention de $\phi$.

La septième propriété stipule qu’un agent ne peut pas désirer ce qu’il pense être impossible. La huitième indique que désirer $\phi$ n’implique pas que l’on croit que $\phi$ sera vraie. Et la neuvième propriété dit que croire que $\phi$ est vrai n’implique pas que l’on désire $\phi$.

Les cinq logiques que Rao et Georgeff proposent vérifient alors des propriétés différentes :

— BDI-B1 : AT2, AT3, AT5, AT6, AT7, AT8

— BDI-B2 : AT2, AT3, AT5, AT6, AT7, AT8

— BDI-S3 : AT1, AT3, AT4, AT5, AT6, AT7

— BDI-R3 : AT1, AT2, AT4, AT5, AT7, AT8

— BDI-W3 : de AT1 à AT9

### 2.3.4 Effet secondaire

Rao et Georgeff analysent également le problème de l’effet secondaire également appelé « consequential-closure problème » (fermeture conséquentielle). Le problème de l’effet secondaire demande à ne pas reconnaître comme intentionnel l’effet secondaire d’une action qui, elle, est intentionnelle. Ici cela prend la forme :

— CC1 : $M, w_s \models INTEND(\phi) \wedge BEL(\phi \rightarrow \psi) \wedge \neg INTEND(\psi)$

À nouveau, ils étendent le principe de « consequential closure » aux relations intention-désir et désir-croyance. Cela prend la forme :

— CC4 : $M, w_s \models INTEND(\phi) \wedge DES(\phi \rightarrow \psi) \wedge \neg INTEND(\psi)$

— CC7 : $M, w_s \models DES(\phi) \wedge BEL(\phi \rightarrow \psi) \wedge \neg DES(\psi)$

Ils montrent ensuite que quatre de leurs logiques vérifient ces trois propriétés : les logiques B1, B2, S3 et W3. La logique BDI-R3, elle, ne vérifie aucune de ces trois propriétés.

En plus de définir cinq logiques différentes, d'étendre la thèse d'asymétrie et l'effet secondaire, Rao et Georgeff proposent avant tout une axiomatisation et démontrent la complétude de leurs logique.
## 2.4 Idée de Shoham

### 2.4.1 Présentation

Shoham dans son papier « Logical Theories of Intention and the Database Perspective » (Théorie logique de l'intention et perspectives sur les bases de données) [Sho09] ne propose pas de formalisme, mais donne des idées afin de construire une base de données des croyances et connaissances d'un agent qui resterait cohérente tout au long du temps. Par cette notion de cohérence, il entend par exemple, qu'un agent ne peut pas à la fois avoir l'intention d'entreprendre une action tout en pensant que toutes les conditions requises pour l'entreprendre ne sont pas réunies.

Shoham propose notamment les conditions suivantes pour la base de données :

- les croyances doivent être cohérente entre elles;

- les intentions doivent être cohérente entre elles :

- l'agent ne peut pas avoir l'intention de plus d'une action par étape;

- si l'agent a l'intention d'effectuer deux actions l'une après l'autre, les préconditions de la deuxième doivent être vérifiées par les postconditions de la première.

- les intentions doivent être en cohérence avec les croyances :

- si l'agent a l'intention d'entreprendre une action, il ne peut pas croire que ses préconditions ne sont pas réunies;

- si l'agent a l'intention d'entreprendre une action, il croit que ses postconditions seront vérifiées après l'action.

L'article de Shoham s'articule notamment autour de la révision des croyances et des intentions lorsqu'on ajoute ou soustrait une croyance ou une intention. Il propose l'algorithme suivant :

- Lorsqu'on ajoute une croyance $\phi_t$ (la croyance que $\phi$ sera vraie à l'instant $t$) :

- Ajouter la croyance $\phi$ à la base de données des croyances;

- Si besoin, restaurer la cohérence de la base de données des croyances avec la théorie des révisions de croyances souhaitée;

- Si besoin, retirer l'intention d'une action $a_t$ si la précondition de cette action n'est plus vérifiée.

- Lorsqu'on soustrait une croyance $\phi_t$ :

- Contracter (au sens de la théorie des révisions de croyances) les croyances par $\phi_t$;

- Si besoin, retirer les intentions d'actions si celle-ci entraînent $\phi_t$ dans leurs postconditions.

- Lorsqu'on souhaite ajouter l'intention $a_t$ (l'intention de faire l'action $a$ à l'instant $t$) :

- Ajouter $a_t$ à la base de données des intentions;

- S'il y a une intention $b_t$ et que $b \neq a$, retirer $b$;

- Ajouter la postcondition de $a_t$ annotée par $a_t$ dans la base de données des croyances;

- Contracter la base de données des croyances par la négation de la précondition de $a_t$.

- Lorsqu'on souhaite soustraire une intention $a_t$ :

- Supprimer l'intention $a_t$ de la base de données des intentions;

- Supprimer les croyances annotées par $a_t$ dans la base de données des croyances.
Shoham exprime ainsi l'idée que les croyances et les intentions doivent être cohérentes. Son algo-
rithme vérifie également la cohérence intention-croyance ($I(\phi) \rightarrow \neg B(\neg \phi)$). Cependant, contrairement
à la thèse d'asymétrie de Bratman, il demande à ce que la base de données vérifie la complétude intention-
croyance ($I(\phi) \rightarrow B(\phi)$), c'est-à-dire que lorsqu'on a l'intention de A, on doit croire que A adviendra.

Le problème de l’effet secondaire ne se pose pas ici car pour Shoham, l’agent n’a pas l’intention d’obtenir un résultat, il a l’intention d’exécuter une action.

2.4.2 Logique

Shoham propose une logique afin de satisfaire les postulats qu’il a proposés dans un article « Joint
revision of belief and intention » (révision jointe de la croyance et de l’intention)[IPS10] qu’il a écrit avec
T.Icard et E.Pacuit. Ses co-auteurs ont approfondi leur logique dans une autre publication « Intention as
commitment toward time » (l’intention comme engagement dans le temps) [vDv+20].

La logique proposée est composée d'un ensemble Z représentant les instants t, un ensemble de propositions Prop = {p, q, r, ...} et un ensemble fini d'actions déterministes élémentaires Act = {a, b, c, ...}.
À chaque action a à chaque temps t, on associe une précondition pre(a)_t et une postcondition post(a)_{t+1}.

Ils définissent un ensemble $\mathbf{P} = P(\mathbf{Prop} \cup \{\mathbf{pre}(a), \mathbf{post}(a)|a \in \mathbf{Act}\})$ afin de pouvoir définir
ce qu'ils appellent des chemins $\pi$, des fonctions de $\mathbf{Z}$ vers $\mathbf{P} \times \mathbf{Act}$. Ces chemins associent donc à
chaque temps $t$, un ensemble de propositions vraies ainsi qu'une action qui correspond à l'action qui
sera exécutée entre le temps $t$ et le temps $t + 1$. En notant $\pi_1$ la projection gauche et $\pi_2$ la projection
droite, ils nomment *chemin approprié* tout chemin $\pi$ qui vérifie : si $\pi(t)_2 = a$ alors $\mathbf{post}(a) \in \pi(t+1)_1$.

Ils définissent ensuite une relation d'équivalence $R_t$ telle que $\pi R_t \pi'$ si et seulement si $\forall t' \le t, \pi(t') = \pi'(t')$. Enfin ils définissent les ensembles de chemins appropriés $\Pi$ comme des ensembles de chemins appropriés vérifiant : si $\mathbf{pre}(a) \in \pi(t)_1$ alors $\exists \pi' \in \Pi$ tel que $\pi R_t \pi'$ et $\pi'(t) = a$.

La syntaxe de la logique est alors la suivante :

$$
\phi ::= p_t | \mathit{pre}(a)_t | \mathit{post}(a)_t | \mathit{Do}(a)_t | \neg \phi | \phi \wedge \phi | \Box \phi
$$

La sémantique est :

— Π, π, t | α<sub>t</sub> si et seulement si α ∈ π(t)<sub>1</sub>, où α ≡ p, pre(a), post(a)

— Π, π, t | Do(a)<sub>t</sub> si et seulement si ∃t' tel que π(t')<sub>2</sub> = a

— Π, π, t | □φ si et seulement si ∀π' ∈ Π si πR<sub>t</sub>π' alors Π, π', t | φ

— Π, π, t | φ ∧ ψ si et seulement si Π, π, t | φ et Π, π, t | ψ

— Π, π, t | ¬φ si et seulement si Π, π, t | ψ

Ils définissent ensuite un ensemble de contraintes que doivent vérifier les ensembles Π :

— les tautologies

— la relation *R* doit vérifier les contraintes du système S5 : euclidiannité et réflexivité.

— $\bigvee_{a \in \mathbf{Act}} \mathbf{Do}(a)_t$, à chaque instant, au moins une action est réalisée dans le chemin

— $Do(a)_t \rightarrow \bigwedge_{b \neq a} Do(b)_t$, à chaque instant, pas plus d'une action est réalisée dans le chemin

— $Do(a)_t \rightarrow post(a)_{t+1}$, condition des chemins appropriés

— pre(a)_t → ¬□¬Do(a), condition des ensembles de chemins appropriés

— Modus Ponens
## 2.5 Idée de Roy

Roy dans son papier « A dynamic-epistemic hybrid logic for intentions and information changes in strategic games » (Une logique hybride dynamique/épistémique pour l'évolution des intentions et des informations dans les jeux stratégiques) [Roy09] propose un formalisme basé sur les opérateurs KNOW et INTEND. L'opérateur KNOW étant la version connaissance de l'opérateur BEL pour la croyance. Pour rappel, les connaissances sont des croyances qui sont vraies. L'opérateur BEL n'étant pas nécessaire pour étudier les jeux en général.

Roy étudie en grande partie les effets des modifications des connaissances et des intentions sur les stratégies des joueurs. La stratégie est un terme de la théorie des jeux et définit l'enchaînement des actions qu'effectuera un joueur jusqu'à la fin du jeu.

La plupart de ses résultats portent donc sur les stratégies. Cependant Roy amène tout de même quelques propriétés sur l'intention :

— $\models \phi \rightarrow \mathit{INTEND} \phi$ (nécessitation)

— $\models \mathit{INTEND}(\phi \rightarrow \psi) \rightarrow (\mathit{INTEND} \phi \rightarrow \mathit{INTEND} \psi)$ (axiome K)

— $\models \mathit{INTEND} \phi \rightarrow \neg \mathit{INTEND} \neg \phi$ (sérialité)

— $\models \mathit{INTEND} \phi \rightarrow \mathit{KNOW} (\mathit{INTEND} \phi)$ (interaction)

La première propriété dite de nécessitation indique qu'on a l'intention de tout ce qui sera vrai. Cette propriété est en désaccord avec la thèse d'asymétrie de Bratman. Avec l'axiome K en plus, dit règle de distribution, l'opérateur INTEND devient « normal » au sens logique.

La propriété de sérialité stipule qu'on ne peut pas avoir l'intention d'une chose et de son contraire. Et enfin la propriété d'interaction nous dit qu'un agent connaît ses intentions.

## 2.6 Conclusion

L'idée partagée par l'ensemble de ces travaux est que l'intention correspond à un engagement, dans le sens où il va contraindre d'une part les actions qui seront réalisées, mais aussi les croyances ou connaissances que l'on aura dans le futur. Il y a donc un lien certain entre les croyances des agents et leurs intentions. La thèse d'asymétrie de Bratman résume ce lien. Un agent ne peut pas avoir l'intention de A tout en croyant que A n'arrivera pas, c'est ce qu'on appelle la cohérence intention-croyance. Cette propriété semble centrale dans la théorie de l'intention. L'autre propriété de la thèse d'asymétrie, l'incomplétude intention-croyance, le fait d'avoir l'intention de A sans croire que A arrivera, est elle aussi importante sans toutefois être partagée par toutes les logiques proposées. Également, la non-intentionnalité des effets secondaires est une propriété pertinente qu'il faut chercher à acquérir.

Le lien profond entre intention et croyance nous conforte donc dans l'idée d'extraire l'intention à partir de la croyance des agents. Et c'est ici toute la différence entre ces travaux et cette thèse. En effet, dans l'ensemble des travaux proposés, l'intention est donnée, c'est un paramètre d'entrée. Dans cette thèse, l'objectif est d'arriver à l'intention des agents en n'ayant accès qu'à leurs connaissances, les connaissances étant une sous-famille des croyances, suffisante pour l'étude des jeux. L'enjeu sera alors de vérifier si cette intention ainsi extraite vérifie les propriétés que l'on attend d'elle.
# Deuxième partie

## Modélisation de l'intention
3

Première modélisation

L'objectif de notre travail est de déterminer *a posteriori* les intentions qu'un joueur a eues au cours d'une partie. En d'autres termes, nous souhaitons expliquer les actions effectuées par un joueur pendant le déroulement du jeu. En effet, nous partons de l'hypothèse que le jeu est trop difficile pour que le joueur soit en capacité de calculer la stratégie optimale pour gagner. On ajoute une autre hypothèse, celle que le joueur se fixe alors des objectifs à plus court terme tout au long de la partie, lui permettant étape par étape de chercher à obtenir le score maximal.

Notre idée se base sur le principe suivant : *par rapport à tous les résultats potentiels imaginés par le joueur, a-t-il effectué l'action qui le menait vers le meilleur résultat espéré?*. Nous allons expliquer cette idée plus en détail.

**3.1 Présentation**

**3.1.1 Premier principe**

Prenons l'exemple d'une personne qui souhaite se désaltérer. Il y a deux choix qui s'offrent à elle : aller dans la cuisine où il y a du café ou aller à la cafétéria où il n'y pas de café mais du thé. Elle n'a le temps d'aller qu'à l'un ou l'autre mais pas aux deux. Si la personne va dans la cuisine on dira qu'elle avait l'intention de boire du café. Si elle va à la cafétéria, on pourra dire qu'elle n'a pas l'intention de boire du café et même qu'elle avait l'intention de ne pas boire du café.

Recommençons l'exemple mais cette fois-ci, il y a trois choix. Le premier choix est d'aller dans la cuisine, où il y a habituellement 1 fois sur 4 du café. Le deuxième choix est d'aller dans la cafétéria où il y a 2 fois sur 4 du café. Et enfin le troisième choix est d'aller dans la salle de repos où il y a 3 fois sur 4 du café. On dira alors que la personne avait l'intention de boire du café si elle va à la salle de repos et qu'elle avait l'intention de ne pas boire du café si elle va dans la cuisine. Cependant si la personne va à la cafétéria, on pourra simplement dire qu'elle n'avait ni l'intention de boire du café, ni l'intention de ne pas en boire.

Supposons maintenant que dans toutes les pièces il y ait du café, dans ce cas, on ne pourra pas dire si la personne avait l'intention de boire du café ou l'intention de ne pas en boire. En effet, lorsque toutes les actions disponibles amènent au même résultat, on ne peut pas déduire l'intention de l'agent, puisqu'il n'a aucun impact sur ce qu'il arrive.

**3.1.2 Deuxième principe**

Continuons l'exemple de la personne cherchant à se désaltérer. Habituellement il y a toujours du café dans la cuisine et 1 fois sur 3 à la cafétéria. Cependant, la personne a appris que durant une moitié de
la journée il n'y aura pas d'eau dans la cuisine mais ne sait pas si cela sera le matin ou l'après-midi. Nous sommes le matin, la personne imagine donc deux mondes possibles indistinguishables : le monde où l'eau est actuellement coupée et le monde où l'eau n'est pas encore coupée. Dans cet exemple, l'action d'aller dans la cuisine lui permet de boire du café dans 1 cas sur 2 qu'elle imagine. L'action d'aller à la cafétéria lui permet de boire du café dans 1 cas sur 3. On dira donc que la personne avait l'intention de boire du café si elle a décidé d'aller dans la cuisine et qu'elle avait l'intention de ne pas en boire si elle a décidé d'aller dans la cafétéria. À la différence du premier principe où nous n'avions qu'une incertitude sur l'effet de l'action, nous avons ici une incertitude sur le monde réel.

### 3.1.3 Troisième principe

L'exemple va cette fois-ci faire intervenir d'autres personnes, il va donc se complexifier davantage. La personne est accompagnée de son collègue, ils peuvent soit aller dans la cuisine où suivant le nombre de personnes déjà passées, il reste 1, 2 ou 3 cafés (quelqu'un finissant le café doit en préparer pour les suivants), soit aller dans la cafétéria où il y a une machine automatique mais fonctionnant une fois sur 3. Le collègue se servira en premier et prendra 1 ou 2 cafés qu'ils aillent dans la cuisine ou à la cafétéria.

À la cafétéria, peu importe le comportement du collègue, la personne aura du café dans 1 cas sur 3.

À la cuisine, cela est différent. S'il reste un café, le collègue le prend et il n'en reste plus pour la personne. S'il en reste deux, il y a une chance sur deux qu'il en reste un après que le collègue se soit servi. S'il en reste trois, la personne peut boire du café. Dans la cuisine, la personne aura donc son café dans 1 cas sur 2.

Dans cet exemple, on dira que la personne avait l'intention de boire du café si elle va dans la cuisine, et qu'elle avait l'intention de ne pas en boire si elle va à la cafétéria.

Dans ce troisième principe, nous avons à la fois une incertitude sur l'effet des actions mais aussi sur le monde réel.

## 3.2 Définitions

Afin de pouvoir modéliser ces principes au sein de la logique épistémique dynamique, nous allons devoir l'adapter. En effet, il apparaît clairement que les actions et la connaissance de l'auteur des actions ont des places importantes dans la modélisation. Ceci n'est initialement pas pris en compte par la logique épistémique dynamique. En effet les transitions que représentent les actions ne sont ni associées à un agent, ni associées à une possibilité ou non de les effectuer, associations qui sont naturellement présentes dans la description d'un jeu.

Pour rappel, un jeu est symbolisé par sa signature, c'est-à-dire un triplet $J = (\mathbb{P}, A, N)$. Dans les modèles épistémiques présentés en section 1.4, l'association de l'agent $\alpha$ et de sa relation d'accessibilité $R_\alpha$ est sous-entendue. La notion d'agent devient ici plus importante, puisqu'elle n'est plus seulement caractéristique des relations d'accessibilité entre les mondes mais également des actions possibles. En effet, dans la présentation de la logique épistémique dynamique, la notion d'agent apparaît uniquement pour donner une signification aux différentes relations d'accessibilité. Il n'était pas utile de préciser la relation qui se rapportait à un agent en particulier, les raisonnements sur la relation suffisaient. Ce que nous allons faire ici est d'associer à la fois un agent à sa relation et aux actions qu'il va entreprendre. Il est donc important de construire un système possédant un lien entre l'ensemble des agents, l'ensemble des relations et l'ensemble des actions. On va donc définir deux fonctions d'associations, la première, $f_r$ appelée *fonction d'association des relations* et la deuxième, $f_\alpha$ dite *fonction d'association des actions*. Une action attachée à un agent portera alors le nom *d'action atomique*.
**Définition 11 (fonctions d'associations)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, soit $W$ un ensemble de mondes, soit $R$ un ensemble de relations binaires sur $W$ tel que $|N| = |R|$, soit $\pi$ une fonction de $\mathbb{P}$ vers $2^W$ appelée fonction de valuation.

On appelle $f_r$ fonction d'association des relations toute fonction bijective de $N$ vers $R$ et $f_a$ fonction d'association des actions toute fonction de $N$ vers $2^A$. On note $R_\alpha$ la relation $f_r(\alpha)$ et $A_\alpha$ l'ensemble $f_a(\alpha)$ des actions atomiques de l'agent $\alpha$.

**Définition 12 (modèle épistémique)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, soit $W$ un ensemble de mondes, soit $R$ un ensemble de relations binaires sur $W$ tel que $|N| = |R|$, soit $\pi$ une fonction de $\mathbb{P}$ vers $2^W$ appelée fonction de valuation, soit $f_r$ une fonction d'association des relations et $f_a$ une fonction d'association des actions, on définit un modèle épistémique comme le 5-uplet $M = (W, R, \pi, f_r, f_a)$.

De plus on appelle $(M, w_0)$ (ou $M^{w_0}$) le modèle épistémique pointé où le monde $w_0 \in W$ est le monde réel.

Dans le calcul de l'intention, la prise en compte des mondes possibles est aussi un élément clé. Cependant un modèle épistémique représente plus que les mondes indistinguishables du monde réel, il représente aussi les connaissances des autres agents et de manière générale les connaissances sur les connaissances. On va donc définir comme $[w]_\alpha$ l'ensemble des mondes indistinguishables du monde $w$ pour l'agent $\alpha$, c'est-à-dire l'ensemble des mondes $w_i$ reliés au monde $w$ par la relation $R_\alpha$.

**Définition 13 (mondes indistinguishables)** Soit un modèle $M = (W, R, \pi, f_r, f_a)$, on définit $[w]_\alpha$ l'ensemble des mondes indistinguishables du monde $w$ par $[w]_\alpha = \{w_i \in W \text{ tel que } wR_\alpha w_i\}$

Les mondes imaginés par l'agent, ceux liés au monde réel, sont considérés comme indistinguishables du monde réel. Car pour rappel, les relations dans le système S5 sont des relations d'équivalences. De plus ce système ne permet pas de représenter en l'état des mondes qui seraient plus probables que d'autres. En d'autres termes, pour l'agent, l'ensemble des mondes indistinguishables du monde réel sont considérés comme équiprobables. Nous allons ainsi traiter la possibilité pour l'agent d'obtenir une propriété comme une probabilité parmi les mondes qu'il imagine. Nous allons donc définir le rapport de présence d'une propriété parmi les mondes imaginés.

**Définition 14 (rapport de présence)** Soit un modèle $M^w = (W, R, \pi, f_r, f_a)$, soit $\phi$ une formule du langage, on définit $\text{pr}_{M^w}^\alpha(\phi)$ le rapport de présence de la propriété $\phi$ comme le réel suivant :

$$ \text{pr}_{M^w}^{\alpha}(\phi) = \frac{|\{w_i \in [w]_{\alpha} \text{ tel que } \models_{w_i}^{M} \phi\}|}{|[w]_{\alpha}|} $$

À présent, il nous faut nous occuper des actions. Il existe deux types de jeux : les jeux simultanés et les jeux au tour par tour. On parle de jeu simultané lorsque tous les joueurs effectuent une action à chaque tour et de jeu au tour par tour lorsque il n'y a qu'un joueur qui effectue une action à chaque tour. Dans les faits, les jeux au tour par tour sont une sous-famille des jeux simultanés. Un jeu au tour par tour est un jeu simultané où les autres joueurs effectuent l'action de ne rien faire (noop no-operation) lors du tour du joueur. Modéliser les actions dans les jeux simultanés nous permet donc de modéliser tous les jeux.

Cependant, étant donné qu'une action complète est l'association de toutes les actions atomiques des agents effectuées simultanément, il nous faut traiter la fusion d'actions. En effet, chaque action possède une précondition ainsi qu'une postcondition, qu'en est-il de l'action complète ?

Pour la précondition de l'action complète, il s'agit simplement de la conjonction de toutes les pré-conditions des actions individuelles.
Pour la postcondition, c'est un peu plus compliqué : comment connaître l'effet résultant de plusieurs actions sur une même variable propositionnelle ?

Par exemple, imaginons deux personnes dans une pièce, chacune a un interrupteur va-et-vient qui change l'état courant d'une ampoule (qui peut être allumée ou éteinte). Que se passe-t-il si les deux personnes appuient sur leur interrupteur en même temps ? Même question s'il y a trois personnes ? Imaginons un autre exemple où ces 3 personnes n'ont pas un interrupteur va-et-vient mais plutôt un interrupteur classique ON/OFF. Que se passe t-il si 2 d'entre eux appuient sur ON et 1 seul sur OFF ?

Une solution pourrait être de compter pour garder le choix majoritaire ou bien encore de garder la valeur $\top$ dès qu'une seule action l'amène. Devant la multitude de solutions possibles, il faut fixer une règle arbitraire. Celle que nous avons choisie est présentée dans la définition suivante, cette idée a été proposée dans la logique ATDEL [dL14]. L'idée peut être résumée de la façon suivante : si toutes les actions effectuent la même opération sur la variable, on effectue ce changement. Si ce n'est pas le cas, on laisse la valeur de la variable comme elle était.

**Définition 15 (action complète)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$ et une fonction $f_a$ d'association des actions de $N$ vers $2^A$, on appelle action complète le n-uplet $c = (a_1, ..., a_n) \in \times f_a(\alpha)_{\alpha \in N}$ où $n$ est égale au cardinal de $N$. On associe à cette action complète une précondition et une postcondition comme suit :

$$ 
\begin{array}{l}
- \text{pre}(c) = \bigwedge_{\alpha \in N} \text{pre}(a_\alpha) \\
- \forall p \in \mathbb{P}, \text{post}(c)(p) = \left\{ \begin{array}{ll} \top & \text{si } \forall \alpha \in N, \text{post}(a_\alpha) \in \{\top, p\} \\ \bot & \text{si } \forall \alpha \in N, \text{post}(a_\alpha) \in \{\bot, p\} \\ \neg p & \text{si } \forall \alpha \in N, \text{post}(a_\alpha) \in \{\neg p, p\} \\ p & \text{sinon} \end{array} \right.
\end{array}
$$

On appelle C l'ensemble des actions complètes.

L'exécution d'une action complète sur un modèle est la même que pour une action classique, voir définition 5.

Il faut noter que dans cette modélisation, nous ne traitons pas les modèles d'événements. Les actions semi-privées ne sont donc pas prises en charge, certains jeux ne pourront donc pas être modélisés.

## 3.3 Calcul de l'intention

### 3.3.1 Exemple

#### Premier exemple

Commençons par présenter un exemple simple de calcul de l'intention correspondant au premier principe. Nous avons donc un jeu représenté par trois propositions $p, q, r$, deux actions *noop, inverse* et un seul joueur nommé J1. Nous nous intéressons à l'intention pour le joueur d'obtenir la propriété $r$ après un tour.

Dans l'état initial nous avons le monde réel $w_1$ où $p$ est vrai, le monde $w_2$ où $p, q$ sont vraies et le monde $w_3$ où $r$ est vraie. Ces trois mondes sont indistinguishables du monde réel.

La première action *noop* notée $n$ est l'action de ne rien faire. Sa précondition est $\text{pre(noop)} = \top$ et sa postcondition est $\text{post(noop)}(t) = t, \forall t \in \mathbb{P}$. La deuxième action est l'action *inverse* notée $i$ qui correspond à inverser la valuation des propositions. Sa précondition est $\text{pre(inverse)} = \top$ et sa postcondition est $\text{post(inverse)}(p) = \neg p, \text{post(inverse)}(q) = \neg q, \text{post(inverse)}(r) = \neg r$.

La représentation en logique épistémique dynamique est présentée en figure 3.1.

Dans cette figure 3.1 est représenté le calcul de l'intention.
<figure><img src="image_15.png" /><figcaption>FIGURE 3.1 – Représentation DEL du premier exemple</figcaption></figure>

Après avoir effectué l'action *noop* (branche de gauche), le modèle $M_{|n}^{w_1}$ possède trois mondes, tous reliés au monde réel. Sur ces trois mondes, seul le monde $w_3$ possède la proposition $r$. Le rapport de présence de la propriété $r$ dans ce modèle $M_{|n}^{w_1}$ pour l'agent J1 est donc $pr_{M_{|n}^{w_1}}^{J1}(r) = 1/3$.

Nous allons associer à ce modèle une valeur qui correspond à la probabilité d'après l'agent d'obtenir la propriété $r$ à 0 tour qui est $v(M_{|n}^{w_1}, J1, r, 0) = pr_{M_{|n}^{w_1}}^{J1}(r) = 1/3$.

Après l'action *inverse* (branche de droite) le modèle $M_{|i}^{w_1}$ possède aussi trois mondes reliés au monde réel. Sur ces trois mondes, deux possèdent la propriété $r$. Le rapport de présence de la propriété $r$ est donc $pr_{M_{|i}^{w_1}}^{J1}(r) = 2/3$ et la valeur de ce modèle est $v(M_{|i}^{w_1}, J1, r, 0) = 2/3$

Pour obtenir la valeur du modèle $M^{w_1}$ initial il faut utiliser une méthode différente. En effet, ici, ce qui nous intéresse n'est pas tout à fait l'état présent mais l'état après un tour. Il nous faut donc regarder la valeur des modèles résultant de ce modèle après qu'une action ait été effectuée. On associe comme valeur à un tour pour ces deux actions, la valeur à 0 tour du modèle résultant, soit $v_n(M^{w_1}, J1, r, 1) = 1/3$ et $v_i(M^{w_1}, J1, r, 1) = 2/3$.

Nous prenons finalement le maximum de ces deux valeurs comme valeur pour le modèle $M^{w_1}$ initial, pour l'agent J1, pour la propriété $r$ à un tour : $v(M^{w_1}, J1, r, 1) = 2/3$. Nous prenons le maximum de ces deux valeurs et non une moyenne par exemple, car les actions correspondent à un choix du joueur. Étant rationnel, il prendra l'action ayant la valeur la plus élevée.

On va appeler *Best* l'ensemble des meilleures actions, les actions dont la valeur est maximale, ici $Best(M^{w_1}, J1, r, 1) = \{inverse\}$. On dira alors que le joueur aura intentionnellement obtenu la propriété $r$ s'il a effectué l'une des meilleures actions, c'est-à-dire ici, s'il a effectué l'action *inverse*. Par contre, s'il n'a pas effectué l'action *inverse*, on dira qu'il n'avait pas l'intention d'obtenir la propriété $r$.

## Deuxième exemple

Ce deuxième exemple de calcul présente un jeu simultané à deux joueurs. L'ensemble des propositions est composé de $p$ et $q$. Il y a deux actions pour le joueur J1 {+p, noop}, l'action +p = ($\top$, {p : $\top$, q : q}) correspond à obtenir la propriété $p$ et l'action noop = ($\top$, {p : p, q : q}). Le joueur J2 a deux actions,
`(+q, noop)`, l'action `+q = (⊤, {p : p, q : ⊤})` correspondant à l'obtention de la propriété `q` et l'action `noop = (⊤, {p : p, q : q})` (les actions sont notées sous la forme action=(precondition,postcondition)). Nous allons étudier l'intention du joueur J1 concernant la propriété `p ∨ q` après un tour.

Les actions sont simultanées, les deux actions de chaque joueur nous donne 4 actions complètes :

- l'action `( +p, +q )`, a pour précondition `pre(+p, +q) = ⊤` et pour postcondition
  `post(+p, +q) = {p : ⊤, q : ⊤}`

- l'action `( +p, n )`, a pour précondition `pre(+p, n) = ⊤` et pour postcondition
  `post(p, n) = {p : ⊤, q : q}`

- l'action `(n, +q)`, a pour précondition `pre(n, +q) = ⊤` et pour postcondition
  `post(n, q) = {p : p, q : ⊤}`

- l'action `(n, n)`, a pour précondition `pre(n, n) = ⊤` et pour postcondition
  `post(n, q) = {p : p, q : q}`

<figure><img src="image_16.png" /><figcaption>FIGURE 3.2 – Représentation DEL du deuxième exemple</figcaption></figure>

Cet exemple est présenté en figure 3.2. Dans cet exemple chaque modèle n'a qu'un seul monde, chaque monde est donc le monde réel de chaque modèle (par simplicité il n'y a pas de double cerclage). Il n'y a pas d'incertitude, c'est un jeu à information complète. Dans cet exemple, l'état initial *M* est qu'il n'y a ni la proposition *p* ni la proposition *q*.

- après l'action `( +p, +q )`, le modèle $M_{|(+p,+q)}$ possède un rapport de présence pour $p \lor q$ de 1,
donc une valeur $v(M_{|(+p,+q)}, J1, p \lor q, 0) = 1$ pour le joueur J1. La valeur de l'action est alors
$v_{(+p,+q)}(M_{|(+p,+q)}, J1, p \lor q, 0) = 1$.

- après l'action `( +p, n )`, le modèle $M_{|(+p,n)}$ possède un rapport de présence pour $p \lor q$ de 1,
donc une valeur $v(M_{|(+p,n)}, J1, p \lor q, 0) = 1$ pour le joueur J1. La valeur de l'action est alors
$v_{(+p,n)}(M_{|(+p,n)}, J1, p \lor q, 0) = 1$.

- après l'action `(n, +q)`, le modèle $M_{|(n,+q)}$ possède un rapport de présence pour $p \lor q$ de 1,
donc une valeur $v(M_{|(n,+q)}, J1, p \lor q, 0) = 1$ pour le joueur J1. La valeur de l'action est alors
$v_{(n,+q)}(M_{|(n,+q)}, J1, p \lor q, 0) = 1$.

- après l'action `(n, n)`, le modèle $M_{|(n,n)}$ possède un rapport de présence pour $p \lor q$ de 0, donc une valeur $v(M_{|(n,n)}, J1, p \lor q, 0) = 0$ pour le joueur J1. La valeur de l'action est alors
$v_{(n,n)}(M_{|(n,n)}, J1, p \lor q, 0) = 0$.

Pour obtenir la valeur des actions du joueur J1, il nous faut faire la moyenne sur les modèles atteints par les actions. Par exemple, pour l'action *p*, deux modèles sont à prendre en compte : les modèles
$M_{(+p,+q)}$ et $M_{(+p,n)}$ (en fait, on fait la moyenne sur les actions des autres joueurs). La moyenne de la valeur de ces deux modèles est $\frac{1+1}{2} = 1$, la valeur de l'action $p$ est donc : $v_p(M, J1, p \lor q, 1) = 1$.

Pour l'action $n$ nous avons aussi deux modèles dont la valeur moyenne est $\frac{1+0}{2} = 0.5$. La valeur de l'action $n$ pour le joueur J1 est donc $v_n(M, J1, p \lor q, 1) = 0.5$.

La valeur du modèle $M$ initial, pour la propriété $p \lor q$, pour le joueur J1, à un tour est donc $v(M, J1, p \lor q, 1) = 1$. L'ensemble des meilleures actions est, lui, composé de l'action $p : Best(M, J1, p \lor q, 1) = \{p\}$.

Si le joueur J1 fait l'action $p$, il a l'intention d'obtenir la propriété $p \lor q$, sinon il n'en a pas l'intention.

## Troisième exemple

Dans ce troisième exemple, nous allons prendre un jeu à deux joueurs à information complète. Nous allons cette fois-ci nous intéresser à l'intention du joueur 1 à trois tours. Ce jeu se déroule tour par tour. Étant donné qu'on ne modélise que des jeux simultanés, il faut utiliser les variables et la définition des actions pour reproduire le concept de tour par tour. Il faudra également introduire le concept, déjà rencontré dans la section GDL, d'action légale.

Une action *légale*, ou jouable, est une action que le joueur peut effectuer au moment considéré. Dans le cas présent, un joueur ne peut jouer que si c'est son tour. Sinon, il ne pourra qu'effectuer l'action *noop*.

Pour rappel de la définition de l'exécution d'une action (voir définition 5), un monde ne vérifiant pas la précondition d'une action se voit supprimé du modèle résultant. Pour qu'une action soit jouable dans un modèle, il faut alors que sa précondition soit au moins vérifiée dans le monde réel. C'est une condition suffisante ici car chaque modèle ne contient que le monde réel, nous verrons dans l'exemple suivant que ce n'est pas le cas en général.

<figure><img src="image_17.png" /><figcaption>FIGURE 3.3 – Représentation DEL du troisième exemple</figcaption></figure>

Ce jeu est donc composé des propositions $\mathbb{P} = \{p, q, r, t\}$, la variable $t$ sert à coder les tours des joueurs J1 et J2. La variable $t$ est vraie quand c'est le tour du joueur J1 et fausse quand c'est celui du joueur J2. Le joueur J1 à quatre actions $+p,+q,+r$ et $n_1$. L'action $+p$ sert au joueur J1 quand c'est son tour à choisir la variable $p$ quand elle existe. Sa précondition est donc $pre(+p) = p \land t$ et sa postcondition
est :

- post(+p)(p) = ⊤ le joueur a choisi p

- post(+p)(q) = ⊥ le joueur n'a pas choisi q

- post(+p)(r) = ⊥ le joueur n'a pas choisi r

- post(+p)(t) = ⊥ ce n'est plus au joueur J1 de jouer

Les actions $+q$ et $+r$ sont définies de manière similaire : $+q = (q \wedge t, \{p : \bot, q : \top, r : \bot, t : \bot\})$ et $+r = (r \wedge t, \{p : \bot, q : \bot, r : \top, t : \bot\})$.

L'action $n_1$ est légèrement différente d'une action *noop* classique, le joueur J1 ne fait rien que lorsque ce n'est pas son tour. La précondition est ainsi $pre(n_1) = \neg t$. Sa postcondition prend en compte le changement de tour $post(n_1) = \{p : p, q : q, r : r, t : \top\}$.

Pour le joueur J2, il y a deux actions, l'action *noop* qu'il peut jouer n'importe quand et l'action *inverse* qu'il ne peut effectuer qu'à son tour. L'action *noop* est définie comme suit : $noop = (\top, \{p : p, q : q, r : r, t : t\})$. L'action *inverse* inverse la valuation de $p, q, r$, elle est définie comme suit : $inverse = (\neg t, \{p : \neg p, q : \neg q, r : \neg r, t : t\})$. Le changement de tour a déjà été pris en charge dans les actions de l'autre joueur.

Finalement, les actions complètes sont simples à générer. Bien qu'il y ait quatre actions pour le joueur J1 et deux pour le joueur J2, il n'y a que cinq actions légales complètes qui seront utilisées lors de ce jeu :

- action (+p, noop) = ($t \wedge p, \{p : \top, q : \bot, r : \bot, t : \bot\}$) noté P

- action (+q, noop) = ($t \wedge q, \{p : \bot, q : \top, r : \bot, t : \bot\}$) noté Q

- action (+r, noop) = ($t \wedge r, \{p : \bot, q : \bot, r : \top, t : \bot\}$) noté R

- action ($n_1$, noop) = ($\neg t, \{p : p, q : q, r : r, t : \top\}$) noté N

- action ($n_1$, inverse) = ($\neg t, \{p : \neg p, q : \neg q, r : \neg r, t : \top\}$) noté I

Cet exemple est présenté en figure 3.3. Dans cet exemple, nous étudions l'intention du joueur J1 vis à vis de la propriété $p \lor r$ à trois tours.

Depuis le modèle *M* initial le joueur 1 peut effectuer deux actions : *p* ou *q*. Dans chacun des deux modèles résultants, le joueur J2 peut effectuer deux actions « ne rien faire » et *inverse*. Pour finir le joueur J1 pourra effectuer l'une de ses trois actions.

Si l'action *P* puis l'action *N* sont effectuées, nous nous retrouvons dans le modèle $M_{|P,N}$. Dans ce modèle ne comportant qu'un seul monde où seul *p* est vraie, il n'y a qu'une seule action légale : *P*. Cette action nous amène vers le modèle $M_{|P,N,P}$ où le rapport de présence de la formule $p \lor r$ vaut 1. La valeur du modèle est alors $v(M_{|P,N,P}, J1, p \lor r, 0) = 1$ et donc $v(M_{|P,N}, J1, p \lor r, 1) = 1$ étant donné qu'il n'y a qu'une action.

Si l'action *P* puis l'action *I* sont effectuées, nous nous retrouvons dans le modèle $M_{|P,I}$. Dans ce modèle comportant un seul monde où *q* et *r* sont vraies, il n'y a que deux actions légales : *Q* et *R*. L'action *Q* nous amène vers le modèle $M_{|P,I,Q}$ avec un rapport de présence de 0 et donc une valeur $v(M_{|P,I,Q}, J1, p \lor r, 0) = 0$. L'action *R* nous amène vers le modèle $M_{|P,I,R}$ avec un rapport de présence de 1 et donc une valeur $v(M_{|P,I,R}, J1, p \lor r, 0) = 1$. Pour obtenir la valeur des actions du joueur J1, il faut moyenner sur les actions du joueur J2, ici il n'y a qu'une action *noop* pour le joueur J2. La valeur de l'action $+q$ du joueur J1 est donc $v_{+q}(M_{|P,I}, J1, p \lor r, 1) = 0$. De même, la valeur de l'action *r* du joueur J1 est donc $v_{+r}(M_{|P,I}, J1, p \lor r, 1) = 1$. Le joueur étant rationnel, il choisira l'action de valeur maximale qui donne une valeur de 1, la valeur du modèle $M_{|P,I}$ est donc $v(M_{|P,I}, J1, p \lor r, 1) = 1$.

Pour obtenir la valeur du modèle $M_{|P}$ il faut moyenner la valeur de chaque action du joueur J1 sur les actions du joueur J2 et prendre la valeur maximale. Le joueur J1 n'a qu'une seule action : $n_1$ et le
joueur J2 a deux actions : *noop* et *inverse*. La moyenne des modèles résultants est $\frac{1+1}{2} = 1$. La valeur du modèle $M_{|P}$ est donc $v(M_{|P}, J1, p \wedge r, 2) = 1$ et donc la valeur de l'action $+p$ du joueur 1 est $v_{+p}(M, J1, p \wedge r, 3) = 1$.

D'une manière similaire, on obtient pour le modèle $M_{|Q}$ une valeur de $v(M_{|Q}, J1, p \wedge r, 2) = 0.5$. La valeur de l'action $+q$ est donc $v_{+q}(M, J1, p \wedge r, 3) = 0.5$.

L'ensemble *Best* est donc formé d'un seul élément $Best(M, J1, p \wedge r, 3) = \{+p\}$. Si le joueur 1 fait l'action $+p$ c'est qu'il a l'intention d'obtenir la propriété $p \vee r$ dans 3 tours.

## Quatrième exemple

Dans ce quatrième et dernier exemple, nous allons nous focaliser sur les mondes indistinguishables du monde réel. L'exemple est un jeu simultané à deux joueurs, il y a trois propositions $p, q, r$, le joueur J1 a deux actions *noop*, *inverse* et le joueur J2 a deux actions notées *flip(q)*, *flip(r)* qui permettent de rendre vraie une proposition (abrégé en $|q|$ et $|r|$ dans la figure 3.4). Dans l'état initial $M$, la proposition $p$ est vraie, la proposition $q$ est fausse et les joueurs le savent. Cependant le joueur J1 ne sait pas si $r$ est vrai ou faux, le joueur J2 sait que $r$ est faux. Cet état initial est présenté en figure 3.4. Nous allons nous intéresser à l'intention du joueur J1 (représentée en rouge) et du joueur J2 (représentée en bleu) d'obtenir la propriété $q \wedge r$ après 1 tour.

<figure><img src="image_18.png" /><figcaption>FIGURE 3.4 – Représentation DEL du quatrième exemple</figcaption></figure>

Le joueur J1 possède deux actions *noop* et *inverse*. Pour rappel l'action *noop* est définie comme suit : $noop = (\top, \{p : p|p \in \mathbb{P}\})$. L'action *inverse* est définie comme $inverse = (\top, \{p : \neg p|p \in \mathbb{P}\})$.

Le joueur J2 possède deux actions *flip(q)* et *flip(r)*, elles décrivent l'action d'inverser la valeur de la proposition correspondante si celle-ci était initialement fausse. Elles sont définies de la manière suivante : $flip(q) = (\neg q, \{p : p, q : \neg q, r : r\})$ et $flip(r) = (\neg r, \{p : p, q : q, r : \neg r\})$. La précondition de l'action *flip(r)* n'est pas vérifiée dans le monde $w_2$ où le joueur J1 imagine que $r$ est vraie. Le joueur J1 ne peut donc pas penser que le joueur J2 peut effectuer l'action *flip(r)* dans le monde $w_2$.
Il est important de noter que les actions du joueur J1 sont toutes jouables dans tous les mondes qu'il considère indistinguishables du monde réel. En effet, que se passerait-il si un agent tentait d'effectuer une action alors que le monde réel est précisément un monde où cette action n'est pas jouable ? Ceci n'est pas modélisé ici.

Nous avons ici quatre actions complètes, qui sont définies comme :

— action (noop, flip(q)) = (¬q, {p : p, q : ¬q, r : r}) noté (n, /q)

— action (noop, flip(r)) = (¬r, {p : p, q : q, r : ¬r}) noté (n, /r)

— action (inverse, flip(q)) = (¬q, {p : ¬p, q : ¬q, r : ¬r}) noté (i, /q)

— action (inverse, flip(r)) = (¬r, {p : ¬p, q : ¬q, r : ¬r}) noté (i, /r)

Dans l'esprit du joueur J1, il y a deux cas possibles. Soit le monde réel est le monde $w_1$, soit c'est le monde $w_2$. Dans les deux cas, le joueur J1 a deux actions atomiques possibles : noop et inverse. Mais, dans le monde $w_1$ il y a quatre actions complètes possibles et dans le monde $w_2$ il y a deux actions complètes possibles.

Dans le modèle $M^{w_1}$ où $w_1$ est le monde réel, l'action noop du joueur J1 nous amène vers deux modèles différents suivant l'action du joueur J2. L'action $(n, /q)$ nous amène vers le modèle $M^w_1|_{(n,q)}$ (voir définition 5 pour plus d'explications sur l'exécution d'une action), où il y a deux mondes indistinguishables pour le joueur J1 et dans l'un d'entre eux $q \land r$ est vrai. L'action $(n, /r)$ nous amène vers le modèle $M^w_1|_{(n,r)}$ où il n'a qu'un seul monde et où $q \land r$ est faux. Les valeurs de ces modèles sont donc les suivantes : $v(M^w_1|_{(n,q)}, J1, q \land r, 0) = 0.5$ et $v(M^w_1|_{(n,r)}, J1, q \land r, 0) = 0$. Le joueur J2 a deux actions possibles et le joueur J1 ne sachant pas quelle action fera le joueur J2, on va considérer qu'il effectuera de manière équiprobable l'une de ses deux actions. Dans le cas où le monde $w_1$ est le monde réel, l'action noop a donc une valeur de 0.25.

Dans le modèle $M^{w_2}$ où $w_2$ est le monde réel, l'action noop du joueur J1 amène vers un seul modèle $M^w_2|_{(n,q)}$, puisque le joueur J2 n'a maintenant qu'une seule action jouable flip(q). On peut noter que les modèles $M^w_1|_{(n,q)}$ et $M^w_2|_{(n,q)}$ sont similaires (sauf pour la désignation du monde réel). C'est un résultat attendu puisque $w_1$ et $w_2$ sont liés et c'est exactement la même action qui est effectuée. Dans ce modèle, $q \land r$ est vrai dans l'un des deux mondes indistinguishables pour le joueur J1, la valeur de ce modèle est donc $v(M^w_2|_{(n,q)}, J1, q \land r, 0) = 0.5$. Dans le cas où le monde $w_2$ est le monde réel, la valeur de l'action noop a une valeur de 0.5.

Les mondes $w_1$ et $w_2$ étant indistinguishables pour le joueur J1 on va les considérer équiprobables. La valeur de l'action noop est alors la moyenne des valeurs qu'a l'action suivant le monde réel considéré. La valeur de l'action de noop pour le joueur 1 pour la formule $q \land r$ à un tour est donc $v_{noop}(M^{w_2}, J1, q \land r, 1) = 0.375$. On peut noter que $v_{noop}(M^{w_2}, J1, q \land r, 1) = v_{noop}(M^{w_1}, J1, q \land r, 1)$ puisque le calcul, et donc le résultat, aurait été identique si $w_2$ était le « vrai » monde réel.

De la même manière on peut calculer la valeur de l'action inverse, celle-ci vaut $v_{inverse}(M^{w_2}, J1, q \land r, 1) = v_{inverse}(M^{w_1}, J1, q \land r, 1) = 0.625$. L'ensemble Best est donc composé de $Best(M^{w_1}, J1, q \land r, 1) = \{inverse\}$. Si le joueur J1 a fait l'action inverse c'est qu'il avait l'intention d'obtenir la propriété $q \land r$.

Dans l'esprit du joueur J2, il n'y a qu'un cas possible, celui où $w_1$ est le monde réel, représenté par le modèle $M^{w_1}$. Le calcul de l'intention du joueur J2 est donc plus simple.

L'action $r$ du joueur J2 amène vers deux modèles différents suivant l'action du joueur J1 : $M^w_1|_{(n,r)}$ et $M^w_1|_{(i,r)}$. Le modèle $M^w_1|_{(n,r)}$ ne comporte qu'un seul monde où $q \land r$ est faux. La valeur de ce modèle est donc $v(M^w_1|_{(n,r)}, J2, q \land r, 0) = 0$. Le modèle $M^w_1|_{(i,r)}$ comporte lui aussi un seul monde cependant celui-ci vérifie $q \land r$. La valeur du modèle est donc $v(M^w_1|_{(i,r)}, J2, q \land r, 0) = 1$. La valeur de l'action flip(r) du joueur J2 pour la formule $q \land r$ après un tour est donc : $v_{flip}(r)(M^{w_1}, J2, q \land r, 1) = 0.5$.
L'action $q$ du modèle nous amène également vers 2 modèles $M_{(n,q)}^{w_1}$ et $M_{|(i,q)}^{w_1}$. Le modèle $M_{|(n,q)}^{w_1}$ comporte deux mondes, cependant seul le monde réel $w_1$ est à considérer puisque que l'autre monde $w_2$ n'est pas indistinguishable du monde réel $w_1$ pour le joueur J2. Il n'y a donc qu'un monde à prendre en compte, où $q \wedge r$ est faux. La valeur de ce modèle est donc $v(M_{|(n,q)}^{w_1}, J2, q \wedge r, 0) = 0$. Le modèle $M_{|(i,q)}^{w_1}$ comporte lui aussi deux mondes et il n'y a également qu'un seul monde à prendre en compte, dans lequel $q \wedge r$ est vrai. La valeur de ce modèle est $v(M_{|(n,q)}^{w_1}, J2, q \wedge r, 0) = 1$. La valeur de l'action flip($q$) pour le joueur J2 vaut alors $v_{flip}(q)(M^{w_1}, J2, q \wedge r, 1) = 0.5$.

L'ensemble Best est alors composé des actions flip($q$) et flip($r$) : Best($M^{w_1}$, J2, $q \wedge r, 1$) = {flip($q$), flip($r$)}. L'ensemble Best est donc composé de l'ensemble des actions jouables par le joueur J2. On ne peut donc pas conclure quant à l'intention du joueur J2 d'obtenir la propriété $q \wedge r$.

### 3.3.2 Définitions

Comme nous avons pu le voir dans les différents exemples précédents, la notion d'action jouable a une place importante. Cependant cette notion n'est pas nativement prise en compte par la logique épistémique dynamique, une action n'est en effet qu'une transition entre modèles épistémiques.

Dans un jeu, chaque action est associée à un joueur et chaque action n'est pas forcément jouable à tout moment. Nous allons donc chercher à représenter la jouabilité/légalité d'une action à un moment donné. Tout d'abord, pour qu'une action soit jouable dans un monde, sa précondition doit être vérifiée. En effet, selon la définition de l'exécution d'une action (voir définition 5), un monde ne vérifiant pas la précondition est supprimé du modèle résultant. Cependant ce n'est pas suffisant. Dans un jeu, les actions sont définies de façon à ce qu'elles couvrent toutes les situations possibles. En effet, prenons l'exemple d'un cas où parmi l'ensemble des mondes considérés comme possibles par le joueur, certains n'auraient pas les mêmes actions jouables que d'autres. Dans ce cas, d'une part on ne pourrait pas dire que ces mondes sont indistinguishables et d'autre part, on ne pourrait pas dire ce qui se passerait si une action non jouable dans le monde réel était engagée par exemple.

Une action est donc jouable dans un monde pour un joueur si sa précondition est vérifiée dans ce monde et par tous les mondes indistinguishables pour le joueur.

**Définition 16 (Action jouable/légale)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, un modèle $M^w = (W, R, \pi, f_r, f_a)$, soit un monde $w_i \in W$, soit $\alpha \in N$, une action atomique $a$ est dite jouable/légale par l'agent $\alpha$ dans le monde $w_i$ si et seulement si $\forall w_j \in \{w_i\}_\alpha, \models_{w_j}^M \text{pre}(a_k)$.

On va noter $A_{\alpha, w_i}^l$ l'ensemble des actions jouables par $\alpha$ dans le monde $w_i$ l'ensemble $A_{\alpha, w_i}^l = \{a_k \in A_\alpha \text{ tel que } \forall w_j \in \{w_i\}_\alpha, \models_{w_j}^M \text{pre}(a_k)\}$.

Enfin on note $C_{w_i}^l$ l'ensemble des actions complètes jouables dans le monde $w_i$ l'ensemble $C_{w_i}^l = \{c = (a_1, ..., a_n) \in \times_{\alpha \in N} A_{\alpha, w_i}^l\}$

À présent que les actions jouables ont été définies, nous pouvons définir la valeur d'un modèle et d'une action. À travers les quatre exemples précédents, le calcul de la valeur d'une action $a$ depuis un modèle $M^w$ pour un joueur $\alpha$ pour une formule $\phi$ à $k$ tours se fait en trois strates : (1) on fait la moyenne sur les mondes indistinguishables du monde réel pour le joueur $\alpha$, (2) de la moyenne sur l'ensemble des actions complètes jouables issues de l'action $a$, (3) de la valeur à $k-1$ tours des modèles résultants de ces actions.

La valeur d'un modèle pour un joueur est alors simplement la valeur maximale des valeurs des actions jouables pour le joueur. Lorsque $k=0$, la valeur d'un modèle est égale au rapport de présence de la formule parmi les mondes indistinguishables du monde réel pour le joueur.
**Définition 17 (valeur d'un modèle et valeur d'une action)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, un modèle $M^w = (W, R, \pi, f_r, f_a)$, soit $\alpha$ un agent, soit $\phi$ une formule et soit $k$ un entier naturel, on appelle $v(M^w, \alpha, \phi, k)$ pvaleur du modèle $M$ d'après l'agent $\alpha$ pour la formule $\phi$ à $k$ tours le réel suivant :

$$v(M^w, \alpha, \phi, k \ge 1) = \max_{a_\alpha \in A_{\alpha,w}^l} \sum_{w_i \in [w]_\alpha} \frac{\sum_{c_j=(a_1, \dots, a_\alpha, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1,w_i}^l \times \dots \times \{a_\alpha\} \times \dots \times A_{n,w_i}^l|}}{|[w]_\alpha|}$$
$$v(M^w, \alpha, \phi, k = 0) = \text{pr}_{M^w}^{\alpha}(\phi)$$

Soit $a_\alpha \in A_{\alpha,w}^l$ une action jouable du joueur $\alpha$ dans le modèle $M^w$, on appelle $v_{a_\alpha}(M^w, \alpha, \phi, k)$ valeur de l'action $a_\alpha$ depuis le modèle $M$ d'après l'agent $\alpha$ pour la formule $\phi$ à $k \ge 1$ tours le réel suivant :

$$v_{a_\alpha}(M^w, \alpha, \phi, k \ge 1) = \sum_{w_i \in [w]_\alpha} \frac{1}{|[w]_\alpha|} \times \sum_{c_j=(a_1, \dots, a_\alpha, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1,w_i}^l \times \dots \times \{a_\alpha\} \times \dots \times A_{n,w_i}^l|}$$

On remarque que l'on a bien $v(M^w, \alpha, \phi, k) = v(M^{w_i}, \alpha, \phi, k)$ quel que soit le monde $w_i$ appartenant à l'ensemble $[w]_\alpha$.

On peut remarquer aussi que l'on dit la valeur « d'après tel agent » car cette valeur change suivant l'agent. De plus, celle-ci dépend directement de la connaissance de l'agent sur l'état du monde.

Nous pouvons alors définir l'ensemble des meilleures actions pour obtenir la propriété $\phi$ à $k$ tours d'après un agent.

**Définition 18 (ensemble des meilleures actions)** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, un modèle $M^w = (W, R, \pi, f_r, f_a)$, soit $\alpha$ un agent, soit $\phi$ une formule et soit $k$ un entier, on appelle Best($M^w$, $\alpha$, $\phi$, $k$) l'ensemble des meilleures actions depuis le modèle $M^w$ d'après l'agent $\alpha$ pour obtenir la formule $\phi$ dans $k$ tours :

$$\text{Best}(M^w, \alpha, \phi, k) = \{a \in A_{\alpha,w}^l, \forall b \in A_{\alpha,w}^l v_a(M^w, \alpha, \phi, k) \ge v_b(M^w, \alpha, \phi, k)\}$$

## 3.4 Propriétés

### 3.4.1 Opérateur

Grâce à la définition des meilleures actions, il est possible de définir un opérateur d'intention. Un agent a l'intention d'obtenir une propriété s'il fait l'une des meilleures actions pour obtenir cette propriété et si toutes les actions ne permettent pas avec autant de chance d'obtenir cette propriété.

**Définition 19** Soit une signature de jeu $J = (\mathbb{P}, A, N)$, un modèle $M = (W, R, \pi, f_r, f_a)$, soit $\alpha$ un agent, soit $\phi$ une formule, soit $k$ un entier et $a$ une action :

$$M, w \models I_{\alpha}^{a} X^{k} \phi \text{ si et seulement si } a \in \text{Best}(M^w, \alpha, \phi, k) \text{ et si } \text{Best}(M^w, \alpha, \phi, k) \neq A_{\alpha,w}^{l}$$

La formule $M, w \models I_{\alpha}^{a} X^{k} \phi$ se lit alors : dans le monde $w$ du modèle $M$, si l'agent $\alpha$ effectue l'action $a$ alors il a l'intention d'obtenir $\phi$ en $k$ tours.
3.4.2 Extension de DEL

Afin d'utiliser et de démontrer des propriétés intéressantes de l'opérateur d'intention, il nous faut
tout d'abord étendre la logique DEL. On va ajouter deux opérateurs qui sont [a] et AX. Une formule
[a]φ se lit « la formule φ est vraie après l'action a » et la formule AXφ se lit « la formule φ est vraie
après n'importe quelle action légale » .

— M, w, |> [c]φ si et seulement si on a M|c, w, |> φ

— M, w, |> AXφ si et seulement si ∀c ∈ C<sub>w</sub><sup>l</sup>, M, w, |> [c]φ

Le langage L est l'ensemble des formules φ définies par la grammaire suivante en BNF :

$$
\phi ::= \top | p | \neg \phi | \phi \land \phi | K_{\alpha} \phi | [c] \phi | AX \phi
$$

$$
\psi ::= \top | \phi | \neg \psi | \psi \land \psi | K_{\alpha} \psi | [c] \psi | AX \psi | I_{\alpha}^{a} X^{k} \phi
$$

Il est à noter que le langage n'accepte pas l'imbrication de l'opérateur $I_{\alpha}^{a}X^{k}$.

La formule I_α XX φ n'est pas une formule bien formée, il faut lui préférer l'écriture I_α X² φ. D'autres
exemples de formules bien formées sont par exemple : I_α XK_β φ et I_α Xφ → I_β Xψ.

3.4.3 Principes

On veut prouver que l'opérateur $I_\alpha X$ est effectivement un opérateur d'intention. Pour ce faire, on va montrer qu'il vérifie certaines propriétés désirées. La plus importante est celle appelée *cohérence intention-croyance* (intention-belief consistency). En effet, cette propriété semble partagée par toutes les théories de l'intention. Par exemple la thèse d'asymétrie de Bratman stipule que :

L'intention de faire A fournit normalement à l'agent une raison de croire qu'il va faire A.
Mais il n'y a pas besoin d'être irrationnel pour avoir l'intention de faire A et pourtant ne pas
croire qu'on le fera. En revanche, il est généralement irrationnel d'avoir l'intention de faire
A en croyant qu'on ne fera pas A. Car il y a une exigence révocable que ses intentions soient
en cohérence avec ses croyances. [Bra87, p.38]<fnref n="10" />

Dans l'article plus récent de Shoham sur une approche de l'intention dans la perspective des bases de données [Sho09], celui-ci stipule que l'agent qui a l'intention d'une action ne peut pas croire que la précondition de l'action n'est pas vérifiée et en même temps croire que les postconditions de cette même action seront appliquées après l'exécution.

L'idée que les croyances et les intentions doivent être cohérentes les unes avec les autres est égale-
ment adoptée par plusieurs approches logiques de l'intention [CL90, Roy09, Woo00]. Dans la logique
BDI [RG98], cela a été interprété par les 3 principes suivants :

1. $|\models INTEND(\phi) \rightarrow \neg BEL(\neg \phi)$ (cohérence intention-croyance)

2. $|\not\models INTEND(\phi) \rightarrow BEL(\phi)$ (incomplétude intention-croyance)

3. $|\not\models BEL(\phi) \rightarrow INTEND(\phi)$ (incomplétude croyance-intention)

Pour rappel de la section 2.3, la logique BDI repose sur trois opérateurs : BEL pour la croyance, DES pour le désir et INTEND pour l'intention. Elle stipule qu'un agent ne peut pas avoir l'intention d'obtenir $\phi$ tout en croyant qu'obtenir $\phi$ est impossible. Mais d'un autre côté, on ne peut avoir l'intention de $\phi$ sans croire que l'on va obtenir $\phi$ c'est le principe d'incomplètude intention-croyance. Ces deux principes forment la thèse d'asymétrie de Bratman. Enfin, le principe d'incomplètude croyance-intention explique que l'on peut croire que l'on obtiendra $\phi$ sans pour autant avoir l'intention d'obtenir $\phi$.

Cohen et Levesque [CL90] ont présenté un exemple habituellement appelé l'exemple du dentiste :

<footnote n="10">10. traduction faite par l'auteur</footnote>
J'ai l'intention de faire soigner mes dents et je sais que cela impliquera de la douleur, mais
je n'ai pas l'intention de ressentir cette douleur.

Cohen et Levesque utilisent cet exemple pour défendre le principe d'absence d'effet secondaire. Ce principe dit qu'avoir l'intention d'atteindre un objectif n'implique pas que l'on ait l'intention d'en obtenir les effets secondaires, ce qui peut être formalisé de cette manière :

$$
4 \models \left( \mathit{INTEND}(\phi) \wedge \mathit{BEL}(\phi \to \psi) \right) \to \mathit{INTEND}(\psi) \quad \text{(absence d'effet secondaire)}
$$

Roy [Roy09] défend les quatre principes suivants dans son approche de l'intention :

$$
5 \models \phi \text{ implique } \models I_{\alpha}\phi \qquad \text{(nécessitation)}
$$

$$
6 \models I_{\alpha}(\phi \rightarrow \psi) \rightarrow (I_{\alpha}\phi \rightarrow I_{\alpha}\psi) \qquad \text{(axiome K)}
$$

$$
7 \models I_{\alpha}\phi \rightarrow \neg I_{\alpha}\neg\phi \qquad \text{(sérialité)}
$$

$$
8 \models I_{\alpha}\phi \rightarrow K_{\alpha}I_{\alpha}\phi \qquad \text{(interaction)}
$$

Le principe de nécessitation implique qu’un agent a l’intention de ce qui sera toujours vrai, cela rentre en contradiction avec le principe d’incomplétude croyance-intention. L’axiome K, dit de distributivité, est l’axiome que doit vérifiée l’intention pour être un opérateur normal. En français, il stipule que lorsqu’on a l’intention que $\phi \to \psi$ alors si on a l’intention de $\phi$ alors on a également l’intention de $\psi$. L’axiome de sérialité représente le fait qu’on ne peut pas avoir l’intention d’une chose et de son contraire. Enfin le principe d’interaction implique qu’un agent doit connaître ses intentions.

Khan et Lespérance [KL10] montrent aussi que leur approche satisfait différentes propriétés. Celles
qui peuvent être traduites dans notre formalisme sont :

$$
9 \models \neg I_{\alpha} X \perp \qquad \text{(cohérence)}
$$

$$
10 \models K_{\alpha}AX\phi \rightarrow I_{\alpha}X\phi \qquad \text{(réalisme)}
$$

$$
11 \models I_{\alpha}X\phi \rightarrow \neg K_{\alpha}AX\neg\phi \qquad \text{(cohérence intention-connaissance)}
$$

Le principe de cohérence traduit le fait qu’on ne peut pas avoir l’intention de l’impossible. Le prin-
cipe de réalisme indique qu’un agent doit avoir l’intention de ce qu’il pense obtenir dans tous les cas,
cela rentre en contradiction avec le principe d’incomplétude croyance-intention. Enfin, le principe de
cohérence intention-connaissance est la version « connaissance » du principe de cohérence intention-
croyance.

Il n'y a pas d'opérateur de croyance dans notre logique. La façon de montrer que notre approche
respecte la cohérence intention-croyance est indirecte. Pour les premiers principes, nous faisons appel à
une relation entre croyance et connaissance qui est largement acceptée : « ce qui est su est aussi cru ».
Cela revient à la validé de $K_\alpha\phi \rightarrow BEL_\alpha\phi$. Cela veut dire que si le principe 1 était valide dans une
logique avec des opérateurs de croyance et de connaissance, alors la formule $I_\alpha^\alpha X\phi \rightarrow \neg K_\alpha AXK_\alpha \neg\phi$
devrait aussi être valide. On appelle ce principe (comme dans [KL10]) *cohérence intention-connaissance*.
Il est à noter que l'on utilise $K_\alpha AXK_\alpha$ à la place de $K_\alpha$. C'est nécessaire car dans notre modélisation
quand on écrit $I_\alpha^\alpha X\phi$ nous exprimons le fait que l'agent a l'intention d'obtenir $\phi$ dans l'état suivant. Cela
sera un prérequis pour tous les principes que nous aborderons dans la suite.

**3.4.4 Propositions**

Présentation

Voici une liste de principes vérifiés par notre opérateur d'intention :

**Proposition 1**

$$
1. \models I_{\alpha}^{a} X \phi \rightarrow \neg K_{\alpha} A X K_{\alpha} \neg \phi \qquad \text{(cohérence intention-connaissance)}
$$
2. $| \models I_{\alpha}^{a} X^{k} \phi \rightarrow \neg K_{\alpha}(AXK_{\alpha})^{k} \neg \phi$ (k-tours cohérence intention-connaissance)

3. $\not\models I_{\alpha}^{a} X^{k} \phi \rightarrow K_{\alpha}(AXK_{\alpha})^{k} \phi$ (k-tours incomplétude intention-connaissance)

4. $\not\models K_{\alpha}(AXK_{\alpha})^{k} \phi \rightarrow I_{\alpha}^{a} X^{k} \phi$ (k-tours incomplétude connaissance-intention)

5. $\not\models (I_{\alpha}^{a} X^{k} \phi \wedge K_{\alpha}(AX)^{k}(\phi \rightarrow \psi)) \rightarrow I_{\alpha}^{a} X^{k} \psi$ (absence d'effet secondaire)

6. $| \models \neg I_{\alpha}^{a} X^{k} \perp$ (cohérence)

7. $\not\models I_{\alpha}^{a} X^{k} \phi \rightarrow \neg I_{\alpha}^{a} X^{k} \neg \phi \text{ pour } k \geq 2$ (non-serialité)

8. $| \models I_{\alpha}^{a} X^{k} \phi \rightarrow K_{\alpha} I_{\alpha}^{a} X^{k} \phi$ (interaction)

9. $| \models \neg I_{\alpha}^{a} X^{k} \phi \rightarrow K_{\alpha} \neg I_{\alpha}^{a} X^{k} \phi$ (interaction)

10. Depuis $\phi \leftrightarrow \psi$ déduire $I_{\alpha}^{a} X^{k} \phi \leftrightarrow I_{\alpha}^{a} X^{k} \psi$ (indépendance de la syntaxe)

Les propriétés 1.2, 1.3 et 1.4 correspondent aux principes 1 à 3 respectivement. Notre opérateur d'intention satisfait donc tous les principes de la thèse d'asymétrie, mais en utilisant la connaissance à la place de croyance. La propriété 1.1 correspond aussi au principe 11. La propriété 1.5 correspond au principe 4. La propriété 1.6 correspond au principe 9. La propriété 1.7 correspond à la négation du principe 7 et la propriété 1.8 correspond au principe 8. La propriété 1.9 est un corollaire de la proposition 1.8.

Quatre principes ne sont pas satisfaits : les principes 5, 6, 7 et 10. Notamment, le principe 7 de cohérence interne des intentions n'est pas satisfait, nous y reviendrons plus tard. Le principe 10 contredit le principe 3 de la thèse d'asymétrie. Il est donc préférable de ne pas le satisfaire.

## Démonstration

Afin de démontrer les propositions, il faut d'abord commencer par montrer quatre lemmes.

**Lemme 1** $M, w \models K_{\alpha}AXK_{\alpha}\phi$ implique $\text{Best}(M^{w}, \alpha, \phi, 1) = A_{\alpha,w}^{l}$

**Preuve** : Si la formule $M, w \models K_{\alpha}AXK_{\alpha}\phi$ est vraie, alors par définition $\forall w' \in [w]_{\alpha}, M, w' \models AXK_{\alpha}\phi$ est vrai. Pour chaque $w' \in [w]_{\alpha}$ on aura alors $\forall c \in C_{w'}^{l}, M_{|c}, w' \models K_{\alpha}\phi$, ce qui implique de part la définition de l'opérateur $K_{\alpha}$ que $\text{pr}_{M_{|c}^{w'}}^{\alpha}(\phi) = 1$. Donc $\forall w' \in [w]_{\alpha}, \forall c \in C_{w}^{l}, \text{pr}_{M_{|c}^{w'}}^{\alpha}(\phi) = 1$.

Or :

$$v_{a_{\alpha}}(M^{w}, \alpha, \phi, 1) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{\text{pr}_{M_{|c_j}^{w_i}}^{\alpha}(\phi)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|}$$

Ce qui donne $\forall a \in A_{\alpha,w}^{l}$ :

$$v_{a_{\alpha}}(M^{w}, \alpha, \phi, 1) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{1}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|}$$

Ceci amène à $\forall a \in A_{\alpha,w}^{l}, v_{a_{\alpha}}(M^{w}, \alpha, \phi, 1) = 1$ vérifiant ainsi que $\text{Best}(M^{w}, \alpha, \phi, 1) = A_{\alpha,w}^{l}$.

**Lemme 2** $M, w \models K_{\alpha}(AXK_{\alpha})^{k} \phi$ implique $\forall a \in A_{\alpha,w}^{l}, v_{a_{\alpha}}(M^{w}, \alpha, \phi, k) = 1$.
**Preuve :** Cette démonstration va se faire par récurrence.

On a déjà montré dans le lemme 1 que $M, w \models K_\alpha AXK_\alpha\phi$ implique que $\forall a \in A_{\alpha,w}^l$,
$v_{a_\alpha}(M^w, \alpha, \phi, 1) = 1$. Pour la suite de la récurrence partons de l'hypothèse que
$M, w \models K_\alpha(AXK_\alpha)^{k-1}\phi$ implique $\forall a \in A_{\alpha,w}^l$, $v_{a_\alpha}(M^w, \alpha, \phi, k-1) = 1$ et que la formule
$M, w \models K_\alpha(AXK_\alpha)^k\phi$ est vraie.

Par hypothèse, $\forall w' \in [w]_\alpha, \forall a \in A_{\alpha,w}^l, \forall c \in C_{w'}^l$, on a $M|_c \models K_\alpha(AXK_\alpha)^{k-1}\phi$ vrai et donc
$\forall w' \in [w]_\alpha, \forall a_\alpha \in A_{\alpha,w}^l, \forall c \in C_{w'}^l, v(M_{|c}^{w'}, \alpha, \phi, k-1) = 1$.

Pour rappel la valeur d'une action est :

$$v_{a_{\alpha}}(M^{w}, \alpha, \phi, k) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1, w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n, w_i}^l|}$$

On a alors $\forall w' \in [w]_\alpha, \forall a_\alpha \in A_{w,\alpha}^l$ :

$$\sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{1}{|A_{1, w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n, w_i}^l|} = 1$$

Puis $\forall a \in A_{w,\alpha}^l$

$$v_{a_{\alpha}}(M^{w}, \alpha, \phi, k) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} = 1$$

En conclusion on obtient bien $\forall a \in A_{\alpha,w}^l, v_{a_\alpha}(M^w, \alpha, \phi, k) = 1$.

**Lemme 3** $M, w \models K_\alpha AXK_\alpha\neg\phi$ implique $\text{Best}(M^w, \alpha, \phi, 1) = A_{\alpha,w}^l$

**Preuve :** Si la formule $M, w \models K_\alpha AXK_\alpha\neg\phi$ est vraie, alors par définition $\forall w' \in [w]_\alpha$, $M, w' \models AXK_\alpha\neg\phi$ est vrai. Pour chaque $w' \in [w]_\alpha$ on aura alors $\forall c \in C_{w'}^l, M|_c, w', \models K_\alpha\neg\phi$, ce qui implique de par la définition de l'opérateur $K_\alpha$ que $\text{pr}_{M|_c}^\alpha(\phi) = 0$. Donc $\forall w' \in [w]_\alpha$, $\forall c \in C_w, \text{pr}_{M|_c}^\alpha(\phi) = 0$. Ceci amène à $\forall a \in A_{\alpha,w}^l, v_{a_\alpha}(M^w, \alpha, \phi, k) = 0$ vérifiant ainsi que $\text{Best}(M^w, \alpha, \phi, 1) = A_{\alpha,w}^l$.

**Lemme 4** $M, w \models K_\alpha(AXK_\alpha)^{k-1}\neg\phi$ implique $\forall a \in A_{\alpha,w}^l, v_{a_\alpha}(M^w, \alpha, \phi, k) = 0$.

**Preuve :** Cette démonstration va se faire par récurrence.

On a déjà montré dans le lemme 3 que $M, w \models K_\alpha AXK_\alpha\phi$ implique que $\forall a \in A_{\alpha,w}^l$,
$v_{a_\alpha}(M^w, \alpha, \phi, 1) = 0$. Pour la suite de la récurrence partons de l'hypothèse que
$M, w \models K_\alpha(AXK_\alpha)^{k-1}\phi$ implique $\forall a \in A_{\alpha,w}^l$, $v_{a_\alpha}(M^w, \alpha, \phi, k-1) = 0$ et que la formule
$M, w \models K_\alpha(AXK_\alpha)^k\neg\phi$ est vraie.

Par hypothèse, $\forall w' \in [w]_\alpha, \forall a \in A_{\alpha,w}^l, \forall c \in C_{w'}^l$, on a $M|_c \models K_\alpha(AXK_\alpha)^{k-1}\neg\phi$ vrai et donc
$\forall w' \in [w]_\alpha, \forall a_\alpha \in A_{\alpha,w}^l, \forall c \in C_{w'}^l, v(M_{|c}^{w'}, \alpha, \phi, k-1) = 0$.

Pour rappel la valeur d'une action est :

$$v_{a_{\alpha}}(M^{w}, \alpha, \phi, k) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1, w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n, w_i}^l|}$$

On a alors $\forall w' \in [w]_\alpha, \forall a_\alpha \in A_{w,\alpha}^l$ :
$$ \sum_{c_j=(a_1, \dots, a_\alpha, \dots, a_n) \in C_{w_i}^l} \frac{0}{|A_{1,w_i}^l \times \dots \times \{a_\alpha\} \times \dots \times A_{n,w_i}^l|} = 0 $$

Puis $\forall a \in A_{w,\alpha}^l$

$$ v_{a_\alpha}(M^w, \alpha, \phi, k) = \sum_{w_i \in [w]_\alpha} \frac{0}{|[w]_\alpha|} = 0 $$

En conclusion on obtient bien $\forall a \in A_{\alpha,w}^l, v_{a_\alpha}(M^w, \alpha, \phi, k) = 0$.

**Proposition 1.1 et 1.2 : cohérence intention-connaissance**

$$ \models I_{\alpha} X^k \phi \rightarrow \neg K_{\alpha} (AXK_{\alpha})^k \neg \phi $$

**Preuve :** La preuve de cette proposition se fait par l'absurde. Supposons que l'on ait à la fois $M, w \models I_{\alpha}^a X^k \phi$ et $M, w \models K_{\alpha}(AXK_{\alpha})^k \neg \phi$. Dans ce cas, d'après le lemme 4, $\forall a \in A_{\alpha,w}^l$, $v_a(M^w, \alpha, \neg \phi, k) = 0$ c'est-à-dire $\text{Best}(M^w, \alpha, \phi, 1) = A_{\alpha,w}^l$. Or $M, w \models I_{\alpha}^a X^k \phi$ implique que $\text{Best}(M^w, \alpha, \phi, 1) \neq A_{\alpha,w}^l$.

**Proposition 1.3 : incomplétude intention-connaissance**

$$ \not\models I_{\alpha}^a X^k \phi \rightarrow K_{\alpha}(AXK_{\alpha})^k \phi $$

**Preuve :** La preuve de cette proposition se fait par l'absurde avec le lemme 1 et on le fera pour $k=1$. Supposons que l'on ait à la fois $M, w \models I_{\alpha}^a X^k \phi$ et $M, w \models K_{\alpha}AXK_{\alpha}\phi$. Dans ce cas, d'après le lemme 1, $M, w \models K_{\alpha}AXK_{\alpha}\phi$ implique $\text{Best}(M^w, \alpha, \phi, 1) = A_{\alpha,w}^l$. Or $M, w \models I_{\alpha}^a X^k \phi$ implique $\text{Best}(M^w, \alpha, \phi, 1) \neq A_{\alpha,w}^l$, ce qui démontre la proposition.

**Proposition 1.4 : incomplétude connaissance-intention**

$$ \not\models K_{\alpha}(AXK_{\alpha})^k \phi \rightarrow I_{\alpha}^a X^k \phi $$

**Preuve :** Le lemme 2 nous permet d'écrire que $M, w \models K_{\alpha}(AXK_{\alpha})^k \phi$ implique $\text{Best}(M^w, \alpha, \phi, k) = A_{\alpha,w}^l$. Or par définition $M, w \not\models I_{\alpha}^a X^k \phi$ si $\text{Best}(M^w, \alpha, \phi, k) = A_{\alpha,w}^l$.

**Proposition 1.5 : absence d'effet secondaire**

$$ \not\models (I_{\alpha}^a X^k \phi \wedge K_{\alpha}(AX)^k (\phi \rightarrow \psi)) \rightarrow I_{\alpha}^a X^k \psi $$

**Preuve :** Afin de montrer cette invalidité, un contre-exemple suffira et on le montrera pour $k=1$. Soit l'exemple présenté en figure 3.5, dans celui-ci, depuis le modèle $M$ initial, deux actions $a$ et $b$ amène vers les modèles $M|_a$ et $M|_b$. L'actions sont définis comme $a = (\top, \{p : \top, q : \top\})$ et $b = (\top, \{p : \bot, q : \top\})$. Dans le modèle $M|_a$ il n'y a qu'un monde où $p$ et $q$ sont vrais et donc $p \rightarrow q$ est vrai également. Dans le modèle $M|_b$ il n'y a un seul monde où $q$ est vrai et donc $p \rightarrow q$ est vrai aussi. On a alors depuis le modèle $M : M, w \models K_{\alpha}AX(p \rightarrow q)$.

L'action $a$ a une valeur pour la propriété $p$ de $v_a(M^w, \alpha, p, 1) = 1$ et l'action $b$ une valeur de $v_b(M^w, \alpha, p, 1) = 0$. On a donc $M, w \models I_{\alpha}^a Xp$.
<figure><img src="image_19.png" /><figcaption>FIGURE 3.5 – Exemple pour la proposition 1.5</figcaption></figure>

L'action $a$ a une valeur pour la propriété $q$ de $v_a(M^w, \alpha, q, 1) = 1$ et l'action $b$ une valeur de $v_b(M^w, \alpha, q, 1) = 1$. Nous n'avons donc pas $M, w \models I_\alpha^a Xq$ puisque $\text{Best}(M^w, \alpha, q, 1) = A_{\alpha,w}^l$.
En résumé, on a bien $M, w \models I_\alpha^a Xp \wedge K_\alpha(AX)(p \to q)$ mais on a pas $M, w \models I_\alpha^a Xq$.

**Proposition 1.6 : cohérence**

$$ \models \neg I_{\alpha}^{a} X^{k} \perp $$

**Preuve :** Par définition, on a $M, w \models K_\alpha(AXK_\alpha)^k \top$, ce qui implique d'après le lemme 3 que $\text{Best}(M^w, \alpha, \perp, k) = A_{\alpha,w}^l$. Or par définition si $\text{Best}(M^w, \alpha, \perp, k) = A_{\alpha,w}^l$ alors $\models \neg I_\alpha^a X^k \perp$.

**Proposition 1.7 : non-serialité**

$$ \models \neg I_{\alpha} a X^{k} \phi \rightarrow \neg I_{\alpha} a X^{k} \neg \phi \text{ pour } k \geq 2 $$

<figure><img src="image_20.png" /><figcaption>FIGURE 3.6 – Exemple pour la proposition 1.7</figcaption></figure>
**Preuve** : Afin de montrer cette invalidité, un contre-exemple suffira et on le montrera pour $k=2$. L'exemple est présenté en figure 3.6. Il y a un seul joueur et cinq actions $a, b, c, d$ et $e$. Elles sont définies comme : $a = (\neg p \lor \neg q, \{p : \top, q : \top\})$, $b = (\neg p \lor \neg q, \{p : \top, q : \bot\})$, $c = (\neg p \lor \neg q, \{p : \bot, q : \top\})$, $d = (p, \{p : \top, q : \bot\})$ et $e = (q, \{p : \bot, q : \top\})$.

Dans cet exemple, depuis le modèle initial $M$ nous avons trois actions légales $a, b$ et $c$ qui mène vers les modèles $M|_a, M|_b$ et $M|_c$.

Dans le modèle $M|_a$ nous avons deux actions légales $d$ et $e$ qui amènent vers les modèles $M|_{a,d}$ et $M|_{a,e}$. Dans le modèle $M|_{a,d}$ la formule $p$ est vraie dans le seul monde, la valeur à un tour du modèle $M|_a$ pour la formule $p$ est donc de $v(M^w|_a, \alpha, p, k) = 1$. Dans le modèle $M|_{a,e}$ la formule $p$ est fausse dans le seul monde, la valeur à 1 tour du modèle $M|_a$ pour la formule $\neg p$ est donc de $v(M^w|_a, \alpha, \neg p, k) = 1$. Les valeurs de l'action $a$ sont donc respectivement $v_a(M^w, \alpha, p, 2) = 1$ et $v_a(M^w, \alpha, \neg p, 2) = 1$.

Dans le modèle $M|_b$ nous avons une action légale $d$ qui amène vers le modèle $M|_{b,d}$. Dans le modèle $M|_{b,d}$ la formule $p$ est vraie dans le seul monde, la valeur à un tour du modèle $M|_b$ pour la formule $p$ est donc de $v(M^w|_b, \alpha, p, k) = 1$. Et la valeur du modèle $M|_b$ pour la formule $\neg p$ est alors $v(M^w|_b, \alpha, \neg p, k) = 0$. Les valeurs de l'action $b$ sont donc respectivement $v_b(M^w, \alpha, p, 2) = 1$ et $v_b(M^w, \alpha, \neg p, 2) = 0$.

Dans le modèle $M|_c$ nous avons une action légale $e$ qui amène vers le modèle $M|_{c,e}$. Dans le modèle $M|_{c,e}$ la formule $p$ est fausse dans le seul monde, la valeur à un tour du modèle $M|_c$ pour la formule $p$ est donc de $v(M^w|_c, \alpha, p, k) = 0$. Et la valeur du modèle $M|_c$ pour la formule $\neg p$ est alors $v(M^w|_c, \alpha, \neg p, k) = 1$. Les valeurs de l'action $c$ sont donc respectivement $v_c(M^w, \alpha, p, 2) = 0$ et $v_c(M^w, \alpha, \neg p, 2) = 1$.

On a alors $\text{Best}(M^w, \alpha, p, 2) = \{a, b\}$ et $\text{Best}(M^{w_1}, \alpha, \neg p, 2) = \{a, c\}$. Ceci implique que l'on a $M, w \models I_\alpha^a X(p)$ et $M, w \models I_\alpha^a X(\neg p)$

**Proposition 1.8 : interaction**

$$ \models I_{\alpha}^{a} X^{k} \phi \rightarrow K_{\alpha} I_{\alpha}^{a} X^{k} \phi $$

**Preuve** : Par définition la valeur d'une action est :

$$ v_{a_{\alpha}}(M^w, \alpha, \phi, k) = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|} $$

Cela implique $\forall w' \in [w]_{\alpha}, v_{a_{\alpha}}(M^{w'}, \alpha, \phi, k) = v_{a_{\alpha}}(M^w, \alpha, \phi, k)$. Ce qui amène à $\forall w' \in [w]_{\alpha}, \text{Best}(M^{w'}, \alpha, \phi, k) = \text{Best}(M^w, \alpha, \phi, k)$.

Par définition $\forall w' \in [w]_{\alpha}, A_{\alpha,w'}^l = A_{\alpha,w}^l$.

Ainsi si $a \in \text{Best}(M^w, \alpha, \phi, k)$ et $\text{Best}(M^w, \alpha, \phi, k) \neq A_{\alpha,w}^l$ alors $\forall w' \in [w]_{\alpha}$ on a $a \in \text{Best}(M^{w'}, \alpha, \phi, k)$ et $\text{Best}(M^{w'}, \alpha, \phi, k) \neq A_{\alpha,w'}^l$. Donc $M, w \models I_{\alpha}^a X^k \phi$ implique que $\forall w' \in [w]_{\alpha}$ on a $M, w' \models I_{\alpha}^a X^k \phi$. En d'autres termes $M, w \models I_{\alpha}^a X^k \phi$ implique $M, w \models K_{\alpha} I_{\alpha}^a X^k \phi$

**Proposition 1.9 : interaction**

$$ \models \neg I_{\alpha}^{a} X^{k} \phi \rightarrow K_{\alpha} \neg I_{\alpha}^{a} X^{k} \phi $$

**Preuve** : Par l'absurde si on a $M, w \models \neg I_{\alpha}^a X^k \phi$ et qu'il existe un monde $w' \in [w]_{\alpha}$ tel que $M, w' \models I_{\alpha}^a X^k \phi$ alors d'après la proposition 1.8 on aurait $M, w' \models K_{\alpha} I_{\alpha}^a X^k \phi$ et donc par définition de l'opérateur $K_{\alpha}, M, w \models I_{\alpha}^a X^k \phi$ ce qui contredit l'hypothèse de départ.
**Proposition 1.10 : indépendance de la syntaxe**

Depuis $\phi \leftrightarrow \psi$ déduire $I_{\alpha}^{a}X^{k}\phi \leftrightarrow I_{\alpha}^{a}X^{k}\psi$

**Preuve :** Si $|\phi| \leftrightarrow \psi$ alors $\forall M, \forall w, M, w, |\phi| \leftrightarrow M, w, |\psi|$.

Donc $\forall M, \forall w, \forall \alpha, pr_{M^w}^{\alpha}(\phi) = pr_{M^w}^{\alpha}(\psi)$.

Ainsi pour $k=1, \forall M, \forall w, \forall \alpha, \forall a_{\alpha} \in A_{\alpha,w}^{l}$ :

$$ 
\begin{aligned}
& \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{pr_{M^w_{c_j}}^{\alpha}(\phi)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|} \\
& = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{pr_{M^w_{c_j}}^{\alpha}(\psi)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|}
\end{aligned}
$$

C'est-à-dire $\forall M, \forall w, \forall \alpha, \forall a_{\alpha} \in A_{\alpha,w}^{l}, v_{a_{\alpha}}(M^{w}, \alpha, \phi, 1) = v_{a_{\alpha}}(M^{w}, \alpha, \psi, 1)$

Et par récurrence pour $k \ge 1, \forall M, \forall w, \forall \alpha, \forall a_{\alpha} \in A_{\alpha,w}^{l}$ :

$$ 
\begin{aligned}
& \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \phi, k-1)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|} \\
& = \sum_{w_i \in [w]_{\alpha}} \frac{1}{|[w]_{\alpha}|} \times \sum_{c_j = (a_1, \dots, a_{\alpha}, \dots, a_n) \in C_{w_i}^l} \frac{v(M_{|c_j}^{w_i}, \alpha, \psi, k-1)}{|A_{1,w_i}^l \times \dots \times \{a_{\alpha}\} \times \dots \times A_{n,w_i}^l|}
\end{aligned}
$$

C'est-à-dire $\forall M, \forall w, \forall \alpha, \forall a_{\alpha} \in A_{\alpha,w}^{l}, v_{a_{\alpha}}(M^{w}, \alpha, \phi, k) = v_{a_{\alpha}}(M^{w}, \alpha, \psi, k)$

Ce qui nous amène à Best($M^w, \alpha, \phi, k$) = Best($M^w, \alpha, \psi, k$) pour tout $w, \alpha, k$. Et donc on a $|\phi| \le I_{\alpha}^a X^k \phi$ si et seulement si $|\psi| \le I_{\alpha}^a X^k \psi$

**3.5 Limitations**

Cette première modélisation présente plusieurs limites sérieuses. Tout d'abord, on ne peut pas modéliser les actions de n'importe quel jeu. Les modèles d'évènements n'existent pas ici et avec eux la possibilité de gérer les actions semi-privées comme par exemple la pioche d'une carte par un joueur.

Certaines actions publiques ne sont également pas modélisables ici. En effet, certaines actions publiques demandent l'utilisation d'un modèle d'évènement. Par exemple lorsqu'un joueur pose une carte, les effets de cette action dépendent de la carte posée, donc du monde possible considéré. Ce type d'action peut être représenté par un modèle d'événement sans relation avec les actions. On peut parler de choix non-déterministe entre les actions ou bien d'action indéterminée.

Concernant le calcul de l'intention en lui-même, nous sommes partis du principe que l'autre joueur choisira aléatoirement l'une de ses actions. Cela peut suffire pour une première modélisation, mais a priori un agent ne fait pas des choix aléatoires. C'est d'autant plus vrai que nous cherchons justement à donner l'intention d'un agent dans le choix de ses actions.

Enfin, concernant l'intention, même si elle vérifie un certain nombre de principes intéressants, elle ne vérifie pas le principe de cohérence interne des intentions. Ce principe correspond au fait de ne pas avoir l'intention d'une chose et l'intention de son contraire. C'est une propriété que doit vérifier un opérateur d'intention.
# Deuxième modélisation

La modélisation présentée dans le chapitre précédent offre une première approche du calcul de l'in-
tention d'un agent. Cependant cette modélisation ne permet pas de modéliser l'ensemble des actions des
jeux, ni même les seules actions publiques. Une des améliorations apportée par la deuxième modélisation
est de pouvoir gérer toutes les actions publiques.

La première modélisation met également de côté la partie décisionnelle, non aléatoire des agents.
En effet, les agents ont des préférences dans le choix de leurs actions. Cette deuxième modélisation
propose de prendre en compte cette préférence en associant aux actions une valeur. Cette valeur peut être
rapprochée de la notion d'utilité de la théorie des jeux.

Cette deuxième modélisation a été présentée dans une première version à RJCIA 2019 [GCSLDL19]
et à ICAART 2020 [CGLd20].

Ce chapitre commence par une présentation du jeu Hanabi qui va nous servir régulièrement d'exemple
pour la suite de la thèse.

## 4.1 Hanabi

### 4.1.1 Présentation

Hanabi est un jeu de cartes coopératif au tour par tour. Il est composé de 50 cartes de 5 couleurs différentes, les 10 cartes de chaque couleur étant numérotées de 1 à 5 (trois cartes 1, deux cartes 2,3,4 et une carte 5). Le but du jeu est de former des piles de cartes d'une même couleur allant de 1 à 5. La particularité de ce jeu est que chaque joueur ne voit pas les cartes qu'il a en main mais voit les cartes détenues par tous les autres joueurs. Les joueurs peuvent se donner des informations afin de tenter de poser les bonnes cartes dans le bon ordre.

L'intérêt de ce jeu est l'importance du rôle joué par la connaissance des joueurs sur l'état du jeu. La connaissance de l'état du jeu n'est cependant pas une fin en soi, comme cela pourrait être le cas dans un jeu comme le cluedo. Ici la connaissance de l'état du jeu permet de préciser l'effet de la carte qui sera jouée et donc de prévoir l'efficacité de l'action qui sera effectuée.

On pourrait argumenter que dans la plupart des jeux de cartes, améliorer sa connaissance de l'état du jeu, c'est-à-dire connaître les cartes dans les mains des joueurs, augmente les chances de marquer plus de points. Mais donner un indice sur les cartes ne fait pas partie des règles de la plupart des jeux, ce qui ne laisse que le comptage des cartes pour augmenter ses connaissances. Par ailleurs, si l'on considère un jeu de 52 cartes classique simultané à 4 joueurs, chacun ayant 5 cartes, l'incertitude sur l'effet de la carte que l'on va jouer doit être combinée avec l'incertitude sur les 3 cartes jouées par les autres joueurs, parmi les 15 qu'ils ont en main, elles-mêmes prélevées parmi les 47 cartes inconnues restantes. De ce fait, le
nombre très grand de possibilités ne permet pas, en général, de baser sa stratégie sur la connaissance de l'état du jeu. À l'inverse, dans Hanabi, l'incertitude initiale porte sur les 4 cartes que l'on a en main parmi les 38 cartes encore inconnues, incertitude rapidement réduite par les informations reçues et les cartes jouées. En effet, les joueurs tentent de donner les indices les plus pertinents possibles afin d'inciter les autres joueurs à effectuer certaines actions de jeu.

Hanabi est donc un très bon candidat pour une étude de l'intention en logique épistémique.

### 4.1.2 Règles du jeu

Hanabi se joue de 2 à 5 joueurs, les joueurs recevant chacun cinq cartes s'il y a 2 ou 3 joueurs et quatre cartes s'il y a 4 ou 5 joueurs. Les joueurs doivent placer leurs cartes de façon à ce que les autres joueurs puissent les voir mais qu'eux-mêmes ne puissent pas les voir. Il y a aussi 8 jetons pour les indices et 3 jetons pour les échecs.

Sur la table il ne peut y avoir qu'une seule pile de chaque couleur et les cartes doivent être posées dans l'ordre ascendant (1, 2, 3, 4 puis 5). Il ne peut y avoir qu'une carte de chaque valeur (5 au total) dans une pile. Ces piles de cartes sont appelées dans le jeu « feux d'artifice ». Les joueurs jouent à leur tour les uns après les autres dans le sens des aiguilles d'une montre. Lorsqu'un joueur prend son tour, il a le choix entre trois actions : donner un indice, poser une carte ou défausser une carte.

**Donner un indice** : le joueur qui donne l'indice peut indiquer à un autre joueur uniquement la valeur ou bien la couleur d'un ensemble de cartes de sa main. Il doit obligatoirement lui indiquer toutes les cartes ayant cette caractéristique. En faisant cela, les joueurs perdent un jeton indice. Si les joueurs ont utilisé tous les jetons indices alors donner un indice devient une action illégale dans le jeu.

**Défausser une carte** : le joueur défausse une carte de sa main. Il la pose dans la pile de défausse, face visible, reprend une nouvelle carte dans la pioche qu'il place dans sa main et les joueurs regagnent alors un jeton indice (sauf s'ils en ont déjà huit).

**Poser une carte** : un joueur peut choisir une carte de sa main pour tenter de la poser. La carte peut être posée sil est possible de l'ajouter à une pile existante ou de démarrer une pile d'une nouvelle couleur avec elle. Si la carte posée est un 5, alors elle complète un feu d'artifice et les joueurs regagnent un jeton indice. Si la carte ne peut pas être posée, alors le joueur défausse la carte et les joueurs perdent un jeton échec.

Les joueurs remportent la victoire s'ils ont terminé les cinq feux d'artifice, avec 25 points (1 point par carte posée).

Si un joueur prend la dernière carte de la pioche, chaque joueur ne peut alors rejouer qu'une seule fois avant la fin de la partie. Une fois leurs tours joués, les joueurs comptent le nombre de cartes faisant partie des feux d'artifice (celles qui ont été posées), c'est le score final.

La partie s'arrête aussi si les joueurs perdent leurs 3 jetons échecs, le score final est aussi le nombre de cartes posées sur la table.

Évidemment le jeu interdit les communications entre les joueurs autrement que par les indices qu'ils se donnent.

### 4.1.3 Simplification et logique épistémique

Afin de rendre plus facile la description et l'explication des exemples modélisés en logique épistémique, nous allons utiliser une version très simplifiée de Hanabi : il n'y a plus que trois cartes 1,2,3, deux jetons indices, un jeton échec et deux joueurs J1 et J2. Cet exemple simplifié de Hanabi est courant, on peut le retrouver dans l'article [EMNT18] par exemple. La situation initiale est la suivante : J1 reçoit la carte 1, J2 reçoit la carte 2 et il reste donc dans la pioche la carte 3. La modélisation de cet état initial est représentée en figure 4.1
<figure><img src="image_21.png" /><figcaption>FIGURE 4.1 – Modèle épistémique du jeu simplifié Hanabi</figcaption></figure>

Pour ce qui concerne le joueur J1, il voit la carte 2 dans la main du joueur J2, il imagine donc deux mondes possibles : le monde $w_1$ où il possède la carte 1 et le monde $w_2$ où il possède la carte 3. Si le joueur J1 possède la carte 1, le joueur J2 se dit qu'il a soit la carte 2, soit la carte 3, situation correspondant au monde $w_1$ et au monde $w_6$. Mais si le joueur J1 possède la carte 3, alors le joueur J2 pense avoir la carte 2 ou la carte 1, ce qui correspond aux mondes $w_2$ et $w_3$. Et ainsi de suite... voir section 1.3.4 pour plus d'explications sur les autres mondes.

## 4.2 Action indéterminée

Afin d'illustrer le problème rencontré par la première modélisation pour traiter les actions publiques, nous allons reprendre l'exemple du jeu simplifié de Hanabi (voir figure 4.1).

Pour rappel, les joueurs ne voient pas leur carte, le joueur 1 a la carte 1, le joueur 2 a la carte 2 et dans la pioche se trouve la carte 3. Nous dirons ici que c'est le tour du joueur 1, celui-ci peut poser sa carte, défausser sa carte ou bien donner un indice au joueur 2. N'étant pas le tour du joueur 2, celui-ci ne peut exécuter que l'action *noop* (ne rien faire).

Le joueur 1 choisit de poser sa carte. En DEL classique, étant donné que le monde réel est le monde où le joueur 1 possède la carte 1, cette action est simplement celle où la carte 1 est effectivement posée sur la table. Cette action nommée $a_1$ a pour précondition $pre(a_1) = (J1 : 1)$ et pour postcondition en version simplifiée $post(a_1) = \{(J1 : 1) : \perp, (T : 1) : \top\}$. L'effet de cette action est de supprimer les mondes où le joueur 1 n'avait pas la carte 1 et ensuite de faire passer la carte 1 de la main du joueur 1 vers la table.

Cependant, ici nous cherchons à calculer l'intention d'un agent à travers son regard sur le monde. Pour le joueur 1, il y a deux mondes possibles, celui où il a la carte 1 et celui où il a la carte 3 : les mondes $w_1$ et $w_2$. L'action de poser peut avoir deux effets différents : soit le joueur a la carte 1 et celle-ci va sur la table, soit il a la carte 3 et comme la carte 2 n'est pas posé, la carte 3 va dans la défausse. L'effet de l'action est donc indéterminé. Dans le calcul de l'intention, il faut prendre en compte ces deux
possibilités car c'est de cette façon que le joueur 1 se représente le jeu.

Afin de pouvoir représenter cette action, l'idée est de reprendre en partie le modèle d'événement des actions semi-privées sans les relations entre les actions. L'action d'un joueur sera donc composée d'un ensemble d'actions atomiques et on appellera cet ensemble une action atomique indéterminée. On se passe des relations entre les actions car celles-ci n'existent pas. Les joueurs ne savent pas forcément quelle action sera effectuée avant mais les effets étant distinguables, les actions seront elles aussi distinguables. Les actions n'étant pas indistinguishables, il n'y a pas besoin d'utiliser de relations d'instinguabilité entre les actions.

L'action atomique indéterminée dans cet exemple est composée de l'action atomique $a_1$ et de l'action atomique $a_3$. L'action atomique $a_3$ est définie comme suit $a_3 = (J1 : 3, \{(J1 : 3) : \perp, (D : 3) : \top\}, e : \top)$, jouer la carte 3 à ce moment-ci donnant un jeton échec. On note $a_{13}^i = \{a_1, a_3\}$ l'action indéterminée décrivant l'action de poser la carte pour le joueur 1.

Il faut aussi composer avec l'action du joueur 2 pour former l'action complète indéterminée. Comme pour l'action complète classique, nous devons fusionner les actions atomiques indéterminées de chaque agent. Nous allons suivre les règles de la définition 15. Ici, l'action indéterminée du joueur 1 est formée de deux actions atomiques et l'action indéterminée du joueur 2 est formée d'une seule action atomique (noop). L'action complète indéterminée sera donc formée de 2 × 1 actions complètes. Ces deux actions sont $c_1 = ((J1 : 1), \{(J1 : 1) : \perp, (T : 1) : \top\})$ et $c_3 = (J1 : 3, \{(J1 : 3) : \perp, (D : 3) : \top\}, e : \top)$ et on note $c_{13}^i = \{c_1, c_3\}$ l'action complète indéterminée formée de ces deux actions complètes.

<figure><img src="image_22.png" /><figcaption>FIGURE 4.2 – Effet de l'action $c_{13}^i$</figcaption></figure>

Lorsque le joueur 1 pose sa carte, il imagine deux possibilités, celle où le monde réel est le monde $w_1$ et celle où le monde réel est le monde $w_2 : M^{w_1}$ et $M^{w_2}$. Dans le cas où le monde $w_1$ est le monde réel, c'est l'action $c_1$ qui est réalisée lorsque les joueurs jouent l'action $c_{13}^i$. En effet, dans le modèle $M^{w_1}$,
le monde réel $w_1$ vérifie la précondition de l'action $c_1$ mais pas de l'action $c_3$. Comme pour la première
modélisation, on dira que l'action $c_3$ n'est alors pas jouable dans ce modèle. On passe alors du modèle
$M^{w_1}$ au modèle $M_{c_13}^{w_1}$ (voir définition 5). Dans ce modèle, il y a deux mondes indistinguishables pour le
joueur 2, celui-ci ne connaissant toujours pas sa carte et le monde réel est le monde $w_1$.

Dans le cas où le monde $w_2$ est le monde réel, c'est l'action $c_3$ qui est réalisée. On passe du modèle $M^{w_2}$ au modèle $M_{c_13}^{w_2}$. Dans ce modèle, il y a deux mondes indistinguishables pour le joueur 2 et le monde réel est $w_2$. L'effet de l'action $c_{13}^i$ est représenté en figure 4.2.

Afin de simplifier l'utilisation des actions indéterminées, on cherchera à ce qu'une seule action soit
jouable par action indéterminée pour chaque modèle. Cela sera justifié dans la section 4.4.1. Il faut donc
vérifier que deux actions complètes d'une même action complète indéterminée ne voient pas leur pré-
condition vérifiée par un même monde. C'est bien le cas ici, néanmoins, afin de garantir l'unicité de
la jouabilité, on obligera à présent les préconditions des actions atomiques indéterminées à être insatis-
fiables entre elles. De cette manière, on est sûr, quel que soit le modèle, qu'une seule action complète ne
peut être jouée.

Cependant, ceci empêchera de modéliser toutes les actions publiques. Par exemple, l'action de jeter
un dé à six faces n'est pas modélisable. En effet, chacune des six sorties est possible, l'action indé-
terminée qui la modélisera devrait voir les préconditions des six actions atomiques vérifiées. L'action
indéterminée ne respecterait donc pas la contrainte des préconditions insatisfiables entre elles. Mais cela
n'empêchera pas de modéliser tous les jeux à actions publiques. En effet, on peut représenter les six
sorties possibles d'un lancer de dé dans un modèle avec un seul monde par un modèle où il y a six
mondes indistinguishables. Les six mondes représentant les six sorties possibles, le lancer de dé ne serait
alors qu'une projection sur le monde « réel ».

La définition d'une action atomique indéterminée par un agent se fait alors comme suit :

**Définition 20 (action atomique indéterminée)** Soit $J = (\mathbb{P}, A, N)$ une signature d'un jeu, soit $\alpha$ un agent et une fonction $g$ d'association des actions indéterminées de $N$ vers $2^{2^A}$, on note $a^i$ action atomique indéterminée les éléments de $g(\alpha) = A_\alpha$ vérifiant $\forall a_j, a_k \in a^i, \text{pre}(a_j) \wedge \text{pre}(a_k) \equiv \perp$. On note $A_\alpha^i$ l'ensemble des actions atomiques indéterminées de l'agent $\alpha$.

La définition de l'action complète indéterminée reprend la définition 15 de l'action complète.

**Définition 21 (action complète indéterminée)** Soit $J = (\mathbb{P}, A, N)$ une signature d'un jeu, soit $\alpha$, une fonction $g$ d'association des actions de $N$ vers $2^{2^A}$, soit $(a_1^i, ..., a_n^i) \in \times_{\alpha \in N} A_\alpha^i$ un n-uplet d'actions atomiques indéterminées de chaque agent.

On note $c^i$ l'action complète indéterminée issue de $(a_1^i, ..., a_n^i)$, l'ensemble d'actions complètes suivant : $c^i = \{c = (a_1, ..., a_n) \in \times_{\alpha \in N} a_\alpha^i\}$.

On note $C^i$ l'ensemble formé de toutes les actions complètes indéterminées issues de tous les n-uplets d'actions atomiques indéterminées de $\times_{\alpha \in N} A_\alpha^i$.

Soit $a_\alpha^i$ une action atomique indéterminée de l'agent $\alpha$, soit $c^i$ une action complète indéterminée issue de $(a_1^i, ..., a_n^i)$, on dit que $c^i$ est issu de $a_\alpha^i$ si $(a_1^i, ..., a_n^i) \in A_1^i \times \dots \times \{a_\alpha^i\} \times \dots \times A_n^i$. On note $C^i(a_\alpha^i)$ l'ensemble des actions complètes indéterminées issues de $a_\alpha^i$.

Pour rappel, la précondition d'une action complète est la conjonction des préconditions des actions
atomiques la composant. Les préconditions des actions atomiques d'un même agent sont insatisfiables
entre elles. Donc les préconditions des actions complètes d'une même action complète indéterminée sont
également insatisfiables entre elles. Cela nous assure qu'une seule action complète est légale par modèle.

La définition d'un modèle change pour intégrer la nouvelle fonction $g$.

**Définition 22 (modèle)** Soit $J = (\mathbb{P}, A, N)$ une signature d'un jeu, un modèle est un 5-uplet $M = (W, R, \pi, f_r, g)$ où
— *W* est un ensemble non vide de mondes possibles

— *R* est un ensemble de relations d'équivalence sur *W*

— $\pi$ est une fonction de valuation de $\mathbb{P}$ vers $2^W$

— $f_r$ est une fonction de $N$ vers $R$

— *g* est une fonction d'association des actions indéterminées de *N* vers 2<sup>2A</sup>

On note $M^w$ le modèle dont le monde réel est $w$.

Enfin, il nous faut définir l'effet d'une action complète indéterminée. Pour rappel, l'effet d'une action complète indéterminée sur un modèle est l'effet de l'action complète dont la précondition est vérifiée dans le monde réel du modèle. La définition reprend la définition 5 de l'exécution d'une action.

**Définition 23 (exécution d'une action complète indéterminée)** Soit une signature de jeu

$J = (\mathbb{P}, A, N)$, un modèle $M^w = (W, R, \pi, f_r, g)$, soit $c^i = \{c_j\}_{1\ge j\ge m}$ une action complète indéterminée, l'exécution de $c^i$ dans le modèle $M^w$ donne le modèle $M^w|_{c^i}$ tel que :

— s'il existe $c_j \in c^i$ tel que $|\cdot|_{M^w} \text{ pre}(c_j)$ alors $M^w|_{c^i} = M^w|_{c_j}$

— sinon on note $d = (\bot, \{p : p, \forall p \in \mathbb{P}\})$ l'action destruction et on l'applique : $M^w|_{c^i} = M^w|_d$

**4.3 Utilité**

Un deuxième problème de la première modélisation était que l'on ne prenne pas en compte le fait que les autres joueurs pouvaient préférer une action plutôt qu'une autre. En effet, dans cette première modélisation, d'après le joueur étudié, les autres joueurs choisissaient leurs actions de manière équitable. C'est une première approximation que nous allons améliorer ici en introduisant un paramètre mesurant la préférence d'un joueur à choisir une action plutôt qu'une autre. Étant donné que l'on se place dans l'esprit d'un agent pour mesurer son intention, ce paramètre mesure en fait la préférence d'un autre joueur d'après cet agent. La connaissance du joueur sur les connaissances du monde et des autres joueurs aura donc à nouveau une place importante.

Nous appellerons ce paramètre *utilité* car il se rapproche de la notion d'utilité en théorie des jeux. En effet, dans cette modélisation on partira du principe qu'un joueur choisira forcément une action d'utilité maximale. Cependant, ce paramètre diffère de l'utilité de la théorie des jeux pour deux raisons. Premièrement il ne concerne qu'une action et non pas la stratégie entière (c'est-à-dire l'ensemble des actions que le joueur effectuera jusqu'à la fin du jeu). Deuxièmement, ce paramètre ne sera pas forcément égal au score espéré par le joueur. On ne calcule pas la véritable utilité car on part du principe que les joueurs ne sont pas en mesure de le faire, d'où l'idée de suivre les intentions pas à pas des joueurs pendant le jeu.

En théorie des jeux, l'utilité d'une stratégie est en général donnée, il n'est pas nécessaire de savoir comment la calculer pour étudier un exemple. Dans cette modélisation il ne sera pas non plus nécessaire de connaître le calcul d'une utilité pour étudier un exemple, elle sera considérée comme donnée. En effet, l'agent peut avoir des caractéristiques particulières pouvant affecter l'importance qu'il accorde à certaines actions. Par exemple une intelligence artificielle qui évite par construction d'utiliser sa tour aux échecs ou bien un joueur humain qui n'aimerait pas jouer une carte noire.

Nous allons tout de même proposer une utilité particulière qui correspondrait au cas général, ceci permettant de proposer une modélisation « complète » de l'intention et aussi de comprendre les exemples qui seront présentés.