Corrigé des devoirs no 1 et 2 utilisant la question 1 (une ligne est dominée dans l'extension mixte du jeu) et la notion de meilleure réponse

On calcule avec la calculatrice de matrice de WIMS.

Devoir no 1. (corrigé succint du devoir no 2 plus bas)
Soit le jeu de matrice A=
1,-1,2,1
2,1,-3,0
0,1/2,-2,1/4

1. On veut montrer que la stratégie pure 3 est dominée par une stratégie mixte de la forme (p,1-p,0). Les gains moyens de J1 pour une telle stratégie mixte et pour chacune des stratégies pures de J2 est donné par le produit matriciel [p,1-p,0]*A=
-p+2,-2*p+1,5*p-3,p
et on veut trouver p dans l'intervalle [0,1] tel que chacune des coefficients du vecteur ci-dessus soit supérieur au coefficient correspondant (ie de même colonne) de la ligne 3 de A. Autrement dit on doit avoir  -p+2≥0 , -2*p+1≥1/2 , 5*p-3≥-2 et p≥1/4
p=1/4 est l'unique solution et deux des inégalités ci-dessus sont des égalités de sorte que la stratégie pure 3 est dominée au sens large mais n'est pas strictement dominée.
On en déduit que le joueur 1 admet une stratégie mixte prudente de la forme (p,1-p,0), mais il admet peut être aussi des stratégies mixtes de la forme (p1,p2,p3) avec p3≠0. On en déduit également que les stratégies mixtes du joueur 2 sont les mêmes que celle pour le nouveau jeu obtenu en supprimant la ligne 3. Dans ce nouveau jeu la colonne 1 est strictement dominée par la colonne 2 donc les stratégies mixtes prudentes du joueur 2 sont de la forme (0,q1,q2,q3).

2. Recherche des stratégies mixtes prudentes de J1 de la forme (p,1-p,0) et des stratégies mixtes prudentes de J2.
D'après ce qui précède on est ramené au jeu de matrice B=
-1,2,1
1,-3,0
Le plus mauvais gain moyen que craint J1 en jouant (p,1-p) est le min des trois composantes du produit matriciel [p,1-p]*B=
-2p+1,5p-3,p
Notons f(p) le min de ces trois réels. La fonction f est affine par morceaux sur l'intervalle [0,1] et les morceaux sont des intervalles d'extrémités 0,1 et les p égalisant deux des termes ci-dessus.
-2p+1=5p-3 donne p=4/7
-2p+1=p donne p=1/3
5p-3=p donne p=3/4
On sait que f est maximale en l'une de ces 5 extrémités et que l'ensemble des points où f est maximale est l'enveloppe convexe dans [0,1] des extrémités où f est maximale.
Notons P la matrice des (p,1-p), avec p donné ci-dessus : P=
1,0
0,1
4/7,3/7
1/3,2/3
3/4,1/4
Les valeurs de f en chacun des p ci dessus sont les coefficients minimaux des lignes du produit P*B=
-1,2,1
1,-3,0
-1/7,-1/7,4/7
1/3,-4/3,1/3
-1/2,3/4,3/4
f(p) vaut respectivement
-1
-3
-1/7
-4/3
-1/2
Le max de f est -1/7 (troisième ligne) atteint en la seule extrémité p=4/7 donc (p,1-p)=(4/7,3/7) est la seule stratégie mixte prudente de J1 pour le jeu de matrice B donc (4/7,3/7,0) est la seule stratégie mixte prudente de J1 de la forme (p,1-p,0) pour le jeu initial de matrice A.
On peut aussi tracer le graphe des fonctions de p : -2p+1,5p-3,p et en déduire le graphe de f avec lequel on lit le tableau de variation de f :


Une stratégie mixte prudente (q1,q2,q3) de J2 pour le nouveau jeu de matrice B est forcément une meilleure réponse à la stratégie mixte prudente (4/7,3/7) de J1. En calculant le produit [4/7,3/7]*B=
-1/7,-1/7,4/7
On voit que la colonne 3 n'est pas une meilleure réponse. Les stratégies mixtes prudentes de J2 sont donc de la forme (q,1-q,0). En jouant une telle stratégie J2 craint la plus grande perte donnée comme le max des deux composantes du produit B*[q,1-q,0]=
-3*q+2
4*q-3
Notons g(q) le max de ces deux composantes. La fonction g est affine par morceaux. Les morceaux ont pour extrémité 0,1 et la valeur de q égalisant les deux composantes ci-dessus :
-3*q+2=4*q-3 donne q=5/7.
On a g(0)=2>g(5/7)=-1/7<g(1)=1 donc g est minimale en le seul point q=5/7 donc (5/7,2/7,0) est la seule stratégie mixte prudente de J2 pour le jeu de matrice B puis (0,5/7,2/7,0) est la seule stratégie mixte prudente de J2 pour le jeu initial de matrice A.

3. Recherche des éventuelles autres stratégies mixtes prudentes de J1 pour le jeu initial.
Une stratégie mixte prudente (p1,p2,p3) de J1 pour le jeu initial est forcément une meilleure réponse à la stratégie mixte prudente (0,5/7,2/7,0) de J2. En calculant le produit A*[0,5/7,2/7,0]~ =
-1/7
-1/7
-3/14
on voit que la ligne 3 n'est pas une meilleure réponse donc les stratégies mixtes prudentes de J1 sont forcément de la forme (p,1-p,0). (4/7,3/7,0) est la seule stratégie mixte prudente de J1 de cette forme.


Devoir no 2.
Jeu de matrice A=
1/2,7/4,0,3/2
0,3,2,2
2,-2,3,1
Stratégie pure 1 dominée par (0,3/4,1/4) mais pas strict. dominée ; J1 admet une stratégie mixte prudente de la forme (0,p,1-p). colonne 3 strictement dominée après élimination de la ligne 1 d'où le nouveau jeu B=
0,3,2
2,-2,1
(p,1-p) prudente ssi elle maximise f(p)=min([0,p,1-p]*A)=min(-2p+2,5p-2,p+1) fonction affine par morceaux sur [0,1], les morceaux ayant pour extrémité 0,1/3,4/7,3/4,1.

Le max de la fonction f est atteint pour p=4/7 uniquement donc (0,4/7,3/7) est la seule stratégie mixte prudente de J1 de la forme (0,p,1-p) pour le jeu initial.
Stratégie mixte prudente de J2 : On calcule [4/7,3/7]*B=
6/7,6/7,11/7
La colonne 3 de B n'est pas une meilleure réponse à la strat. mixte prudente de J1 donc (q,1-q,0) seule forme possible.
(q,1-q,0) est prudente pour J2 si elle minimise max(B*[q,1-q,0]~)=max(-3q+3,4q-2), fonction minimale en q=5/7 uniquement ; donc (5/7,2/7,0) est la seule stratégie mixte prudente de J2 pour le nouveau jeu de matrice B donc (5/7,2/7,0,0) est la seule stratégie mixte prudente de J2 pour le jeu initial.
On calcule A*[5/7,2/7,0,0]=
6/7
6/7
6/7
Toute les stratégies de J1 sont des meilleures réponses à la stratégie mixte prudente de J2 ; il faut un auter argument pour conclure.
On connaît la valeur de l'extension mixte du jeu : max(f)=6/7. Les stratégies mixtes prudentes de J1 pour le jeu initial sont exactement les stratégies mixtes (x,y,z)  vérifiant : toutes les composantes de [x,y,z]*A=
1/2x+2z,7/4x+3y-2z,2y+3z,3/2x+2y+z
sont ≥ 6/7. On écrit z=1-x-y et on résoud graphiquement les 4 inégalités dans le plan sous les contraintes x≥0, y≥0, x+y≤1.
-3/2x-2y+8/7≥0
15/4x+5y-20/7≥0
-3x-y+15/7≥0
1/2x+y+1/7≥0
L'égalité à la place de l'inégalité donne les 4 droites d1, d2, d3, d4. On a d1=d2. L'ensemble solution de chacune des inégalités est un demi-plan délimité par l'une des droites d1,..,d4.

On voit que l'ensemble solution des 4 inégalités avec les contraintes x≥0, y≥0, x+y≤1 est le segment [A,B] où A est l'intersection de d1 avec l'axe des ordonnées, ie A=(0,4/7), B est l'intersection des droites d1 et d3 soit B=(44/63,1/21).
On obtient que l'ensemble des stratégies mixtes prudentes de J1 est l'enveloppe convexe des deux stratégies mixtes (0,4/7,3/7) et (44/63,1/21,16/63), c'est à dire le segment {x(0,4/7,3/7)+(1-x)(44/63,1/21,16/63), x∈[0,1]}.

F-X Dehon, 19 jan 2011, dessins obtenus avec WxGéométrie.