Trouver un équilibre où il n’y

en a pas !

un petit exemple

L’exemple le plus simple possible où il n’y a pas d’équilibre évident:

( \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} )

Par symétrie, la valeur du jeu doit être 0, mais quelles sont les stratégies pour un joueur ou l’autre qui garantissent de ne pas être sous 0 (en moyenne) pour n’importe quelle stratégie de l’adversaire?

Réponse : une stratégie aléatoire ! Si je choisis entre les deux possibilités avec probabilités 0.5, 0.5, j’aurai une gagne moyenne de 0 contre toute stratégie de l’adversaire si elle soit déterministe ou également aléatoire.

Propriété paradoxale de cette stratégie aléatoire : si je la joue, le résultat (moyen) ne dépend pas de la stratégie de l’adversaire. Le bon choix pour tous les deux est de choisir cette stratégie mais il suffit que l’un d’eux le fasse pour garantir le résultat “correct”.

Il faut trouver les bonnes

probabilités

un autre exemple

Toujours 2 personnes somme nulle: ( \begin{matrix}1 & 3 \\ 5 & 2 \end{matrix} )

Pour le joueur qui choisit la ligne et veut maximiser la valeur, choisir chaque ligne avec probabilité 0.5 n’est pas optimal. En effet l’adversaire peut choisir la seconde colonne pour un résultat moyen de 2.5; le premier ferait mieux de choisir la première ligne avec probabilité 0.6 et il a une gagne garantie de 2.6.

C’est pareil pour l’autre : s’il choisit avec probabilité 0.5 pour chaque colonne, le premier peut jouer la seconde ligne pour 3.5. Il faut choisir la première colonne avec probabilité 0.2 pour garantir de restreindre la perte à 2.6.

Application au jeu des

tétradés

Après suppression de stratégies dominées (miser 5 sur un dé qui vaut 4) et numérotation des stratégies en binaire selon les 3 choix sur les autres valeurs, on a la matrice

( \begin{matrix}0 & −10 & 0 & −10 & 10 & 0 & 10 & 0 \\ 10 & 0 & −15 & −25 & −5 & −15 & −30 & −40 \\ 0 & 15 & 0 & 15 & −15 & 0 & −15 & 0 \\ 10 & 25 & −15 & 0 & −30 & −15 & −55 & −40 \\ −10 & 5 & 15 & 30 & 0 & 15 & 25 & 40 \\ 0 & 15 & 0 & 15 & −15 & 0 & −15 & 0 \\ −10 & 30 & 15 & 55 & −25 & 15 & 0 & 40 \\ 0 & 40 & 0 & 40 & −40 & 0 & −40 & 0 \end{matrix} )

Une stratégie qui garantit de ne pas perdre serait de choisir les premier et troisième lignes avec probabilités 0.6 et 0.4. Ça ne gagne rien en moyenne contre les autres stratégies montrées mais gagne contre les stratégies dominées.

C’est-à-dire qu’une stratégie optimale est de miser 20 toujours sur un dé de 4 et dans 40% des cas sur un dé de 2.

Un peu de terminologie

• Ce que j’appelais au départ une stratégie est une action

• Une stratégie mixte choisit entre deux ou plusieurs actions avec probabilités nonnulles

• Une stratégie pure choisit une seule action (avec probabilité 1)

• Le support d’une stratégie est l’ensemble d’actions choisies avec probabilité non-nulle.

Les équilibres instables

Le jeu des deux conducteurs

( \begin{matrix}1 & −10 \\ −10 & 1 \end{matrix} )

Il y a deux équilibres avec des stratégies pures (chacun va à gauche ou chacun va à droite). Il y a aussi un équilibre où chacun a la même stratégie (0.5, 0.5). Mais si l’un change un peu sa stratégie (mettons (0.51, 0.49)), l’autre ferait mieux de jouer (1, 0)

Les propriétés d’une solution

à stratégies mixtes

Si la (toutes les) stratégie optimale pour un joueur est mixte, il y a un autre joueur pour lequel c’est vrai aussi.

Si S1 et S2 sont deux stratégies constituant un point d’équilibre, alors le résultat reste le même pour le joueur 2 (et donc pour 1 si c’est un jeu somme nulle), si l’autre garde sa stratégie S1 et le joueur 2 joue la stratégie pure d’une action dans le support de S2.

Mais si le joueur 2 joue une autre tratégie pure, le résultat (pour le joueur 2) est inférieur (ou égal) à celui du point d’équilibre.

Le calcul de l’équilibre quand

les supports sont connus

(deux joueurs, somme nulle)

Il suffit d’utiliser le fait que chaque colonne donne le même résultat. Par exemple, si la matrice était

( \begin{matrix}1 & 5 & 8 \\ 10 & 2 & 4 \\ 4 & 6 & 3 \end{matrix} )

et je pensais que toutes les actionsétaient dans les supports des deux stratégies optimales, J’écrirais les équations:

x_{1} + 10x_{2} + 4x_{3}  = v
5x_{1} + 2x_{2} + 6x_{3}  = v
8x_{1} + 4x_{2} + 3x_{3}  = v
x_{1} + x_{2} + x_{3} = 1

pour la stratégie du premier joueur x_{1} = 0.285714, x_{2} = 0.257143, x_{3} = 0.457143, v = 4.685714 Ou, pour l’autre joueur:

x_{1} + 5x_{2} + 8x_{3}  = v
10x_{1} + 2x_{2} + 4x_{3}  = v
4x_{1} + 6x_{2} + 3x_{3}  = v
x_{1} + x_{2} + x_{3} = 1

pour la solution x_{1} = 0.271429, x_{2} = 0.471429, x_{3} = 0.257143, v = 4.685714 Mais il faut remarquer que, si les équations ne sont pas indépendantes, on doit choisir entre plusieurs solutions possibles.

Et si les supports ne sont

pas bons?

Soit les équations n’ont pas de solution,

soit la solution des équations sera impossible; valeurs inférieures à 0 et/ou supérieures à 1.

( \begin{matrix}1 & 4 & 7 & 3 \\ 0 & 5 & 2 & 6 \\ 5 & 2 & 4 & 4 \\ 6 & 1 & 1 & 3 \end{matrix} )

x_{1} = 0.441176x_{2} = 0.852941x_{3} = −0.058824x_{4} = −0.235294

soit la stratégie ne sera pas optimale; une action hors du support sera meilleur que la stratégie calculée.

La recherche de(s) bons

supports

• Pas d’algorithme très efficace en général.

• Essayer d’améliorer itérativement un ensemble initial de supports

• Si une probabilité devient négative, enlever l’action

• Si une action hors du support est meilleur que celles du support la rajouter

• Refaire le calcul des probabilités.

Un exemple d’un jeu qui

n’est pas somme nulle

Matrice du joueur 1 (qui choisit la ligne) ( \begin{matrix}1 & 3 \\ 4 & 2 \end{matrix} )

et du joueur 2 (qui choisit la colonne) ( \begin{matrix}4 & 1 \\ 1 & 2 \end{matrix} )

Le point d’équilibre est (1/4, 3/4), (1/4, 3/4) La valeur du jeu est de 2.5 et de 1.75 respectivement pour les deux joueurs. Ni l’un ni l’autre ne peut améliorer son résultat en déviant de sa stratégie mixte.

L’exemple des 3 stations de service

Nouveau modèle: marges 16% ou 11% ; 75% des clients indifférents aux prix ; 25% influencés par les prix (choisissent une station à bas prix s’il y en a)

• Par symétrie la stratégie optimale doit être la même pour chaque propriétaire

• Il n’y a pas de point d’équilibre avecla même stratégie pure pour chacun

• Donc, la stratégie optimale pour chacun est de choisir le prix élevé avec probabilité p et le prix bas avec probabilité q = 1 − p

• Comment calculer la probabilité correcte p ?

Le calcul

En supposant que les deux autres ont le prix élevé avec probabilité p Si j’ai le prix élevé mes gains moyens (exprimés en pourcentages du marché total) sont de 16(p^{2}/3 + (1 − p)^{2}/4 + 2p(1 − p)/4) mais si j’ai le prix bas, ils sont de 11(p^{2}/2 + (1 − p)^{2}/3 + 2p(1 − p)(3/8)).

Les deux doiventêtre pareilsà un point d’équilibre; (16/3 − 11/2)p^{2} + (16/4 − 11/3)(1 − p)^{2}+ (16/4 − 33/8)2p(1 − p) = 0. En multipliant par 12 −2p^{2} + 4(1 − p)^{2} − 3p(1 − p) = 0. Et en regroupant les termes 5p^{2} − 11p + 4 = 0, et alors p ≈ 0.543.