La Théorie des Jeux Le type de situations considérées

• Deux ou plusieurs participants

• Chacun décide sa stratégie : une action parmi plusieurs

• Chacun gagne une quantité qui dépend de sa stratégie et de celles des autres

• Pas de coopération

• Soit tout se passe d’un seul coup, soit plusieurs étapes : la stratégie est une description complète de ce qu’il faut faire pour toute situation possible

• Description par des matrices de la ”valeur” du jeu pour chaque joueur et pour chaque combinaison des stratégies de tous.

Applications

• Jeux réels : poker, bluffer ou non?,...

Un exemple simple: dé tétraédral; marqué 1, 2, 3, 4; deux joueurs misent 5 ou 20 euros; 20 gagne contre 5, sinon le vainqueur est déterminé par les deux dés. 5 stratégies permises (pour maintenant)

– S4: mise 20 si dé vaut (au moins) 4

– S3: mise 20 si dé vaut au moins 3

– S2: mise 20 si dé vaut au moins 2

– S1: mise 20 (si dé vaut au moins 1)

– Timide: mise toujours 5.

• Economie : concurrence, combien des déspenses de publicité? réduire les prix? augmente la part du marché mais réduit les marges.

• Diplomatie

• Guerre

Les jeux ”Somme nulle” et

autres

Souvent (jeux de hasard où un joueur gagne de l’argent des autres), pour n’importe quelle combinaison de stratégies, la somme des valeurs de tous les joueurs est toujours nulle.

Dan le cas particulier d’un tel jeu ”somme nulle” entre deux joueurs, il suffit une matrice pour décrire le jeu parce que la seconde matrice n’est que la négation de la première.

Tout jeu de n joueurs peut être transformé en jeu somme nulle de n + 1 joueurs, en ajoutant un nouveau joueur numéro n+1, dont la stratégie n’influence pas la valeur du jeu pour les autres et dont la valeur est toujours −(somme des valeurs des autres joueurs)

La nature d’une solution

C’est quoi la (une) stratégie optimale?

Pas une stratégie qui gagne contre toute stratégie des autres (probablement une telle stratégie n’existe pas).

Pas une stratégie qui gagne en moyenne contre des autres qui jouent aléatoirement (ils sont aussi intelligent et veulent gagner).

On suppose que tous les joueurs sont intelligents et capable des déscider leur stratégie optimale.

Et que chacun sait que tous les autres sont capables, etc. à l’infini !

Conclusion : chacun peut aussi décider quelle est la stratégie optimale de chaque autre !

Donc, chacun joue la stratégie qui lui donnerait la meilleur valeur du jeu si tous les autres font pareil.

Définition circulaire de la stratégie optimale ?

Equilibre

Toute combinaison de stratégies optimales, une pour chaque joueur, possède la propriété d’équilibre : si un joueur change sa stratégie, sa valeur du jeu va diminuer (ou peut-être rester inchangée).

Au lieu de chercher une stratégie optimale, on va chercher n stratégies ”optimales” qui possèdent cette propriété d’équilibre.

Nous allons voir que chaque jeu possède un tel point d’équilibre; mais seulement quand nous avons généralisé un peu l’idée d’une stratégie.

Trouver une solution 1:

Domination et élimination

Une stratégie A domine B si, pour toute stratégie des opposants, sa valeur est supérieure (ou égale).

Dans le jeu des dés, la stratégie timide est dominée par S4.

On peut éliminer les stratégies dominées et leurs lignes et colonnes des matrices.

Et peut-être maintenant d’autres seront dominées etc.

Ce processus peut amener à une situation où chaque joueur n’a qu’une seule stratégie; ces stratégies donnent forcément un point d’equilibre.

Trouver une solution 2: Les

Points ”Selle”

Dans un jeu somme nulle à deux joueurs Un point d’équilibre est forcément une selle (de la forme d’une selle de cheval ou une selle en montagne).

(Du point de vue d’un joueur), si lui change sa stratégie, la valeur du jeu diminue;

Donc, tous les points d’équilibre ont la même valeur.

Calcul de la stratégie optimale dans le jeu des dés

Calcul de la matrice des valeurs.

( \begin{matrix}0 & −80 & −45 & −20 & −5 \\ 80 & 0 & −40 & −40 & 0 \\ 45 & 40 & 0 & −20 & −10 \\ 20 & 40 & 20 & 0 & −10 \\ 5 & 0 & 10 & 10 & 0 \end{matrix} )

La stratégie S4 est la meilleure (parmi les 5 permises)

Une Difficulté : Plusieurs

équilibres possibles

a Un exemple:

• 2 stations de service à une intersection ont chacune 50% du marché

• chaque propriétaire sait que réduire les marges par 30% lui donnerait 70% du marché (si l’autre ne fait pas pareil)

• (prix haut, prix haut) est un point d’équilibre • (prix bas, prix bas) en est un autre

Une deuxième difficulté :

Aucun équilibre possible

• La même intersection 5 ans plus tard

• Une station modernisée, plus jolie, plus rapide a déja 60% du marché

• Si elle réduit le prix, elle aura 90%

• Mais si l’autre réduite ses prix elle ne mon-

tera qu’à 50% Peut produire une guerre continue de réductions et augmentations des prix! (Le jeu des dés peut être pareil si on permet la stratégie de Bluffer, miser 20 sur 1 et 4. Bluffer bat S4 mais S1 bat Bluffer.

Une troisième difficulté : l’équilibre n’est pas optimal

Le dilemme des prisonniers

• Deux prisonniers arrêtés pour un crime et intérrogés séparément

• Si les deux avouent, chacun aura une sentence de 5 ans

• Si les deux se taisent, chacun aura une sentence de 6 mois

• Si l’un avoue, il sera libéré et l’autre aura

10 ans. Avouer est la stratégie dominante. Mais le résultat est que les deux ont une sentence de 5 ans au lieu de 6 mois.