éUniversité de Nice Sophia Antipolis

De
Publié par

Niveau: Supérieur, Licence, Bac+2
éUniversité de Nice-Sophia Antipolis Département de Mathématiques Théorie des jeux Optimisation Chaînes De Markov Décision DEUG MASS 2 :OPTION année 2004-2005 D.SOUBIRAN-ZONE

  • paires de stratégies optimales pour les joueurs

  • durée de l'examen final

  • paiement

  • matrice des paiements

  • révision des programmes d'optimisation sans contraintes

  • stratégie x1


Publié le : mardi 29 mai 2012
Lecture(s) : 32
Source : math.unice.fr
Nombre de pages : 42
Voir plus Voir moins

é
Université de Nice-Sophia Antipolis
Département de Mathématiques
Chaînes
DDee
Markov
Décision
TThhééoorriiee ddeess jjeeuuxx OOppttiimmiissaattiioonn


DEUG MASS 2 :OPTION année 2004-2005
D.SOUBIRAN-ZONE















2 ANALYSE de la DECISION
année 2002-2003 Cours (26h) : D.Soubiran-Zone TD (26h) :D.Lamberger/B.Rousselet

semaines de 1 à 5 :

Ch.1 : Les outils du décideur. L’importance de l’information.
Jeux à deux joueurs et à somme zéro.
Jeux ayant une valeur, les points selles, les stratégies optimales.
Les stratégies mixtes.
Stratégies dominantes, réduction d’une matrice de paiement.

Ch.2 : Les processus de Markov. Les matrices stochastiques, les matrices de transitions.
Marches aléatoires sur des graphes. Etats absorbants. Comportement à long terme.
Applications.

Semaine 6 ou 7 : test n°1

semaines de 7 à 13 :

Ch.3 : Loteries. Utilité espérée. Révision des programmes d’optimisation sans contraintes.
Programmes d’optimisation avec contraintes du type g(x)=0 et h(x) 0.
CNPO, CSSO, fonctions convexes, fonctions concaves, formes quadratiques définies
positives, définies négatives, semi-définies.

Ch.4 : La théorie de la décision. L’interprétation subjectiviste.
Valeur monétaire espérée (VME), Perte d’opportunité espérée (POE), calcul avec les probabilités corrigées,
valeur de l’information parfaite (VIPE).

** Vous avez la possibilité de poser vos questions relatives au cours du lundi par mail (zone@unice.fr) jusqu’au
jeudi 12h, seules les questions bien posée auront un droit de réponse !
Les réponses seront soit adressées avant le lundi suivant, soit intégrées dans le poly si des commentaires se révèlent
utiles.

*** Ni documents ni machines programmables autorisés pendant le test et l’examen final.
i.e. vous n’avez droit que à une calculette 4 opérations.
*** Durée du test : 2h. Durée de l’examen final : 3h.

N.B.)Des petits contrôles seront programmés en TD pour permettre une notation pondérée de contrôle
continu, la présence est donc indispensable. Les salariés et dispensés de TD sont priés de communiquer
leur nom au plus tard le lundi 24 février.












Ch1. Les jeux mathématiques.



§1.1 Jeux à deux joueurs et à somme zéro :

Si deux joueurs X et Y s’affrontent, dans un soucis de simplification on notera X l’ensemble des stratégies possibles du
joueur X et Y l’ensembles des stratégies possibles du joueur Y :
Déf.1 : On appellera alors jeux à deux joueurs et à somme zéro le triplet (X,Y,u) avec :
X={x X, avec x stratégie possible du joueur X et i= 1,2,…..n ; si le joueur X dispose de n stratégies possibles} i i
Y={y Y, avec y stratégie possible du joueur Y et i= 1,2,… m ; si le joueur Y dispose de m stratégies possibles} i i
U : X×Y →R une fonction continue, qui à toute paire de stratégies (x,y) X×Y associe le paiement r R
(x,y) →u(x,y) = r R
Par convention on assumera ici que r est la somme que Y doit paye à X.
(Il va de soi que on aurait pu assumer que r est la somme que X doit payer à Y, l’important étant de choisir des le départ et de s’y tenir !!)

§1.2 Représentation d’un jeu sous forme normale
Si on représente les n stratégies du joueur X en ligne et les m stratégies du joueur Y en colonne, la simple lecture
de la matrice n×m ayant comme entrées les valeurs de la fonction de paiement nous permettra une représentation
très commode du jeux.
Exemple (1) : y y y 1 2 3
X 2 + 1 11
X2 2 4 + 1
X 3 3 + 2 4

On lira donc : « si X choisit la stratégie x et Y choisit la stratégie y alors le joueur Y doit payer -2 au joueur X, i.e. X 1 1,
doit payer 2 à Y »
De même on lira : « si X choisit x et Y choisit y alors Y doit payer 2 à X, si X choisit x et Y choisit y alors X 3 2 3 3
payera 4 à Y, etc ….. »
Avec la convention relative au paiement il est évident que X doit choisir une stratégie qui maximise u(x,y), alors que Y
doit raisonnablement en choisir une qui le minimise.
Les deux joueurs sont supposés être également intelligents, rationnels et également informés.
Chacun est donc parfaitement capable d’effectuer le raisonnement de l’autre et d’agir de conséquence.

Si on reprend l’exemple (1) et on regarde la matrice des paiements successivement du point de vue de Y et de X, on peut
donc observer que :
Point de vue de Y « si X choisit x alors je dois choisir y (paiement minimum vu le choix de X), car ainsi je minimiserai 1 1
ma perte (je gagnerai 2 ), si X choisit x je choisirai et si X choisit x je choisirai y ».2 3 3
Point de vue de X « si Y choisit y , je choisirai x ou x (paiement maximum vu le choix de Y), si Y choisit y je choisirai 1 1 2 2
x ……… »3
Nous allons noter les choix de X et de Y respectivement en ligne et en colonne :

y y y 1 2 3
2 + 1 1 X - 2 1
X 2 4 + 1- 4 2
X - 4 3 3 + 2 4
-2 , Maxmin = Max ( -2, -4, -4) = choix de X -2 +2 +1
minMax = -2 , min (-2, 2,1) = choix de Y
4
--˛--------˛-˛-˛˛
Parmi les paiements minimaux proposés par Y il va de soi que X choisira le plus grand et parmi les paiements
maximaux proposés par X le joueur Y ne pourra que choisir le plus petit ! C’est la méthode du minMax et Maxmin.
Si Maxmin=minMax on dit que le jeu admet une valeur en stratégie pure et on notera
val (u) = Maxmin=minMax. Ici val (u) = -2


Exemple (2) :

y y y 1 2 3
X 1 + 1 1 -1 1
X -4 2 4 + 12
X -4 3 3 + 2 4
-1 , Maxmin = Max ( -1, -4, -4) = choix de X
-1 +2 +1
Minmax = -1 , min (-2, 2,1) = choix de Y


Maxmin=minmax, donc ce jeu admet une valeur en stratégie pure.

Exercice (1) : Soit le jeu à deux joueurs et à somme zéro représenté par la matrice de paiement suivante :
Déterminer, si elle existe, la valeur de ce jeu en stratégie pure.
Stratégies de Y
-1 1 + 1 + 1 1
Stratégies -3 2 3 + 2 + 2
De X 2 + 1 2 + 1 -2

1 3 + 4 + 1 -3
-1 +1 +4 +2 -1= Maxmin
-1=minMax

Solution :
Maxmin = -1 = minmax, donc valu = -1

Il semble légitime à ce stade de se poser la question « Les points P( x ,y ), Q(x ,y ), T(x ,y ) ayant tous pour 1 1 1 4 4 1
image dans R la valeur -1= val(u), correspondent-ils à des paires de stratégies optimales pour les joueurs ? »
A savoir : si le joueur X choisit la stratégie x et le joueur Y choisit y , ou si X choisit x et Y choisit y , ou si X 1 1 1 4
choisit x et Y choisit y , les deux joueurs sont-ils confrontés à des choix équivalents ? 4 1
Pour répondre à cette question il est indispensable de connaître et bien comprendre le paragraphe suivant :

§1.3 Les points selles
Un point S(x*, y*) est un point selle pour un jeux à deux joueurs et à somme zéro ssi :
(déf.2) u(x , y*) ≤ u(x*,y*) ≤ u(x*, y)
A savoir ‘’si X déplace son choix de stratégie de manière unilatérale de x* à une autre stratégie x≠x*, alors que Y
conserve son choix y*,
le paiement diminue (donc X s’auto-pénalise, car u(x,y*)≤ u(x*,y*)) et de même si Y modifie
son choix de y* à une autre stratégie y≠y* alors que X conserve le choix x* le paiement augmente (donc Y sera aussi
pénalisé, car u(x*,y*) ≤ u(x*, y))
Le point S(x*,y*) constitue ainsi le meilleur compromis possible entre les deux joueurs : ont parle alors de choix prudent.
Il ne faut jamais oublier que chaque joueur est parfaitement capable et dispose de toute l’information nécessaire pour simuler avec exactitude le raisonnement de
l’autre !
On peut désormais utiliser la (déf.2) pour répondre à la question posée à la fin de l’exercice (1) :
Si P( x ,y ) est un point selle alors le choix de stratégies (x ,y ) doit satisfaire: u(x , y ) ≤ u(x ,y ) ≤ u(x , y) 1 1 1 1 1 1 1 1
Or u(x,y )= -1 ou -2 ≤ u( x ,y ) = -1≤ u(x ,y) = -1 ou +1 donc P est un point selle. 1 1 1 1
5
--------------
Si Q(x ,y ) est un point selle alors le choix de stratégies (x ,y ) doit satisfaire: u(x , y ) ≤ u(x ,y ) ≤ u(x , y) 1 4 1 4 4 1 4 1
mais u(x,y )= -1 ou +1 ou +2 n’est pas toujours ≤ u(x ,y ) = -1 , la double inégalité de la (déf.2) n’est donc pas vérifiée : 4 1 4
Q ne peut pas être un point selle pour le jeu donné.
Vous pouvez maintenant facilement démontrer que T(x ,y ) ne sera pas un point selle ! 4 1
Le jeux admet donc un seul point selle : le point P(x ,y ). 1 1
X a donc une seule stratégie optimale : la stratégie x ; Y a aussi une seule stratégie optimale : la stratégie y . 1 1

Théorème 1 : Si l’ensemble S de tous les points selles d’un jeux est non vide ( S≠Ø) alors le paiement est le même
dans tous les points selles et ces derniers sont échangeables,
à savoir (x ,x ), (y ,y ) S × S ⇒ (x ,y ) S et (x ,y ) S. 1 2 1 2 1 2 2 1
Remarque : Le paiement commun à tous les points selles est la valeur du jeux, on note val (u) : u(S) ={val(u)}
Démonstration :
(1) Si (x ,y ) S alors la Déf.2 ⇒ (a) u(x , y ) ≤ u(x ,y ) ≤ u(x , y) , x≠ x y≠ y 1 1 1 1 1 1 1 1

si (x ,y ) S alors la Déf.2 ⇒ (b) u(x , y ) ≤ u(x ,y ) ≤ u(x , y) , x≠ x y≠ y2 2 2 2 2 2 2 2
donc en particulier
si dans (a) on choisit x=x et y=y on a : u(x , y ) ≤ u(x ,y ) ≤ u(x , y ) 2 2 2 1 1 1 1 2

si dans (b) on choisit x= x et y=y on a : u(x , y ) ≤ u(x ,y ) ≤ u(x , y ) 1 1 1 2 2 2 2 1
on peut alors observer le troisième terme de la première inégalité est égal au premier terme de la deuxième
inégalité et ceci ⇒ l’égalité des six paiements, avec en particulier u( x ,y )= u( x ,y )= val(u). 1 1 2 2
Nous venons donc de démontrer que le paiement est bien le même pour les différents points selles du jeu, car le
raisonnement se généralise très facilement pour un nombre de points selles supérieur à deux.

(2) Nous allons maintenant démontrer l’échangeabilité des points selles :
Pour ce faire on observe d’abord que la Déf.2 peut s’écrire autrement car:
u(x , y*) ≤ u(x*,y*) ≤ u(x*, y) équivalent à u(x*,y*) = sup u(x,y*) et u(x*,y*) = u(x*,y) inf
y Yx X
Au passage il est intéressant d’observer que un point (x*,y*) sera donc un point selle pour un jeu à deux joueurs
et à somme zéro ssi Déf.2’ : u(x*,y*) = u(x,y*) et u(x*,y*) = u(x*,y) sup inf
y Yx X
Ici donc u(x ,y )=u(x ,y )= sup (x,y ) et u(x ,y )=u(x ,y )= (x ,y) 1 2 2 2 2 1 2 1 1 inf 1
y Yx X
Ce qui permet d’affirmer que (x ,y ) est aussi un point selle. 1 2
De même u(x ,y )=u(x ,y )=…………., ce qui prouve que (x ,y ) est aussi un point selle. 2 1 1 1 2 1
Les points selles sont ainsi échangeables au sens précisé dans l’énoncé du Théorème 1 Q.E.D.

§1.4 Les stratégies optimales et l’existence de points selles pour un jeu.
A ce stade nous nous sommes limité à affirmer qu’une stratégie était optimale pour un joueur si elle était une
coordonnée d’un point selle (abscisse pour X, ordonnée pour Y).
Le moment est venu d’être plus précis.
Etant donné que tous les points selles d’un jeu ont même paiement et sont échangeables il existe un sous-ensemble
de X et un sous-ensemble de Y, que nous noterons O (et que nous appellerons l’ensemble de stratégies optimales X
du joueur X) et O (que nous appellerons l’ensemble de stratégies optimales du joueur Y) t.q.O × O = S Y X Y
Si X choisit une stratégie de O , alors contre toute défense de Y il sera certain d’obtenir un paiement au X
moins égal à la valeur du jeu.
Si Y choisit une stratégie de O , alors quelque soit le choix de X il sera certain de ne devoir payer plus Y
que la valeur du jeu.
X tente donc d’imposer un paiement compris entre val(u) et +∞ , alors que Y fera tout pour obtenir un
paiement compris entre -∞ et val(u).
6
"˛˛˛"˛"˛"˛"˛˛˛˛˛
Si un des deux joueurs choisit une stratégie ailleurs que dans son propre ensemble de stratégies optimales,
son adversaire peut exploiter la faute et gagner plus ! (ou perdre moins !)
Des joueurs rationnels et ‘’prudents’’ choisiront toujours l’issue du jeu qui leur attribuera la valeur du jeu !!
On ne peut donc parler de stratégies optimales (pures) que pour des jeux qui ont des points selles.
Le théorème suivant nous permet de caractériser l’existence de points selles (admis sans démonstration).

Rappel (1) :
Un ensemble A est compact si il est à la fois fermé et borné. (cf. rappels de mathématiques , ci joint)
2
Rappel (2) :Pour toute fonction f : X×Y ? R R il est toujours vrai que :
sup sup inf f(x,y) ≤ inf f(x,y)
y Y y Yx X x X
Théorème 2 : Si les ensembles X et Y sont compacts,
sup sup supinf inf u(x,y) = u(x,y) ⇒ S ≠ Ø et la val(u) =
y Y y Yx X x X x X
supinf inf=
y Y y Y x X
sup supet réciproquement Si S ≠ Ø ⇒ inf u(x,y) = inf u(x,y) =
y Y y Yx X x X
val(u)
**Pour la démonstration voir H.Moulin, p.15 « Théorie des jeux » Ed.Hermann

infThéorème 3 : Si S ≠ Ø une stratégie x*sera optimale pour le joueur X ssi u(x*,y)= val(u)
y Y
supet une stratégie y* sera optimale pour Y ssi u(x,y*)= val(u)
x X
Nous avons vu que le choix d’une stratégie optimale garantit au décideur un gain au moins égal à la valeur du jeu.
Une telle stratégie étant abscisse d’un point selle pour X et ordonnée pour Y, il est clair que un point selle constitue
une issue stable du jeu, car aucun joueur n’a intérêt à changer d’avis.
3Représentation dans R

u(x*,y*)





y
x

fig-1-

RRééfflléécchhiirr,, ppuuiiss ééccrriirree uunnee ddééffiinniittiioonn ppeerrttiinneennttee ddee ssttrraattééggiiee nnoonn ooppttiimmaallee..
Si certaines hypothèses ne sont pas vérifiées le jeu tout en admettant une valeur
sup supinf inf sans avoir de points selles ! On aura alors toujours u(x,y) = u(x,y)
y Y y Yx X x X
mais vous pourrez vérifier que inf u(x,y) ne peut atteindre son maximum sur X ou ……..
y Y
7
˛fi˛˛˛˛˛fi˛fi˛˛˛˛˛˛˛˛˛˛˛fi˛˛˛˛˛
Pour éviter toute « confusion » l’ecriture Maxmin=minMax, utilisée dans les exemples et les exercices Pour éviter toute « confusion » l’ecriture Maxmin=minMax, utilisée dans les exemples et les exercices
traités dans les pages précédentes, sera maintenant systématiquement remplacée par supinf=infsup
Je suppose que les raisons de cette nécessité sont maintenant claires pour tous ! Si non à vos e-mails !



****au travail !!!
vos propositions de démonstration complète avant vendredi 12h !


1) ( H.Moulin, p21)
2 Soient X= Y [0,1] les ensembles des stratégies possibles des joueurs X et Y, et soit u(x,y)= 1 –(x-y) la fonction
de paiement d’un jeu à deux joueurs et à somme zéro.
Démontrer que ce jeu n’admet pas de points selles.
Solution :
3
supinf u = sup inf= supinf u = sup inf=
4
infsup u = inf sup =1
donc pas de valeur en stratégie pure.



























8

Mr.X tire une carte dans un jeu et ne la montre pas.
Il peut choisir de donner un euro ou de demander un euro à son adversaire Mr.Y.
Ce dernier peut soit accepter de donner l’euro demandé soit de dire « menteur ».
A ce stade du jeu X doit montrer sa carte : si elle est rouge il reçoit 4 euros de Y, si elle est noire il doit payer 5
euros à Y.
Ecrire la matrice qui représente ce jeu et montrer que les joueurs n’ont pas de stratégies optimales en
stratégie pure. -1€


+1€

X
joue +4€
-1€

+1€



-5€

Une observation attentive de l’arbre de décision est suffisante pour réaliser que toutes les informations
nécessaires sont contenues dans le graphe.
1) Le joueur Y ne dispose que de deux stratégies : (D) donner 1€ ou (M)dire « menteur ! ».
Le joueur X dispose de quatre stratégies : il peut donner 1€si il a tiré une carte rouge et donner
1€ si il a tiré une carte noire i.e. x1= ( Donner, Donner)
il peut demander 1€ si il a tiré une carte rouge donner 1€
si il a tiré une carte noire i.e. x2=( Demander, Donner)
il peut donner 1€si il a tiré une carte rouge et demander
1€ si il a tiré une carte noire i.e. x3= ( Donner, Demander)
il peut demander 1€si il a tiré une carte rouge et
demander 1€ si il a tiré une carte noire i.e. x4= ( Demander, Demander)
La matrice aura donc 4 lignes et 2 colonnes.
Les paiements (entrées de la matrice) se calculent simplement en effectuant le « bon parcours » dans l’arbre
1 1
si X choisit x4, alors le paiement espéré de X est : (1) + (1)= +1 si Y choisit la stratégie (D)
2 2
1 1 1
et (-5) + (+4)= - si Y choisit la stratégie (M)
2 2 2
9
¤“§'
1 1
et ainsi de suite : si X choisit x3 , alors le paiement espéré de X est : (-1) + (1)= 0 si Y choisit la
2 2
1 1
stratégie (D) et (-1) + (-5)= -3 si Y choisit la stratégie (M)
2 2
1 1
si X choisit x1 alors le paiement espéré de X est : (-1) + (-1)= -1 si Y choisit la stratégie (D) et
2 2
1 1
(-1) + (-1)= -1 si Y choisit la st
2 2
et si X choisit x2 ……………..
Il est maintenant possible de fournir sans hésitation la matrice qui représente le jeu du menteur
1 1
3
0 +
2
0 3avec les règles énoncées :
1
+1
2
Si on observe de plus près on voit que la stratégie x1 est dominée par x2 et x3 est aussi dominée
3
0 +
2
par x2, donc la matrice se réduit à : 1
+1
2
Après élimination des stratégies dominées X choisira donc ou x2 ou x4, mais aucun des deux
joueurs a des stratégies optimales en stratégie pure car :
1 3
= - ≠ = sup supinf inf2 2Y YX X









10
-----

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.