summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex52
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