Équilibres et jeux matriciels

En théorie des jeux, un équilibre de Nash définit une situation dans laquelle aucun joueur ne peut modifier seul sa stratégie sans affaiblir sa position personnelle^{[Note 1]}. La notion d'équilibre a pris un essor considérable au XX^e siècle et se trouve désormais au centre de la théorie des jeux. Depuis 1928, lorsque John von Neumann initie la théorie des jeux avec son théorème du minimax, les équilibres deviennent un outil essentiel d'analyse dans des domaines variés tels que l'économie, les sciences sociales et les sciences politiques. En 1958, John Forbes Nash décrit un théorème qui assure que tout jeu à nombre de joueurs et stratégies finis possède un équilibre pour les stratégies mixtes. La théorie des jeux se consacre, entre autres, à calculer si ces états peuvent être atteints, efficacement en pratique, avec des agents rationnels. En 1994, Christos Papadimitriou crée la classe de complexité PPAD dans laquelle sont repris les calculs des équilibres de Nash pour les jeux à plusieurs joueurs.

Notion d'équilibre

Dans la théorie des jeux, l'équilibre ou l'équilibre de Nash, nommé d'après John Forbes Nash, est un concept de solution dans lequel l'ensemble des choix faits par plusieurs joueurs, connaissant leurs stratégies réciproques, est devenu stable du fait qu'aucun ne peut modifier seul sa stratégie sans affaiblir sa position personnelle.

Cela signifie que n'importe quel jeu pourrait, en principe, atteindre un état de calme où personne n'aurait l'intention de changer son comportement. Cette situation soulève immédiatement plusieurs questions : est-ce possible dans la réalité de notre monde économique ou politique ? Est-il possible de calculer cet équilibre efficacement ? Il est important de résoudre cette deuxième question. Car ce principe d'équilibre est au-delà de tout outil conceptuel, c'est une prédiction de comportements stratégiques rationnels par des agents en situation de conflit, un contexte pourtant dénué de logique et de calculs. La crédibilité de cette solution envers les économistes dépend directement de l'efficacité avec laquelle la théorie des jeux peut la proposer.

Matrices de gain

La matrice des gains, matrice de coût ou encore matrice des paiements (anglicismes issus de payoff matrix) est un moyen de représenter un jeu sous forme stratégique par un tableau indiquant les gains (ou paiements) associés à chaque action en fonction des actions de l'autre joueur.

Typiquement, une matrice de gain pour les jeux à somme nulle se représente comme suit :

	j2
j1		stratégie 1	stratégie 2
	stratégie 1	-2	3
	stratégie 2	3	-4

Lorsque le joueur 1 choisit sa stratégie 2 et le joueur 2 choisit sa stratégie 1 : le joueur 1 gagne 3 et le joueur 2 perd 3.

Lorsque le joueur 1 choisit sa stratégie 1 et le joueur 2 choisit sa stratégie 1 : le joueur 1 perd 2 et le joueur 2 gagne 2.

Une matrice de gain pour les jeux à somme non nulle se représente comme suit :

	j2
j1		stratégie 1	stratégie 2
	stratégie 1	(5 ; 3)	(5 ; -10)
	stratégie 2	(-10 ; 5)	(-5 ; -5)

Lorsque le joueur 1 choisit sa stratégie 2 et le joueur 2 choisit sa stratégie 1 : le joueur 1 perd 10 et le joueur 2 gagne 5.

Nous prendrons soin de toujours placer le joueur 1 à gauche et le joueur 2 en haut.

Équilibre dans les jeux deux joueurs à somme nulle

Pour les stratégies pures

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

Point-selle du Minimax

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 :

J1/J2	joue sa stratégie 1	joue sa stratégie 2	joue sa stratégie 3
joue sa stratégie 1	-1	1,5	0
joue sa stratégie 2	2	2	1
joue sa stratégie 3	2	-3	0

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

---

J1/J2	joue sa stratégie 1	joue sa stratégie 2	joue sa stratégie 3
joue sa stratégie 1	0	-1,03	1,02
joue sa stratégie 2	1,05	0	-1,01
joue sa stratégie 3	-1,07	1,04	0

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}$

Pour les stratégies mixtes

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.

Théorème du Minimax

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}$ :

	j2
j1	-2	3
	3	-4

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}}}$.

Résolution des matrices de gain 2x2

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}$.

Proposition^[3] — S'il n'y a aucun point-selle, alors soit ${\displaystyle a>b}$, ${\displaystyle b<c}$ ; ${\displaystyle c>d}$ et ${\displaystyle d<a}$ ; soit ${\displaystyle a<b}$, ${\displaystyle b>c}$ ; ${\displaystyle c<d}$ et ${\displaystyle 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.

Résolution par suppression de la stratégie dominante

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.

Définition^[3] — La i-ième ligne d'une matrice ${\displaystyle A=(a_{ij})}$ domine la k-ième ligne si ${\displaystyle a_{ij}\geq a_{kj}}$ pour tout j. La i-ième ligne de A domine strictement la k-ième ligne si ${\displaystyle a_{ij}>a_{kj}}$ pour tout j. Similairement, la j-ième colonne de A domine (domine strictement) la k-ième colonne si ${\displaystyle a_{ij}\leq a_{ik}}$ (${\displaystyle a_{ij}<a_{ik}}$) pour tout i.

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}}$

Généralisation aux matrices NxN

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.

Méthode du simplexe

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 :

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

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}}$.

Méthode de l'ellipsoïde

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.

Algorithme de Karmarkar

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.

Équilibre pour les jeux à n joueurs

Prenons le célèbre exemple du dilemme du prisonnier pour introduire les jeux à somme non nulle. Nous prenons encore un jeu à 2 joueurs par simple souci de clarté dans les matrices de gains. Les concepts de ce chapitre s'appliquent pour n joueurs.

Dilemme du prisonnier

---

Deux prisonniers sont accusés d'un crime et chacun est confronté au choix de trahir (T) ou de rester silencieux (S). Leur choix va définir leur sentence qui se traduit par des années passées en prison. Voici la matrice de coût associée à ces choix que les prisonniers veulent minimiser :

J1\J2	(T)	(S)
(T)	(4 ; 4)	(1 ; 5)
(S)	(5 ; 1)	(2 ; 2)

La seule solution stable est celle où les deux prisonniers trahissent. Dans les trois autres possibilités, un prisonnier peut passer du silence à trahir et améliorer son gain. Les prisonniers n'oseront donc jamais jouer le payement 2 et 1 par peur de récolter la sentence maximale.

Solution par stratégie dominante

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.

Proposition ^[4] —  Soit
- un vecteur de stratégie ${\displaystyle s\in \mathbf {S} }$ où ${\displaystyle s_{i}}$ est la stratégie du joueur ${\displaystyle i}$
- ${\displaystyle s_{-i}}$ pour décrire le vecteur de dimension ${\displaystyle (n-1)}$ des stratégies des autres joueurs
- ${\displaystyle u_{i}(s)}$ une valeur représentant l'issue de la situation, typiquement le gain ou le coût.

Un vecteur de stratégie ${\displaystyle s\in \mathbf {S} }$ est solution par stratégie dominante si, pour chaque joueur ${\displaystyle i}$, et chaque vecteur de stratégie alternatif ${\displaystyle s'\in \mathbf {S} }$, nous avons :

${\displaystyle u_{i}(s_{i},s'_{-i})\geqslant u_{i}(s'_{i},s'_{-i})}$.

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.

Pour les stratégies pures

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.

Proposition ^[4] —  Soit un vecteur de stratégie ${\displaystyle s\in \mathbf {S} }$ est un équilibre de Nash si, pour chaque joueur ${\displaystyle i}$, et chaque stratégie alternative ${\displaystyle s'_{i}\in \mathbf {S_{i}} }$ nous avons :

${\displaystyle u_{i}(s_{i},s_{-i})\geqslant u_{i}(s'_{i},s_{-i})}$

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.

Pour les stratégies mixtes

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.

La classe PPAD

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.

Équilibres de Nash approximés

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/ϵ.

Annexes

Notes et références

Notes

1. Défini en détail plus loin.

Références

1. Binmore 2007, p. 220-221
2. Binmore 2007, p. 228
3. Thomas S. Ferguson (Université de Californie à Los Angeles), Game Theory, p. 10,11.
4. N. Nisan, T. Roughgarden, E. Tardos, V. V. Vazirani (2007) (Université de Cambridge), Algorithmic Game Theory, p. 10,11,29-53.
5. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou (Massachusetts Institute of Technology), The Complexity of Computing a Nash Equilibrium, p. 3 et suivantes.

Liens externes

• (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

Bibliographie

• (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