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