diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 108 |
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 |