Link zero-sum games and linear programming.

1 files changed, 96 insertions, 1 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index f3253a6..1bcf911 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -30,6 +30,7 @@
 \newtheorem{thm}[comcnt]{Théorème}
 \newtheorem{cor}[comcnt]{Corollaire}
 \newtheorem{scho}[comcnt]{Scholie}
+\newtheorem{algo}[comcnt]{Algorithme}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \newcommand{\outnb}{\operatorname{outnb}}
@@ -1260,7 +1261,7 @@ peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on
 voulait.
 \end{proof}
 
-\begin{cor}
+\begin{cor}\label{symmetric-zero-sum-game}
 Soit $C$ un convexe compact dans un espace affine réel de dimension
 finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine
 antisymétrique (i.e., $u(y,x) = -u(x,y)$).  Alors il
@@ -1284,6 +1285,100 @@ Avec les hypothèses et notations du corollaire, l'ensemble des $x$
 tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
 compact $C_0 \neq \varnothing$ inclus dans $C$.
 
+\thingy\label{minimax-for-games} Le théorème \ref{theorem-minimax}
+s'applique à la théorie des jeux de la manière suivante : si on
+considère un jeu à deux joueurs à somme nulle, en notant $S_1$ et
+$S_2$ les ensembles des stratégies mixtes des deux joueurs, et $u
+\colon S_1 \times S_2 \to \mathbb{R}$ le gain espéré du joueur $1$, le
+gain du joueur $2$ étant donc $-u$, le fait que $(x_0,y_0)$ soit un
+équilibre de Nash se traduit par le fait que $x_0$ soit la meilleure
+réponse possible de $1$ contre $y_0$, i.e., $u(x_0,y_0) = \max_{x\in
+  S_1} u(x,y_0)$, et le fait que $y_0$ soit la meilleure réponse
+possible de $2$ contre $x_0$, c'est-à-dire $u(x_0,y_0) = \min_{y\in
+  S_2} u(x_0,y)$ (puisque $2$ cherche à maximiser $-u$, c'est-à-dire
+minimiser $u$).  Comme on l'a expliqué dans la preuve, on a
+\[
+\max_{x\in S_1} \min_{y\in S_2} u(x,y)
+\geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0)
+= \max_{x\in S_1} u(x,y_0) \geq
+\min_{y\in S_2} \max_{x\in S_1} u(x,y)
+\]
+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
+\textbf{valeur} du jeu à somme nulle.  On peut donc parler de
+\textbf{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.
+
+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
+signifie que $u$ est antisymétrique), alors la valeur du jeu est
+nulle.
+
+\thingy Dans le contexte ci-dessus, on peut légèrement reformuler le
+minimax : si on se rappelle qu'\emph{une fonction affine sur un
+  simplexe prend son maximum (ou son minimum) sur un des sommets} du
+simplexe, cela signifie que, quel que soit $x\in S_1$ fixé, le minimum
+$\min_{y\in S_2} u(x,y)$ est en fait atteint sur une stratégie
+\emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{y\in A_2} u(x,y)$ (avec
+$A_2$ l'ensemble des sommets de $S_2$, i.e., l'ensemble des stratégies
+pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{x\in
+  A_1} u(x,y)$ quel que soit $y \in S_2$.  \emph{Ceci ne signifie pas}
+qu'il existe un équilibre de Nash en stratégies pures (penser à
+pierre-papier-ciseaux).  Néanmoins, cela signifie que pour calculer la
+pire valeur possible $\min_{y\in S_2} u(x,y)$ d'une stratégie $x$ du
+joueur $1$, celui-ci peut ne considérer que les réponses en stratégies
+pures du joueur $2$.
+
+\begin{algo}
+Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec
+$A_1,A_2$ deux ensembles finis) définissant la matrice de gains pour
+le joueur $1$ d'un jeu à somme nulle.  On peut calculer une stratégie
+mixte optimale (cf. \ref{minimax-for-games}) pour le joueur $1$ en
+résolvant, par exemple au moyen de l'algorithme du simplexe, le
+problème de programmation linéaire dont les variables sont les $x_a$
+pour $a \in A_1$ (les poids de la stratégie mixte) et $v$ (le gain
+obtenu) cherchant à maximiser $v$ sujet aux contraintes :
+\[(\forall a\in A_1)\;x_a \geq 0\]
+\[\sum_{a\in A_1} x_a = 1\]
+\[(\forall b\in A_2)\;v \leq u(x,b) := \sum_{a \in A_1} u(a,b)\, x_a\]
+Autrement dit, il s'agit d'un problème de programmation linéaire à
+$\#A_1 + 1$ variables avec des contraintes de positivité sur $\#A_1$
+d'entre elles, une contrainte d'égalité et $\#A_2$ inégalités affines.
+\end{algo}
+
+\thingy Pour ramener ce problème à un problème de programmation
+linéaire en \emph{forme normale} (maximiser $\textbf{p} x$ sous les
+contraintes $\textbf{M} x \leq \textbf{q}$ et $x\geq 0$), on sépare la
+variable $v$ en $v_+ - v_-$ avec $v_+,v_- \geq 0$, et le problème
+devient de maximiser $v_+ - v_-$ sous les contraintes
+\[v_+\geq 0,\; v_- \geq 0,\;\; (\forall a\in A_1)\;x_a \geq 0\]
+\[\sum_{a\in A_1} x_a \leq 1\]
+\[-\sum_{a\in A_1} x_a \leq -1\]
+\[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\]
+Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les
+contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$
+et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes
+\[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\]
+\[\sum_{b\in A_2} y_b \leq 1\]
+\[-\sum_{b\in A_2} y_b \leq -1\]
+\[(\forall a\in A_1)\;w_+ - w_- - \sum_{b \in A_2} u(a,b)\, y_b \geq 0\]
+Il s'agit donc exactement du même problème, mais pour l'autre joueur.
+
+Le théorème \ref{theorem-minimax} est essentiellement équivalent au
+théorème de dualité pour la programmation linéaire (qui assure que si
+le problème primal a un optimum $x_0$ alors le dual en a un $y_0$, et
+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
+joueurs.
+
 
 %
 %