diff options
| -rw-r--r-- | notes-mitro206.tex | 134 |
1 files 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 |