Un corrigé du devoir no 1 : méthode algorithmique

Soit le jeu donné par la matrice A=

1,-1,2,1 2,1,-3,0 0,1/2,-2,1/4

(3 lignes et 4 colonnes). On cherche les stratégies mixtes prudentes des joueurs 1 et 2.
Une stratégie mixte de J1 est un triplet de réels

x,y,z

vérifiant (1) x≥0, y≥0, z≥0 et x+y+z=1. Elle est prudente si elle maximise le plus mauvais gain, lequel s'exprime comme le minimum des trois colonnes du produit matriciel (x,y,z)*A=
x+2*y,-x+(y+1/2*z),2*x+(-3*y-2*z),x+1/4*z
(On a utilisé le multiplicateur de matrices de WIMS, voir la liste d'outils).
Notons f(x,y,z) le minimum des trois réels ci-dessus ; on cherche x,y,z  satisfaisant les contraintes (1) et maximisant  f . La fonction f est affine par morceaux sur un domaine convexe dont les coins sont les (x,y,z) égaux à

1,0,0 0,1,0 0,0,1

Les morceaux eux mêmes sont des parties convexes du plan d'équation x+y+z=1 et leurs coins sont solutions de l'équation

x+y+z=1

et de deux autres équations parmis

x=0 y=0 z=0 x+2*y=-x+(y+1/2*z) x+2*y=2*x+(-3*y-2*z) x+2*y=x+1/4*z -x+(y+1/2*z)=2*x+(-3*y-2*z) -x+(y+1/2*z)=x+1/4*z 2*x+(-3*y-2*z)=x+1/4*z

(Les 3 premières correspondent au bords du domaine, les 6 suivantes correspondent à un cas d'égalité parmis les fonctions dont f est le min.) Il y a 31 choix de 2 équations parmis les 9 ci-dessus sans redondance, ce qui donne avec l'équation de la contrainte x+y+z=1 31 systèmes de 3 équations aux inconus x,y,z, qu'on résoud avec la solveuse d'équations linéaires de WIMS.

Rq Formalisation par le calcul matriciel et utilisation de la calculatrice de matrice de WIMS : Posons B= 1,1,0,0,1,-1,2,1 1,0,1,0,2,1,-3,0 1,0,0,1,0,1/2,-2,1/4 Posons C= 1,0,0 0,1,0 0,0,0 0,0,0 0,0,1 0,0,-1 0,0,0 0,0,0 La solution x,y,z du système d'équations (pris en exemple) x+y+z=1 x=0 x+2*y=-x+(y+1/2*z) est le produit matriciel [1,0,0]*(B*C)^(-1) = 0,1/3,2/3 Posons D= 1,0,0 0,0,0 0,0,0 0,0,0 0,1,0 0,0,1 0,-1,0 0,0,-1 La solution x,y,z du système d'équations x+y+z=1 x+2*y=2*x+(-3*y-2*z) -x+(y+1/2*z)=x+1/4*z est le produit matriciel [1,0,0]*(B*D)^(-1) = -1/6,-5/6,2

Un système peut très bien ne pas avoir de solution ou une infinité de solutions ou une solution ne vérifiant pas les contraintes x≥0, y≥0, z≥0. Un coin correspond forcément à une solution unique vérifiant les contraintes ; on ne retient que de telles solutions. On obtient pour x,y,z les solutions suivantes :

0,0,1 0,1,0 1,0,0 0,1/3,2/3 0,1/9,8/9 1/5,0,4/5 2/3,0,1/3 5/11,0,6/11 1/9,0,8/9 9/13,0,4/13 5/6,1/6,0 4/7,3/7,0 1/3,2/3,0 3/4,1/4,0 1/7,2/21,16/21 7/10,1/30,4/15 8/17,1/17,8/17

On note P la matrice ci dessus. Le produit P*A est la matrice des gains moyen de J1 pour chaque stratégie pure de J2 :

0,1/2,-2,1/4 2,1,-3,0 1,-1,2,1 2/3,2/3,-7/3,1/6 2/9,5/9,-19/9,2/9 1/5,1/5,-6/5,2/5 2/3,-1/2,2/3,3/4 5/11,-2/11,-2/11,13/22 1/9,1/3,-14/9,1/3 9/13,-7/13,10/13,10/13 7/6,-2/3,7/6,5/6 10/7,-1/7,-1/7,4/7 5/3,1/3,-4/3,1/3 5/4,-1/2,3/4,3/4 1/3,1/3,-32/21,1/3 23/30,-8/15,23/30,23/30 10/17,-3/17,-3/17,10/17

Le minimum de chaque ligne est la valeur de f en la stratégie mixte de J1 correspondant à cette ligne :

-2 -3 -1 -7/3 -19/9 -6/5 -1/2 -2/11 -14/9 -7/13 -2/3 -1/7 -4/3 -1/2 -32/21 -8/15 -3/17

La plus grande valeur de f est -1/7 atteinte en la ligne 12 c'est à dire pour la stratégie mixte

4/7,3/7,0

On sait que f atteint son maximum en au moins l'un des coins des morceaux sur lesquels elle est affine et que l'ensemble des points où f est maximale est l'enveloppe convexe des coins où elle est maximale. Ici elle est maximale en le seul coin (x,y,z)=(4/7,3/7,0) donc (4/7,3/7,0) est la seule stratégie mixte prudente du joueur 1.

En remplaçant la matrice A par l'opposée de sa transposée et en reprenant la méthode ci-dessus on obtient les stratégies mixtes prudentes du joueur 2.