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. Utilité espérée

2.3.1. Critère d'Hurwitz

2.3.2. Critère de Laplace

3. Jeux évolutionnaires

4. Equilibre de Cournot

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 equation 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 equation (donc une issue n'est pas considérée comme un noeud !)

- D'un élément equation de D et d'une fonction p de equation dans D tel que :

equation   (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 equation des noeuds de décision de ce joueur vers l'ensemble D de tous les noeuds de décision du jeu telle que :

equation   (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.

Remarque: La fonction stratégie pure n'est que la fonction réciproque de tel que equation.

D4. Une "stratégie mixte" pour un joueur n est une distribution de probabilité equation avec equation sur l'ensemble de ses stratégies pures equation.

exempleExemple:

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.

Remarques:

R1. Une stratégie pure peut être regardée ainsi comme une stratégie qui donne la probabilité 1 à equation 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 equationequation est un élément de equation (donc un numéro de noeud) et equation une distribution de probabilité sur le sous-ensemble equation 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 equation, est une relation binaire sur l'ensemble des issues d'un jeu. Nous noterons equation et nous dirons que "x est au moins aussi bon que y". Nous pouvons alors définir la préférence stricte equation telle que :

equation   (19)

que nous lirons "x est préféré à y", et la relation d'indifférence :

equation   (20)

Remarque: Nous réutiliserons ces concepts en économétrie lors de notre étude de la théorie de la préférence.

D7. Une relation de préférence equation 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 equation qui associe les utilités retirées par chaque joueur.

Si U est une fonction d'utilité, nous noterons equation la fonction de l'ensemble des issues d'un jeu vers equation correspondant aux utilités d'u joueur i. Une telle fonction sera dite représentant de la relation de préférence equation si pour toute issue equation, nous avons :

equation   (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" equation est la donnée :

- d'un arbre de jeu equation

- 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

Remarque: Comme nous l'avons déjà précisé, un jeu sous forme développée est également dite "forme extensive", ou encore "arbre de Kuhn".

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.

Remarque: Nous pouvons remarquer que toues les jeux simultanés, c'est-à-dire dans lesquels les joueurs font leur choix en même temps, sont des jeux à information imparfaite. En effet, au moment de son choix, le joueur ne pas sur quel noeud de décision il se trouve.

Maintenant nous pouvons en venir à définir ce qu'est la matrice des gains :

D12. Un "jeu sous forme normale" equation 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 :

equation   (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 :

equation   (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 :

equation   (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" equation est la donnée :

- d'un jeu constitutif equation

- du nombre de répétition T

- du vecteur equation de taux d'escompte d'utilité, equation étant le taux d'escompte du joueur equation (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é equation 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 equation, alors l'utilité associée à l'issue du superjeu est :

equation   (25)

il est clair que si equation 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

Tableau: 10  - Préparation du jeu pour analyse graphique

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).

Remarques:

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

Tableau: 11  - Simplification du jeu pour analyse graphique

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

 
Tableau: 12  - Mise sous forme paramètrique du jeu pour analyse graphique

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 :

equation   (26)

et pour la société S2 :

equation   (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 :

equation   (28)

et la représentation graphique de v en fonction de p correspondante :

equation
  (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...) :

equation   (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 :

equation   (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 :

equation   (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