diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 52 |
1 files changed, 24 insertions, 28 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 03118a3..e726aad 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -23,7 +23,7 @@ \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} -\usepackage{hyperref} +\usepackage[hyperindex=false]{hyperref} % \theoremstyle{definition} \newtheorem{comcnt}{Tout}[subsection] @@ -78,7 +78,7 @@ % \makeindex \begin{document} -\title{Théorie(s) des jeux\\(notes provisoires)} +\title{Théorie(s) des jeux\\(notes de cours)} \author{David A. Madore} \maketitle @@ -101,11 +101,6 @@ Git: \input{vcline.tex} % % -{\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} @@ -213,7 +208,7 @@ 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 +\thingy Le jeu peut être \index{partial (jeu)|see{partisan}}\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). @@ -403,7 +398,7 @@ 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 +\thingy\label{dove-or-hawk} Le jeu du \defin[trouillard (jeu du)]{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 @@ -581,7 +576,7 @@ impartial à connaissance parfaite (un cas particulier du jeu général défini en \ref{introduction-graph-game}). On verra en \ref{subsection-nim-sum} 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 \index{nim (somme de)}\index{somme de nim}\textit{somme de nim} dans ce contexte des + exclusif », appelé aussi \index{nim (somme de)|see{somme de nim}}\index{somme de nim}\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 \index{Grundy (fonction de)}\textit{fonction de Grundy} de la position, et le jeu est gagnable par le second joueur (c'est-à-dire, @@ -1500,11 +1495,11 @@ 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 +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 d'un jeu]{arbre} du jeu $G_X$. Une \defin[partie|see{confrontation}]{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é.} @@ -2023,7 +2018,7 @@ 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 +Une \textbf{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 @@ -2573,7 +2568,7 @@ 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 +\defin[progressivement fini|see{bien-fondé}]{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). @@ -2859,9 +2854,9 @@ 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 +seront appelés les \defin[P-position]{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 +que $f(x) = \mathtt{N}$) seront appelés \defin[N-position]{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}. @@ -3772,7 +3767,7 @@ ordinal $\alpha$ : \subsection{Ensembles bien-ordonnés et induction transfinie} \thingy\label{definition-well-ordered-set} -Un ensemble \defin[ordonné]{[partiellement] ordonné} est un ensemble +Un ensemble \defin[ordonné (ensemble)]{[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 @@ -3786,7 +3781,7 @@ $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 $x<y$ pour $y>x$. -Un ensemble partiellement ordonné est dit \defin[totalement ordonné]{totalement ordonné} +Un ensemble partiellement ordonné est dit \defin[totalement ordonné (ensemble)]{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 @@ -4775,10 +4770,11 @@ On rappelle qu'on a vu (cf. \ref{discussion-n-and-p-vertices} (=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 (Next)) en a une si et seulement si elle est $\neq 0$. (On -parlera de P-positions et de N-positions selon que la valeur de -Grundy est nulle ou non.) La stratégie « universelle » consiste -toujours à \emph{jouer de façon à annuler la valeur de Grundy} du -sommet vers lequel on joue (i.e., jouer vers les P-positions). +parlera de \index{P-position}P-positions et de +\index{N-position}N-positions selon que la valeur de Grundy est nulle +ou non.) La stratégie « universelle » consiste toujours à \emph{jouer + de façon à annuler la valeur de Grundy} du sommet vers lequel on +joue (i.e., jouer vers les P-positions). (On notera parfois $G\doteq 0$ pour dire que le second joueur a une stratégie gagnante, i.e., la valeur de Grundy de $G$ est $0$, i.e., la @@ -4838,7 +4834,7 @@ pour $\beta<\alpha$, c'est donc exactement $\alpha$. \begin{defn}\label{definition-nim-sum-of-games} Soient $G_1,G_2$ deux jeux combinatoires impartiaux dont on note $x_1,x_2$ les positions initiales et $E_1,E_2$ les relations d'arêtes. -On appelle \index{nim (somme de)}\defin{somme de nim} (ou simplement « somme ») de $G_1$ et +On appelle \defin{somme de nim} (ou simplement « somme ») de $G_1$ et $G_2$, et on note $G_1 \oplus G_2$ le jeu combinatoire impartial dont \begin{itemize} \item l'ensemble des positions est $G_1 \times G_2$, @@ -4893,7 +4889,7 @@ d'après \ref{definition-product-of-ordinals}.) \end{proof} \begin{defn}\label{definition-nim-sum-of-ordinals} -Soient $\alpha_1,\alpha_2$ deux ordinaux. On appelle \index{nim (somme de)}\defin{somme de +Soient $\alpha_1,\alpha_2$ deux ordinaux. On appelle \defin{somme de nim} de $\alpha_1$ et $\alpha_2$ et on note $\alpha_1 \oplus \alpha_2$ l'ordinal défini inductivement (cf. \ref{scholion-transfinite-definition}) par @@ -5449,7 +5445,7 @@ jeu — il n'est pas difficile de trouver des exemples de jeux tels que $G \doteq G'$ mais que cette relation ne vaille plus après l'opération. -On peut appeler \defin[valeur (d'un jeu combinatoire parisan)]{valeur} +On peut appeler \defin[valeur (d'un jeu combinatoire partisan)]{valeur} d'un jeu $G$ la classe de $G$ pour la relation $\doteq$. La proposition ci-dessus affirme donc que les \emph{valeurs} des jeux combinatoires partisans bien-fondés forment un groupe abélien |