Des marchands d'eau minérale de Cournot aux algorithmes qui affectent aujourd'hui des étudiants et des médecins, trois siècles d'idées pour décider quand les autres décident aussi. Cinq moments fondateurs, chacun rejoué sous vos yeux.
0
Trois siècles en une frise
Chaque point est un jalon ; touchez-le pour lire sa notice. En haut, les jalons sont espacés régulièrement ; en bas, la règle les replace à leur vraie date. L'éventail des traits montre l'accélération : deux siècles de précurseurs isolés, puis une explosion après 1944, l'année où John von Neumann et Oskar Morgenstern publient le livre fondateur.
précurseursfondationsl'âge d'orapplications et prix Nobel
Planche 1
1838 — Cournot et les deux sources d'eau minérale
Dans ses Recherches sur les principes mathématiques de la théorie des richesses, le mathématicien français Antoine-Augustin Cournot imagine deux propriétaires de sources identiques qui vendent la même eau. Le prix baisse quand la quantité totale mise en vente augmente. Chacun choisit sa production en supposant celle de l'autre fixée : c'est la meilleure réponse. Cournot décrit alors un va-et-vient — l'un s'ajuste, puis l'autre — et montre qu'il se fixe sur un point où chacun répond au mieux à l'autre. Il venait de trouver, 112 ans avant Nash, ce que nous appelons un équilibre de Nash.
Les deux courbes de réaction de Cournot : production optimale du propriétaire 1 selon celle du 2, et inversement. L'escalier orange suit le tâtonnement, chacun à son tour. Touchez le carré pour choisir le point de départ.
Prix de marché selon le nombre de vendeurs : monopole (1 vendeur), équilibre de Cournot, et la droite coût de production vers laquelle le prix descend quand les vendeurs se multiplient.
Équilibre par la formule (a − c)/3 pour chacun
—
Point atteint par le tâtonnement : écart à la formule
—
Rapport mesuré entre deux écarts successifs
—
Profit total : monopole / deux vendeurs de Cournot
—
Prix avec n vendeurs : formule (a + n c)/(n + 1) / calcul direct
—
Ce que Cournot a vu. Chaque ajustement divise l'écart à l'équilibre par deux et en change le signe (rapport mesuré −0,5) : l'escalier tourne autour du point et s'y enroule. À l'équilibre, chaque propriétaire vend (a − c)/3 ; ensemble, ils vendent plus qu'un monopoleur et gagnent moins (8/9 du profit de monopole) : se faire concurrence leur coûte, ce qui profite aux acheteurs. Avec n vendeurs, le prix descend vers le coût de production — Cournot en tire la première théorie mathématique de la concurrence. En 1883, Joseph Bertrand objecte que si les vendeurs fixaient leurs prix plutôt que leurs quantités, ils se sous-coteraient jusqu'au coût dès deux vendeurs : le choix des stratégies change tout, leçon que la théorie des jeux retiendra.
Planche 2
1913 — Zermelo : tout jeu fini est déjà joué d'avance
Dans les actes du congrès international des mathématiciens de Cambridge (tenu en 1912, publiés en 1913), Ernst Zermelo pose une question sur les échecs : existe-t-il une position à partir de laquelle un joueur peut forcer la victoire ? Sa réponse vaut pour tout jeu fini à deux joueurs où chacun voit tout : chaque position a une valeur — gagnée, perdue ou nulle — qui se calcule en remontant depuis les fins de partie. Pour les échecs, le calcul est hors de portée. Pour le morpion, la machine le fait en un instant : la page parcourt toutes les positions et les colore.
Vous jouez les ×, la machine les ○ et joue parfaitement. Les cases libres affichent la valeur du coup pour celui qui doit jouer : G gagne, N nul, P perd (contre une défense parfaite).
Les positions légales selon le nombre de pions posés, coloriées par leur valeur : × gagne, nulle, ○ gagne. Le bouton rejoue le raisonnement de Zermelo à rebours, des grilles pleines vers la grille vide.
Valeur de la grille vide
—
Positions atteignables (exploration de l'arbre)
—
Contrôle : grilles légales parmi les 3⁹ = 19 683 coloriages
—
Parties possibles (toutes les suites de coups)
—
dont gagnées par × / par ○ / nulles
—
Votre partie : valeur de la position actuelle
—
Un jeu résolu n'a plus de suspense. Les 5 478 positions du morpion se colorient en remontant depuis la fin, et la grille vide est nulle : deux joueurs parfaits font toujours match nul. Pourtant, parmi les 255 168 parties possibles, la moitié environ est gagnée par celui qui commence — les erreurs sont faciles. C'est exactement l'argument de Zermelo : pour les échecs aussi, la position initiale a une valeur (gain des blancs, des noirs, ou nulle), mais personne ne la connaît, car le nombre de positions dépasse 1040. Le raisonnement à rebours deviendra l'induction à rebours, outil central de la théorie.
Planche 3
1928 — Von Neumann : le théorème du minimax
En 1921, Émile Borel se demande s'il existe une « meilleure manière de jouer » à un jeu où ce que l'un gagne, l'autre le perd (jeu à somme nulle), et pressent qu'il faut tirer ses coups au sort. Il en doute pour les grands jeux. En 1928, à 24 ans, John von Neumann tranche : si chacun peut mélanger ses stratégies, le gain que Ligne peut garantir (le maximin) est exactement égal à la perte que Colonne peut limiter (le minimax). Ce nombre commun est la valeur du jeu. Ci-dessous, Ligne a deux choix et mélange avec une probabilité p ; chaque droite donne son gain moyen face à une colonne. Colonne choisira toujours la droite la plus basse : Ligne vise donc le sommet de l'enveloppe inférieure.
Une droite par colonne, l'enveloppe inférieure en rouge épais, son sommet (le maximin) marqué par un point. Le curseur orange suit votre choix de p.
Gains de Ligne (modifiables) :
Gain garanti par votre p (pire colonne)
—
Maximin de Ligne (sommet cherché par balayage puis section dorée)
—
Minimax de Colonne (supports de 1 ou 2 colonnes, calcul exact)
—
Écart maximin − minimax (théorème de von Neumann)
—
Stratégies optimales p* et q*
—
Sans tirage au sort : meilleur gain pur garanti / meilleure perte pure
—
Pourquoi von Neumann aimait le poker. Dans le bluff, Ligne reçoit une carte haute ou basse ; avec une carte basse, elle peut miser quand même (bluffer). Colonne, qui ne voit pas la carte, peut suivre ou se coucher. Si Ligne ne bluffait jamais, Colonne se coucherait à chaque mise ; si elle bluffait toujours, Colonne suivrait toujours. L'équilibre : bluffer une fois sur trois et suivre deux fois sur trois, pour une valeur de 1/3 en faveur de Ligne. Le bluff n'est pas une ruse psychologique mais une nécessité mathématique. Sans tirage au sort, le gain garanti et la perte limitée ne coïncident pas (ligne orange) ; avec, ils coïncident toujours — sauf dans le jeu à point-selle, où le tirage est inutile. En 1944, von Neumann et l'économiste Oskar Morgenstern bâtiront sur ce théorème le livre Theory of Games and Economic Behavior.
Planche 4
1950 — Nash : un équilibre existe toujours
Le minimax ne vaut que si l'un perd ce que l'autre gagne. La plupart des situations réelles ne sont pas ainsi : on peut gagner ensemble ou perdre ensemble. En 1950, John Nash, doctorant de 21 ans à Princeton, démontre en une page que tout jeu fini possède au moins un équilibre, éventuellement en stratégies mixtes. Sa preuve de 1951 est remarquable : il fabrique une transformation T qui déplace chaque profil de stratégies vers les choix qui rapportent davantage, puis invoque le théorème du point fixe de Brouwer — toute transformation continue d'un carré dans lui-même laisse au moins un point immobile. Un point immobile de T, c'est un profil que personne n'a intérêt à modifier : un équilibre.
Le carré des stratégies mixtes (p pour Ligne, q pour Colonne). Chaque flèche va de x vers T(x) ; le fond est d'autant plus clair que x bouge peu. Les points fixes sont trouvés par la page. Touchez le carré pour itérer T depuis un point.
L'image du quadrillage par T : le carré est plié et tassé, mais retombe entièrement dans lui-même — c'est tout ce qu'exige Brouwer. Les points rouges sont ceux qui ne bougent pas.
Points fixes de T trouvés (recherche numérique)
—
Contrôle : équilibres calculés par le principe d'indifférence, écart maximal
—
|T(x) − x| au point fixe
—
Itération de T depuis votre point : distance au point fixe le plus proche
—
Exister n'est pas savoir y aller. Brouwer garantit qu'un point fixe existe, il ne dit pas comment le trouver : dans pile ou face, les itérations de T tournent autour de l'équilibre sans s'en approcher (encore à 0,25 environ après 2 000 itérations), alors que dans les autres jeux elles s'en approchent, lentement (à moins de 10−3 après 2 000 itérations). La même année 1950, à la RAND Corporation, Merrill Flood et Melvin Dresher font jouer cent fois un jeu dont l'unique équilibre est la défiance mutuelle — et observent beaucoup de coopération. Albert Tucker l'habille d'une histoire de deux prisonniers pour une conférence à Stanford : le dilemme du prisonnier était né. Nash recevra le prix Nobel d'économie en 1994, avec John Harsanyi et Reinhard Selten.
Planche 5 — signature
1962 — Gale et Shapley : des mariages stables aux affectations
Dans un article de l'American Mathematical Monthly intitulé « Admissions à l'université et stabilité du mariage », David Gale et Lloyd Shapley posent la question suivante : des candidats classent des établissements, les établissements classent les candidats ; comment former des couples pour qu'aucun candidat et aucun établissement ne préfèrent tous deux s'associer entre eux plutôt qu'à leur partenaire attitré ? Un tel couple frustré s'appelle une paire bloquante ; une affectation sans paire bloquante est stable. Leur algorithme de l'acceptation différée en trouve toujours une : chaque candidat libre propose à son établissement préféré parmi ceux qui ne l'ont pas encore refusé ; chaque établissement garde provisoirement la meilleure proposition reçue et refuse les autres. On recommence jusqu'à ce que tout le monde soit placé.
À gauche les candidats, à droite les établissements. Trait orange : proposition en cours ; trait bleu : acceptation provisoire ; éclair rouge : refus. Le petit nombre à côté de chaque nom est le rang du partenaire actuel dans sa liste (1 = premier choix).
Toutes les affectations stables, trouvées en examinant une à une les n! affectations possibles. Abscisse : rang moyen obtenu par les candidats ; ordonnée : rang moyen obtenu par les établissements (en bas à gauche = tout le monde comblé). ■ résultat quand les candidats proposent, ■ quand les établissements proposent.
Les listes de préférences (de la plus aimée à la moins aimée) :
Propositions faites / tours
—
Paires bloquantes du résultat (examen de tous les couples)
Chaque proposant obtient son meilleur partenaire stable ?
—
Rang moyen : candidats / établissements
—
Affectation « au premier vœu » : paires bloquantes
—
Un théorème qui place des millions de personnes. L'examen exhaustif confirme les deux résultats de Gale et Shapley : l'affectation obtenue est toujours stable, et le côté qui propose obtient, chacun individuellement, le meilleur partenaire possible parmi toutes les affectations stables — tandis que l'autre côté obtient le pire. Qui propose n'est donc pas un détail technique mais un choix politique. La procédure naïve « chacun reçoit son premier vœu s'il reste de la place, et ainsi de suite », où chaque tour est définitif, laisse au contraire souvent des paires bloquantes (pas toujours : essayez plusieurs tirages), donc des gens qui ont intérêt à tricher ou à contourner le système. En 1984, Alvin Roth découvre que le système d'affectation des internes en médecine américains, en service depuis 1952, appliquait déjà sans le savoir l'acceptation différée ; il en conçoit ensuite de nouvelles versions pour les écoles de New York et de Boston et pour les dons croisés de reins. Shapley et Roth reçoivent le prix Nobel d'économie en 2012.
Synthèse
Ce qu'il faut retenir
Une idée plus ancienne que son nom
L'équilibre apparaît chez Cournot en 1838, le raisonnement à rebours chez Zermelo en 1913, le tirage au sort chez Borel en 1921. Il a fallu von Neumann puis Nash pour en faire une théorie.
Trois théorèmes d'existence
Zermelo : toute position d'un jeu fini a une valeur. Von Neumann : maximin = minimax. Nash : tout jeu fini a un équilibre. Aucun ne dit comment le trouver vite — d'où un siècle d'algorithmes.
De la théorie aux institutions
Après 1970, la théorie conçoit des règles : enchères de fréquences (Milgrom et Wilson, Nobel 2020), affectations stables (Gale, Shapley, Roth), mécanismes incitatifs (Hurwicz, Maskin, Myerson, Nobel 2007).
Pour aller plus loin
Textes fondateurs. A.-A. Cournot, Recherches sur les principes mathématiques de la théorie des richesses (1838), chapitre VII ; E. Zermelo, « Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels » (1913) ; É. Borel, « La théorie du jeu et les équations intégrales à noyau symétrique gauche » (1921) ; J. von Neumann, « Zur Theorie der Gesellschaftsspiele » (1928) ; J. von Neumann et O. Morgenstern, Theory of Games and Economic Behavior (1944) ; J. Nash, « Equilibrium points in n-person games » (1950) et « Non-cooperative games » (1951) ; D. Gale et L. Shapley, « College Admissions and the Stability of Marriage » (1962).
Histoire. W. Poundstone, Le Dilemme du prisonnier ; R. Leonard, Von Neumann, Morgenstern, and the Creation of Game Theory (2010) ; S. Nasar, Un homme d'exception (biographie de Nash).
Ce que la page simplifie. Le marché de Cournot est linéaire (prix = a − quantité totale). La transformation de Nash est celle de 1951, appliquée aux jeux 2 × 2. Les préférences « communes » de la planche 5 mélangent un classement partagé par tous et un classement individuel tiré au hasard, ce qui réduit le nombre d'affectations stables.
Les autres pages de la série reprennent les notions en détail : les notions fondamentales, le minimax à pierre-papier-ciseaux, le triopole de Cournot, l'ultimatum, le jeu de Nim, les jeux d'échecs et de bridge.