La théorie des jeux et l’équilibre de Nash
Le raisonnement stratégique quand les joueurs ne sont pas strictement opposés : stratégies dominantes, le dilemme du prisonnier déroulé depuis sa matrice de gains, l’équilibre de Nash, l’optimalité de Pareto, et pourquoi équilibre et efficacité peuvent s’opposer.
Prérequis : La recherche adversariale et le minimax
La recherche adversariale et le minimax supposait une opposition stricte : tout ce qu’un joueur gagne, l’autre le perd. La plupart des situations stratégiques ne sont pas ainsi. Les deux parties peuvent préférer la coopération au conflit et pourtant échouer à l’atteindre. La théorie des jeux étudie exactement ces cas, et son concept de solution central explique quantité de comportements autrement déroutants.
A. Les ingrédients
Un jeu sous forme normale est spécifié par trois choses :
- les joueurs ;
- les stratégies dont chacun dispose ;
- la matrice des gains, donnant l’utilité de chaque joueur pour chaque combinaison.
Un profil de stratégies est une stratégie par joueur. Quand chaque joueur a une stratégie unique (plutôt qu’un plan conditionné à ce que font les autres), c’est une stratégie pure.
B. Le dilemme du prisonnier
L’exemple canonique, d’après Russell et Norvig. Alice et Bob sont arrêtés et interrogés séparément. Chacun se voit proposer un marché :
- Si vous témoignez contre votre complice et qu’il refuse, vous êtes libéré et il purge 10 ans.
- Si vous témoignez tous les deux, vous prenez 5 ans chacun.
- Si vous refusez tous les deux, vous purgez 1 an chacun pour un chef d’accusation moindre.
En prenant l’utilité comme l’opposé des années purgées, la matrice des gains est :
| Alice : témoigner | Alice : refuser | |
|---|---|---|
| Bob : témoigner | ||
| Bob : refuser |
C. La résoudre par dominance
Alice raisonne sur les deux choix possibles de Bob :
Supposons que Bob témoigne. Alice obtient en témoignant et en refusant. Témoigner est meilleur.
Supposons que Bob refuse. Alice obtient en témoignant et en refusant. Témoigner est encore meilleur.
Témoigner est meilleur dans tous les cas : c’est donc une stratégie dominante pour Alice. Précisément : la stratégie domine fortement si l’issue de est meilleure que celle de pour tout choix des autres joueurs. ( domine faiblement si elle est meilleure sur au moins un profil et jamais pire.)
Il est irrationnel de jouer une stratégie dominée, et irrationnel de ne pas jouer une stratégie dominante quand il en existe une. Alice témoigne donc.
La matrice est symétrique, le raisonnement de Bob est donc identique : il témoigne aussi. Quand chaque joueur a une stratégie dominante, le profil obtenu est un équilibre en stratégies dominantes.
L’issue : tous deux témoignent, tous deux prennent 5 ans.
D. Pourquoi c’est un dilemme
Regardez la case en bas à droite. Si tous deux avaient refusé, chacun aurait purgé 1 an au lieu de 5. Les deux joueurs préfèrent cette issue, et pourtant le jeu individuellement rationnel ne l’atteint pas.
Le vocabulaire pour cela : une issue est Pareto-optimale si aucune autre issue n’est préférée par tous les joueurs, et Pareto-dominée si une autre issue est préférée par tous. Ici est Pareto-dominée par .
Voilà le dilemme - des choix individuellement rationnels produisent un résultat conjointement pire. Rien d’irrationnel chez les joueurs ; c’est la structure des incitations elle-même qui les y mène.
E. L’équilibre de Nash
Les stratégies dominantes sont rares. Le concept général :
Un profil de stratégies est un équilibre de Nash si aucun joueur ne peut améliorer son propre gain en changeant unilatéralement de stratégie, les autres restant fixées.
« Unilatéralement » est le mot porteur : chaque joueur ne vérifie que sa propre déviation, les choix de tous les autres restant constants.
Vérifions (témoigner, témoigner) : Alice peut-elle s’améliorer en changeant seule ? Elle passerait de à . Non. Bob, symétriquement, non. C’est un équilibre de Nash.
Vérifions (refuser, refuser) : Alice peut-elle s’améliorer en changeant seule ? Elle passerait de à . Oui. Donc, bien que meilleure pour les deux, ce n’est pas un équilibre - c’est instable, car chaque joueur est individuellement tenté de faire défection.
Tout équilibre en stratégies dominantes est un équilibre de Nash, mais tout équilibre de Nash ne provient pas de stratégies dominantes.
La grille ci-dessous transforme la définition en quelque chose que vous pouvez tester à la main : choisissez une issue et cherchez un coup qui rapporte à un joueur, seul. Deux autres jeux accompagnent le dilemme, car le dilemme seul confond trois idées distinctes - dominance, équilibre et efficacité. La chasse au cerf possède des équilibres sans aucune stratégie dominante ; pile ou face n’a aucun équilibre en stratégies pures, et c’est précisément la lacune que comble la section suivante.
Interactif : essayez de quitter la case
Cliquez une issue. Le gain du joueur en ligne d’abord.
| Bob: testify | Bob: refuse | |
|---|---|---|
| Alice: testify | ||
| Alice: refuse |
- Cette issue
- quelqu’un peut mieux faire
- Équilibres purs
- 1
- Stratégies dominantes
- les deux joueurs
Pas un équilibre : Alice peut passer seul à testify et gagner 1. Rien ne doit changer chez l’autre joueur, et c’est précisément le test : un profil ne survit que si TOUT écart unilatéral est non rentable, pour chacun.
F. Le théorème de Nash et les stratégies mixtes
Certains jeux n’ont aucun équilibre en stratégies pures. Le jeu de pile ou face apparié en est l’exemple standard : un joueur gagne s’il y a correspondance, l’autre s’il y a discordance, et quel que soit votre choix pur, votre adversaire a une déviation profitable, indéfiniment.
La résolution consiste à autoriser des stratégies mixtes - des distributions de probabilité sur les stratégies pures. Dans ce jeu, jouer pile avec probabilité de part et d’autre est un équilibre : puisque le gain espéré de l’adversaire est alors identique pour pile et face, aucune déviation n’aide.
John Nash a démontré que tout jeu fini possède au moins un équilibre dès lors que les stratégies mixtes sont autorisées. Le concept général d’équilibre porte aujourd’hui son nom.
Le texte fondateur est Theory of Games and Economic Behavior de von Neumann et Morgenstern (1944), qui contenait l’analyse montrant que certains jeux exigent des stratégies randomisées.
L’existence n’est pas l’unicité, et l’équilibre n’est pas l’optimalité. Un jeu peut avoir plusieurs équilibres de Nash aux gains différents, ce qui soulève le problème distinct de savoir lequel sera joué. Et comme le montre le dilemme du prisonnier, un équilibre peut être Pareto-dominé - « stable » et « bon » sont des propriétés différentes.
G. Vérifier l’analyse
Les petits jeux peuvent être vérifiés exhaustivement - cela vaut la peine, car les arguments de dominance et d’équilibre sont faciles à rater subtilement :
S'exécute dans votre navigateur. La première exécution télécharge l'environnement Python (~10 Mo), puis il est mis en cache.
Son exécution affiche testify comme dominante pour les deux joueurs, identifie
(testify, testify) comme le seul équilibre de Nash avec les gains
, et signale qu’il est Pareto-dominé par ('refuse', 'refuse') - confirmant chaque affirmation ci-dessus par vérification exhaustive plutôt que par
assertion.
H. Pourquoi cela compte au-delà des énigmes
La structure du dilemme réapparaît partout où les incitations individuelles divergent des incitations collectives : ressources partagées épuisées par un usage individuellement rationnel, courses aux armements, guerres des prix, et passager clandestin sur les biens publics.
Cela compte aussi directement pour les systèmes d’IA. Quand plusieurs agents apprenants partagent un environnement, chacun optimisant son propre objectif, l’issue est gouvernée par la structure d’équilibre du jeu plutôt que par l’objectif d’un agent isolé. Un agent individuellement bien conçu peut malgré tout contribuer à une issue collectivement médiocre - d’où le fait que la conception de mécanismes, le problème de concevoir les règles pour que le jeu intéressé produise de bonnes issues, soit un domaine à part entière.
À retenir
- Un jeu sous forme normale, ce sont joueurs, stratégies, gains ; une stratégie dominante est la meilleure contre tout choix adverse.
- Dans le dilemme du prisonnier, témoigner domine pour les deux, donnant - alors que était disponible et meilleur pour les deux.
- Une issue est Pareto-dominée quand tous les joueurs en préfèrent une autre ; les issues d’équilibre peuvent être Pareto-dominées.
- Un équilibre de Nash est un profil où aucun joueur ne gagne à dévier unilatéralement.
- Nash a démontré que tout jeu fini possède un équilibre dès que les stratégies mixtes sont autorisées.
- Les équilibres ne sont ni nécessairement uniques ni nécessairement efficaces.
La suite
Ceci clôt la série Recherche et jeux. Pour voir la machinerie statistique auprès de laquelle ces idées stratégiques se rangent, partez de Qu’est-ce que l’apprentissage statistique ? ; pour suivre le fil de l’optimisation qui entraîne les modèles modernes, voyez La rétropropagation et la descente de gradient.
Références et lectures complémentaires
- Stuart Russell, Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson (3rd edition), 2010· Bibliothèque de référence Kudos AI
Les œuvres protégées par le droit d’auteur sont citées à titre de référence uniquement et ne sont pas hébergées ici ; veuillez consulter l’éditeur pour y accéder.