Enoncé modifié de l'exercice 3 du TD 3 (L2ande - jeux)

Alice et Gulliver jouent au jeu suivant : Chacun mise d'abord un euro. Alice tire une carte, qui est soit rouge soit noire, avec même probabilité, et la regarde. Elle choisit alors d'annoncer “rouge” ou “noire”. Pour annoncer “rouge” elle doit miser un euro supplémentaire. Si elle annonce “rouge”, Gulliver peut demander à voir la carte, mais pour cela il doit miser un euro.

Si Alice annonce “noire” ou bien si elle annonce “rouge” et que Gulliver demande à voir la carte et observe qu'Alice a menti, Gulliver remporte la mise. Dans les autres cas Alice remporte la mise.

a. Donner la forme extensive du jeu.

Instructions : l'intervention du hasard est modélisée par un joueur nommé “Nature”. Chaque noeud a pour étiquette le nom du joueur devant décider un choix en ce noeud et les branches partant de ce noeud correspondent aux choix que peut faire ce joueur. On relie deux noeuds étiquetés d'un même nom de joueur par une ligne pointillée pour indiquer que le joueur ne peut distinguer ces noeuds ("jeu à information incomplète") ; il ne fait donc qu'un seul choix pour cet ensemble de noeuds.

Réponse :

poker-pencil.svg

Gulliver ne distingue pas les deux noeuds où il intervient.

b. Donner les formes normales du jeu pour Alice et Gulliver avec comme gains de chaque joueur les espérances de gains.

Explication : les gains d'Alice et Gulliver dépendent du choix que fait le joueur “Nature”, lequel choisit aléatoirement une carte rouge ou noire de façon équiprobable. Les gains d'Alice et Gulliver sont donc des variables aléatoires dont on retiendra ici l'espérance.

Quelle est l'interprétation de cette espérance de gain lorsque le jeu est répété ?

Que se passe t-il si Gulliver perçoit chez Alice un signe de réjouissance lorsqu'elle tire une carte rouge ?

Réponse :

Les stratégies d'Alice sont de la forme (choix si carte rouge, choix si carte noire) et les choix en question sont 'annoncer noire' ou 'annoncer rouge' qu'on code par les mots 'n' et 'r'. Alice a ainsi 4 stratégies : (n,n), (n,r),(r,n),(r,r)

Gulliver a deux stratégies : 'constester' (demander à voir la carte) ou 'laisser' qu'on code par 'c' et 'n'

Un couple formé d'une stratégie d'Alice et d'une stratégie de Gulliver et le choix de "Nature" (la couleur de la carte tirée) détermine un chemin dans l'arbre donc un paiement (gain d'Alice, gain de Gulliver). Le jeu est à somme nulle : le gain de Gulliver est l'opposé du gain d'Alice. Dit autrement le gain d'Alice est la perte de Gulliver.

Voici le tableau des gains d'Alice conditionné à la couleur de la carte tirée

$ \begin{array} {|c|c|c|c|c|} \hline \textrm{Gulliver} \setminus \textrm{Alice} & \textrm{(n,n)} &\textrm{(n,r)} & \textrm{(r,n)} & \textrm{(r,r)} \\ \hline \textrm{l} & -1 & {\begin{array}{cl}-1\textrm{ si carte rouge} \\ 1\textrm{ si carte noire}\end{array}} & {\begin{array}{c}1\textrm{ si carte rouge} \\ -1\textrm{ si carte noire}\end{array}} &1 \\ \hline \textrm{c} &-1 & {\begin{array}{cl}-1\textrm{ si carte rouge} \\ -2\textrm{ si carte noire}\end{array}} & {\begin{array}{c}2\textrm{ si carte rouge} \\ -1\textrm{ si carte noire}\end{array}} &{\begin{array}{c}2\textrm{ si carte rouge} \\ -2\textrm{ si carte noire}\end{array}} \\ \hline \end{array} $

En considérant les gains d'Alice et Gulliver comme des variables aléatoires on obtient le tableau suivant des espérances de gains d'Alice (celles de Gulliver sont opposées):

$ \begin{array} {|c|c|c|c|c|} \hline \textrm{Gulliver} \setminus \textrm{Alice} & \textrm{(n,n)} &\textrm{(n,r)} & \textrm{(r,n)} & \textrm{(r,r)} \\ \hline \textrm{l} & -1 & 0 & 0 &1 \\ \hline \textrm{c} &-1 & -3/2 & 1/2 & 0 \\ \hline \end{array} $

L'espérance de gain s'interprète comme le gain moyen lorsque le jeu est répété de façon indépendante un grand nombre de fois. Si le jeu est répété sur la base d'un ensemble de carte, les répétitions ne sont plus tout à fait indépendantes entre elles : le tirage d'une carte rouge diminue la probabilité qu'une carte rouge soit tirée le coup suivant.

Si Gulliver perçoit par un signe la couleur de la carte tirée par Alice alors les deux noeux où il doit faire son choix sont discernables de sorte qu'il a comme Alice 4 stratégies et non plus deux.

c. Quel est le gain moyen garanti maximal (maxmin) de Gulliver si Alice et Gulliver choisissent leurs stratégies une fois pour toute avant la répétition du jeu ?

Si Gulliver choisit une stratégie prudente ; le regrètera t-il ? Qu'est il d'Alice ?

Quel est le gain moyen garanti de Gulliver s'il conteste “rouge” aléatoirement trois fois sur quatre ? Quelle est la meilleure réponse d'Alice à un tel comportement ? Est ce en équilibre ?

Réponse :

Le gain moyen garanti de Gulliver lorsqu'il choisit une stratégie est son plus mauvais gain : celui qu'il obtient lorsque Alice joue la meilleure réponse.

D'après le tableau plus haut, s'il choisit 'l', sa plus grande perte moyenne (l'opposé du gain moyen) est 1 ; s'il choisit 'c', sa plus grande perte est 1/2. Son gain moyen garanti maximal est donc -1/2 et l'unique stratégie prudente est 'c'

Supposons que Gulliver joue 'c'. Il regrette son choix si Alice joue (r,n) ; dans les autres cas c'est Alice qui regrette son choix.

Rq : Il n'y a donc pas d'équilibre si Gulliver joue sa stratégie prudente. Comme les équilibres d'un jeu à deux joueurs à somme nulle sont forcément des couples de stratégies prudentes, le jeu n'admet pas d'équilibre.

Observons qu'Alice ne peut garantir mieux que 0 en jouant les deux dernières stratégies.

Observons que les deux premières stratégies d'Alice sont strictement dominées par la dernière.

Supposons que Gulliver choisit 'c' aléatoirement trois fois sur quatre. Son gain moyen suivant le choix d'Alice est alors la moyenne pondérée de ses gains moyens lorsqu'il joue 'c' ou 'l' ; on obtient le tableau suivant des gains de Gulliver (et non plus d'Alice):

$ \begin{array} {|c|c|c|c|c|} \hline \textrm{Gulliver} \setminus \textrm{Alice} & \textrm{(n,n)} &\textrm{(n,r)} & \textrm{(r,n)} & \textrm{(r,r)} \\ \hline \textrm{l:1/4, c:3/4} & 1 & 9/8 & -3/8 &-1/4 \\ \hline \end{array} $

Le gain moyen garanti de Gulliver devient -3/8, c'est mieux que -1/2 !

La meilleure réponse d'Alice à ce comportement est (r,n) (ne jamais mentir) : celle qui ne donne pas plus à Gulliver que ce qui lui est garanti, mais alors Gulliver regrette son choix : si Alice joue (r,n) il a intérêt à jouer constamment 'l' et on retombe dans la discussion de la question précédente. Ce n'est donc pas une position d'équilibre.

d. Gulliver choisit de contester “rouge” aléatoirement avec probabilité $p$ (stratégie dite "mixte"). Quelle valeur de $p$ optimise son gain moyen garanti ?

Quelle sont les meilleures réponses d'Alice à cette stratégie (dite stratégie mixte prudente) de Gulliver ?

Y a t-il parmi ces meilleures réponses une qui fait que Gulliver ne regrette pas son choix ? Comment cela s'interprète en terme d'équilibre ?

Réponse : Si Gulliver choisit la stratégie 'c' aléatoirement avec probabilité $p$, son gain moyen est donné par le tableau suivant :

$ \begin{array} {|c|c|c|c|c|} \hline \textrm{Gulliver} \setminus \textrm{Alice} & \textrm{(n,n)} &\textrm{(n,r)} & \textrm{(r,n)} & \textrm{(r,r)} \\ \hline \textrm{l:1-p, c:p} & 1 & 3p/2 & -p/2 &p-1 \\ \hline \end{array} $

Son gain moyen garanti est la plus petite de ces quatre valeurs.

Dessin :

In [6]:
var('p')
plot([1,3*p/2,-p/2,p-1],(p,0,1),legend_label=['y=1','y=3p/2','y=-p/2','y=p-1'])
Out[6]:

Sur le dessin on voit que le gain moyen garanti (le plus mauvais gain) est d'abord $p-1$ puis $-p/2$ avec un maximum là où ces deux expressions coïncident, c'est pour $p=2/3$.

In [7]:
solve(p-1==-p/2,p)
Out[7]:
[p == (2/3)]

Le gain moyen garanti de Gulliver est alors $2/3-1=-1/3$.

Les meilleures réponses d'Alice à cette stratégie mixte de Gulliver sont (r,n) ou (r,r) ou toute succession aléatoire de (r,n) et (r,r).

Si Alice joue (r,n) aléatoirement avec probabilité $q$ et (r,r) avec probabilité $1-q$, le gain moyen de Gulliver est $-pq/2+(p-1)(1-q)$. Gulliver ne regrette pas son choix si tout autre valeur de $p$ ne lui donne pas un meilleur gain que $-1/3$. Il suffit pour cela de tester en $p=0$ et en $p=1$ : le max sur le segment $[0,1]$ d'une fonction affine de $p$ (une fonction de la forme $p\mapsto ap+b$) est atteint en $0$ ou en $1$.

En $p=0$ le gain moyen de Gulliver est de $q-1$ ; en $p=1$ il est de $-q/2$. On veut $q-1,-q/2 \leq -1/3$ c'est à dire $q\leq 2/3$ et $2/3\leq q$ donc unique solution pour $q=2/3$.

Conclusion : si Alice joue la stratégie mixte (r,n) avec probabilité $2/3$ et $(r,r)$ avec probabilité $1/3$ (qui fait partie des meilleures réponses au choix $p=2/3$ de Gulliver), Gulliver ne regrette pas son choix $p=2/3$ ; c'est un équilibre.

Rq : (p,q)=(2/3,2/3) est un point selle de la fonction $(p,q)\mapsto -pq/2+(p-1)(1-q)$.

In [4]:
var('p,q')
plot3d(-p*q/2+(p-1)*(1-q),(p,0,1),(q,0,1),viewer='threejs')
Out[4]:
In [0]: