diff options
| -rw-r--r-- | notes-mitro206.tex | 217 |
1 files changed, 182 insertions, 35 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 25279c8..72876d7 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -95,20 +95,20 @@ quelques unes de ces théories des jeux. \thingy Une tentative pour approcher la notion de jeu mathématique : le jeu possède un \textbf{état}, qui évolue dans un ensemble (fini ou -infini) d'états possibles ; un certain nombre de \textbf{joueurs} -choisissent, simultanément ou consécutivement, un \textbf{coup} à -jouer parmi différentes \textbf{options}, en fonction de l'état -courant, ou peut-être seulement d'une fonction de l'état courant ; ce -coup peut éventuellement faire intervenir un aléa (hasard voulu par le -joueur) ; l'état du jeu évolue en fonction des coups des joueurs et -éventuellement d'un autre aléa (hasard intrinsèque au jeu) ; au bout -d'un certain nombre de coups (fini ou infini), la règle du jeu -attribue, en fonction de l'état final, ou de son évolution complète, -un \textbf{gain} à chaque joueur, ce gain pouvant être un réel (gain -numérique), l'étiquette « gagné » / « perdu », ou encore autre chose, -et chaque joueur cherche en priorité à maximiser son gain (i.e., à -gagner le plus possible, ou à gagner tout court), ou dans le cas -probabiliste, son espérance de gain. +infini) d'états ou \textbf{positions} possibles ; un certain nombre de +\textbf{joueurs} choisissent, simultanément ou consécutivement, un +\textbf{coup} à jouer parmi différentes \textbf{options}, en fonction +de l'état courant, ou peut-être seulement d'une fonction de l'état +courant ; ce coup peut éventuellement faire intervenir un aléa (hasard +voulu par le joueur) ; l'état du jeu évolue en fonction des coups des +joueurs et éventuellement d'un autre aléa (hasard intrinsèque au +jeu) ; au bout d'un certain nombre de coups (fini ou infini), la règle +du jeu attribue, en fonction de l'état final, ou de son évolution +complète, un \textbf{gain} à chaque joueur, ce gain pouvant être un +réel (gain numérique), l'étiquette « gagné » / « perdu », ou encore +autre chose, et chaque joueur cherche en priorité à maximiser son gain +(i.e., à gagner le plus possible, ou à gagner tout court), ou dans le +cas probabiliste, son espérance de gain. Mais même cette définition très vague est incomplète !, par exemple dans le cas des jeux différentiels, les coups n'ont pas lieu tour à @@ -138,7 +138,7 @@ ne connaissent pas toute la règle du jeu (voir « information \thingy Le \textbf{nombre de joueurs} est généralement $2$. On peut néanmoins étudier des jeux multi-joueurs, ce qui pose des questions d'alliances et compliquer la question des buts (un joueur peut être -incapable de gagner lui-même mais être en position de décider quel +incapable de gagner lui-même mais être en situation de décider quel autre joueur gagnera : on parle de « kingmaker »). On peut aussi étudier des jeux à un seul joueur (jouant contre le hasard), voire à zéro joueurs (systèmes dynamiques), mais ceux-ci relèvent plutôt @@ -197,15 +197,16 @@ on ne considérera que des jeux à information complète [et toute occurrence des mots « information complète » sera probablement un lapsus pour « information parfaite »].) -\thingy Le nombre de positions, comme le nombre d'options dans une -position donnée, ou comme le nombre de coups, peut être \textbf{fini - ou infini}. Même si l'étude des jeux finis (de différentes -manières) est la plus intéressante pour des raisons pratiques, toutes -sortes de jeux infinis peuvent être considérés, par exemple en logique -(voir plus loin sur l'axiome de détermination). Pour un jeu à durée -infinie, le gagnant pourra être déterminé, par exemple, par toute la -suite des coups effectués par les deux joueurs ; on peut même -introduire des coups après un nombre infini de coups, etc. +\thingy Le nombre de positions (= états possibles), comme le nombre +d'options dans une position donnée, ou comme le nombre de coups, peut +être \textbf{fini ou infini}. Même si l'étude des jeux finis (de +différentes manières) est la plus intéressante pour des raisons +pratiques, toutes sortes de jeux infinis peuvent être considérés, par +exemple en logique (voir plus loin sur l'axiome de détermination). +Pour un jeu à durée infinie, le gagnant pourra être déterminé, par +exemple, par toute la suite des coups effectués par les deux joueurs ; +on peut même introduire des coups après un nombre infini de coups, +etc. De même, l'ensemble des positions, des options ou des temps peut être \textbf{discret ou continu}. Dans ce cours, on s'intéressera presque @@ -273,7 +274,7 @@ nul ; sinon, papier gagne sur pierre, ciseaux gagne sur papier et pierre gagne sur ciseaux (l'intérêt étant qu'il s'agit d'un « ordre » cyclique, totalement symétrique entre les options). Il s'agit toujours d'un jeu à somme nulle (disons que gagner vaut $+1$ et perdre -vaut $-1$), et cette fois les deux joueurs sont en position +vaut $-1$), et cette fois les deux joueurs sont en situation complètement symétrique. On verra que la meilleure stratégie possible consiste à choisir chacune des options avec probabilité $\frac{1}{3}$ (ceci assure une espérance de gain nul quoi que fasse l'autre joueur). @@ -366,14 +367,34 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vivien qui en a une. +\thingy\label{introduction-graph-game} Le jeu d'un graphe : soit $G$ +un graphe orienté (cf. \ref{definitions-graphs} ci-dessous pour la +définition) et $x_0$ un sommet de $G$. Partant de $x_0$, Alice et Bob +choisissent tour à tour une arête à emprunter pour arriver dans un +nouveau sommet (c'est-à-dire : Alice choisit un voisin sortant $x_1$ +de $x_0$, puis Bob un voisins ortant $x_2$ de $x_1$, puis Alice $x_3$ +de $x_2$ et ainsi de suite). \emph{Le perdant est celui qui ne peut + plus jouer}, et si ceci ne se produit jamais (si on définit un +chemin infini $x_0, x_1, x_2, x_3,\ldots$) alors la partie est +déclarée nulle (ceci ne peut pas se produire lorsque le graphe $G$ est +« bien-fondé »). On verra qu'il s'agit là du cadre général dans +lequel on étudie la théorie combinatoire des jeux impartiaux à +information parfaite +(cf. \ref{definition-impartial-combinatorial-game}). + +Dans une variante du jeu, celui qui ne peut plus jouer gagne au lieu +de perdre : on parle alors de la variante « misère » du jeu. + \thingy Le \textbf{jeu de Nim} : un certain nombre d'allumettes sont arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob retirent des alumettes, au moins une à chaque fois, et autant qu'ils veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui retire la dernière allumette (de façon équivalente, le perdant est celui qui ne peut pas jouer). Il s'agit ici d'un jeu à deux joueurs -impartial à connaissance parfaite : on verra que la théorie de Grundy -permet de décrire exactement la stratégie gagnante (et pour qui). +impartial à connaissance parfaite (un cas particulier du jeu général +défini en \ref{introduction-graph-game}) : on verra que la théorie de +Grundy permet de décrire exactement la stratégie gagnante (et pour +qui). \subsection{Remarques} @@ -765,7 +786,7 @@ compact $C_0 \neq \varnothing$ inclus dans $C$. \subsection{Graphes orientés bien-fondés} -\begin{defn} +\begin{defn}\label{definitions-graphs} Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit @@ -1060,16 +1081,24 @@ On verra que la notion de fonction de Grundy, et particulièrement le fait que la valeur soit nulle ou pas, a énormément d'importance dans l'étude de la théorie des jeux impartiaux. + +\subsection{Écrasement transitif} + \begin{defn}\label{definition-transitive-collapse} Soit $G$ un graphe orienté bien-fondé. En utilisant le théorème \ref{well-founded-definition} (modulo la remarque qui suit), on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) : -y\in\outnb(x)\}$. L'image de $G$ par la fonction $f$ (c'est-à-dire +y\in\outnb(x)\}$. L'image $f(G)$ de $G$ par la fonction $f$ (c'est-à-dire l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que $f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe orienté) s'appelle l'écasement transitif du sommet $x$. + +On considérera l'écrasement $f(G)$ de $G$ comme un graphe orienté, en +plaçant une arête de $u$ vers $v$ lorsque $v \in u$ ; autrement dit, +lorsque $v = f(y)$ et $u = f(x)$ pour certains $x,y$ de $G$ tels qu'il +existe une arête de $x$ vers $y$. \end{defn} \thingy En particulier, un puits a pour écrasement $\varnothing$, un @@ -1079,6 +1108,11 @@ que de tels sommets a pour écrasement $\{\{\varnothing\}\}$ tandis que s'il a aussi des sommets terminaux pour voisins sortants ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$, et ainsi de suite. +La terminologie « transitif » fait référence au fait qu'un ensemble +$E$ est dit transitif lorsque $v \in u\in E$ implique $v \in E$ (de +façon équivalente, $E \subseteq \mathscr{P}(E)$ où $\mathscr{P}(E)$ +est l'ensemble des parties de $E$) : c'est le cas de $f(G)$ ici. + Il y a une subtilité ensembliste dans la définition ci-dessus, c'est qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel $f$ prend sa valeur : il faut en fait appliquer une généralisation @@ -1093,7 +1127,12 @@ sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x) = \outnb(x')$) sont égaux. \end{defn} -\begin{prop} +Pour bien comprendre et utiliser la définition ci-dessus, il est +pertinent de rappeler que \emph{deux ensembles sont égaux si et + seulement si il sont les mêmes éléments} (\textbf{axiome + d'extensionalité}). + +\begin{prop}\label{extensional-iff-collapse-injective} Un graphe orienté bien-fondé est extensionnel si et seulement si sa fonction d'écrasement $f$ définie en \ref{definition-transitive-collapse} est injective. @@ -1104,13 +1143,121 @@ particulier $f(x) = f(x')$ (puisque $f(x)$ est définie comme l'image par $f$ de $\outnb(x)$), donc $x = x'$. Ceci montre que $G$ est extensionnel. -Réciproquement, $G$ extensionnel et montrons par induction bien-fondée que $f$ -est injective sur l'aval de tout sommet $x$. Soit $P$ l'ensemble des -$x$ tels que $f$ restreinte à l'aval de $x$ soit injective. Soit $x$ -un sommet dont tous les voisins sortants appartiennent à $P$ : -\textcolor{red}{à finir.} +Réciproquement, $G$ extensionnel et montrons que $f$ est injective, +c'est-à-dire que $f(x) = f(x')$ implique $x = x'$. On va procéder par +induction bien-fondée sur le graphe $G^2$ dont les sommets sont les +couples $(x,x')$ de sommets de $G$, avec une arête de $(x,x')$ vers +$(y,y')$ lorsqu'il y en a de $x$ vers $y$ \emph{et} de $x'$ +vers $y'$ : il est clair que $G^2$ est bien-fondé ; soit $P$ +l'ensemble des sommets $(x,x')$ de $G^2$ tels que $f(x) = f(x')$ +implique $x=x'$ (autrement dit, l'ensemble des sommets tels que +$(x,x')$ tels que $x=x'$ \emph{ou bien} $f(x) \neq f(x')$). Soit +$(x,x')$ un sommet de $G^2$ dont tous les voisins sortants vérifient +l'hypothèse d'induction (i.e., appartiennent à $P$) : on suppose $f(x) += f(x')$ et on veut montrer $x = x'$ pour pouvoir conclure $P = G^2$. +Or $f(x) \subseteq f(x')$ signifie que tout $f(y) \in f(x)$ appartient +à $f(x')$, c'est-à-dire que pour tout voisin sortant $y$ de $x$ il +existe un voisin sortant $y'$ de $x'$ pour lequel $f(y) = f(y')$, et +l'hypothèse d'induction montre alors $y = y'$ : ainsi, $\outnb(x) +\subseteq \outnb(x')$, et par symétrie, $f(x) = f(x')$ montre +$\outnb(x) = \outnb(x')$ donc, par extensionalité de $G$, on a $x = +x'$ comme on le voulait. \end{proof} +\thingy Si $G$ est un graphe orienté (non nécessairement bien-fondé), +et si $\sim$ est une relation d'équivalence sur l'ensemble des sommets +de $G$, on peut définir un \emph{graphe quotient} $G/\sim$ dont les +sommets sont les classes d'équivalences pour $\sim$ de sommets de $G$ +et dont les arêtes sont les couples $(\bar x,\bar y)$ de classes +telles qu'il existe une arête $(x,y)$ (i.e., de $x$ vers $y$) dans $G$ +avec $\bar x$ classe de $x$ et $\bar y$ celle de $y$ ; si ce graphe +est extensionnel, on peut dire abusivement que $\sim$ l'est : +concrètement, cela signifie que pour tous $x,x' \in G$, si pour chaque +voisin sortant $y$ de $x$ il existe un voisin sortant $y'$ de $x'$ +avec $y \sim y'$ et que la même chose vaut en échangeant $x$ et $x'$, +alors $x \sim x'$. Une intersection quelconque de relations +d'équivalence extensionnelles sur $G$ est encore une relation +d'équivalence extensionnelle, donc il existe une plus petite relation +d'équivalence extensionnelle $\equiv$ sur $G$, c'est-à-dire un plus +grand quotient $G/\equiv$ de $G$ qui soit extensionnel (« plus grand » +au sens où tout quotient de $G$ par une relation d'équivalence se +factorise à travers ce quotient $G/\equiv$). + +Le contenu essentiel de la +proposition \ref{extensional-iff-collapse-injective} est que +l'écrasement transitif $f(G)$ d'un graphe $G$ bien-fondé réalise ce +plus grand quotient extensionnel $G/\equiv$ : la relation $f(x) = +f(x')$ sur $G$ est précisément la plus petite relation d'équivalence +extensionnelle $\equiv$ sur $G$ (en effet, la relation $f(x) = f(x')$ +est évidemment extensionnelle, donc contient $\equiv$ par définition +de celle-ci, mais l'écrasement de $G/\equiv$ est le même que celui +de $G$, et comme la fonction d'écrasement est injective sur +$G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$). + + +\subsection{Jeux impartiaux à information parfaite} + +\begin{defn}\label{definition-impartial-combinatorial-game} +Un jeu \textbf{impartial à information parfaite} est un graphe +orienté $G$ muni d'un sommet $x_0$ appelé \textbf{position initiale} +et vérifiant de plus : +\begin{itemize} +\item pour un jeu « court » : $G$ est fini acyclique (ou de façon + équivalente, fini et bien-fondé) ; +\item pour un jeu « terminant » : $G$ est bien-fondé ; +\item pour un jeu « fini à boucles » : $G$ est fini. +\item pour un jeu « non nécessairement terminant » : (aucune + hypothèse). +\end{itemize} +On supposera de plus que tout sommet de $G$ est accessible à partir +de $x_0$ (si ce n'est pas le cas, il reviendra au même de supprimer +tous les sommets inaccessibles, assurant du coup cette hypothèse). +\end{defn} + +La terminologie est malheureusement peu standardisée : la plupart des +auteurs font implicitement une des deux hypothèses +(« bien-fondé »=« terminant », et/ou « fini ») sur le jeu $G$, le cas +« court » étant la conjonction des deux. Ici, on fera le plus souvent +l'hypothèse que $G$ est terminant. + +\begin{defn} +Pour un jeu $G$ comme +en \ref{definition-impartial-combinatorial-game}, une +\textbf{stratégie} est une fonction $\varsigma$ de $G$ vers $G \cup +\{\bot\}$ (où $\bot$ signifiant « forfait » ou « non-défini », est un +symbole n'appartenant pas à $G$) telle que $\varsigma(x)$ soit, pour +chaque $x$, un voisin sortant de $x$ ou bien $\bot$. + +Une \textbf{partie} de $G$ est une suite finie ou infinie $(x_i)$ de +sommets de $G$ telle que $x_0$ soit la position initiale et que pour +chaque $i$ pour lequel $x_{i+1}$ soit défini, ce dernier soit un +voisin sortant de $x_i$. Lorsque le dernier $x_i$ défini l'est pour +un $i$ pair, on dit qu'Alice perd et que Bob gagne, tandis que lorsque +le dernier $x_i$ défini l'est pour un $i$ impair, on dit qu'Alice +gagne et que Bob perd ; enfin, lorsque $x_i$ est défini pour tout +entier naturel $i$ (ce qui ne peut pas se produire si $G$ est +bien-fondé), on dit que la partie est nulle ou que les deux joueurs +survivent sans gagner. Lorsque de plus $\varsigma(x_i) = x_{i+1}$ +pour chaque $i$ pair pour lequel $x_i$ est défini (et en interprétant +$\bot$ comme « non-défini »), on dit qu'Alice a joué la partie selon +la stratégie $\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour +chaque $i$ impair pour lequel $x_i$ est défini, on dit que Bob a joué +la partie selon la stratégie $\tau$. + +Si $\varsigma$ et $\tau$ sont deux stratégies, on définit $\varsigma +\ast \tau$ comme la partie jouée lorsque Alice joue $\varsigma$ et Bob +joue $\tau$ : autrement dit, $x_0$ est la position initiale du jeu, +et, si $x_i$ est défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ si +$i$ est pair et $\tau(x_i)$ si $i$ est impair (en convenant que $\bot$ +signifie que le terme de la suite n'est pas défini et que la suite +s'arrête). + +La stratégie $\varsigma$ est dite \textbf{gagnante pour Alice} lorsque +Alice gagne toute partie où elle joue selon $\varsigma$. La stratégie +$\tau$ est dite \textbf{gagnante pour Bob} lorsque Bob gagne toute +partie où il joue selon $\tau$. +\end{defn} + % % % |