Jeu de potentiel

En théorie des jeux, un jeu de potentiel est un jeu où il existe une fonction globale décrivant les conséquences d'un changement de stratégie pour chaque joueur. Cette fonction est appelée fonction de potentiel.

Ces jeux ont des propriétés intéressantes du point de vue des équilibre de Nash, et ont des applications, par exemple dans les jeux de congestion (en) en théorie algorithmique des jeux, qui peuvent représenter le trafic routier.

Histoire

On situe attribue souvent la définition des jeux de potentiel à Robert W. Rosenthal dans un article de 1973 : A class of games possessing pure-strategy Nash equilibria[1].

Définitions

Les définitions suivantes concernent les jeux de potentiel finis. On peut aussi envisager des jeux infinis.

Soit ${\displaystyle N}$ le nombre de joueurs, ${\displaystyle A}$ l'ensemble (produit) des stratégies possibles, ${\displaystyle A_{i}}$ les stratégies du joueur ${\displaystyle i}$ et ${\displaystyle u}$ la fonction d'utilité.

• Un jeu ${\displaystyle G=(N,A_{1}\times ...\times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$ est un jeu de potentiel ordinal s'il existe ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ telle que

${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}},u_{i}(a'_{i},a_{-i})<u_{i}(a''_{i},a_{-i})}$ implique ${\displaystyle \Phi (a'_{i},a_{-i})>\Phi (a''_{i},a_{-i})}$.

• Un jeu ${\displaystyle G=(N,A_{1}\times ...\times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$ est un jeu de potentiel exact s'il existe ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ telle que

${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}},\Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a''_{i},a_{-i})-u_{i}(a'_{i},a_{-i})}$.

Dans la littérature scientifique, l'expression jeu de potentiel peut désigner l'une ou l'autre de ces notions. On peut définir des variantes, avec des poids etc.

Propriétés

Si un point est un minimum global du potentiel, alors c'est un équilibre de Nash[2]. En conséquence, si l'ensemble des stratégies et la fonction de potentiel sont convexes, il y a existence d'un équilibre de Nash pur.

Notes et références

1. Voir (Rosenthal 1973) pour l'article initial et (Monderer et Shapley 1996) pour un exemple d'attribution à Rosenthal.
2. (Monderer et Shapley 1996)

Bibliographie

• Robert W Rosenthal, « A class of games possessing pure-strategy Nash equilibria », International Journal of Game Theory, Springer, vol. 2, n^o 1,‎ 1973, p. 65-67

• Dov Monderer et Lloyd Shapley, « Potential games », Games and Economic Behavior, Elsevier, vol. 14, n^o 1,‎ 1996, p. 124-143

Liens externes

• Notes de cours de Yishay Mansour sur les jeux de potentiel et les jeux de congestion.