La théorie des jeux : définition, histoire, exemples et applications
En bref : la théorie des jeux est la branche des mathématiques qui étudie les décisions dont le résultat dépend de ce que décident les autres. Un « jeu » est toute situation où plusieurs joueurs choisissent chacun une stratégie et reçoivent un gain qui dépend des choix de tous. La discipline a été fondée par John von Neumann (théorème du minimax, 1928) et par le livre qu'il a écrit avec Oskar Morgenstern, Theory of Games and Economic Behavior (1944) ; John Nash y a ajouté l'équilibre de Nash en 1950. On l'applique aujourd'hui en économie, aux enchères, en politique, en biologie, en sécurité et en intelligence artificielle.
Rares sont les décisions prises seul. Le prix d'une boutique dépend de celui du magasin d'en face, le meilleur côté pour tirer un penalty dépend de l'endroit où plongera le gardien, et le budget militaire d'un pays dépend de celui de ses voisins. À chaque fois, le bon choix dépend de ce que l'on prévoit du choix de l'autre, et l'autre fait le même raisonnement sur nous. La théorie des jeux est l'outil qui permet de penser cette boucle, et c'est pourquoi le mot « jeu » y désigne aussi bien les échecs que les guerres des prix ou les négociations de paix.
Qu'est-ce que la théorie des jeux ? Définition
La théorie des jeux étudie les interactions stratégiques : des situations où le résultat de chaque participant dépend non seulement de sa propre décision, mais aussi des décisions des autres. Pour analyser une telle situation, on la décrit avec quatre éléments :
- Les joueurs : ceux qui décident. Ce peuvent être des personnes, des entreprises, des États, des animaux ou des programmes informatiques.
- Les stratégies : les options entre lesquelles chaque joueur choisit, ou un plan complet pour chaque situation qu'il peut rencontrer.
- Les gains : ce que chaque joueur obtient pour chaque combinaison de stratégies, exprimé en nombres (argent, années de prison, points, descendants).
- L'information : ce que sait chaque joueur au moment de choisir. Aux échecs, on voit tout l'échiquier ; au poker, on ne voit pas les cartes de l'adversaire.
Une fois la situation ainsi décrite, la question devient : que doit faire chaque joueur, et que se passe-t-il si tout le monde raisonne soigneusement ? Les réponses surprennent souvent, car le choix le meilleur pour chacun pris isolément peut mener à un résultat moins bon pour tous.
Les notions clés de la théorie des jeux
Jeux à somme nulle et à somme non nulle
Dans un jeu à somme nulle, ce que gagne un joueur, l'autre le perd exactement : les gains s'additionnent toujours à zéro. Les échecs, le poker à deux et un penalty sont à somme nulle. Dans un jeu à somme non nulle, les deux camps peuvent gagner ou perdre ensemble. Le commerce, les négociations et l'essentiel de la vie économique en font partie, et c'est pourquoi la théorie des jeux ne parle pas seulement de gagner.
Stratégie dominante
Une stratégie est dominante si elle est le meilleur choix quoi que fassent les autres joueurs. Quand un joueur en a une, l'analyse est simple : il doit la jouer. Beaucoup de jeux célèbres sont intéressants justement parce que les stratégies dominantes de tous les joueurs, réunies, donnent un mauvais résultat.
L'équilibre de Nash
Un équilibre de Nash est un ensemble de stratégies, une par joueur, dans lequel personne ne peut faire mieux en changeant seulement son propre choix. C'est un point stable : une fois qu'on y est, personne n'a intérêt à en sortir seul. Deux voitures qui se croisent sont en équilibre si toutes deux roulent à droite, mais aussi si toutes deux roulent à gauche ; c'est pourquoi un pays n'a besoin de s'entendre que sur l'une des deux règles. La notion porte le nom de John Nash, qui a démontré en 1950 que tout jeu avec un nombre fini de joueurs et de stratégies possède au moins un équilibre.
Les stratégies mixtes
Parfois, tout choix prévisible peut être exploité. À pierre-feuille-ciseaux, celui qui joue toujours pierre perd à chaque fois contre feuille. L'équilibre consiste à jouer chaque option au hasard avec une probabilité d'un tiers. Choisir au hasard selon des probabilités fixées s'appelle une stratégie mixte, et c'est en les autorisant que le théorème de Nash s'applique à tout jeu fini. Les tireurs de penalty et les gardiens se comportent à peu près ainsi : celui qui tire toujours du même côté est facile à lire.
Jeux simultanés et séquentiels
Dans un jeu simultané, les joueurs choisissent en même temps sans voir le choix des autres (une enchère sous pli fermé, pierre-feuille-ciseaux). Dans un jeu séquentiel, ils jouent chacun leur tour et peuvent réagir aux coups précédents (les échecs, une négociation avec offre et contre-offre). On représente les jeux séquentiels par un arbre de jeu et on les résout par induction à rebours : on part de la fin, on cherche le meilleur dernier coup, puis le meilleur coup juste avant, et ainsi de suite jusqu'au début.
Jeux coopératifs et non coopératifs
La théorie des jeux non coopératifs étudie des joueurs qui décident chacun pour soi ; c'est là que se trouve l'équilibre de Nash. La théorie des jeux coopératifs se demande ce que des groupes de joueurs (des coalitions) peuvent obtenir ensemble et comment partager équitablement le résultat. Sa réponse la plus connue au partage est la valeur de Shapley, proposée par Lloyd Shapley en 1953 ; on s'en sert aujourd'hui aussi pour expliquer quelles données d'entrée ont déterminé la prédiction d'un modèle d'apprentissage automatique.
Le dilemme du prisonnier : le jeu le plus célèbre
Deux suspects sont arrêtés et interrogés dans des pièces séparées. Chacun peut se taire ou dénoncer l'autre. Si les deux se taisent, chacun écope d'un an de prison. Si l'un dénonce et que l'autre se tait, le dénonciateur est libéré et celui qui s'est tu prend trois ans. Si les deux se dénoncent, chacun prend deux ans.
| B se tait | B dénonce | |
|---|---|---|
| A se tait | 1 an chacun | A : 3 ans, B : libre |
| A dénonce | A : libre, B : 3 ans | 2 ans chacun |
Du point de vue de A : si B se tait, dénoncer le libère au lieu d'un an. Si B dénonce, dénoncer lui vaut deux ans au lieu de trois. Quoi que fasse B, dénoncer est meilleur pour A : c'est une stratégie dominante. Il en va de même pour B. Les deux dénoncent donc et prennent deux ans chacun, alors qu'en se taisant tous les deux ils n'en auraient pris qu'un. Le seul équilibre de Nash est pire pour les deux joueurs qu'un résultat qu'ils auraient atteint en se faisant confiance.
Le jeu a été imaginé en 1950 par Merrill Flood et Melvin Dresher à la RAND Corporation ; le mathématicien Albert Tucker lui a donné l'histoire des prisonniers et son nom. On retrouve la même structure dans les guerres des prix, la course aux armements, la surpêche et les accords sur le climat : chaque partie gagne à faire cavalier seul, et tout le monde perd si tous le font.
Ce qui change quand le jeu se répète
Joué une fois, le dilemme du prisonnier récompense la trahison. Joué de nombreuses fois avec le même partenaire, il change de nature, car la trahison d'aujourd'hui peut être punie demain. Vers 1980, le politologue Robert Axelrod a invité des chercheurs à envoyer des programmes qui s'affrontaient au dilemme répété. Le vainqueur fut l'un des plus simples, donnant-donnant (en anglais tit for tat), proposé par Anatol Rapoport : coopérer au premier tour, puis refaire ce que l'adversaire a fait au tour précédent. Axelrod a présenté les résultats dans The Evolution of Cooperation (1984). Sa leçon : réussissent les stratégies bienveillantes (ne jamais trahir en premier), qui répliquent, qui pardonnent et qui sont faciles à comprendre.
D'autres jeux classiques
- Le jeu de la poule mouillée (faucon-colombe) : deux conducteurs foncent l'un vers l'autre ; celui qui fait un écart perd la face, mais si aucun ne s'écarte, c'est l'accident. Il y a deux équilibres, chacun avec un joueur qui cède, et tout l'enjeu est de convaincre l'autre que ce ne sera pas vous.
- La chasse au cerf : deux chasseurs peuvent chasser ensemble un cerf (grosse prise qui exige les deux) ou chacun un lièvre (petit mais sûr). Chasser le cerf ensemble et chasser chacun son lièvre sont deux équilibres ; lequel se produit dépend de la confiance.
- Pile ou face apparié (matching pennies) : un joueur gagne si les deux pièces sont identiques, l'autre si elles diffèrent. Il n'y a aucun choix stable, seulement la stratégie mixte : pile ou face avec une probabilité d'un demi. C'est le jeu à somme nulle le plus simple.
Quand la théorie des jeux est-elle née ? Petite histoire
On raisonnait stratégiquement bien avant les premières équations, mais la théorie des jeux comme discipline mathématique a environ cent ans. Les grandes étapes :
| Année | Étape |
|---|---|
| 1838 | Antoine Augustin Cournot modélise deux entreprises qui choisissent leur production ; sa solution est un exemple précoce de ce qu'on appelle aujourd'hui un équilibre de Nash. |
| 1913 | Ernst Zermelo montre qu'aux échecs, soit les Blancs peuvent forcer la victoire, soit les Noirs, soit chaque camp peut forcer au moins la nulle. |
| 1921 | Émile Borel publie des travaux sur les stratégies mixtes. |
| 1928 | John von Neumann démontre le théorème du minimax pour les jeux à deux joueurs à somme nulle. |
| 1944 | Von Neumann et Oskar Morgenstern publient Theory of Games and Economic Behavior, généralement considéré comme l'acte de naissance de la discipline. |
| 1950 | John Nash définit l'équilibre de Nash ; Flood et Dresher créent le dilemme du prisonnier à la RAND. |
| 1953 | Lloyd Shapley introduit la valeur de Shapley pour partager les gains d'une coalition. |
| 1962 | David Gale et Lloyd Shapley publient l'algorithme d'acceptation différée pour les appariements stables. |
| 1973 | John Maynard Smith et George Price introduisent la stratégie évolutivement stable et font entrer la théorie des jeux en biologie. |
| 1984 | The Evolution of Cooperation de Robert Axelrod présente ses tournois du dilemme du prisonnier répété. |
| 1994 | John Nash, John Harsanyi et Reinhard Selten reçoivent le prix Nobel d'économie. |
| 2005 | Robert Aumann et Thomas Schelling reçoivent le prix pour leur analyse du conflit et de la coopération. |
| 2012 | Alvin Roth et Lloyd Shapley reçoivent le prix pour la théorie des allocations stables et la conception de marchés. |
| 2020 | Paul Milgrom et Robert Wilson reçoivent le prix pour leurs avancées en théorie des enchères et de nouveaux formats d'enchères. |
S'il ne faut retenir qu'une date, c'est 1944, l'année du livre de von Neumann et Morgenstern ; s'il faut le premier théorème, c'est le théorème du minimax de von Neumann, en 1928. La vie de Nash a ensuite inspiré le film Un homme d'exception (2001).
Le théorème du minimax
Le résultat de von Neumann de 1928 dit que, dans tout jeu à deux joueurs à somme nulle avec un nombre fini de stratégies, il existe une valeur v et une stratégie (éventuellement mixte) pour chaque joueur telles que le premier peut s'assurer en moyenne au moins v et le second peut le limiter à au plus v. Autrement dit, « maximiser son pire résultat » et « minimiser le meilleur résultat de l'adversaire » se rejoignent sur le même nombre. C'est pour cela qu'un jeu à somme nulle a une manière « correcte » de jouer bien définie, et cette même idée, appliquée coup par coup, est la façon de penser des programmes d'échecs.
À quoi sert la théorie des jeux ?
Économie et entreprise
La théorie des jeux fait aujourd'hui partie des outils de base de l'économie. Elle sert à modéliser la concurrence entre quelques grandes entreprises (l'oligopole), la fixation des prix et l'entrée sur un marché, les négociations entre syndicats et employeurs, et les contrats signés quand une partie en sait plus que l'autre. Un domaine voisin, la théorie des mécanismes (prix Nobel 2007 pour Leonid Hurwicz, Eric Maskin et Roger Myerson), raisonne à l'envers : il part du résultat souhaité et fixe les règles du jeu pour que les joueurs y arrivent en suivant leur propre intérêt.
Les enchères
Une enchère est un jeu, et ses règles changent la façon d'enchérir. Les États vendent les fréquences radio aux opérateurs mobiles avec des formats d'enchères issus de la théorie des jeux : l'enchère simultanée à tours multiples, à la conception de laquelle ont participé Milgrom et Wilson, a été utilisée pour la première fois par la Commission fédérale des communications (FCC) américaine en 1994. Et la publicité qui s'affiche sur une page web est généralement choisie par une enchère automatique éclair entre annonceurs.
Les marchés d'appariement : médecins et reins
Certains marchés ne peuvent pas utiliser de prix : on n'achète ni une place à l'école ni un rein. L'algorithme de Gale-Shapley trouve un appariement stable, dans lequel aucune paire de participants ne se préférerait mutuellement aux partenaires qu'on leur a attribués. Une version revue par Alvin Roth dans les années 1990 affecte aux États-Unis les jeunes diplômés en médecine aux programmes d'internat des hôpitaux. Roth a aussi contribué à mettre en place les dons croisés de rein, où des couples donneur-receveur incompatibles échangent leurs donneurs pour permettre davantage de greffes.
Politique et relations internationales
Pendant la guerre froide, la théorie des jeux a servi à penser la dissuasion nucléaire : comment rendre une menace crédible, et pourquoi une capacité de seconde frappe rend une première frappe inutile. Dans The Strategy of Conflict (1960), Thomas Schelling a montré comment l'engagement, les menaces crédibles et les « points focaux » (des solutions que l'on choisit sans se concerter, comme se retrouver à midi sous l'horloge de la gare) façonnent les négociations. Les mêmes outils servent à analyser les votes, la formation de coalitions et les accords sur le climat.
Biologie et évolution
Les animaux ne calculent pas leurs gains, mais la sélection naturelle le fait pour eux : les stratégies qui laissent plus de descendants se répandent. L'article de Maynard Smith et Price de 1973 a utilisé le jeu faucon-colombe pour expliquer pourquoi la plupart des combats entre animaux d'une même espèce sont des parades rituelles et non des luttes à mort. Une stratégie évolutivement stable est une stratégie qui, une fois répandue dans une population, ne peut pas être supplantée par une alternative rare. Les mêmes idées servent à étudier la coopération, le rapport entre les sexes et la concurrence entre bactéries et virus.
Informatique, IA et sécurité
Les programmes de jeu parcourent un arbre de jeu selon la règle du minimax : ils supposent que l'adversaire répondra toujours par son meilleur coup et choisissent le coup dont le pire cas est le meilleur. En 2017, le programme de poker Libratus, de l'université Carnegie Mellon, a battu des professionnels de haut niveau au Texas hold'em no limit en tête-à-tête, et en 2019 son successeur Pluribus a gagné à six joueurs ; tous deux calculaient des stratégies proches d'un équilibre plutôt que d'imiter le jeu humain. La théorie des jeux guide aussi la sécurité : depuis 2007, la police de l'aéroport de Los Angeles utilise un logiciel fondé sur les jeux de sécurité de Stackelberg qui répartit au hasard contrôles et patrouilles pour qu'on ne puisse pas les prévoir.
Vie quotidienne
Pas besoin d'équations pour profiter des grandes leçons. Avant une décision qui concerne d'autres personnes, demandez-vous comment elles réagiront. Cherchez une stratégie dominante. Repérez les cas où l'intérêt de chacun mène à un résultat pire pour tous (un dilemme du prisonnier) et cherchez alors comment faire tenir la coopération : relations répétées, réputation, accords respectés. Partager l'addition, choisir sa file à la caisse ou décider de marchander : autant de petits jeux.
La théorie des jeux et les jeux de ce site
Théorie des jeux et jeux de loisir se rejoignent surtout dans les jeux à deux joueurs sans hasard, comme le morpion, le Puissance 4 ou les dames. Il n'y a ni dés ni cartes cachées, donc, comme Zermelo l'a montré pour les échecs, chacun a un résultat fixé si les deux camps jouent parfaitement. Notre article sur les jeux résolus (en anglais) explique lesquels les ordinateurs ont percés : le morpion se termine par un match nul, au Puissance 4 le premier joueur gagne, et les dames se terminent par une nulle.
Les adversaires informatiques de nos jeux utilisent exactement l'idée du minimax issue du théorème de von Neumann, arrêtée à une profondeur limitée. Dans Quatre en ligne, l'ordinateur en niveau difficile regarde quatre coups à l'avance (en comptant ceux des deux joueurs), avec le minimax et l'élagage alpha-bêta, qui écarte les coups ne pouvant pas changer le résultat. Aux Dames, il calcule huit coups en niveau difficile, à Reversi cinq et au Mancala neuf. Comme la recherche s'arrête tôt, l'ordinateur ne joue pas parfaitement, et c'est pour cela qu'on peut le battre : tendez-lui un piège qui ne se referme qu'au-delà de son horizon.
Une branche à part, la théorie combinatoire des jeux, étudie justement ces jeux à information parfaite et sans hasard, comme le jeu de Nim, les fins de partie de go ou le Hex. Elle est née de la solution du jeu de Nim par Charles Bouton en 1901 et constitue un sujet distinct de la théorie des jeux économique décrite plus haut, même si les deux partagent le raisonnement à rebours depuis la fin de la partie.
Idées reçues
- « La théorie des jeux suppose que tout le monde est égoïste. » Elle suppose que les joueurs recherchent leurs gains, mais ces gains peuvent inclure le souci des autres, l'équité ou la réputation. La théorie dit comment agir compte tenu de ce que vous valorisez, pas ce que vous devez valoriser.
- « Un équilibre est le meilleur résultat. » Pas forcément. Le dilemme du prisonnier montre un équilibre pire pour tous qu'un autre résultat possible.
- « Les gens jouent comme le prévoit la théorie. » Souvent non. Dans des expériences comme le jeu de l'ultimatum, les gens refusent des offres injustes alors que refuser leur coûte de l'argent. La théorie des jeux comportementale étudie ces écarts.
- « C'est réservé aux mathématiciens. » Les idées centrales (joueurs, stratégies, gains, penser à la réponse de l'autre) ne demandent aucune mathématique et s'appliquent à toute décision qui implique d'autres personnes.
Questions fréquentes
Qu'est-ce que la théorie des jeux, en termes simples ?
La théorie des jeux est la mathématique des décisions dont le résultat dépend des décisions des autres. Elle décrit une situation par des joueurs, les stratégies que chacun peut choisir et le gain de chacun pour chaque combinaison de choix, puis se demande ce qu'un joueur raisonnable devrait faire et à quel résultat s'attendre.
Qui a inventé la théorie des jeux ?
On considère le mathématicien John von Neumann comme son fondateur. Il a démontré le théorème du minimax en 1928, et son livre Theory of Games and Economic Behavior, écrit en 1944 avec l'économiste Oskar Morgenstern, en a fait une discipline à part entière. Ernst Zermelo (1913) et Émile Borel (1921) avaient publié avant eux des travaux importants.
Qu'est-ce qu'un équilibre de Nash ?
Un équilibre de Nash est une combinaison de stratégies dans laquelle aucun joueur ne peut faire mieux en changeant seulement son propre choix, les autres gardant le leur. John Nash a démontré en 1950 que tout jeu fini en possède au moins un, si les joueurs ont le droit de tirer leurs choix au hasard.
À quoi sert la théorie des jeux ?
Elle sert à concevoir des enchères et des systèmes d'affectation (par exemple l'affectation des internes en médecine aux hôpitaux et les dons croisés de rein), à étudier la concurrence entre entreprises, la course aux armements et les négociations, à expliquer la coopération et les conflits chez les animaux, à organiser des patrouilles de sécurité et, en intelligence artificielle, à jouer aux échecs ou au poker.
La théorie des jeux parle-t-elle de jeux vidéo ?
Non. En théorie des jeux, un jeu est toute situation où plusieurs décideurs influencent mutuellement leurs résultats, comme une guerre des prix ou une négociation. Les jeux de société et les jeux vidéo n'en sont qu'un petit exemple, même si c'est bien le principe du minimax, issu de la théorie des jeux, qui permet à l'ordinateur de choisir ses coups dans des jeux comme le Puissance 4 ou les dames.
