summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2015-12-03 12:12:53 +0100
committerDavid A. Madore <david+git@madore.org>2015-12-03 12:12:53 +0100
commitcb037fa60cb356a695c3323a7d27990aa1ae7767 (patch)
tree35aca78d3f33cfc2a31c4b028bfd8bf0a346c9fd /notes-mitro206.tex
parentb694d921bf756d3c822d8eee32d23477186598da (diff)
downloadmitro206-cb037fa60cb356a695c3323a7d27990aa1ae7767.tar.gz
mitro206-cb037fa60cb356a695c3323a7d27990aa1ae7767.tar.bz2
mitro206-cb037fa60cb356a695c3323a7d27990aa1ae7767.zip
Start writing about games in normal form.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex121
1 files changed, 121 insertions, 0 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index a3e60d1..1c9edcf 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -403,4 +403,125 @@ 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}
+
+%
+%
+%
\end{document}