É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. 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 :

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 :

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 
{{Théorème|nom=Proposition|Une matrice  de réels  possède un point d'équilibre (ou point-selle) si et seulement siEn tout point d'équilibre de la matrice, l'entrée correspondante du tableau est égale à ce minimax.|style=background-color:#ffeedd;border-color:#ff8822;}}

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 :

 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

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  :

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.

 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.

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  pour les deux joueurs :  que j1 cherche à maximiser et  que j2 cherche à minimiser.
Nous avons donc :
  pour le j1
  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  est la matrice de gain, c'est la négation de la transposée de  qui est placée dans le tableau du simplexe :

Soit la matrice :

Le tableau devient :

Nous désirerions pivoter  et . 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  en haut et ensuite pour déplacer  à gauche. On inter-change alors  et  et supprimons la ligne , puis nous inter-changeons  et  et supprimons la colonne .

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

Donc, . L'unique stratégie optimale pour le J1 vaut . L'unique stratégie optimale pour le J2 vaut .

 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  par rapport à l'ellipse originale. Donc, pour  chaque n-étape, le volume diminue d'un facteur de . 

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 :

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.

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

En d'autres termes, aucun joueur ne peut changer sa stratégie  en  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.

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

 Références

 Liens externes 
   T. S. Ferguson Linear Programming A Concise Introduction.
   T. S. Ferguson Game Theory Part II. Two-Person Zero-Sum Games.
   A. Blum Linear Programming

 Bibliographie 
 
  N. Nisan, T. Roughgarden, E. Tardos, V. V. Vazirani (2007). Algorithmic Game Theory''

Théorie des jeux