Équilibres et jeux matriciels

Soit un joueur qui dispose d'un ensemble de choix fini ${\displaystyle X}$; une stratégie pure est un choix ${\displaystyle x\in X}$.

Proposition[1] — Une matrice ${\displaystyle (n,k)}$ de réels ${\displaystyle A=(a_{ij})}$ possède un point d'équilibre (ou point-selle) si et seulement si

${\displaystyle \max _{1\leq j\leq k}(\min _{1\leq i\leq n}a_{ij})=\min _{1\leq i\leq n}(\max _{1\leq j\leq k}a_{ij})}$

En tout point d'équilibre de la matrice, l'entrée correspondante du tableau est égale à ce minimax.

Jeu 1

Soit k le nombre de stratégies pures disponibles pour le joueur 1 et n le nombre de stratégies pures disponibles pour le joueur 2. On numérote de 1 à k les stratégies à la disposition du J1 et de 1 à n celles du J2. Prenons un exemple facile de jeu où n = k = 3.

Voici la matrice de gain :

Le joueur 1 se dit : « Si je joue 1, je risque de perdre 1 unité, et si je joue 3 d'en perdre 3; mais si je joue 2, je gagne une unité dans le pire des cas. »

Le joueur 2 se dit : « Si je joue 1, je risque de perdre 2 unités, et si je joue 2 d'en perdre 2; mais si je joue 3 mes pertes sont limitées à une unité dans le pire des cas.

Le joueur 1, reconstituant le raisonnement du joueur 2 à choisir sa stratégie 3 pour limiter ses pertes, est conforté dans son choix.

Le joueur 2, reconstituant le raisonnement du joueur 1 à choisir sa stratégie 2, est conforté dans son choix (il perdrait 2 s'il choisissait autrement).

Aucun des joueurs n'est prêt à changer sa stratégie car ce sont les choix les plus rationnels.

Par exemple, si le joueur 1 devient gourmand et change sa stratégie pour gagner 1,5 ou 3 unités, sachant que le joueur 2 joue intelligemment et donc sa stratégie 3, le joueur 1 ne gagnerait plus que 0 unité, au lieu de 1. Il n'a donc aucun intérêt à changer sa stratégie. Ce raisonnement est réciproque pour le joueur 2.

En effet, selon la proposition, nous trouvons bien un équilibre :

${\displaystyle \max _{1\leq j\leq k}(\min _{1\leq i\leq n}a_{ij})=\max\{-1,1,-3\}=1}$ tandis que ${\displaystyle \min _{1\leq i\leq n}(\max _{1\leq j\leq k}a_{ij})=\min\{2,1.5,1\}=1.}$

Le minimax et le maximin sont égaux; la ligne où le minimax est atteint et la colonne où le maximin est atteint indiquent un point d'équilibre.

Jeu 2

Similairement au jeu 1, le joueur 1 va choisir sa stratégie 2 pour minimiser les pertes, ici 1,01 unité. Le joueur 2 choisira sa stratégie 3 où il perdra au pire 1,02 unité.

Le joueur 1 anticipe la décision du joueur 2 et se rend compte qu'il va bel et bien perdre 1,01 unité et choisira alors sa stratégie 1 pour gagner 1,02 unité. Le joueur 2 va lui aussi anticiper cette décision et choisir sa stratégie 2 pour gagner 1,03 unité, etc. Aucune stratégie pure de la part des deux joueurs ne parviendra à s'imposer.

Toujours par rapport à la proposition, nous pouvons remarquer qu'il n'y a aucun équilibre :

${\displaystyle \max _{1\leq j\leq k}(\min _{1\leq i\leq n}a_{ij})=-1,01}$ tandis que ${\displaystyle \min _{1\leq i\leq n}(\max _{1\leq j\leq k}a_{ij})=1,02}$

Soit un joueur qui dispose d'un ensemble de choix fini ${\displaystyle X}$; une stratégie mixte est l'attribution d'une certaine distribution de probabilité sur l'ensemble des stratégies pures ${\displaystyle x\in X}$. Bien entendu, chaque stratégie pure ${\displaystyle x\in X}$ est une stratégie mixte qui choisit ${\displaystyle x}$ avec une probabilité de 1.

En 1928, John von Neumann démontre son théorème du minimax. Il assure que, pour un jeu non coopératif opposant deux joueurs, à nombre fini de stratégies pures et à somme nulle, il existe au moins une situation d'interaction stable, à savoir une situation dans laquelle aucun des deux joueurs n'a intérêt à changer sa stratégie mixte si l'autre ne la change pas. Ce théorème est un cas particulier du théorème fondamental de la théorie des jeux à n joueurs de John Forbes Nash, démontré en 1950.

À la différence du cas des points-selle vu précédemment, il existe toujours un équilibre dans un jeu à somme nulle et à deux joueurs aux stratégies mixtes.

Explications :

Soit la stratégie mixte du joueur 1 un vecteur colonne ${\displaystyle X=(p_{1}\,\ldots \,p_{m})^{T}}$ et le joueur 2 choisit la colonne j, alors le gain moyen du J1 est ${\displaystyle \sum _{1\leq i\leq m}p_{i}a_{ij}}$. Similairement, soit la stratégie mixte du J2 représentée par le vecteur colonne ${\displaystyle Y=(q_{1}\,\ldots \,q_{n})^{T}}$ et le J1 choisit la ligne i, alors le gain moyen du J1 est ${\displaystyle \sum _{1\leq j\leq n}a_{ij}q_{j}}$. De manière plus générale, si J1 utilise sa stratégie mixte ${\displaystyle X}$ et J2 utilise sa stratégie mixte ${\displaystyle Y}$, le gain moyen pour le J1 est de :

${\displaystyle Y^{T}AX=\sum _{1\leq i\leq m \atop 1\leq j\leq n}p_{i}a_{ij}qj}$

Désormais, un couple de stratégies mixtes ${\displaystyle (X_{0},Y_{0})\in \Delta _{k}\times \Delta _{n}}$ est un équilibre de Nash pour ${\displaystyle A}$ lorsque :

• Pour tout ${\displaystyle Y\in \Delta _{n}}$, ${\displaystyle Y_{0}^{T}AX_{0}\leq Y^{T}AX_{0}}$ (si J2 change de stratégie tandis que J1 conserve la stratégie ${\displaystyle X_{0}}$, J2 ne peut qu'y perdre)
• Pour tout ${\displaystyle X\in \Delta _{k}}$, ${\displaystyle Y_{0}^{T}AX\leq Y_{0}^{T}AX_{0}}$ (si J1 change de stratégie tandis que J2 conserve la stratégie ${\displaystyle Y_{0}}$, J1 ne peut qu'y perdre).

Proposition[2] — Soit ${\displaystyle A=(a_{ij})}$ une matrice ${\displaystyle (n,k)}$ de réels. Il y a un équilibre de Nash pour ${\displaystyle A}$ (au sens défini ci-dessus) si et seulement si

${\displaystyle \max _{X\in \Delta _{k}}\min _{Y\in \Delta _{n}}Y^{T}AX=\min _{Y\in \Delta _{n}}\max _{X\in \Delta _{k}}Y^{T}AX.}$

En tout équilibre de Nash ${\displaystyle (X_{0},Y_{0})}$ pour ${\displaystyle A}$, la valeur de ${\displaystyle Y_{0}^{T}AX_{0}}$ est alors égale à ce minimax.

Exemple :

Soit la matrice de gain ${\displaystyle A}$ :

Analysons premièrement ce jeu du point de vue du joueur 1. Supposons qu'il joue sa stratégie "une" 3/5 du temps et "deux" 2/5 du temps de manière aléatoire (${\displaystyle X}$ vaut ici ${\displaystyle (3/5\,\,\,2/5)^{T}}$). Dans ce cas :

• Si J2 choisit sa stratégie 1, J1 perd 2 3/5 du temps et gagne 3 2/5 du temps. En moyenne, il gagne -2(3/5) + 3(2/5) = 0
• Si J2 choisit sa stratégie 2, J1 gagne 3 3/5 du temps et perd 4 2/5 du temps. En moyenne, il gagne 3(3/5) - 4(2/5) = 1/5

Sur la durée, le J1 est assuré d'être rentable. Mais peut-il améliorer cette stratégie pour qu'il ait un gain positif quoi que J2 choisisse ?

Définissons ${\displaystyle p}$ comme la quantité de fois que J1 choisit sa stratégie 1. Commençons par trouver p tel que J1 gagne le même montant qu'il choisisse sa stratégie 1 ou sa stratégie 2 :

${\displaystyle -2p+3(1-p)=3p-4(1-p)}$

${\displaystyle 3-5p=7p-4}$

${\displaystyle 12p=7}$

${\displaystyle p={\frac {7}{12}}}$

Donc ${\displaystyle X}$ = ${\displaystyle (7/12\,\,\,5/12)^{T}}$. En moyenne, J1 gagne −2(7/12) + 3(5/12) = 1/12 quoi que J2 choisisse.

Peut-il faire mieux ? Pas si J2 joue intelligemment. En fait, J2 peut utiliser la même procédure et il se retrouvera avec ${\displaystyle Y}$ = ${\displaystyle (7/12\,\,\,5/12)^{T}}$ qui lui garantit une perte moyenne d'au plus 1/12.

On dit alors que la valeur du jeu ${\displaystyle v}$ vaut ${\displaystyle {\frac {1}{12}}}$.

Soit ${\displaystyle A={\begin{pmatrix}a&b\\d&c\\\end{pmatrix}}}$

Nous supposons qu'il n'y a aucun point-selle.

Si ${\displaystyle a\geq b}$ alors ${\displaystyle b<c}$ sinon b serait un point-selle. Si ${\displaystyle b<c}$, alors ${\displaystyle c>d}$ sinon c serait un point-selle.

Donc, ${\displaystyle d<a}$ et ${\displaystyle a>b}$.

En résumé, si ${\displaystyle a>b}$, ${\displaystyle a>b<c>d<a}$.

De manière symétrique, si ${\displaystyle a\leq b}$, alors ${\displaystyle a<b>c<d>a}$.

Comme vu précédemment, reprenons la formule du gain moyen pour le j1 avec ${\displaystyle X}$ = ${\displaystyle (p\,\,\,1-p)^{T}}$ lorsque le j2 utilise sa colonne 1 et 2 :

${\displaystyle ap+d(1-p)=bp+c(1-p)}$

Lorsqu'on résout ${\displaystyle p}$, on trouve :

${\displaystyle p={\frac {c-d}{(a-b)+(c-d)}}}$

Vu qu'il n'y a aucun point-selle, ${\displaystyle (a-b)}$ et ${\displaystyle (c-d)}$ sont soit tous deux strictement positifs soit tous deux strictement négatifs, donc ${\displaystyle 0<p<1}$. Le gain moyen de j1 pour utiliser sa stratégie vaut :

${\displaystyle v=ap+d(1-p)={\frac {ac-bd}{a-b+c-d}}}$

Le calcul de la perte moyenne de j2 est similaire et nous obtenons :

${\displaystyle v=aq+b(1-q)={\frac {ac-bd}{a-b+c-d}}}$

Cette similarité prouve que le jeu a une valeur et que les joueurs ont leur stratégie optimale (propriété du théorème minimax pour les jeux à stratégies finies).

Exemple 1 :

${\displaystyle A={\begin{pmatrix}-2&3\\3&-4\\\end{pmatrix}}}$

${\displaystyle p={\frac {-4-3}{-2-3-4-3}}=7/12}$ ${\displaystyle q=p}$ ${\displaystyle v={\frac {-8-9}{-2-3-4-3}}=1/12}$

Exemple 2 :

${\displaystyle A={\begin{pmatrix}0&-10\\1&2\\\end{pmatrix}}}$

${\displaystyle p={\frac {2-1}{0+10+2-1}}=1/11}$ ${\displaystyle q={\frac {2+10}{0+10+2-1}}=12/11}$

Dans ce dernier exemple, q devrait être entre 0 et 1. Il ne l'est pas car il existe un point-selle. Dans la matrice A, "1" est un point-selle donc p vaut 0, q vaut 1 et v vaut 1.

Parfois, de grandes matrices peuvent être réduites en taille jusqu'à, dans le meilleur des cas, une matrice 2x2. Pour y parvenir, il faut supprimer les lignes et les colonnes qui sont mauvaises (inutiles) pour les deux joueurs.

Tout ce qui peut être atteint avec une ligne ou une colonne dominante peut être atteint au moins aussi bien avec la ligne ou la colonne dominée. Donc, la suppression d'une colonne ou d'une ligne dominante ne change pas la valeur du jeu. Cependant, il existe peut-être une stratégie optimale qui utilisait cette ligne et cette colonne dominante et disparaîtra avec sa suppression, mais il restera toujours au moins une stratégie optimale autre part.

Dans le cas d'une suppression d'une colonne ou d'une ligne strictement dominante, l'ensemble des stratégies optimales reste inchangé.

Exemple :

Nous allons itérer la procédure successivement sur les lignes et colonnes sur la matrice A.

${\displaystyle A={\begin{pmatrix}2&0&4\\1&2&3\\4&1&2\\\end{pmatrix}}}$

La dernière colonne est strictement dominée celle du milieu.

${\displaystyle A={\begin{pmatrix}2&0\\1&2\\4&1\\\end{pmatrix}}}$

La ligne une est dominée par la ligne trois.

${\displaystyle A={\begin{pmatrix}1&2\\4&1\\\end{pmatrix}}}$

Cette matrice n'a pas de point-selle donc : ${\displaystyle p=3/4}$ ${\displaystyle q=1/4}$ ${\displaystyle v=7/4}$ ${\displaystyle X}$ = ${\displaystyle (0\,\,\,3/4\,\,\,1/4)^{T}}$ et ${\displaystyle Y}$ = ${\displaystyle (1/4\,\,\,3/4\,\,\,0)^{T}}$

Connaissances supposées : la programmation linéaire.

De manière informelle, nous voulons trouver des variables qui sont des distributions de probabilité sur différents choix ${\displaystyle p_{1}\,\ldots \,p_{n}}$. Ces probabilités doivent suivre deux inégalités linéaires : ${\displaystyle p_{1}+\ldots +p_{n}=1}$ et ${\displaystyle p_{i}\geq 0}$ pour tout ${\displaystyle i}$.

Notre but est de maximiser le pire cas (le minimum) de notre gain, sur toutes les colonnes que l'adversaire peut jouer. Plus formellement, on assignera une variable ${\displaystyle v}$ qui représente le minimum et on donnera comme contrainte que notre gain soit au moins ${\displaystyle v}$ pour chaque colonne et que notre objectif soit de maximiser ${\displaystyle v}$. En résumé nous avons :

Variables : ${\displaystyle p_{1}\,\ldots ,p_{n}}$ et ${\displaystyle v}$.

Objectifs : Maximiser ${\displaystyle v}$.

Contraintes :

• ${\displaystyle p_{i}\geq 0}$ pour tout ${\displaystyle i}$ et ${\displaystyle \sum _{i}p_{i}=1}$
• pour toutes les colonnes ${\displaystyle j}$, nous avons ${\displaystyle \sum _{i}{p_{i}a_{ij}}\geq v}$

Ce problème est un programme linéaire et peut donc être résolu.

Connaissances supposées : l'algorithme du simplexe.

L'algorithme le plus courant est la méthode du simplexe, introduite par George Dantzig à partir de 1947. La plupart des exemples sont résolus en temps polynomial mais ce n'est pas garanti. Certains cas peuvent dépasser cette complexité. Nous poursuivrons avec un exemple :

Déclinons ${\displaystyle v}$ pour les deux joueurs : ${\displaystyle \lambda }$ que j1 cherche à maximiser et ${\displaystyle \mu }$ que j2 cherche à minimiser. Nous avons donc :

• ${\displaystyle \lambda -\sum _{1\leq i\leq n}{x_{i}a_{ij}}\leq 0}$ pour le j1
• ${\displaystyle \mu -\sum _{1\leq j\leq m}{y_{j}a_{ij}}\geq 0}$ pour le j2

On remarque que le problème du j2 est le "dual" du problème du j1. Ces deux problèmes peuvent donc être résolus ensemble grâce à la méthode du simplexe dual.

Notez que si ${\displaystyle A}$ est la matrice de gain, c'est la négation de la transposée de ${\displaystyle A}$ qui est placée dans le tableau du simplexe :

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle \ldots }$	${\displaystyle x_{n}}$	${\displaystyle \lambda }$
${\displaystyle y_{1}}$	${\displaystyle -a_{11}}$	${\displaystyle -a_{21}}$	${\displaystyle \ldots }$	${\displaystyle -a_{n1}}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle \vdots }$	${\displaystyle \vdots }$				${\displaystyle \vdots }$	${\displaystyle \vdots }$
${\displaystyle y_{m}}$	${\displaystyle -a_{1m}}$	${\displaystyle -a_{2m}}$	${\displaystyle \ldots }$	${\displaystyle -a_{nm}}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle \mu }$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle \ldots }$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 1}$
	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle \ldots }$	${\displaystyle 0}$	${\displaystyle -1}$	${\displaystyle 0}$

Soit la matrice :

Le tableau devient :

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle \lambda }$
${\displaystyle y_{1}}$	${\displaystyle -1}$	${\displaystyle -2}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle y_{2}}$	${\displaystyle -4}$	${\displaystyle 1}$	${\displaystyle -1}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle y_{3}}$	${\displaystyle 0}$	${\displaystyle -3}$	${\displaystyle 0}$	①	${\displaystyle 0}$
${\displaystyle y_{4}}$	${\displaystyle 1}$	${\displaystyle -1}$	${\displaystyle -3}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle \mu }$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 1}$
	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle -1}$	${\displaystyle 0}$

Nous désirerions pivoter ${\displaystyle \lambda }$ et ${\displaystyle \mu }$. Malheureusement, comme toujours pour les matrices de gain pour les jeux, la valeur du pivot vaut 0. Donc on doit pivoter en deux fois : premièrement pour déplacer ${\displaystyle \mu }$ en haut et ensuite pour déplacer ${\displaystyle \lambda }$ à gauche. On inter-change alors ${\displaystyle y_{3}}$ et ${\displaystyle \lambda }$ et supprimons la ligne ${\displaystyle \lambda }$, puis nous inter-changeons ${\displaystyle x_{3}}$ et ${\displaystyle \mu }$ et supprimons la colonne ${\displaystyle \mu }$.

${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle y_{3}}$ ${\displaystyle y_{1}}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle y_{2}}$ ${\displaystyle -4}$ ${\displaystyle 4}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle y_{4}}$ ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle -3}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle \mu }$ ${\displaystyle 1}$ ${\displaystyle 1}$ ① ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle -3}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$

${\displaystyle \longrightarrow }$

${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle y_{3}}$ ${\displaystyle y_{1}}$ ${\displaystyle -2}$ ${\displaystyle 0}$ ${\displaystyle -1}$ ${\displaystyle -1}$ ${\displaystyle y_{2}}$ ${\displaystyle -3}$ ${\displaystyle 5}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle y_{4}}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle -1}$ ${\displaystyle 3}$ ${\displaystyle x_{3}}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle -3}$ ${\displaystyle 1}$ ${\displaystyle 0}$

Maintenant, nous utilisons la règle des pivots pour la méthode du simplexe jusqu'à obtenir, par exemple :

	${\displaystyle y_{4}}$	${\displaystyle y_{2}}$	${\displaystyle y_{1}}$
${\displaystyle y_{3}}$				${\displaystyle 3/7}$
${\displaystyle x_{2}}$				${\displaystyle 16/35}$
${\displaystyle x_{1}}$				${\displaystyle 2/7}$
${\displaystyle x_{3}}$				${\displaystyle 9/35}$
	${\displaystyle 13/35}$	${\displaystyle 8/35}$	${\displaystyle 14/35}$	${\displaystyle 33/35}$

Donc, ${\displaystyle v=33/35}$. L'unique stratégie optimale pour le J1 vaut ${\displaystyle (2/7\,\,\,16/35\,\,\,9/35)^{T}}$. L'unique stratégie optimale pour le J2 vaut ${\displaystyle (14/35\,\,\,8/35\,\,\,0\,\,\,13/35)^{T}}$.

Cette méthode a été inventée par Leonid Khatchian dans les années 1980 en Russie. L'algorithme ne permet de résoudre que la "faisabilité" du problème mais peut se poursuivre avec une recherche binaire sur la fonction objectif pour résoudre le problème d'optimisation.

Le principe est de commencer avec une ellipse (appelée ellipsoïde pour les grandes dimensions) qui contient à coup sûr la région de "faisabilité". Ensuite, on essaye le centre de l'ellipse et on observe si des contraintes sont enfreintes. Dans la négative, on a terminé. Si oui, on regarde les contraintes enfreintes. Désormais, nous savons que la solution (si elle existe) se trouve dans au plus la moitié restante de l'ellipse. On trouve alors une nouvelle ellipse plus petite qui contient cette moitié et on répète l'opération.

On estime qu'on diminue à chaque étape le volume de l'ellipse d'au moins un facteur de ${\displaystyle (1-1/n)}$ par rapport à l'ellipse originale. Donc, pour chaque n-étape, le volume diminue d'un facteur de ${\displaystyle 1/e}$.

C'était le premier algorithme qui garantissait la résolution d'un programme linéaire en temps polynomial mais reste assez lent en pratique.

L'algorithme de Karmarka est un algorithme introduit par Narendra Karmarkar en 1984 et décrit une complexité polynomiale beaucoup plus rapide que la méthode de l'ellipsoïde en pratique.

L’idée de base de la méthode est d’utiliser des fonctions barrières pour décrire l’ensemble des solutions qui est convexe par définition du problème. À l’opposé de l’algorithme du simplexe, cette méthode atteint l’optimum du problème en passant par l’intérieur de l’ensemble des solutions réalisables. Il utilise la méthode des points intérieurs.

Dans le jeu du prisonnier, chaque joueur détient une stratégie optimale unique, indépendante de la stratégie des autres. Un jeu qui a cette propriété a une solution par stratégie dominante.

Il est important de noter qu'une solution à stratégie dominante ne donne pas forcément le meilleur gain. Nous l'avons vu, par exemple, dans le jeu du prisonnier.

Par ailleurs, ce cas particulier où tous les joueurs ont leur propre stratégie dominante est assez rare. Peu de jeux satisfont cette propriété. La cause est que l'évaluation de la valeur ${\displaystyle u_{i}(s)}$ peut être très complexe, jusqu'à devenir exponentielle.

Parce que des situations de stratégies dominantes sont rares, il est nécessaire de chercher un concept de solutions plus largement applicable. Une solution acceptable selon la théorie des jeux est l'idée qu'aucun joueur, poursuivant toujours ses intérêts, ne peut améliorer individuellement sa situation sans s'écarter de sa stratégie. C'est l'idée que capture l'équilibre de Nash.

En d'autres termes, aucun joueur ne peut changer sa stratégie ${\displaystyle s_{i}}$ en ${\displaystyle s'_{i}}$ et améliorer son payement, en supposant que chacun des autres joueurs garde sa stratégie choisie dans s.

Nous remarquons également qu'une solution par stratégie dominante est un équilibre de Nash.

Désormais, les joueurs ne jouent plus leur stratégie de manière déterministe. Le problème se pose alors de comprendre comment les joueurs évaluent leur payement d'un choix probabiliste. Un joueur préférait-il un choix qui rapporte peu avec une forte probabilité, un choix qui rapporte beaucoup avec une faible probabilité ou encore un choix qui risque de faire perdre peu avec une grande probabilité ? Dans le cas des équilibres de Nash pour les stratégies mixtes, nous supposons qu'ils sont neutres par rapport au risque et qu'ils essayent uniquement de maximiser leur gain.

Pour définir ce choix de stratégie aléatoire formellement, on dit que chaque joueur peut définir une distribution de probabilité sur sa palette de choix, et que chacun choisira de manière indépendante un choix selon cette distribution de probabilité.

En 1951, Nash prouve que, sous ces conditions, tout jeu à nombre de joueurs et de stratégies mixtes fini possède un équilibre de Nash.

Calculer un équilibre de Nash peut s'avérer, pour certains jeux, extrêmement long. Traditionnellement, les problèmes se retrouvent dans deux catégories de complexité : la classe P pour les problèmes qui ont un algorithme en temps polynomial et la classe NP-complet. Cependant, le concept de NP-complet ne peut être appliqué pour les rares problèmes "dont chaque instance possède une solution", comme les équilibres pour les jeux à nombre de joueurs et de stratégies mixtes fini.

On démontre alors que trouver un équilibre de Nash est complet pour la classe de problème PPAD grâce au Théorème du point fixe de Brouwer. Chaque problème de cette classe partage cette même propriété que chacune de leurs instances possède une solution. PPAD est donc une sous-classe de NP qui contient les problèmes durs, les équilibres de Nash y compris[5].

Plusieurs algorithmes de résolution ont été proposés depuis les années 1970, mais la plupart ont des complexités inconnues. C'est pourquoi désormais, les jeux sont séparés en "classes" de jeux pour étudier les différents cas et les différentes complexités. Principalement, les recherches espèrent établir l'existence d'un algorithme sous-exponentiel - ${\displaystyle O(n^{logn/\epsilon ^{2}})}$ - où n est la taille du jeu.

Pour les jeux à deux joueurs, les mesures de l'équilibre de Nash sont des nombres rationnels (la distribution de leur stratégie mixte) et sa solution est donc claire. Mais, selon Nash, lorsque le nombre de joueurs augmente, il ne peut y avoir que des solutions irrationnelles. Les calculs deviennent alors numériquement imprécis, c'est pourquoi on introduit le concept d'équilibre de Nash approximé.

Si un équilibre de Nash est une situation dans laquelle personne ne souhaite dévier de sa stratégie, un ϵ-équilibre de Nash est un ensemble de stratégies mixtes dans laquelle les joueurs peuvent espérer augmenter leurs gain d'au plus ϵ en changeant de stratégie. Un ϵ-équilibre de Nash n'est pertinent que si ϵ est petit.

La question se pose de savoir s'il existe un Schéma d'approximation en temps polynomial pour les équilibres de Nash approximés, c'est-à-dire un algorithme qui tourne en temps polynomial en rapport à la taille du jeu, en acceptant des dépendances sur temps sur 1/ϵ.

Notes

Références

• (en) [PDF] T. S. Ferguson Linear Programming A Concise Introduction.
• (en) [PDF] T. S. Ferguson Game Theory Part II. Two-Person Zero-Sum Games.
• (en) [PDF] A. Blum Linear Programming

• (en) Ken Binmore, Playing for Real : A Text on Game Theory, Oxford University Press US, 2007, 639 p. (ISBN 978-0-19-530057-4, lire en ligne)
  Un cours d'initiation à la théorie des jeux et à son formalisme mathématique, par un des spécialistes mondiaux du sujet.
• (en) N. Nisan, T. Roughgarden, E. Tardos, V. V. Vazirani (2007). Algorithmic Game Theory