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:
(
)
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:
(
)
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
(
)
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 non-nulles
- 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
(
)
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
(
)
et je pensais que toutes les actions étaient dans les supports des deux stratégies optimales,
J'écrirais les équations:
pour la stratégie du premier joueur
x1=0.285714, x2=0.257143, x3=0.457143, v=4.685714
Ou, pour l'autre joueur:
pour la solution
x1=0.271429, x2=0.471429, x3=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.
(
)
x1=0.441176x2=0.852941x3=-0.058824x4=-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)
(
)
et du joueur 2 (qui choisit la colonne)
(
)
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.
File translated from
TEX
by
TTH,
version 3.05.
On 11 Oct 2007, 12:00.