Rework and describe outline.

1 files changed, 72 insertions, 36 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index ce85b43..c8d954c 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -286,16 +286,16 @@ 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 Le jeu de \textbf{pierre-papier-ciseaux} : Alice et Bob
-choisissent simultanément un élément de l'ensemble
-$\{\textrm{pierre},\penalty0 \textrm{papier},\penalty0
-\textrm{ciseaux}\}$.  S'ils ont choisi le même élément, le jeu est
-nul ; sinon, papier gagne sur pierre, ciseaux gagne sur papier et
-pierre gagne sur ciseaux (l'intérêt étant qu'il s'agit d'un « ordre »
-cyclique, totalement symétrique entre les options).  Il s'agit
-toujours d'un jeu à somme nulle (disons que gagner vaut $+1$ et perdre
-vaut $-1$), et cette fois les deux joueurs sont en situation
-complètement symétrique.
+\thingy\label{rock-paper-scissors} Le jeu de
+\textbf{pierre-papier-ciseaux} : Alice et Bob choisissent
+simultanément un élément de l'ensemble $\{\textrm{pierre},\penalty0
+\textrm{papier},\penalty0 \textrm{ciseaux}\}$.  S'ils ont choisi le
+même élément, le jeu est nul ; sinon, papier gagne sur pierre, ciseaux
+gagne sur papier et pierre gagne sur ciseaux (l'intérêt étant qu'il
+s'agit d'un « ordre » cyclique, totalement symétrique entre les
+options).  Il s'agit toujours d'un jeu à somme nulle (disons que
+gagner vaut $+1$ et perdre vaut $-1$), et cette fois les deux joueurs
+sont en situation complètement symétrique.
 
 \begin{center}
 \begin{tabular}{r|ccc}
@@ -335,9 +335,10 @@ Puits&$+1,-1$&$-1,+1$&$+1,-1$&$0,0$\\
 \end{tabular}
 \end{center}
 
-\thingy Le \textbf{dilemme du prisonnier} : Alice et Bob choisissent
-simultanément une option parmi « coopérer » ou « faire défaut ».  Les
-gains sont déterminés par la matrice suivante :
+\thingy\label{prisonners-dilemma} Le \textbf{dilemme du prisonnier} :
+Alice et Bob choisissent simultanément une option parmi « coopérer »
+ou « faire défaut ».  Les gains sont déterminés par la matrice
+suivante :
 
 \begin{center}
 \begin{tabular}{r|cc}
@@ -364,11 +365,11 @@ 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 Le jeu du \textbf{trouillard}, ou de la \textbf{colombe et du
-  faucon}, obtenu en modifiant les gains du dilemme du prisonnier pour
-pénaliser le double défaut (maintenant appelé rencontre faucon-faucon)
-plus lourdement que la coopération (colombe) face au défaut.
-Autrement dit :
+\thingy\label{dove-or-hawk} Le jeu du \textbf{trouillard}, ou de la
+\textbf{colombe et du faucon}, obtenu en modifiant les gains du
+dilemme du prisonnier pour pénaliser le double défaut (maintenant
+appelé rencontre faucon-faucon) plus lourdement que la coopération
+(colombe) face au défaut.  Autrement dit :
 
 \begin{center}
 \begin{tabular}{r|cc}
@@ -408,10 +409,10 @@ probabilités respectives $\frac{L-X}{W-T + L-X}$ et $\frac{W-T}{W-T +
 $\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 La \textbf{guerre des sexes}.  Alice et Bob veulent faire du
-sport ensemble : Alice préfère l'alpinisme, Bob préfère la boxe, mais
-tous les deux préfèrent faire quelque chose avec l'autre que
-séparément.  D'où les gains suivants :
+\thingy\label{battle-of-sexes} La \textbf{guerre des sexes}.  Alice et
+Bob veulent faire du sport ensemble : Alice préfère l'alpinisme, Bob
+préfère la boxe, mais tous les deux préfèrent faire quelque chose avec
+l'autre que séparément.  D'où les gains suivants :
 
 \begin{center}
 \begin{tabular}{r|cc}
@@ -526,7 +527,8 @@ 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 Le \textbf{jeu de nim} : un certain nombre d'allumettes sont
+\thingy\label{introduction-nim-game} Le \textbf{jeu de nim} : un
+certain nombre d'allumettes sont
 arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
 retirent des allumettes, au moins une à chaque fois, et autant qu'ils
 veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui
@@ -677,8 +679,8 @@ directement en mordant en $(i,j)$, il se ramènerait à cet état, les
 rôles des joueurs étant inversés, donc il aurait une stratégie
 gagnante, et cela signifie qu'il en a une dès le premier tour.
 
-\thingy Le jeu de \textbf{Hackenbush} impartial, bicolore, ou
-tricolore.
+\thingy\label{introduction-hackenbush} Le jeu de \textbf{Hackenbush}
+impartial, bicolore, ou tricolore.
 
 Dans ce jeu, l'état est défini par un dessin, plus précisément un
 graphe non orienté, pouvant avoir des arêtes multiples et des arêtes
@@ -890,11 +892,40 @@ sur le coup $y$ qu'il jouerait selon le coup $x$ de $A$, on peut
 véritablement changer le jeu.
 
 
+\subsection{Plan}
+
+La section \ref{section-games-in-normal-form} concerne les jeux en
+forme normale et la notion d'équilibre de Nash : on gardera donc à
+l'esprit les exemples tels que le dilemme du
+prisonnier (\ref{prisonners-dilemma}), le
+trouillard (\ref{dove-or-hawk}) et la bataille des
+sexes (\ref{battle-of-sexes}).  On évoque plus particulièrement les
+jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des
+jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}).
+
+La section \ref{section-well-founded-induction} introduit la notion de
+graphe bien-fondée et d'induction bien-fondée qui est essentielle pour
+la suite.
+
+La section \ref{section-combinatorial-impartial-games} concerne la
+théorie, dite « combinatoire », des jeux impartiaux à information
+parfaite, dont le modèle est décrit en \ref{introduction-graph-game}
+(sans coloriage) et dont l'archétype est le jeu de nim
+(cf. \ref{introduction-nim-game}) ou le Hackenbush impartial (=vert)
+(cf. \ref{introduction-hackenbush}).
+
+On parlera ensuite des jeux \emph{partiaux} à information parfaite,
+dont l'archétype est le Hackenbush bicolore ou tricolore, et de la
+théorie des nombres de Conway.
+
+Enfin, on évoquera quelques jeux en vrac et des liens avec la logique.
+
+
 %
 %
 %
 
-\section{Jeux en forme normale}
+\section{Jeux en forme normale}\label{section-games-in-normal-form}
 
 \subsection{Généralités}
 
@@ -1006,6 +1037,10 @@ 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
@@ -1130,13 +1165,8 @@ de Nash.
 \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}
+\subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games}
 
 \begin{thm}[« du minimax », von Neumann, 1928]\label{theorem-minimax}
 Soient $C$ et $C'$ deux convexes compacts dans des espaces affines
@@ -1251,9 +1281,7 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 %
 %
 
-\section{Théorie combinatoire des jeux impartiaux}
-
-\subsection{Graphes orientés bien-fondés}
+\section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction}
 
 Le but de cette section est de présenter les outils fondamentaux sur
 les graphes orientés bien-fondés (cf. \ref{definitions-graphs})
@@ -1262,6 +1290,8 @@ 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}
+
 \begin{defn}\label{definitions-graphs}
 Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
 d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
@@ -1901,7 +1931,13 @@ de $G$, et comme la fonction d'écrasement est injective sur
 $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$).
 
 
-\subsection{Jeux impartiaux à information parfaite}
+%
+%
+%
+
+\section{Théorie combinatoire des jeux impartiaux à information parfaite}\label{section-combinatorial-impartial-games}
+
+\subsection{Généralités}
 
 \begin{defn}\label{definition-impartial-combinatorial-game}
 Un jeu \textbf{impartial à information parfaite} est un graphe