\documentclass[XUPS,XML,SOM,NoEqCountersInSection,Unicode,francais]{cedram}
\usepackage{xups06-04}
\setcounter{tocdepth}{2}


\begin{document}
\frontmatter

\title{Jeux stochastiques}
\author[\initial{R.} \lastname{Laraki}]{\firstname{Rida} \lastname{Laraki}}
\address{CNRS, Laboratoire d'Économétrie,
École polytechnique,
1~rue~Descartes,
75005 Paris}

\email{rida.laraki@dauphine.fr}
\urladdr{https://sites.google.com/site/ridalaraki}

\thanks{Journées X-UPS 2006. Théorie des jeux -- Introduction à la théorie des jeux répétés. Éditions de l'École polytechnique, 2006}

\maketitle
\vspace*{-\baselineskip}
\tableofcontents
\mainmatter

\section{Introduction}\label{sec:1}

Les jeux stochastiques modélisent l'interaction entre des décideurs pouvant influencer leur environnement. Ces jeux ont d'abord été introduits et étudiés par Loyd Shapley (1953). Depuis, la littérature n'a cessé de croître.

Dans un jeu stochastique, les joueurs font face à des buts potentiellement différents. Ils doivent assurer un bon paiement aujourd'hui tout en maintenant une espérance de paiement élevée pour demain.

Les jeux stochastiques utilisent des outils mathématiques très variés. Nous allons présenter ici quelques résultats classiques, principalement pour les jeux à somme nulle. Plus précisément, les sections \ref{sec:2} à \ref{sec:4} présentent le modèle. Les sections (\ref{sec:5}, \ref{sec:6} puis \ref{sec:12}) sont dédiées aux jeux à $n$ joueurs et somme non nulle. Les sections \ref{sec:7} à \ref{sec:11} sont dédiées aux jeux à somme nulle.

Ce texte s'est inspiré principalement du cours sur les jeux répétés à somme nulle de Sorin (2002), du cours NATO sur les jeux stochastiques et leurs applications édité par Neyman et Sorin (2003), du polycopié de cours de DEA --- non publié --- sur les jeux stochastiques par Solan (2006) et, enfin, d'un article sur l'étude asymptotique des jeux absorbants à somme nulle par Laraki (2006).

\section{Déroulement}\label{sec:2}

Nous considérons un espace d'états (ou d'environnements) $\Omega $ fini. Nous avons un ensemble fini de joueurs noté $N=\left\{1,\ldots,\vert N\vert \right\}$. Dans chaque état $\omega $ le joueur~$i$ aura un ensemble d'actions (par étape) $A^{i}\left(\omega \right)$ considéré lui aussi fini (et non vide). $A(\omega)=\Pi_{i}A^{i}(\omega)$ est donc l'ensemble de tous les profils d'actions admissibles en une étape donnée à l'état $\omega $. Nous notons l'ensemble des couples (état, profil d'actions) par:
\begin{equation*}
\Omega A=\{ \left(\omega,a\right)\mid a\in A(\omega)\}.
\end{equation*}
Donnons nous aussi une famille de probabilités de transition $q:\Omega A\to \Delta (\Omega)$ où $\Delta (X)$ est l'ensemble des probabilités sur $X$, et un état initial~$\omega_1$. Enfin, soit $g^{i}:\Omega A\to \mathbb{R}$ la fonction de paiement d'étape du joueur~$i$.

Le jeu se déroule comme suit:
\begin{itemize}
\item
\textit{Étape 1}: l'état initial est noté $\omega_{1}$. De manière simultanée et indépendante, chaque joueur choisit une action dans son ensemble d'actions admissibles en $\omega_{1}$. Si le profil $a_{1}=(a_{1}^{i})_{i\in N}\in A(\omega)$ a été choisi, chaque joueur~$i$ reçoit pour l'étape 1 le paiement $g_{1}^{i}=g^{i}(\omega_{1},a_{1})$. Un~état $\omega_{2}$ est alors tiré selon la distribution de probabilité $q(\omega_{1},a_{1})$. Ensuite, le couple (état, profil d'actions) $(a_{1},\omega_{2})$ est annoncé publiquement à tous les joueurs.

Le déroulement est maintenant défini par induction.

\item
\textit{Étape} $t\geq 2$: connaissant l'histoire passée $h_{t}$,\vspace*{-3pt}\enlargethispage{\baselineskip}
\begin{equation*}
h_{t}=(\omega_{1},a_{1},\dots,\omega_{t-1,}a_{t-1},\omega_{t}),
\end{equation*}
simultanément, chaque joueur choisit de façon indépendante aux autres une action dans son ensemble d'actions admissibles en $\omega_{t}$. Si le profil $a_{t}=(a_{t}^{i})_{i\in N}$ est choisi, chaque joueur~$i$ reçoit pour l'étape $t$ le paiement $g_{t}^{i}=g^{i}(\omega_{t},a_{t})$. Un état $\omega_{t+1}$ est alors tiré selon la distribution de probabilité $q(\omega_{t},a_{t})$. Enfin, le couple (profil d'actions,état) $(a_{t},\omega_{t+1})$ est annoncé publiquement à tous les joueurs.
\end{itemize}

\emph{À titre d'exemple}, la pêche est une industrie importante au Royaume-Uni et en Islande. Les deux pays partagent le même territoire dans l'Atlantique. Chaque année ils doivent fixer des quotas pour leurs pêcheurs respectifs. La décision des quotas est déterminée chaque année par rapport au nombre moyen $z$ de $kg$ de poisson par $km^{2}$. Celui-ci est mesuré chaque année à la fin de septembre. Les pêcheurs pêchent généralement l'intégralité de leurs quotas. Le taux de croissance des poissons est supposé être de $2\%\left(1-\exp(-cz)\right)$ où $c$ est une constante fixée. Le gain pour le Royaume-Uni est mesuré par le nombre $x$ de $kg$ de poissons pêchés par ses pêcheurs par $km^{2}$. Le gain pour l'Islande est mesuré par le nombre $y$ de $kg$ de poissons pêchés par ses pêcheurs par $km^{2}$. En supposant que le Royaume-Uni a un pouvoir de négociation par rapport à l'Islande égal à $\alpha \in \left[ 0,1\right] $, cette description peut s'écrire comme un jeu stochastique (avec un espace d'état et des ensembles d'actions compacts mais qui peuvent tous être discrétisés). La variable d'état serait alors $\omega =z$. Quand l'état est $z$, le Royaume-Uni peut choisir $x$ dans l'intervalle $A^{1}(z)=[0,\alpha z]$ et l'Islande peut choisir $y$ dans l'intervalle $A^{1}(z)=[0,(1-\alpha)z]$. Si l'état actuel est $z_{t}$ et que $x_{t}$ et $y_{t}$ ont été sélectionnés l'état demain sera,\vspace*{-3pt}
\begin{equation*}
z_{t+1}=(z_{t}-x_{t}-y_{t})+(z_{t}-x_{t}-y_{t})\times 2\%(1-\exp(-c(z_{t}-x_{t}-y_{t})).
\end{equation*}
La loi de transition est donc déterministe. Enfin la fonction de paiement du Royaume-Uni est $g^{1}(\omega,x,y)=x$ et celle de l'Islande est $g^{2}(\omega,x,y)=y$.

\section{Stratégies}\label{sec:3}

C'est essentiellement la même définition que dans le texte sur les jeux répétés (ce volume). Ici nous l'adaptons à notre contexte. Pour tout entier (ou étape) $t$, l'\textit{ensemble de toutes les histoires} possibles jusqu'à la date $t$ est noté:
\begin{equation*}
H_{t}=\left(\Omega A\right)^{t-1}\times \Omega.
\end{equation*}
Un élément de $H_{t}$ sera noté $h_{t}$ et la dernière composante est notée~$\omega_{t}$. $H_{1}$ est identifié avec l'espace d'état $\Omega$. La première histoire n'est autre que $\omega_{1}$. L'ensemble de toutes \textit{les histoires de longueur finie} est noté
\begin{equation*}
H=\bigcup_{t\geq 1}H_{t}.
\end{equation*}
Enfin, l'espace de toutes les \textit{histoires d'une longueur infinie} (appelé \textit{l'ensemble des parties}) est noté:
\begin{equation*}
H_{\infty}=\left(\Omega A\right)^{{\mathbb{N}^*}}.
\end{equation*}
Pour chaque date $t$, $H_{t}$ définit une partition (une algèbre ou un cylindre) de $H_{\infty}$: à chaque histoire de longueur finie $h_{t}\in H_{t}$ est associée l'ensemble des histoires infinies qui coïncident avec $h_{t}$ jusqu'à l'étape~$t$. Nous notons cette algèbre par $\mathcal{H}_{t}$ et notons par $\mathcal{H}$ la $\sigma$-algèbre générée par tous les cylindres.

\textit{Une stratégie de comportement} $\sigma^{i}$ pour le joueur~$i$ est une fonction qui associe à chaque histoire de longueur finie une action mixte dans $\Delta (A^{i})$. L'ensemble des stratégies de comportement du joueur~$i$ est noté $\Sigma^{i}$.

Une stratégie de comportement est \textit{pure} si pour chaque histoire finie $h_{t}$, $\sigma^{i}(h_{t})$ est pure (est une masse de dirac).

Une stratégie \textit{mixte} est une distribution de probabilité sur les stratégies pures.

Une stratégie de comportement est dite \textit{stationnaire} si, pour tout couple d'histoires de longueur finie $h_{t}=(\omega_{1},a_{1},\dots,\omega_{t-1,}a_{t-1},\omega_{t})$ et $\widehat{h}_{\widehat{t}}=(\widehat{\omega}_{1},\widehat{a}_{1},\dots,\widehat{\omega}_{\widehat{t}-1,}\widehat{a}_{\widehat{t}-1},\widehat{\omega}_{\widehat{t}})$,
\begin{equation*}
\omega_{t}=\widehat{\omega}_{\widehat{t}}\implies \sigma (h_{t})=\sigma (\widehat{h}_{\widehat{t}}).
\end{equation*}

Une stratégie stationnaire pour le joueur~$i$ sera notée $x^{i}$ et un profil sera noté par $x=(x^{1},\dots,x^{\left| N\right|})$. L'ensemble des stratégies stationnaires du joueur~$i$ sera noté $X^{i}$, qui peut être identifié à $\prod_{\omega \in \Omega}\Delta \left(A^{i}(\omega)\right)$. Ainsi, le nombre de stratégies stationnaires pures du joueur~$i$ est $\prod_{\omega \in \Omega}\left| A^{i}\left(\omega \right) \right| $ (où $\left| F\right| $ désigne le cardinal de l'ensemble~$F$).

Une stratégie est dite \textit{markovienne} si elle dépend seulement de l'état en cours et du nombre d'étapes écoulées. Mathématiquement, une stratégie de comportement est markovienne si, pour chaque couple d'histoires de même longueur $h_{t}=(\omega_{1},a_{1},\dots,\omega_{t-1,}a_{t-1},\omega_{t})$ et $\widehat{h}_{t}=(\widehat{\omega}_{1},\widehat{a}_{1},\dots,\widehat{\omega}_{t-1,}\widehat{a}_{t-1},\widehat{\omega}_{t})$,\enlargethispage{\baselineskip}
\begin{equation*}
\omega_{t}=\widehat{\omega}_{t}\implies \sigma (h_{t})=\sigma (\widehat{h}_{t}).
\end{equation*}

Chaque profil de stratégies $\sigma $ et chaque état initial $\omega_{1}$ définissent une unique distribution de probabilité sur $H_{\infty}$ (voir le texte sur les jeux répétés (ce volume)). Cette probabilité sera notée $\P_{\omega_{1},\sigma}$ et l'espérance mathématique associée sera noté $\E_{\omega_{1},\sigma}$.

\section{Objectifs}\label{sec:4}

Ce sont essentiellement les mêmes définitions que celles du le texte sur les jeux répétés (ce volume). Ici, nous les adaptons à notre contexte et les reprenons pour préserver une certaine indépendance entre les textes de ce volume.

\subsection{Approche compacte}

Dans cette approche on cherche une modélisation qui permet l'application directe des théorèmes standards d'existence de l'équilibre. On suppose donc que chaque joueur~$i$ cherche à maximiser une fonction de paiement total. Une telle fonction $\phi^{i}$ associe à chaque suite de paiements d'étapes $\left\{ g^{i}(\omega_{t},a_{t})\right\}_{t=1,\dots}$ une valeur dans l'intervalle $\left[ -M,M\right] $ que l'on peut interpréter comme le paiement moyen par étape, où
\begin{equation*}
M=\max_{\left(i,\omega,a\right) \in I\times \Omega A}\left| g^{i}(\omega,a)\right|.
\end{equation*}
Rappelons que $H_{\infty}$ est toujours munie de la topologie naturelle induite par les cylindres. On supposera dans l'approche compacte que pour chaque profil de stratégies pures des autres joueurs $\sigma^{-i}$, la fonction $\sigma^{i}\mto \phi^{i}\left(\sigma^{i},\sigma^{-i}\right)$ où $\sigma^{i}$ parcourt l'ensemble des stratégies pures du joueur~$i$, est continue pour la topologie naturelle induite par les cylindres.

L'ensemble de stratégies pures étant clairement compact pour la topologie naturelle, il est possible d'appliquer un théorème standard et d'en déduire l'existence d'un équilibre en stratégies mixtes. Le théorème de Kuhn (voir le texte sur les jeux répétés (ce volume)), nous permet ensuite de déduire l'existence d'un équilibre en stratégies de comportement.

Pour prouver l'existence d'un équilibre ayant des propriétés plus spécifiques (stationnaire ou markovien) il nous faut plus de structure dans les paiements. Les deux types de jeux qui vont suivre nous intéressent tout particulièrement du fait de leur récursivité et de l'intérêt qu'ils suscitent dans les applications.

\textit{Le jeu répété fini} $\Gamma_{T}$ dure $T$ étapes. Dans un tel jeu, on suppose que le paiement (moyen) du joueur~$i$ pour une partie $h_{\infty}=\left(\omega_{1},a_{1},\dots,\omega_{t},a_{t},\dots\right) \in H_{\infty}$ est
\begin{equation*}
g_{T}^{i}(h_{\infty})=\sum_{t=1}^{T}\frac{1}{T}\,g^{i}\left(\omega_{t},a_{t}\right).
\end{equation*}

Dans \textit{le jeu escompté} $\Gamma_{\lambda}$, avec $\lambda \in{}]0,1]$, on suppose que le paiement du joueur~$i$ est
\begin{equation*}
g_{\lambda}^{i}(h_{\infty})=\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^{i}(\omega_{t},a_{t}).
\end{equation*}

Il est facile de voir que ces deux jeux appartiennent à la famille des jeux compacts et donc admettent des équilibres en stratégies de comportement. Deux questions restent à résoudre: trouver des équilibres particuliers (stationnaires ou markoviens) mais aussi étudier le comportement asymptotique quand les joueurs sont de plus en plus patients ($T\to \infty $ ou $\lambda \to 0$).

Dans le cadre des jeux à deux joueurs et à somme nulle, on notera dans la suite $v_{T}(\omega_{1})$ (\resp $v_{\lambda}(\omega_{1})$) \textit{la valeur} du jeu fini $T$ fois (\resp du jeu $\lambda $-escompté).

\subsection{Approche uniforme}

Nous allons montrer dans le section Big-Match que l'unique stratégie optimale peut dépendre explicitement de la durée $T$ du jeu (respectivement du taux d'escompte $\lambda)$. On montrera aussi que la stratégie limite, quand $T\to \infty $ (\resp $\lambda \to 0)$ peut converger vers une mauvaise stratégie. Ceci justifie l'approche unifor\-me, dans laquelle on cherche des stratégies \textit{uniformément bonnes}: c'est-à-dire presque optimales pour tout jeu fini de durée~$T$ assez grande (\resp tout jeu escompté avec un taux d'escompte $\lambda $ assez \hbox{petit}).

Dans un jeu à somme nulle, on dit que la valeur uniforme $v(\omega_{1})$ existe si pour tout $\varepsilon >0$ il existe un profil de stratégies de comportement $(\sigma,\tau)\in \Sigma^{1}\times \Sigma^{2}$ et il existe $T\left(\varepsilon \right)$ tels que pour tout $T\geq T\left(\varepsilon \right)$,\vspace*{-3pt}\enlargethispage{1.2\baselineskip}
\begin{align}
\E_{\omega_{1},\sigma,\widetilde{\tau}}\bigg(\sum_{t=1}^{T}\frac{1}{T}\,g^{1}\left(\omega_{t},a_{t}\right) \bigg) &\geq v(\omega_{1})-\varepsilon&
\forall \widetilde{\tau}&\in \Sigma^{2},\label{eq:1}\\
\E_{\omega_{1},\widetilde{\sigma},\tau}\bigg(\sum_{t=1}^{T}\frac{1}{T}\,g^{2}\left(\omega_{t},a_{t}\right) \bigg) &\leq v(\omega_{1})+\varepsilon&
\forall \widetilde{\sigma}&\in \Sigma^{1}.\label{eq:2}
\end{align}
L'équation \eqref{eq:1} (\resp l'équation \eqref{eq:2}) sera interprétée: le joueur~1 (\resp 2) peut \textit{garantir uniformément} $v(\omega_{1})$.

La somme d'Abel pour une suite bornée de réels $\left\{ z_{t}\right\}_{t\in \naturals*}$ peut s'écrire comme une combinaison convexe infinie des sommes de Cesàro:\vspace*{-3pt}
\begin{gather*}
\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}z_{t}=\sum_{T=1}^{\infty}T\lambda^{2}(1-\lambda)^{T-1}\Big(\frac{1}{T}\sum_{t=1}^{T}z_{t}\Big).
\\[-3pt]
\tag*{avec}
\sum_{T=1}^{\infty}T\lambda^{2}(1-\lambda)^{T-1}=1.\vspace*{-5pt}
\end{gather*}
Ainsi, si la moyenne de Cesàro ($\lim_{T\to \infty}\frac{1}{T}\sum_{t=1}^{T}z_{t}$) existe, alors la moyenne d'Abel ($\lim_{\lambda \to 0}\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}z_{t}$) existe aussi.

Ceci implique en particulier que si la valeur uniforme existe, alors pour tout $\varepsilon >0$, il existe un profil de stratégies de comportement $(\sigma,\tau)\in \Sigma^{1}\times \Sigma^{2}$ et il existe $\lambda \left(\varepsilon \right)$ tels que pour tout $0<\lambda \leq \lambda \left(\varepsilon \right)$ et tout $(\widetilde{\sigma},\widetilde{\tau})\in \Sigma^{1}\times \Sigma^{2}$,\vspace*{-5pt}
\begin{align*}
\E_{\omega_{1},\sigma,\widetilde{\tau}}\bigg(\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^{1}(\omega_{t},a_{t})\bigg) &\geq v_{\infty}(\omega_{1})-\varepsilon,\\
\E_{\omega_{1},\widetilde{\sigma},\tau}\bigg(\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^{2}(\omega_{t},a_{t})\bigg) &\leq v_{\infty}(\omega_{1})+\varepsilon.
\end{align*}

Donc si la valeur uniforme existe, alors nous avons:\vspace*{-5pt}
\begin{equation*}
v=\lim_{\lambda \to 0}v_{\lambda}=\lim_{T\to \infty}v_{T}.
\end{equation*}

Pour la définition d'un équilibre uniforme en somme non nulle, consulter le texte sur les jeux répétés (ce volume). Cependant, même dans les jeux à somme nulle, un équilibre uniforme n'existe pas toujours --- par exemple dans le Big Match plus bas --- d'où le recours à la valeur dans le cas à somme nulle et à des paiements uniformes (les limites de paiements d'$\epsilon$-équilibres uniformes).\enlargethispage{\baselineskip}

La définition exacte de l'ensemble des paiements d'équilibres uniformes $E_0$ est similaire à celle de la valeur uniforme (voir Mertens, Sorin et Zamir, p\ptbl 403): on définit $E_{\epsilon}$ comme l'ensemble des paiements $v= (v^1,v^2,\dots)$ tels qu'on trouve un profil de stratégies et une date $T$ qui vérifient: dans tout jeu fini à au moins $T$ étapes, d'une part le paiement du joueur~$i$ est au moins $v^i-{\epsilon}$ et d'autre part en déviant, aucun des joueurs $i$ ne peut gagner plus que $v^ i + \epsilon$. Puis $E_0$ est l'intersection des $E_{\epsilon}$ pour $\epsilon >0$.

Dans la suite nous allons présenter plusieurs techniques proposées dans la littérature pour montrer l'existence et/ou la caractérisation de $\lim_{\lambda \to 0}v_{\lambda}$, ainsi que l'égalité entre $\lim_{\lambda \to 0}v_{\lambda}$ et $\lim_{T\to \infty}v_{T}$. Enfin, nous développerons la preuve difficile concernant l'existence de la valeur uniforme (valable seulement dans notre cadre où tous les ensembles sont finis et où les joueurs se rappellent de tout le passé, observent les états et les actions passées).

\subsection{Approche infinie}

Cette approche consiste à définir pour chaque joueur~$i$, une fonction mesurable et bornée par $M$, définie directement sur l'ensemble des parties $H_{\infty}$. Les exemples de l'approche compacte y sont inclus mais nous avons aussi les exemples suivants:

\begin{itemize}
\item
$\lim \inf_{T\to \infty}\sum_{t=1}^{T}\frac{1}{T}\,g^{i}\left(\omega_{t},a_{t}\right) $;

\item
$\lim \sup_{T\to \infty}\sum_{t=1}^{T}\frac{1}{T}\,g^{i}\left(\omega_{t},a_{t}\right) $;

\item
$\lim \inf_{\lambda \to 0}\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t}g^{i}(\omega_{t},a_{t})$;

\item
$\lim \sup_{\lambda \to 0}\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t}g^{i}(\omega_{t},a_{t})$.
\end{itemize}

D'après la relation précédente entre les sommes d'Abel et de Cesàro nous déduisons que\vspace*{-3pt}
\begin{equation*}
\lim_{T\to \infty}\inf \frac{1}{T}\sum_{t=1}^{T}z_{t}\leq \lim \inf_{\lambda \to 0}\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}z_{t}.
\end{equation*}
$\lim_{T\to \infty}\inf \frac{1}{T}\sum_{t=1}^{T}z_{t}$ est donc l'évaluation la plus pessimiste de la suite des paiements d'étapes des quatre: si un joueur garantit un montant pour cette évaluation, il en est de même pour les trois autres évaluations.

\section{Équilibre markovien}\label{sec:5}

\begin{theorem} \label{Theorem(Markov)}Tout jeu stochastique fini $\Gamma_{T}$ à $N$ joueurs admet un équilibre en stratégies markoviennes.
\end{theorem}

\begin{proof}
Nous montrons ce résultat par récurrence sur la longueur du jeu $T$. Pour cela nous utilisons un argument de programmation dynamique.

Sans perte de généralité, nous supposerons que les joueurs maximisent la somme des paiements d'étapes (au lieu de la somme divisée par la longueur du jeu $T$).

Pour $T=1$ c'est trivial.

Supposons que le résultat est vrai pour un jeu qui dure $T$ étapes.

Soit le jeu de longueur $T+1$ et d'état initial $\omega_{1}$. Quand les joueurs ont joué une fois, on arrive à un état $\omega_{2}$ et il reste à jouer $T$ étapes. En utilisant l'hypothèse de récurrence, nous sélectionnons pour chaque état futur possible $\omega_{2}$ un équilibre markovien dans le jeu qui dure~$T$ étapes. Chaque joueur décide alors de jouer, à partir de l'étape 2, l'équilibre markovien du jeu fini qui dure $T$ étapes.

Soit $f^{i}(\omega_{2})$ le paiement global d'un tel équilibre (en sommant les paiements d'étapes à partir de l'étape 2). Ainsi, à l'étape 1, on peut considérer que les joueurs font face au jeu statique suivant:
\begin{itemize}
\item
L'ensemble des joueurs est $N$;

\item
L'ensemble d'actions du joueur~$i$ est $A^{i}(\omega_{1})$;

\item
La fonction de paiement du joueur~$i$ est:
\begin{equation*}
r^{i}(\omega_{1},a)=g^{i}(\omega_{1},a)+\sum_{\omega_{2}\in \Omega}q(\omega_{1},a)(\omega_{2})f^{i}(\omega_{2}).
\end{equation*}
\end{itemize}

Ce jeu fini admet un équilibre en stratégies mixtes par application du théorème de Nash. Supposons alors que dans le jeu fini de $T+1$ étapes, les joueurs commencent par jouer un équilibre du jeu statique puis jouent l'équilibre markovien sélectionné dans le jeu fini qui dure~$T$ étapes. Ceci définit un équilibre markovien du jeu fini en $T+1$ étapes.
\end{proof}

\section{Équilibre stationnaire}\label{sec:6}

Shapley (1953), l'inventeur du modèle des jeux stochastiques, a montré l'existence de la valeur et des stratégies optimales stationnaires pour les jeux escomptés à deux joueurs et à somme nulle. Nous montrons ici le résultat de Fink (1964) et Takahashi (1964) qui généralisent Shapley aux jeux à $n$ joueurs.

On commence par proposer une méthodologie générale pour calculer explicitement le paiement $\lambda $-escompté $g_{\lambda}^{i}(\omega,x)$ pour un profil de stratégies stationnaires $x=(x^{i})_{i\in N}$.

\begin{proposition} \label{PropCalculG_lambda}
$\left\{ g_{\lambda}^{i}(\omega,x)\right\}_{\omega \in \Omega}$ est l'unique solution au système liné\-aire de $\left| \Omega \right| $-équations:
\[
g_{\lambda}^{i}(\omega,x)\!
=\!\sum_{a\in A\left(\omega \right)}\hspace*{-2mm}\Big(\prod_{i\in N}x^{i}(a^{i})\Big) \biggl(
\begin{array}{c} \lambda g^{i}(\omega,a)\\
+\left(1-\lambda \right) \sum_{\omega'\in \Omega}q(\omega,a)(\omega')g_{\lambda}^{i}(\omega',x)
\end{array}\biggr).
\]
\end{proposition}

\begin{proof} Puisque les joueurs jouent des stratégies stationnaires, l'espérance de paiement dépend seulement de l'état courant. Donc $\left\{ g_{\lambda}^{i}(\omega,x)\right\}_{\omega \in \Omega}$ satisfait nécessairement ce système d'équations. Pour montrer que c'est l'unique solution, nous utilisons un principe de maximum. Supposons qu'il y ait deux solutions, $\left\{ \alpha (\omega)\right\}_{\omega \in \Omega}$ et $\left\{ \beta (\omega)\right\}_{\omega \in \Omega}$, au système. Soit
\begin{equation*}
\omega_{0}\in \arg \max_{\omega \in \Omega}\alpha (\omega)-\beta (\omega),
\end{equation*}
et supposons sans perte de généralité que
\begin{equation*}
\alpha (\omega_{0})-\beta (\omega_{0})=k\geq 0.
\end{equation*}
Alors,
\begin{align*}
k &=\alpha (\omega_{0})-\beta (\omega_{0})\\
&=\sum_{a\in A\left(\omega_{0}\right)}\Big(\prod_{i\in N}x^{i}(a^{i})\Big) \Big(\left(1-\lambda \right) \sum_{\omega'\in \Omega}q(\omega_{0},a)(\omega')\Big) \left(\alpha (\omega')-\beta (\omega')\right)\\
&\leq (1-\lambda)k.
\end{align*}
D'où $k=0$.
\end{proof}

Nous en déduisons les propriétés suivantes.

\begin{proposition} \label{proposition(continuite)}
Pour tout joueur~$i$ et tout état initial $\omega $, la fonction $\left(\lambda,x\right) \mto g_{\lambda}^{i}(\omega,x)$ est continue et une fraction rationnelle en $\lambda $.
\end{proposition}

\begin{proof} Puisque le système est linéaire en $\lambda $, la solution est nécessairement une fraction rationnelle en $\lambda $. La continuité découle du fait que le système linéaire admet une unique solution.
\end{proof}

Nous allons maintenant utiliser la continuité pour montrer que le jeu $\Gamma_{\lambda}$ admet une stationnarité qui permet l'existence d'un équilibre stationnaire. Pour cela, on définit une famille de jeux auxiliaires statiques similaire à celle de la section précédente. Pour chaque $\left| N\right|$-uplet de fonctions $f^{1},\dots,f^{\left| N\right|}$ de $\Omega \to \mathbb{R}$ bornées par $M$ et chaque $\omega_{1}\in \Omega $, on considère un jeu en un coup $G_{\omega_{1}}(f^{1},\dots,f^{\left| N\right|})$ défini comme suit:
\begin{itemize}
\item
l'ensemble des joueurs est $N$;

\item
l'ensemble d'actions du joueur~$i$ est $A^{i}(\omega)$;

\item
la fonction de paiement du joueur~$i$ est:
\begin{equation*}
r^{i}(\omega_{1},a)=\lambda g^{i}(\omega_{1},a)+(1-\lambda)\sum_{\omega_{2}\in \Omega}q(\omega_{1},a)(\omega_{2})f^{i}(\omega_{2}).
\end{equation*}
\end{itemize}

\begin{theorem}[Fink (1964), Takahashi (1964)]
Tout jeu stochastique escompté à $N$ joueurs admet un équilibre en stratégies stationnaires.
\end{theorem}

\skpt
\begin{proof}
\textit{Étape 1}: nous appliquons le théorème de Kakutani. Considérons l'ensemble
\begin{equation*}
XF:=\prod_{i\in N}\prod_{\omega \in \Omega}\Delta \left(A^{i}\left(\omega \right) \right) \times \left[ -M,M\right]^{\left| N\right| \times \left| \Omega \right|}.
\end{equation*}
C'est un convexe compact d'un espace euclidien de dimension finie.

Un élément de $XF$ sera noté
\begin{equation*}
(x,f)=\left(\left\{ x^{i}(\omega)\right\}_{\omega \in \Omega}^{i\in N},\left\{ f^{i}(\omega)\right\}_{\omega \in \Omega}^{i\in N}\right).
\end{equation*}
$x^{i}(\omega)$ doit être interprétée comme la stratégie jouée par le joueur~$i$ si l'état aujourd'hui est $\omega $ et $f^{i}(\omega)$ comme étant le paiement de continuation du joueur~$i$ si le nouvel état est $\omega $.

Nous allons définir une correspondance $W:XF\to XF$ comme suit. Si les coordonnées de $W$ sont notées
\begin{equation*}
W=\left(W_{X}^{i,\omega},W_{F}^{i,\omega}\right)_{\omega \in \Omega}^{i\in N},
\end{equation*}
alors
\begin{multline*}
W_{X}^{i,\omega}(x,f)\\
=\arg \max_{y^{i}\in \Delta (A^{i}(\omega))}\left\{
\begin{array}{c} \lambda g^{i}(\omega,y^{i},x^{-i}\left(\omega \right))\\
+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,y^{i},x^{-i}\left(\omega \right))(\omega')f^{i}(\omega')
\end{array}
\right\},
\end{multline*}
et
\begin{equation*}
W_{F}^{i,\omega}(x,f)=\lambda g^{i}(\omega,x\left(\omega \right))+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,x)(\omega')f^{i}(\omega').
\end{equation*}
où la notation $(y^{i},x^{-i})$ veut dire que le joueur $i$ utilise la stratégie stationnaire $y^{i}$ et les autres joueurs le profil $x^{-i}$. La motivation est la suivante. Considérons le jeu en un coup $G_{\omega}(f^{1},\dots,f^{\left| N\right|})$. Alors, $W_{F}^{i,\omega}(x,f)$ est le paiement espéré du joueur~$i$ si les joueurs utilisent le profil de stratégies stationnaires $x$ et $W_{X}^{i,\omega}(x,f)$ est l'ensemble de toutes les meilleures réponses possibles du joueur~$i$ face à $x^{-i}$.

Il est facile de vérifier que cette correspondance satisfait aux hypothèses du théorème de Kakutani (pour la semi-continuité supérieure, on utilise la propriété de continuité dans la proposition \ref{proposition(continuite)}). Nous concluons alors à l'existence d'un point fixe que nous notons $(x,f)$.

\textit{Étape 2}: nous montrons que $g_{\lambda}^{i}(\omega,x)=f^{i}(\omega)$.

Ceci résulte de la proposition \ref{PropCalculG_lambda}. En effet, puisque $(x,f)$ est un point fixe de $W$, nous avons que pour tout $i$ et tout $\omega$:
\begin{equation*}
f^{i}(\omega)=\lambda g^{i}(\omega,x(\omega))+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,x\left(\omega \right))(\omega')f^{i}(\omega').
\end{equation*}

\textit{Étape 3}: nous prouvons que pour toute stratégie $\sigma^{i}$ du joueur~$i$, $g_{\lambda}^{i}(\omega,\sigma^{i},x^{-i})\leq g_{\lambda}^{i}(\omega,x)$.

Par définition de $F$, nous avons que pour tout $\omega $, $x^{i}(\omega)$ est une meil\-leure réponse du joueur~$i$ contre $x^{-i}\left(\omega \right)$ dans le jeu $G_{\omega}(f^{1},\dots,f^{\left| N\right|})$. D'où, pour tout $\omega $ et tout $y^{i}(\omega)\in \Delta \left(A^{i}(\omega)\right)$,
\begin{align*}
\lambda g^{i}(\omega,&y^{i},x^{-i}\left(\omega \right))+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,y^{i},x^{-i}\left(\omega \right))(\omega')f^{i}(\omega')\\
&\leq \lambda g^{i}(\omega,x(\omega))+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,x\left(\omega \right))(\omega')f^{i}(\omega')\\
&=f^{i}(\omega)=g_{\lambda}^{i}(\omega,x).
\end{align*}
Soit $h_{t}=\left(\omega_{1},a_{1},\dots,\omega_{t-1},a_{t-1},\omega_{t}\right)$ une histoire partielle de durée~$t$ et soit $\sigma^{i}$ une stratégie quelconque du joueur~$i$ (qui peut dépendre de toute l'histoire du jeu). La dernière inégalité permet alors de déduire que:
\begin{multline*}
\E_{\omega_{1},\sigma^{i},x^{-i}}\bigg(
\begin{array}{l} \lambda g^{i}(\omega_{t},\sigma^{i}(h_{t}),x^{-i}\left(\omega_{t}\right))\\
+(1-\lambda)\hspace*{-2mm}\sum\limits_{\omega_{t+1}\in \Omega}\hspace*{-2mm}q(\omega_{t},\sigma^{i}(h_{t}),x^{-i}\left(\omega_{t}\right))(\omega_{t+1})g_{\lambda}^{i}(\omega_{t+1},x)\left| h_{t}\right.
\end{array}\bigg)\\
\leq g_{\lambda}^{i}(\omega_{t},x).
\end{multline*}
Ceci implique, après une sommation, que
\begin{align*}
g_{\lambda}^{i}(\omega_{1},\sigma^{i},x^{-i}) &=\E_{\omega_{1},\sigma^{i},x^{-i}}\bigg(\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^{i}(\omega_{t},a_{t})\bigg)\\
&\leq g_{\lambda}^{i}(\omega_{1},x).
\end{align*}
Nous avons donc bien un équilibre de Nash stationnaire.
\end{proof}

\section{Opérateur de Shapley}\label{sec:7}

À partir de maintenant et sauf mention explicite, nous nous focaliserons sur les jeux à deux joueurs et à somme nulle.

Puisque l'état du jeu est connu des deux joueurs, chaque joueur peut écrire le principe de programmation dynamique pour calculer sa stratégie optimale. En fait, $v_{\lambda}$ et $v_{T}$ peuvent être calculés à l'aide d'un même opérateur appelé l'opérateur de Shapley. Celui-ci étend le principe de programmation dynamique de Bellman. Ce principe a été publié par Shapley avant et indépendamment de Bellman. De plus Shapley traite le cas de deux joueurs alors que Bellman considère seulement celui d'un seul joueur.

L'opérateur de Shapley n'est autre que l'opérateur valeur pour un jeu statique, similaire à celui introduit dans la preuve du théorème \ref{Theorem(Markov)}. Pour chaque état possible $\omega_{1}$ et chaque fonction $f:\Omega \to \mathbb{R}$ bornée par $M$, on introduit le jeu statique suivant à deux joueurs et à somme nulle:
\begin{itemize}
\item
l'ensemble de stratégies pures du joueur $1$ est $A^{1}(\omega_{1})$;

\item
l'ensemble de stratégies pures du joueur $2$ est $A^{2}(\omega_{1})$;

\item
la fonction de paiement du joueur $1$ est:
\begin{equation*}
r^{1}(a,\omega_{1})=g^{1}(a,\omega_{1})+\sum_{\omega_{2}\in \Omega}q(\omega_{1},a)(\omega_{2})f(\omega_{2}).
\end{equation*}
Ce jeu admet une valeur en stratégies mixtes, noté $\Psi \left(f\right) (\omega_{1})$. L'opérateur de Shapley $\Psi $ est défini sur l'espace $\mathcal{F}$ des fonctions $f:\Omega \to \mathbb{R}$ qui sont bornées par $M$.
\end{itemize}

Pour tout $\lambda \in{}]0,1[$ nous définissons l'opérateur $\Phi $ comme suit:
\begin{equation*}
\Phi \left(\lambda,f\right) =\lambda \Psi \Big(\frac{1-\lambda}{\lambda}f\Big).
\end{equation*}
$\Phi \left(\lambda,f\right) \left(\omega_{1}\right)$ correspond à la valeur en stratégies mixtes du jeu statique ayant comme paiement:
\begin{equation*}
\lambda g^{1}(a,\omega_{1})+\left(1-\lambda \right) \sum_{\omega_{2}\in \Omega}q(\omega_{1},a)(\omega_{2})f(\omega_{2}).
\end{equation*}
L'analyse de la section précédente montre le résultat suivant.

\begin{theorem} \label{TheoremeFormuleRecurrence}$v_{\lambda}$ est l'unique élément de $\mathcal{F}$ qui vérifie
\begin{equation*}
v_{\lambda}=\Phi \left(\lambda,v_{\lambda}\right).
\end{equation*}
La suite $\left\{ v_{T}\right\}_{T\in \naturals^*}$\ est l'unique suite dans $\mathcal{F}$ solution de:
\begin{align*}
v_{T+1}&=\Phi \Big(\frac{1}{T+1},v_{T}\Big);\\
v_{0}&=0.
\end{align*}
\end{theorem}

Il est facile de voir que l'opérateur $\Phi \left(\lambda,\cdot \right)$ est contractant et donc admet un unique point fixe. Nous n'avons donc pas besoin d'utiliser le théorème de point fixe de Kakutani pour l'existence de $v_{\lambda}$ ou de $v_{T}$ mais seulement du théorème du minmax pour montrer que $\Phi $ est bien défini, et de l'argument de contraction de Picard.

Remarquons que dans $\Gamma_{\lambda}$ et $\Gamma_{T}$, les joueurs ont une stratégie optimale markovienne et n'ont donc besoin d'observer que l'état courant pour bien jouer. Nous allons voir que, pour bien jouer uniformément, il est nécessaire que les joueurs observent leurs paiements. Sans cette observabilité, la valeur uniforme n'existerait pas. Ceci montre une différence fondamentale et intuitive entre l'approche compacte et l'approche uniforme: pour bien jouer uniformément, un joueur joue d'une manière élaborée.

Nous nous intéressons à l'étude de $v_{\lambda}$ et $v_{T}$ quand les joueurs sont de plus en plus patients ($\lambda \to 0$ et $T\to \infty $) et à la caractérisation de leur limite si possible. Nous allons commencer par un cas (plus) simple: celui des jeux absorbants.

\section{Jeux absorbants}\label{sec:8}

Dans cette section nous étudions une classe de jeu, introduite formellement par Kohlberg (1974) et qui va nous servir pour illustrer certains des résultats exposés et expliquer une partie des difficultés qui peuvent être rencontrées dans les jeux stochastiques.

Un état $\omega \in \Omega $ est dit absorbant si, une fois atteint, les joueurs ne peuvent jamais en sortir. Mathématiquement, cela veut dire que pour tout profil $a\in A(\omega)$, on a $q\left(\omega,a\right) (\omega)=1$. Un jeu est absorbant s'il admet seulement un unique état non absorbant.

Une fois qu'un état absorbant est atteint, le jeu est réduit à un jeu répété à information parfaite (déjà analysé dans le premier texte de ce volume). Nous savons alors que, partant d'un tel état, un équilibre existe. Si nous nous intéressons à l'analyse des équilibres, on peut supposer, sans perte de généralité, qu'une fois qu'un état absorbant est atteint, la suite des paiements est constante et égale à un paiement d'équilibre (que nous avons préalablement sélectionné dans le jeu répété).

En résumé, on va supposer dans toute la suite et sans perte de généralité, qu'à tout état absorbant dans un jeu stochastique est associé un paiement absorbant (un paiement d'étape que les joueurs reçoivent à toutes les étapes suivantes du jeu). Nous supposerons que l'état initial $\omega_{1}$ d'un jeu absorbant est l'état non absorbant (sinon le jeu serait trivial et sans enjeu). Dès que l'on quitte cet état, le jeu est essentiellement terminé (il n'y a plus de difficulté mathématique liée à l'aspect stochastique). Il n'est donc plus nécessaire de spécifier l'état de départ dans un jeu absorbant.

Ainsi, un jeu absorbant à somme nulle peut être décrit d'une manière compacte comme suit. Il y a deux joueurs, 1 et 2. Le jeu est donné par deux ensembles finis d'actions, $A^{1}$ pour le joueur~1 et $A^{2}$ pour le joueur~2. Nous avons par ailleurs besoin de deux fonctions de paiements $\widetilde{g}:A^{1}\times A^{2}\to \mathbb{R}$ et $g^{\ast}:A^{1}\times A^{2}\to \mathbb{R}$. Enfin, nous avons besoin d'une famille de probabilités de transition $p^{\ast}:A^{1}\times A^{2}\to \lbrack 0,1]$. Le jeu est joué comme suit. À l'étape $t=1,2,\dots,$ le joueur~1 choisit une action $a_{t}^{1}\in A^{1}$ et simultanément le joueur~2 une action $a_{t}^{2}\in A^{2}$, puis
\begin{enumeratei}
\item
avec probabilité $p^{\ast}\left(a_{t}^{1},a_{t}^{2}\right)$ le jeu est absorbé et le joueur~1\ reçoit le paiement $g^{\ast}\left(a_{t}^{1},a_{t}^{2}\right)$ à chacune des étapes restantes.

\item
avec probabilité $1-p^{\ast}\left(a_{t}^{1},a_{t}^{2}\right) =
\widetilde{p}\left(a_{t}^{1},a_{t}^{2}\right)$ le jeu n'est pas absorbé et le paiement de l'étape $t$ du joueur~1 est $\widetilde{g}\left(a_{t}^{1},a_{t}^{2}\right)$.
\end{enumeratei}

\subsubsection*{Exemple d'un jeu d'arrêt}
Soit le jeu absorbant suivant à deux joueurs et à somme nulle.
\begin{equation*}
\begin{tabular}{ccc} & C & A\\
\cline{2-3} C & \multicolumn{1}{|c}{0} & \multicolumn{1}{|c|}{1$^{\ast}$}\\
\cline{2-3} A & \multicolumn{1}{|c}{1$^{\ast}$} & \multicolumn{1}{|c|}{0$^{\ast}$}\\
\cline{2-3}
\end{tabular}
\end{equation*}
Dans ce jeu, il y a deux paiements absorbants: $1$ et $0$ (ils sont marqués par $\ast $). Le paiement absorbant $1^{\ast}$ est atteint si un des profils d'actions (A,C) ou (C,A) est joué (et dans ce cas le joueur gagne $1$ par étape, et ce jusqu'à la fin des temps, et le joueur~2 gagne l'opposé, soit $-1$). Le paiement absorbant $0^{\ast}$ est atteint si (A,A) est joué. Le jeu reste dans l'état non absorbant si et seulement si les joueurs jouent (C,C) (c'est la seule case de la matrice sans $\ast $).

Dans un \textit{jeu d'arrêt} général chaque joueur a deux options: A (arrê\-ter) ou C (continuer). Dès qu'un joueur choisit A, le jeu est absorbé (s'arrête) et tant que le jeu continue les joueurs reçoivent un paiement de $0$ par étape.

Considérons le profil suivant de stratégies stationnaires dans l'exemple du jeu d'arrêt: le joueur~1 joue $(xH,(1-x)B)$ et le joueur~2 joue $(yG,(1-y)D)$. Calculons maintenant le paiement du joueur~1 $g_{\lambda}(x,y)$ dans le jeu escompté $\Gamma_{\lambda}$:
\begin{equation*}
g_{\lambda}(x,y)=xy\left(\lambda \times 0+\left(1-\lambda \right) g_{\lambda}(x,y)\right) +\left((1-x)y+(1-y)x\right),
\end{equation*}
d'où
\begin{equation*}
g_{\lambda}(x,y)=\frac{x+y-2xy}{1-xy(1-\lambda)}.
\end{equation*}
Dans cet exemple, la valeur $v_{\lambda}\in \left[ 0,1\right] $ satisfait:
\begin{eqnarray*} v_{\lambda} &=&\text{valeur}\left(
\begin{tabular}{ccc} & C & A\\
\cline{2-3} C & \multicolumn{1}{|c}{$(1-\lambda)v_{\lambda}$} & \multicolumn{1}{|c|}{1}\\
\cline{2-3} A & \multicolumn{1}{|c}{1} & \multicolumn{1}{|c|}{0}\\
\cline{2-3}
\end{tabular}
\right)\\
&=&\max_{x\in \left[ 0,1\right]}\min_{y\in \left[ 0,1\right]}\left[ xy(1-\lambda)v_{\lambda}+x(1-y)+y(1-x)\right]\\
&=&\min_{y\in \left[ 0,1\right]}\max_{x\in \left[ 0,1\right]}\left[ xy(1-\lambda)v_{\lambda}+x(1-y)+y(1-x)\right].
\end{eqnarray*}
On vérifie alors que les joueurs n'ont pas de stratégies optimales pures. Si $x_{\lambda}\in{}]0,1[$ (\resp $y_{\lambda}\in{}]0,1[)$ est la stratégie optimale du joueur~1 (\resp du joueur~2) alors, en utilisant le fait que chaque joueur est indifférent entre ces deux actions (les deux ont la même espérance de paiement) nous trouvons que:
\begin{equation*}
v_{\lambda}=x_{\lambda}(1-\lambda)v_{\lambda}+\left(1-x_{\lambda}\right) =x_{\lambda}=y_{\lambda}.
\end{equation*}
Donc il existe des stratégies optimales uniques, elles sont stationnaires et l'on a:
\begin{equation*}
v_{\lambda}=x_{\lambda}=y_{\lambda}=\frac{1-\sqrt{\lambda}}{1-\lambda}.
\end{equation*}
Remarquons que $v_{\lambda}$ n'est pas une fraction rationnelle de $\lambda $. Ceci est une différence fondamentale avec les jeux à un seul joueur (programmation dynamique). Dans le cas d'un joueur, il existe toujours une stratégie optimale qui est stationnaire et pure pour tout $\lambda $. Ceci implique en particulier que $v_{\lambda}$ est une fraction rationnelle de $\lambda $ (car c'est un maximum sur un ensemble fini de fonctions rationnelles en $\lambda $) mais aussi qu'il existe un $\lambda_{0}>0$ et une même stratégie pure qui est optimale pour tout $\lambda <\lambda_{0}$ (une stratégie uniformément bonne, Blackwell (1962)). Enfin, si le jeu d'arrêt se jouait en temps continu (escompté ou non), le joueur~1 pourrait arrêter seul le jeu avec probabilité 1 et garantir ainsi un paiement proche de $1$: il lui suffit de tirer un instant uniformément entre le début du jeu et un temps très proche du début et d'arrêter le jeu à cet instant. Ceci montre une différence fondamentale entre le comportement optimal en temps discret et celui en temps continu. En effet, en temps discret, le joueur~1 ne peut garantir d'arrêter le jeu seul.

Dans cet exemple, $\lim v_{\lambda}$ existe et est égale à $1$. Dans la section suivante nous allons montrer, par l'utilisation d'une approche semi-algébrique, que la valeur asymptotique existe pour tout jeu stochastique à somme nulle. Dans le cas des jeux absorbants, la convergence peut être démontrée plus simplement, en utilisant une approche variationnelle (Laraki 2006). La méthode s'inspire de l'utilisation des solutions de viscosité pour montrer l'existence et la caractérisation de la valeur dans les jeux différentiels à somme nulle et découle d'une méthodologie plus générale (voir Laraki 2001, 2002). Cette approche dans les jeux absorbants permet une caractérisation explicite de $\lim v_{\lambda}$ comme la valeur d'un jeu.

Nous avons besoin des \emph{notations suivantes spécifiques à cette section}:\enlargethispage{\baselineskip}
\begin{itemize}
\item
$\mathbb{R}_{+}^{A^{1}}=\{z=(z_{a^{1}})_{a^{1}\in A^{1}}\mid z_{a^{1}}\in \mathbb{R}_{+}\}$ est l'orthant positif associé à l'ensemble fini d'actions du joueur~1 $A^{1}$ (qu'on peut identifier à l'ensemble des mesures positives sur $A^{1}$).

\item
Pour $z\in \mathbb{R}_{+}^{A^{1}}$, $x\in \Delta (A^{1})$ et $a^{2}\in A^{2}$,

\begin{itemize}
\item
$x_{a^{1}}$ est la probabilité avec laquelle le joueur~1 joue l'action~$a^{1}$.

\item
$\widetilde{g}(x,a^{2})=\sum_{a^{1}\in A^{1}}x_{a^{1}}(1-p^{\ast}(a^{1},a^{2}))\widetilde{g}(a^{1},a^{2})$ est le paiement non absorbant d'étape si le joueur~1 joue $x$ et le joueur~2 joue $j$;

\item
$g^{\ast}(z,a^{2})=\sum_{a^{1}\in A^{1}}z_{a^{1}}p^{\ast}(a^{1},a^{2})g^{\ast}(a^{1},a^{1})$ est l'extension linéaire de $\widetilde{g}(\cdot,a^{2})$ à $\mathbb{R}_{+}^{A^{1}}$;

\item
$p^{\ast}(z,a^{2})=\sum_{a^{1}\in A^{1}}z_{a^{1}}p^{\ast}\left(a^{1},a^{2}\right)$ est la probabilité d'absorption étendue linéairement à $\mathbb{R}_{+}^{A^{1}}$;

\item
$\widetilde{p}(x,a^{2})=1-p^{\ast}(x,a^{2})$ est la probabilité de continuation.
\end{itemize}
\end{itemize}

L'opérateur de Shapley implique que $v_{\lambda}$ existe et est l'unique réel dans $\left[ -M,+M\right] $ qui satisfait
\begin{equation}\label{AbsorbantShapley}
v_{\lambda}=\max_{x\in \Delta (A^{1})}\min_{a^{2}\in A^{2}}\left[ \lambda \widetilde{g}(x,a^{2})+\left(1-\lambda \right) \widetilde{p} (x,a^{2})v_{\lambda}+g^{\ast}(x,a^{2})\right].
\end{equation}

\begin{proposition} \label{Main}
$v_{\lambda}$ converge vers $v$ quand $\lambda $ tend vers zéro, où $v$ est donné par la formule suivante:
\begin{equation*}
v=\sup_{z\in \mathbb{R}_{+}^{A^{1}}}\sup_{x\in \Delta (A^{1})}\min_{a^{2}\in A^{2}}\left(
\begin{array}{c} \frac{g^{\ast}(x,a^{2})}{p^{\ast}(x,a^{2})}1_{\left\{ p^{\ast}(x,a^{2})>0\right\}}\\
+\frac{\widetilde{g}(x,a^{2})+g^{\ast}(z,a^{2})}{\widetilde{p} (x,a^{2})+p^{\ast}(z,a^{2})}1_{\left\{ p^{\ast}(x,a^{2})=0\right\}}
\end{array}
\right).
\end{equation*}
\end{proposition}

\begin{proof} Soit $w$ un point d'accumulation de $v_{\lambda}$ quand $\lambda $ tend vers zéro: $w=\lim_{n\to \infty}v_{\lambda_{n}}$ où $\lambda_{n}\to 0$.

\textit{Étape 1}: nous allons montrer que $w\leq v$. L'idée est de considérer une stratégie stationnaire optimale $x\left(\lambda_{n}\right)$ pour le joueur~1 puis d'aller à la limite dans l'opérateur de Shapley. Ce procédé est bien connu dans la théorie du contrôle optimal.

De (\ref{AbsorbantShapley}), nous déduisons qu'il existe $x\left(\lambda_{n}\right) \in \Delta (A^{2})$ tel que,
\begin{equation*}
v_{\lambda_{n}}=\min_{a^{2}\in A^{2}}\left[
\begin{array}{c} \lambda_{n}\widetilde{g}(x(\lambda_{n}),a^{2})+\left(1-\lambda_{n}\right) \widetilde{p}(x(\lambda_{n}),a^{2})v_{\lambda_{n}}\\
+g^{\ast}(x(\lambda_{n}),a^{2})
\end{array}
\right].
\end{equation*}
D'où, pour tout $a^{2}\in A^{2}$,
\begin{equation} v_{\lambda_{n}}\leq \frac{\lambda_{n}\widetilde{g}(x(\lambda_{n}),a^{2})+g^{\ast}(x(\lambda_{n}),a^{2})}{\lambda_{n}\widetilde{p}(x(\lambda_{n}),a^{2})+p^{\ast}(x(\lambda_{n}),a^{2})}. \label{2}
\end{equation}
Par compacité de $\Delta (A^{1})$, et en considérant si nécessaire une sous-suite de $\left\{ \lambda_{n}\right\} $, on peut supposer sans perte de généralité que $x\left(\lambda_{n}\right) \to x\in \Delta (A^{1})$.

Si $p^{\ast}(x,a^{2})>0$, alors en faisant tendre $\lambda_{n}$ vers zéro, on trouve que:
\begin{equation*}
w=\lim v\left(\lambda_{n}\right) \leq \frac{g^{\ast}(x,a^{2})}{p^{\ast}(x,a^{2})}.
\end{equation*}
Supposons maintenant que $p^{\ast}(x,a^{2})=\sum_{a^{1}\in A^{1}}x_{a^{1}}p^{\ast}(a^{1},a^{2})=0$, et donc que pour tout $a^{1}$ tel que $x_{a^{1}}>0$, nous avons $p^{\ast}(a^{1},a^{2})=0$. Soit alors $z(\lambda_{n})=\left(\sfrac{x_{a^{1}}\left(\lambda_{n}\right)}{\lambda_{n}}\right)_{a^{1}\in A^{1}}\in \mathbb{R}_{+}^{A^{1}}$. L'équation (\ref{2}) devient, après la division par $\lambda_{n}$,
\begin{eqnarray*} v\left(\lambda_{n}\right) &\leq &\frac{\widetilde{g}(x(\lambda_{n}),a^{2})+g^{\ast}(z(\lambda_{n}),a^{2})}{\widetilde{p}(x(\lambda_{n}),a^{2})+p^{\ast}(z(\lambda_{n}),a^{2})}\\
&\triangleq &r(\lambda_{n},a^{2}).
\end{eqnarray*}
Puisque $A^{2}$ est fini, en considérant si nécessaire une sous-suite de $\left\{ \lambda_{n}\right\} $, on peut supposer\ que $r\left(\lambda_{n},a^{2}\right)$ converge pour tout~$a^{2}$. Puisque $\widetilde{p}(x,a^{2})\!=\!\lim_{n\to \infty}\widetilde{p}(x(\lambda_{n}),a^{2})\!=\!1$ et $\widetilde{g}(x,a^{2})\!=\!\lim_{n\to \infty}\widetilde{g}(x(\lambda_{n}),a^{2})$, on en déduit que
\begin{equation*}
w\leq \lim_{n\to \infty}\frac{\widetilde{g}(x,a^{2})+g^{\ast}(z(\lambda_{n}),a^{2})}{\widetilde{p}(x,a^{2})+p^{\ast}(z(\lambda_{n}),a^{2})}.
\end{equation*}
Soit $\varepsilon >0$. Puisque $A^{2}$ est fini, on en déduit l'existence d'un entier $N(\varepsilon)$ tel que, pour tout $a^{2}\in A^{2}$,

\begin{itemize}
\item
si $p^{\ast}(x,a^{2})>0$ alors $w\leq \dfrac{g^{\ast}(x,a^{2})}{p^{\ast}(x,a^{2})}$.

\item
si $p^{\ast}(x,a^{2})=0$ alors $w\leq \dfrac{\widetilde{g}(x,a^{2})+g^{\ast}(z(\lambda_{N(\varepsilon)}),a^{2})}{\widetilde{p}(x,a^{2})+p^{\ast}(z(\lambda_{N(\varepsilon)}),a^{2})}+\varepsilon $.
\end{itemize}

En conséquence, $w\leq v$.

\textit{Étape 2}: nous montrons que $w\geq v$. L'idée est de construire une stratégie du joueur~1 dans le jeu $\lambda_{n}$-escompté qui lui garantit approximativement $v$.

Rappelons que $\lambda_{n}$ converge vers 0, et que $w=\lim v_{\lambda_{n}} $.

Soit $(z,x)\in \mathbb{R}_{+}^{A^{1}}\times \Delta (A^{1})$ $\varepsilon $-optimal pour le joueur~1 dans l'expression de $v$. Supposons que $\lambda_{n}$ soit assez petit. Soit
$$
A^{1}(x):=\{a^{1}\in A^{1}\mid x_{a^{1}}=0\}
$$
et définissons $x(\lambda_{n})\in \Delta (A^{1})$ comme suit:
\begin{itemize}
\item
si $A^{1}(x)=\emptyset $ alors $x(\lambda_{n})=x$.

\item
si $a^{1}\in A^{1}(x)$ alors $x_{a^{1}}(\lambda_{n})=z_{a^{1}}\times \lambda_{n}$.

\item
si $a^{1}\!\notin\! A^{1}(x)$ et $A^{1}(x)\!\neq\! \emptyset $ alors $x_{a^{1}}(\lambda_{n})\!=\!x_{a^{1}}-\dfrac{\sum_{a^{1}\in A^{1}(x)}z_{a^{1}}}{\left| A^{1}(x)\right|}\lambda_{n}$.
\end{itemize}

Ainsi, nous avons $v(\lambda_{n})\geq r(\lambda_{n})-\varepsilon $, où $r(\lambda_{n})$ est l'unique réel dans $\left[ -M,M\right] $ qui satisfait,
\begin{equation} r(\lambda_{n})=\min_{a^{2}\in A^{2}}\left[
\begin{array}{l} \lambda_{n}\left[ \widetilde{g}(x(\lambda_{n}),a^{2})\right]\\
{}+\left(1-\lambda_{n}\right) \left(\widetilde{p}(x(\lambda_{n}),a^{2})\right) r\left(\lambda_{n}\right)\\
{}+g^{\ast}(x(\lambda_{n}),a^{2})
\end{array}
\right]. \label{3}
\end{equation}
En effet, $r(\lambda_{n})$ est ce que le joueur~1 s'assure de gagner dans le jeu $\lambda_{n}$-escompté s'il joue la stratégie stationnaire $x(\lambda_{n})$. Soit $a_{\lambda_{n}}^{2}\in A^{2}$ une stratégie optimale stationnaire pure pour le joueur~2 contre $x(\lambda_{n})$ dans le jeu $\lambda_{n}$-escompté (un élément du $\arg \min $\ dans (\ref{3})). Puisque la suite $(a_{\lambda_{n}}^{2})_{n\geq 1}$ appartient à un ensemble fini $A^{2}$, il y a un nombre fini de sous-suites de $\left\{ \lambda_{n}\right\} $ pour lesquelles $a_{\lambda_{n}}^{2}$ est constant pour $n$ grand. Pour chacune de ces sous-suites, (que l'on continuera à appeler $\lambda_{n}$) on peut supposer que $r(\lambda_{n})$ converge vers un certain $r$. En reprenant exactement le calcul de l'étape 1, nous en déduisons que $w\geq v-\varepsilon $ pour tout $\varepsilon >0$.
\end{proof}

Remarquez qu'on aurait pu obtenir une autre formule en considérant dans la preuve une stratégie optimale du joueur~2 (au lieu du joueur~1).

Coulomb (2001), obtient une formule explicite pour le maxmin uniforme des jeux absorbants avec signaux. Si l'on suppose l'observation parfaite des actions et en utilisant le fait que dans ce cas le maxmin uniforme coïncide avec la valeur uniforme et donc avec $\lim v_{\lambda}$, nous aboutissons à une autre formule pour $\lim v_{\lambda}$.

Cette analyse variationnelle et la formule qui en résulte peuvent être étendues aux cas où les ensembles d'actions sont compacts et les fonctions $\widetilde{g}$, $g^{\ast}$ et $p^{\ast}$ continues. Ceci ne peut être fait dans le cadre de Coulomb (2001) qui utilise une approche semi-algébrique. Cependant, Coulomb étudie le cas uniforme qui nécessite des outils plus complexes et des stratégies plus élaborées...

\section{Approche semi-algébrique}\label{sec:9}

Ici, nous montrons l'existence de $\lim_{\lambda \to 0}v_{\lambda}$ pour tout jeu stochastique à somme nulle en utilisant une approche semi-algébrique, initiée par Bewley et Kohlberg (1976 a et b). Cela permet de montrer en particulier que $v_{\lambda}$ est à variation bornée. Cette propriété impliquera que $\lim_{T\to \infty}v_{T}$ existe et est égale à $\lim_{\lambda \to 0}v_{\lambda}$. Ici on suit Sorin (2002).

Un ensemble dans $\mathbb{R}^{m}$ est semi-algébrique s'il peut s'écrire comme union finie d'ensembles $A_{k}$ de la forme:
\begin{equation*}
A_{k}=\{x\in \mathbb{R}^{m}\mid p_{k}(x)>0\}\quad\text{ou}\quad
A_{k}=\{x\in \mathbb{R}^{m}\mid p_{k}(x)=0\}.
\end{equation*}
où $p_{k}$ est un polynôme de $\mathbb{R}^{m}$.

En utilisant le fait que $v_{\lambda}$ est l'unique point fixe de $\Phi \left(\lambda,\cdot \right)$, on en déduit le résultat suivant.

\begin{proposition} L'ensemble des $(\lambda,v_{\lambda},x_{\lambda})$ tel que $\lambda $ parcourt $]0,1]$, $v_{\lambda}$ est la valeur du jeu $\lambda $-escompté, $x_{\lambda}^{i}$ est une stratégie optimale stationnaire du joueur~$i$ est semi-algébrique.
\end{proposition}

Ce résultat peut facilement être étendu aux jeux à somme non nulle en remplaçant valeur par paiement d'équilibre et stratégie optimale par profil d'équilibre de Nash (pour plus de détails sur l'approche semi-algébrique, consulter le chapitre 6 par Neyman dans Neyman et Sorin 2003).

En utilisant l'élimination de Tarski-Seidenberg (Benedetti et Risler 1990, théorème 2.21, p\ptbl 54) on en déduit qu'il existe une sélection semi-algébrique par rapport à $\lambda \in{}]0,1[$. Ceci implique l'existence d'un développement en série de Puiseux au voisinage de $0$ pour chaque élément $z_{\lambda}\in \{x_{\lambda},y_{\lambda},v_{\lambda}\}$.

\begin{theorem}[Bewley and Kohlberg 1976]
Étant donné un jeu stochastique (où tout est fini) à somme nulle, pour chaque $z_{\lambda}\in \{x_{\lambda},y_{\lambda},v_{\lambda}\}$, il existe $\lambda_{0}>0$, $k\in \mathbb{N}^{*}$, $r_{n}:\Omega \to \mathbb{R}$, $n=0,\dots,$ tels que:
\begin{equation*}
z_{\lambda}(\omega)=\sum_{n=0}^{\infty}r_{n}\left(\omega \right) \lambda^{\frac{n}{k}}.
\end{equation*}
pour tout $\lambda \in{}]0,\lambda_{0}[$ et tout $\omega \in \Omega $.
\end{theorem}

\begin{proof}
On applique le résultat de Forster 1981, théorème 8.14, p\ptbl 58, au cas où les paiements sont uniformément bornés.
\end{proof}

Ainsi dans l'exemple du jeu d'arrêt nous avons:
\begin{eqnarray*} v_{\lambda} &=&x_{\lambda}=y_{\lambda}=\frac{1-\sqrt{\lambda}}{1-\lambda}\\
&=&\left(1-\sqrt{\lambda}\right) \left(1+\lambda +\lambda^{2}+\cdots\right).
\end{eqnarray*}
Dans le cadre des jeux avec plus de deux joueurs ou à somme non nulle, on peut montrer l'existence d'une sélection de stratégies et de paiements d'équilibre ayant un développement en série de Puiseux.

La fonction $\lambda \to f_{\lambda}$ où $f_{\lambda}\in \mathcal{F}$ et $\lambda \in{}]0,1[$ sera dite \textit{à variation bornée} si pour toute suite $\left\{ \lambda_{n}\right\}_{n\in \mathbb{N}}$ dans $]0,1[$ décroissante vers 0, nous avons:
\begin{equation*}
\sum_{n=1}^{\infty}\left\| f_{\lambda_{n+1}}-f_{\lambda_{n}}\right\|_{\infty}<\infty.
\end{equation*}

\begin{corollary} \label{CorollaireBoudedVariation}
$v_{\lambda}$ est une fonction à variation bornée au voisinage de $0$ et admet une limite quand $\lambda \to 0$.
\end{corollary}

\begin{proof}
La convergence est une conséquence du développement de Puiseux. La variation bornée est une conséquence du fait que pour tout $\lambda \in (0,\lambda_{0})$ nous avons:
\begin{equation*}
\left\| \frac{dv_{\lambda}}{d\lambda}\right\|_{\infty}\leq C\lambda^{\sfrac{(1-k)}{k}}.\qedhere
\end{equation*}
\end{proof}

\begin{corollary} $\lim_{T\to \infty}v_{T}$ existe et est égale à $\lim_{\lambda \to 0}v_{\lambda}$.
\end{corollary}

Ceci est une conséquence directe d'un résultat général (voir le chapitre 26 par Neyman dans Neyman et Sorin 2003).

Soit $\Theta $ un opérateur d'un espace de Banach $\mathcal{Z}$ dans lui-même qu'on supposera non dilatant, \ie pour tout $z$ et $z'$ dans $\mathcal{Z}$, $\left\| \Theta (z)-\Theta (z')\right\| \leq \left\| z-z'\right\| $. Il est facile de voir alors que, pour tout $z$ et $z'$ dans $\mathcal{Z}$,
\begin{equation*}
\left\| \lambda \Theta \Bigl(\frac{1-\lambda}{\lambda}z\Bigr) -\lambda \Theta \Bigl(\frac{1-\lambda}{\lambda}z'\Bigr) \right\| \leq \left(1-\lambda \right)\| z-z'\|.
\end{equation*}
de sorte que $w\to \lambda \Theta \left(\frac{1-\lambda}{\lambda}w\right)$ admet un point fixe qui est nécessairement unique (par contraction de Picard). Soit $w_{\lambda}$ ce point fixe.

Définissons la suite $\left\{ w_{T}\right\}_{T=0,1,\dots}$ dans $\mathcal{Z}$ par récurrence comme suit: $w_{0}=0$ et $w_{T+1}=\frac{1}{T+1}\Theta \left(Tw_{T}\right)$, celle-ci pouvant s'écrire aussi $w_{T}=\frac{\Theta^{T}(0)}{T}$.

\begin{theorem}[Neyman 2003] Si $w_{\lambda}$ est à variation bornée alors $\lim_{\lambda \to 0}w_{\lambda}=\lim_{T\to \infty}w_{T}$.
\end{theorem}

Pour montrer le dernier corollaire il suffit de prendre $\Theta =\Psi $ et $\mathcal{Z}=\mathcal{F}$.

\begin{proof} Remarquons que si $w_{\lambda}$ est à variation bornée, elle converge nécessairement vers un certain $w$. Supposons que $\lambda_{t}=\sfrac{1}{t}$. Dans ce cas,
\begin{eqnarray*} \left\| w_{t+1}-w_{\lambda_{t+1}}\right\| &=&\left\| \frac{1}{t+1}\Theta \left(tw_{t}\right) -\frac{1}{t+1}\Theta \left(tw_{\lambda_{t+1}}\right) \right\|\\
&\leq &\frac{t}{t+1}\left\| w_{t}-w_{\lambda_{t+1}}\right\|\\
&\leq &\frac{t}{t+1}\left(\left\| w_{t}-w_{\lambda_{t}}\right\| +\left\| w_{\lambda_{t}}-w_{\lambda_{t+1}}\right\| \right),
\end{eqnarray*}
soit
\begin{equation*}
\left(t+1\right) \left\| w_{t+1}-w_{\lambda_{t+1}}\right\| \leq t\left\| w_{t}-w_{\lambda_{t}}\right\| +t\left\| w_{\lambda_{t}}-w_{\lambda_{t+1}}\right\|.
\end{equation*}
En sommant on trouve
\begin{equation*}
\left(T+1\right) \left\| w_{T+1}-w_{\lambda_{T+1}}\right\| \leq \left\| w_{1}-w_{\lambda_{1}}\right\| +\sum_{t=1}^{T}t\left\| w_{\lambda_{t}}-w_{\lambda_{t+1}}\right\|.
\end{equation*}
Puisque la somme $\sum_{t=1}^{T}\left\| w_{\lambda_{t}}-w_{\lambda_{t+1}}\right\| $ est bornée, nous obtenons que $\frac{1}{T+1}\sum_{t=1}^{T}t\left\| w_{\lambda_{t}}-w_{\lambda_{t+1}}\right\| \to 0$, d'où le résultat.
\end{proof}

\section{Big-Match}\label{sec:10}

Avant d'étudier l'approche uniforme dans les jeux à somme nulle en général, nous étudions le Big-Match. C'est le premier exemple résolu explicitement dans le cadre uniforme par Blackwell et Ferguson (1968). C'est le jeu suivant:
\begin{equation*}
\begin{tabular}{ccc} & $\overline{0}$ & $\overline{1}$\\
\cline{2-3} $\overline{0}$ & \multicolumn{1}{|c}{1} & \multicolumn{1}{|c|}{0}\\
\cline{2-3} $\overline{1}$ & \multicolumn{1}{|c}{0$^{\ast}$} & \multicolumn{1}{|c|}{1$^{\ast}$}\\
\cline{2-3}
\end{tabular}
\end{equation*}
L'histoire qu'ils ont utilisée pour le présenter est la suivante:

\emph{\og Chaque jour le joueur~2 choisit un nombre $\overline{0}$ ou $\overline{1}$, et le joueur~1 essaye de prédire le choix du joueur~2, gagnant un point à chaque fois qu'il a raison. Cela continue tant que le joueur~1 prédit $\overline{0}$. Si un jour il prédit $\overline{1}$, tous les choix futurs pour les deux joueurs sont contraints à être les mêmes que le choix de ce jour: si le joueur~1 avait raison ce jour là, il gagne~$1$ point chaque jour suivant; s'il s'est trompé ce jour là, il gagne $0$ tous les jours suivants.\fg}

Seul le joueur~1 peut arrêter le jeu et ceci arrive dès qu'il choisit l'option $\overline{1}$. La formule du théorème \ref{TheoremeFormuleRecurrence} implique que:
\begin{equation*}
v_{T+1}=\frac{1}{T+1}\,\text{valeur}\left(
\begin{tabular}{ccc} & $\overline{0}$ & $\overline{1}$\\
\cline{2-3} $\overline{0}$ & \multicolumn{1}{|c}{1+Tv$_{T}$} & \multicolumn{1}{|c|}{Tv$_{T}$}\\
\cline{2-3} $\overline{1}$ & \multicolumn{1}{|c}{0} & \multicolumn{1}{|c|}{1}\\
\cline{2-3}
\end{tabular}
\right).
\end{equation*}
Par récurrence, on montre que $v_{T}=\sfrac{1}{2}$. La stratégie $(\frac{1}{2}\overline{0},\frac{1}{2}\overline{1})$\ du joueur~2 lui garantit une espérance de gain de $\sfrac{1}{2}$ par étape et donc~$\sfrac{1}{2}$ uniformément. L'unique stratégie optimale du joueur $1$ est markovienne et consiste de jouer $\overline{1}$ avec probabilité $x_{m}=\frac{1}{m+1}$, s'il reste $m$ étapes à jouer (en particulier il n'existe pas de stratégie stationnaire optimale pour le joueur~1). On calcule facilement que $v_{\lambda}=\sfrac{1}{2}$ et que l'unique stratégie optimale du joueur~1 est évidemment stationnaire. Elle consiste à jouer $\overline{1}$ avec probabilité $x_{\lambda}=\frac{\lambda}{1+\lambda}$. À la limite quand $\lambda \to 0$, le joueur~1 joue $\overline{0}$ avec probabilité 1 à chaque étape. Cette stratégie est mauvaise car elle ne permet d'assurer que zéro par étape (face à cette stratégie, le joueur~2 pourrait jouer l'option $\overline{1}$ à chaque étape).

Nous allons montrer que le joueur~1 peut garantir uniformément tout paiement strictement moins que $\sfrac{1}{2}$ (ce qui implique que la valeur uniforme de ce jeu existe et est égale à $\sfrac{1}{2})$. Cependant, il assez facile de montrer qu'il n'a pas de stratégie uniforme qui garantit exactement $\sfrac{1}{2}$. Pour le montrer il suffit de remarquer que le joueur~1 doit assurer tout le temps un paiement de continuation de 1/2 ce qui l'oblige à continuer le jeu avec probabilité 1 à chaque étape (en jouant tout le temps l'option $\overline{0}$). Cette stratégie ne lui garantit qu'un paiement de 0. Le Big-Match n'admet donc pas d'équilibre uniforme mais seulement un paiement d'équilibre uniforme.

L'idée de la construction est la suivante: tant que le jeu n'est pas absorbé, si le joueur~1 a obtenu dans le passé un bon paiement (plus de 1 que de 0), il joue avec une probabilité relativement grande la stratégie $\overline{0}$, sinon il augmente sa probabilité de jouer $\overline{1}$.

\begin{theorem}[Blackwell et Ferguson 1968] Pour tout entier $K>0$ le joueur~1 a une stratégie qui garantit uniformément le paiement $\sfrac{K}{2(K+1)}$.
\end{theorem}

\begin{proof} Fixons un entier $K\!>\!0$. Pour tout nombre d'éta\-pes~$T$, définissons trois entiers:

\begin{itemize}
\item
$0_{T}$ le nombre d'étapes avant $T$ où le joueur~2 joue $\overline{0}$;

\item
$1_{T}$ le nombre d'étapes avant $T$ où le joueur~2 joue $\overline{1}$;

\item
$k_{T}=0_{T}-1_{T}$.
\end{itemize}

On remarque que $0_{T}+1_{T}=T-1$, ce qui implique:
\begin{equation*}
k_{T}=2l_{T}-T-1.
\end{equation*}
Si le joueur~2 a souvent joué $\overline{0}$, $k_{T}$ est grand (en particulier positif). Dans ce cas, le joueur~1 augmentera sa probabilité de jouer $\overline{0}$. Dans le cas contraire, $k_{T}$ est petit (en particulier négatif) et le joueur~1 augmentera sa probabilité de jouer $\overline{1}$.

Nous définissons la stratégie du joueur~1, $\sigma_{K}$, comme suit: à~l'éta\-pe~$T$, si le jeu n'a pas été absorbé, jouer $\overline{1}$ avec probabilité $\sfrac{1}{\left(k_{T}+K+1\right)^{2}}$. On note que si $k_{T}=-K$ alors le jeu est absorbé avec probabilité 1. En particulier, tout choix suivant des joueurs n'affecte plus les paiements. Nous allons montrer que pour toute suite d'actions $a^{2}=\left(a_{1}^{2},\dots,a_{t}^{2},\dots\right)$ du joueur~2, nous avons:
\begin{equation*}
\E_{\sigma_{K}^{1},a^{2}}\bigg(\sum_{t=1}^{T}\frac{1}{T}\,g^{1}\left(\omega_{t},a_{t}\right) \bigg) \geq \frac{K}{2(K+1)}-\frac{K+1}{2T}.
\end{equation*}
Ceci impliquerait que la même propriété est vraie pour toute stratégie pure du joueur~2 et donc aussi pour toute stratégie mixte du joueur~2. Nous déduirons alors que le joueur~1 peut garantir uniformément $\frac{K}{2\left(K+1\right)}-\varepsilon $ pour tout $\varepsilon $.

Fixons donc une suite d'actions $a^{2}=\left(a_{1}^{2},\dots,a_{t}^{2},\dots\right)$ pour le joueur~2. Remarquons alors que:
\begin{itemize}
\item
si $a_{1}^{2}=\overline{1}$, alors $\sigma_{K}^{1}$ coïncide avec $\sigma_{K-1}^{1}$ à partir de l'étape 2,

\item
si $a_{1}^{2}=\overline{0}$, alors $\sigma_{K}^{1}$ coïncide avec $\sigma_{K+1}^{1}$ à partir de l'étape 2.
\end{itemize}

Soit $t_{\ast}$ la première étape où le jeu est absorbé (le joueur~1 joue $\overline{1}$). Définissons la variable aléatoire $X_{T}$ comme suit:
\begin{equation*}
X_{T}=
\begin{cases}
\sfrac{1}{2} & \text{si } t_{\ast}>T \\
1 & \text{si } t_{\ast}\leq T,\quad a_{t_{\ast}}^{2}=\overline{1}\\
0 & \text{si } t_{\ast}\leq T,\quad a_{t_{\ast}}^{2}=\overline{0}
\end{cases}
\end{equation*}
Si le jeu s'est arrêté avant ou à l'étape $T$, $X_{T}$ représente le paiement d'absorption du joueur~1. Sinon, $X_{T}$ vaut $\sfrac{1}{2}$ (l'objectif approximatif du joueur~1). Nous allons montrer par récurrence sur $T$ que
\begin{equation*}
\E_{\sigma_{K}^{1},a^{2}}\left(X_{T}\right) \geq \frac{K}{2(K+1)}.
\end{equation*}
Pour $T=1$:

\begin{itemize}
\item
Si $a_{1}^{2}=\overline{1}$, alors
\[
\E_{\sigma_{K}^{1},a^{2}}\left(X_{T}\right) =\left(1-\frac{1}{\left(K+1\right)^{2}}\right) \frac{1}{2}+\frac{1}{\left(K+1\right)^{2}}
>\frac{1}{2}>\frac{K}{2(K+1)}.
\]

\item
Si $a_{1}^{2}=\overline{0}$, alors
\[
\E_{\sigma_{K}^{1},a^{2}}\left(X_{T}\right) =\left(1-\frac{1}{\left(K+1\right)^{2}}\right) \frac{1}{2}=\frac{K(K+2)}{2(K+1)^{2}}>\frac{K}{2(K+1)}.
\]
\end{itemize}

Supposons maintenant que la dernière inégalité est satisfaite pour $T=t_{0}$ et montrons qu'elle est vraie pour $T=t_{0}+1$.

\begin{itemize}
\item
Si $a_{1}^{2}=\overline{1}$, alors
\begin{eqnarray*} \E_{\sigma_{K}^{1},a^{2}}\left(X_{t_{0}+1}\right) &=&\left(1-\frac{1}{\left(K+1\right)^{2}}\right) E_{\sigma_{K-1}^{1},a^{2}}\left(X_{t_{0}}\right) +\frac{1}{\left(K+1\right)^{2}}\\
&>&\left(1-\frac{1}{\left(K+1\right)^{2}}\right) \frac{K-1}{2K}+\frac{1}{\left(K+1\right)^{2}}\\
&=&\frac{K}{2\left(K+1\right)}.
\end{eqnarray*}

\item
Si $a_{1}^{2}=\overline{0}$, alors
\begin{eqnarray*} \E_{\sigma_{K}^{1},a^{2}}\left(X_{t_{0}+1}\right) &=&\left(1-\frac{1}{\left(K+1\right)^{2}}\right) E_{\sigma_{K+1}^{1},a^{2}}\left(X_{t_{0}}\right)\\
&>&\left(1-\frac{1}{\left(K+1\right)^{2}}\right) \frac{K+1}{2(K+2)}\\
&=&\frac{K}{2(K+1)}.
\end{eqnarray*}
\end{itemize}

Soit $t^{\ast}\!:=\!\min \{t_{\ast},T\}$: c'est l'étape courante si le jeu n'a pas \hbox{encore} été absorbé, sinon c'est l'étape d'absorption. Rappelons que si \hbox{$k_{T}\!=\!-K$}, alors le jeu est absorbé avec probabilité 1. Donc $k_{T}\geq -K$ d'où $0_{T}\geq \sfrac{(T-K-1)}{2}$, ce qui implique que:
\begin{align*}
\E_{\sigma_{K}^{1},a^{2}}\bigg(\sum_{t=1}^{T}\frac{1}{T}\,g^{1}&\left(\omega_{t},a_{t}\right) \bigg) =\E_{\sigma_{K}^{1},a^{2}}\bigg(\frac{0_{t^{\ast}}+\left(T-t^{\ast}\right) 1_{a_{t^{\ast}}^{2}=\overline{1}}}{T}\bigg)\\
&\geq \E_{\sigma_{K}^{1},a^{2}}\bigg(\frac{\frac{t^{\ast}-K-1}{2}+\left(T-t^{\ast}\right) 1_{a_{t^{\ast}}^{2}=\overline{1}}}{T}\bigg)\\
&=\E_{\sigma_{K}^{1},a^{2}}\bigg(\frac{\frac{t^{\ast}}{2}+\left(T-t^{\ast}\right) 1_{a_{t^{\ast}}^{2}=\overline{1}}}{T}\bigg) -\frac{K+1}{2T}\\
&=\frac{1}{T}\E_{\sigma_{K}^{1},a^{2}}\bigg(\sum_{t=1}^{T}X_{t}\bigg) -\frac{K+1}{2T}\\
&\geq \frac{K}{2(K+1)}-\frac{K+1}{2T}.\qedhere
\end{align*}
\end{proof}

La stratégie utilisée dans la preuve nécessite l'observation par les joueurs des paiements et de l'état. Sans l'observation des paiements, la valeur uniforme du Big-Match n'existe pas (Coulomb (1992)). Cepen\-dant, dans le cas d'un joueur qui n'observe rien (ni état, ni paiements), il peut être démontré qu'une stratégie uniforme existe toujours (Rosenberg, Solan et Vieille (2002)) mais elle n'est pas aussi simple (stationnaire) que la stratégie uniforme de Blackwell (1962) en observation parfaite de l'état.

\section{Valeur uniforme}\label{sec:11}

Ici nous étendons le résultat précédent, à savoir l'existence de la valeur uniforme, à tout jeu stochastique à somme nulle.

\begin{theorem}[Mertens et Neyman (1981)] Tout jeu stochastique à deux joueurs et à somme nulle admet une valeur uniforme.
\end{theorem}

\begin{proof} Comme cela a déjà été montré précédemment, si la valeur uniforme existe, elle est nécessairement égale à
\[
\lim_{\lambda \to 0}v_{\lambda}(\omega_{1}):=v\left(\omega_{1}\right).
\]
Nous allons montrer que pour tout $\varepsilon >0$, le joueur~1 peut s'assurer uniformément $v\left(\omega_{1}\right) -\varepsilon $. Par symétrie, le joueur~2 peut aussi garantir uniformément $v\left(\omega_{1}\right) +\varepsilon $, d'où le résultat.

Par la section sur l'opérateur de Shapley, nous avons que pour tout taux d'escompte $\lambda $, il existe une stratégie optimale stationnaire $x_{\lambda}^{1}$ pour le joueur~1 (le joueur qui maximise). Donc pour tout $\omega \in \Omega $ et tout $y_{\lambda}^{2}\in \Delta \left(A^{2}(\omega)\right)$ nous avons\vspace*{-5pt}\enlargethispage{\baselineskip}
\begin{multline*}
\lambda g^{1}(\omega,x_{\lambda}^{1}(\omega),y_{\lambda}^{2} \left(\omega \right))\\
+(1-\lambda)\sum_{\omega'\in \Omega}q(\omega,x_{\lambda}^{1}\left(\omega \right),y_{\lambda}^{2}\left(\omega \right))(\omega')v_{\lambda}(\omega')\geq v_{\lambda}(\omega).
\end{multline*}
Nous allons construire explicitement une stratégie uniforme $\varepsilon $\nobreakdash-opti\-male pour le joueur~1 comme suit. À chaque étape $t$, le joueur~1\ va jouer la stratégie $x_{\lambda_{t}}^{1}(\omega_{t})$, où $\lambda_{t}$ est une fonction du paiement reçu dans le passé et $\omega_{t}$ est l'état courant. Si le paiement moyen passé est bon, le joueur~1 va augmenter le poids des opportunités futures ($\lambda_{t+1}<\lambda_{t})$. Dans le cas contraire, il doit essayer d'assurer un bon paiement aujourd'hui ($\lambda_{t+1}>\lambda_{t}$).

En effet, le taux d'escompte (comme le taux d'intérêt) mesure l'importance du paiement de court terme relativement au paiement de long terme. Dans l'étude de la valeur uniforme, le taux d'escompte peut être arbitrairement petit de telle sorte que les opportunités futu\-res ont un poids très élevé relativement aux opportunités présen\-tes. Cela dit, si le joueur a tout le temps des paiements faibles, il ne va \hbox{jamais} pouvoir utiliser les opportunités futures. Le mécanisme d'adaptation du taux d'escompte dynamiquement en fonction des performances passées permet au joueur de faire proprement son arbitrage entre le paiement aujourd'hui et le paiement demain.

D'après le corollaire \ref{CorollaireBoudedVariation}, il existe $\lambda_{0}$ tel que pour tout $0<\lambda <\lambda^{'}\leq \lambda_{0}$, il existe une fonction positive et intégrable $\psi $ sur $[0,\lambda_{0}]$ telle que\vspace*{-5pt}
\begin{equation*}
\max_{\omega \in \Omega}\left| v_{\lambda}(\omega)-v_{\lambda^{'}}\left(\omega \right) \right| =\int_{\lambda}^{\lambda^{'}}\psi (s)ds.
\end{equation*}
Soit $\varepsilon \in{}]0,M[$ fixé. On définit une fonction $D:[0,\lambda_{0}]\to \mathbb{R}$ comme suit:\vspace*{-5pt}
\begin{equation*}
D(y)=\frac{12M}{\varepsilon}\int_{y}^{\lambda_{0}}\frac{\psi (s)}{s}ds+\frac{1}{\sqrt{y}}
\end{equation*}

Nous allons commencer par montrer quelques propriétés sur $D$ avant de prouver le théorème.

\begin{propr}
$D$ est décroissante et intégrable ($\int_{0}^{\lambda_{0}}D(y)dy<+\infty $).
\end{propr}

\begin{proof}
La décroissance est évidente. Le second terme, $\sfrac{1}{\sqrt{y}}$, est clairement intégrable. Pour le deuxième terme, on intervertit les intégrales ce qui permet d'obtenir:
\begin{align*}
\int_{y=0}^{\lambda_{0}}\int_{s=y}^{\lambda_{0}}\frac{\psi (s)}{s}dsdy &=\int_{s=0}^{\lambda_{0}}\int_{y=s}^{\lambda_{0}}\frac{\psi (s)}{s}dsdy\\
&=\int_{s=0}^{\lambda_{0}}\psi (s)ds\leq 2M.\qedhere
\end{align*}
\end{proof}

\begin{propr}\mbox{}
\[
\lim_{y\to 0}D\left(y-\frac{\varepsilon}{6M}y\right) -D(y)=\lim_{y\to 0}D\left(y\right) -D\Big(y+\frac{\varepsilon}{6M}y\Big)=+\infty.
\]
\end{propr}

\begin{proof}
Nous avons:
\[
\lim_{y\to 0}D\left(y-\frac{\varepsilon}{6M}y\right) -D(y)=\lim_{y\to 0}\int_{y-\frac{\varepsilon}{6M}y}^{y}\frac{\psi (s)}{s}ds+\frac{1}{\sqrt{y-\frac{\varepsilon}{6M}y}}-\frac{1}{\sqrt{y}}.
\]
Le premier terme est positif et le second tend vers $+\infty $. L'autre limite se démontre de la même façon.
\end{proof}

Nous définissons maintenant une deuxième fonction $\varphi $ sur $[0,\lambda_{0}]$ comme suit:
\begin{equation*}
\varphi (\lambda)=\int_{D(\lambda)}^{+\infty}D^{-1}(y)dy=\int_{0}^{\lambda}D(y)dy-\lambda D(\lambda)
\end{equation*}
L'égalité plus haut se déduit géométriquement.

Définissons aussi pour tout entier $t$ la variable aléatoire $Z_{t}$ comme suit:
\begin{equation*}
Z_{t}=v_{\lambda_{t}}(\omega_{t})-\varphi (\lambda_{t}).
\end{equation*}
Puisque $D$ est intégrable, quand $\lambda_{t}\to 0$ la quantité $\varphi (\lambda_{t})$ approche $0$ et donc $Z_{t}$ approche $v_{0}(\omega_{t})$. Notre but est de construire une stratégie du joueur~1 telle que $Z_{t}$ soit une sous-martingale. Puisque la stratégie du joueur~1 va être de jouer la stratégie optimale du jeu $\lambda_{t}$-escompté, il nous faut d'abord construire les variables aléatoires $\lambda_{t}$. Nous allons les construire inductivement.

Nous choisissons $\lambda_{1}$ assez petit pour que

\begin{enumeratei}
\item
$\varphi (\lambda_{1})<\varepsilon $;

\item
$\forall y>D(\lambda_{1})$, $D\left(y-\frac{\varepsilon}{6M}y\right) -D(y)>6M$;

\item
$\forall y>D(\lambda_{1})$, $D\left(y\right) -D(y+\frac{\varepsilon}{6M}y)>6M$.
\end{enumeratei}

Ceci est possible grâce aux propriétés 1 et 2. Nous définissons $\lambda_{t+1}=D^{-1}(d_{t+1})$ où la suite $\left\{ d_{t}\right\} $ est définie comme suit:
\begin{eqnarray*} d_{1} &=&D(\lambda_{1})\\
d_{t+1} &=&\max \left\{ D(\lambda_{1}),d_{t}+g^{1}(\omega_{t},a_{t})-v_{\lambda_{t}}(\omega_{t+1})+4\varepsilon \right\}.
\end{eqnarray*}
Puisque $d_{t}\geq D(\lambda_{1})$ pour $t\geq 1$, nous concluons que $\lambda_{t}\leq \lambda_{1}$.

Nous allons commencer par étudier quelques propriétés utiles des deux suites.

\begin{propr}
$\left| d_{t+1}-d_{t}\right| \leq 6M$.
\end{propr}

\begin{proof} Cela découle de sa définition puisque $\left| g^{1}(\omega_{t},a_{t})\right| $, $\left| v_{\lambda_{t}}(\omega_{t+1})\right| $ et $\varepsilon $ sont bornés par $M$.
\end{proof}

\begin{propr}
$\left| \lambda_{t+1}-\lambda_{t}\right| \leq \sfrac{\varepsilon \lambda_{t}}{6M}$.
\end{propr}

\begin{proof} Étudions le cas $\lambda_{t+1}\leq \lambda_{t}$ (l'autre cas se montre de la même façon). Donc $d_{t}\leq d_{t+1}$ ce qui implique d'après la propriété~3 que $d_{t+1}\leq d_{t}+6M$.

Supposons maintenant que $\lambda_{t+1}<\lambda_{t}-\sfrac{\varepsilon \lambda_{t}}{6M}$. En utilisant (ii) nous aurons alors que
\begin{equation*}
d_{t+1}-d_{t}\geq D(\lambda_{t}-\frac{\varepsilon \lambda_{t}}{6M})-D(\lambda_{t})>6M,
\end{equation*}
ce qui est une contradiction.
\end{proof}

Nous définissons maintenant la stratégie du joueur~1 comme suit: à l'étape $t$, connaissant l'état actuel $\omega_{t}$ et observant le paiement de l'étape précédente, le joueur actualise le taux d'escompte à $\lambda_{t}$ puis à l'étape $t$ il joue la stratégie optimale $x_{\lambda_{t}}^{1}(\omega_{t})$ dans le jeu $\lambda_{t}$ escompté. Appelons cette stratégie $\sigma^{1}$.

On définit
\begin{eqnarray*} C_{1} &=&\varphi (\lambda_{t})-\varphi (\lambda_{t+1});\\
C_{2} &=&v_{\lambda_{t+1}}(\omega_{t+1})-v_{\lambda_{t}}(\omega_{t+1});\\
C_{3} &=&\lambda_{t}\left(g^{1}\left(\omega_{t},a_{t}\right) -v_{\lambda_{t}}(\omega_{t+1})\right).
\end{eqnarray*}
Rappelons que $Z_{t}:=v_{\lambda_{t}}(\omega_{t})-\varphi (\lambda_{t})$ et que
\begin{equation*}
\varphi (\lambda)=\int_{0}^{\lambda}D(y)dy-\lambda D(\lambda).
\end{equation*}

\begin{propr}
Pour tout $t$, nous avons:
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ Z_{t+1}-Z_{t}\left| \mathcal{H}_{t}\right. \right] \geq \E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ C_{1}+C_{2}-C_{3}\left| \mathcal{H}_{t}\right. \right].
\end{equation*}
\end{propr}

\begin{proof} Nous avons, par définition de $\sigma^{1}$
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ \lambda_{t}g^{1}(\omega_{t},a_{t})+(1-\lambda_{t})v_{\lambda_{t+1}}(\omega_{t+1})\left| \mathcal{H}_{t}\right. \right] \geq v_{\lambda_{t}}(\omega_{t}),
\end{equation*}
d'où
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[
\begin{array}{l} \lambda_{t}\left(g^{1}(\omega_{t},a_{t})-v_{\lambda_{t}}(\omega_{t})\right)\\
{}+(1-\lambda_{t})\left(v_{\lambda_{t+1}}(\omega_{t+1})-v_{\lambda_{t}}(\omega_{t})\right) \left| \mathcal{H}_{t}\right.
\end{array}
\right] \geq 0.
\end{equation*}
Donc
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[
\begin{array}{l} \lambda_{t}\left(g^{1}(\omega_{t},a_{t})-v_{\lambda_{t}}(\omega_{t})\right)\\
{}+(1-\lambda_{t})\left(v_{\lambda_{t+1}}(\omega_{t+1})-v_{\lambda_{t}}(\omega_{t})\right)\\
{}+v_{\lambda_{t+1}}(\omega_{t+1})-v_{\lambda_{t+1}}(\omega_{t+1})\\
{}+\varphi (\lambda_{t})-\varphi (\lambda_{t})\\
{}+\varphi (\lambda_{t+1})-\varphi (\lambda_{t+1})\left| \mathcal{H}_{t}\right.
\end{array}
\right] \geq 0.
\end{equation*}
Nous en déduisons donc que
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ C_{3}-C_{2}-C_{1}+Z_{t+1}-Z_{t}\left| \mathcal{H}_{t}\right. \right] \geq 0.\qedhere
\end{equation*}
\end{proof}

Nous allons maintenant borner les termes $C_{1}$, $C_{2}$ et $C_{3}$.

\begin{propr}
$C_{1}\geq \lambda_{t}\left(d_{t+1}-d_{t}\right) -\varepsilon \lambda_{t}$.
\end{propr}

\begin{proof} Considérons le cas $\lambda_{t+1}<\lambda_{t}$ (l'autre cas se traite de la même façon). Dans ce cas on observe géométriquement, en utilisant la définition de $\varphi $ et la propriété 1, que
\begin{equation*}
\varphi (\lambda_{t})-\varphi (\lambda_{t+1})\geq \lambda_{t}\left(d_{t+1}-d_{t}\right) -\left(\lambda_{t+1}-\lambda_{t}\right) \left(d_{t+1}-d_{t}\right),
\end{equation*}
puis nous utilisons les propriétés 3 et 4.
\end{proof}

\begin{propr}
$\left| C_{2}\right| \leq \varepsilon \lambda_{t}$.
\end{propr}

\begin{proof} Nous avons:
\begin{eqnarray*} \left| C_{2}\right| &=&\left| v_{\lambda_{t+1}}(\omega_{t+1})-v_{\lambda_{t}}(\omega_{t+1})\right|\\
&\leq &\left| \int_{\lambda_{t}}^{\lambda_{t+1}}\psi (y)dy\right|.
\end{eqnarray*}
La propriété 4 implique alors que pour tout $y$ entre $\lambda_{t}$ et $\lambda_{t+1}$ nous avons,
\begin{equation*}
\frac{\lambda_{t}}{y}\geq \frac{1}{2},
\end{equation*}
d'où
\begin{eqnarray*} \left| C_{2}\right| &\leq &\left| \int_{\lambda_{t}}^{\lambda_{t+1}}\frac{\psi (y)}{y}dy\right| 2\lambda_{t}\\
&=&\lambda_{t}\left| \frac{\varepsilon}{6M}\left(d_{t}-d_{t+1}\right) +\frac{1}{\sqrt{\lambda_{t}}}-\frac{1}{\sqrt{\lambda_{t+1}}}\right|.
\end{eqnarray*}
On observe par ailleurs que l'intégrale $\int_{\lambda_{t}}^{\lambda_{t+1}}\frac{\psi (y)}{y}dy$ est positive si et seulement si $\lambda_{t}<\lambda_{t+1}$. Ceci est vrai si et seulement si $\frac{1}{\sqrt{\lambda_{t}}}>\frac{1}{\sqrt{\lambda_{t+1}}}$. Nous déduisons donc que $\left| C_{2}\right| \leq \frac{\varepsilon}{6M}\left| d_{t}-d_{t+1}\right| \lambda_{t}$. Il nous suffit donc d'appliquer la propriété 3.
\end{proof}

\begin{propr}
$C_{3}\leq \lambda_{t}\left(d_{t+1}-d_{t}\right) -4\varepsilon \lambda_{t}$.
\end{propr}

\begin{proof}
Par définition de $d_{t+1}$ nous avons
\begin{equation*}
d_{t+1}-d_{t}\geq g^{1}(\omega,a_{t})-v_{\lambda_{t}}(\omega_{t+1})+4\varepsilon,
\end{equation*}
d'où l'inégalité souhaitée.
\end{proof}

Nous en déduisons maintenant la propriété souhaitée.

\begin{propr}
$Z_{t}$ est une sous-martingale qui satisfait
\begin{eqnarray*} \E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ Z_{t}\right] &\geq &2\varepsilon \E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ \sum_{t=1}^{T}\lambda_{t}\right] +Z_{1}\\
&\geq &Z_{1}.
\end{eqnarray*}
\end{propr}

\begin{proof} En utilisant les propriétés 5 à 8 nous obtenons que
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ Z_{t+1}-Z_{t}\left| \mathcal{H}_{t}\right. \right] \geq 2\varepsilon \lambda_{t}.
\end{equation*}
Puis en sommant nous en déduisons l'inégalité recherchée.
\end{proof}

Nous finissons maintenant la preuve du théorème. Pour cela nous allons montrer que pour toute stratégie $\sigma^{2}$ du joueur~2 nous avons
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\biggl(\sum_{t=1}^{T}\frac{1}{T}\,g^{1}\left(\omega_{t},a_{t}\right) \biggr) \geq v_{0}\left(\omega_{1}\right) -7\varepsilon,
\end{equation*}
pour tout $T\geq T_{0}$ que nous choisirons plus tard.

En remplaçant $Z_{t}$ par sa valeur $v_{\lambda_{t}}(\omega_{t})-\varphi \left(\lambda_{t}\right)$ dans la propriété~9 (la dernière inégalité) nous obtenons que
\begin{eqnarray*} \E_{\omega_{1},\sigma^{1},\sigma^{2}}\left[ v_{\lambda_{t}}(\omega_{t})\right] &\geq &v_{\lambda_{1}}(\omega_{1})+\varphi \left(\lambda_{t}\right) -\varphi \left(\lambda_{1}\right)\\
&\geq &v_{\lambda_{1}}(\omega_{1})-\varphi \left(\lambda_{1}\right)\\
&\geq &v_{\lambda_{1}}(\omega_{1})-\varepsilon,
\end{eqnarray*}
où la dernière inégalité utilise ($i$). Nous en déduisons donc que l'espérance du paiement $\lambda_{t}$-escompté en $\omega_{t}$ est élevée.

Par ($i$) et par définition de $Z_{t}$ nous obtenons que $\left| Z_{t}\right| \leq 2M$. Ainsi, utilisant la propriété 9, nous en déduisons que
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \sum_{t=1}^{+\infty}\lambda_{t}\bigg] \leq \frac{M}{\varepsilon},
\end{equation*}
d'où
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \sum_{t=1}^{+\infty}\mathbf{1}_{\left\{ \lambda_{t}=\lambda_{1}\right\}}\bigg] \leq \frac{M}{\varepsilon}.
\end{equation*}
Par définition de $d_{t+1}$ et en utilisant la propriété 3 nous obtenons:
\begin{equation*}
d_{t+1}-d_{t}\leq g^{1}(\omega_{t},a_{t})-v_{\lambda_{t}}(\omega_{t+1})+4\varepsilon +6M\mathbf{1}_{\left\{ \lambda_{t+1}=\lambda_{1}\right\}},
\end{equation*}
en sommant nous obtenons:
\begin{align*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \frac{1}{T}\sum_{t=1}^{T}g^{1}(\omega_{t},a_{t})\bigg]
&\geq \E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \frac{1}{T}\sum_{t=1}^{T}v_{\lambda_{t}}(\omega_{t+1})\bigg]\\
&\hspace*{1cm}+\frac{1}{T}\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ d_{T+1}-d_{1}\bigg] -4\varepsilon\\
&\hspace*{1cm}-\frac{6M}{T}\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \sum_{t=1}^{+\infty}\mathbf{1}_{\left\{ \lambda_{t}=\lambda_{1}\right\}}\bigg]\\
&\geq v_{\lambda_{1}}(\omega_{1})-\varepsilon-\frac{d_{1}}{T}-4\varepsilon-\frac{6M^{2}}{T\varepsilon},
\end{align*}
car $d_{T+1}\geq 0$. Il nous suffit maintenant pour conclure de choisir $T\geq T_{0}$ avec
\begin{equation*}
T_{0}=\max \left\{ \frac{d_{1}}{\varepsilon},\frac{6M^{2}}{\varepsilon^{2}}
\right\}.\qedhere
\end{equation*}
\end{proof}

\begin{rema*}
Nous avons prouvé par la même occasion que
\begin{equation*}
\E_{\omega_{1},\sigma^{1},\sigma^{2}}\bigg[ \lim \inf \frac{1}{T}\sum_{t=1}^{T}g^{1}(\omega_{t},a_{t})\bigg] \geq v_{\lambda_{1}}(\omega_{1})-7\varepsilon.
\end{equation*}
ce qui montre que tous les exemples de l'approche infinie ont une valeur qui coïncide avec la valeur uniforme.
\end{rema*}
\section{Paris Match}\label{sec:12}

Ce jeu a été introduit et étudié explicitement par Sorin (1986) et il appartient à la famille du Big-Match. L'exemple est célèbre car il montre que dans les jeux stochastiques à somme non nulle, il n'y a aucun lien entre l'approche asymptotique (l'ensemble des paiements d'équilibres de Nash quand le taux d'escompte tend vers zéro) et l'approche uniforme (l'ensemble des paiements d'équilibres de Nash uniformes). Ceci montre aussi la différence fondamentale entre les jeux répétés sans aléas (section 3 du le texte sur les jeux répétés (ce volume)) et les jeux stochastiques. L'exemple de Sorin (1986) est le suivant:
\begin{equation*}
\begin{tabular}{ccc} & G & D\\
\cline{2-3} H & \multicolumn{1}{|c}{(1,0)} & \multicolumn{1}{|c|}{(0,1)}\\
\cline{2-3} B & \multicolumn{1}{|c}{(0,2)$^{\ast}$} & \multicolumn{1}{|c|}{(1,0)$^{\ast}$}\\
\cline{2-3}
\end{tabular}
\end{equation*}
Ainsi, en gardant seulement les paiements du joueur~1, nous retrouvons le Big-Match étudié par Blackwell et Ferguson (1968).

Soit $E_{\lambda}$ l'ensemble des paiements d'équilibres de Nash du Paris-Match $\lambda $-escompté, $E_{T}$ l'ensemble des paiements d'équilibres de Nash du Paris-Match répété $T$ fois et enfin $E_0$ l'ensemble des paiements d'équilibres uniformes.

\begin{theorem}[Sorin (1986)] $E_{\lambda}$ et $E_{T}$ sont disjoints de $E_0$. Plus précisément, pour tout $\lambda $ et $T$ nous avons:

\begin{itemize}
\item[(a)] $E_{\lambda}=\{(\frac{1}{2},\frac{2}{3})\}$;

\item[(b)] $E_{T}=\{(\frac{1}{2},\frac{2}{3})\}$;

\item[(c)] $E_0=\{\alpha (\frac{1}{2},1)+(1-\alpha)(\frac{2}{3},\frac{2}{3});\alpha \in \left[ 0,1\right] \}$.
\end{itemize}
\end{theorem}

\begin{proof} Nous donnons seulement l'idée de la preuve en suivant Thuijsman au chapitre 12 dans Neyman et Sorin (2003). Pour une preuve complète veuillez consulter Sorin (1986).

\subsubsection*{Étape 1} Nous prouvons (a), (b) se prouve de la même manière.

Remarquons que tout paiement d'équilibre doit donner au moins~$\frac{1}{2}$ au joueur~1 et doit donner au moins $\frac{2}{3}$ au joueur~2. En effet, chaque joueur peut garantir au moins son montant (le joueur~2 en jouant $\frac{1}{3}G+\frac{2}{3}D$ à chaque étape et le joueur~1 en jouant comme dans le Big-Match escompté $\frac{\lambda}{1+\lambda}H+\frac{1}{1+\lambda}B$).

Soit $w$ le paiement d'équilibre le plus favorable au joueur~2 dans~$E_{\lambda}$. Nous allons prouver que $w\leq \frac{2}{3}$ (et donc est égal à $\frac{2}{3}$).

Soit $\left(\sigma^{1},\sigma^{2}\right)$ un équilibre dans $\Gamma_{\lambda}$ tel que $g_{\lambda}^{2}\left(\sigma^{1},\sigma^{2}\right) =w$. Soit $w_{1}$ (\resp $w_{2}$) le paiement de continuation sous $\left(\sigma^{1},\sigma^{2}\right)$ si à l'étape 1 la paire $(H,G)$ a été jouée (\resp $(H,D)$ a été jouée).

Remarquez que $w_{1}$ et $w_{2}$ doivent aussi correspondre à des paiements d'équilibres dans $\Gamma_{\lambda}$ pour le joueur~2 (car sinon le joueur~2 pourrait dévier). Donc on a:
\begin{equation*}
w_{1}\leq w
\begin{array}{cccc} & \text{et} & &
\end{array}
w_{2}\leq w.
\end{equation*}

Soit maintenant $p$ la probabilité avec laquelle le joueur~1 joue $B$ à la première étape sous $\sigma^{1}$ et soit $q$ la probabilité avec laquelle le joueur~2 joue $D$ sous $\sigma^{2}$. On vérifie facilement que si $\left(\sigma^{1},\sigma^{2}\right)$ est un équilibre alors $p$ et $q$ sont dans $]0,1[$. Nous en déduisons alors que le joueur~2 est indifférent entre ces deux actions à la première étape, d'où\vspace*{-5pt}
\begin{align*}
w&=2p+(1-p)(1-\lambda)w_{1}\\
&=0p+(1-p)(\lambda +(1-\lambda)w_{2})
\end{align*}
La ligne 2 (\resp 3) correspond à l'espérance de gain si $G$ est jouée (\resp si $D$ est jouée). Puisque $w_{1}\leq w$ et $w_{2}\leq w$ nous obtenons:\vspace*{-3pt}
\begin{eqnarray*} w &\leq &2p+(1-p)(1-\lambda)w\\
w &\leq &(1-p)(\lambda +(1-\lambda)w).
\end{eqnarray*}
La deuxième inégalité devient\vspace*{-5pt}
\begin{equation*}
2-w\geq (1-p)(2-(1-\lambda)w),
\end{equation*}
et en utilisant la première inégalité nous trouvons\vspace*{-5pt}
\begin{equation*}
\left(2-w\right) (1-p)(\lambda +(1-\lambda)w)\geq (1-p)(2-(1-\lambda)w)w
\end{equation*}
qui est équivalente à $w\leq \frac{2}{3}$.

Un calcul similaire montre que le paiement maximal possible pour le joueur~1 n'excède pas $\frac{1}{2}$.

\subsubsection*{Étape 2}
Pour prouver que $E_0\subset \{\alpha (\frac{1}{2},1)+(1-\alpha)(\frac{2}{3},\frac{2}{3})\mid\alpha \in \left[ 0,1\right] \}$ Sorin (1986) donne l'argument suivant:

\textit{L'idée de la preuve est très simple: si la probabilité d'obtenir un paiement absorbant sur le chemin d'équilibre est moins que 1, alors après un certain temps le joueur~1 joue essentiellement l'action H; les paiements de continuations correspondants à partir de cette étape ne sont pas individuellement rationnels, d'où la contradiction.}

Le lecteur est prié de consulter Sorin (1986) pour la traduction mathématique de cet argument.

\subsubsection*{Étape 3}
Nous prouvons que $\{\alpha (\frac{1}{2},1)+(1-\alpha)(\frac{2}{3},\frac{2}{3})\mid\alpha \in \left[ 0,1\right] \}\subset E_0$.

L'argument se comprend facilement à l'aide d'un exemple. Prenons par exemple le couple de paiements $\left(\frac{7}{12},\frac{10}{12}\right)$ et expliquons la méthode de Sorin pour construire un $\varepsilon $-équilibre uniforme. Considérons le jeu auxiliaire à somme nulle suivant:\vspace*{-5pt}
\begin{equation*}\renewcommand{\arraystretch}{1.3}
\begin{tabular}{ccc} & G & D\\
\cline{2-3} H & \multicolumn{1}{|c}{$\frac{7}{12}$} & \multicolumn{1}{|c|}{$-\frac{5}{12} $}\\
\cline{2-3} B & \multicolumn{1}{|c}{$-\frac{7}{12}^{\ast}$} & \multicolumn{1}{|c|}{$\frac{5}{12}^{\ast}$}\\
\cline{2-3}
\end{tabular}
\end{equation*}

Soit $\sigma_{\varepsilon}^{1}$ une stratégie uniformément $\varepsilon $-optimale pour le joueur~1 dans le jeu auxiliaire, similaire à celle de Blackwell et Ferguson 1968. Soit $x^{2}$ la stratégie stationnaire du joueur~2 qui joue $\frac{5}{12}G+\frac{7}{12}D$ à chaque étape. Sous $(\sigma_{\varepsilon}^{1},x^{2})$ le jeu est absorbé avec probabilité 1 et induit donc un vecteur de paiements dans le vrai jeu exactement égal à $\left(\frac{7}{12},\frac{10}{12}\right)$. Donc, $\sigma_{\varepsilon}^{1}$ est une meilleure réponse du joueur~1 dans le Paris-Match face à $x^{2}$ car sans absorption (en jouant H) le joueur~1 gagne seulement $\frac{5}{12}$. En utilisant la définition de la stratégie du joueur~$1$, il~est possible de montrer que $x^{2}$ est uniformément $\varepsilon $-optimale face à~$\sigma_{\varepsilon}^{1}$ dans le Paris Match (voir Sorin (1986)).
\end{proof}

\section{Extensions}\label{sec:13}

La construction d'une stratégie maxmin uniforme en cas d'observation imparfaite des actions a été faite d'une manière indépendante par Coulomb (2003) et Rosenberg, Solan et Vieille (2003).

Vieille (2000 a,b) a généralisé remarquablement le résultat de Mertens et Neyman (1982) aux jeux à deux joueurs et à somme non nulle en prouvant l'existence d'un paiement d'équilibre uniforme. Sa preuve, en deux étapes, consiste à réduire d'abord le problème d'existence à la classe des jeux récursifs (jeux dans lesquels les joueurs ont une fonction de paiement nulle dans tous les états non absorbants). Les jeux d'arrêts présentent la particularité d'être à la fois récursifs et absorbants d'où leur intérêt.

Exception faite de quelques cas particuliers, comme les jeux absorbants à trois joueurs résolus positivement par Solan (1999) qui prouve l'existence d'un paiement d'équilibre uniforme, le problème pour les jeux à plus de deux joueurs reste entièrement ouvert. Solan et Vieille (2003) ont exhibé un jeu d'arrêt à quatre joueurs qui prouve que pour montrer l'existence d'un paiement d'équilibre uniforme, il faut nécessairement inventer une nouvelle classe de stratégies, différentes de celles utilisées habituellement (comme celle dans la preuve de Mertens-Neyman 1981).

Plusieurs personnes conjecturent la non-existence d'un paiement d'équilibre uniforme pour tout jeu stochastique à $n$ joueurs. Pour prouver cela, il y a deux possibilités: trouver un contre exemple ou prouver que l'existence induit un paradoxe mathématique. La non-existence a été prouvée en temps continu. Laraki, Solan et Vieille (2004) ont exhibé un jeu d'arrêt simple à trois joueurs qui n'admet pas d'équilibre approché, que ça soit au sens faible (escompté) ou fort (uniforme). Le même exemple en temps discret admet un équilibre stationnaire pour le jeu escompté (par Fink (1964)) et un paiement d'équilibre uniforme (par Solan (1999)).

La classe la plus simple à étudier est certainement celle des jeux d'arrêts. Dans un jeu d'arrêt, chaque joueur a le choix entre A (arrêter) ou C (continuer). Tant que le jeu n'est pas arrêté, le gain d'étape est zéro pour chaque joueur. La première fois qu'un ou plusieurs joueurs choisissent l'action A le jeu est absorbé. Le paiement d'absorption de chaque joueur dépend de la coalition des joueurs $S$ qui ont arrêté le jour de l'absorption. À part une sous classe résolue positivement par Solan et Vieille (2001), le problème de l'existence d'un paiement d'équilibre uniforme reste entièrement ouvert (peut être pourriez vous le résoudre?).

L'existence de la valeur dans les jeux escomptés a été généralisée à des espaces d'états et d'actions plus généraux par Maitra et Parthasarathy (1970) et d'autres auteurs jusqu'au résultat très général de Nowak (1985).

Une façon très naturelle d'étudier $v_{\lambda}$ et $v_{T}$ consiste à étudier les propriétés mathématiques de l'opérateur de Shapley et de sa dérivée pour en déduire la convergence et une caractérisation de la limite. Cette approche a été utilisée pour la première fois par Kohlberg (1974) dans le cadre restreint des jeux absorbants et a été définie et étudiée d'une manière générale pour les jeux stochastiques à somme nulle par Rosenberg et Sorin (2001). Elle a été appliquée par les deux auteurs pour étudier les jeux absorbants avec des espaces d'actions compacts mais aussi pour l'étude des jeux répétés à information incomplète des deux côtés (\cf texte sur les jeux répétés (ce volume)). La même approche permet à Rosenberg (2000) de montrer l'existence et la caractérisation variationnelle de la valeur asymptotique des jeux absorbants et information incomplète d'un côté.

Nous invitons les lecteurs intéressés par d'autres résultats ou extensions à consulter le livre sur les jeux stochastiques édités par Neyman et Sorin (2003), le livre de Sorin (2002) ou encore l'ouvrage de référence sur les jeux répétés par Mertens, Sorin et Zamir (1994). Pour une étude détaillée de l'approche infinie (avec des fonctions de paiements mesurables définies sur l'ensemble des parties comme les liminf et limsup des sommes de Cesàro mais aussi d'autres objectifs comme atteindre ou éviter un sous ensemble mesurable de $H_{\infty}$) vous pouvez consulter l'ouvrage de référence de Maitra et Sudderth (1996).

\backmatter
\nocite{*}
\bibliographystyle{jepalpha+eid}
\bibliography{xups06-04}
\end{document}

