Équilibre corrélé

En théorie des jeux, la notion d’équilibre corrélé est une généralisation du concept d'équilibre de Nash proposée pour la première fois en 1974 par le mathématicien Robert Aumann.

Celle-ci suppose l'existence d'un dispositif externe de corrélation, par exemple un "maître du jeu" auquel tous les joueurs font confiance. Celui-ci affecte leurs stratégies aux différents joueurs suivant une certaine loi de probabilité. On dit de cette loi que c'est un équilibre corrélé lorsque, quelles que soient les stratégies {s_i} attribuées aux joueurs, aucun joueur i n'aura intérêt à changer sa stratégie (connaissant s_i ainsi que la loi de probabilité suivie par le dispositif).

Définition formelle

Considérons un jeu à n joueurs où chaque joueur i choisit sa stratégie dans un ensemble S_i. La valeur reçue par le joueur i est notée $\displaystyle v_i(s_i, s_{-i})$. Soit une loi de probabilité p sur les vecteurs de stratégies $s \in \prod_i S_i$ : p(s) désigne la probabilité du vecteur s, que l'on écrira de manière équivalente $\displaystyle p(s_i, s_{-i})$ lorsqu'on s'intéressera au joueur i.

On dit que la loi de probabilité p est un équilibre corrélé lorsque, pour tout joueur i et toute stratégie $s_i \in S_i$, on a la relation :

$\forall s'_i \in S_i, \quad \sum_{s_{-i}} p(s_i, s_{-i}) v_i(s_i, s_{-i}) \;\geq\; \sum_{s_{-i}} p(s_i, s_{-i}) v_i(s'_i, s_{-i})$

En français, ceci se lit : « sachant que le joueur i s'est vu attribuer la stratégie s_i, il ne peut obtenir en moyenne de valeur perçue plus grande en optant pour une autre stratégie $\displaystyle s'_i$. »

La moyenne en question correspond à l'espérance de v_i sur les stratégies des autres joueurs, distribuées selon la loi p conditionnée par l'événement « le joueur i a reçu la stratégie s_i ». En d'autres termes, le raisonnement présente deux étapes : les joueurs reçoivent d'abord leurs stratégies, puis envisagent d'améliorer leurs valeurs moyennes en supposant que les autres ne changent pas de tactique. S'il n'y a d'amélioration possible pour aucun joueur, on a un équilibre corrélé.

Exemple

Jeu de la poule mouillée

	O	R
O	0, 0	7, 2
R	2, 7	6, 6

Considérons le jeu de la poule mouillée représenté ci-contre : deux joueurs s'affrontent, chacun ayant le choix entre deux stratégies, oser (O) ou renoncer (R). Si l'un ose, l'autre a tout intérêt à renoncer, et symétriquement, si l'un renonce, l'autre a tout intérêt à oser. Ce jeu représente donc une situation ou chacun souhaite « oser », mais seulement si son adversaire est susceptible d'abandonner.

Il y a trois équilibres de Nash : deux équilibres purs, (O,R) et (R,O)), ainsi qu'un équilibre mixte où chaque joueur « ose » avec probabilité 1 / 3.

Supposons maintenant l'existence d'un arbitre choisissant uniformément un couple de stratégies parmi (R,R), (O,R) et (R,O). Une fois le couple choisi, l'arbitre informe chaque joueur de sa stratégie (mais pas de la stratégie de son adversaire). Deux situations se présentent alors :

• Imaginons qu'un joueur reçoive O : il sait alors que son adversaire a reçu R et n'a pas intérêt à revenir sur sa stratégie.
• Imaginons qu'un joueur reçoive R : dans ce cas, son adversaire jouera O avec probabilité 1 / 2 et R sinon; la valeur moyenne perçue par le joueur s'il conserve la stratégie R est alors $1/2 \times 2 + 1/2 \times 6 = 4$, tandis que s'il décide de jouer O plutôt cette moyenne ne sera que de $1/2 \times 0 + 1/2 \times7 = 3,5$.

En définitive, aucun joueur n'a intérêt à revenir sur la stratégie que lui suggère l'arbitre : il y a équilibre corrélé. (On remarquera que la valeur moyenne perçue dans cet équilibre est alors $1/3 \times 7 + 1/3 \times 2 + 1/3 \times 6 = 5$, soit plus que celle obtenue avec l'équilibre de Nash mixte.)

Lien avec les équilibres de Nash

Lorsque p est la loi produit induite par n stratégies mixtes {p_i}, i.e. $p(s_1,...,s_n) = p_1(s_1) p_2(s_2) \cdots p_n(s_n)$, un équilibre corrélé est exactement un équilibre de Nash. En effet, la relation d'équilibre devient alors (après division par p_i(s_i))

$\forall s'_i \in S_i, \quad \sum_{s_{-i}} p_{-i}(s_{-i}) v_i(s_i, s_{-i}) \;\geq\; \sum_{s_{-i}} p_{-i}(s_{-i}) v_i(s'_i, s_{-i}).$

C'est-à-dire que le mouvement s_i est une réponse optimale aux stratégies (mixtes) des adversaires (les équilibres de Nash mixtes sont exactement les combinaisons convexes de réponses optimales^[1]).

Ainsi, un équilibre de Nash est un cas particulier d'équilibre corrélé où la loi est une loi produit (i.e. décorrélée).

Références

1. ↑ (en) N. Nisan, T. Roughgarden, E. Tardos et V. V. Vazirani, Algorithmic Game Theory, Cambridge, Cambridge University Press, 2007 (ISBN 978-0-521-87282-9) (LCCN 2007014231) [lire en ligne]  (chapître 2)

• Robert Aumann (1974), Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics, 1:67-96.
• Robert Aumann (1987), Correlated Equilibrium as an Expression of Bayesian Rationality, Econometrica, 55(1):1-18.
• Fudenberg, Drew et Jean Tirole (1991), Game Theory, MIT Press, 1991, ISBN 0-262-06141-4
• Martin J. Osborne et Ariel Rubinstein (1994), A Course in Game Theory, MIT Press, ISBN 0-262-65040-1.