path: root/notes-mitro206.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{matrix}
%
\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}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\outnb}{\operatorname{outnb}}
\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\mex}{\operatorname{mex}}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
%
%
\begin{document}
\title{Théorie(s) des jeux\\(notes provisoires)}
\author{David A. Madore}
\maketitle

\centerline{\textbf{MITRO206}}


%
%
%

\section{Introduction et typologie}

\subsection{La notion de jeu mathématique : généralités}

\thingy Il n'est pas possible de donner une définition générale
précise de la notion de « jeu mathématique ».  On verra plus loin des
définitions précises de certains types de jeux (p. ex., les jeux
impartiaux à information parfaite), mais il n'existe pas de définition
générale utile qui s'applique à tous ces types, et à partir de
laquelle on pourrait développer une théorie intéressante.

Pire, différentes disciplines se sont développées sous le nom de
« théorie des jeux », chacune donnant une définition différente de ce
qu'est un « jeu ».  Par exemple, l'étude des jeux « en forme normale »
(=jeux définis par des matrices de gains), la théorie combinatoire des
jeux (jeux à information parfaite), la théorie des jeux logiques, la
théorie des jeux différentiels, etc.  Il n'existe donc pas une mais
plusieurs théories des jeux.

Ces différentes théories des jeux intersectent différentes branches
des mathématiques ou d'autres sciences : probabilités,
optimisation/contrôle, combinatoire, logique, calculabilité,
complexité, analyse/EDP ou encore (en-dehors ou en marge des
mathématiques), économie, cryptographie, physique quantique,
cybernétique, biologie, sociologie, linguistique, philosophie.

Il va de soi qu'on ne pourra dans ce cours donner qu'un aperçu de
quelques unes de ces théories des jeux.


\thingy Une tentative pour approcher la notion de jeu mathématique :
le jeu possède un \textbf{état}, qui évolue dans un ensemble (fini ou
infini) d'états possibles ; un certain nombre de \textbf{joueurs}
choisissent, simultanément ou consécutivement, un \textbf{coup} à
jouer parmi différentes \textbf{options}, en fonction de l'état
courant, ou peut-être seulement d'une fonction de l'état courant ; ce
coup peut éventuellement faire intervenir un aléa (hasard voulu par le
joueur) ; l'état du jeu évolue en fonction des coups des joueurs et
éventuellement d'un autre aléa (hasard intrinsèque au jeu) ; au bout
d'un certain nombre de coups (fini ou infini), la règle du jeu
attribue, en fonction de l'état final, ou de son évolution complète,
un \textbf{gain} à chaque joueur, ce gain pouvant être un réel (gain
numérique), l'étiquette « gagné » / « perdu », ou encore autre chose,
et chaque joueur cherche en priorité à maximiser son gain (i.e., à
gagner le plus possible, ou à gagner tout court), ou dans le cas
probabiliste, son espérance de gain.

Mais même cette définition très vague est incomplète !, par exemple
dans le cas des jeux différentiels, les coups n'ont pas lieu tour à
tour mais continûment.

Une \textbf{stratégie} d'un joueur est la fonction par laquelle il
choisit son coup à jouer en fonction de l'état du jeu (ou de la
fonction de l'état qui lui est présentée), et d'aléa éventuel.  On
peut ainsi résumer le jeu en : chaque joueur choisit une stratégie, et
la règle du jeu définit alors un gain pour chaque joueur.  Les
stratégies peuvent être contraintes de différentes manières (par
exemple : être calculables par une machine de Turing).  Une stratégie
est dite \textbf{gagnante} si le joueur qui l'utilise gagne le jeu
(supposé avoir une notion de « joueur gagnant ») quels que soient les
coups choisis par l'autre joueur.

Il faut aussi se poser la question de si les joueurs peuvent
communiquer entre eux (et si oui, s'ils peuvent prouver leur honnêteté
ou s'engager irrévocablement quant au coup qu'ils vont jouer, etc.).
Dans certains cas, on peut aussi être amené à supposer que les joueurs
ne connaissent pas toute la règle du jeu (voir « information
  complète » ci-dessous).


\subsection{Quelques types de jeux}

\thingy Le \textbf{nombre de joueurs} est généralement $2$.  On peut
néanmoins étudier des jeux multi-joueurs, ce qui pose des questions
d'alliances et compliquer la question des buts (un joueur peut être
incapable de gagner lui-même mais être en position de décider quel
autre joueur gagnera : on parle de « kingmaker »).  On peut aussi
étudier des jeux à un seul joueur (jouant contre le hasard), voire à
zéro joueurs (systèmes dynamiques), mais ceux-ci relèvent plutôt
d'autres domaines.  Dans ce cours, on s'intéressera (presque
uniquement) aux jeux à deux joueurs.

\thingy Les joueurs peuvent avoir \textbf{des intérêts communs,
  opposés, ou toute situation intermédiaire}.

Le cas d'intérêts communs est celui où tous les joueurs ont le même
gain.  Si les joueurs peuvent parfaitement communiquer, on est alors
essentiellement ramené à un jeu à un seul joueur : on s'intéresse donc
ici surtout aux situations où la communication est imparfaite.

Le cas de deux joueurs d'intérêts opposés est le plus courant : dans
le cas de gains numériques, on le modélise en faisant des gains d'un
joueur l'opposé des gains de l'autre — on parle alors de \textbf{jeu à
  somme nulle} ; ou bien la règle fera qu'un et un seul joueur aura
gagné et l'autre perdu (mais parfois, elle peut aussi admettre le
match nul).

Toute autre situation intermédiaire est possible.  Mais on conviendra
bien que le but de chaque joueur est de maximiser son propre gain,
sans considération des gains des autres joueurs.

\thingy Le jeu peut être \textbf{partial/partisan ou impartial}.  Un
jeu impartial est un jeu où tous les joueurs sont traités de façon
équivalente par la règle (le sens de « équivalent » étant à définir
plus précisément selon le type de jeu).

\thingy\label{intro-simultaneous-or-sequential} Les coups des joueurs
peuvent avoir lieu \textbf{simultanément ou séquentiellement}.

Formellement, il s'agit seulement d'une différence de présentation.
On peut toujours ramener des coups séquentiels à plusieurs coups
simultanés en n'offrant qu'une seule option à tous les joueurs sauf
l'un, et réciproquement, on peut ramener des coups simultanés à des
coups séquentiels en cachant à chaque joueur l'information de ce que
l'autre a joué.  La question \ref{question-preposing-moves} est
cependant plus intéressante.

\thingy Le jeu peut être à \textbf{information parfaite} ou non.  Un
jeu à information parfaite est un jeu dont la règle ne fait pas
intervenir le hasard et où chaque joueur joue séquentiellement en
ayant la connaissance complète de l'état du jeu et de tous les coups
effectués antérieurement par tous les autres joueurs.

(Cette notion est parfois distinguée de la notion plus faible
d'\textbf{information complète}, qui souligne que les joueurs ont
connaissance complète de la \emph{règle} du jeu, i.e., des gains
finaux et des options disponibles à chaque joueur.  Néanmoins, on peut
formellement ramener un jeu à information incomplète en jeu à
information complète en regroupant toute l'inconnue sur les règles du
jeu dans des coups d'un joueur appelé « la nature ».  Dans ce cours,
on ne considérera que des jeux à information complète [et toute
  occurrence des mots « information complète » sera probablement un
  lapsus pour « information parfaite »].)

\thingy Le nombre de positions, comme le nombre d'options dans une
position donnée, ou comme le nombre de coups, peut être \textbf{fini
  ou infini}.  Même si l'étude des jeux finis (de différentes
manières) est la plus intéressante pour des raisons pratiques, toutes
sortes de jeux infinis peuvent être considérés, par exemple en logique
(voir plus loin sur l'axiome de détermination).  Pour un jeu à durée
infinie, le gagnant pourra être déterminé, par exemple, par toute la
suite des coups effectués par les deux joueurs ; on peut même
introduire des coups après un nombre infini de coups, etc.

De même, l'ensemble des positions, des options ou des temps peut être
\textbf{discret ou continu}.  Dans ce cours, on s'intéressera presque
exclusivement au cas discret (on écartera, par exemple, la théorie des
jeux différentiels).


\subsection{Quelques exemples en vrac}

\thingy Le jeu de \textbf{pile ou face} entre Pauline et Florian.  On
tire une pièce non-truquée : si elle tombe sur pile, Pauline gagne, si
c'est face, c'est Florian.  Aucun des joueurs n'a de choix à faire.
Chacun a une probabilité $\frac{1}{2}$ de gagner, ou une espérance de
$0$ si les gains sont $+1$ au gagnant et $-1$ au perdant (il s'agit
donc d'un jeu à somme nulle).

Variante entre Alice et Bob : maintenant, Alice choisit « pile » ou
« face » avant qu'on (Bob) tire la pièce.  Si Alice a bien prévu, elle
gagne, sinon c'est Bob.  Ici, seule Alice a un choix à faire.
Néanmoins, il n'y a pas de stratégie intéressante : la stratégie
consistant à choisir « pile » offre la même espérance que celle
consistant à choisir « face », et il n'existe pas de stratégie
(c'est-à-dire, de stratégie mesurable par rapport à l'information dont
dispose Alice) offrant une meilleure espérance.

\thingy Variante : Alice choisit « pile » ou « face », l'écrit dans
une enveloppe scellée sans la montrer à Bob (elle s'\emph{engage} sur
son choix), et Bob, plutôt que tirer une pièce, choisit le côté qu'il
montre.  Si Alice a bien deviné le choix de Bob, Alice gagne, sinon
c'est Bob.  Variante : Bob choisit une carte dans un jeu de 52 cartes
sans la montrer à Bob, et Alice doit deviner si la carte est noire ou
rouge.

Variante équivalente : Alice choisit « Alice » ou « Bob » et Bob
choisit simultanément « gagne » ou « perd ».  Si la phrase obtenue en
combinant ces deux mots est « Alice gagne » ou « Bob perd », alors
Alice gagne, si c'est « Alice perd » ou « Bob gagne », alors Bob
gagne.  Encore une variante : Alice et Bob choisissent simultanément
un bit (élément de $\{0,1\}$), si le XOR de ces deux bits vaut $0$
alors Alice gagne, s'il vaut $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).

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 le film \textit{Princess Bride} à ce sujet.)

\thingy Le jeu de \textbf{pierre-papier-ciseaux} : Alice et Bob
choisissent simultanément un élément de l'ensemble
$\{\textrm{pierre},\penalty0 \textrm{papier},\penalty0
\textrm{ciseaux}\}$.  S'ils ont choisi le même élément, le jeu est
nul ; sinon, papier gagne sur pierre, ciseaux gagne sur papier et
pierre gagne sur ciseaux (l'intérêt étant qu'il s'agit d'un « ordre »
cyclique, totalement symétrique entre les options).  Il s'agit
toujours d'un jeu à somme nulle (disons que gagner vaut $+1$ et perdre
vaut $-1$), et cette fois les deux joueurs sont en position
complètement symétrique.  On verra que la meilleure stratégie possible
consiste à choisir chacune des options avec probabilité $\frac{1}{3}$
(ceci assure une espérance de gain nul quoi que fasse l'autre joueur).

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).

\thingy Le \textbf{jeu du partage} ou \textbf{de l'ultimatum} : Alice
et Bob ont $10$ points à se partager : Alice choisit un $k$ entre $0$
et $10$ entier (disons), la partie 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).  Un « équilibre de Nash » signifie que dans cette
situation, aucun des joueurs n'améliorerait son gain en changeant
unilatéralement le coup qu'il joue.

\thingy Le \textbf{dilemme du prisonnier} : Alice et Bob choisissent
simultanément une option parmi « coopérer » ou « faire défaut ».
\textcolor{red}{À finir.}

\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 Le \textbf{jeu topologique de Choquet} : soit $X$ un espace
métrique (ou topologique) fixé à l'avance.  Uriel et Vania choisissent
tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert
précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0
\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$,
puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de
suite.  Le jeu continue pendant un nombre infini de tours indicés par
les entiers naturels.  À la fin, on a bien sûr $\bigcap_{n=0}^{\infty}
U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si
cette intersection est vide, Vania le gagne si elle est non-vide.  On
peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vivien qui en
a une.

\thingy Le \textbf{jeu de Nim} : un certain nombre d'allumettes sont
arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
retirent des alumettes, au moins une à chaque fois, et autant qu'ils
veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui
retire la dernière allumette (de façon équivalente, le perdant est
celui qui ne peut pas jouer).  Il s'agit ici d'un jeu à deux joueurs
impartial à connaissance parfaite : on verra que la théorie de Grundy
permet de décrire exactement la stratégie gagnante (et pour qui).


\subsection{Remarques}

\thingy\label{question-preposing-moves} La question suivante mérite
l'attention : supposons que, dans un jeu, deux joueurs aient à jouer
deux coups successifs, disons que le joueur $A$ choisit une option $x$
parmi un certain ensemble $E$ (typiquement fini), \emph{puis} le
joueur $B$ choisit, en connaissant le $x$ choisi par $A$, une option
$y$ parmi un certain ensemble $F$ (typiquement fini).  Revient-il au
même de demander de choisir \emph{simultanément} pour $A$ un élément
de $E$ et pour $B$ un élément de l'ensemble $F^E$ des fonctions de $E$
dans $F$ ?  L'idée étant que $B$ choisit la fonction $\varphi$ qui,
selon le coup $x \in E$ joué par $A$, déterminera le coup $y :=
\varphi(x) \in F$ qu'il joue en réponse.  Au moins si $E$ est fini, on
peut imaginer que $B$ considère mentalement tous les coups que $A$
pourra jouer et choisit la réponse qu'il y apporterait, déterminant
ainsi la fonction $\varphi$ (si on préfère, $\varphi$ est une
stratégie locale pour le prochain coup de $B$).

En principe, les jeux ainsi considérés (le jeu initial, et celui où on
a demandé à $B$ d'anticiper son choix en le remplaçant par une
fonction du choix de $A$) devraient être équivalents.  En pratique, il
se peut qu'on les analyse différemment pour différentes raisons.

Notons que si on permet ou oblige $B$ à communiquer à $A$ la fonction
$\varphi$ qu'il a choisie, i.e., à s'\emph{engager} irrévocablement
sur le coup $y$ qu'il jouerait selon le coup $x$ de $A$, on peut
véritablement changer le jeu.


%
%
%

\section{Jeux en forme normale}

\subsection{Généralités}

\begin{defn}\label{definition-game-in-normal-form}
Un \textbf{jeu en forme normale} à $N$ joueurs est la donnée de $N$
ensembles finis $A_1,\ldots,A_N$ et de $N$ fonctions
$u_1,\ldots,u_N\colon A \to \mathbb{R}$ où $A := A_1 \times \cdots
\times A_N$.

Un élément de $A_i$ s'appelle une \textbf{option} ou \textbf{stratégie
  pure} pour le joueur $i$.  Un élément de $A := A_1 \times \cdots
\times A_N$ s'appelle un \textbf{profil de stratégies pures}.  La
valeur $u_i(a)$ de la fonction $u_i$ sur un $a\in A$ s'appelle le
\textbf{gain} du joueur $i$ selon le profil $a$.
\end{defn}

Le jeu doit se comprendre de la manière suivante : chaque joueur
choisit une option $a_i \in A_i$ indépendamment des autres, et chaque
joueur reçoit un gain égal à la valeur $u_i(a_1,\ldots,a_n)$ définie
par le profil $(a_1,\ldots,a_n)$ des choix effectués par tous les
joueurs.  Le but de chaque joueur est de maximiser son propre gain.

On utilisera le terme « option » ou « stratégie pure » selon qu'on
veut souligner que le joueur $i$ choisit effectivement $a_i$ ou décide
a priori de faire forcément ce choix-là.  Cette différence vient du
fait que les joueurs peuvent également jouer de façon probabiliste, ce
qui amène à introduire la notion de stratégie mixte :

\begin{defn}\label{definition-mixed-strategy-abst}
Donné un ensemble $B$ fini d'« options », on appelle \textbf{stratégie
  mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que
$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ :
autrement dit, il s'agit d'une distribution de probabilités sur $B$.

Le \textbf{support} de $s$ est l'ensemble des options $b\in B$ pour
lesquelles $s(b) > 0$.

Parfois, on préférera considérer la stratégie comme la combinaison
formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le
produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est
défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est
donc une simple notation pour $s$).  Autrement dit, ceci correspond à
voir une stratégie mixte comme une combinaison convexe d'éléments
de $B$, i.e., un point du simplexe affine dont les sommets sont les
éléments de $B$.  En particulier, un élément $b$ de $B$ (stratégie
pure) sera identifié à l'élément de $S_B$ qui affecte le poids $1$
à $b$ et $0$ à tout autre élément.

En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$
sera vu (notamment comme espace topologique) comme le fermé de
$\mathbb{R}^B$ défini par l'intersection des demi-espaces de
coordonnées positives et de l'hyperplan défini par la somme des
coordonnées égale à $1$.
\end{defn}

\begin{defn}\label{definition-mixed-strategy-game}
Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i
\to\mathbb{R}$ comme on vient de le dire.  On notera parfois $S_i$
l'ensemble des stratégies mixtes du joueur $i$.  Un \textbf{profil de
  stratégies mixtes} est un élément du produit cartésien $S := S_1
\times \cdots \times S_N$.

Plus généralement, si $I \subseteq \{1,\ldots,N\}$ est un ensemble de
joueurs, un élément du produit $S_I := \prod_{j\in I} S_j$ s'appellera
un profil de stratégies mixtes pour l'ensemble $I$ de joueurs ; ceci
sera notamment utilisé si $I = \{1,\ldots,N\}\setminus\{i\}$ est
l'ensemble de tous les joueurs sauf le joueur $i$, auquel cas on
notera $S_{?i} := \prod_{j\neq i} S_j$ l'ensemble des profils.
Naturellement, si chaque composante est une stratégie pure, on pourra
parler de profil de stratégies pures.
\end{defn}

\thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un
élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une
distribution de probabilité sur chaque $A_i$, n'est pas la même chose
qu'une distribution de probabilités sur $A := A_1 \times \cdots \times
A_N$.  Néanmoins, on peut voir les profils de stratégies mixtes comme
des distributions particulières sur $A$, à savoir celles pour
lesquelles les marginales (i.e., les projections sur un des $A_i$)
sont indépendantes.  Concrètement, ceci signifie que donné
$(s_1,\ldots,s_N) \in S$, on en déduit un $s\colon A\to\mathbb{R}$,
aussi une distribution de probabilité, par la définition suivante :
$s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des
$s_i(a_i)$).  On identifiera parfois abusivement l'élément
$(s_1,\ldots,s_N) \in S$ à la distribution $s\colon A\to\mathbb{R}$
qu'on vient de décrire (ce n'est pas un problème car $s_i$ se déduit
de $s$ : précisément, $s_i(b) = \sum_{a: a_i = b} s(a)$ où la somme
est prise sur les $a \in A$ tels que $a_i = b$).

Ceci conduit à faire la définition suivante :

\begin{defn}
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
appelle \textbf{gain [espéré]} du joueur $i$ selon ce profil la
quantité
\[
u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
\]
(ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$
vers $\mathbb{R}$).
\end{defn}

Selon l'approche qu'on veut avoir, on peut dire qu'on a défini
$u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré selon
la distribution de probabilité $s_i$ ; ou bien qu'on a utilisé
l'unique prolongement de $u_i$ au produit des simplexes $S_i$ qui soit
affine en chaque variable $s_i$.

\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 \ldots i \leq N$ et si
$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots
\times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil
de stratégies mixtes pour tous les joueurs autres que le joueur $i$,
on dit que la stratégie mixte $s_! \in S_i$ est une \textbf{meilleure
  réponse} (resp. la meilleure réponse stricte) contre $s_?$ lorsque
pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$
(resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a
$u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ désigne l'élément de
$S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme
$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$.

Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble
des joueurs) est dit être un \textbf{équilibre de Nash} (resp., un
équilibre de Nash \emph{strict}) lorsque pour tout $1\leq i \leq N$,
la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse
(resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour
les autres joueurs obtenu en supprimant la composante $s_i$ de $s$.
\end{defn}

\begin{prop}\label{stupid-remark-best-mixed-strategies}
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $1 \ldots 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.
\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 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).

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_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$.  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 ?}


%
%
%

\section{Jeux à somme nulle en forme normale}

\subsection{Le théorème du minimax}

\begin{thm}[« du minimax », 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 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}
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}y
\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}

Avec les hypothèses et notations du corollaire, l'ensemble des $x$
tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
compact $C_0 \neq \varnothing$ inclus dans $C$.


%
%
%

\section{Théorie combinatoire des jeux impartiaux}

\subsection{Graphes orientés bien-fondés}

\begin{defn}
Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
d'un ensemble $G$ muni d'une relation $E$ irreflexive.  Les éléments
de $G$ s'appelle \textbf{sommets} et les éléments de $E$
\textbf{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 \textbf{atteint} par une arête de
source $x$, ou encore que $y$ est un \textbf{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é \textbf{puits} dans $G$.

Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
que $E$ l'est alors aussi).  Il est dit \textbf{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 \textbf{bien-fondé}
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}$.
\end{defn}

\thingy 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}
Si $G$ est un graphe orienté on appelle \textbf{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 atteint par une arête de source $x_i$ (on autorise
$n=0$, c'est-à-dire que chaque sommet est toujours accessible à partir
de lui-même).

L'ensemble des sommets accessibles à partir d'un sommet $x$
s'appellera aussi l'\textbf{aval} de $x$.  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.

L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour
chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
\end{defn}

\thingy On peut remarquer que la relation d'accessibilité sur $G$ est
antisymétrique (i.e., est une relation d'ordre partiel) si et
seulement si $G$ est acyclique.  Lorsque $G$ est bien-fondé, la
relation d'accessibilité est elle-même bien-fondée (i.e., le graphe
qu'elle définit est bien-fondé).

\begin{defn}
Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
$G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
« si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $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 \textbf{aval-inductif} lorsqu'il vérifie la propriété suivante :
« lorsque $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$ »).
\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, 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 « lorsque $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 »), 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}
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}

\begin{prop}
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é « lorsque $x \in
  G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors
  $x$ lui-même appartient à $P$ » entre guillemets dans (\ddag)
de \ref{well-founded-induction}).
\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é),
donc un sommet qui appartient à toute partie aval-inductive de $G$
est, en particulier, dans la partie bien-fondée de $G$.
\end{proof}

\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é anoncé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}
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}
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
$\rho\colon G \to \mathbb{N}$ par $\rho(x) = \max\{\rho(y) :
y\in\outnb(x)\} + 1$ où on 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 $\rho$ la fonction telle que $\rho(x) = \Phi(x,
\rho|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par
le théorème.  Cette fonction $\rho$ s'appelle la \textbf{fonction
  rang} sur $G$, on dit que $\rho(x)$ est le rang (ou rang bien-fondé)
d'un sommet $x$.
\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
$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est 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$.

Pour un graphe non supposé bien-fondé, on peut définir son rang comme
on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) =
\infty$ lorsque $x$ n'appartient pas à la partie bien-fondée.

Voici un autre exemple de définition par induction bien-fondée :

\begin{defn}
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
$\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(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
$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
\gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont
garanties par le théorème.  Cette fonction $\gamma$ s'appelle la
\textbf{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
valeur de Grundy d'un sommet $x$.
\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.

\begin{defn}\label{definition-transitive-collapse}
Soit $G$ un graphe orienté bien-fondé.  En utilisant le
théorème \ref{well-founded-definition} (modulo la remarque qui suit),
on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
y\in\outnb(x)\}$.  L'image de $G$ par la fonction $f$ (c'est-à-dire
l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
  transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
$f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
orienté) s'appelle l'écasement transitif du sommet $x$.
\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.

Il y a une subtilité ensembliste dans la définition ci-dessus, c'est
qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel
$f$ prend sa valeur : il faut en fait appliquer une généralisation
de \ref{well-founded-definition} où $Z$ est remplacé par l'univers de
tous les ensembles : nous ne rentrerons pas dans ces subtilités, et
admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui
vérifie $f(x) = \{f(y) : y\in\outnb(x)\}$ pour chaque $x\in G$.

\begin{defn}
Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux
sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x)
= \outnb(x')$) sont égaux.
\end{defn}

\begin{prop}
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 par induction bien-fondée que $f$
est injective sur l'aval de tout sommet $x$.  Soit $P$ l'ensemble des
$x$ tels que $f$ restreinte à l'aval de $x$ soit injective.  Soit $x$
un sommet dont tous les voisins sortants appartiennent à $P$ :
\textcolor{red}{à finir.}
\end{proof}

%
%
%
\end{document}