From 6adeb9190e730a5ae8ba39675306031619c648fe Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 21 Feb 2017 15:01:03 +0100
Subject: Various clarifications / improvements on normal form games.

---
 notes-mitro206.tex | 134 ++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 102 insertions(+), 32 deletions(-)

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index d648151..96dfe79 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1145,6 +1145,18 @@ 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$).
 
+\danger (Il faudra prendre garde au fait qu'on peut voir $S$ soit
+comme une partie $S_1\times\cdots\times S_N$ de
+$\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$ formé des
+$N$-uplets $(s_1,\ldots,s_N)$, soit comme la partie de $\mathbb{R}^A =
+\mathbb{R}^{A_1\times\cdots\times A_N}$ formé des fonctions de la
+forme $s\colon (a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ comme on
+l'a expliqué au paragraphe précédent.  Ces deux points de vue ont un
+sens et ont parfois un intérêt, mais ils ne partagent pas les mêmes
+propriétés.  Par exemple, $S$ est convexe en tant que partie
+$S_1\times\cdots\times S_N$ de $\mathbb{R}^{A_1}\times\cdots\times
+\mathbb{R}^{A_N}$, mais pas en tant que partie de $\mathbb{R}^A$.)
+
 Ceci conduit à faire la définition suivante :
 
 \begin{defn}
@@ -1177,12 +1189,13 @@ $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 \defin{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)$
+  réponse} (resp. la meilleure réponse \textbf{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}$.
+$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$, c'est-à-dire le gain
+[espéré] obtenu en jouant $t$ contre $s_?$.
 
 Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble
 des joueurs) est dit être un \index{Nash (équilibre de)}\defin{équilibre de Nash} (resp., un
@@ -1197,24 +1210,36 @@ Donné un jeu en forme normale comme
 en \ref{definition-game-in-normal-form}, si $1 \leq 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_!$.
+qui est une stratégie pure.  De plus, si $s_!$ (stratégie mixte) est
+une meilleure réponse contre $s_?$ si et seulement si \emph{chaque}
+stratégie pure appartenant au support de $s_!$ est une meilleure
+réponse possible contre $s_?$ (et elles apportent toutes le même
+gain).
 
 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.
-
-(Si on préfère : une fonction affine sur un simplexe prend son maximum
-— ou son minimum — sur un des sommets de ce simplexe.)
+Tout ceci résulte du fait que le gain espéré $u_i(s_?,t)$ est une
+fonction affine de $t \in S_i$ (et une fonction affine sur un simplexe
+prend son maximum — ou son minimum — sur un des sommets de ce
+simplexe, et ne peut le prendre à l'intérieur que si elle prend aussi
+cette valeur sur les sommets).
+
+Plus précisément : $u_i(s_?,t)$ (pour $t \in S_i$) est combinaison
+convexe avec pour coefficients $t(a)$ pour $a\in A_i$, des
+$u_i(s_?,a)$.  Si $v$ est le maximum des $u_i(s_?,a)$ (qui sont en
+nombre fini donc ce maximum existe), alors $v$ est aussi le maximum de
+toute combinaison convexe $u_i(s_?,t)$ des $u_i(s_?,a)$ : c'est-à-dire
+que $t\in S_i$ est une meilleure réponse possible contre $s_?$ si et
+seulement si $u_i(s_?,t) = v$.  En particulier, tout $a \in A_i$ qui
+réalise ce maximum $v$ est une meilleure réponse possible
+(contre $s_?$) qui est une stratégie pure.  D'autre part, une
+combinaison convexe $u_i(s_?,t)$ de valeurs $\leq v$ ne peut être
+égale à $v$ que si toutes les valeurs $u_i(s_?,a)$ entrant
+effectivement (c'est-à-dire avec un coefficient $>0$) dans la
+combinaison sont égales à $v$ (s'il y en avait une $<v$, elle
+entraînerait forcément une moyenne pondérée $<v$), et réciproquement.
 \end{proof}
 
 \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria}
@@ -1277,8 +1302,10 @@ mais elle peut donner l'impression qu'on commet une « erreur
 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$ d'après \ref{brouwer-fixed-point-theorem}.  On va montrer que
-$s$ est un équilibre de Nash.
+fixe $s$ d'après \ref{brouwer-fixed-point-theorem} (notons qu'ici, $S$
+est vu comme le convexe $S_1\times\cdots\times S_N$ dans
+$\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$).  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
@@ -1294,7 +1321,41 @@ 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 ?}
+\thingy La question du calcul \emph{algorithmique} des équilibres de
+Nash, ou simplement d'\emph{un} équilibre de Nash, est délicate en
+général, ou même si on se restreint à $N=2$ joueurs (on verra
+en \ref{zero-sum-games-by-linear-programming-algorithm} ci-dessous que
+dans le cas particulier des jeux à somme nulle elle se simplifie
+considérablement).  Il existe un algorithme pour $N=2$, appelé
+\index{Lemke-Howson (algorithme de)}algorithme de Lemke-Howson, qui
+généralise l'algorithme du simplexe pour la programmation linéaire
+pour trouver un équilibre de Nash d'un jeu en forme normale : comme
+l'algorithme du simplexe, il est exponentiel dans le pire cas, mais se
+comporte souvent bien « en pratique ».
+
+Pour $N=2$, une méthode qui peut fonctionner dans des cas suffisamment
+petits consiste à énumérer tous les supports
+(cf. \ref{definition-mixed-strategy-abst}) possibles des stratégies
+mixtes des joueurs dans un équilibre de Nash, c'est-à-dire toutes les
+$(2^{\#A_1}-1)\times(2^{\#A_2}-1)$ données de parties non vides de
+$A_1$ et $A_2$, et, pour chacune, appliquer le raisonnement suivant :
+si $s_i$ est une meilleure réponse possible pour le joueur $i$ (contre
+la stratégie $s_{?i}$ de l'autre joueur) alors \emph{toutes les
+  options du support de $s_i$ ont la même espérance de gain}
+(contre $s_{?i}$ ; cf. \ref{stupid-remark-best-mixed-strategies}), ce
+qui fournit un jeu d'égalités linéaires sur les valeurs de $s_{?i}$.
+En rassemblant ces inégalités (ainsi que celles qui affirment que la
+somme des valeurs de $s_i$ et de $s_{?i}$ valent $1$), on arrive
+« normalement » à trouver tous les équilibres de Nash possibles : voir
+les exercices
+\ref{normal-form-game-exercise-two-by-two} et \ref{normal-form-game-exercise-three-by-three}
+(dernières questions) pour des exemples.
+
+(Pour $N\geq 3$, on sera amené en général à résoudre des systèmes
+d'équations algébriques pour chaque combinaison de supports : ceci est
+algorithmiquement possible en théorie en vertu d'un théorème de Tarski
+et Seidenberg sur la décidabilité des systèmes d'équations algébriques
+réels, mais possiblement inextricable dans la pratique.)
 
 
 
@@ -1425,13 +1486,19 @@ minimiser $u$).  Comme on l'a expliqué dans la preuve, on a
 donc en fait il y a égalité partout : tout équilibre de Nash réalise
 la même valeur $u(x_0,y_0) = \max_{x\in S_1} \min_{y\in S_2} u(x,y) =
 \min_{y\in S_2} \max_{x\in S_1} u(x,y)$, qu'on appelle la
-\defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle.  On peut donc parler de
-\index{optimale (stratégie)}\defin{stratégie optimale} pour le joueur $1$, resp. $2$ pour
-désigner une composante $x_0$, resp. $y_0$, d'un équilibre de Nash,
-i.e., vérifiant $\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in
-  S_2} u(x,y)$, resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2}
-\max_{x\in S_1} u(x,y)$, ces deux quantités étant égales à la valeur
-du jeu.
+\defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle.
+
+On peut donc parler de \index{optimale (stratégie)}\defin{stratégie
+  optimale} pour le joueur $1$, resp. $2$ pour désigner une composante
+$x_0$, resp. $y_0$, d'un équilibre de Nash, i.e., vérifiant
+$\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in S_2} u(x,y)$,
+resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2} \max_{x\in S_1}
+u(x,y)$, ces deux quantités étant égales à la valeur du jeu.
+
+Moralité : \emph{dans un jeu à somme nulle, un profil de stratégies
+  est un équilibre de Nash si et seulement si chaque joueur joue une
+  stratégie optimale} (l'ensemble des stratégies optimales étant
+défini pour chaque joueur indépendamment).
 
 Le corollaire \ref{symmetric-zero-sum-game} nous apprend (de façon peu
 surprenante) que si le jeu à somme nulle est \emph{symétrique} (ce qui
@@ -1461,9 +1528,12 @@ des $x$ tels que $u(x,b) \geq v$ pour tout $b\in A_2$.  En
 particulier, c'est un convexe compact dans $S_1$ (puisque chaque
 inégalité $u(x,b) \geq v$ définit un convexe compact dans $S_1$ vu que
 $x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies
-  optimales pour un joueur on obtient encore une telle stratégie}, ce
-qui n'est pas le cas en général pour des jeux qui ne sont pas à somme
-nulle.
+  optimales pour un joueur on obtient encore une telle stratégie}
+(notamment, l'ensemble des équilibres de Nash est un convexe de
+$S_1\times S_2$ — puisque c'est le produit du convexe des stratégies
+optimales pour le premier joueur par celui des stratégies optimales
+pour le second — affirmation qui n'est pas vraie en général pour des
+jeux qui ne sont pas à somme nulle).
 
 \begin{algo}\label{zero-sum-games-by-linear-programming-algorithm}
 Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec
@@ -1507,7 +1577,7 @@ on a égalité des optima).
 
 Comme l'algorithme du simplexe résout simultanément le problème primal
 et le problème dual, l'algorithme ci-dessus (exécuté avec l'algorithme
-du simplexe) trouve simultanément la stratégie optimale pour les deux
+du simplexe) trouve simultanément une stratégie optimale pour les deux
 joueurs.
 
 
@@ -5842,7 +5912,7 @@ les parties de l'ensemble, et font appel aux notions correspondantes.)
 
 \subsection{Jeux en forme normale}
 
-\exercice
+\exercice\label{normal-form-game-exercise-two-by-two}
 
 Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
 deux possibles appelées U et V, et Bob choisit une option parmi deux
@@ -6011,7 +6081,7 @@ et on a prouvé que c'étaient bien les seuls.
 %
 %
 
-\exercice
+\exercice\label{normal-form-game-exercise-three-by-three}
 
 Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
 trois possibles appelées U, V et W, et Bob choisit une option parmi
-- 
cgit v1.2.3