FORME ENSEMBLISTE d'un jeu
THÉORIE DES JEUX ET DE LA DÉCISION
1. Représentatives
1.1. Forme extensive d'un jeu
1.2. Forme extensive d'une décision
1.3. Forme normale d'un jeu
1.3.1. Jeux répétitifs
1.1. Forme ensembliste d'un jeu
1.2. Forme graphique d'un jeu
2. Jeux coopératifs et non-coopératifs
2.1. Optimum de Pareto
2.2. Equilibre de Nash
2.3.1. Critère d'Hurwitz
2.3.2. Critère de Laplace
5. Chaîne de Markov
Nous avons donc vu jusqu'à maintenant qu'il existe un certain nombre d'éléments qui composent un jeu : les joueurs, les actions et stratégies des joueurs, les déroulements et les étapes du jeu, les résultats du jeu et les informations dont disposent les joueurs de chaque choix d'action.
Définitions:
D1. Les règles d'un jeu indiquent :
- Les succession des étapes du jeu, et l'ordre dans lequel interviennent les joueurs
- Les actions qui sont autorisées à chaque étape
- Les informations dont dispose le joueur chaque fois qu'il doit prendre une décision
Nous avons vu qu'il y a deux formes de représentations possible pour un jeu jusqu'à maintenant. L'une d'entre elles utilise un arbre et l'autre une table (forme normale). Sous une expression formelle cela donne :
D2. Un arbre
de jeu 
est la donnée :
- D'un ensemble D de noeuds de décisions, ou situations de jeu
- D'un ensemble
I d'issues de jeu, avec 
(donc une issue n'est pas considérée comme un noeud
!)
- D'un élément
de D et d'une fonction p de 
dans D tel que :
(17)
appelée "fonction prédécesseur", qui pour chaque situation de jeu, ou issue, indique l'unique action (décision ou situation, d'où le fait que nous enlevons au moins un élément D de l'ensemble de départ) qui a permis d'arriver à cette situation, ou issue.
Pour déterminer l'issue d'un jeu, il suffit de connaître les stratégies utilisées par chacun des joueurs. Une stratégie est une combinaison d'actions autorisées par les règles du jeu jusqu'à la fin de celui-ci. Il existe plus précisément trois types de stratégies.
D3. Une "stratégie
pure" s pour un joueur n est une application de
l'ensemble 
des noeuds de décision de ce joueur vers l'ensemble D
de tous les noeuds de décision du jeu telle que :
(18)
Plus simplement dit, une stratégie pure est une stratégie ne faisant intervenir aucune forme de hasard, qui est donc complètement déterministe.
.D4. Une "stratégie
mixte" pour un joueur n est une distribution de
probabilité
avec 
sur
l'ensemble de ses stratégies pures 
.
Exemple:
Les tirs aux buts (penaltys) sont une forme de jeu à stratégie mixte. Effectivement, le gardien de but doit anticiper le tir en ne peut l'analyser. Il doit donc choisir au hasard s'il restera au milieur, s'il ira à gauche ou à droite. Idem, pour l'attaquant (normalement le gardien doit se lancer au moment mêment où l'attaquant tire) qui ne sachant pas où se lancera la gardien tirera donc au hasard.
R1. Une stratégie
pure peut être regardée ainsi comme une stratégie
qui donne la probabilité 1 à 
et 0 à toutes les autres.
R2. Dans notre définition de l'ensemble des stratégies, il y a un nombre fini de stratégies pour chaque agent mais en économie, les ensembles des stratégies sont souvent continus et contiennet une infinité de stratégies possibles (choix de quantité, de prix, etc.).
Naturellement, le résultat obtenu par le joueur ne peut pas être garanti de façon certaine, puisque le processus de choix de la décision fait intervenir des probabilités.
Une stratégie pure est donc une stratégie faisant le choix d'une parmi toutes les stratégie mixtes et qui utilise celle-ci durant toute la durée de jeu. Un joueur utilisant une stratégie mixte face à un joueur utilisant une stratégie pure utilisera (sera forcé) donc lui aussi d'utiliser une stratégie pure pour une rencontre, mais n'utilisera pas toujours la même stratégie pure lors de toutes leurs rencontres.
D5. Une "stratégie
de comportement" pour un joueur n est un ensemble 
où 
est un élément de 
(donc un numéro de noeud) et 
une distribution de probabilité sur le sous-ensemble 
des successeurs de noeud de décision i.
D6. Une "combinaison stratégique" est un vecteur de stratégies dont chaque élément correspond à la stratégie utilisée par un joueur participant au jeu.. La donnée d'une combinaisons stratégique détermine donc de manière complète l'issue du jeu.
Les joueurs
doivent avoir des préférences parmi les issues qui
sont à leur portée. C'est avec la définition
des ces préférences que nous pouvons caractériser
la rationalité d'un joueur. La relation de préférence
que nous noterons 
,
est une relation binaire sur l'ensemble des issues d'un jeu. Nous
noterons 
et nous dirons que "x est au moins aussi bon que y".
Nous pouvons alors définir la préférence
stricte 
telle que :
(19)
que nous lirons "x est préféré à y", et la relation d'indifférence :
(20)
D7. Une relation
de préférence
est dite "relation rationnelle", si elle est complète
(réflexive)
et transitive. Dans ce cas, comme nous l'avons vu dans le chapitre
des opérateurs (section arithmétique), nous avons
affaire à un préordre.
D8. Une "fonction
d'utilité", ou encore "fonction
de paiement" ("payoff function"
en anglais) est une fonction de l'ensemble des issues d'un jeu
à n joueurs vers 
qui associe les utilités retirées par chaque joueur.
Si U
est une fonction d'utilité, nous noterons 
la fonction de l'ensemble des issues d'un jeu vers 
correspondant aux utilités d'u joueur i. Une telle
fonction sera dite représentant de la relation de préférence
si pour toute issue 
,
nous avons :
(21)
La théorie de l'utilité qu'utilise la théorie des jeux, axiomatise le fait que seule cette notion de préférence est importante. En bref, nous dirons que seul l'ordre de préférence de l'utilité des issues est important, la valeur des gains apportés par chaque issue étant sans importance.
Nous pouvons maintenant étendre la définition du jeu :
D9. Un "jeu
sous forme développée" 
est la donnée :
- d'un arbre
de jeu
- d'un ensemble N de joueurs
- d'une fonction d'utilité U qui donne pour un joueur donné son gain
- d'un ensemble de partition d'informations F, dont chaque élément est une partition de D et indique les états du jeu que le joueur est capable de distinguer
D10. Une jeu est à "information complète" quand chaque joueur connaît l'ensemble des composantes du jeu, et à "information incomplète" sinon. Il est à noter que de parler d'un jeu à information complète revient à dire que F ne contient qu'une seule partition et donc que les joueurs n'ont qu'une seule vue sur l'arbre de jeu.
D11. Un jeu est à "information parfaite" quand l'unique élément de F se réduit à une partition de D où chaque noeud de décision forme un sous-ensemble, c'est-à-dire que chaque élément de la partition est un noeud de l'arbre et réciproquement. Plus simplement, nous pouvons dire que dans ce cas les joueurs peuvent savoir à chaque instant quel noeud de l'arbre est atteint. Dans le cas contraire le jeu est dit à information imparfaite.
Maintenant nous pouvons en venir à définir ce qu'est la matrice des gains :
D12. Un "jeu
sous forme normale" 
est la donnée :
- d'un ensemble N de joueurs
- d'un ensemble S de combinaisons stratégiques
- d'une fonction d'utilité U définie sur S
Ainsi, un jeu sous forme normale est également dit sous forme stratégique. Nous simplifions d'ailleurs la donnée du jeu à la donnée de la fonction d'utilité, sous la forme d'une matrice de gain (ou de paiement).
D13. Un jeu est "concurrentiel pur" ou "strictement compétitif" si :
(22)
Donc un jeu est strictement compétitif si pour un ensemble couple d'issues, les gains d'un au moins des joueurs diminue. Si les deux joueurs ont pour un couple d'issues, leurs gains respective qui augment ou diminuent respectivement, alors nous avons :
(23)
le jeu n'est dès lors plus strictement positif. Nous en avons par ailleurs donné des exemples au début de ce chapitre.
D14. Un jeu strictement compétitif est un "jeu à somme nulle" si :
(24)
Un jeu est à somme nulle quand les intérêts des joueurs sont diamétralement opposés. Dans un jeu à deux joueurs à somme nulle, par exemple, ce qui est gagné par l'un est perdu par l'autre. Ce terme trouve son origine dans les jeux de salon comme le poker où un joueur qui veut gagner de l'argent doit le faire aux dépens des autres. Les échecs sont un jeu à somme nulle.
D15. Un "superjeu"
est la donnée :
- d'un jeu
constitutif 
- du nombre de répétition T
- du vecteur
de taux d'escompte d'utilité, 
étant le taux d'escompte du joueur 
(souvent pris comme égal à l'unité)
Ainsi, comme
nous en avons déjà fait mention lors de notre jeu
répétitif GDS2, nous considérons qu'à
une étape t le choix dicté par une combinaison
stratégique s au joueur n est noté 
et que l'utilité, pour ce même joueur, obtenu à
cette étape du jeu, c'est-à-dire l'utilité
issue du jeu constitutif correspondant, est notée 
,
alors l'utilité associée à l'issue du superjeu
est :
(25)
il est clair
que si 
nous retrouvons une définition intuitive simple de la cumulation
des gains.
FORME GRAPHIQUE D'UN JEU
Nous avons maintenant amassé suffisamment d'élément pour avoir une approche probabiliste et opérationnelle de jeux à somme nulle relativement simples.
Comme il est toujours relativement difficile d'être trop théorique pour que ce domaine reste compréhensible étudions les formes graphiques via un exemple.
Considérons deux sociétés que nous nommerons respectivement S1 et S2 qui sont spécialisées dans la vente à grande échelle d'un certain produit et qui forment un oligopole bilatéral en concurrence parfaite (cf. chapitre d'Économétrie). La société S1 décide d'investir un nouveau marché, constitué par un ensemble de régions d'importances comparables.
La pénétration dans différentes régions s'opère grâce à l'installation d'un présentoir dans une chaîne de magasins C1 ou C2 dans chacune des région. Pour mieux motiver ses détaillants, la société S1 ne choisira qu'une seule chaîne de distribution (C1 ou C2) par région pour vendre ses produits.
La société S2 ayant pris connaissance du projet de la société S1 décide alors aussi d'investir le marché de manière similaire.
Le problème pour chaque société est de savoir, pour chaque région, s'il vaut mieux faire installer un présentoir dans la chaîne de magasins C1 ou C2 ou ne pas en faire installer du tout, c'est-à-dire nulle part (ce que nous noterons NP).
Suite à une étude de marché (il faut bien obtenir au moins quelques chiffres au départ pour faire des maths...) la société S1 apprend que ses gains par rapport au concurrent seraient ceux représentés dans le tableau ci-dessous :
S1 / S2 |
C1 |
C2 |
NP |
C1 |
0 |
2 |
4 |
C2 |
6 |
-3 |
8 |
NP |
-3 |
-5 |
0 |
La société S2 arrive au même résultat suite à une étude de marche (nous simplifions par cette hypothèse l'analyse du problème).
R1. Puisque tout ce gagne un concurrent serait perdu par l'autre, le jeu est à somme nulle (d'où le fait qu'il n'y ait qu'une seule valeur dans chaque cellule)
R2. Nous supposerons que les deux sociétés ne peuvent et ne veulent pas communiquer entre elles, en d'autres termes qu'il s'agit d'un jeu non coopératif.
Commençons par analyser quelles sont les stratégies qui n'ont aucun intérêt pour l'une ou l'autre des sociétés.
Pour cela, regardons s'il y a une stratégie qui ne sera jamais choisie par S1 quelque soit la stratégie de S2 :
1. Si S2 choisit C1 alors S1 aura pour meilleur intérêt à choisir C2
2. Si S2 choisit C2 alors S1 aura pour meilleur intérêt à choisir C1
2. Si S2 choisit NP alors S1 aura pour meilleur intérêt à choisir C2
Nous voyons ici que quelque soit le choix de S2, la société S1 ne choisira jamais NP. Donc la stratégie NP pour S1 est totalement dominée et peut être éliminée.
De même, regardons s'il y a une stratégie qui ne sera jamais choisie par S2 quelque soit la stratégie de S1.
1. Si S1 choisit C1 alors S1 aura pour meilleur intérêt à choisir C1
2. Si S1 choisit C2 alors S1 aura pour meilleur intérêt à choisir C2
3. Si S1 choisit NP alors S1 aura pour meilleur intérêt à choisir C2
Nous voyons ici que quelque soit le choix de S1, la société S2 ne choisira jamais NP. Donc la stratégie NP pour S2 est totalement dominée et peut être éliminée.
Le tableau se simplifie alors de la manière suivante :
S1 / S2 |
C1 |
C2 |
C1 |
0 |
2 |
C2 |
6 |
-3 |
Par ailleurs, ce jeu ne contient pas d'équilibre de Nash (donc aucune stratégie pure n'est avantageuse). Il est donc sans équilibres. Effectivement, si S1 choisit C1 alors S2 a intérêt à choisir aussi C1. Mais S1 à alors meilleur intérêt à jouer C2. Mais S2 a maintenant intérêt a choisir plutôt C2. Ce qui redonne à S1 l'envie de choisir C1...
Etudions maintenant l'aspect ensembliste, en d'autres termes l'aspect du jeu qui va donner la stratégie mixte à opter par S1 avec la répartition du choix ad hoc pour que celle-ci ait un gain maximal.
Pour cela, appelons p et q les fréquences avec lesquelles les sociétés S1 et S2 choisissent la chaîne de magasin C1.
S1 / S2 |
C1 |
C2 |
|
C1 |
0 |
2 |
p |
C2 |
6 |
-3 |
1-p |
q |
1-q |
Ces probabilités doivent être interprétées comme de la manière suivante :
1. Si p et q sont égaux à l'unité alors pour toutes les régions ce sera la chaîne C1 qui s'occupera de la commercialisation
2. Si p et q sont par exemple 9/11 et respectivement 5/11 cela signifiera que la société S1 donnera le droite de vente à la chaîne de magasins C1 dans 9 régions sur 11 (les deux restantes étant pour C2) et respectivement la société S2 donnera le droite de vente à la chaîne de magasins C1 dans 5 régions sur 11 (les 6 restantes étant pour C2).
Donc commençons notre étude. Nous allons nous mettre dans une optique d'analyse dans laquelle la société S1 cherche sa stratégie mixe de manière à maximiser son gain (ou utilité) que nous noterons v et à connaître la stratégie mixte de la société S2 afin qu'elle minimise sa perte v (puisque c'est un jeu à somme nulle et tout ce que gagne l'un l'autre le perd).
Le système d'équation sera alors naturellement pour la société S1 :
(26)
et pour la société S2 :
(27)
Or, nous retrouvons ici une situation remarquable. Effectivement il ne s'agit que de deux formes standards de programmation linéaire (cf. chapitre de Méthodes Numériques). Nous avons vu lors de notre étude de celle-ci que lorsqu'il y a qu'une seule inconnue par forme (ou système) alors il est possible de passer par une résolution graphique sans faire usage de l'algorithme du simplexe.
Après simplification cela donne :
(28)
et la représentation graphique de v en fonction de p correspondante :
(29)
En résolvant avec l'algorithme du simplexe nous avons comme valeurs optimales pour les deux systèmes respectifs (il est aussi possible de lire la valeur approximative sur les graphiques mais bon...) :
(30)
La société S1 peut par conséquent se garantir un gain moyen v (nous devrions parler "d'espérance" pour être rigoureux) de 12/11. Effectivement :
(31)
et la probabilité p donnant au fait la distribution entre les chaînes de magasin C1 qui aura 9/11 du marché de l'ensemble des régions et C2 le reste soit 2/11 (la somme devant faire bien évidemment 1).
La société S2 peut par conséquent se garantir aussi un gain moyen v de 12/11. Effectivement :
(32)
et la probabilité q donnant la distribution entre les chaînes de magasin C1 qui aura 5/11 du marché de l'ensemble des régions et C2 le reste soit 6/11.
page suivante : 2. Jeux coopératifs et non-coopératifs
