%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} % \theoremstyle{definition} \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } \newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} \newtheorem{thm}[comcnt]{Théorème} \newtheorem{cor}[comcnt]{Corollaire} \newtheorem{scho}[comcnt]{Scholie} \newtheorem{algo}[comcnt]{Algorithme} \renewcommand{\qedsymbol}{\smiley} % \newcommand{\outnb}{\operatorname{outnb}} \newcommand{\downstr}{\operatorname{downstr}} \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} % \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} % \DeclareFontFamily{U}{manual}{} \DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} \newcommand{\manfntsymbol}[1]{% {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} \newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % % % \begin{document} \title{Théorie(s) des jeux\\(notes provisoires)} \author{David A. Madore} \maketitle \centerline{\textbf{MITRO206}} {\footnotesize \immediate\write18{sh ./vc > vcline.tex} \begin{center} Git: \input{vcline.tex} \end{center} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pretolerance=8000 \tolerance=50000 % % % {\color{brown!70!black}\textbf{Version provisoire incomplète} de ces notes (voir la ligne « Git » ci-dessus pour la date de dernière modification). La numérotation \emph{devrait} ne pas changer, mais ce n'est pas complètement exclu.} \bigbreak \section{Introduction et typologie} \subsection{La notion de jeu mathématique : généralités} \thingy Il n'est pas possible de donner une définition générale précise de la notion de « jeu mathématique ». On verra plus loin des définitions précises de certains types de jeux (p. ex., les jeux impartiaux à information parfaite), mais il n'existe pas de définition générale utile qui s'applique à tous ces types, et à partir de laquelle on pourrait développer une théorie intéressante. Pire, différentes disciplines se sont développées sous le nom de « théorie des jeux », chacune donnant une définition différente de ce qu'est un « jeu ». Par exemple, l'étude des jeux « en forme normale » (=jeux définis par des matrices de gains), la théorie combinatoire des jeux (jeux à information parfaite), la théorie des jeux logiques, la théorie des jeux différentiels, etc. Il n'existe donc pas une mais plusieurs théories des jeux. Ces différentes théories des jeux intersectent différentes branches des mathématiques ou d'autres sciences : probabilités, optimisation/contrôle, combinatoire, logique, calculabilité, complexité, analyse/EDP ou encore (en-dehors ou en marge des mathématiques), économie, cryptographie, physique quantique, cybernétique, biologie, sociologie, linguistique, philosophie. Il va de soi qu'on ne pourra dans ce cours donner qu'un aperçu de 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 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 à tour mais continûment. Une \textbf{stratégie} d'un joueur est la fonction par laquelle il choisit son coup à jouer en fonction de l'état du jeu (ou de la fonction de l'état qui lui est présentée), et d'aléa éventuel. On peut ainsi résumer le jeu en : chaque joueur choisit une stratégie, et la règle du jeu définit alors un gain pour chaque joueur. Les stratégies peuvent être contraintes de différentes manières (par exemple : être calculables par une machine de Turing). Une stratégie est dite \textbf{gagnante} si le joueur qui l'utilise gagne le jeu (supposé avoir une notion de « joueur gagnant ») quels que soient les coups choisis par l'autre joueur. Il faut aussi se poser la question de si les joueurs peuvent communiquer entre eux (et si oui, s'ils peuvent prouver leur honnêteté ou s'engager irrévocablement quant au coup qu'ils vont jouer, etc.). Dans certains cas, on peut aussi être amené à supposer que les joueurs ne connaissent pas toute la règle du jeu (voir « information complète » ci-dessous). \subsection{Quelques types de jeux} \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 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 d'autres domaines. Dans ce cours, on s'intéressera (presque uniquement) aux jeux à deux joueurs. \thingy Les joueurs peuvent avoir \textbf{des intérêts communs, opposés, ou toute situation intermédiaire}. Le cas d'intérêts communs est celui où tous les joueurs ont le même gain. Si les joueurs peuvent parfaitement communiquer, on est alors essentiellement ramené à un jeu à un seul joueur : on s'intéresse donc ici surtout aux situations où la communication est imparfaite. Le cas de deux joueurs d'intérêts opposés est le plus courant : dans le cas de gains numériques, on le modélise en faisant des gains d'un joueur l'opposé des gains de l'autre — on parle alors de \textbf{jeu à somme nulle} ; ou bien la règle fera qu'un et un seul joueur aura gagné et l'autre perdu (mais parfois, elle peut aussi admettre le match nul). Toute autre situation intermédiaire est possible. Mais on conviendra bien que le but de chaque joueur est de maximiser son propre gain, sans considération des gains des autres joueurs. \thingy Le jeu peut être \textbf{partial/partisan ou impartial}. Un jeu impartial est un jeu où tous les joueurs sont traités de façon équivalente par la règle (le sens de « équivalent » étant à définir plus précisément selon le type de jeu). \thingy\label{intro-simultaneous-or-sequential} Les coups des joueurs peuvent avoir lieu \textbf{simultanément ou séquentiellement}. Formellement, il s'agit seulement d'une différence de présentation. On peut toujours ramener des coups séquentiels à plusieurs coups simultanés en n'offrant qu'une seule option à tous les joueurs sauf l'un, et réciproquement, on peut ramener des coups simultanés à des coups séquentiels en cachant à chaque joueur l'information de ce que l'autre a joué. La question \ref{question-preposing-moves} est cependant plus intéressante. \thingy Le jeu peut être à \textbf{information parfaite} ou non. Un jeu à information parfaite est un jeu dont la règle ne fait pas intervenir le hasard et où chaque joueur joue séquentiellement en ayant la connaissance complète de l'état du jeu et de tous les coups effectués antérieurement par tous les autres joueurs. (Cette notion est parfois distinguée de la notion plus faible d'\textbf{information complète}, qui souligne que les joueurs ont connaissance complète de la \emph{règle} du jeu, i.e., des gains finaux et des options disponibles à chaque joueur. Néanmoins, on peut formellement ramener un jeu à information incomplète en jeu à information complète en regroupant toute l'inconnue sur les règles du jeu dans des coups d'un joueur appelé « la nature ». Dans ce cours, 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 (= é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 exclusivement au cas discret (on écartera, par exemple, la théorie des jeux différentiels). \subsection{Quelques exemples en vrac} \thingy Le jeu de \textbf{pile ou face} entre Pauline et Florian. On tire une pièce non-truquée : si elle tombe sur pile, Pauline gagne, si c'est face, c'est Florian. Aucun des joueurs n'a de choix à faire. Chacun a une probabilité $\frac{1}{2}$ de gagner, ou une espérance de $0$ si les gains sont $+1$ au gagnant et $-1$ au perdant (il s'agit donc d'un jeu à somme nulle). Variante entre Alice et Bob : maintenant, Alice choisit « pile » ou « face » avant qu'on (Bob) tire la pièce. Si Alice a bien prévu, elle gagne, sinon c'est Bob. Ici, seule Alice a un choix à faire. Néanmoins, il n'y a pas de stratégie intéressante : la stratégie consistant à choisir « pile » offre la même espérance que celle consistant à choisir « face », et il n'existe pas de stratégie (c'est-à-dire, de stratégie mesurable par rapport à l'information dont dispose Alice) offrant une meilleure espérance. \thingy Variante : Alice choisit « pile » ou « face », l'écrit dans une enveloppe scellée sans la montrer à Bob (elle s'\emph{engage} sur son choix), et Bob, plutôt que tirer une pièce, choisit le côté qu'il montre. Si Alice a bien deviné le choix de Bob, Alice gagne, sinon c'est Bob. Variante : Bob choisit une carte dans un jeu de 52 cartes sans la montrer à Bob, et Alice doit deviner si la carte est noire ou rouge. Variante équivalente : Alice choisit « Alice » ou « Bob » et Bob choisit simultanément « gagne » ou « perd ». Si la phrase obtenue en combinant ces deux mots est « Alice gagne » ou « Bob perd », alors Alice gagne, si c'est « Alice perd » ou « Bob gagne », alors Bob gagne. Encore une variante : Alice et Bob choisissent simultanément un bit (élément de $\{\mathtt{0},\mathtt{1}\}$), si le XOR de ces deux bits vaut $\mathtt{0}$ alors Alice gagne, s'il vaut $\mathtt{1}$ c'est Bob. Ce jeu est impartial (même s'il n'est pas parfaitement symétrique entre les joueurs) : Alice n'a pas d'avantage particulier sur Bob (ce qui est assez évident sur ces dernières variantes). \begin{center} \begin{tabular}{r|cc} $\downarrow$Alice, Bob$\rightarrow$&$\mathtt{0}$/« gagne »&$\mathtt{1}$/« perd »\\\hline $\mathtt{0}$/« Alice »&$+1,-1$&$-1,+1$\\ $\mathtt{1}$/« Bob »&$-1,+1$&$+1,-1$\\ \end{tabular} \end{center} La notion de coups simultanés peut se convertir en coups engagés dans une enveloppe scellée (cf. \ref{intro-simultaneous-or-sequential}). On verra, et il est assez facile de comprendre intuitivement, que la meilleure stratégie possible pour un joueur comme pour l'autre, consiste à choisir l'une ou l'autre des deux options offertes avec probabilité $\frac{1}{2}$ (ceci assure une espérance de gain nul quoi que fasse l'autre joueur). (En pratique, si on joue de façon répétée à ce jeu, il peut être intéressant d'essayer d'exploiter le fait que les humains ont des générateurs aléatoires assez mauvais, et d'arriver à prédire leurs coups pour gagner. Ceci est particulièrement amusant avec des petits enfants. Voir aussi la « battle of wits » du film \textit{Princess Bride} à ce sujet.) \thingy\label{rock-paper-scissors} Le jeu de \textbf{pierre-papier-ciseaux} : Alice et Bob choisissent simultanément un élément de l'ensemble $\{\textrm{pierre},\penalty0 \textrm{papier},\penalty0 \textrm{ciseaux}\}$. S'ils ont choisi le même élément, le jeu est 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 situation complètement symétrique. \begin{center} \begin{tabular}{r|ccc} $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline Pierre&$0,0$&$-1,+1$&$+1,-1$\\ Papier&$+1,-1$&$0,0$&$-1,+1$\\ Ciseaux&$-1,+1$&$+1,-1$&$0,0$\\ \end{tabular} \end{center} 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). Ce jeu s'appelle aussi papier-ciseaux-puits, qui est exactement le même si ce n'est que « pierre » s'appelle maintenant « puits » (donc ciseaux gagne sur papier, puits gagne sur ciseaux et papier gagne sur puits) : la stratégie optimale est évidemment la même. Certains enfants, embrouillés par l'existence des deux variantes, jouent à pierre-papier-ciseaux-puits, qui permet les quatre options, et où on convient que la pierre tombe dans le puits : quelle est alors la stratégie optimale ? il est facile de se convaincre qu'elle consiste à ne jamais jouer pierre (qui est strictement « dominée » par puits), et jouer papier, ciseaux ou puits avec probabilité $\frac{1}{3}$ chacun (cette stratégie garantit un gain au moins nul quoi que fasse l'autre adversaire, et même strictement positif s'il joue pierre avec probabilité strictement positive). \begin{center} \begin{tabular}{r|cccc} $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Puits\\\hline Pierre&$0,0$&$-1,+1$&$+1,-1$&$-1,+1$\\ Papier&$+1,-1$&$0,0$&$-1,+1$&$+1,-1$\\ Ciseaux&$-1,+1$&$+1,-1$&$0,0$&$-1,+1$\\ Puits&$+1,-1$&$-1,+1$&$+1,-1$&$0,0$\\ \end{tabular} \end{center} \thingy\label{prisonners-dilemma} Le \textbf{dilemme du prisonnier} : Alice et Bob choisissent simultanément une option parmi « coopérer » ou « faire défaut ». Les gains sont déterminés par la matrice suivante : \begin{center} \begin{tabular}{r|cc} $\downarrow$Alice, Bob$\rightarrow$&Coopère&Défaut\\\hline Coopère&$2,2$&$0,4$\\ Défaut&$4,0$&$1,1$\\ \end{tabular} \end{center} Ou plus généralement, en remplaçant $4,2,1,0$ par quatre nombres $T$ (tentation), $R$ (récompense), $P$ (punition) et $S$ (\textit{sucker}) tels que $T>R>P>S$. Ces inégalités font que chaque joueur a intérêt à faire défaut, quelle que soit l'option choisie par l'autre joueur : on se convaincra facilement que le seul équilibre de Nash (cf. \ref{definition-best-response-and-nash-equilibrium}) pour ce jeu est celui où Alice et Bob font tous deux défaut ; pourtant, tous les deux reçoivent moins dans cette situation que s'ils coopèrent mutuellement. Ce jeu a été énormément étudié du point de vue économique, psychologique, politique, philosophique, etc., pour trouver des cadres d'étude justifiant que la coopération est rationnelle, pour expliquer en quoi le jeu itéré (=répété) diffère du jeu simple, ou pour montrer que la notion d'équilibre de Nash est perfectible. \thingy\label{dove-or-hawk} Le jeu du \textbf{trouillard}, ou de la \textbf{colombe et du faucon}, obtenu en modifiant les gains du dilemme du prisonnier pour pénaliser le double défaut (maintenant appelé rencontre faucon-faucon) plus lourdement que la coopération (colombe) face au défaut. Autrement dit : \begin{center} \begin{tabular}{r|cc} $\downarrow$Alice, Bob$\rightarrow$&Colombe&Faucon\\\hline Colombe&$2,2$&$0,4$\\ Faucon&$4,0$&$-4,-4$\\ \end{tabular} \end{center} Ou plus généralement, en remplaçant $4,2,0,-4$ par quatre nombres $W$ (\textit{win}), $T$ (\textit{truce}), $L$ (\textit{loss}) et $X$ (\textit{crash}) tels que $W>T>L>X$. Ces inégalités font que chaque joueur a intérêt à faire le contraire de ce que fait l'autre (si Bob joue faucon, Alice a intérêt à jouer colombe, et si Bob joue colombe, Alice a intérêt à jouer faucon). (Pour justifier le nom de « jeu du trouillard », on peut évoquer le scénario d'une course de voitures vers une falaise, à la façon du film \textit{La Fureur de vivre} : jouer colombe, c'est arrêter sa voiture avant d'arriver à la falaise, et jouer faucon, c'est ne pas s'arrêter sauf si l'autre s'est arrêté : celui qui s'arrête passe pour un trouillard et perd le jeu, mais si aucun ne s'arrête, les deux voitures tombent dans la falaise, ce qui est pire que de passer pour un trouillard.) Ce jeu présente par exemple un intérêt en biologie, notamment pour ce qui est de l'évolution des comportements. On pourra se convaincre que ce jeu a trois équilibres de Nash (cf. \ref{definition-best-response-and-nash-equilibrium} ; en gros, il s'agit d'une situation dans laquelle aucun des joueurs n'améliorerait son gain en changeant \emph{unilatéralement} la stratégie employée) : l'un où Alice joue colombe et Bob joue faucon, un deuxième où c'est le contraire, et un troisième où chacun joue colombe ou faucon avec les probabilités respectives $\frac{L-X}{W-T + L-X}$ et $\frac{W-T}{W-T + L-X}$ (avec les valeurs ci-desssus : $\frac{2}{3}$ et $\frac{1}{3}$), pour un gain espéré de $\frac{LW - TX}{W-T + L-X}$ (avec les valeurs ci-dessus : $\frac{4}{3}$). \thingy\label{battle-of-sexes} La \textbf{guerre des sexes}. Alice et Bob veulent faire du sport ensemble : Alice préfère l'alpinisme, Bob préfère la boxe, mais tous les deux préfèrent faire quelque chose avec l'autre que séparément. D'où les gains suivants : \begin{center} \begin{tabular}{r|cc} $\downarrow$Alice, Bob$\rightarrow$&Alpinisme&Boxe\\\hline Alpinisme&$2,1$&$0,0$\\ Boxe&$0,0$&$1,2$\\ \end{tabular} \end{center} Ou plus généralement, en remplaçant $2,1,0$ par trois nombres $P$ (préféré), $Q$ (autre), $N$ (nul) tels que $P>Q>N$. Ce jeu présente par exemple un intérêt en sociologie, notamment pour ce qui est de la synchronisation aoutour d'une ressource commune (par exemple l'adoption d'un standard). On pourra se convaincre que ce jeu a trois équilibres de Nash (cf. \ref{definition-best-response-and-nash-equilibrium}) : l'un où les deux joueurs vont à l'alpinisme, un deuxième où les deux vont à la boxe, et un troisième où chacun va à son activité préférée avec probabilité $\frac{P-N}{P+Q-2N}$ et à l'autre avec probabilité $\frac{Q-N}{P+Q-2N}$ (avec les valeurs ci-dessus : $\frac{2}{3}$ et $\frac{1}{3}$), pour un gain espéré de $\frac{PQ-N^2}{P+Q-2N}$ (avec les valeurs ci-dessus : $\frac{2}{3}$). Remarquablement, ce gain espéré est inférieur à $Q$. \thingy Le \textbf{jeu du partage} ou \textbf{de l'ultimatum} : Alice et Bob ont $10$ points à se partager : Alice choisit un $k$ entre $0$ et $10$ entier (disons), la part qu'elle se propose de garder pour elle, \emph{puis} Bob choisit, en fonction du $k$ proposé par Alice, d'accepter ou de refuser le partage : s'il accepte, Alice reçoit le gain $k$ et Bob reçoit le gain $10-k$, tandis que si Bob refuse, les deux reçoivent $0$. Cette fois, il ne s'agit pas d'un jeu à somme nulle ! Variante : Alice choisit $k$ et \emph{simultanément} Bob choisit $\varphi \colon \{0,\ldots,10\} \to \{\textrm{accepte},\penalty0 \textrm{refuse}\}$. Si $\varphi(k) = \textrm{accepte}$ alors Alice reçoit $k$ et Bob reçoit $10-k$, tandis que si $\varphi(k) = \textrm{refuse}$ alors Alice et Bob reçoivent tous les deux $0$. Ceci revient (cf. \ref{question-preposing-moves}) à demander à Bob de préparer sa réponse $\varphi(k)$ à tous les coups possibles d'Alice (notons qu'Alice n'a pas connaissance de $\varphi$ quand elle choisit $k$, les deux sont choisis simultanément). On se convainc facilement que si Bob accepte $k$, il devrait aussi accepter tous les $k'\leq k$, d'où la nouvelle : Variante : Alice choisit $k$ entre $0$ et $10$ (la somme qu'elle propose de se garder) et \emph{simultanément} Bob choisit $\ell$ entre $0$ et $10$ (le maximum qu'il accepte qu'Alice garde pour elle) : si $k\leq \ell$ alors Alice reçoit $k$ et Bob reçoit $10-k$, tandis que si $k>\ell$ alors Alice et Bob reçoivent tous les deux $0$. Ce jeu peut sembler paradoxal pour la raison suivante : dans la première forme proposée, une fois $k$ choisi, on il semble que Bob ait toujours intérêt à accepter le partage dès que $k<10$ (il gagnera quelque chose, alors que s'il refuse il ne gagne rien) ; pourtant, on a aussi l'impression que refuser un partage pour $k>5$ correspond à refuser un chantage (Alice dit en quelque sorte à Bob « si tu n'acceptes pas la petite part que je te laisse, tu n'auras rien du tout »). Dans la troisième forme, qui est censée être équivalente, on verra qu'il existe plusieurs équilibres de Nash, ceux où $\ell=k$ (les deux joueurs sont d'accord sur le partage) et celui où $k=10$ et $\ell=0$ (les deux joueurs demandent tous les deux la totalité du butin, et n'obtiennent rien). \thingy Un jeu idiot : Alice et Bob choisissent simultanément chacun un entier naturel. Celui qui a choisi le plus grand gagne (en cas d'égalité, on peut déclarer le nul, ou décider arbitrairement qu'Alice gagne — ceci ne changera rien au problème). Ce jeu résiste à toute forme d'analyse intelligente, il n'existe pas de stratégie gagnante (ni d'équilibre de Nash, cf. plus haut), on ne peut rien en dire d'utile. Cet exemple sert à illustrer le fait que dans l'étude des jeux sous forme normale, l'hypothèse de finitude des choix sera généralement essentielle. \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}), et qu'un des joueurs a forcément une stratégie gagnante ou bien les deux joueurs une stratégie assurant le nul (si le nul est possible) (cf. \ref{determinacy-of-perfect-information-games}). 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. On peut aussi considérer un graphe dont les arêtes peuvent être coloriées de trois couleurs possibles : des arêtes rouges, qui ne peuvent être suivies que par Alice, des arêtes bleues, qui ne peuvent être suivies que par Bob, et des arêtes vertes (équivalentes à une arête rouge \emph{et} une arête bleue entre les mêmes deux sommets), qui peuvent être suivies par l'un ou l'autre joueur (le cas précédent est donc équivalent à celui d'un graphe entièrement vert). Il s'agira là du cadre général dans lequel on étudie la théorie combinatoire des jeux \emph{partiaux} à information parfaite : on verra que, si le nul est rendu impossible, quatre cas sont possibles (Alice a une stratégie gagnante qui que soit le joueur qui commence, ou Bob en a une, ou le premier joueur a une stratégie gagnante, ou le second en a une). \thingy\label{introduction-nim-game} Le \textbf{jeu de nim} : un certain nombre d'allumettes sont arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob retirent des allumettes, 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). Autrement dit, une position du jeu de nim est une suite finie $(n_1,\ldots,n_r)$ d'entiers naturels (représentant le nombre d'allumettes de chaque ligne), et un coup possible à partir de cette position consiste à aller vers l'état $(n'_1,\ldots,n'_r)$ où $n'_i = n_i$ pour tout $i$ sauf exactement un pour lequel $n'_i < n_i$. Il s'agit ici d'un jeu à deux joueurs 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 : en anticipant sur la suite, il s'agit de calculer le XOR (= « ou exclusif », appelé aussi \textit{somme de nim} dans ce contexte des nombres $n_i$ d'allumettes des différentes lignes (écrits en binaire) : ce XOR s'appelle la \textit{fonction de Grundy} de la position, et le jeu est gagnable par le second joueur (c'est-à-dire, celui qui \emph{vient de} jouer) si et seulement cette fonction de Grundy vaut $0$. (À titre d'exemple, la position de départ la plus courante du jeu de nim est $(1,3,5,7)$, et comme $\mathtt{001} \oplus \mathtt{011} \oplus \mathtt{101} \oplus \mathtt{111} = \mathtt{000}$ en binaire, en notant $\oplus$ pour le XOR, le second joueur a une stratégie gagnante.) On peut aussi jouer à la variante « misère » du jeu : celui qui prend la dernière allumette a perdu (cf. le film \textit{L'année dernière à Marienbad}) ; néanmoins, elle se ramène assez facilement à la variante « normale » (où celui qui prend la dernière allumette a gagné), cette dernière ayant plus d'intérêt mathématique. Le jeu de nim apparaît sous différents déguisements. On peut par exemple évoquer le suivant, complètement équivalent à ce qu'on vient de dire : on place $r$ jetons sur un plateau formé d'une seule ligne dont les cases sont numérotées $0,1,2,3,\ldots$ (de la gauche vers la droite, pour fixer les idées). Chacun tour à tour déplace un jeton vers la gauche ; plusieurs jetons ont le droit de se trouver sur la même case, et ils peuvent passer par-dessus l'un l'autre. Le perdant est celui qui ne peut plus jouer (parce que tous les jetons sont sur la case la plus à gauche, $0$). Il s'agit exactement du jeu de nim, en considérant que la position où les jetons sont sur les cases $n_1,\ldots,n_r$ correspond à celle du jeu de nim où il y a $n_1,\ldots,n_r$ allumettes sur les différentes lignes. C'est ce point de vue qui suggère le type de jeux suivant : \thingy Jeux de \textbf{retournement de pièces}. Ici une position est une rangée de pièces (qui pourront être numérotées, de la gauche vers la droite, de $0$ à $N-1$ ou de $1$ à $N$, selon la commodité du jeu), chacune en position « pile vers le haut » (qu'on notera $\mathtt{0}$) ou « face vers le haut » ($\mathtt{1}$). Chaque joueur tour à tour va retourner certaines pièces selon des règles propres au jeu, avec toujours la règle générale que \textit{au moins une pièce est retournée, et la plus à droite à être retournée doit passer de face à pile} (d'autres pièces peuvent passer de pile à face, et d'autres pièces plus à droite peuvent rester sur pile ou rester sur face, mais la plus à droite parmi les pièces qui se font retourner devait être face avant le mouvement et devient du coup pile). Cette règle générale assure que le nombre binaire formé de l'ensemble des pièces, lues de la droite vers la gauche, diminue strictement à chaque coup, et donc que le jeu termine forcément en temps fini. Le joueur qui ne peut plus jouer a perdu. Il faut bien sûr mettre des règles supplémentaires restreignant les retournements possibles, sinon le jeu n'a aucun intérêt (le premier joueur met toutes les pièces à montrer pile et gagne immédiatement). Quelques exemples de telles règles peuvent être : \begin{itemize} \item On ne peut retourner qu'une pièce à chaque coup. Dans ce cas, seul importe le nombre de pièces montrant face, et les joueurs n'ont essentiellement aucun choix dans le coup à jouer : peu importe la pièce retournée (qui passe forcément de face à pile) ; si le nombre de pièces montrant face est pair, le second joueur gagne, tandis que s'il est impair, c'est le premier qui gagne. Ce jeu est très peu intéressant. \item On retourne exactement deux pièces à chaque coup (toujours avec la règle générale que la plus à droite des deux passe de face à pile). Il s'agit de nouveau du jeu de nim déguisé (mais un peu mieux) : si les pièces sont numérotées à partir de $0$ (la plus à gauche), retourner les pièces $n$ et $n' 0$. Parfois, on préférera considérer la stratégie comme la combinaison formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est donc une simple notation pour $s$). Autrement dit, ceci correspond à voir une stratégie mixte comme une combinaison convexe d'éléments de $B$, i.e., un point du simplexe affine dont les sommets sont les éléments de $B$. En particulier, un élément $b$ de $B$ (stratégie pure) sera identifié à l'élément de $S_B$ qui affecte le poids $1$ à $b$ et $0$ à tout autre élément. En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$ sera vu (notamment comme espace topologique) comme le fermé de $\mathbb{R}^B$ défini par l'intersection des demi-espaces de coordonnées positives et de l'hyperplan défini par la somme des coordonnées égale à $1$. \end{defn} \begin{defn}\label{definition-mixed-strategy-game} Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i \to\mathbb{R}$ comme on vient de le dire. On notera parfois $S_i$ l'ensemble des stratégies mixtes du joueur $i$. Un \textbf{profil de stratégies mixtes} est un élément du produit cartésien $S := S_1 \times \cdots \times S_N$. Plus généralement, si $I \subseteq \{1,\ldots,N\}$ est un ensemble de joueurs, un élément du produit $S_I := \prod_{j\in I} S_j$ s'appellera un profil de stratégies mixtes pour l'ensemble $I$ de joueurs ; ceci sera notamment utilisé si $I = \{1,\ldots,N\}\setminus\{i\}$ est l'ensemble de tous les joueurs sauf le joueur $i$, auquel cas on notera $S_{?i} := \prod_{j\neq i} S_j$ l'ensemble des profils. Naturellement, si chaque composante est une stratégie pure, on pourra parler de profil de stratégies pures. \end{defn} \thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une distribution de probabilité sur chaque $A_i$, n'est pas la même chose qu'une distribution de probabilités sur $A := A_1 \times \cdots \times A_N$. Néanmoins, on peut voir les profils de stratégies mixtes comme des distributions particulières sur $A$, à savoir celles pour lesquelles les marginales (i.e., les projections sur un des $A_i$) sont indépendantes. Concrètement, ceci signifie que donné $(s_1,\ldots,s_N) \in S$, on en déduit un $s\colon A\to\mathbb{R}$, aussi une distribution de probabilité, par la définition suivante : $s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des $s_i(a_i)$). On identifiera parfois abusivement l'élément $(s_1,\ldots,s_N) \in S$ à la distribution $s\colon A\to\mathbb{R}$ qu'on vient de décrire (ce n'est pas un problème car $s_i$ se déduit de $s$ : précisément, $s_i(b) = \sum_{a: a_i = b} s(a)$ où la somme est prise sur les $a \in A$ tels que $a_i = b$). Ceci conduit à faire la définition suivante : \begin{defn} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on appelle \textbf{gain [espéré]} du joueur $i$ selon ce profil la quantité \[ u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a) \] (ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$ vers $\mathbb{R}$). \end{defn} Selon l'approche qu'on veut avoir, on peut dire qu'on a défini $u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré selon la distribution de probabilité $s_i$ ; ou bien qu'on a utilisé l'unique prolongement de $u_i$ au produit des simplexes $S_i$ qui soit affine en chaque variable $s_i$. \subsection{Équilibres de Nash} \begin{defn}\label{definition-best-response-and-nash-equilibrium} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si $s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots \times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil de stratégies mixtes pour tous les joueurs autres que le joueur $i$, on dit que la stratégie mixte $s_! \in S_i$ est une \textbf{meilleure réponse} (resp. la meilleure réponse stricte) contre $s_?$ lorsque pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$ (resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a $u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ désigne l'élément de $S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme $i$-ième composante entre $s_{i-1}$ et $s_{i+1}$. Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble des joueurs) est dit être un \textbf{équilibre de Nash} (resp., un équilibre de Nash \emph{strict}) lorsque pour tout $1\leq i \leq N$, la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse (resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour les autres joueurs obtenu en supprimant la composante $s_i$ de $s$. \end{defn} \begin{prop}\label{stupid-remark-best-mixed-strategies} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si $s_?$ est un profil de stratégies mixtes pour tous les joueurs autres que le joueur $i$, il existe une meilleure réponse pour le joueur $i$ qui est une stratégie pure. Et même, si $s_!$ (stratégie mixte) est une meilleure réponse, alors il existe une meilleure réponse qui est une stratégie pure appartenant au support de $s_!$. En particulier, une meilleure réponse stricte est nécessairement une stratégie pure. \end{prop} \begin{proof} Il suffit de se rappeler que $u_i(s_?,t)$ est une fonction affine de $t \in S_i$, c'est-à-dire que sa valeur est combinaison convexe, à coefficients les $t(a)$ pour $a\in S_i$, des $u_i(s_?,a)$. Comme une combinaison convexe est majorée par la plus grande des valeurs combinée (ici, des $u_i(s_?,a)$), il est clair que le maximum des $u_i(s_?,t)$ existe et est égal au maximum des $u_i(s_?,a)$ ; les autres affirmations sont tout aussi faciles. (Si on préfère : une fonction affine sur un simplexe prend son maximum — ou son minimum — sur un des sommets de ce simplexe.) \end{proof} \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria} Pour un jeu en forme normale comme en \ref{definition-game-in-normal-form}, il existe un équilibre de Nash. \end{thm} Pour démontrer le théorème en question, on utilise (et on admet) le théorème du point fixe de Brouwer, qui affirme que : \begin{thm}[L. E. J. Brouwer, 1910]\label{brouwer-fixed-point-theorem} Si $K$ est un convexe compact de $\mathbb{R}^m$, et que $T \colon K \to K$ est continue, alors il existe $x\in K$ tel que $T(x) = x$ (un \emph{point fixe} de $T$, donc). \end{thm} L'idée intuitive de la démonstration suivante est : partant d'un profil $s$ de stratégies, on peut définir continûment un nouveau profil $s^\sharp$ en donnant plus de poids aux options qui donnent un meilleur gain au joueur correspondant — si bien que $s^\sharp$ sera différent de $s$ dès que $s^\sharp$ n'est pas un équilibre de Nash. Comme la fonction $T \colon s \to s^\sharp$ doit avoir un point fixe, ce point fixe sera un équilibre de Nash. \begin{proof}[Démonstration de \ref{theorem-nash-equilibria}] Si $s \in S$ et $1\leq i\leq N$, convenons de noter $s_{?i}$ l'effacement de la composante $s_i$ (c'est-à-dire le profil pour les joueurs autres que $i$). Si de plus $b \in A_i$, notons $\varphi_{i,b}(s) = \max(0,\; u_i(s_{?i},b) - u_i(s))$ l'augmentation du gain du joueur $i$ si on remplace sa stratégie $s_i$ par la stratégie pure $b$ en laissant le profil $s_{?i}$ des autres joueurs inchangé (ou bien $0$ s'il n'y a pas d'augmentation). On remarquera que $s$ est un équilibre de Nash si et seulement si les $\varphi_{i,b}(s)$ sont nuls pour tout $1\leq i\leq N$ et tout $b\in A_i$ (faire appel à la proposition précédente pour le « si »). On remarquera aussi que chaque $\varphi_{i,b}$ est une fonction continue sur $S$. Définissons maintenant $T\colon S\to S$ de la façon suivante : si $s \in S$, on pose $T(s) = s^\sharp$, où $s^\sharp = (s^\sharp_1,\ldots,s^\sharp_N)$ avec $s^\sharp_i$ le barycentre de $s_i$ avec coefficient $1$ et des $a \in A_i$ avec les coefficients $\varphi_{i,a}(s)$, autrement dit : \[ \begin{aligned} s^\sharp_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\ &= \frac{s_i(a) + \varphi_{i,a}(s)}{1 + \sum_{b\in A_i}\varphi_{i,b}(s)} \end{aligned} \] (L'important est que $s^\sharp_i$ augmente strictement le poids des options $a\in A_i$ telles que $u_i(s_{?i},a) > u_i(s)$ ; en fait, on pourrait composer $\varphi$ à gauche par n'importe quelle fonction $\mathbb{R} \to \mathbb{R}$ croissante, continue, nulle sur les négatifs et strictement positive sur les réels strictement positifs, on a choisi l'identité ci-dessus pour rendre l'expression plus simple à écrire, mais elle peut donner l'impression qu'on commet une « erreur d'homogénéité » en ajoutant un gain à une probabilité.) D'après la première expression donnée, il est clair qu'on a bien $s^\sharp_i \in S_i$, et qu'on a donc bien défini une fonction $T\colon S\to S$. Cette fonction est continue, donc admet un point fixe $s$ d'après \ref{brouwer-fixed-point-theorem}. On va montrer que $s$ est un équilibre de Nash. Si $1\leq i\leq N$, il existe $a \in A_i$ tel que $u_i(s_{?i},a) \leq u_i(s)$ (car, comme dans la preuve de \ref{stupid-remark-best-mixed-strategies}, $u_i(s)$ est combinaison convexe des $u_i(s_{?i},a)$ dont est supérieur au plus petit d'entre eux) : c'est-à-dire $\varphi_{i,a}(s) = 0$. Pour un tel $a$, la seconde expression $s^\sharp_i(a) = s_i(a) / \big(1 + \sum_{b\in A_i}\varphi_{i,b}(s)\big)$ montre, en tenant compte du fait que $s^\sharp_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i} \varphi_{i,b}(s) = 0$, donc $\varphi_{i,b}(s) = 0$ pour tout $b$. On vient de voir que les $\varphi_{i,b}(s)$ sont nuls pour tout $i$ et tout $b$, et on a expliqué que ceci signifie que $s$ est un équilibre de Nash. \end{proof} \textcolor{red}{Dire quelque chose sur l'algorithme de Lemke-Howson ?} \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games} \begin{thm}[« du minimax », J. von Neumann, 1928]\label{theorem-minimax} Soient $C$ et $C'$ deux convexes compacts dans des espaces affines réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$ une application bi-affine (c'est-à-dire, affine en chaque variable séparément). Alors \[ \max_{x\in C} \min_{y\in C'} u(x,y) = \min_{y\in C'} \max_{x\in C} u(x,y) \] \end{thm} \begin{proof} Tout d'abord, l'inégalité dans un sens est évidente : on a \[ \max_{x\in C} \min_{y\in C'} u(x,y) = \min_{y\in C'} u(x_*,y) \leq u(x_*,y_*) \leq \max_{x\in C} u(x,y_*) = \min_{y\in C'} \max_{x\in C} u(x,y) \] où $x_* \in C$ est un point où $\max_{x\in C} \min_{y\in C'} u(x,y)$ est atteint et $y_* \in C'$ un point où $\min_{y\in C'} \max_{x\in C} u(x,y)$ l'est. Il s'agit donc de prouver l'inégalité de sens contraire. Commençons par supposer que $C$ est l'enveloppe convexe d'un nombre fini de points $(x_i)_{i\in I}$ et $C'$ de $(y_j)_{j\in J}$, et on expliquera plus loin comment se ramener à ce cas (même si c'est le seul qui servira dans le cadre de la théorie des jeux). Lorsque cette hypothèse est vérifiée, on va définir une fonction $T\colon C\times C' \to C\times C'$ de la façon suivante. Donnons-nous $(x,y) \in C\times C'$. Pour chaque $i\in I$, on définit $\varphi_i(x,y) = \max (0,\; u(x_i,y)-u(x,y))$, et de même on pose $\psi_j(x,y) = \max (0,\; u(x,y)-u(x,y_j))$. Posons enfin $T(x,y) = (x^\sharp,y^\sharp)$ où $x^\sharp$ et $y^\sharp$ (qui dépendent tous les deux de $x$ et $y$ à la fois, malgré la notation) sont définis comme suit. On appelle $x^\sharp$ le barycentre de $x$ affecté du coefficient $1$ et des $x_i$ (pour $i\in I$) affectés des coefficients respectifs $\varphi_i(x,y)$, c'est-à-dire $x^\sharp = \frac{x + \sum_{i\in I} \varphi_i(x,y)\,x_i}{1 + \sum_{i\in I} \varphi_i(x,y)}$ ; et soit de même $y^\sharp$ le barycentre de $y$ avec coefficient $1$ et des $y_i$ avec les coefficients $\psi_i(x,y)$. Clairement, $x^\sharp$ et $y^\sharp$ sont dans $C$ et $C'$ respectivement (il s'agit de barycentres à coefficients positifs, c'est-à-dire de combinaisons convexes). La fonction $T\colon C\times C' \to C\times C'$ définie par $T(x,y) = (x^\sharp,y^\sharp)$ est continue. Par ailleurs, on a $x^\sharp = x$ si et seulement si $x$ réalise $\max_{\tilde x\in C} u(\tilde x,y)$ (un sens est évident, et pour l'autre il suffit de se convaincre que s'il existe $\tilde x$ tel que $u(\tilde x,y) > u(x,y)$ alors il y a un $i$ tel que ceci soit vrai en remplaçant $\tilde x$ par $x_i$, et on a alors $\varphi_i(x,y)>0$ donc $u(x^\sharp,y) > u(x,y)$) ; et on a un résultat analogue pour $y$. La fonction $T$ continue du compact convexe $C\times C'$ vers lui-même y admet d'après \ref{brouwer-fixed-point-theorem} un point fixe $(x_0,y_0)$, vérifiant donc $(x_0^\sharp, y_0^\sharp) = (x_0,y_0)$, c'est-à-dire que $u (x_0,y_0) = \max_{x\in C} u(x,y_0) = \min_{y\in C'} u(x_0, y)$. On a donc maintenant \[ \max_{x\in C} \min_{y\in C'} u(x,y) \geq \min_{y\in C'} u(x_0,y) = u(x_0,y_0) = \max_{x\in C} u(x,y_0) \geq \min_{y\in C'} \max_{x\in C} u(x,y) \] ce qu'on voulait. Pour se ramener au cas où $C$ et $C'$ sont enveloppes convexes d'un nombre fini de points, on observe que pour tout $\varepsilon>0$ il existe $\Sigma$ et $\Sigma'$ des enveloppes convexes d'un nombre fini de points (= polytopes) contenues dans $C$ et $C'$ respectivement et telles que pour tout $x\in C$ on ait $\min_{y\in C'} u(x,y) > \min_{y\in\Sigma'} u(x,y)-\varepsilon$ et $\max_{x\in C} u(x,y) < \max_{x\in\Sigma} u(x,y)+\varepsilon$ (explication : il est trivial que pour chaque $x$ il existe un $\Sigma'$ vérifiant la condition demandée, le point intéressant est qu'un unique $\Sigma'$ peut convenir pour tous les $x$ ; mais pour chaque $\Sigma'$ donné, l'ensemble des $x$ pour lesquels il convient est un ouvert de $C$, qui est compact, donc un nombre fini de ces ouverts recouvrent $C$, et on prend l'enveloppe convexe de la réunion des $\Sigma'$ en question ; on procède de même pour $\Sigma$). On a alors $\max_{x\in C} \min_{y\in C'} u(x,y) > \max_{x\in \Sigma} \min_{y\in \Sigma'} u(x,y) - \varepsilon$ et une inégalité analogue pour l'autre membre : on en déduit l'inégalité recherchée à $2\varepsilon$ près, mais comme on peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on voulait. \end{proof} \begin{cor}\label{symmetric-zero-sum-game} Soit $C$ un convexe compact dans un espace affine réel de dimension finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine antisymétrique (i.e., $u(y,x) = -u(x,y)$). Alors il existe $x\in C$ tel que pour tout $y\in C$ on ait $u(x,y)\geq 0$ (et la valeur commune des deux membres de l'égalité du théorème \ref{theorem-minimax} est $0$). \end{cor} \begin{proof} On applique le théorème : il donne $\max_{x\in C}\penalty0 \min_{y\in C} u(x,y) = \min_{y\in C}\penalty0 \max_{x\in C} u(x,y)$. Mais puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C} \max_{x\in C} (-u(y,x))$, soit, en renommant les variables liées, $\min_{x\in C}\penalty0 \max_{y\in C} (-u(x,y)) = -\max_{x\in C}\penalty0 \min_{y\in C} u(x,y)$. Par conséquent, $\max_{x\in C}\penalty0 \min_{y\in C} u(x,y) = 0$ (il est son propre opposé), et en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in C} u(x,y) = 0$, ce qu'on voulait prouver. \end{proof} \thingy\label{minimax-for-games} Le théorème \ref{theorem-minimax} s'applique à la théorie des jeux de la manière suivante : si on considère un jeu à deux joueurs à somme nulle, en notant $S_1$ et $S_2$ les ensembles des stratégies mixtes des deux joueurs, et $u \colon S_1 \times S_2 \to \mathbb{R}$ le gain espéré du joueur $1$, le gain du joueur $2$ étant donc $-u$, le fait que $(x_0,y_0)$ soit un équilibre de Nash se traduit par le fait que $x_0$ soit la meilleure réponse possible de $1$ contre $y_0$, i.e., $u(x_0,y_0) = \max_{x\in S_1} u(x,y_0)$, et le fait que $y_0$ soit la meilleure réponse possible de $2$ contre $x_0$, c'est-à-dire $u(x_0,y_0) = \min_{y\in S_2} u(x_0,y)$ (puisque $2$ cherche à maximiser $-u$, c'est-à-dire minimiser $u$). Comme on l'a expliqué dans la preuve, on a \[ \max_{x\in S_1} \min_{y\in S_2} u(x,y) \geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) = \max_{x\in S_1} u(x,y_0) \geq \min_{y\in S_2} \max_{x\in S_1} u(x,y) \] donc en fait il y a égalité partout : tout équilibre de Nash réalise la même valeur $u(x_0,y_0) = \max_{x\in S_1} \min_{y\in S_2} u(x,y) = \min_{y\in S_2} \max_{x\in S_1} u(x,y)$, qu'on appelle la \textbf{valeur} du jeu à somme nulle. On peut donc parler de \textbf{stratégie optimale} pour le joueur $1$, resp. $2$ pour désigner une composante $x_0$, resp. $y_0$, d'un équilibre de Nash, i.e., vérifiant $\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in S_2} u(x,y)$, resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2} \max_{x\in S_1} u(x,y)$, ces deux quantités étant égales à la valeur du jeu. Le corollaire \ref{symmetric-zero-sum-game} nous apprend (de façon peu surprenante) que si le jeu à somme nulle est \emph{symétrique} (ce qui signifie que $u$ est antisymétrique), alors la valeur du jeu est nulle. \thingy Dans le contexte ci-dessus, on peut légèrement reformuler le minimax : si on se rappelle (cf. \ref{stupid-remark-best-mixed-strategies}) qu'une fonction affine sur un simplexe prend son maximum (ou son minimum) sur un des sommets du simplexe, cela signifie que, quel que soit $x\in S_1$ fixé, le minimum $\min_{y\in S_2} u(x,y)$ est en fait atteint sur une stratégie \emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{b\in A_2} u(x,b)$ (avec $A_2$ l'ensemble des sommets de $S_2$, i.e., l'ensemble des stratégies pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{a\in A_1} u(a,y)$ quel que soit $y \in S_2$. \emph{Ceci ne signifie pas} qu'il existe un équilibre de Nash en stratégies pures (penser à pierre-papier-ciseaux). Néanmoins, cela signifie que pour calculer la pire valeur possible $\min_{y\in S_2} u(x,y)$ d'une stratégie $x$ du joueur $1$, celui-ci peut ne considérer que les réponses en stratégies pures du joueur $2$. Si on appelle $v$ la valeur du jeu, l'ensemble des $x$ tels que $u(x,y) \geq v$ pour tout $y\in S_2$, c'est-à-dire l'ensemble des stratégies optimales pour le joueur $1$, coïncide donc avec l'ensemble des $x$ tels que $u(x,b) \geq v$ pour tout $b\in A_2$. En particulier, c'est un convexe compact dans $S_1$ (puisque chaque inégalité $u(x,b) \geq v$ définit un convexe compact dans $S_1$ vu que $x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies optimales pour un joueur on obtient encore une telle stratégie}, ce qui n'est pas le cas en général pour des jeux qui ne sont pas à somme nulle. \begin{algo} Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec $A_1,A_2$ deux ensembles finis) définissant la matrice de gains pour le joueur $1$ d'un jeu à somme nulle. On peut calculer une stratégie mixte optimale (cf. \ref{minimax-for-games}) pour le joueur $1$ en résolvant, par exemple au moyen de l'algorithme du simplexe, le problème de programmation linéaire dont les variables sont les $x_a$ pour $a \in A_1$ (les poids de la stratégie mixte) et $v$ (le gain obtenu) cherchant à maximiser $v$ sujet aux contraintes : \[(\forall a\in A_1)\;x_a \geq 0\] \[\sum_{a\in A_1} x_a = 1\] \[(\forall b\in A_2)\;v \leq u(x,b) := \sum_{a \in A_1} u(a,b)\, x_a\] Autrement dit, il s'agit d'un problème de programmation linéaire à $\#A_1 + 1$ variables avec des contraintes de positivité sur $\#A_1$ d'entre elles, une contrainte d'égalité et $\#A_2$ inégalités affines. \end{algo} \thingy Pour ramener ce problème à un problème de programmation linéaire en \emph{forme normale} (maximiser $\textbf{p} x$ sous les contraintes $\textbf{M} x \leq \textbf{q}$ et $x\geq 0$), on sépare la variable $v$ en $v_+ - v_-$ avec $v_+,v_- \geq 0$, et le problème devient de maximiser $v_+ - v_-$ sous les contraintes \[v_+\geq 0,\; v_- \geq 0,\;\; (\forall a\in A_1)\;x_a \geq 0\] \[\sum_{a\in A_1} x_a \leq 1\] \[-\sum_{a\in A_1} x_a \leq -1\] \[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\] Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$ et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes \[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\] \[\sum_{b\in A_2} y_b \geq 1\] \[-\sum_{b\in A_2} y_b \geq -1\] \[(\forall a\in A_1)\;w_+ - w_- - \sum_{b \in A_2} u(a,b)\, y_b \geq 0\] Il s'agit donc exactement du même problème, mais pour l'autre joueur. Le théorème \ref{theorem-minimax} est essentiellement équivalent au théorème de dualité pour la programmation linéaire (qui assure que si le problème primal a un optimum $x_0$ alors le dual en a un $y_0$, et on a égalité des optima). Comme l'algorithme du simplexe résout simultanément le problème primal et le problème dual, l'algorithme ci-dessus (exécuté avec l'algorithme du simplexe) trouve simultanément la stratégie optimale pour les deux joueurs. % % % \section{Jeux de Gale-Stewart et détermination}\label{gale-stewart-games} \subsection{Définitions} \begin{defn}\label{definition-gale-stewart-game} Soit $X$ un ensemble non vide quelconque (à titre indicatif, les cas $X = \{0,1\}$ et $X = \mathbb{N}$ seront particulièrement intéressants). Soit $A$ un sous-ensemble de $X^{\mathbb{N}}$. Le \textbf{jeu de Gale-Stewart} $G_X(A)$ (ou $G_X^{\mathrm{a}}(A)$, cf. \ref{remark-player-names}) est défini de la manière suivante : Alice et Bob choisissent tour à tour un élément de $X$ (autrement dit, Alice choisit $x_0 \in X$ puis Bob choisit $x_1 \in X$ puis Alice choisit $x_2 \in X$ et ainsi de suite). Ils jouent un nombre infini de tours, « à la fin » desquels la suite $(x_0,x_1,x_2,\ldots)$ de leurs coups définit un élément de $X^{\mathbb{N}}$ : si cet élément appartient à $A$, Alice \textbf{gagne}, sinon c'est Bob (la partie n'est jamais nulle). Dans ce contexte, les suites finies $(x_0,\ldots,x_{\ell-1})$ d'éléments de $X$ s'appellent les \textbf{positions} (y compris la suite vide $()$, qui peut s'appeler position initiale) de $G_X(A)$, ou de $G_X$ vu que $A$ n'intervient pas ici ; leur ensemble $\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle parfois l'\textbf{arbre} du jeu $G_X$. Une \textbf{partie} ou \textbf{confrontation}\footnote{Le mot « partie » peut malheureusement désigner soit un sous-ensemble soit une partie d'un jeu au sens défini ici : le mot « confrontation » permet d'éviter l'ambiguïté.} de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$. \end{defn} \thingy\label{remark-player-names} Il peut arriver qu'on ait envie de faire commencer la partie à Bob. Il va de soi que ceci ne pose aucune difficulté, il faudra juste le signaler le cas échéant. De façon générale, sauf précision expresse du contraire, « Alice » est le joueur qui cherche à jouer dans l'ensemble $A$ tandis que « Bob » est celui qui cherche à jouer dans son complémentaire $B := X^{\mathbb{N}} \setminus A$. Le « premier joueur » est celui qui choisit les termes pairs de la suite, le « second joueur » est celui qui choisit les termes impairs. On pourra noter $G_X^{\mathrm{a}}(A)$ lorsqu'il est souhaitable d'insister sur le fait qu'Alice joue en premier, et $G_X^{\mathrm{b}}(A)$ lorsqu'on veut indiquer que Bob joue en premier : formellement, le jeu $G_X^{\mathrm{b}}(A)$ est le même que $G_X^{\mathrm{a}}(X^{\mathbb{N}}\setminus A)$ si ce n'est que les noms des joueurs sont échangés. \begin{defn}\label{definition-strategies-for-gale-stewart-games} Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une \textbf{stratégie} pour le premier joueur (resp. le second joueur) est une fonction $\varsigma$ qui à une suite finie (=position) de longueur paire (resp. impaire) d'éléments de $X$ associe un élément de $X$, autrement dit une fonction $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell}\big) \to X$ (resp. $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell+1}\big) \to X$). Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G_X$ on a $\varsigma((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ pair (y compris $\varsigma(()) = x_0$ en notant $()$ la suite vide), on dit que le premier joueur a joué la partie selon la stratégie $\varsigma$ ; de même, lorsque $\tau((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ impair, on dit que le second joueur a joué la partie selon la stratégie $\tau$. Si $\varsigma$ et $\tau$ sont deux stratégies pour le premier et le second joueurs respectivement, on définit $\varsigma \ast \tau$ comme la partie jouée lorsque le premier joueur joue selon $\varsigma$ et le second selon $\tau$ : autrement dit, $x_i$ est défini par $\varsigma((x_0,\ldots,x_{i-1}))$ si $i$ est pair ou $\tau((x_0,\ldots,x_{i-1}))$ si $i$ est impair. Si on se donne une partie $A$ de $X^{\mathbb{N}}$ et qu'on convient qu'Alice joue en premier : la stratégie $\varsigma$ pour Alice est dite \textbf{gagnante} (dans $G_X^{\mathrm{a}}(A)$) lorsque Alice gagne toute partie où elle joue selon $\varsigma$ comme premier joueur, et la stratégie $\tau$ pour Bob est dite gagnante lorsque Bob gagne toute partie où il joue selon $\tau$. Lorsque l'un ou l'autre joueur a une stratégie gagnante, le jeu $G_X^{\mathrm{a}}(A)$ est dit \textbf{déterminé}. \end{defn} \thingy Il est clair que les deux joueurs ne peuvent pas avoir simultanément une stratégie gagnante (il suffit de considérer la suite $\varsigma \ast \tau$ où $\varsigma$ et $\tau$ seraient des stratégies gagnantes pour les deux joueurs : elle devrait simultanément appartenir et ne pas appartenir à $A$). En revanche, il faut se garder de croire que les jeux $G_X(A)$ sont toujours déterminés. \thingy\label{unshifting-notation} Introduisons la notation suivante : si $\underline{x} := (x_0,\ldots,x_{\ell-1})$ est une suite finie d'éléments de $X$ et si $A$ est un sous-ensemble de $X^{\mathbb{N}}$, on notera $\underline{x}^\$ A$ l'ensemble des suites $(x_\ell, x_{\ell+1}, \ldots) \in X^{\mathbb{N}}$ telles que $(x_0,\ldots,x_{\ell-1}, x_\ell, \ldots)$ appartienne à $A$. Autrement dit, il s'agit de l'image réciproque de $A$ par l'application $X^{\mathbb{N}} \to X^{\mathbb{N}}$ qui insère $x_0,\ldots,x_{\ell-1}$ au début de la suite. On utilisera notamment cette notation pour une suite à un seul terme : si $x\in X$ alors $x^\$ A$ est l'ensemble des $(x_1,x_2,x_3,\ldots) \in X^{\mathbb{N}}$ telles que $(x,x_1,x_2,\ldots) \in A$. (Ainsi, si $\underline{x} := (x_0,\ldots,x_{\ell-1})$, on a $\underline{x}^\$ A = x_{\ell-1}^{\$} \cdots x_1^{\$} x_0^{\$} A$.) \thingy\label{gale-stewart-positions-as-games} Toute position $(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart peut être considéré comme définissant un nouveau jeu de Gale-Stewart consistant à jouer \textbf{à partir de là}, c'est-à-dire, comme si les $\ell$ premiers coups étaient imposés. La notation \ref{unshifting-notation} permet d'en donner une définition formelle : la position $\underline{x} := (x_0,\ldots,x_{\ell-1})$ du jeu $G_X^{\mathrm{a}}(A)$ (où Alice joue en premier) sera considérée comme définissant le jeu $G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair (=c'est à Alice de jouer), et $G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair (=c'est à Bob de jouer). Autrement dit, les joueurs choisissent $x_{\ell},x_{\ell+1},x_{\ell+2},\ldots$, on insère les coups imposés $x_0,\ldots,x_{\ell-1}$ au début de la partie, et on regarde si la suite tout entière appartient à $A$ (ce qui revient à regarder si la suite choisie appartient à $\underline{x}^\$ A$) pour déterminer le gagnant. (Symétriquement, bien sûr, la position $\underline{x}$ du jeu $G_X^{\mathrm{b}}(A)$ sera considérée comme définissant le jeu $G_X^{\mathrm{b}}(\underline{x}^\$ A)$ lorsque $\ell$ est pair, et $G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.) \thingy\label{gale-stewart-winning-positions} On dira qu'une position $(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart $G_X(A)$ est \textbf{gagnante} pour Alice lorsque Alice a une stratégie gagnante dans le jeu qui consiste à jouer à partir de cette position (cf. \ref{gale-stewart-positions-as-games}). On définit de meme une position gagnante pour Bob. \medbreak La proposition suivante est presque triviale et signifie qu'Alice (qui doit jouer) possède une stratégie gagnante si et seulement si elle peut jouer un coup $x$ qui l'amène à une position d'où elle (Alice) a une stratégie gagnante, et Bob en possède une si et seulement si n'importe quel coup $x$ joué par Alice amène à une position d'où il (Bob) a une stratégie gagnante : \begin{prop}\label{strategies-forall-exists-lemma} Soit $X$ un ensemble non vide et $A \subseteq X^{\mathbb{N}}$. Dans le jeu de Gale-Stewart $G_X^{\mathrm{a}}(A)$, et en utilisant la notation \ref{unshifting-notation} : \begin{itemize} \item Alice (premier joueur) possède une stratégie gagnante si et seulement si il existe $x \in X$ tel qu'elle (=Alice) possède une stratégie gagnante en jouant en second dans le jeu de Gale-Stewart $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble $x^{\$} A$ ; \item Bob (second joueur) possède une stratégie gagnante si et seulement si pour tout $x \in X$ il (=Bob) possède une stratégie gagnante en jouant en premier dans le jeu de Gale-Stewart $G_X^{\mathrm{b}}(x^{\$} A)$ défini par le sous-ensemble $x^{\$} A$. \end{itemize} \end{prop} \begin{proof} La démonstration suivante ne fait que (laborieusement) formaliser l'argument « une stratégie gagnante pour Alice détermine un premier coup, après quoi elle a une stratégie gagnante, et une stratégie gagnante pour Bob est prête à répondre à n'importe quel coup d'Alice après quoi il a une stratégie gagnante » : Si Alice (premier joueur) possède une stratégie $\varsigma$ gagnante dans $G_X^{\mathrm{a}}(A)$, on pose $x := \varsigma(())$ le premier coup préconisé par cette stratégie, et on définit $\varsigma'((x_1,x_2,\ldots,x_{i-1})) = \varsigma((x,x_1,x_2,\ldots,x_{i-1}))$ pour $i$ pair : cette définition fait que si $(x_1,x_2,x_3,\ldots)$ est une confrontation où Alice joue en second selon $\varsigma'$ alors $(x,x_1,x_2,x_3,\ldots)$ en est une où elle joue en premier selon $\varsigma$, donc cette suite appartient à $A$ puisque $\varsigma$ est gagnante pour Alice dans $G_X^{\mathrm{a}}(A)$, donc $(x_1,x_2,x_3,\ldots)$ appartient à $x^{\$} A$, et Alice a bien une stratégie gagnante, $\varsigma'$ dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où elle joue en second). Réciproquement, si Alice possède une stratégie gagnante $\varsigma'$ dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où elle joue en second), on définit $\varsigma$ par $\varsigma(()) = x$ et $\varsigma((x,x_1,x_2,\ldots,x_{i-1})) = \varsigma'((x_1,x_2,\ldots,x_{i-1}))$ pour $i > 0$ pair : cette définition fait que si $(x_0,x_1,x_2,x_3,\ldots)$ est une confrontation où Alice joue en premier selon $\varsigma$ alors $x_0 = x$ et $(x_1,x_2,x_3,\ldots)$ est confrontation où elle (Alice) joue en second selon $\varsigma'$, donc cette suite appartient à $x^{\$} A$ puisque $\varsigma'$ est gagnante pour Alice second joueur dans $G_X^{\mathrm{b}}(x^{\$} A)$, donc $(x_0,x_1,x_2,x_3,\ldots)$ appartient à $A$, et Alice a bien une stratégie gagnante, $\varsigma$, dans $G_X^{\mathrm{a}}(A)$ (où elle joue en premier). Si Bob (second joueur) possède une stratégie $\tau$ gagnante dans $G_X^{\mathrm{a}}(A)$ et si $x \in X$ est quelconque, on définit $\tau'((x_1,x_2,\ldots,x_{i-1})) = \tau((x,x_1,x_2,\ldots,x_{i-1}))$ pour $i$ impair : cette définition fait que si $(x_1,x_2,x_3,\ldots)$ est une confrontation où Bob joue en premier selon $\tau'$ alors $(x,x_1,x_2,x_3,\ldots)$ en est une où il joue en second selon $\tau$, donc cette suite n'appartient pas à $A$ puisque $\tau$ est gagnante pour Bob dans $G_X^{\mathrm{a}}(A)$, donc $(x_1,x_2,x_3,\ldots)$ n'appartient pas à $x^{\$} A$, et Bob a bien une stratégie gagnante, $\tau'$, dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où il joue en premier). Réciproquement, si pour chaque $x\in X$ Bob possède une stratégie gagnante dans $G_X^{\mathrm{b}}(x^{\$} A)$ (où il joue en premier), on en choisit une $\tau_x$ pour chaque $x$, et on définit $\tau$ par $\tau((x,x_1,x_2,\ldots,x_{i-1})) = \tau_x((x_1,x_2,\ldots,x_{i-1}))$ pour $i$ impair : cette définition fait que si $(x_0,x_1,x_2,x_3,\ldots)$ est une confrontation où Bob joue en second selon $\tau$ alors $(x_1,x_2,x_3,\ldots)$ est confrontation où il (Bob) joue en premier selon $\tau_{x_0}$, donc cette suite n'appartient pas à ${x_0}^{\$} A$ puisque $\tau_{x_0}$ est gagnante pour Bob premier joueur dans $G_X^{\mathrm{b}}({x_0}^{\$} A)$, donc $(x_0,x_1,x_2,x_3,\ldots)$ n'appartient pas à $A$, et Bob a bien une stratégie gagnante, $\tau$, dans $G_X^{\mathrm{a}}(A)$ (où il joue en second). \end{proof} \thingy En utilisant la terminologie \ref{gale-stewart-winning-positions}, la proposition \ref{strategies-forall-exists-lemma} peut se reformuler de la façon suivante : \begin{itemize} \item une position $\underline{z}$ est gagnante pour le joueur qui doit jouer si et seulement si \emph{il existe} un coup $x$ menant à une position $\underline{z}x$ gagnante pour ce même joueur (qui est maintenant le joueur qui vient de jouer), \item une position $\underline{z}$ est gagnante pour le joueur qui vient de jouer si et seulement si \emph{tous} les coups $x$ mènent à des positions $\underline{z}x$ gagnantes pour ce même joueur (qui est maintenant le joueur qui doit jouer). \end{itemize} (Dans ces affirmations, « un coup $x$ » depuis une position $\underline{z} := (z_0,\ldots,z_{\ell-1})$ doit bien sûr se comprendre comme menant à la position $\underline{z}x := (z_0,\ldots,z_{\ell-1},x)$ obtenue en ajoutant $x$ à la fin.) \subsection{Topologie produit} \begin{defn}\label{definition-product-topology} Soit $X$ un ensemble non vide. Si $\underline{x} := (x_0,x_1,x_2,\ldots)$ est une suite d'éléments de $X$ et $\ell\in\mathbb{N}$, on appelle $\ell$-ième \textbf{voisinage fondamental} de $\underline{x}$, et on note $V_\ell(\underline{x})$ l'ensemble de tous les éléments $(z_0,z_1,z_2,\ldots)$ de $X^{\mathbb{N}}$ dont les $\ell$ premiers termes coïncident avec celles de $\underline{x}$, autrement dit $z_i = x_i$ si $i<\ell$. On dit aussi qu'il s'agit du voisinage fondamental défini par la suite finie $(x_0,\ldots,x_{\ell-1})$ (il ne dépend manifestement que de ces termes), et on peut le noter $V_\ell(x_0,\ldots,x_{\ell-1})$ ou $V(x_0,\ldots,x_{\ell-1})$. Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \textbf{ouvert} [pour la topologie produit] lorsque pour tout $\underline{x} \in A$ il existe un $\ell$ tel que le $\ell$-ième voisinage fondamental $V_\ell(\underline{x})$ de $\underline{x}$ soit inclus dans $A$. Autrement dit : dire que $A$ est ouvert signifie que lorsque $A$ contient une suite $\underline{x} := (x_0,x_1,x_2,\ldots)$, il existe un rang $\ell$ tel que $A$ contienne n'importe quelle suite obtenue en modifiant la suite $\underline{x}$ à partir du rang $\ell$. Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dite \textbf{fermé} lorsque son complémentaire $B := X^{\mathbb{N}} \setminus A$ est ouvert. \end{defn} \thingy On notera qu'il existe des parties de $X^{\mathbb{N}}$ à la fois ouvertes et fermées : c'est le cas non seulement de $\varnothing$ et de $X^{\mathbb{N}}$, mais plus généralement de n'importe quel voisinage fondamental $V_\ell(\underline{x})$ (en effet, $V_\ell(\underline{x})$ est ouvert car si $\underline{y} \in V_\ell(\underline{x})$, c'est-à-dire si $\underline{y}$ coïncide avec $\underline{x}$ sur les $\ell$ premiers termes, alors toute suite $\underline{z}$ qui coïncide avec $\underline{y}$ sur les $\ell$ premiers termes coïncide aussi avec $\underline{x}$ dessus, et appartient donc à $V_\ell(\underline{x})$, autrement dit, $V_\ell(\underline{y})$ est inclus dans $V_\ell(\underline{x})$ ; mais $V_\ell(\underline{x})$ est également fermé car si $\underline{y} \not\in V_\ell(\underline{x})$, alors toute suite $\underline{z}$ qui coïncide avec $\underline{y}$ sur les $\ell$ premiers termes ne coïncide \emph{pas} avec $\underline{x}$ dessus, donc n'appartient pas à $V_\ell(\underline{x})$, autrement dit $V_\ell(\underline{y})$ est inclus dans le complémentaire de $V_\ell(\underline{x})$). Il sera utile de remarquer que l'intersection de deux voisinages fondamentaux $V,V'$ d'une même suite $\underline{x}$ est encore un voisinage fondamental de $\underline{x}$ (en fait, cette intersection est tout simplement égale à $V$ ou à $V'$). \medbreak L'énoncé suivant est une généralité topologique : \begin{prop} Soit $X$ un ensemble non vide. Alors, dans $X^{\mathbb{N}}$ (pour la topologie produit) : \begin{itemize} \item[(i)]$\varnothing$ et $X^{\mathbb{N}}$ sont ouverts, \item[(ii)]une réunion quelconque d'ouverts est un ouvert (i.e., si $A_i$ est ouvert pour chaque $i\in I$ alors $\bigcup_{i\in I} A_i$ est ouvert), \item[(iii)]une intersection finie d'ouverts est un ouvert (i.e., si $A_1,\ldots,A_n$ sont ouverts alors $A_1\cap \cdots \cap A_n$ est ouvert). \end{itemize} \end{prop} \begin{proof} L'affirmation (i) est triviale. Montrons (ii) : si les $A_i$ sont ouverts et si $\underline{x} \in \bigcup_{i\in I} A_i$, alors la définion d'une réunion fait qu'il existe $i$ tel que $\underline{x} \in A_i$, et comme $A_i$ est ouvert il existe un voisinage fondamental de $\underline{x}$ inclus dans $A_i$, donc inclus dans $\bigcup_{i\in I} A_i$ : ceci montre que $\bigcup_{i\in I} A_i$ est ouvert. Montrons (iii) : il suffit de montrer que si $A, A'$ sont ouverts alors $A \cap A'$ est ouvert. Soit $\underline{x} \in A \cap A'$. Il existe des voisinages fondamentaux $V$ et $V'$ de $\underline{x}$ inclus dans $A$ et $A'$ respectivement (puisque ces derniers sont ouverts) : alors $V \cap V'$ est un voisinage fondamental de $\underline{x}$ inclus dans $A \cap A'$ : ceci montre que $A \cap A'$ est ouvert. \end{proof} \subsection{Détermination des jeux ouverts} \thingy\label{fundamental-neighorhood-terminates-game} La remarque suivante, bien que complètement évidente, sera cruciale : si $(x_0,\ldots,x_{\ell-1})$ est une suite finie d'éléments de $X$ (i.e., une position de $G_X$) et $A$ une partie contenant le voisinage fondamental (cf. \ref{definition-product-topology}) défini par $(x_0,\ldots,x_{\ell-1})$, alors Alice possède une stratégie gagnante à partir de $(x_0,\ldots,x_{\ell-1})$ dans le jeu $G_X(A)$ (cf. \ref{gale-stewart-positions-as-games}). Mieux : quoi que fassent l'un et l'autre joueur à partir de ce point, la partie sera gagnée par Alice. C'est tout simplement qu'on a fait l'hypothèse que \emph{toute} suite commençant par $x_0,\ldots,x_{\ell-1}$ appartient à $A$. \begin{thm}[D. Gale \& F. M. Stewart, 1953]\label{gale-stewart-theorem} Si $A \subseteq X^{\mathbb{N}}$ est ouvert, ou bien fermé, alors le jeu $G_X(A)$ est déterminé. \end{thm} \begin{proof}[Première démonstration] Il suffit de traiter le cas ouvert : le cas fermé s'en déduit d'après \ref{remark-player-names} en passant au complémentaire, c'est-à-dire en échangeant les deux joueurs (à condition d'avoir traité le cas ouvert aussi le cas $G_X^{\mathrm{a}}(A)$ où Alice joue en premier et le cas $G_X^{\mathrm{b}}(A)$ où Bob joue en premier). Soit $A \subseteq X^{\mathbb{N}}$ ouvert. Quel que soit le joueur qui commence, on va montrer que si Alice (le joueur qui cherche à jouer dans $A$) n'a pas de stratégie gagnante, alors Bob (le joueur qui cherche à jouer dans le complémentaire) en a une. On va définir une stratégie $\tau$ pour Bob en évitant les positions où Alice a une stratégie gagnante. Si $(x_0,\ldots,x_{i-1})$ est une position où c'est à Bob de jouer et qui n'est pas gagnante pour Alice (c'est-à-dire qu'Alice n'a pas de stratégie gagnante à partir de là, cf. \ref{gale-stewart-winning-positions}), alors d'après \ref{strategies-forall-exists-lemma}, (a) il existe un $x$ tel que $(x_0,\ldots,x_{i-1},x)$ ne soit pas gagnante pour Alice : choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ : toujours d'après \ref{strategies-forall-exists-lemma}, (b) quel que soit $x' \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas gagnante pour Alice (et c'est de nouveau à Bob de jouer). Aux points où $\tau$ n'a pas été défini par ce qui vient d'être dit, on le définit de façon arbitraire. Si $x_0,x_1,x_2,\ldots$ est une confrontation où Bob joue selon $\tau$, on voit par récurrence sur $i$ qu'aucune des positions $(x_0,\ldots,x_{i-1})$ n'est gagnante pour Alice : pour $i=0$ c'est l'hypothèse faite sur le jeu (à savoir, qu'Alice n'a pas de stratégie gagnante depuis la position initiale), pour les positions où c'est à Bob de jouer, c'est la construction de $\tau$ qui assure la récurrence (cf. (a) ci-dessus), et pour les positions où c'est à Alice de jouer, c'est le point (b) ci-dessus qui assure la récurrence. On utilise maintenant le fait que $A$ est supposé ouvert : si $x_0,x_1,x_2,\ldots$ appartient à $A$, alors il existe $\ell$ tel que toute suite commençant par $x_0,\ldots,x_{\ell-1}$ appartienne à $A$. Mais alors Alice a une stratégie gagnante à partir de la position $(x_0,\ldots,x_{\ell-1})$ (cf. \ref{fundamental-neighorhood-terminates-game} : elle ne peut que gagner à partir de là). Or si Bob a joué selon $\tau$, ceci contredit la conclusion du paragraphe précédent. On en déduit que si Bob joue selon $\tau$, la confrontation n'appartient pas à $A$, c'est-à-dire que $\tau$ est gagnante pour Bob. \end{proof} \begin{proof}[Seconde démonstration] Comme dans la première démonstration (premier paragraphe), on remarque qu'il suffit de traiter le cas ouvert. Soit $A \subseteq X^{\mathbb{N}}$ ouvert. On utilise la notion d'ordinaux qui sera introduite ultérieurement. Soit $X^* := \bigcup_{\ell=0}^{+\infty} X^\ell$ l'arbre des positions de $G_X$. On définit les positions « gagnantes en $0$ coups pour Alice » comme les positions $(x_0,\ldots,x_{\ell-1})$ qui définissent un voisinage fondamental inclus dans $A$ (cf. \ref{fundamental-neighorhood-terminates-game} : quoi que les joueurs fassent à partir de là, Alice aura gagné, et on peut considérer qu'Alice a déjà gagné). En supposant définies les positions gagnantes en $\alpha$ coups pour Alice, on définit les positions « gagnantes en $\alpha+1$ coups pour Alice » de la façon suivante : ce sont les positions $(x_0,\ldots,x_{\ell-1})$ où c'est à Alice de jouer et pour lesquelles il existe un $x$ tel que $(x_0,\ldots,x_{\ell-1},x)$ soit gagnante en $\alpha$ coups pour Alice, ainsi que les positions $(x_0,\ldots,x_{\ell-1})$ où c'est à Bob de jouer et pour lesquels, quel que soit $x\in X$, la position $(x_0,\ldots,x_{\ell-1},x)$ est gagnante en $\alpha+1$ coups pour Alice (au sens où on vient de le dire). Enfin, si $\delta$ est un ordinal limite, en supposant définies les positions « gagnantes en $\alpha$ coups pour Alice » pour tout $\alpha < \delta$, on définit une position comme gagnante en $\delta$ coups par Alice lorsqu'elle est gagnante en $\alpha$ coups pour un certain $\alpha < \delta$. La définition effectuée a les propriétés suivantes : (o) si une position est gagnante en $\alpha$ coups pour Alice alors elle est gagnante en $\alpha'$ coups pour tout $\alpha'>\alpha$, (i) si une position où c'est à Bob de jouer est gagnante en $\alpha$ coups pour Alice, alors tout coup (de Bob) conduit à une position gagnante en $\alpha$ coups pour Alice, et (ii) si une position où c'est à Alice de jouer est gagnante en $\alpha > 0$ coups pour Alice, alors il existe un coup (d'Alice) conduisant à une position gagnante en strictement moins que $\alpha$ coups (en fait, si $\alpha = \beta+1$ est successeur, il existe un coup conduisant à une position gagnante en $\beta$ coups par Alice, et si $\alpha$ est limite, la position elle-même est déjà gagnable en strictement moins que $\alpha$ coups). Si la position initiale $()$ est gagnante en $\alpha$ coups par Alice pour un certain ordinal $\alpha$, alors Alice possède une stratégie gagnante consistant à jouer, depuis une position gagnante en $\alpha$ coups, vers une position gagnante en $\beta$ coups pour un certain $\beta < \alpha$ (ou bien $\beta = 0$), qui existe d'après (ii) ci-dessus : comme Bob ne peut passer d'une position gagnante en $\alpha$ coups par Alice que vers d'autres telles positions (cf. (i)), et comme toute suite strictement décroissante d'ordinaux termine, ceci assure à Alice d'arriver en temps fini à une position gagnante en $0$ coups. Réciproquement, si la position initiale $()$ n'est pas gagnante en $\alpha$ coups par Alice quel que soit $\alpha$ (appelons-la « non comptée »), alors Bob possède une stratégie consistant à jouer toujours sur des telles positions non décomptées : d'après la définition des positiosn gagnantes en $\alpha$ coup, quand c'est à Alice de jouer, une position non comptée ne conduit qu'à des positions non comptées, et quand c'est à Bob de jouer, une position non comptée conduit à au moins une condition non comptée. Ainsi, si Bob joue selon cette stratégie, la confrontation $(x_0,x_1,x_2,\ldots)$ ne passe que par des positions non comptées, et en particulier, ne passe jamais par une position gagnante en $0$ coups par Alice, c'est-à-dire qu'elle ne peut pas avoir un voisinage fondamental inclus dans $A$, et comme $A$ est ouvert, elle n'appartient pas à $A$, i.e., la confrontation est gagnée par Bob. \end{proof} \subsection{Détermination des jeux combinatoires} On va définir ici rapidement les notions relatives aux jeux impartiaux à information parfaite pour expliquer comment ces jeux peuvent se ramener à des jeux de Gale-Stewart et comment la détermination des jeux ouverts peut s'appliquer dans ce contexte : \begin{defn}\label{first-definition-impartial-combinatorial-game} Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une relation $E$ irreflexive dont les éléments sont appelés arêtes du graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions générales) dont les sommets seront appelés \textbf{positions} de $G$, et soit $x_0$ un sommet de $G$ qu'on appellera \textbf{position initiale}. Le \textbf{jeu impartial à information parfaite} associé à ces données est défini de la manière suivante : partant de $x = x_0$, Alice et Bob choisissent tour à tour un voisin sortant de $x$, autrement dit, Alice choisit une arête $(x_0,x_1)$ de $G$, puis Bob choisit une arête $(x_1,x_2)$ de $G$, puis Alice choisit une arête $(x_2,x_3)$, et ainsi de suite. Si un joueur ne peut plus jouer, il a perdu ; si la confrontation dure un temps infini, elle est considérée comme nulle (ni gagnée ni perdue par les joueurs). Une \textbf{partie} ou \textbf{confrontation} de ce jeu 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 que le premier joueur \textbf{perd} et que les second \textbf{gagne}, tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que le premier joueur gagne et que le second perd ; enfin, lorsque $x_i$ est défini pour tout entier naturel $i$, on dit que la confrontation est nulle ou que les deux joueurs \textbf{survivent} sans gagner. \end{defn} \thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme en \ref{first-definition-impartial-combinatorial-game}, va définir un, ou plutôt deux, jeux de Gale-Stewart : l'intuition est que si un joueur enfreint la « règle » du jeu (i.e., choisit un sommet qui n'est pas un voisin sortant du sommet actuel), il a immédiatement perdu. Autrement dit, soit $G$ un graphe orienté et $x_0 \in G$. On pose $X = G$ et on partitionne l'ensemble des suites à valeurs dans $X$ en trois : \begin{itemize} \item l'ensemble $D$ des (confrontations nulles, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles que pour chaque $i \in \mathbb{N}$ (y compris $0$) le sommet $x_{i+1}$ soit un voisin sortant de $x_i$ (c'est-à-dire : $(x_i,x_{i+1})$ est une arête de $G$) (bref, personne n'a enfreint la règle), \item l'ensemble $A$ des (confrontations gagnées par Alice, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus petit tel $i$ soit \emph{impair} (i.e., Bob a enfreint la règle en premier), \item l'ensemble $B$ des (confrontations gagnées par Bob, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus petit tel $i$ soit \emph{pair} (i.e., Alice a enfreint la règle en premier). \end{itemize} (On a choisi ici d'indicer les suites par les entiers naturels non nuls : il va de soi que ça ne change rien à la théorie des jeux de Gale-Stewart ! Si on préfère, on peut les faire commencer à $0$, et mettre dans $A$ toutes les suites qui ne commencent pas par $x_0$.) Le jeu de Gale-Stewart $G_X(A)$ est essentiellement identique au jeu considéré en \ref{first-definition-impartial-combinatorial-game}, à ceci près que les nuls sont comptés comme des gains de Bob ; le jeu $G_X(A \cup D)$, pour sa part, est lui aussi identique à ceci près que les nuls sont comptés comme des gains d'Alice. \begin{lem}\label{openness-of-combinatorial-to-gale-stewart} Avec les notations de \ref{combinatorial-to-gale-stewart}, les parties $A$ et $B$ sont ouvertes (pour la topologie produit, cf. \ref{definition-product-topology}). \end{lem} \begin{proof} Soit $(x_1,x_2,x_3,\ldots)$ est une suite d'éléments de $X = G$. Si la suite appartient à $A$ alors, par définition de $A$, il existe un $i$ impair tel que $x_{i+1}$ ne soit pas un voisin sortant de $x_i$ et tel que $x_{j+1}$ soit un voisin sortant de $x_j$ pour tout $j0$ comme voisins sortants (ceci inclut le cas particulier d'un puits), tandis qu'un sommet de valeur de Grundy $>0$ est un sommet ayant au moins un sommet de valeur de Grundy $0$ comme voisin sortant. 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. On verra aussi comment la définir sans l'hypothèse que chaque sommet n'a qu'un nombre fini de voisins sortants (mais ce ne sera pas forcément un entier naturel). En attendant, peut se passer de cette hypothèse pour définir isolément l'ensemble des sommets de valeur de Grundy $0$ : \begin{defn}\label{definition-grundy-kernel} Soit $G$ un graphe orienté bien-fondé. En utilisant le théorème \ref{well-founded-definition}, on définit alors une partie $P \subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P = \varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x) \to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x \in G : f(x) = 0\}$. Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou P-positions) de $G$, tandis que les éléments du complémentaire $G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins sortants sont des N-sommets, et un N-sommet est un sommet qui a au moins un P-sommet pour voisin sortant}. \end{defn} On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si le graphe est bien-fondé, les P-sommets sont les positions du jeu à partir desquelles le joueur précédent a une stratégie gagnante, tandis que les N-sommets sont celles à partir desquelles le joueur suivant (`N' comme « Next ») a une stratégie gagnante (consistant, justement, à jouer vers un P-sommet). \subsection{Généralisations aux graphes non nécessairement bien-fondés} \begin{defn}\label{definition-wfpart} L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé, autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe. \end{defn} \thingy\label{trivial-remark-wfpart} Il sera utile pour la suite de remarquer que la partie bien-fondée de $G$ est à la fois aval-close et aval-inductive (car on peut construire une suite infinie $x_0, x_1, x_2\ldots$, avec $x_{i+1}$ voisin sortant de $x_i$, commençant par un $x_0$ donné si et seulement si on peut le faire en commençant pour un certain voisin sortant $x_1$ de ce $x_0$). \begin{prop}\label{wfpart-is-smallest-inductive} Si $G$ est un graphe orienté non supposé bien-fondé, la partie bien-fondée de $G$ est la plus petite (pour l'inclusion) partie $P$ aval-inductive de $P$ (i.e., vérifiant la propriété « si $x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ », cf. \ref{definition-downstream-closed-inductive}). \end{prop} \begin{proof} La plus petite partie aval-inductive de $G$ a bien un sens, car l'intersection de toutes les parties aval-inductives est encore aval-inductive (cf. \ref{trivial-remark-downstream}). Si $x$ est un sommet de $G$ et $\downstr(x)$ désigne son aval (considéré comme sous-graphe induit de $G$), il est clair que pour toute partie $P$ aval-inductive de $G$, la partie $P \cap \downstr(x)$ de $\downstr(x)$ est aval-inductive dans ce dernier (le point important étant que les voisins sortants d'un sommet de $\downstr(x)$ dans ce dernier sont les mêmes que ceux dans $G$). En particulier, si $\downstr(x)$ est bien-fondé (c'est-à-dire, si $x$ appartient à la partie bien-fondée de $G$), alors $x$ appartient à toute partie aval-inductive de $G$. Mais réciproquement, la partie bien-fondée de $G$ est elle-même aval-inductive (car si $\downstr(y)$ est bien-fondé pour tout voisin sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé, cf. \ref{trivial-remark-wfpart}), donc un sommet qui appartient à toute partie aval-inductive de $G$ est, en particulier, dans la partie bien-fondée de $G$. \end{proof} \thingy Pour pouvoir énoncer le théorème suivant, on aura besoin de faire les rappels, définitions et remarques suivants. Une \textbf{fonction partielle} $A \dasharrow Z$, où $A$ est un ensemble quelconque, n'est rien d'autre qu'une fonction définie $D \to Z$ sur une partie $D\subseteq A$ de $Z$ (appelée \textbf{ensemble de définition} de la partie). Si $f,g\colon A \dasharrow Z$ sont deux fonctions partielles, on dit que $f$ \textbf{prolonge} $g$ et on note $f \supseteq g$ ou $g\subseteq f$, lorsque l'ensemble de définition $D_f$ de $f$ contient celui $D_g$ de $g$ et que $f$ et $g$ coïncident sur $D_f$ (ceci signifie bien que $f \supseteq g$ en tant qu'ensembles si on identifie une fonction avec son graphe). Il s'agit bien sûr là d'un ordre partiel (sur l'ensemble des fonctions partielles $A \dasharrow Z$). Enfin, si $\Phi$ est une fonction partielle elle-même définie sur l'ensemble des fonctions partielles $A \dasharrow Z$ (cet ensemble est $\bigcup_{D\subseteq A} Z^D$, si on veut), on dit que $\Phi$ est \textbf{cohérente} lorsque $\Phi(f) = \Phi(g)$ à chaque fois que $f$ prolonge $g$ et que $\Phi(g)$ est définie (autrement dit, une fois que $\Phi$ est définie sur une fonction partielle $g$, elle est définie sur tout prolongement de $g$ et y prend la même valeur que sur $g$ ; intuitivement, il faut s'imaginer que si $g$ apporte assez d'information pour décider la valeur de $\Phi(g)$, toute information supplémentaire reste cohérente avec cette valeur). \begin{thm}\label{non-well-founded-definition} Soit $G$ un graphe orienté et $Z$ un ensemble quelconque. Notons $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins sortants d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une arête de source $x$). Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et $f$ une fonction \emph{partielle} de l'ensemble des voisins sortants de $x$ vers $Z$ (autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \bigcup_{D \subseteq \outnb(x)} \big(\{x\}\times Z^D\big)$). Soit enfin $\Phi\colon \mathscr{F} \dasharrow Z$ une fonction partielle cohérente en la deuxième variable, c'est-à-dire telle que $\Phi(x,f) = \Phi(x,g)$ dès que $f \supseteq g$ et que $\Phi(x,g)$ est définie. Alors il existe une plus petite (au sens du prolongement) fonction partielle $f\colon G \dasharrow Z$ telle que pour tout $x \in G$ on ait \[ f(x) = \Phi(x,\, f|_{\outnb(x)}) \] (au sens où chacun des deux membres est défini ssi l'autre l'est, et dans ce cas ils ont la même valeur). Si $\Phi(x,g)$ est défini à chaque fois que $g$ est totale, alors la fonction $f$ qu'on vient de décrire est définie \emph{au moins} sur la partie bien-fondée de $G$. \end{thm} \begin{proof} Soit $\mathscr{D}$ l'ensemble des fonctions partielles $f \colon G \dasharrow Z$. Pour $f \in \mathscr{D}$, on définit $\Psi(f)$ comme la fonction partielle $x \mapsto \Phi(x, f|_{\outnb(x)})$. Remarquons que si $f$ prolonge $g$ dans $\mathscr{D}$ alors $\Psi(f)$ prolonge $\Psi(g)$ (c'est une traduction de la cohérence supposée sur $\Phi$). Le lemme suivant (appliqué à $X=G$, les autres notations étant inchangées) permet de conclure à l'existence de $f$. Pour ce qui est de la dernière affirmation, on procède par induction bien-fondée sur la partie bien-fondée de $G$ : si $f|_{\outnb(x)}$ est totale, i.e., si $f$ est définie sur chaque voisin sortant de $x$, alors l'hypothèse faite sur $\Phi$ assure que $f(x)$ est définie, et l'induction bien-fondée ((\ddag) de \ref{well-founded-induction} appliqué à l'intersection $P$ de la partie bien-fondée de $G$ et de l'ensemble de définition de $f$) montre alors que $f$ est définie partout sur la partie bien-fondée de $G$. \end{proof} La démonstration du théorème repose crucialement sur le lemme suivant, dont on va donner deux démonstrations : \begin{lem} Soient $X$ et $Z$ deux ensembles quelconques : notons $\mathscr{D}$ l'ensemble des fonctions partielles $X\dasharrow Z$, qu'on verra comme des parties de $X\times Z$ ne contenant jamais deux couples $(x,z_1)$ et $(x,z_2)$ avec la même première coordonnée. (Lorsque $f\supseteq g$, on dit que « $f$ prolonge $g$ ».) Soit $\Psi \colon \mathscr{D} \to \mathscr{D}$ une fonction (totale !) vérifiant : $\Psi$ est \emph{croissante} pour l'inclusion, c'est-à-dire que si $f$ prolonge $g$, alors $\Psi(f)$ prolonge $\Psi(g)$. Alors il existe une plus petite (au sens du prolongement) fonction partielle $f \in \mathscr{D}$ telle que $\Psi(f) = f$. \end{lem} \begin{proof}[Première démonstration] Montrons d'abord que \emph{si} il existe une fonction partielle $f \in \mathscr{D}$ telle que $\Psi(f) = f$, ou même simplement $\Psi(f) \subseteq f$, alors il en existe une plus petite. Pour cela, il suffit de considérer l'intersection $h$ de toutes les $f$ telles que $\Psi(f) \subseteq f$ (considérées comme des parties de $X\times Z$) : dès lors qu'il existe au moins un $f \in \mathscr{D}$ tel que $\Psi(f) \subseteq f$, cette intersection $h$ est bien définie et est bien un élément de $\mathscr{D}$. Si $\Psi(f) \subseteq f$ alors $h \subseteq f$ (puisque $h$ est l'intersection des $f$), donc $\Psi(h) \subseteq \Psi(f)$ (par croissance de $\Psi$), donc $\Psi(h) \subseteq f$ (par transitivité), et comme ceci est vrai pour tous les $f$ dont l'intersection est $h$, on a finalement $\Psi(h) \subseteq h$ ; mais la croissance de $\Psi$ donne alors aussi $\Psi(\Psi(h)) \subseteq \Psi(h)$, et du coup $\Psi(h)$ fait partie des $f$ qu'on a intersectées pour former $h$, et on a ainsi $h \subseteq \Psi(h)$ ; bref, $\Psi(h) = h$, et $h$ est à la fois le plus petit élément $f \in \mathscr{D}$ vérifiant $\Psi(f) \subseteq f$ (de par sa construction) et le plus petit vérifiant $\Psi(f) = f$ (puisqu'il vérifie cette propriété). Reste à montrer qu'il existe bien une fonction partielle $f$ telle que $\Psi(f) = f$, ou même simplement $\Psi(f) \subseteq f$. Pour cela, on introduit l'ensemble $\mathscr{E}$ des $f \in \mathscr{D}$ qui vérifient $\Psi(f) \supseteq f$ (inclusion dans le sens opposé du précédent !). Notons que $\mathscr{E}$ n'est pas vide puisque $\varnothing \in \mathscr{E}$ (où $\varnothing$ est la fonction vide, définie nulle part). Soit maintenant $\mathfrak{M}$ l'ensemble des applications (totales !) $T\colon\mathscr{E}\to\mathscr{E}$ qui vérifient (i) $T(f) \supseteq f$ pour tout $f\in \mathscr{E}$ et (ii) si $f \supseteq g$ alors $T(f) \supseteq T(g)$. Ainsi $\id_{\mathscr{E}} \in \mathfrak{M}$ (trivialement) et $\Psi \in \mathfrak{M}$ (par définition de $\mathscr{E}$ et par croissance de $\Psi$) ; et si $T, T' \in \mathfrak{M}$ on a $T'\circ T \in \mathfrak{M}$ (en notant $T'\circ T$ la composée). L'observation suivante sera cruciale : si $g \in \mathscr{E}$ et $T, T' \in \mathfrak{M}$, alors on a à la fois $(T'\circ T)(g) \supseteq T(g)$ (d'après (i) pour $T'$) et $(T'\circ T)(g) \supseteq T'(g)$ (d'après (i) pour $T$ et (ii) pour $T'$). Affirmation : si $g \in \mathscr{E}$ alors la réunion des $T(g)$ pour tous les $T\in\mathfrak{M}$ est, en fait, une fonction partielle. En effet, l'observation faite ci-dessus montre que si $T, T' \in \mathfrak{M}$ alors les fonctions partielles $T(g)$ et $T'(g)$ sont toutes deux restrictions d'une même fonction partielle $(T'\circ T)(g)$, donc il ne peut pas y avoir de conflit entre leurs valeurs (au sens où si toutes les deux sont définies en un $x\in X$, elles y coïncident) — c'est exactement ce qui permet de dire que la réunion est encore une fonction partielle. Notons $U(g) := \bigcup_{T\in\mathfrak{M}} T(g)$ cette réunion. On a au moins $U(g) \in \mathscr{D}$. Mais en fait, comme $U(g)$ prolonge tous les $T(g)$, la croissance de $\Psi$ assure que $\Psi(U(g))$ prolonge tous les $\Psi(T(g))$, qui prolongent eux-mêmes les $T(g)$ (puisque $T(g) \in \mathscr{E}$), bref $\Psi(U(g)) \supseteq U(g)$ et ainsi $U(g) \in \mathscr{E}$. Mais alors $U \in \mathfrak{M}$ (on vient de voir que $U$ est une fonction $\mathscr{E}\to\mathscr{E}$, et les propriétés (i) et (ii) sont claires). En particulier, $\Psi\circ U \in \mathfrak{M}$, donc $(\Psi\circ U)(g)$ fait partie des $T(g)$ dont $U(g)$ est la réunion, et on a donc $(\Psi\circ U)(g) \subseteq U(g)$, l'inclusion réciproque ayant déjà été vue (et de toute façon on n'en a pas besoin). On a donc bien trouvé une fonction partielle $f := U(\varnothing)$ telle que $\Psi(f) \subseteq f$ (même $\Psi(f) = f$). \end{proof} \begin{proof}[Seconde démonstration] On utilise la notion d'ordinaux. On pose $f_0 = \varnothing$, et par induction sur l'ordinal $\alpha$ on définit $f_{\alpha+1} = \Psi(f_\alpha)$ et si $\delta$ est un ordinal limite alors $f_\delta = \bigcup_{\gamma<\delta} f_\gamma$. On montre simultanément par induction sur $\alpha$ que $f_\alpha$ est bien définie, est une fonction partielle, et, grâce à la croissance de $\Psi$, prolonge $f_\beta$ pour chaque $\beta<\alpha$ (c'est ce dernier point qui permet de conclure que $\bigcup_{\gamma<\delta} f_\gamma$ est une fonction partielle lorsque $\delta$ est un ordinal limite : la réunion d'une famille totalement ordonnée pour l'inclusion de fonctions partielles est encore une fonction partielle). Les inclusions $f_\beta \subseteq f_\alpha$ pour $\beta<\alpha$ ne peuvent pas être toutes strictes sans quoi on aurait une surjection d'un ensemble sur la classe des ordinaux. Il existe donc $\tau$ tel que $f_{\tau+1} = f_\tau$, c'est-à-dire $\Psi(f_\tau) = f_\tau$. D'autre part, si $\Psi(h) = h$, alors par induction sur $\alpha$ on montre $f_\alpha \subseteq h$ pour chaque $\alpha$ (l'étape successeur étant que si $f_\alpha \subseteq h$ alors $f_{\alpha+1} = \Psi(f_\alpha) \subseteq \Psi(h) = h$), donc en particulier $f_\tau \subseteq h$, et $f_\tau$ est bien le plus petit $f$ tel que $\Psi(f) = f$. \end{proof} \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 $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 sommet qui n'a pour voisins sortants que des sommets terminaux a pour écrasement $\{\varnothing\}$, un sommet qui n'a pour voisins sortants 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 de \ref{well-founded-definition} où $Z$ est remplacé par l'univers de tous les ensembles : nous ne rentrerons pas dans ces subtilités, et admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui vérifie $f(x) = \{f(y) : y\in\outnb(x)\}$ pour chaque $x\in G$. \begin{defn} Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x) = \outnb(x')$) sont égaux. \end{defn} 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. \end{prop} \begin{proof} Si $f$ est injective et si $\outnb(x) = \outnb(x')$ alors en 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 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'$). % % % \section{Théorie combinatoire des jeux impartiaux à information parfaite}\label{section-combinatorial-impartial-games} \textcolor{red}{Section à refondre.} \subsection{Généralités sur les jeux et stratégies} \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} Les sommets de $G$ sont aussi appelés les \textbf{positions} de $G$, et les voisins sortants d'une position $x \in G$ sont aussi appelés les \textbf{options} à partir de $x$. On supposera 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 ; on attire l'attention sur le fait que cela signifie que $x_0$ appartient à la partie bien-fondée (cf. \ref{definition-wfpart}) du graphe $G$. \thingy\label{playing-from-a-position} Si $G$ est un jeu comme en \ref{definition-impartial-combinatorial-game}, et $x \in G$ une position quelconque de $G$, on définit le jeu joué \textbf{à partir} de $x$ comme l'aval de $x$ (c'est-à-dire l'ensemble des positions accessibles à partir de $x$, cf. \ref{definition-accessibility-downstream}) considéré comme un graphe (le sous-graphe induit) et muni du sommet $x$ lui-même comme position initiale. Ceci définit un nouveau jeu qui sera parfois noté $G_x$ et qui sera parfois identifié à $x$ quand aucune confusion ne peut en résulter. (Ainsi, $G_{x_0}$ est exactement $G$.) De façon moins formelle : on peut toujours considérer une position $x$ quelconque d'un jeu $G$ comme position initiale d'un nouveau jeu (le jeu joué si une fois atteinte la position $x$). Cette remarque triviale permet de considérer n'importe quelle fonction d'un jeu impartial à information parfaite comme une fonction de n'importe quelle position de n'importe quel jeu. \begin{defn} Soit $G$ un jeu comme en \ref{definition-impartial-combinatorial-game}. Une \textbf{partie} ou \textbf{confrontation} 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 que le premier joueur \textbf{perd} et que les second \textbf{gagne}, tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que le premier joueur gagne et que le second 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 \textbf{survivent} sans gagner. \end{defn} \thingy Il est parfois plus agréable de donner aux joueurs des noms comme « Alice » et « Bob ». Il faut néanmoins se rappeler, dans la théorie des jeux \emph{impartiaux} considérée dans cette section, que l'identité des joueurs n'est inscrite nulle part dans le jeu : ils ont tous les deux toutes les options possibles depuis chaque position (comparer le jeu de Hackenbush impartial avec les autres en \ref{introduction-hackenbush}). Plutôt que de parler de « premier » et de « second » joueur, on peut aussi parler de \textbf{joueur suivant} et de \textbf{joueur précédent} : le joueur suivant est celui qui doit jouer, c'est-à-dire le premier, et le joueur précédent est celui qui vient de jouer, c'est-à-dire le second. (Ceci est d'ailleurs très malheureux compte tenu des initiales de ces quatre mots...) Il peut paraître bizarre de dire que le second joueur « vient de jouer » quand on commence la partie, mais c'est logique vu que c'est à l'autre de jouer, et c'est cohérent avec la convention \ref{playing-from-a-position} : si on a atteint la position $x$ d'un jeu $G$, le second joueur pour le jeu $G_x$ partant de $x$ est bien le joueur qui vient de jouer pour amener à la position $x$. L'avantage de parler de joueur suivant et de joueur précédent est qu'on se rappelle plus facilement qu'ils échangent leurs rôles à chaque tour. À l'inverse, quand on nomme les joueurs Alice et Bob, on entend généralement que l'un ou l'autre peut commencer mais qu'ils gardent leur identité d'un tour sur l'autre. \medbreak Définissons maintenant la notion de stratégie. On distinguera les stratégies positionnelles, où le choix d'un coup à effectuer dépend uniquement de l'état du jeu, et les stratégies historiques, où le choix dépend de tous les coups joués jusqu'à ce point : \begin{defn} Pour un jeu $G$ comme en \ref{definition-impartial-combinatorial-game}, une \textbf{stratégie positionnelle} est une fonction partielle $\varsigma\colon G \dasharrow G$ telle que $\varsigma(x)$ soit, s'il est défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut comprendre que le joueur abandonne la partie). Une \textbf{stratégie historique} est une fonction partielle $\varsigma \big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où $\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des suites finies de $G$ de longueur non nulle (i.e., des suites $z_0,\ldots,z_{\ell-1}$ d'éléments de $G$ avec $\ell>0$ entier) telle que $\varsigma(z_0,\ldots,z_{\ell-1})$ soit un voisin sortant de $z_{\ell-1}$. Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ on a $\varsigma(x_i) = x_{i+1}$ pour chaque $i$ pair pour lequel $x_i$ est défini, on dit que le premier joueur a joué la partie selon la stratégie positionnelle $\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour chaque $i$ impair pour lequel $x_i$ est défini, on dit que le second joueur a joué la partie selon la stratégie $\tau$. Pour une stratégie historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$ et $\tau(x_i) = x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et $\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement. Si $\varsigma$ et $\tau$ sont deux stratégies (positionnelles ou historiques), on définit $\varsigma \ast \tau$ comme la partie jouée lorsque le premier joueur joue selon $\varsigma$ et le second joue selon $\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)$ ou $\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou $\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas défini, la suite s'arrête là). La stratégie (positionnelle ou historique) $\varsigma$ est dite \textbf{gagnante pour le premier joueur} lorsque le premier joueur gagne toute partie où il joue selon $\varsigma$. La stratégie $\tau$ est dite \textbf{gagnante pour le second joueur} lorsque le second joueur gagne toute partie où il joue selon $\tau$. On définit de même une stratégie \textbf{survivante} (c'est-à-dire, permettant d'assurer au moins le nul) pour le premier joueur, resp. le second joueur. \end{defn} Le résultat suivant explique que, au moins pour les stratégies survivantes, la différence entre stratégies positionnelles et stratégies historiques est sans importance (ce sera aussi le cas pour les stratégies gagnantes, mais on le verra plus loin) : \begin{prop} Soit $G$ un jeu impartial à information parfaite : un joueur possède une stratégie positionnelle survivante si et seulement si ce même joueur possède une stratégie historique survivante. \end{prop} \begin{proof} Si $\varsigma$ est une stratégie positionnelle, on en déduit une stratégie historique $\varsigma_\sharp$ par $\varsigma_\sharp(z_0,\ldots,z_{\ell-1}) = \varsigma(z_{\ell-1})$ (i.e., en ignorant l'historique). Comme une partie est jouée selon $\varsigma_\sharp$ si et seulement si elle l'est selon $\varsigma$, il est évident que $\varsigma_\sharp$ est survivante si $\varsigma$ l'est. Traitons l'autre implication. Mettons pour fixer les idées que le joueur considéré est le premier. Si $\varsigma$ est une stratégie historique, définissons une stratégie positionnelle $\varsigma_\flat$ de la façon suivante : si $y \in G$, s'il existe au moins une partie (=confrontation) $x_0,\ldots,x_{\ell-1}$ dans laquelle le premier joueur joue selon $\varsigma$ et vérifiant $x_{\ell-1} = y$, alors on pose $\varsigma_\flat(y) = \varsigma(x_0,\ldots,x_{\ell-1})$ pour un choix quelconque de $x_0,\ldots,x_{\ell-1}$ (et sinon, $\varsigma_\flat(y)$ n'est pas défini). Soit $x_0,x_1,x_2,\ldots$ une confrontation où le premier joueur joue selon $\varsigma_\flat$ : pour chaque $i$, la confrontation $x_0,\ldots,x_{2i}$ (s'arrêtant à $2i$) est jouée par le premier joueur selon $\varsigma$, et le fait que $\varsigma$ soit une stratégie survivante pour le premier joueur impose que $\varsigma(x_0,\ldots,x_{2i})$ soit défini, ce qui impose à son tour que $\varsigma_\flat(x_{2i})$ soit défini, i.e., $x_{2i+1}$ est toujours défini : donc le premier joueur survit. \end{proof} % % % \end{document}