From cb037fa60cb356a695c3323a7d27990aa1ae7767 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 3 Dec 2015 12:12:53 +0100
Subject: Start writing about games in normal form.

---
 notes-mitro206.tex | 121 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 121 insertions(+)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index a3e60d1..1c9edcf 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -400,6 +400,127 @@ sur le coup $y$ qu'il jouerait selon le coup $x$ de $A$, on peut
 véritablement changer le jeu.
 
 
+%
+%
+%
+
+\section{Jeux en forme normale}
+
+\subsection{Généralités}
+
+\begin{defn}\label{definition-game-in-normal-form}
+Un \textbf{jeu en forme normale} à $N$ joueurs est la donnée de $N$
+ensembles finis $A_1,\ldots,A_N$ et de $N$ fonctions
+$u_1,\ldots,u_N\colon A \to \mathbb{R}$ où $A := A_1 \times \cdots
+\times A_N$.
+
+Un élément de $A_i$ s'appelle une \textbf{option} ou \textbf{stratégie
+  pure} pour le joueur $i$.  Un élément de $A := A_1 \times \cdots
+\times A_N$ s'appelle un \textbf{profil de stratégies pures}.  La
+valeur $u_i(a)$ de la fonction $u_i$ sur un $a\in A$ s'appelle le
+\textbf{gain} du joueur $i$ selon le profil $a$.
+\end{defn}
+
+Le jeu doit se comprendre de la manière suivante : chaque joueur
+choisit une option $a_i \in A_i$ indépendamment des autres, et chaque
+joueur reçoit un gain égal à la valeur $u_i(a_1,\ldots,a_n)$ définie
+par le profil $(a_1,\ldots,a_n)$ des choix effectués par tous les
+joueurs.  Le but de chaque joueur est de maximiser son propre gain.
+
+On utilisera le terme « option » ou « stratégie pure » selon qu'on
+veut souligner que le joueur $i$ choisit effectivement $a_i$ ou décide
+a priori de faire forcément ce choix-là.  Cette différence vient du
+fait que les joueurs peuvent également jouer de façon probabiliste, ce
+qui amène à introduire la notion de stratégie mixte :
+
+\begin{defn}\label{definition-mixed-strategy}
+Donné un ensemble $B$ fini d'« options », on appelle \textbf{stratégie
+  mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que
+$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ :
+autrement dit, il s'agit d'une distribution de probabilités sur $B$.
+
+Parfois, on préférera considérer la stratégie comme la combinaison
+formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le
+produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est
+défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est
+donc une simple notation pour $s$).  Autrement dit, ceci correspond à
+voir une stratégie mixte comme une combinaison barycentrique
+d'éléments de $B$, i.e., un point du simplexe affine dont les sommets
+sont les éléments de $B$.  En particulier, un élément $b$ de $B$
+(stratégie pure) sera identifié à l'élément de $S_B$ qui affecte le
+poids $1$ à $b$ et $0$ à tout autre élément.
+
+En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$
+sera vu (notamment comme espace topologique) comme le fermé de
+$\mathbb{R}^B$ défini par l'intersection des demi-espaces de
+coordonnées positives et de l'hyperplan défini par la somme des
+coordonnées égale à $1$.
+
+Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
+stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i
+\to\mathbb{R}$ comme on vient de le dire.  On notera parfois $S_i$
+l'ensemble des stratégies mixtes du joueur $i$.  Un \textbf{profil de
+  stratégies mixtes} est un élément du produit cartésien $S_1 \times
+\cdots \times S_N$.
+\end{defn}
+
+\thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un
+élément de $S_1 \times \cdots \times S_N$, i.e., la donnée d'une
+distribution de probabilité sur chaque $A_i$, n'est pas la même chose
+qu'une distribution de probabilités sur $A := A_1 \times \cdots \times
+A_N$.  Néanmoins, on peut voir les profils de stratégies mixtes comme
+des distributions particulières sur $A$, à savoir celles pour
+lesquelles les marginales (i.e., les projections sur un des $A_i$)
+sont indépendantes.  Concrètement, ceci signifie que donné
+$(s_1,\ldots,s_N) \in S_1\times \cdots \times S_N$, on en déduit un
+$s\colon A\to\mathbb{R}$, aussi une distribution de probabilité, par
+la définition suivante : $s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$
+(produit des $s_i(a_i)$).  Ceci conduit à faire la définition
+suivante :
+
+\begin{defn}
+Donné un jeu en forme normale comme
+en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
+S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
+appelle \textbf{gain [espéré]} du joueur $i$ selon ce profil la
+quantité
+\[
+u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
+\]
+(ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$
+vers $\mathbb{R}$).
+\end{defn}
+
+Selon l'approche qu'on veut avoir, on peut dire qu'on a défini
+$u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré selon
+la distribution de probabilité $s_i$ ; ou bien qu'on a utilisé
+l'unique prolongement de $u_i$ au produit des simplexes $S_i$ de
+sommets $A_i$ lui-même plongé multilinéairement dans le simplexe de
+sommets $A$.
+
+\begin{defn}
+Donné un jeu en forme normale comme
+en \ref{definition-game-in-normal-form}, un profil de stratégies
+mixtes $s = (s_1,\ldots,s_N)$ est dit être un \textbf{équilibre de
+  Nash} (resp., un équilibre de Nash \emph{strict}) lorsque pour tout
+$1\leq i \leq N$ et tout $t \in S_i$, on a
+\[
+u_i(s_1,\ldots,s_i,\ldots,s_N) \leq
+u_i(s_1,\ldots,t,\ldots,s_N)
+\]
+(resp. $u_i(s_1,\ldots,s_i,\ldots,s_N) <
+u_i(s_1,\ldots,t,\ldots,s_N)$), où ici $u_i(s_1,\ldots,t,\ldots,s_N)$
+désigne le gain espéré du joueur $i$ selon le profil de stratégies
+mixtes obtenu en remplaçant la $i$-ième coordonnées $s_i$ de $s$
+par $t$ (et en laissant les autres inchangées).
+\end{defn}
+
+\begin{thm}
+Pour un jeu en forme normale comme
+en \ref{definition-game-in-normal-form}, il existe un équilibre de
+Nash.
+\end{thm}
+
 %
 %
 %
-- 
cgit v1.2.3