Équilibre de Nash
- Introduite par
- John Nash
- Année
- 1950
- Type
- algorithm
- Famille
- Game-theoretic
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'équilibre de Nash est un concept de solution en théorie des jeux où aucun joueur ne peut dévier unilatéralement pour améliorer son gain.
Formalisé par John Nash en 1950, l'algorithme de Lemke-Howson trouve de manière computationnelle les équilibres dans les jeux bimatriciels en identifiant des paires de sommets complètement étiquetés dans les polytopes de stratégie.
L’intuition derrière la méthode
Dans un équilibre de Nash, la stratégie de chaque joueur est une meilleure réponse à la stratégie de tous les autres joueurs. Imaginez une situation où les deux joueurs connaissent la stratégie de l'autre : aucun ne voudrait changer, car cela ne ferait que lui nuire. L'algorithme de Lemke-Howson exploite la géométrie des polyèdres de jeu, suivant les étiquettes (contraintes non satisfaites) et pivotant à travers les sommets jusqu'à ce qu'une paire complètement étiquetée soit trouvée — une configuration où les deux joueurs n'ont pas de déviations profitables.
Histoire
John Nash a prouvé dans sa thèse de 1950 que tout jeu fini possède au moins un équilibre de Nash en stratégies mixtes. En 1964, Lemke et Howson ont publié le premier algorithme constructif pour trouver ces équilibres, transformant la preuve d'existence de Nash en une méthode de calcul pratique. Leurs travaux sont devenus fondamentaux pour la théorie des jeux computationnelle et l'économie algorithmique.
Quand l’utiliser
Utilisez l'analyse de l'équilibre de Nash lors de l'étude de jeux à deux joueurs et d'espaces de stratégie discrets, ou lorsque vous recherchez des équilibres complètement mixtes. Convient pour modéliser les problèmes de concurrence, de négociation et de coordination où l'interaction stratégique est primordiale. La méthode de Lemke-Howson fonctionne mieux pour les jeux bimatriciels non dégénérés ; les cas dégénérés peuvent nécessiter un calcul symbolique ou une perturbation.
Limites et points d’attention
- Limité aux jeux bimatriciels (à deux joueurs) ; l'extension aux jeux à n joueurs est NP-difficile
- Échoue ou devient inefficace sur les jeux dégénérés où plusieurs pivots entrants sont possibles
- Peut ne trouver qu'un seul équilibre ; plusieurs équilibres existent souvent dans les jeux à somme non nulle
- Ne gère pas directement les jeux dynamiques ou sous forme extensive sans reformulation
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Efficace sur le plan computationnel pour trouver les équilibres de Nash dans les jeux bimatriciels finis
- Garantit la convergence vers une paire de sommets complètement étiquetés pour les jeux non dégénérés
- Fournit une base théorique reliant la géométrie combinatoire à la théorie des jeux
- Applicable aux équilibres en stratégies mixtes, qui sont souvent plus réalistes que les résultats en stratégies pures
Applications
- Économie : modélisation de la concurrence oligopolistique et du comportement de fixation des prix sur les marchés
- Enchères et conception de mécanismes : analyse des stratégies d'enchères dans les enchères au premier prix et à l'aveugle
- Cybersécurité : prédiction des équilibres attaquant-défenseur dans les jeux de sécurité réseau
- Biologie de la faune : analyse des stratégies évolutivement stables dans les interactions prédateur-proie
Comment ça marche
Comment ça marche
Convertir le jeu bimatriciel en deux problèmes de complémentarité linéaire (LCP), un pour chaque joueur, représentant leurs conditions de meilleure réponse.
Attribuer des étiquettes aux arêtes et aux sommets des polytopes de stratégie en fonction des contraintes d'incitation du joueur qui sont violées.
En partant du sommet « tout-un » (complètement étiqueté), effectuer des pivots de type simplexe pour naviguer dans le polytope, en supprimant et en ajoutant des étiquettes jusqu'à ce qu'une paire complètement étiquetée soit découverte.
Confirmer que les stratégies des deux joueurs forment des meilleures réponses mutuelles en vérifiant qu'aucun ne peut améliorer son gain étant donné la stratégie de l'autre.
Pièges courants
- Supposer qu'un équilibre unique existe ; de nombreux jeux ont plusieurs équilibres de Nash avec des implications de gain différentes
- Confondre les équilibres en stratégies mixtes (jeu probabiliste) avec les équilibres en stratégies pures, ce qui conduit à une mauvaise interprétation du comportement de l'agent
- Négliger la distinction entre les conditions nécessaires et suffisantes pour l'équilibre ; une paire complètement étiquetée satisfait l'optimalité mais peut ne pas être réalisée si les joueurs ne peuvent pas se coordonner
Questions fréquentes
Un jeu peut-il n'avoir aucun équilibre de Nash ?
Les équilibres de Nash en stratégies pures peuvent ne pas exister (par exemple, Pierre-Feuille-Ciseaux), mais tout jeu fini a au moins un équilibre en stratégies mixtes où les joueurs randomisent leurs actions avec des probabilités spécifiques.
En quoi un équilibre en stratégies mixtes est-il différent d'un équilibre en stratégies pures ?
Dans un équilibre en stratégies pures, chaque joueur s'engage avec certitude dans une action spécifique. Dans un équilibre en stratégies mixtes, chaque joueur utilise une distribution de probabilité sur les actions. Les équilibres mixtes sont souvent plus généraux et existent lorsque les équilibres purs n'existent pas.
Pourquoi l'algorithme de Lemke-Howson est-il préféré à la recherche par force brute ?
L'algorithme exploite la structure polyédrique des espaces de stratégie, réduisant exponentiellement l'espace de recherche et atteignant la convergence en temps polynomial pour les jeux non dégénérés, tandis que l'énumération par force brute devient irréalisable à mesure que l'espace de stratégie s'agrandit.
Méthodes associées
Sources
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
Ouvrir la référence DOICopié.Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
Ouvrir la référence DOICopié.