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 personnelleDéfini en détail plus loin.. La notion d'équilibre a pris un essor considérable au 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 :
j2j1 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 :
j2j1 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 ; une stratégie pure est un choix .
Point-selle du 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 :
tandis que
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 :
tandis que
Pour les stratégies mixtes Soit un joueur qui dispose d'un ensemble de choix fini ; une stratégie mixte est l'attribution d'une certaine distribution de probabilité sur l'ensemble des stratégies pures . Bien entendu, chaque stratégie pure est une stratégie mixte qui choisit 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 et le joueur 2 choisit la colonne j, alors le gain moyen du J1 est . Similairement, soit la stratégie mixte du J2 représentée par le vecteur colonne et le J1 choisit la ligne i, alors le gain moyen du J1 est . De manière plus générale, si J1 utilise sa stratégie mixte et J2 utilise sa stratégie mixte , le gain moyen pour le J1 est de :
Désormais, un couple de stratégies mixtes est un équilibre de Nash pour lorsque :
Pour tout , (si J2 change de stratégie tandis que J1 conserve la stratégie , J2 ne peut qu'y perdre) Pour tout , (si J1 change de stratégie tandis que J2 conserve la stratégie , J1 ne peut qu'y perdre).
Exemple :
Soit la matrice de gain :
j2j1 -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 ( vaut ici ). 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 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 :
Donc = . 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 = qui lui garantit une perte moyenne d'au plus 1/12.
On dit alors que la valeur du jeu vaut .
Résolution des matrices de gain 2x2 Soit
Nous supposons qu'il n'y a aucun point-selle.
Si alors sinon b serait un point-selle. Si , alors sinon c serait un point-selle.
Donc, et .
En résumé, si , .
De manière symétrique, si , alors .
Comme vu précédemment, reprenons la formule du gain moyen pour le j1 avec = lorsque le j2 utilise sa colonne 1 et 2 :
Lorsqu'on résout , on trouve :
Vu qu'il n'y a aucun point-selle, et sont soit tous deux strictement positifs soit tous deux strictement négatifs, donc . Le gain moyen de j1 pour utiliser sa stratégie vaut :
Le calcul de la perte moyenne de j2 est similaire et nous obtenons :
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 :
Exemple 2 :
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.
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.
La dernière colonne est strictement dominée celle du milieu.
La ligne une est dominée par la ligne trois.
Cette matrice n'a pas de point-selle donc :
= et =
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 . Ces probabilités doivent suivre deux inégalités linéaires : et pour tout .
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 qui représente le minimum et on donnera comme contrainte que notre gain soit au moins pour chaque colonne et que notre objectif soit de maximiser . En résumé nous avons :
Variables : et .
Objectifs : Maximiser .
Contraintes : pour tout et pour toutes les colonnes , nous avons
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.