From 859fab9a347ae412ee934b81941504de803dd7fd Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 12 Apr 2023 19:06:19 +0200
Subject: Write final exercise.

---
 controle-20230417.tex | 177 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 175 insertions(+), 2 deletions(-)

(limited to 'controle-20230417.tex')

diff --git a/controle-20230417.tex b/controle-20230417.tex
index 1ce23ea..34925af 100644
--- a/controle-20230417.tex
+++ b/controle-20230417.tex
@@ -104,9 +104,9 @@ Durée : 2h
 Barème \emph{indicatif} : \textcolor{red}{XXX}.
 
 \ifcorrige
-Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+Ce corrigé comporte 8 pages (page de garde incluse).
 \else
-Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+Cet énoncé comporte 4 pages (page de garde incluse).
 \fi
 
 \vfill
@@ -596,6 +596,179 @@ revenir en arrière), et notamment, elle n'est pas d'image finie.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+On considère une variante \emph{à somme (possiblement) non-nulle} de
+Pierre-Papier-Ciseaux, à savoir le jeu en forme normale défini par la
+matrice de gain suivante :
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&$U$&$V$&$W$\\\hline
+$U$&$x,x$&$-1,+1$&$+1,-1$\\
+$V$&$+1,-1$&$x,x$&$-1,+1$\\
+$W$&$-1,+1$&$+1,-1$&$x,x$\\
+\end{tabular}
+\end{center}
+où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour
+« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ».  Le but de
+l'exercice est d'étudier les équilibres de Nash de ce jeu.
+
+(On prendra bien note, pour simplifier les raisonnements en cas, du
+fait que les options ont une symétrie cyclique\footnote{C'est-à-dire
+  que remplacer $U$ par $V$ et $V$ par $W$ et $W$ par $U$ ne change
+  rien au jeu.}, et que les joueurs ont eux aussi des rôles
+symétriques.)
+
+(1) Considérons le profil de stratégies mixtes dans lequel les deux
+joueurs choisissent chacun chaque option avec probabilité
+$\frac{1}{3}$ (on rappelle que c'est ça la stratégie optimale dans le
+cas à somme nulle).  Pour quelle(s) valeur(s) de $x$ ce profil est-il
+un équilibre de Nash ?
+
+\begin{corrige}
+Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie
+mixte $\frac{1}{3}U + \frac{1}{3}V + \frac{1}{3}W$, le gain espéré de
+chacun des deux joueurs est le même quelle que soit la stratégie pure,
+donc aussi mixte, de l'autre joueur.  Cette valeur se calcule
+d'ailleurs aisément (comme somme des trois colonnes, ou des trois
+lignes, de la matrice de gains, affectées des
+coefficients $\frac{1}{3}$) : c'est $\frac{1}{3}x$ ; mais la seule
+chose qui importe est que l'adversaire ait le même gain espéré quelle
+que soit la stratégie pure, donc aussi mixte, qu'il choisit : il n'a
+donc pas intérêt à changer unilatéralement sa stratégie.  Il s'agit
+donc \emph{toujours} d'un équilibre de Nash, quelle que soit la valeur
+de $x$.
+\end{corrige}
+
+\emph{On suppose dorénavant que $x<-1$.}
+
+(2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement
+$U$ (Pierre) ?  (On raisonnera sur le support de la stratégie de Bob
+en réponse.)  En déduire tous les équilibres de Nash dans lesquels au
+moins un joueur joue une stratégie pure.
+
+\begin{corrige}
+Si Alice joue purement $U$, les gains de Bob pour les différentes
+stratégies pures de sa réponse sont $x$ pour $U$, $+1$ pour $V$ et
+$-1$ pour $W$ d'après la matrice de gains.  Comme $+1 > -1 > x$, la
+seule option qui peut faire partie du support d'une meilleure réponse
+de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un
+équilibre de Nash, Bob répond forcément purement $V$.  Mais par le
+même raisonnement (compte tenu de la symétrie cyclique des options et
+de la symétrie des joueurs), si Bob joue purement $V$, Alice répond
+purement $W$.  Il ne peut donc pas y avoir d'équilibre de Nash dans
+lequel Alice joue purement $U$.  Et de nouveau par symétrie cyclique
+des options et symétrie des joueurs, il ne peut y avoir aucun
+équilibre de Nash dans lequel un joueur jouerait une stratégie pure.
+\end{corrige}
+
+(3) Dans cette question et la suivante, envisageons un équilibre de
+Nash dans lequel Alice joue une stratégie mixte $pU + (1-p)V$ avec
+$0<p<1$.  Supposons dans cette question que Bob réponde avec un une
+stratégie mixte ayant elle aussi $\{U,V\}$ comme support.  Montrer que
+$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$ ; en
+utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$
+(qu'on admettra pour ne pas perdre son temps en calculs inutiles), en
+déduire qu'un tel équilibre de Nash n'existe pas.
+
+\begin{corrige}
+Si Alice joue $pU + (1-p)V$, les gains espérés de Bob pour les
+différences stratégies pures de sa réponse sont $px-(1-p) =
+-1+(x+1)p$ pour $U$, $p + (1-p)x = x-(x-1)p$ pour $V$ et $-p + (1-p) =
+1-2p$ pour $W$.  Si une meilleure réponse de Bob a $\{U,V\}$ comme
+support, ces deux options doivent apporter le même gain espéré,
+c'est-à-dire qu'on doit avoir $-1+(x+1)p = x-(x-1)p$, ce qui équivaut
+à $p = \frac{x+1}{2x}$, et le gain en question est $\frac{x^2+1}{2x}$,
+tandis que le gain espéré pour $W$ est alors $1-2p = -\frac{1}{x}$.
+D'après l'inégalité $\frac{x^2+1}{2x} < -\frac{1}{x}$, l'option $W$
+fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas
+être le support d'une meilleure réponse de Bob à $pU + (1-p)V$
+d'Alice.
+\end{corrige}
+
+(4) Toujours en considérant un équilibre de Nash dans lequel Alice
+joue une stratégie mixte $pU + (1-p)V$ avec $0<p<1$.  Supposons
+maintenant que Bob réponde avec un une stratégie mixte ayant
+$U$ et $W$ dans son support support.  Montrer que $p = \frac{2}{x+3}$
+(et que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$
+lorsque $-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (qu'on
+admettra aussi), en déduire qu'un tel équilibre de Nash n'existe pas.
+
+\begin{corrige}
+On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les
+gains espérés de Bob pour les différences stratégies pures de sa
+réponse sont $px-(1-p) = -1+(x+1)p$ pour $U$, $p + (1-p)x =
+x-(x-1)p$ pour $V$ et $-p + (1-p) = 1-2p$ pour $W$.  Si une meilleure
+réponse de Bob a $U$ et $W$ dans son support, ces deux options doivent
+apporter le même gain espéré, c'est-à-dire qu'on doit avoir $-1+(x+1)p
+= 1-2p$, ce qui équivaut à $(x+3)p = 3$, donc $x\neq 3$ et $p =
+\frac{2}{x+3}$.  D'après les inégalités admises, $p$, qui devrait être
+entre $0$ et $1$, ne l'est jamais si $x<-1$, donc un tel équilibre de
+Nash n'existe pas.
+\end{corrige}
+
+(5) Expliquer soigneusement pourquoi les questions (2) à (4) montrent
+que dans tout équilibre de Nash du jeu considéré, les deux joueurs
+jouent une stratégie mixte ayant $\{U,V,W\}$ comme support (i.e.,
+aucun ensemble strictement plus petit n'est possible).
+
+\begin{corrige}
+On a vu en (2) qu'il n'existe aucun équilibre de Nash dans lequel un
+joueur joue une stratégie pure.  Supposons maintenant un équilibre de
+Nash dans lequel un joueur a deux options dans son support.  Par
+symétrie, sans perte de généralité, on peut supposer que c'est Alice
+et que ces deux options sont $U$ et $V$.  Comme les stratégies pures
+sont exclues, les supports possibles de la réponse de Bob sont :
+$\{U,V\}$, $\{U,W\}$, $\{V,W\}$ et $\{U,V,W\}$.  Dans la question (3)
+on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et
+$\{U,V,W\}$.  Reste le cas où le support de la stratégie de Bob est
+$\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$).
+Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to
+V\to U$) et permuter les joueurs, cela revient au cas où le support de
+la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ :
+mais on a déjà exclu ce cas.  Il ne reste donc aucune possibilité.
+\end{corrige}
+
+(6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue
+une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et
+$1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi
+$\{U,V,W\}$ comme support.  Écrire un système de deux équations
+linéaires sur $p,p'$, justifier que ce système est non-dégéné et
+conclure.
+
+\begin{corrige}
+Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour
+les différences stratégies pures de sa réponse sont $px - p' +
+(1-p-p') = 1 + (x-1)p - 2p'$ pour $U$, $p + p' x - (1-p-p') = -1 + 2p
++ (x+1)p'$ pour $V$ et $-p + p' + (1-p-p')x = x -(x+1)p -
+(x-1)p'$ pour $W$.  Si une meilleure réponse de Bob a $\{U,V,W\}$
+comme support, ces trois options doivent apporter le même gain espéré,
+c'est-à-dire que $1 + (x-1)p - 2p' = -1 + 2p + (x+1)p' = x -(x+1)p -
+(x-1)p'$, ou (en soustrayant, disons, le premier membre aux deux
+autres) :
+\[
+\begin{aligned}
+-(x-3)p + (x+3)p' &= 2\\
+- 2xp - (x-3)p' &= -(x-1)
+\end{aligned}
+\]
+Le déterminant de ce système est $(x-3)^2 + 2x(x+3) = 3(x^2+3)$ qui
+est non nul quel que soit $x$, donc le système est non-dégénéré : la
+solution $p=p'=\frac{1}{3}$ trouvée en (1) est donc la seule solution.
+
+Bref, on a montré que le seul équilibre de Nash dans lequel les
+supports des stratégies d'Alice et Bob sont $\{U,V,W\}$ est celui
+décrit en (1) ; comme on a vu en (5) que ceci est la seule possibilité
+de support, il s'agit du seul équilibre de Nash du jeu.
+\end{corrige}
+
+
+
+
 
 %
 %
-- 
cgit v1.2.3