%% 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{makeidx} %% Self-note: compile index with: %% xindy -M texindy -C utf8 -L french notes-mitro206.idx % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} \usepackage{hyperref} % \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{\precs}{\operatorname{precs}} \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} \newcommand{\gr}{\operatorname{gr}} \newcommand{\rk}{\operatorname{rk}} % \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}} % \newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}} % % % \makeindex \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.} {\footnotesize \tableofcontents \par} \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 \defin{état}, qui évolue dans un ensemble (fini ou infini) d'états ou \defin{positions} possibles ; un certain nombre de \defin{joueurs} choisissent, simultanément ou consécutivement, un \defin{coup} à jouer parmi différentes \defin{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 \defin{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 \defin{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 \defin{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 \defin{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 \defin[somme nulle (jeu à)]{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 \index{partial (jeu)}\index{partisan (jeu)}\defin[impartial (jeu)]{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 à \defin[information parfaite (jeu à)]{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'\defin[information complète (jeu à)]{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 \defin{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 \defin{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 \defin{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 \defin{trouillard}, ou de la \defin[colombe et faucon]{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-dessus : $\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 \defin{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 autour 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 \defin[partage (jeu du)]{jeu du partage} ou \defin[ultimatum (jeu de l')]{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 voisin sortant $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 \defin[nim (jeu de)]{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 \defin{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 \defin{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 \defin{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 \defin{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 \index{Nash (équilibre de)}\defin{équilibre de Nash} (resp., un équilibre de Nash \defin[strict (équilibre de Nash)]{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 \defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle. On peut donc parler de \index{optimale (stratégie)}\defin{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{section-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 \defin[Gale-Stewart (jeu de)]{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 \defin[gain]{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 \defin[position]{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'\defin{arbre} du jeu $G_X$. Une \defin{partie} ou \defin{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 \defin{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 \index{stratégie gagnante}\defin[gagnante (stratégie)]{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 \defin[déterminé (jeu)]{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ée comme définissant un nouveau jeu de Gale-Stewart consistant à jouer \defin{à 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 \defin[gagnante (position)]{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 même 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\label{strategies-forall-exists-reformulation} 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 \defin{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 \defin{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 dit \defin{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éfinition 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)$ (qu'il s'agisse de $G_X^{\mathrm{a}}(A)$ ou $G_X^{\mathrm{b}}(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 (une stratégie « défensive »). 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 positions 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} \thingy Il ne faut pas croire que l'hypothèse « $A$ est ouvert ou bien fermé » est anodine : il existe des jeux $G_X^{\mathrm{a}}(A)$ qui ne sont pas déterminés — autrement dit, même si dans toute confrontation donnée l'un des deux joueurs gagne, aucun des deux n'a de moyen systématique de s'en assurer. Il ne faut pas croire pour autant que les seuls jeux déterminés soient ceux définis par une partie ouverte. Par exemple, il est facile de voir que si $A$ est dénombrable, alors Bob possède une stratégie gagnante (en effet, si $a = \{a_0,a_1,a_2,a_3,\ldots\}$, alors Bob peut jouer au premier coup pour exclure $a_0$, c'est-à-dire jouer un $x_1$ tel que $x_1 \neq a_{0,1}$, puis au second coup pour exclure $a_1$, c'est-à-dire jouer un $x_3$ tel que $x_3 \neq a_{1,3}$, et ainsi de suite $x_{2i+1} \neq a_{i,2i+1}$ : il s'agit d'un « argument diagonal constructif » ; l'argument fonctionne encore, quitte à décaler les indices, si c'est Bob qui commence). Le résultat ci-dessous généralise à la fois le théorème \ref{gale-stewart-theorem} et ce qu'on vient de dire, et il assez technique à démontrer : \begin{thm}[D. A. Martin, 1975] Si $A \subseteq X^{\mathbb{N}}$ est \defin{borélien}, c'est-à-dire appartient à la plus petite partie de $\mathscr{P}(X^{\mathbb{N}})$ stable par complémentaire et réunions dénombrables (également appelée \defin{tribu}) contenant les ouverts, alors le jeu $G_X(A)$ est déterminé. \end{thm} (Autrement dit, non seulement un ouvert et un fermé sont déterminés, mais aussi une intersection dénombrable d'ouverts et une réunion dénombrable de fermés, ou encore une réunion dénombrable d'intersections dénombrables d'ouverts et une intersection dénombrable de réunions dénombrables de fermés, « et ainsi de suite » ; les mots « et ainsi de suite » glosent ici sur la construction des boréliens, qui est plus complexe qu'une simple récurrence.) \thingy Des résultats de détermination encore plus forts ont été étudiés, et ne sont généralement pas prouvables dans la théorie des ensembles usuelle (par exemple, l'« axiome de détermination projective », indémontrable dans $\mathsf{ZFC}$) ou sont même incompatibles avec elle (l'« axiome de détermination », qui affirme que pour toute partie $A \subseteq \{0,1\}^{\mathbb{N}}$ le jeu $G_{\{0,1\}}(A)$ est déterminé, contredit l'axiome du choix, et a des conséquences mathématiques remarquables comme le fait que toute partie de $\mathbb{R}$ est mesurable au sens de Lebesgue). \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{definition-impartial-combinatorial-game} Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une relation $E$ irréflexive 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 \defin[position]{positions} de $G$, et soit $x_0$ un sommet de $G$ qu'on appellera \index{initiale (position)}\defin{position initiale}. Le \index{impartial (jeu)}\index{information parfaite (jeu à)}\defin[combinatoire (jeu)]{jeu combinatoire 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 \defin{partie} ou \defin{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 le second \defin[gain]{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 \defin[survie]{survivent} sans gagner. \end{defn} \thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme en \ref{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 — il n'y a manifestement pas grande différence entre avoir un jeu où un joueur \emph{ne peut pas} faire un certain coup et un jeu où si ce joueur fait ce coup il a immédiatement perdu (quoi qu'il se passe par la suite). On va définir deux jeux de Gale-Stewart plutôt qu'un parce qu'un jeu de Gale-Stewart a forcément un gagnant (il n'y a pas de partie nulle), donc on va définir un jeu où les parties nulles sont comptées au bénéfice de Bob et un autre où elles sont comptées au bénéfice d'Alice. 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 dans le jeu combinatoire, 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 dans le jeu combinatoire, 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 dans le jeu combinatoire, 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{definition-impartial-combinatorial-game}, à ceci près que les confrontations nulles sont comptées 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$ 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$ (à partir d'une position initiale $x_0$) 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. La position initiale $x_0 \in G$ ayant été fixée, si $\varsigma$ et $\tau$ sont deux stratégies (positionnelles ou historiques), on définit $\varsigma \ast \tau$ comme la confrontation jouée lorsque le premier joueur joue selon $\varsigma$ et le second joue selon $\tau$ : autrement dit, $x_0$ est la position initiale, 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 \index{stratégie gagnante}\defin[gagnante (stratégie)]{gagnante pour le premier joueur} à partir de la position initiale $x_0$ lorsque le premier joueur gagne toute confrontation où il joue selon $\varsigma$, c'est-à-dire que la confrontation est finie et que le dernier $x_i$ défini l'est pour un $i$ impair. On définit de même une stratégie $\varsigma$ \index{stratégie survivante}\defin[survivante (stratégie)]{survivante} (c'est-à-dire, permettant d'assurer au moins le nul) pour le premier joueur à partir d'une position initiale $x_0$, c'est-à-dire que dans toute confrontation où il joue selon $\varsigma$, soit la confrontation est infinie (donc nulle) soit le dernier $x_i$ défini l'est pour un $i$ impair. \end{defn} \thingy La notion de stratégie pour le second joueur peut être définie de façon analogue, bien sûr, mais la notion n'a pas beaucoup d'intérêt : une stratégie gagnante pour le second joueur à partir de $x_0$ est la même chose qu'une stratégie gagnante pour le premier joueur à partir de tout voisin sortant de $x_0$. Pour travailler avec les stratégies positionnelles, il vaut mieux supposer qu'elles sont, en fait, gagnantes partout où elles sont définies, ce qui amène à faire la définition suivante : \thingy\label{set-of-everywhere-winning-positional-strategies} Dans ce qui suit, on va fixer un graphe orienté $G$ et on aura besoin d'introduire l'ensemble $\mathcal{S}$ de ce qu'on pourrait appeler les « stratégies positionnelles gagnantes partout où définies », c'est-à-dire des stratégies positionnelles $\varsigma$ gagnantes pour le premier joueur à partir de n'importe quel point $x_0$ où $\varsigma$ est défini ; autrement dit, il s'agit de l'ensemble des fonctions partielles $\varsigma\colon G \dasharrow G$ telles que \begin{itemize} \item si $\varsigma(x)$ est défini alors il est un voisin sortant de $x$, et que \item si $\varsigma(x_0)$ est défini et si $(x_i)$ est une suite (\textit{a priori} finie ou infinie) partant de $x_0$, dans laquelle $\varsigma(x_i) = x_{i+1}$ pour $i$ impair, et $x_{i+1}$ est voisin sortant de $x_i$ pour tout $i$, alors la suite est de longueur finie et le dernier $x_i$ défini l'est pour un $i$ impair \end{itemize} (i.e., le premier joueur gagne n'importe quelle confrontation à partir d'une position initiale $x_0$ du domaine de définition de $\varsigma$ et où il joue selon $\varsigma$). L'ensemble $\mathcal{S}$ est partiellement ordonné par l'inclusion (si $\varsigma,\tau \in \mathcal{S}$, on dit que $\varsigma$ \defin{prolonge} $\tau$ et on note $\varsigma \supseteq \tau$ ou $\tau \subseteq \varsigma$, lorsque l'ensemble de définition de $\varsigma$ contient celui de $\tau$ et que $\varsigma$ et $\tau$ coïncident là où $\tau$ est définie : ceci signifie bien que $\varsigma \supseteq \tau$ en tant qu'ensembles). \begin{lem}\label{positional-strategies-merging-lemma} Si $\varsigma,\varsigma' \in \mathcal{S}$ avec la notation introduite en \ref{set-of-everywhere-winning-positional-strategies}, alors il existe $\varsigma'' \in \mathcal{S}$ qui prolonge $\varsigma$ et qui est également définie en tout point où $\varsigma'$ l'est. \end{lem} \begin{proof} Définissons $\varsigma''$ par $\varsigma''(x) = \varsigma(x)$ si $\varsigma(x)$ est définie et $\varsigma''(x) = \varsigma'(x)$ si $\varsigma(x)$ n'est pas définie mais que $\varsigma'(x)$ l'est. Il est évident que $\varsigma''$ prolonge $\varsigma$ et est également définie en tout point où $\varsigma'$ l'est : il reste à voir que $\varsigma'' \in \mathcal{S}$. Mais si $x_0,x_1,x_2,\ldots$ (\textit{a priori} finie ou infinie) est une confrontation jouée par le premier joueur selon $\varsigma''$, montrons qu'elle est nécessairement gagnée par le premier joueur : or le premier joueur a soit joué selon $\varsigma$ tout du long, soit selon $\varsigma'$ tout du long, soit selon $\varsigma'$ puis $\varsigma$, mais dans tous les cas il gagne. De façon détaillée : soit $x_0$ est domaine de définition de $\varsigma$ auquel cas tous les $x_i$ pairs le sont et la confrontation est gagnée par le premier joueur ; soit $x_0$ est dans le domaine de définition de $\varsigma'$ mais pas de $\varsigma$, auquel cas il n'existe qu'un nombre fini de $i$ pairs tels que $x_i$ ne soit pas dans domaine de définition de $\varsigma$ (puisque $\varsigma'$ ne peut pas donner une partie nulle) et si $j$ est le plus grand d'entre eux, $x_{j+1}$ est défini, et soit $x_{j+2}$ n'est pas défini (auquel cas le premier joueur a gagné) soit $x_{j+2}$ est dans le domaine de définition de $\varsigma$ et de nouveau le premier joueur gagne à partir de là. \end{proof} \begin{lem}\label{positional-strategies-union-lemma} Si $\varsigma_i \in \mathcal{S}$ pour chaque $i\in I$ avec la notation introduite en \ref{set-of-everywhere-winning-positional-strategies}, et si pour tous $i,j$ les fonctions $\varsigma_i$ et $\varsigma_j$ coïncident là où elles sont toutes deux définies, alors la fonction $\bigcup_{i\in I} \varsigma_i$ (c'est-à-dire la fonction définie sur la réunion des ensembles de définition des $\varsigma_i$ et qui coïncide avec n'importe quel $\varsigma_i$ sur l'ensemble de définition de celui-ci) appartient encore à $\mathcal{S}$. \end{lem} \begin{proof} Si $x_0,x_1,x_2,\ldots$ (\textit{a priori} finie ou infinie) est une confrontation jouée par le premier joueur selon $\varsigma := \bigcup_{i\in I} \varsigma_i$, alors en fait elle est jouée tout du long selon $\varsigma_i$ où $i$ est n'importe quel indice tel que $\varsigma_i(x_0)$ soit définie. Comme $\varsigma_i \in \mathcal{S}$, cette confrontation est gagnée par le premier joueur. \end{proof} Le résultat ensembliste suivant sera admis (même si on pourrait s'en sortir en appliquant \ref{fixed-point-lemma-for-partial-functions} à la place) : \begin{lem}[principe maximal de Hausdorff]\label{hausdorff-maximal-principle} Soit $\mathscr{F}$ un ensemble de parties d'un ensemble $A$. On suppose que $\mathscr{F}$ est non vide et que pour toute partie non vide $\mathscr{T}$ de $\mathscr{F}$ totalement ordonnée par l'inclusion (c'est-à-dire telle que pour $P,P' \in \mathscr{T}$ on a soit $P \subseteq P'$ soit $P \supseteq P'$) la réunion $\bigcup_{P \in \mathscr{T}} P$ soit contenue dans un élément de $\mathscr{F}$. Alors il existe dans $\mathscr{F}$ un élément $M$ maximal pour l'inclusion (c'est-à-dire que si $P \supseteq M$ avec $P \in \mathscr{F}$ alors $P=M$). \end{lem} \begin{prop}\label{existence-of-maximal-positional-strategy} Avec la notation introduite en \ref{set-of-everywhere-winning-positional-strategies}, il existe $\varsigma \in \mathcal{S}$ maximal pour l'inclusion (au sens où si $\varsigma \subseteq \varsigma'$ avec $\varsigma' \in \mathcal{S}$ alors $\varsigma = \varsigma'$) ; de plus, si $\varsigma' \in \mathcal{S}$, alors $\varsigma$ est défini en tout point où $\varsigma'$ l'est. \end{prop} \begin{proof} L'existence de $\varsigma \in \mathcal{S}$ maximal pour l'inclusion découle immédiatement de \ref{hausdorff-maximal-principle} en utilisant \ref{positional-strategies-union-lemma} pour constater que si $\mathscr{T} \subseteq \mathcal{S}$ est totalement ordonné pour l'inclusion alors la réunion $\bigcup_{\varsigma\in\mathscr{T}} \varsigma$ appartient à $\mathcal{S}$. Une fois trouvé $\varsigma \in \mathcal{S}$ maximal pour l'inclusion, si $\varsigma' \in \mathcal{S}$, d'après \ref{positional-strategies-merging-lemma}, on peut trouver $\varsigma''$ prolongeant $\varsigma$ et défini partout où $\varsigma'$ l'est, et comme $\varsigma$ est maximal, on a $\varsigma'' = \varsigma$, donc $\varsigma$ est bien défini partout où $\varsigma'$ l'est. \end{proof} \thingy\label{notation-n-and-p-sets-for-combinatorial-games} En continuant les notations introduites en \ref{set-of-everywhere-winning-positional-strategies}, on fixe maintenant $\varsigma \in \mathcal{S}$ maximal pour l'inclusion (dont l'existence est garantie par la proposition \ref{existence-of-maximal-positional-strategy}). Soit $N$ l'ensemble des sommets $x$ de $G$ où $\varsigma(x)$ est défini (i.e., le domaine de définition de $\varsigma$) ; on vient de voir que $N$ est aussi l'ensemble des points où un élément quelconque de $\mathcal{S}$ est défini, i.e., l'ensemble des positions à partir desquelles le premier joueur a une stratégie positionnelle gagnante. Soit $P$ l'ensemble des sommets $x\in G$ dont tous les voisins sortants appartiennent à $N$ (y compris s'il n'y a pas de voisin sortant, i.e., si $x$ est un puits) : clairement, $P$ est l'ensemble des positions à partir desquelles le second joueur a une stratégie positionnelle gagnante (quel que soit le coup du joueur adversaire, il amènera à une position où on a une stratégie gagnante). Enfin, on note $D := G\setminus(N\cup P)$ l'ensemble des sommets restants. \begin{prop}\label{positional-strategies-forall-exists-lemma} Avec les notations introduites en \ref{set-of-everywhere-winning-positional-strategies} et \ref{notation-n-and-p-sets-for-combinatorial-games}, \begin{itemize} \item[(i)]un sommet $x\in G$ appartient à $N$ si et seulement si il a au moins un voisin sortant qui appartient à $P$, \item[(ii)]un sommet $x\in G$ appartient à $P$ si et seulement si tous ses voisins sortants appartiennent à $N$. \end{itemize} \end{prop} \begin{proof} L'affirmation (ii) est la définition même de $P$ et n'a donc pas à être prouvée. Il s'agit donc de montrer (i). Si $x\in N$ alors $y := \varsigma(x)$ est un voisin sortant de $x$ qui appartient à $P$ puisque $\varsigma \in \mathcal{S}$. Réciproquement, si $x$ a un voisin sortant $y$ qui appartient à $P$, et si $\varsigma(x)$ n'était pas défini, on pourrait étendre $\varsigma$ en posant $\varsigma(x) = y$, ce qui donnerait un élément de $\mathcal{S}$ (toute partie jouée à partir de $x$ conduit à $y$ et de là à des points où $\varsigma$ est définie, donc est gagnée par le premier joueur), contredisant la maximalité de $\varsigma$ ; c'est donc que $\varsigma(x)$ était bien défini, i.e., $x\in N$. \end{proof} \thingy Par contraposée, sur l'ensemble $D := G\setminus(N\cup P)$ des sommets restants de $G$, on a les propriétés suivantes : $x\in G$ appartient à $D$ si et seulement si \begin{itemize} \item[(i*)]tous les voisins sortants de $x$ sont dans $N\cup D$ \emph{et} \item[(ii*)]au moins l'un d'entre eux appartient à $D$. \end{itemize} On définit alors une stratégie positionnelle $\tau$ étendant $\varsigma$ de la façon suivante : si $\varsigma(x)$ est défini (i.e., $x \in N$), on pose $\tau(x) = \varsigma(x)$, et si $x \in D$ on choisit pour $\tau(x)$ un voisin sortant de $x$ qui appartienne à $D$ (lequel voisin existe d'après (ii*)). À partir d'un sommet $x_0$ dans $D$, si l'un ou l'autre joueur joue selon $\tau$, ce joueur survit, puisque soit son adversaire le laisse toujours dans $D$ auquel cas le joueur considéré peut toujours jouer (selon $\tau$) en restant dans $D$, soit son adversaire quitte $D$ et d'après (i*) joue vers $N$, et alors le joueur considéré gagne puisqu'il joue selon $\varsigma$. Bref, à partir d'un sommet de $N$ le premier joueur a une stratégie \emph{positionnelle} gagnante, à partir d'un sommet de $P$ c'est le second joueur qui en a une, et à partir d'un sommet de $D$ les deux joueurs ont une stratégie positionnelle survivante. (Dans tous les cas, on peut utiliser le $\tau$ qu'on vient de construire comme stratégie positionnelle.) \begin{thm}\label{positional-determinacy-of-perfect-information-games} Soit $G$ un graphe orienté. Quel que soit le sommet $x_0$ de $G$ choisi comme position initiale, dans le jeu combinatoire impartial à information parfaite considéré en \ref{definition-impartial-combinatorial-game}, exactement l'une des trois affirmations suivantes est vraie : \begin{itemize} \item le premier joueur (Alice) possède une stratégie positionnelle gagnante, \item le second joueur (Bob) possède une stratégie positionnelle gagnante, \item chacun des deux joueurs possède une stratégie positionnelle survivante. \end{itemize} En particulier, l'existence d'une stratégie positionnelle gagnante ou survivante est équivalente à celle d'une stratégie historique de même nature. De plus, si $N,P,D$ sont les ensembles de sommets $x_0$ à partir desquels chacune des trois affirmations ci-dessus est vraie, \begin{itemize} \item un sommet $x\in G$ appartient à $N$ si et seulement si il a au moins un voisin sortant qui appartient à $P$, \item un sommet $x\in G$ appartient à $P$ si et seulement si tous ses voisins sortants appartiennent à $N$, \item un sommet $x\in G$ appartient à $D$ si et seulement si tous ses voisins sortants appartiennent à $N\cup D$ et au moins l'un d'eux appartient à $D$. \end{itemize} \end{thm} \begin{proof} L'existence des stratégies positionnelles a déjà été montré ci-dessus, ainsi que les propriétés sur $N,P,D$. L'équivalence entre stratégies positionnelles et historiques vient du fait que toute stratégie positionnelle peut être vue comme une stratégie historique (en ignorant l'historique) et du fait que les trois cas sont exclusifs aussi bien pour les stratégies historiques que positionnelles. \end{proof} \thingy On a en particulier redémontré le théorème \ref{determinacy-of-perfect-information-games}, même si la démonstration suivie ici (consistant à prendre une stratégie positionnelle maximale pour l'inclusion) n'est peut-être pas très éclairante. En utilisant la notion d'ordinaux, on pourrait donner une autre démonstration, plus explicite, du théorème \ref{positional-determinacy-of-perfect-information-games} : elle consiste à reprendre la seconde démonstration qui a été donnée du théorème \ref{determinacy-of-perfect-information-games} et à constater qu'en la modifiant à peine elle conduit maintenant à définir une stratégie positionnelle ; un peu plus précisément, on définit par induction sur l'ordinal $\alpha$ les positions gagnantes en $\alpha$ coups par le premier joueur et les positions gagnantes en $\alpha$ coups par le second joueur, et une stratégie gagnante consiste à jouer d'une position gagnante en $\alpha$ coups pour le premier joueur vers une position gagnante en $\beta<\alpha$ coups pour le second joueur (pour les stratégies survivantes, on complète en jouant d'une position non étiquetée vers une position non étiquetée, mais le problème de la survie est de toute façon plus simple). Dans le cas des jeux définis par un graphe bien-fondé (cf. \ref{definitions-graphs}), c'est-à-dire que le nul est impossible, la détermination est beaucoup plus simple à démontrer en on en verra encore une nouvelle démonstration dans le cadre de la théorie de Grundy. Un bonus au théorème \ref{positional-determinacy-of-perfect-information-games} est l'affirmation suivante : \begin{prop}\label{p-d-n-vertices-of-perfect-information-games} Dans le contexte du théorème \ref{positional-determinacy-of-perfect-information-games}, si $N^*,P^*,D^*$ est une partition de $G$ en trois parties vérifiant les trois propriétés qui ont été énoncées pour $N,P,D$ (en remplaçant $N,P,D$ par $N^*,P^*,D^*$ respectivement), alors on a $N\subseteq N^* \subseteq N\cup D$ et $P\subseteq P^* \subseteq P\cup D$ et bien sûr $D\supseteq D^*$. En particulier, si on utilise le théorème \ref{non-well-founded-definition} ci-dessous pour définir la \emph{plus petite} (pour l'inclusion) fonction partielle $f\colon G \dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ telle que $f(x)$ vaille $\mathtt{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel $f(y) = \mathtt{N}$, et que $f(x)$ vaille $\mathtt{N}$ ssi pour tout voisin sortant $y$ de $x$ on a $f(y) = \mathtt{P}$, alors $f(x)$ vaut $\mathtt{P}$ ou bien $\mathtt{N}$ ou bien est indéfinie lorsque respectivement le premier joueur a une stratégie gagnante, le second joueur en a une, ou les deux ont une stratégie survivante. \end{prop} \begin{proof} Si $N^*,P^*,D^*$ ont les mêmes propriétés que $N,P,D$, on peut définir une stratégie (positionnelle) consistant à jouer à partir de $N^*$ dans $P^*$ (c'est-à-dire à choisir pour chaque sommet de $N^*$ un voisin sortant dans $P^*$) et à partir de $D^*$ dans $D^*$ : si le premier joueur suit cette stratégie à partir d'un sommet dans $N^*$ ou $D^*$ ne peut pas perdre puisque les propriétés des parties font que son coup sera toujours défini : donc $N^* \cup D^* \subseteq N \cup D$, ce qui signifie en passant au complémentaire $P^* \supseteq P$, et si le second joueur suit cette stratégie à partir d'un sommet dans $P^*$ ou $D^*$ il ne peut pas perdre non plus : donc $P^* \cup D^* \subseteq P \cup D$, ce qui signifie exactement $N^* \supseteq N$. Le deuxième paragraphe est une reformulation de la même affirmation : la fonction $f \colon G \dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ définie par $f(x) = \mathtt{P}$ lorsque $x \in P$ et $f(x) = \mathtt{N}$ lorsque $x \in N$ est la plus petite fonction partielle vérifiant les propriétés qu'on a dites, i.e., la plus petite telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ avec les notations du théorème \ref{non-well-founded-definition} et $\Phi(x, g)$ valant $\mathtt{N}$ si $g(y)$ est défini et vaut $\mathtt{N}$ pour au moins un $y \in \outnb(x)$ et $\mathtt{P}$ si $g(y)$ est défini et vaut $\mathtt{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente en la seconde variable, on est bien dans le cas d'application duthéorème \ref{non-well-founded-definition}, même si ici on a déjà démontré l'existence d'une plus petite $f$). \end{proof} % % % \section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction} Le but de cette partie est de présenter les outils fondamentaux sur les graphes orientés bien-fondés (cf. \ref{definitions-graphs}) utiles à la théorie combinatoire des jeux impartiaux. Il s'agit notamment de la théorie de l'induction bien-fondée (cf. \ref{scholion-well-founded-induction} et \ref{scholion-well-founded-definition}). \subsection{Graphes orientés bien-fondés}\label{subsection-well-founded-graphs} \begin{defn}\label{definitions-graphs} Un \defin{graphe orienté [simple]} est la donnée d'un ensemble $G$ et d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit d'un ensemble $G$ muni d'une relation $E$ irréflexive. Les éléments de $G$ s'appellent \defin[sommet]{sommets} et les éléments de $E$ \defin[arête]{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de cible $y$, ou encore que $y$ est \defin[atteindre]{atteint} par une arête de source $x$, ou encore que $y$ est un \index{sortant (voisin)}\defin{voisin sortant} de $x$, et on notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins sortants de $x$. Un sommet qui n'a pas de voisin sortant est appelé \defin{puits} dans $G$. Un tel graphe est dit \defin[fini (graphe)]{fini} lorsque $G$ est fini (il est clair que $E$ l'est alors aussi). Il est dit \defin[acyclique (graphe)]{acyclique} lorsqu'il n'existe pas de suite finie (« cycle ») $x_0,\ldots,x_{n-1}$ de sommets telle que $(x_i,x_{i+1})$ soit une arête pour chaque $0\leq i\leq n-1$, où on convient que $x_n = x_0$. Un graphe orienté (possiblement infini) est dit \defin[bien-fondé (graphe)]{bien-fondé} ou \defin{progressivement fini} lorsqu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets telle que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$ (i.e., aucun cycle ni chemin infini, cf. ci-dessous). \end{defn} \thingy\label{finite-graph-is-well-founded-iff-acyclic} Il est évident que tout graphe bien-fondé est acyclique (s'il existe un cycle $x_0,\ldots,x_{n-1}$, on en déduit une suite infinie en posant $x_i = x_{i\mod n}$) ; pour un graphe \emph{fini}, la réciproque est vraie : en effet, s'il existe une suite infinie $x_0,x_1,x_2,\ldots$ avec une arête de $x_i$ à $x_{i+1}$ pour chaque $i$, il doit exister $n$ tel que $x_n = x_0$, et on obtient alors un cycle $x_0,\ldots,x_{n-1}$. En général, cependant, les notions sont distinctes, l'exemple le plus évident étant sans doute celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$ à $i+1$ pour chaque $i$. \begin{defn}\label{definition-accessibility-downstream} Si $G$ est un graphe orienté on appelle \defin[accessibilité]{relation d'accessibilité} la clôture réflexive-transitive de la relation donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est accessible à partir de $x$ lorsqu'il existe $x {=} x_0,x_1,\ldots,x_{n-1},x_n {=} y$ tels que pour chaque $i$ le sommet $x_{i+1}$ soit voisin sortant de $x_i$ (on autorise $n=0$, c'est-à-dire que chaque sommet est toujours accessible à partir de lui-même). On pourra aussi introduire la relation d'\defin{accessibilité stricte} qui est la clôture transitive : autrement dit, la différence avec l'accessibilité définie ci-dessus est qu'on impose $n>0$, i.e., on ne relie pas un sommet à lui-même. L'ensemble des sommets accessibles à partir d'un sommet $x$ s'appellera aussi l'\defin{aval} de $x$ et pourra se noter $\downstr(x)$ (c'est donc la plus petite partie $P$ de $G$ telle que $x\in P$ et $y\in P \limp \outnb(y)\subseteq P$, cf. \ref{definition-downstream-closed-inductive}). On peut considérer l'aval de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire, considérer le graphe dont l'ensemble des sommets est l'aval de $x$ et dont les arêtes sont celles qui partent d'un tel sommet). On remarquera la convention faite que $x$ appartient à son propre aval. \end{defn} \thingy On peut remarquer que la relation d'accessibilité sur $G$ est antisymétrique (i.e., est une relation d'ordre partiel large) si et seulement si $G$ est acyclique : l'accessibilité stricte est alors l'ordre strict correspondant. Lorsque $G$ est bien-fondé, la relation d'accessibilité stricte est elle-même bien-fondée (au sens où le graphe qu'elle définit est bien-fondé) : si on la voit comme une relation d'ordre partiel ($x>y$ signifiant que $y$ est accessible à partir de $x$), cela signifie qu'il n'y a pas de suite infinie strictement décroissante. Une relation d'ordre \emph{total} (strict) $>$ qui soit bien-fondée, i.e., telle qu'il n'existe pas de suite infinie strictement décroissante, est appelée un \defin{bon ordre}, ou définir un ensemble \defin[bien-ordonné (ensemble)]{bien-ordonné}. \begin{defn}\label{definition-downstream-closed-inductive} Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de $G$ est \defin{aval-clos} lorsqu'il vérifie la propriété suivante : « si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $P$ » (soit $x\in P \limp \outnb(x)\subseteq P$ ; ou de façon équivalente, « tout sommet accessible à partir d'un sommet de $P$ est encore dans $P$ »,). Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$ est \defin{aval-inductif} lorsqu'il vérifie la propriété suivante : « si $x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient tout sommet dont tous les voisins sortants sont dans $P$ », soit $\outnb(x)\subseteq P \limp x\in P$). \end{defn} \thingy\label{trivial-remark-downstream} Il est clair qu'une intersection ou réunion quelconque d'ensembles aval-clos est encore aval-close. L'aval de $x$ (ensemble des sommets accessibles depuis $x$) est toujours aval-clos, c'est même la plus petite partie aval-close contenant $x$, et il est facile de se convaincre qu'un ensemble de sommets est aval-clos si et seulement si il est une réunion d'avals. Pour ce qui est des ensembles aval-inductifs, il est clair qu'une intersection quelconque d'ensembles aval-inductifs est aval-inductive. Leur nature, au moins dans un graphe bien-fondé, va être précisée dans ce qui suit, et ceci justifiera le terme d'« aval-inductif ». \begin{prop}[induction bien-fondée]\label{well-founded-induction} Pour un graphe orienté $G$, les affirmations suivantes sont équivalentes : \begin{itemize} \item[(*)]$G$ est bien-fondé. \item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$ contient un sommet $x \in N$ qui est un puits pour $N$, c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in N$ (i.e., aucun voisin sortant de $x$ n'appartient à $N$). \item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété suivante « si $x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e., « $P$ est aval-inductif », cf. \ref{definition-downstream-closed-inductive}), alors $P = G$. \end{itemize} \end{prop} \begin{proof} L'équivalence entre (\dag) et (\ddag) est complètement formelle : elle s'obtient en posant $P = G\setminus N$ ou réciproquement $N = G\setminus P$, en passant à la contraposée, et en passant aussi à la contraposée à l'intérieur de la propriété d'être aval-inductif (entre guillemets dans (\ddag)), et encore une fois dans la prémisse de cette propriété (« tout voisin sortant de $x$ appartient à $P$ » équivaut à « aucun voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un puits pour $N$ »). Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à l'ensemble $N := \{x_0,x_1,x_2,\ldots\}$ des sommets d'une suite telle qu'il y ait une arête de $x_i$ à $x_{i+1}$. Pour montrer que (*) implique (\dag), on suppose que $N$ est un ensemble non-vide de sommets sans puits [i.e., puits pour $N$] : comme $N$ est non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas un puits on peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par une arête, puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de suite — par récurrence (et par l'axiome du choix [dépendants]), on construit ainsi une suite $(x_i)$ de sommets telle qu'il y ait une arête de $x_i$ à $x_{i+1}$. \end{proof} La définition (*) choisie pour un graphe bien-fondé est la plus compréhensible, mais en un certain sens la définition (\ddag) est « la bonne » (en l'absence de l'axiome du choix, il faut utiliser (\dag) ou (\ddag), et en mathématiques constructives il faut utiliser (\ddag)). En voici une traduction informelle : \begin{scho}\label{scholion-well-founded-induction} Pour montrer une propriété $P$ sur les sommets d'un graphe bien-fondé, on peut supposer (comme « hypothèse d'induction »), lorsqu'il s'agit de montrer que $x$ a la propriété $P$, que cette propriété est déjà connue de tous les voisins sortants de $x$. \end{scho} Exactement comme le principe de récurrence sur les entiers naturels, le principe d'induction bien-fondée peut servir non seulement à démontrer des propriétés sur les graphes bien-fondés, mais aussi à définir des fonctions dessus : \begin{thm}[définition par induction bien-fondée]\label{well-founded-definition} Soit $G$ un graphe orienté bien-fondé 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 de l'ensemble des voisins sortants de $x$ vers $Z$ (autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \big(\{x\}\times Z^{\outnb(x)}\big)$). Soit enfin $\Phi\colon \mathscr{F} \to Z$ une fonction quelconque. Alors il existe une unique fonction $f\colon G \to Z$ telle que pour tout $x \in G$ on ait \[ f(x) = \Phi(x,\, f|_{\outnb(x)}) \] \end{thm} \begin{proof} Montrons d'abord l'unicité : si $f$ et $f'$ vérifient toutes les deux la propriété annoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels que $f(x) = f'(x)$. Si $x \in G$ est tel que $\outnb(x) \subseteq P$, c'est-à-dire que $f|_{\outnb(x)} = f'|_{\outnb(x)}$, alors $f(x) = \Phi(x,\, f|_{\outnb(x)}) = \Phi(x,\, f'|_{\outnb(x)}) = f'(x)$, autrement dit, $x\in P$. La phrase précédente affirme précisément que $P$ vérifie la propriété entre guillemets dans (\ddag) de \ref{well-founded-induction}, et d'après la proposition en question, on a donc $P = G$, c'est-à-dire $f = f'$. Ceci montre l'unicité. Pour montrer l'existence, on considère l'ensemble $\mathfrak{E}$ des fonctions $e\colon H\to Z$ définies sur une partie aval-close $H \subseteq G$ et telles que pour tout $e(x) = \Phi(x, e|_{\outnb(x)})$ pour tout $x\in H$. Si $e,e' \in \mathfrak{E}$ alors $e$ et $e'$ coïncident là où toutes deux sont définies, comme le montre l'unicité qu'on a montrée (appliquée à $e$ et $e'$ sur l'ensemble aval-clos $H \cap H'$ de définition commun de $e$ et $e'$). En particulier, la réunion [des graphes] de tous les $e\in\mathfrak{E}$ définit encore un élément $f$ de $\mathfrak{E}$, maximal pour le prolongement. Soit $P$ l'ensemble des $x \in G$ où $f$ est définie. Si $P$ contient (i.e., $f$ est définie sur) tous les voisins sortants d'un certain $x\in G$, alors $f$ est nécessairement définie aussi en $x$, sans quoi on pourrait l'y prolonger par $f(x) = \Phi(x,\, f|_{\outnb(x)})$, ce qui contredirait la maximalité de $f$. Par induction bien-fondée, on en conclut $P = G$, c'est-à-dire que $f$ est définie sur $G$ tout entier. C'est ce qu'on voulait. \end{proof} Ce théorème est difficile à lire. En voici une traduction informelle : \begin{scho}\label{scholion-well-founded-definition} Pour définir une fonction $f$ sur un graphe bien-fondé, on peut supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e., connu) sur tous les voisins sortants de $x$ : autrement dit, on peut librement utiliser la valeur de $f(y)$ sur chaque sommet $y$ voisin sortant de $x$, dans la définition de $f(x)$. \end{scho} Voici un exemple d'application de la définition par induction bien-fondée : \begin{defn}\label{definition-well-founded-rank} Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a qu'un nombre fini de voisins sortants (par exemple, un graphe fini acyclique). En utilisant le théorème \ref{well-founded-definition}, on définit alors une fonction $\rk\colon G \to \mathbb{N}$ par $\rk(x) = \max\{\rk(y) : y\in\outnb(x)\} + 1$ où il est convenu que $\max\varnothing = -1$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ si $x$ est un puits, et qu'on appelle $\rk$ la fonction telle que $\rk(x) = \Phi(x, \rk|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le théorème. Cette fonction $\rk$ s'appelle la \defin[rang]{fonction rang} sur $G$, on dit que $\rk(x)$ est le rang (ou rang bien-fondé) d'un sommet $x$. (Voir aussi \ref{ordinal-valued-rank-and-grundy-function} pour une généralisation.) \end{defn} \thingy Autrement dit, un sommet de rang $0$ est un puits, un sommet de rang $1$ est un sommet non-puits dont tous les voisins sortants sont terminaux, un sommet de rang $2$ est un sommet dont tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de rang exactement $1$, et ainsi de suite. Il revient au même de définir le rang de la manière suivante : le rang $\rk(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus grande longueur possible d'un chemin orienté partant de $x$, c'est-à-dire, le plus grand $n$ tel qu'il existe une suite $x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le sommet $x_{i+1}$ soit atteint par une arête de source $x_i$. Voici un autre exemple de définition par induction bien-fondée : \begin{defn}\label{definition-grundy-function} Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a qu'un nombre fini de voisins sortants. En utilisant le théorème \ref{well-founded-definition}, on définit alors une fonction $\gr\colon G \to \mathbb{N}$ par $\gr(x) = \mex\{\gr(y) : y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S := \mathbb{N}\setminus S$ pour le plus petit entier naturel \emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle $\gr$ la fonction telle que $\gr(x) = \Phi(x, \gr|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le théorème. Cette fonction $\gr$ s'appelle la \defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gr(x)$ est la valeur de Grundy d'un sommet $x$. (Voir aussi \ref{ordinal-valued-rank-and-grundy-function} pour une généralisation.) \end{defn} \thingy En particulier, un sommet de valeur de Grundy $0$ est un sommet qui n'a que des sommets de valeur de Grundy $>0$ 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 : cf. \ref{ordinal-valued-rank-and-grundy-function}). 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 \{\mathtt{P},\mathtt{N}\}$ on définit $\Phi(x, g)$ comme valant $\mathtt{N}$ si $g$ prend la valeur $\mathtt{P}$ et $\mathtt{N}$ si $g$ vaut constamment $\mathtt{P}$ (y compris si $g$ est la fonction vide), 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) = \mathtt{P}\}$. Les éléments de $P$ (i.e., les $x$ tels que $f(x) = \mathtt{P}$) seront appelés les \defin[P-sommet]{P-sommets} (ou P-positions) de $G$, tandis que les éléments du complémentaire $G\setminus P$ (i.e., les $x$ tels que $f(x) = \mathtt{N}$) seront appelés \defin[N-sommet]{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} \thingy\label{discussion-n-and-p-vertices} Dans un jeu combinatoire comme exposé en \ref{introduction-graph-game} et/ou \ref{definition-impartial-combinatorial-game}, si le graphe est bien-fondé, les P-sommets sont les positions du jeu à partir desquelles le joueur Précédent (=second joueur) a une stratégie gagnante, tandis que les N-sommets sont celles à partir desquelles le joueur suivant (`N' comme « Next », =premier joueur) a une stratégie gagnante (consistant, justement, à jouer vers un P-sommet) : ceci résulte de \ref{strategies-forall-exists-lemma} ou \ref{strategies-forall-exists-reformulation} (ou encore de \ref{positional-strategies-forall-exists-lemma} dans le cadre plus général de la section \ref{subsection-positional-strategies-determinacy}). On peut donc résumer ainsi la stratégie gagnante « universelle » pour n'importe quel jeu combinatoire impartial à connaissance parfaite dont le graphe est bien-fondé : \emph{jouer vers un P-sommet}, après quoi l'adversaire sera obligé de jouer vers un N-sommet (si tant est qu'il peut jouer), et on pourra de nouveau jouer vers un P-sommet, et ainsi de suite (et comme le graphe est bien-fondé, le jeu termine forcément en temps fini, et celui qui a joué pour aller vers les P-sommets aura gagné puisqu'il peut toujours jouer). \thingy Pour illustrer la technique de démonstration par induction bien-fondée, montrons que si $\gr$ est la fonction de Grundy introduite en \ref{definition-grundy-function} et si $P$ est la partie introduite en \ref{definition-grundy-kernel}, alors on a $x \in P$ si et seulement si $\gr(x) = 0$, i.e., les P-sommets sont ceux pour lesquels la fonction de Grundy est nulle. Par induction bien-fondé (cf. \ref{scholion-well-founded-induction}), on peut supposer la propriété (« $x \in P$ si et seulement si $\gr(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du sommet $x$ où on cherche à la vérifier. Si $x \in P$, cela signifie par définition de $P$ que tous ses voisins sortants $y$ de $x$ sont dans $G \setminus P$, et d'après l'hypothèse d'induction cela signifie $\gr(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire $\mex\{\gr(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et seulement si $0 \not\in S$), ce qui signifie $\gr(x) = 0$. Toutes ces reformulations étaient des équivalences : on a bien montré que $x \in P$ équivaut à $\gr(x) = 0$, ce qui conclut l'induction. \thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant sur la notion d'ordinaux introduite dans la partie \ref{section-ordinals}, la fonction rang peut se généraliser à n'importe quel graphe bien-fondé (sans hypothèse de nombre fini de voisins sortants), à condition d'autoriser des valeurs ordinales quelconques : précisément, on définit $\rk(x) = \sup\{\rk(y)+1 : y\in\outnb(x)\}$ (avec cette fois $\sup\varnothing = 0$ pour garder $\rk(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rk(x)$ est le plus petit ordinal strictement supérieur à $\rk(y)$ pour tout $y\in\outnb(x)$. De même, la fonction de Grundy peut se généraliser à n'importe quel graphe bien-fondé en définissant $\gr(x) = \mex\{\gr(y) : y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal \emph{n'appartenant pas} à $S$ (voir \ref{definition-grundy-function-again} pour une écriture formelle de cette définition). Il reste vrai (avec la même démonstration) que $\gr(x)$ est nul si et seulement si $x$ est un P-sommet. On peut donc résumer ainsi la stratégie gagnante « universelle » pour n'importe quel jeu combinatoire impartial à connaissance parfaite dont le graphe est bien-fondé : \emph{jouer de façon à annuler la fonction de Grundy} (c'est-à-dire, jouer vers un P-sommet), après quoi l'adversaire sera obligé de jouer vers un sommet dont la valeur de Grundy est non-nulle, et on pourra de nouveau jouer vers zéro, et ainsi de suite (et comme le graphe est bien-fondé, le jeu termine forcément en temps fini, et celui qui a joué pour annuler la fonction de Grundy aura gagné puisqu'il peut toujours jouer). \thingy\label{well-founded-induction-algorithm} Lorsque $G$ est \emph{fini} et bien-fondé, i.e., est un graphe fini acyclique (cf. \ref{finite-graph-is-well-founded-iff-acyclic}), la fonction $f$ définie par le théorème \ref{well-founded-definition} peut se calculer algorithmiquement de la façon suivante (si tant est que $\Phi$ elle-même est calculable) : \begin{itemize} \item utiliser un algorithme de \defin{tri topologique} (en ayant inversé le sens des arêtes pour se ramener à la convention usuelle) pour trouver une numérotation des sommets de $G$ telle que pour toute arête $(x,y)$ de $G$ le sommet $y$ précède $x$ dans la numérotation ; \item parcourir tous les éléments $x\in G$ dans l'ordre de cette numérotation, et définir $f(x) = \Phi(x, f|_{\outnb(x)})$, qui aura toujours un sens car tous les éléments de $\outnb(x)$ auront été parcourus avant $x$. \end{itemize} Si le tri topologique a été effectué par parcours en largeur, il est compatible avec la fonction rang (et inversement, tout tri raffinant la fonction rang est un tri topologique et peut s'obtenir par parcours en largeur). La notion de rang ordinal (cf. \ref{ordinal-valued-rank-and-grundy-function}) est donc une forme de généralisation transfinie du tri topologique. Un algorithme évitant le tri topologique, au prix d'une plus grande complexité, mais ayant le bénéfice de fonctionner dans une situation plus générale (graphes non nécessairement bien-fondés/acycliques), sera exposé dans la section suivante (cf. \ref{non-well-founded-induction-algorithm}). \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 \defin{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 \defin[partielle (fonction)]{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 \defin[définition (ensemble de)]{ensemble de définition} de la partie). Si $f,g\colon A \dasharrow Z$ sont deux fonctions partielles, on dit que $f$ \defin{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 \defin[cohérente (fonction)]{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}\label{fixed-point-lemma-for-partial-functions} 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} \thingy\label{non-well-founded-induction-algorithm} Lorsque $G$ est \emph{fini}, la fonction $f$ définie par le théorème \ref{non-well-founded-definition} (et \textit{a fortiori} par le théorème \ref{well-founded-definition}) peut se calculer algorithmiquement de la façon suivante : \begin{itemize} \item initialement, poser $f(x) = \mathtt{undefined}$ pour tout $x\in G$ ; \item parcourir tous les éléments $x\in G$ et, si $f(y)$ est défini pour suffisamment de voisins sortants $y$ de $x$ pour imposer $f(x)$, autrement dit, si $\Phi(x, f|_{\outnb(x)})$ est défini, alors définir $f(x)$ à cette valeur (noter qu'elle ne changera jamais ensuite du fait de la cohérence de $\Phi$) ; et \item répéter l'opération précédente jusqu'à ce que $f$ ne change plus. \end{itemize} La démonstration donnée avec les ordinaux correspond exactement à cet algorithme, à ceci près que « répéter l'opération » devra peut-être se faire de façon transfinie. \thingy Les différentes définitions par induction bien-fondée proposées en exemple dans la section \ref{subsection-well-founded-graphs}, c'est-à-dire la notion de rang bien-fondé (cf. \ref{definition-well-founded-rank}), de fonction de Grundy (cf. \ref{definition-grundy-function}) et de P-sommets et N-sommets (cf. \ref{definition-grundy-kernel}), et même la généralisation ordinale des deux premiers (cf. \ref{ordinal-valued-rank-and-grundy-function}), peuvent se généraliser à des graphes non nécessairement bien-fondés en utilisant le théorème \ref{non-well-founded-definition} : il faudra juste admettre que ce soient des fonctions \emph{partielles}, non définies sur certains sommets (voire, tous les sommets) qui ne sont pas dans la partie bien-fondée du graphe (cf. \ref{definition-wfpart}). Néanmoins, ces définitions ne présentent qu'un intérêt limité : le rang bien-fondé, par exemple, s'avère être défini exactement sur la partie bien-fondée de $G$ (vérification facile) et coïncider avec le rang bien-fondé sur ce sous-graphe, et pour ce qui est des P-sommets et N-sommets, on obtient exactement la fonction évoquée en \ref{p-d-n-vertices-of-perfect-information-games}. \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'\defin{écrasement transitif} ou \defin{é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'écrasement 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 \defin[extensionnel (graphe)]{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 ils ont les mêmes éléments} (\defin[extensionalité (axiome)]{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{Introduction aux ordinaux}\label{section-ordinals} \subsection{Présentation informelle} \thingy Les ordinaux sont une sorte de nombres, totalement ordonnés et même « bien-ordonnés », qui généralisent les entiers naturels en allant « au-delà de l'infini » : les entiers naturels $0,1,2,3,4,\ldots$ sont en particulier des ordinaux (ce sont les plus petits), mais il existe un ordinal qui vient après eux, à savoir $\omega$, qui est lui-même suivi de $\omega+1,\omega+2,\omega+3,\ldots$, après quoi vient $\omega\cdot 2$ (ou simplement $\omega 2$), et beaucoup d'autres choses. \begin{center} \begin{tikzpicture} \begin{scope}[line width=1.5pt,cap=round,join=round] % x = 10*(1-0.8^k*(1-0.2*(1-0.8^n))) % y = 2*0.8^k*0.8^n \draw (0.00000,2.00000) -- (0.00000,-2.00000); \draw (0.40000,1.60000) -- (0.40000,-1.60000); \draw (0.72000,1.28000) -- (0.72000,-1.28000); \draw (0.97600,1.02400) -- (0.97600,-1.02400); \draw (1.18080,0.81920) -- (1.18080,-0.81920); \draw (1.34464,0.65536) -- (1.34464,-0.65536); \draw (1.47571,0.52429) -- (1.47571,-0.52429); \draw (1.58057,0.41943) -- (1.58057,-0.41943); \draw (1.66446,0.33554) -- (1.66446,-0.33554); \draw (1.73156,0.26844) -- (1.73156,-0.26844); \draw[fill] (1.78525,0.21475) -- (1.78525,-0.21475) -- (2.00000,0.00000) -- (1.78525,0.21475); \draw (2.00000,1.60000) -- (2.00000,-1.60000); \draw (2.32000,1.28000) -- (2.32000,-1.28000); \draw (2.57600,1.02400) -- (2.57600,-1.02400); \draw (2.78080,0.81920) -- (2.78080,-0.81920); \draw (2.94464,0.65536) -- (2.94464,-0.65536); \draw (3.07571,0.52429) -- (3.07571,-0.52429); \draw (3.18057,0.41943) -- (3.18057,-0.41943); \draw (3.26446,0.33554) -- (3.26446,-0.33554); \draw (3.33156,0.26844) -- (3.33156,-0.26844); \draw (3.38525,0.21475) -- (3.38525,-0.21475); \draw[fill] (3.42820,0.17180) -- (3.42820,-0.17180) -- (3.60000,0.00000) -- (3.42820,0.17180); \draw (3.60000,1.28000) -- (3.60000,-1.28000); \draw (3.85600,1.02400) -- (3.85600,-1.02400); \draw (4.06080,0.81920) -- (4.06080,-0.81920); \draw (4.22464,0.65536) -- (4.22464,-0.65536); \draw (4.35571,0.52429) -- (4.35571,-0.52429); \draw (4.46057,0.41943) -- (4.46057,-0.41943); \draw (4.54446,0.33554) -- (4.54446,-0.33554); \draw (4.61156,0.26844) -- (4.61156,-0.26844); \draw (4.66525,0.21475) -- (4.66525,-0.21475); \draw (4.70820,0.17180) -- (4.70820,-0.17180); \draw[fill] (4.74256,0.13744) -- (4.74256,-0.13744) -- (4.88000,0.00000) -- (4.74256,0.13744); \draw (4.88000,1.02400) -- (4.88000,-1.02400); \draw (5.08480,0.81920) -- (5.08480,-0.81920); \draw (5.24864,0.65536) -- (5.24864,-0.65536); \draw (5.37971,0.52429) -- (5.37971,-0.52429); \draw (5.48457,0.41943) -- (5.48457,-0.41943); \draw (5.56846,0.33554) -- (5.56846,-0.33554); \draw (5.63556,0.26844) -- (5.63556,-0.26844); \draw (5.68925,0.21475) -- (5.68925,-0.21475); \draw (5.73220,0.17180) -- (5.73220,-0.17180); \draw (5.76656,0.13744) -- (5.76656,-0.13744); \draw[fill] (5.79405,0.10995) -- (5.79405,-0.10995) -- (5.90400,0.00000) -- (5.79405,0.10995); \draw (5.90400,0.81920) -- (5.90400,-0.81920); \draw (6.06784,0.65536) -- (6.06784,-0.65536); \draw (6.19891,0.52429) -- (6.19891,-0.52429); \draw (6.30377,0.41943) -- (6.30377,-0.41943); \draw (6.38766,0.33554) -- (6.38766,-0.33554); \draw (6.45476,0.26844) -- (6.45476,-0.26844); \draw (6.50845,0.21475) -- (6.50845,-0.21475); \draw (6.55140,0.17180) -- (6.55140,-0.17180); \draw (6.58576,0.13744) -- (6.58576,-0.13744); \draw (6.61325,0.10995) -- (6.61325,-0.10995); \draw[fill] (6.63524,0.08796) -- (6.63524,-0.08796) -- (6.72320,0.00000) -- (6.63524,0.08796); \draw (6.72320,0.65536) -- (6.72320,-0.65536); \draw (6.85427,0.52429) -- (6.85427,-0.52429); \draw (6.95913,0.41943) -- (6.95913,-0.41943); \draw (7.04302,0.33554) -- (7.04302,-0.33554); \draw (7.11012,0.26844) -- (7.11012,-0.26844); \draw[fill] (7.16381,0.21475) -- (7.16381,-0.21475) -- (7.37856,0.00000) -- (7.16381,0.21475); \draw (7.37856,0.52429) -- (7.37856,-0.52429); \draw (7.48342,0.41943) -- (7.48342,-0.41943); \draw (7.56730,0.33554) -- (7.56730,-0.33554); \draw (7.63441,0.26844) -- (7.63441,-0.26844); \draw (7.68810,0.21475) -- (7.68810,-0.21475); \draw[fill] (7.73105,0.17180) -- (7.73105,-0.17180) -- (7.90285,0.00000) -- (7.73105,0.17180); \draw (7.90285,0.41943) -- (7.90285,-0.41943); \draw (7.98673,0.33554) -- (7.98673,-0.33554); \draw (8.05384,0.26844) -- (8.05384,-0.26844); \draw (8.10753,0.21475) -- (8.10753,-0.21475); \draw (8.15048,0.17180) -- (8.15048,-0.17180); \draw[fill] (8.18484,0.13744) -- (8.18484,-0.13744) -- (8.32228,0.00000) -- (8.18484,0.13744); \draw (8.32228,0.33554) -- (8.32228,-0.33554); \draw (8.38939,0.26844) -- (8.38939,-0.26844); \draw (8.44307,0.21475) -- (8.44307,-0.21475); \draw[fill] (8.48602,0.17180) -- (8.48602,-0.17180) -- (8.65782,0.00000) -- (8.48602,0.17180); \draw (8.65782,0.26844) -- (8.65782,-0.26844); \draw (8.71151,0.21475) -- (8.71151,-0.21475); \draw (8.75446,0.17180) -- (8.75446,-0.17180); \draw[fill] (8.78882,0.13744) -- (8.78882,-0.13744) -- (8.92626,0.00000) -- (8.78882,0.13744); \draw (8.92626,0.21475) -- (8.92626,-0.21475); \draw (8.96921,0.17180) -- (8.96921,-0.17180); \draw (9.00357,0.13744) -- (9.00357,-0.13744); \draw[fill] (9.03106,0.10995) -- (9.03106,-0.10995) -- (9.14101,0.00000) -- (9.03106,0.10995); \draw (9.14101,0.17180) -- (9.14101,-0.17180); \draw (9.17537,0.13744) -- (9.17537,-0.13744); \draw[fill] (9.20285,0.10995) -- (9.22484,-0.08796) -- (9.31281,0.00000) -- (9.20285,0.10995); \draw[fill] (9.31281,0.13744) -- (9.31281,-0.13744) -- (9.45024,0.00000) -- (9.31281,0.13744); \draw[fill] (9.45024,0.10995) -- (9.45024,-0.10995) -- (9.56020,0.00000) -- (9.45024,0.10995); \draw[fill] (9.56020,0.08796) -- (9.56020,-0.08796) -- (9.64816,0.00000) -- (9.56020,0.08796); \draw[fill] (9.64816,0.07037) -- (9.64816,-0.07037) -- (9.71853,0.00000) -- (9.64816,0.07037); \draw[fill] (9.71853,0.05629) -- (9.71853,-0.05629) -- (9.77482,0.00000) -- (9.71853,0.05629); \draw[fill] (9.77482,0.04504) -- (9.77482,-0.04504) -- (9.81986,0.00000) -- (9.77482,0.04504); \draw[fill] (9.81986,0.03603) -- (9.81986,-0.03603) -- (9.85588,0.00000) -- (9.81986,0.03603); \draw[fill] (9.85588,0.02882) -- (9.85588,-0.02882) -- (9.88471,0.00000) -- (9.85588,0.02882); \draw[fill] (9.88471,0.02306) -- (9.88471,-0.02306) -- (10.00000,0.00000) -- (9.88471,0.02306); \end{scope} \node[anchor=north] at (0.00000,-2.00000) {$0$}; \node[anchor=north] at (0.40000,-1.60000) {$1$}; \node[anchor=north] at (0.72000,-1.28000) {$2$}; \node[anchor=north] at (0.97600,-1.02400) {$3$}; \node[anchor=north] at (2.00000,-1.60000) {$\omega$}; \node[anchor=north] at (2.32000,-1.28000) {$\scriptscriptstyle \omega+1$}; \node[anchor=north] at (3.60000,-1.28000) {$\omega2$}; \node[anchor=north] at (4.88000,-1.02400) {$\omega3$}; \end{tikzpicture} \\{\footnotesize (Une rangée de $\omega^2$ allumettes.)} \end{center} \thingy Les ordinaux servent à mesurer la taille des ensembles bien-ordonnés (c'est-à-dire, les ensembles totalement ordonnés dans lesquels il n'existe pas de suite infinie strictement décroissante) exactement comme les entiers naturels servent à mesurer la taille des ensembles finis. \thingy On pourra ajouter les ordinaux, et les multiplier, et même élever un ordinal à la puissance d'un autre, mais il n'y aura pas de soustraction ($\omega-1$ n'a pas de sens, en tout cas pas en tant qu'ordinal, parce que $\omega$ est le plus petit ordinal infini). Les ordinaux ont de nombreux points en commun avec les entiers naturels (l'addition est associative, la multiplication aussi, on peut les écrire en binaire, etc.), mais aussi des différences importantes (l'addition n'est pas commutative : on a $1+\omega = \omega$ mais $\omega+1 > \omega$). \thingy Comme la récurrence pour les entiers naturels, il y a sur les ordinaux (ou de façon équivalente, sur les ensembles bien-ordonnés) un principe d'\emph{induction transfinie} (cf. \ref{scholion-transfinite-induction}), qui est en fait l'application directe à eux du principe d'induction bien-fondée : son énoncé est essentiellement le même que le principe parfois appelé de « récurrence forte » pour les entiers naturels, c'est-à-dire que : \begin{center} Pour montrer une propriété sur tous les ordinaux $\alpha$ on peut faire l'hypothèse d'induction qu'elle est déjà connue pour les ordinaux $<\alpha$ au moment de la montrer pour $\alpha$. \end{center} Comme la récurrence sur les entiers naturels, et comme l'induction bien-fondée dont c'est un cas particulier, l'induction transfinie permet soit de \emph{démontrer} des propriétés sur les ordinaux, soit de \emph{définir} des fonctions sur ceux-ci : \begin{center} Pour définir une fonction sur tous les ordinaux $\alpha$ on peut faire l'hypothèse d'induction qu'elle est déjà définie pour les ordinaux $<\alpha$ au moment de la définir pour $\alpha$. \end{center} \thingy\label{decreasing-sequences-of-ordinals-terminate} Ce qui importe surtout pour la théorie des jeux est le fait suivant : \begin{center} \emph{toute suite strictement décroissante d'ordinaux est finie} \end{center} (généralisation du fait que toute suite strictement d'entiers naturels est finie). À cause de ça, les ordinaux peuvent servir à « mesurer » toutes sortes de processus qui terminent à coup sûr en temps fini, ou à généraliser les entiers naturels pour toutes sortes de processus qui terminent à coup sûr en temps fini mais pas en un nombre d'étapes borné \textit{a priori}. Par exemple, on peut imaginer que le dessin de la figure ci-dessus (figurant les ordinaux $<\omega^2$) représente une rangée d'allumettes qu'on pourrait utiliser dans un jeu de nim (cf. \ref{introduction-nim-game}) : si on convient que les allumettes doivent être effacées \emph{par la droite}, ce qui revient à diminuer strictement l'ordinal qui les compte (initalement $\omega^2$), la ligne sera toujours vidée en temps fini même si les joueurs essaient de la faire durer le plus longtemps possible (le premier coup va faire tomber l'ordinal $\omega^2$ à $\omega\cdot k + n$ avec $k,n\in\mathbb{N}$, après quoi les coups suivants l'amèneront au plus à $\omega\cdot k + n'$ avec $n'$ (i.e., on fait pointer une arête orientée de chaque ordinal $\beta$ vers chaque ordinal strictement plus petit), est bien-fondé, ou de façon équivalente, bien-ordonné. \thingy\label{ordinal-counting-genies-story} Voici une façon imagée d'y penser qui peut servir à faire le lien avec la théorie des jeux : imaginons un génie qui exauce des vœux en nombre limité (les vœux eux-mêmes sont aussi limités et ne permettent certainement pas de faire le vœu d'avoir plus de vœux — peut-être qu'on ne peut que souhaiter un paquet de carambars, ou de transformer son ennemi en crapaud, ou d'annuler une transformation en crapaud qu'on aurait soi-même subie, ou des choses de ce genre). Si le génie est prêt à exaucer $3$ vœux, on peut imaginer qu'à la fin de chaque vœu qu'on prononce on doive dire « maintenant, il me reste $n$ vœux » avec $n$ strictement inférieur à la valeur antérieure (initialement $3$). Cette définition se généralise aux ordinaux : un génie qui exauce $\alpha$ vœux est un génie qui demande qu'on formule un vœu et qu'on choisisse un ordinal $\beta < \alpha$, après quoi le vœu est exaucé et le génie se transforme en un génie qui exauce $\beta$ vœux. Ainsi, pour un génie qui exauce $\omega$ vœux on devra, lors du tout premier vœu qu'on formule, décider quel nombre de vœux il reste, ce nombre étant un \emph{entier naturel}, aussi grand qu'on le souhaite — mais fini. Cela peut sembler sans importance (si on a de toute façon autant de vœux que l'on souhaite, même $N = 10^{1000}$, peu importe qu'on doive choisir un nombre dès le début). Mais comparons avec un génie qui exauce $\omega+1$ vœux : pour celui-ci, lors du premier vœu que l'on formule, on pourra décider qu'il reste $\omega$ vœux et c'est au vœu suivant qu'on devra redescendre à un entier naturel (et le choisir). La différence entre avoir $\omega$ et $\omega+1$ vœux apparaîtra si on imagine un combat entre Aladdin et Jafar où Jafar utilise des vœux pour transformer Aladdin en crapaud et Aladdin pour redevenir humain : si Jafar a initialement $\omega$ vœux et Aladdin aussi, Jafar transforme Aladdin en crapaud et choisit qu'il lui reste $N$ vœux avec $N$ fini, alors Aladdin redevient humain choisit qu'il lui reste aussi au moins $N$ vœux, et au final il est sauf ; alors que si Jafar a initialement $\omega+1$ vœux et Aladdin seulement $\omega$, Jafar transforme Aladdin en crapaud et tombe à $\omega$, puis Aladdin est obligé de choisir un $N$ fini en formulant le vœu de redevenir humain, et Jafar peut choisir au moins $N$ vœux et gagne le combat (ainsi que quelques paquets de carambars). \thingy\label{introduction-von-neumann-ordinals} La construction moderne des ordinaux, introduite par J. von Neumann en 1923, est mathématiquement très élégante mais peut-être d'autant plus difficile à comprendre qu'elle est subtile : \begin{center} \index{von Neumann (ordinal de)}\emph{un ordinal est l'ensemble des ordinaux strictement plus petits que lui} \end{center} — ainsi, l'entier $0$ est défini comme l'ensemble vide $\varnothing$ (puisqu'il n'y a pas d'ordinaux plus petits que lui), l'entier $1$ est défini comme l'ensemble $\{0\} = \{\varnothing\}$ ayant pour seul élément $0$ (puisque $0$ est le seul ordinal plus petit que $1$), l'entier $2$ est défini comme $\{0,1\} = \{\varnothing,\{\varnothing\}\}$, l'entier $3$ comme $\{0,1,2\} = \{\varnothing,\{\varnothing\}, \penalty0 \{\varnothing,\{\varnothing\}\}\}$, et ainsi de suite, et l'ordinal $\omega$ est défini comme l'ensemble $\mathbb{N} = \{0,1,2,3,\ldots\}$ de tous les entiers naturels, puis $\omega+1$ comme l'ensemble $\omega \cup \{\omega\}$ des entiers naturels auquel on a ajouté le seul élément $\omega$, et plus généralement $\alpha+1 = \alpha \cup \{\alpha\}$. Formellement, un ordinal est l'écrasement transitif (cf. \ref{definition-transitive-collapse}) d'un ensemble bien-ordonné (i.e., totalement ordonné bien-fondé). Cette définition a certains avantages, par exemple la borne supérieure d'un ensemble $S$ d'ordinaux est simplement la réunion $\bigcup_{\alpha\in S} \alpha$ de(s éléments de) $S$. Néanmoins, elle n'est pas vraiment nécessaire à la théorie des ordinaux, et nous tâcherons d'éviter d'en dépendre. Mais il faut au moins retenir une idée : \thingy Pour tout ensemble $S$ d'ordinaux, il existe un ordinal qui est plus grand que tous les éléments de $S$ ; il existe même un \emph{plus petit} ordinal plus grand que tous les éléments de $S$, c'est-à-dire, une \emph{borne supérieure} de $S$. Ce fait est la clé de l'inexhaustibilité des ordinaux : quelle que soit la manière dont on essaie de rassembler des ordinaux en un ensemble, on peut trouver un ordinal strictement plus grand qu'eux (en particulier, les ordinaux ne forment pas un ensemble, pour un peu la même raison que l'ensemble de tous les ensembles n'existe pas : il est « trop gros » pour tenir dans un ensemble). Pour dire les choses différemment avec un slogan peut-être un peu approximatif : \begin{center} À chaque fois qu'on a construit les ordinaux jusqu'à un certain point, on crée un nouvel ordinal qui vient juste après tous ceux-là. \end{center} \thingy Pour aider à comprendre comment les choses commencent, et en partant de l'idée générale que \begin{center} \emph{comprendre un ordinal, c'est comprendre tous les ordinaux strictement plus petits que lui, et comment ils s'ordonnent} \end{center} voici comment s'arrangent les plus petits ordinaux. Après les entiers naturels $0,1,2,3,\ldots$ vient l'ordinal $\omega$ puis $\omega+1,\omega+2,\omega+3$ et ainsi de suite, après quoi viennent $\omega 2, \omega 2+1, \omega 2+2,\ldots$ qui sont suivis de $\omega 3$ et le même mécanisme recommence. Les ordinaux $\omega k + n$ pour $k,n\in\mathbb{N}$ sont ordonnés par l'ordre lexicographique donnant plus de poids à $k$ : l'ordinal qui vient immédiatement après (c'est-à-dire, leur ensemble, si on utilise la construction de von Neumann) est $\omega\cdot\omega = \omega^2$, qui est suivi de $\omega^2+1,\omega^2+2,\ldots$ et plus généralement des $\omega^2 + \omega k + n$, qui sont eux-mêmes suivis de $\omega^2 \cdot 2$. Les $\omega^2 \cdot n_2 + \omega \cdot n_1 + n_0$ sont ordonnés par l'ordre lexicographique donnant plus de poids à $n_2$, puis à $n_1$ puis à $n_0$. L'ordinal qui vient immédiatement après tous ceux-ci est $\omega^3$. En itérant ce procédé, on fabrique de même $\omega^4$, puis $\omega^5$ et ainsi de suite : les $\omega^r \cdot n_r + \cdots + \omega \cdot n_1 + n_0$ (c'est-à-dire en quelque sorte des polynômes en $\omega$ à coefficients dans $\mathbb{N}$) sont triés par ordre lexicographique en donnant plus de poids aux coefficients $n_i$ pour $i$ grand (et en identifiant bien sûr un cas où $n_r = 0$ par celui où il est omis : il s'agit de l'ordre lexicographique sur les suites d'entiers nulles à partir d'un certain rang). L'ordinal qui vient immédiatement après est $\omega^\omega$, puis on a tous les $\omega^\omega + \omega^r \cdot n_r + \cdots + \omega \cdot n_1 + n_0$ jusqu'à $\omega^\omega \cdot 2$, et de même $\omega^\omega \cdot 3$, etc., jusqu'à $\omega^\omega \cdot \omega = \omega^{\omega+1}$. En répétant $\omega$ fois toute cette séquence, on obtient $\omega^{\omega+2}$, puis de nouveau $\omega^{\omega+3}$ et ainsi de suite : après quoi vient $\omega^{\omega 2}$, et on voit comment on peut continuer de la sorte. \thingy Plus généralement, tout ordinal va s'écrire de façon unique sous la forme $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où $\gamma_s > \cdots > \gamma_1$ sont des ordinaux et $n_s,\ldots,n_1$ sont des entiers naturels non nuls (si un $n_i$ est nul il convient de l'omettre) : il s'agit d'une sorte d'écriture en « base $\omega$ » de l'ordinal, appelée \defin[Cantor (forme normale de)]{forme normale de Cantor}. On compare deux formes normales de Cantor en comparant le terme dominant (le plus à gauche, i.e., $\omega^{\gamma_s} n_s$ dans les notations qui viennent d'être données, ce qui se fait lui-même en comparant les $\gamma_s$ et sinon, les $n_s$), et s'ils sont égaux, en comparant le suivant et ainsi de suite. La forme normale de Cantor ne permet cependant pas de « comprendre » tous les ordinaux, car il existe des ordinaux tels que $\varepsilon = \omega^\varepsilon$. Le plus petit d'entre eux est noté $\varepsilon_0$ et est la limite de $\omega,\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$ \thingy On retiendra qu'il existe trois sortes d'ordinaux, cette distinction étant souvent utile dans les inductions : \begin{itemize} \item l'ordinal nul $0$, qui est souvent un cas spécial, \item les ordinaux « successeurs », c'est-à-dire ceux qui sont de la forme $\beta+1$ pour $\beta$ un ordinal plus petit (de façon équivalente, il y a un plus grand ordinal strictement plus petit), \item les ordinaux qui sont la borne supérieure (ou « limite ») des ordinaux strictement plus petits et qu'on appelle, pour cette raison, « ordinaux limites » (autrement dit, $\delta$ est limite lorsque pour tout $\beta<\delta$ il existe $\beta'$ avec $\beta<\beta'<\delta$). \end{itemize} À titre d'exemple, l'ordinal $0$, l'ordinal $42$ et l'ordinal $\omega$ sont des exemples de ces trois cas. D'autres ordinaux limites sont $\omega\cdot 2$, ou $\omega^2$, ou encore $\omega^\omega + \omega^3\cdot 7$, ou bien $\omega^{\omega+1}$ ; en revanche, $\omega^\omega + 1$ ou $\omega^{\omega 2} + 1729$ sont successeurs. Dans la forme normale de Cantor, un ordinal est successeur si et seulement si le dernier terme (le plus à droite) est un entier naturel non nul. \thingy\label{introduction-nimbers-and-numbers} Les ordinaux vont servir à définir différents jeux qui, pris isolément, sont extrêmement peu intéressants, mais qui ont la vertu de permettre de « mesurer » d'autres jeux : ces jeux ont en commun que, partant d'un ordinal $\alpha$, l'un ou l'autre joueur, ou les deux, ont la possibilité de le faire décroître (strictement), c'est-à-dire de le remplacer par un ordinal $\beta < \alpha$ strictement plus petit — comme expliqué en \ref{decreasing-sequences-of-ordinals-terminate}, ce processus termine forcément. Dans le cadre esquissé en \ref{introduction-graph-game}, on a trois jeux associés à un ordinal $\alpha$ : \begin{itemize} \item Un jeu \emph{impartial}, c'est-à-dire que les deux joueurs ont les mêmes options à partir de n'importe quelle position $\beta \leq \alpha$, à savoir, les ordinaux $\beta' < \beta$ — autrement dit, les deux joueurs peuvent décroître l'ordinal. Dans le cadre de \ref{introduction-graph-game}, le graphe a pour sommets les ordinaux $\beta \leq \alpha$ avec une arête (« verte », i.e., utilisable par tout le monde) reliant $\beta$ à $\beta'$ lorsque $\beta'<\beta$. Il s'agit du jeu de nim (cf. \ref{introduction-nim-game}) avec une seule ligne d'allumettes ayant initialement $\alpha$ allumettes. Ce jeu s'appelle parfois le \index{nimbre}« nimbre » associé à l'ordinal $\alpha$. \item Deux jeux \emph{partiaux} (=partisans), où un joueur n'a aucun coup possible (il a donc immédiatement perdu si c'est à son tour de jouer, ce qui rend le jeu, pris isolément, encore plus inintéressant que le précédent) : un jeu « bleu » ou « positif », dans lequel seul le joueur « bleu » (également appelé « gauche », « Blaise »...) peut jouer, exactement comme dans le jeu impartial ci-dessus, tandis que l'autre joueur ne peut rien faire, et un jeu « rouge » ou « négatif », dans lequel seul le joueur « rouge » (également appelé « droite », « Roxane »...) peut jouer tandis que l'autre ne peut rien faire. Dans le cadre de \ref{introduction-graph-game}, le graphe a pour sommets les ordinaux $\beta \leq \alpha$ avec une arête reliant $\beta$ à $\beta'$ lorsque $\beta'<\beta$, ces arêtes étant toutes bleues ou toutes rouges selon le jeu considéré. Il s'agit d'un jeu qui correspond à un certain avantage du joueur bleu, respectivement rouge, à rapprocher de l'histoire \ref{ordinal-counting-genies-story} ci-dessus. Le jeu bleu est parfois appelé le « nombre surréel » associé à l'ordinal $\alpha$, tandis que le rouge est l'opposé du bleu. \end{itemize} \subsection{Ensembles bien-ordonnés et induction transfinie} \thingy\label{definition-well-ordered-set} Un ensemble \defin[ordonné]{[partiellement] ordonné} est un ensemble muni d'une relation $>$ (d'ordre \emph{strict}) qui soit à la fois \begin{itemize} \item irréflexive ($x>x$ n'est jamais vrai quel que soit $x$), et \item transitive ($x>y$ et $y>z$ entraînent $x>z$). \end{itemize} Une telle relation est automatiquement antisymétrique ($x>y$ et $y>x$ ne sont jamais simultanément vrais pour $x\neq y$). On peut tout aussi bien définir un ensemble partiellement ordonné en utilisant l'ordre \emph{large} $\geq$ ($x\geq y$ étant défini par $x>y$ ou $x=y$, ou symétriquement $x>y$ étant défini par $x\geq y$ et $x\neq y$), réflexive, antisymétrique et transitive. On note bien sûr $x\leq y$ pour $y\geq x$ et $xx$. Un ensemble partiellement ordonné est dit \defin[totalement ordonné]{totalement ordonné} lorsque pour tous $x\neq y$ on a soit $x>y$ soit $y>x$. Un ensemble totalement ordonné bien-fondé $W$ est dit \defin{bien-ordonné}. D'après \ref{well-founded-induction}, ceci peut se reformuler de différentes façons : \begin{itemize} \item[(*)]$W$ est un ensemble totalement ordonné dans lequel il n'existe pas de suite infinie strictement décroissante. \item[(\dag)]$W$ est un ensemble (partiellement) ordonné dans lequel toute partie \emph{non vide} $N$ a un plus petit élément. \item[(\ddag)]$W$ est totalement ordonné, et si une partie $P\subseteq W$ vérifie la propriété suivante « si $x \in W$ est tel que tout élément strictement plus petit que $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ » (on pourra dire « $P$ est inductif »), alors $P = W$. \end{itemize} (Dans (\dag), « partiellement ordonné » suffit car si $\{x,y\}$ a un plus petit élément c'est bien qu'on a $xx$.) \begin{scho}[principe d'induction transfinie]\label{scholion-transfinite-induction} Pour montrer une propriété $P$ sur les éléments d'un ensemble bien-ordonné $W$, on peut supposer (comme « hypothèse d'induction »), lorsqu'il s'agit de montrer que $x$ a la propriété $P$, que cette propriété est déjà connue de tous les éléments strictement plus petits que $x$. \end{scho} \begin{prop}\label{downward-closed-subsets-of-well-ordered-sets} Soit $W$ un ensemble bien-ordonné et $S \subseteq W$ tel que $u < v$ avec $v \in S$ implique $u \in S$ (on peut dire que $S$ est « aval-clos »). Alors soit $S = W$ soit il existe $x\in W$ tel que $S = \precs(x) := \{y\in W : y w'$, resp. $w = w'$. \end{prop} \begin{proof} C'est évident : si $w < w'$ alors l'identité fournit une bijection croissante $W \to \precs_{W'}(w)$, et de même dans les autres cas. \end{proof} \begin{defn} Soient $W,W'$ deux ensembles bien-ordonnés. On notera $\#W < \#W'$, resp. $\#W > \#W'$, resp. $\#W = \#W'$, dans les trois cas du théorème \ref{comparison-of-well-ordered-sets}. Autrement dit, $\#W = \#W'$ signifie qu'il existe une bijection croissante $W \to W'$ (unique d'après \ref{uniqueness-of-isomorphisms-between-well-ordered-sets}), ce qui définit une relation d'équivalence entre ensembles bien-ordonnés, et on note $\#W < \#W'$ lorsque $\#W = \#\precs(y)$ pour un $y \in W'$, le théorème \ref{comparison-of-well-ordered-sets} assurant qu'il s'agit d'une relation d'ordre total entre les classes d'équivalence qu'on vient de définir. La classe d'équivalence\footnote{Pour être parfaitement rigoureux, on ne peut pas vraiment définir des classes d'équivalence de façon usuelle dans ce contexte, d'où l'intérêt de la définition suivante (ordinaux de von Neumann).} $\#W$ s'appelle l'\defin{ordinal} de $W$. Si on préfère éviter la définition par classe d'équivalence, on peut aussi définir $\#W$ comme l'écrasement transitif (cf. \ref{definition-transitive-collapse}) de $W$ (\defin[von Neumann (ordinal de)]{ordinal de von Neumann}), à savoir $\#W = \{\#\precs(x) : x\in W\}$ où $\#\precs(x) = \{\#\precs(y) : y\alpha$ ou $\beta=\alpha$), et il n'existe pas de suite infinie strictement décroissante d'ordinaux. Autrement dit : dans tout ensemble d'ordinaux il y en a un plus petit. \end{thm} \begin{proof} Le théorème \ref{comparison-of-well-ordered-sets} signifie exactement que les ordinaux sont \emph{totalement} ordonnés. Reste à expliquer qu'ils sont bien-ordonnés, c'est-à-dire, qu'il n'existe pas de suite infinie strictement décroissante $\alpha_0 > \alpha_1 > \alpha_2 > \cdots$. Mais si on avait une telle suite, en appelant $W$ un ensemble bien-ordonné tel que $\#W = \alpha_0$, chaque $\alpha_i$ suivant s'écrit $\#\precs(w_i)$ pour un $w_i \in W$, et d'après \ref{triviality-on-comparison-of-initial-segments-in-well-ordered-sets} on devrait avoir une suite strictement décroissante $w_1 > w_2 > \cdots$ dans $W$, ce qui contredit le fait que $W$ est bien-ordonné. La dernière affirmation vient de l'équivalence entre (*) et (\dag) dans \ref{definition-well-ordered-set}. \end{proof} \begin{prop}\label{sup-and-strict-sup-of-sets-of-ordinals} Tout ensemble $S$ d'ordinaux a une borne supérieure : autrement dit, il existe un ordinal $\sup S$ qui est le plus petit majorant (large) de $S$ (i.e., le plus petit ordinal $\alpha$ tel que $\beta\leq\alpha$ pour tout $\beta \in S$), et un ordinal $\sup^+ S$ qui est le plus petit majorant strict de $S$ (i.e., le plus petit ordinal $\alpha$ tel que $\beta<\alpha$ pour tout $\beta \in S$). (On verra plus loin que $\sup^+ S = \sup\{\beta+1 \colon \beta \in S\}$, donc cette notion n'est pas vraiment nouvelle.) \end{prop} \begin{proof} D'après ce qu'on vient de voir (dernière affirmation de \ref{sets-of-ordinals-are-well-ordered}), il suffit de montrer qu'il existe un majorant strict de $S$. Quitte à remplacer $S$ par sa réunion avec l'ensemble des ordinaux inférieurs à un ordinal quelconque de $S$ (pour les ordinaux de von Neumann, ceci revient à remplacer $S$ par $S \cup \bigcup_{\alpha\in S} \alpha$), on peut supposer que (*) si $\alpha \in S$ et $\beta < \alpha$ alors $\beta \in S$. On vient de voir que $S$ est bien-ordonné : si $\alpha = \#S$, montrons qu'il s'agit d'un majorant strict de $S$ ; or si $\beta \in S$, on a $\beta = \#\precs_S(\beta)$ d'après l'hypothèse (*) qu'on vient d'assurer, et la définition de l'ordre sur les ordinaux donne $\beta<\alpha$ : ainsi, $\alpha$ est bien un majorant strict comme voulu. \end{proof} \thingy Une conséquence de cette proposition est qu'il n'y a pas d'ensemble de tous les ordinaux (car si $S$ était un tel ensemble, il aurait un majorant strict, qui par définition ne peut pas appartenir à $S$) : c'est le \defin[Burali-Forti (paradoxe de)]{« paradoxe » de Burali-Forti} ; le mot « paradoxe » fait référence à une conception ancienne de la théorie des ensembles, mais selon les fondements modernes des mathématiques, ce phénomène n'a rien de paradoxal (intuitivement, il y a trop d'ordinaux pour pouvoir tenir dans un ensemble, de même qu'il n'y a pas d'ensemble de tous les ensembles). Ces subtilités ensemblistes ne poseront pas de problème dans la suite de ces notes, il faut juste reconnaître leur existence. \subsection{Ordinaux successeurs et limites} \thingy On appelle \defin[successeur (ordinal)]{successeur} d'un ordinal $\alpha$ le plus petit ordinal strictement supérieur à $\alpha$ (qui existe d'après la proposition \ref{sup-and-strict-sup-of-sets-of-ordinals} : si on veut, c'est $\sup^+\{\alpha\}$) : il est facile de voir que cet ordinal est fabriqué en ajoutant un unique élément à la fin d'un ensemble bien-ordonné d'ordinal $\alpha$ ; on le note $\alpha+1$, et on a $\beta \leq \alpha$ si et seulement si $\beta < \alpha+1$. Réciproquement, tout ordinal ayant un plus grand élément (i.e., l'ordinal d'un ensemble bien-ordonné ayant un plus grand élément) est un successeur : en effet, si $W$ a un plus grand élément $x$, alors $\#W$ est le successeur de $\#\precs(x)$. \thingy On distingue maintenant trois sortes d'ordinaux : \begin{itemize} \item l'ordinal \defin[nul (ordinal)]{nul} $0 = \#\varnothing$, mis à part de tous les autres, \item les ordinaux \defin[successeur (ordinal)]{successeurs}, c'est-à-dire ceux qui ont un plus grand élément (au sens expliqué ci-dessus), \item les autres, qu'on appelle ordinaux \defin[limite (ordinal)]{limites}. \end{itemize} La terminologie d'ordinaux « limites » s'explique ainsi : si $\delta$ est un ordinal non nul qui n'est pas successeur, cela signifie que pour chaque $\beta<\delta$ il existe $\beta'$ avec $\beta<\beta'<\delta$ (puisque $\beta$ n'est pas le plus grand élément de $\delta$). Ceci permet de dire que $\sup\{\beta < \alpha\} = \sup^+\{\beta < \alpha\}$ (de façon générale, on a $\sup^+\{\beta < \alpha\} = \alpha$ par définition), et on va définir la notion de limite ainsi : \thingy Si $\delta$ est un ordinal limite et $f$ est une fonction \emph{croissante} de $\delta$ (i.e., des ordinaux strictement plus petits que $\delta$) vers les ordinaux, on appelle \defin{limite} de $f$ en $\delta$ la valeur $\sup\{f(\xi) : \xi<\delta\}$. On pourra la noter $\lim_{\xi\to\delta} f(\xi)$ ou simplement $\lim_\delta f$. (Il s'agit bien d'une limite pour une certaine topologie : la topologie de l'ordre ; plus exactement, c'est une limite car pour tous $\beta_1 < \lim_\delta f < \beta_2$, il existe $\xi_0$ tel que $\beta_1 < f(\xi) < \beta_2$ si $\xi_0 \leq \xi < \delta$.) Ainsi, si $\delta$ est un ordinal limite, on peut écrire $\delta = \lim_{\xi\to\delta} \xi$ (et réciproquement, si $f$ est \emph{strictement} croissante, alors $\lim_{\xi\to\delta} f(\xi)$ est forcément un ordinal limite). À titre d'exemple, si $(u_n)$ est une suite croissante d'entiers naturels, sa limite en tant que fonction ordinale $\omega \to \omega$ est soit un entier naturel (lorsque la suite est bornée, donc constante à partir d'un certain rang) soit $\omega$ (lorsque la suite n'est pas bornée). Notamment, $\lim_{n\to\omega} 2^n = \omega$ (ce qui permettra de dire que $2^\omega = \omega$ quand on aura défini cet objet). \subsection{Somme, produit et exponentielle d'ordinaux} Les résultats de cette section seront admis (ils ne sont pas très difficiles à montrer — presque toujours par induction transfinie — mais seraient trop longs à traiter en détails). \thingy Il existe deux façons équivalentes de définir la somme $\alpha+\beta$ de deux ordinaux. La première façon consiste à prendre un ensemble bien-ordonné $W$ tel que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta = \#W'$, et définir $\alpha + \beta := \#W''$ où $W''$ est l'ensemble bien-ordonné qui est réunion disjointe de $W$ et $W'$ avec l'ordre qui place $W'$ \emph{après} $W$, c'est-à-dire formellement $W'' := \{(0,w) : w\in W\} \cup \{(1,w') : w'\in W'\}$ ordonné en posant $(i,w_1) < (i,w_2)$ ssi $w_1 < w_2$ et $(0,w) < (1,w')$ quels que soient $w\in W$ et $w' \in W'$ (il est facile de voir qu'il s'agit bien d'un bon ordre). Autrement dit, intuitivement, une rangée de $\alpha+\beta$ allumettes s'obtient en ajoutant $\beta$ allumettes \emph{après} (i.e., \emph{à droite d'})une rangée de $\alpha$ allumettes. La seconde façon consiste à définir $\alpha+\beta$ par induction transfinie sur $\beta$ (le \emph{second} terme) : \begin{itemize} \item $\alpha + 0 = \alpha$, \item $\alpha + (\beta+1) = (\alpha+\beta) + 1$ (cas successeur), \item $\alpha + \delta = \lim_{\xi\to\delta} (\alpha+\xi)$ si $\delta$ est limite. \end{itemize} Nous ne ferons pas la vérification du fait que ces définitions sont bien équivalentes, qui n'est cependant pas difficile (il s'agit de vérifier que la première définition vérifie bien les clauses inductives de la seconde). \thingy Quelques propriétés de l'addition des ordinaux sont les suivantes : \begin{itemize} \item l'addition est associative, c'est-à-dire que $(\alpha+\beta)+\gamma = \alpha+(\beta+\gamma)$ (on notera donc simplement $\alpha+\beta+\gamma$ et de même quand il y a plus de termes) ; \item l'ordinal nul est neutre à gauche comme à droite, c'est-à-dire que $0+\alpha = \alpha = \alpha+0$ ; \item le successeur de $\alpha$ est $\alpha + 1$ ; \item l'addition n'est pas commutative en général : par exemple, $1+\omega = \omega$ (en décalant d'un cran toutes les allumettes) alors que $\omega + 1 > \omega$ ; \item l'addition est croissante en chaque variable, et même strictement croissante en la seconde (si $\alpha\leq\alpha'$ alors $\alpha+\beta \leq \alpha'+\beta$, et si $\beta<\beta'$ alors $\alpha+\beta < \alpha+\beta'$ ; le fait que $0<1$ mais $0+\omega = 1+\omega$ explique qu'il n'y a pas croissante stricte en la première variable) ; \item lorsque $\alpha \leq \alpha'$, il existe un unique $\beta$ tel que $\alpha' = \alpha + \beta$ (certains auteurs le notent $-\alpha + \alpha'$ : on prendra garde au fait qu'il s'agit d'une soustraction \emph{à gauche}) ; \item comme conséquence de l'une des deux propriétés précédentes : si $\alpha + \beta = \alpha + \beta'$ alors $\beta = \beta'$ (simplification \emph{à gauche} des sommes ordinales). \end{itemize} \thingy On pourrait aussi définir des sommes de séries d'ordinaux, ces séries étant elles-mêmes indicées par d'autres ordinaux (le cas des séries ordinaires étant le cas où l'ensemble d'indices est $\omega$). Précisément, si $\alpha_\iota$ est un ordinal pour tout $\iota < \gamma$ (avec $\gamma$ un autre ordinal), on peut définir $\sum_{\iota<\gamma} \alpha_\iota$ par induction transfinie sur $\gamma$ : \begin{itemize} \item $\sum_{\iota<0} \alpha_\iota = 0$ (somme vide !), \item $\sum_{\iota<\gamma+1} \alpha_\iota = \big(\sum_{\iota<\gamma} \alpha_\iota\big) + \alpha_\gamma$ (cas successeur), \item $\sum_{\iota<\delta} \alpha_\iota = \lim_{\xi\to\delta} \sum_{\iota<\xi} \alpha_\iota$ (cas limite). \end{itemize} Ainsi, dans le cas d'une série indicée par les entiers naturels, $\sum_{n<\omega} \alpha_n$ est la limite $n\to\omega$ de la suite croissante d'ordinaux $\alpha_0 + \cdots + \alpha_{n-1}$ (limite qui existe toujours en tant qu'ordinal). Cette notion de somme peut servir à définir le produit, $\alpha\beta = \sum_{\iota<\beta} \alpha$, mais on va le redéfinir de façon plus simple : \thingy Il existe deux façons équivalentes de définir le produit $\alpha\cdot\beta$ (ou $\alpha\beta$) de deux ordinaux. La première façon consiste à prendre un ensemble bien-ordonné $W$ tel que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta = \#W'$, et définir $\alpha \cdot \beta := \#(W\times W')$ où $W \times W'$ est l'ensemble bien-ordonné qui est le produit cardésien de $W$ et $W'$ avec l'ordre lexicographique donnant plus de poids à $W'$, c'est-à-dire $(w_1,w_1') < (w_2,w_2')$ ssi $w_1' < w_2'$ ou bien $w_1' = w_2'$ et $w_1 < w_2$ (il est facile de voir qu'il s'agit bien d'un bon ordre). Autrement dit, intuitivement, une rangée de $\alpha\beta$ allumettes s'obtient en prenant une rangée de $\beta$ allumettes et en y \emph{remplaçant} chaque allumette par une rangée de $\alpha$ allumettes. La seconde façon consiste à définir $\alpha\beta$ par induction transfinie sur $\beta$ (le \emph{second} facteur) : \begin{itemize} \item $\alpha \cdot 0 = 0$, \item $\alpha \cdot (\beta+1) = (\alpha\cdot\beta) + \alpha$ (cas successeur), \item $\alpha \cdot \delta = \lim_{\xi\to\delta} (\alpha\cdot\xi)$ si $\delta$ est limite. \end{itemize} Nous ne ferons pas la vérification du fait que ces définitions sont bien équivalentes, qui n'est cependant pas difficile (il s'agit de vérifier que la première définition vérifie bien les clauses inductives de la seconde). \thingy Quelques propriétés de la multiplication des ordinaux sont les suivantes : \begin{itemize} \item la multiplication est associative, c'est-à-dire que $(\alpha\beta)\gamma = \alpha(\beta\gamma)$ (on notera donc simplement $\alpha\beta\gamma$ et de même quand il y a plus de facteurs) ; \item l'ordinal nul est absorbant à gauche comme à droite, c'est-à-dire que $0\cdot\alpha = 0 = \alpha\cdot0$ ; \item l'ordinal $1$ est neutre à gauche comme à droite, c'est-à-dire que $1\cdot\alpha = \alpha = \alpha\cdot1$ ; \item la multiplication est distributive \emph{à droite} sur l'addition, c'est-à-dire que $\alpha(\beta+\gamma) = \alpha\beta + \alpha\gamma$ (en particulier, $\alpha\cdot 2 = \alpha+\alpha$) ; \item la multiplication n'est pas commutative en général : par exemple, $2\cdot\omega = \omega$ (en doublant chaque allumette) alors que $\omega \cdot 2 > \omega$ ; \item la distributivité à gauche ne vaut pas en général : par exemple, $(1+1)\cdot\omega = 2\cdot\omega = \omega$ n'est pas égal à $\omega+\omega = \omega\cdot 2$ ; \item la multiplication est croissante en chaque variable, et même strictement croissante en la seconde lorsque la première est non nulle (si $\alpha\leq\alpha'$ alors $\alpha\cdot\beta \leq \alpha'\cdot\beta$, et si $\beta<\beta'$ et $\alpha>0$ alors $\alpha\cdot\beta < \alpha\cdot\beta'$) ; \item \defin{division euclidienne} : pour tout $\alpha$ (ici appelé dividende) et tout $\beta>0$ (ici appelé diviseur) il existe $\gamma$ (ici appelé quotient) et $\rho<\beta$ (ici appelé reste) uniques tels que $\alpha = \beta\gamma + \rho$ (on prendra garde au fait qu'il s'agit d'une division \emph{à gauche}) ; \item comme conséquence de l'une des deux propriétés précédentes : si $\beta\gamma = \beta\gamma'$ avec $\beta>0$, alors $\gamma = \gamma'$ (simplification \emph{à gauche} des produits ordinaux). \end{itemize} À titre d'exemple concernant la division euclidienne, tout ordinal $\alpha$ peut s'écrire de façon unique comme $\alpha = \omega\gamma + r$ avec $r$ un entier naturel : on a alors $r>0$ si et seulement si $r$ est successeur (les ordinaux limites sont donc exactement les $\omega\gamma$ avec $\gamma>0$). \thingy On pourrait aussi définir des produits d'ordinaux, ces produits étant eux-mêmes indicés par d'autres ordinaux (le cas des produits infinis ordinaires étant le cas où l'ensemble d'indices est $\omega$). Précisément, si $\alpha_\iota$ est un ordinal non nul pour tout $\iota < \gamma$ (avec $\gamma$ un autre ordinal), on peut définir $\prod_{\iota<\gamma} \alpha_\iota$ par induction transfinie sur $\gamma$ : \begin{itemize} \item $\prod_{\iota<0} \alpha_\iota = 1$ (produit vide !), \item $\prod_{\iota<\gamma+1} \alpha_\iota = \big(\prod_{\iota<\gamma} \alpha_\iota\big) \cdot \alpha_\gamma$ (cas successeur), \item $\prod_{\iota<\delta} \alpha_\iota = \lim_{\xi\to\delta} \prod_{\iota<\xi} \alpha_\iota$ (cas limite), \end{itemize} et on peut étendre au cas où certains ordinaux sont nuls en décrétant que, dans ce cas, le produit est nul (évidemment). Ainsi, dans le cas d'un produit d'ordinaux non nuls indicé par les entiers naturels, $\prod_{n<\omega} \alpha_n$ est la limite $n\to\omega$ de la suite croissante d'ordinaux $\alpha_0 \cdots \alpha_{n-1}$ (limite qui existe toujours en tant qu'ordinal). Cette notion de produit peut servir à définir le produit, $\alpha^\beta = \prod_{\iota<\beta} \alpha$, mais on va le redéfinir de façon plus simple : \thingy Il existe deux façons équivalentes de définir l'exponentielle $\alpha^\beta$ de deux ordinaux. La première façon consiste à prendre un ensemble bien-ordonné $W$ tel que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta = \#W'$, et définir $\alpha ^ \beta := \#(W^{(W')})$ où $W^{(W')}$ est l'ensemble des fonctions $W' \to W$ \emph{prenant presque partout la valeur $0$}, c'est-à-dire partout sauf en un nombre fini de points la plus petite valeur de $W$, cet ensemble étant muni de l'ordre lexicographique donnant plus de poids aux grandes composantes de la fonction, c'est-à-dire que $f < g$ lorsque le plus grand $w' \in W'$ tel que $f(w') \neq g(w')$ vérifie en fait $f(w') < g(w')$ (on peut vérifier qu'il s'agit bien d'un bon ordre). La seconde façon consiste à définir $\alpha^\beta$ par induction transfinie sur $\beta$ (l'exposant) : \begin{itemize} \item $\alpha ^ 0 = 1$, \item $\alpha ^ {\beta+1} = (\alpha^\beta) \cdot \alpha$ (cas successeur), \item $\alpha ^ \delta = \lim_{\xi\to\delta} \alpha^\xi$ si $\delta$ est limite. \end{itemize} Nous ne ferons pas la vérification du fait que ces définitions sont bien équivalentes, qui n'est cependant pas difficile (il s'agit de vérifier que la première définition vérifie bien les clauses inductives de la seconde). \thingy Quelques propriétés de l'exponentiation des ordinaux sont les suivantes : \begin{itemize} \item pour tout $\beta$, on a $1^\beta = 1$ ; \item pour tout $\beta>0$, on a $0^\beta = 0$ (en revanche, $0^0=1$) ; \item on a $\alpha^{\beta+\gamma} = \alpha^\beta \cdot \alpha^\gamma$ ; \item on a $\alpha^{\beta\gamma} = (\alpha^\beta)^\gamma$. \end{itemize} \thingy\label{base-tau-writing-of-ordinals} Soient $\alpha,\tau$ des ordinaux avec $\tau>1$ (dans la pratique, on ne s'intéressera guère qu'à $\tau = 2$ et $\tau = \omega$) : alors il existe une unique écriture \[ \alpha = \tau^{\gamma_s} \xi_s + \cdots + \tau^{\gamma_1} \xi_1 \] où $\gamma_s > \cdots > \gamma_1$ et $\xi_s,\ldots,\xi_1$ tous non nuls et strictement inférieurs à $\tau$, ou, ce qui revient au même (mais en changeant $\xi_i$ en $\xi_{(\gamma_i)}$), \[ \alpha = \cdots + \tau^\iota \xi_{(\iota)} + \cdots + \tau \xi_{(1)} + \xi_{(0)} \] où les $\xi_{(\iota)}$ sont tous nuls sauf un nombre fini (ce qui rend finie la somme ci-dessus) et tous $<\tau$. Deux telles expressions se comparent par l'ordre lexicographique donnant le plus de poids aux puissances élevées de $\tau$. On parle d'écriture de $\alpha$ \defin[écriture en base $\tau$]{en base $\tau$} : on dit que les $\xi_{(\iota)}$ sont les \emph{chiffres} de cette écriture. On souligne que les chiffres sont \emph{tous nuls sauf un nombre fini} (ce qui permet de les comparer lexicographiquement). Les deux cas les plus importants sont $\tau=2$ et $\tau=\omega$ : le cas $\tau=2$ correspond à l'\defin{écriture binaire} d'un ordinal, c'est-à-dire son écriture comme somme décroissante finie de puissances de $2$ distinctes, et le cas $\tau=\omega$ s'appelle écriture en \defin[Cantor (forme normale de)]{forme normale de Cantor}, c'est-à-dire comme somme décroissante finie de puissances de $\omega$. \thingy La forme normale de Cantor permet de comprendre, et de manipuler informatiquement, les ordinaux strictement inférieurs à l'ordinal appelé $\varepsilon_0$. On peut donner la définition suivante : un ordinal $<\varepsilon_0$ est \emph{soit} un entier naturel $n$ (qui pourra aussi s'écrire $\omega^0\cdot n$ si on le souhaite), qu'on compare comme on compare usuellement les entiers naturels, \emph{soit} une écriture de la forme $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où $\gamma_s > \cdots > \gamma_1$ sont eux-mêmes des ordinaux $<\varepsilon_0$ (précédemment définis), et les $n_i$ sont des entiers naturels non nuls, et de telles expressions se comparent par ordre lexicographique (i.e., comparer d'abord $\gamma_s$, ou, s'ils sont égaux, comparer les $n_s$, ou, s'ils sont égaux, comparer le terme suivant, etc.). À titre d'exemple, $\alpha := \omega^{\omega^{\omega 3}\cdot 7 + \omega^{\omega+5}\cdot 42}\cdot 1729 + \omega^{\omega^{\omega 2}\cdot 1000 + \omega + 33}\cdot 299\,792\,458$ est un ordinal $<\varepsilon_0$ (écrit en forme normale de Cantor) car le premier exposant, $\omega^{\omega 3}\cdot 7 + \omega^{\omega+5}\cdot 42$, est lui-même un ordinal $<\varepsilon_0$ écrit en forme normale de Cantor et supérieur au second exposant, $\omega^{\omega 2}\cdot 1000 + \omega + 33$. L'ordinal $\alpha$ est plus grand que $\beta := \omega^{\omega^{\omega 3}\cdot 7 + \omega^{\omega+4}\cdot 333}\cdot 2016 + \omega^{\omega^{\omega 3}\cdot 5 + \omega + 33}\cdot 299\,792\,458$ car (une fois qu'on a vérifié, de même, que $\beta$ est correctement écrit) le premier exposant de $\alpha$, à savoir $\omega^{\omega 3}\cdot 7 + \omega^{\omega+5}\cdot 42$, est supérieur au premier exposant de $\beta$, à savoir $\omega^{\omega 3}\cdot 7 + \omega^{\omega+4}\cdot 333$ (cette comparaison se fait elle-même en comparant le premier exposant, dans les deux cas $\omega\cdot 3$, puis son coefficient, dans les deux cas $7$, puis l'exposant suivant, et c'est là qu'on constate que $\omega+5$ dépasse $\omega+4$). \thingy Expliquons rapidement pourquoi la forme normale de Cantor permet de calculer la somme ou le produit de deux ordinaux. Pour l'addition, à part le fait qu'elle est associative, on a simplement besoin de savoir que : \begin{itemize} \item si $\gamma < \gamma'$ alors $\omega^\gamma\cdot n + \omega^{\gamma'}\cdot n' = \omega^{\gamma'} \cdot n'$ (autrement dit, les plus grandes puissances de $\omega$ absorbent les plus petites situées à leur gauche), \item et bien sûr, $\omega^\gamma\cdot n + \omega^\gamma \cdot n' = \omega^\gamma \cdot (n+n')$ par associativité à droite (on peut donc regrouper deux puissances égales). \end{itemize} À titre d'exemple, la somme de $\omega^{\omega 2}\cdot 2 + \omega^7\cdot 3$ et $\omega^{\omega 2}\cdot 5 + 12$ dans cet ordre vaut $\omega^{\omega 2}\cdot 7 + 12$, et dans l'autre sens elle vaut $\omega^{\omega 2}\cdot 7 + \omega^7\cdot 3$. Pour la multiplication, comme elle est distributive à droite et associative, il suffit de savoir calculer le produit de $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ (en forme normale de Cantor, avec les $\gamma_i$ strictement décroissants et les $n_i$ strictement positifs) par $\omega^{\gamma'}$ \emph{à droite}, et par $n' > 0$ (entier) lui aussi \emph{à droite}. Or on a : \begin{itemize} \item $(\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1) \times \omega^{\gamma'} = \omega^{(\gamma_s + \gamma')}$ dès que $\gamma'>0$, et \item $(\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1) \times n' = \omega^{\gamma_s} n_s n' + \cdots + \omega^{\gamma_1} n_1$ dès que $n'>0$ (i.e., seul le coefficient le plus à gauche est multiplié par $n'$, les autres sont inchangés). \end{itemize} À titre d'exemple, le produit de $\omega^{\omega 2}\cdot 2 + \omega^7\cdot 3$ et $\omega^{\omega 2}\cdot 5 + 12$ dans cet ordre vaut $\omega^{\omega 4}\cdot 5 + \omega^{\omega 2}\cdot 24 + \omega^7\cdot 3$, et dans l'autre sens il vaut $\omega^{\omega 4}\cdot 2 + \omega^{\omega 2 + 7}\cdot 3$. \thingy Puisque $\omega = 2^\omega$ (et par conséquent, $\omega^\gamma\, 2^c = 2^{\omega\gamma + c}$), l'écriture binaire d'un ordinal s'obtient en remplaçant chaque chiffre $n$ (un entier naturel) dans sa forme normale de Cantor par l'écriture binaire de $n$ (somme de $2^c$ pour des entiers naturels $c$ distincts). À titre d'exemple, \[ \begin{array}{rllll} &\omega^{\omega^2\cdot 3}\cdot 5 &\strut + \omega^{\omega+1}\cdot 8 &\strut + \omega^{17}\cdot 6 &\strut + 12\\ =& 2^{\omega^3\cdot 3 + 2} + 2^{\omega^3\cdot 3} &\strut + 2^{\omega^2+\omega+3} &\strut + 2^{\omega\cdot 17+2} + 2^{\omega\cdot 17+1} &\strut + 2^3 + 2^2 \end{array} \] % % % \section{Jeux combinatoires impartiaux à information parfaite}\label{section-combinatorial-impartial-games} \subsection{Récapitulations} \thingy On a introduit en \ref{introduction-graph-game} et plus formellement en \ref{definition-impartial-combinatorial-game} la notion de \emph{jeu combinatoire impartial} (à information parfaite) associé à un graphe $G$ muni d'un sommet initial $x_0$ (c'est le jeu où, partant de $x = x_0$, chacun des deux joueurs choisit à son tour un voisin sortant de $x$ : si l'un des joueurs ne peut pas jouer, il a perdu, tandis que si la confrontation se continue indéfiniment, elle est considérée comme nulle) ; on a vu en \ref{determinacy-of-perfect-information-games} que ces jeux sont déterminés. On fera dans toute cette partie l'hypothèse supplémentaire que le graphe $G$ est bien-fondé (cf. \ref{definitions-graphs}), c'est-à-dire qu'aucune confrontation ne peut être nulle (=durer indéfiniement) : il arrive forcément un point où l'un des joueurs ne peut plus jouer (et a donc perdu), et la détermination signifie qu'un des joueurs a une stratégie \emph{gagnante}. On peut qualifier un tel jeu de \index{bien-fondé (jeu)}« bien-fondé » ou de \defin[terminant (jeu)]{terminant}. \thingy\label{combinatorial-positions-as-games} Il va de soi qu'une position $x$ d'un jeu combinatoire impartial $G$ peut elle-même être considérée comme un jeu combinatoire impartial : le jeu joué \defin{à partir de là}, à savoir celui dont $x$ est la position initiale (on avait fait une remarque semblable pour les jeux de Gale-Stewart en \ref{gale-stewart-positions-as-games}) et dont l'ensemble des positions est $G$ ou, mieux (cf. paragraphe suivant) l'aval de $x$. On se permettra souvent d'identifier ainsi une position et un jeu. Pour éviter des discussions inutiles, on fera aussi souvent implicitement l'hypothèse, en parlant d'un jeu combinatoire impartial $(G,x_0)$, que tout sommet de $G$ est accessible depuis $x_0$ (cf. \ref{definition-accessibility-downstream} ; i.e., il n'y a pas de positions « inutiles » car inaccessibles) : on peut toujours se ramener à cette hypothèse en remplaçant $G$ par l'aval de $x_0$, c'est-à-dire, en supprimant les positions inaccessibles. On rappelle la définition de la fonction de Grundy (généralisant \ref{definition-grundy-function} à des valeurs non nécessairement finies, comme expliqué en \ref{ordinal-valued-rank-and-grundy-function}) : \begin{defn}\label{definition-grundy-function-again} Soit $G$ un graphe orienté bien-fondé. On appelle \defin[Grundy (fonction de)]{fonction de Grundy} sur $G$ la fonction $\gr$ définie sur $G$ et à valeurs ordinales définie inductivement (en utilisant le théorème \ref{well-founded-definition}) par $\gr(x) = \mex\{\gr(y) : y\in\outnb(x)\}$ (où $\mex S$ désigne le plus petit ordinal n'appartenant pas à $S$, qui existe d'après \ref{sets-of-ordinals-are-well-ordered} et \ref{sup-and-strict-sup-of-sets-of-ordinals}). On appelle fonction (ou valeur) de Grundy du jeu combinatoire impartial (terminant) associé à $(G,x_0)$ la valeur $\gr(x_0)$. \end{defn} On rappelle qu'on a vu (cf. \ref{discussion-n-and-p-vertices} à \ref{ordinal-valued-rank-and-grundy-function}) que le second joueur (=joueur précédent) a une stratégie gagnante si et seulement si la valeur de Grundy est $0$, tandis que le premier joueur (=joueur suivant) en a une si et seulement si elle est $\neq 0$. La stratégie « universelle » consiste toujours à \emph{jouer de façon à annuler la fonction de Grundy} du sommet vers lequel on joue. La signification de la valeur exacte de la fonction de Grundy (au-delà du fait qu'elle soit nulle ou non nulle) est plus mystérieuse. Pour l'éclaircir, on va introduire les \emph{nimbres} (déjà évoqués en \ref{introduction-nimbers-and-numbers}) : \begin{defn}\label{definition-nimber} Soit $\alpha$ un ordinal. On appelle alors \defin{nimbre} associé à $\alpha$, et on note $*\alpha$, le jeu combinatoire impartial dont \begin{itemize} \item l'ensemble des positions est l'ensemble des ordinaux $\beta \leq \alpha$ (c'est-à-dire, si on utilise la construction de von Neumann des ordinaux, cf. \ref{introduction-von-neumann-ordinals}, l'ensemble $\alpha+1$), \item la relation d'arête (définissant le graphe) est $>$, c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les ordinaux $\beta'<\alpha$, \item la position initiale est $\alpha$. \end{itemize} Autrement dit, il s'agit du jeu où, partant de l'ordinal $\beta = \alpha$, chaque joueur peut dimininuer l'ordinal $\beta$, c'est-à-dire le remplacer par un ordinal $\beta' < \beta$ de son choix (ce jeu termine en temps fini d'après \ref{decreasing-sequences-of-ordinals-terminate} ou \ref{sets-of-ordinals-are-well-ordered}). On dira aussi que $*\alpha$ est le jeu constituée d'« une rangée de $\alpha$ allumettes » au nim (si $\alpha$ est fini, cela coïncide bien avec ce qu'on a dit en \ref{introduction-nim-game}). En accord avec la remarque \ref{combinatorial-positions-as-games}, on peut identifier les positions du nimbre $*\alpha$ avec les jeux $*\beta$ pour $\beta\leq\alpha$. \end{defn} \begin{prop} La valeur de Grundy du nimbre $*\alpha$ est $\alpha$. \end{prop} \begin{proof} On procède par induction transfinie (cf. \ref{scholion-transfinite-induction}) : si on sait que $\gr(*\beta) = \beta$ pour tout $\beta<\alpha$, alors $\gr(*\alpha)$ est le plus petit ordinal différent de $\beta$ pour $\beta<\alpha$, c'est donc exactement $\alpha$. \end{proof} % % % \printindex % % % \end{document}