Théorie des jeux

Les notions fondamentales de la théorie des jeux

Quand le résultat de chacun dépend aussi des choix des autres, décider devient un jeu. Cinq planches pour en saisir les idées maîtresses : le tableau des gains, le tirage au sort, l'arbre des coups successifs, la répétition qui fait naître la coopération, et l'évolution des populations.

Le vocabulaire en une page

La théorie des jeux étudie les situations d'interdépendance stratégique : mon gain dépend de ma décision, mais aussi de celle des autres, qui raisonnent comme moi. Un « jeu » n'a donc rien de frivole : une négociation, une guerre des prix, un contrôle fiscal, un combat entre animaux en sont. Six mots suffisent pour tout décrire.

Notion	En une phrase	Où la voir
Joueurs	Ceux qui décident. Dans cette page, ils sont deux : Ligne (toujours en bleu) choisit une ligne du tableau, Colonne (toujours en violet) choisit une colonne.	partout
Stratégies	Les choix possibles de chaque joueur. Une stratégie pure est un choix ferme ; une stratégie mixte est un tirage au sort entre plusieurs choix.	planches 1 et 2
Gains	Un nombre par joueur et par issue, qui mesure sa satisfaction. Chacun cherche à rendre son gain le plus grand possible, sans se soucier de celui de l'autre.	planche 1
Meilleure réponse	Le choix qui rapporte le plus étant donné ce que fait l'adversaire.	planches 1 et 2
Équilibre de Nash	Une situation où chacun joue une meilleure réponse à l'autre : personne ne regrette son choix tant que l'autre ne change pas le sien.	planches 1 à 5
Information	Ce que chacun sait au moment de jouer. Coups simultanés : un tableau (forme normale). Coups successifs : un arbre (forme extensive).	planche 3

Le fil des planches : on part d'un tableau de gains (1), on découvre qu'il faut parfois jouer au hasard (2), on fait jouer les joueurs l'un après l'autre (3), puis plusieurs fois de suite (4), et l'on finit par remplacer les joueurs rationnels par des populations qui se reproduisent selon leurs gains (5). Tous les chiffres affichés sont calculés dans la page et contrôlés par une seconde méthode indépendante.

Planche 1

Le tableau des gains : dominance et équilibre de Nash

Un jeu à coups simultanés se résume à un tableau. Chaque case correspond à un couple de choix et contient deux nombres : le gain de Ligne, puis celui de Colonne. Pour chaque colonne, le meilleur gain de Ligne est entouré en bleu ; pour chaque ligne, le meilleur gain de Colonne est entouré en violet. Une case où les deux nombres sont entourés est un équilibre de Nash : aucun des deux n'a intérêt à changer seul. Les petites flèches montrent dans quelle direction un joueur voudrait s'échapper d'une case.

Choisissez un exemple dans la liste. En mode « modifier », un clic sur un nombre l'augmente ou le diminue de 1 : la moitié gauche d'une case règle le gain de Ligne, la moitié droite celui de Colonne.

équilibre de Nashissue Pareto-optimalestratégie éliminée

Jeu

Modifier les gains :

Équilibres de Nash en stratégies pures

—

Contrôle : recherche case par case de toute déviation profitable

—

Stratégie strictement dominante

—

Issues Pareto-optimales

—

Somme des gains : la meilleure possible / au meilleur équilibre

—

Ce qu'il faut voir. Dans le dilemme du prisonnier, « Trahir » rapporte plus que « Coopérer » quoi que fasse l'autre : c'est une stratégie dominante, et l'unique équilibre est (Trahir, Trahir), avec 1 point chacun, alors que (Coopérer, Coopérer) en donnait 3. L'équilibre n'est donc pas forcément Pareto-optimal (une issue est Pareto-optimale si on ne peut améliorer le sort de l'un sans dégrader celui de l'autre) : la rationalité individuelle peut produire un gâchis collectif. La bataille des sexes, la chasse au cerf et la poule mouillée ont deux équilibres — il faut alors se coordonner ; pile ou face n'en a aucun en stratégies pures, ce qui mène à la planche 2. Enfin, l'élimination des stratégies dominées résout parfois tout le jeu (exemple 2 × 3), mais pas toujours (exemple 3 × 3, où rien n'est dominé et pourtant l'équilibre est unique).

Planche 2

Tirer au sort : les stratégies mixtes

Un contrôleur qui inspecterait toujours, ou jamais, serait facile à déjouer. Il a intérêt à être imprévisible : contrôler au hasard, avec une certaine probabilité. Une stratégie mixte est ce tirage au sort. Dans le carré, l'abscisse p est la probabilité que Ligne joue sa première stratégie, l'ordonnée q celle de Colonne. La courbe bleue donne les meilleures réponses de Ligne à chaque q, la violette celles de Colonne à chaque p : leurs croisements sont exactement les équilibres de Nash. Déplacez le point orange : les flèches indiquent où chaque joueur voudrait aller.

Le carré des stratégies mixtes. Point orange déplaçable ; en orange pâle, la trajectoire du « jeu fictif ».

En haut : gains espérés de Ligne pour chacune de ses deux stratégies, selon q. En bas : gains espérés de Colonne selon p. Le point rouge marque le croisement.

Jeu

Amende si le fraudeur est pris

Gain d'une fraude non détectée

Coût d'un contrôle

Équilibre mixte : p*

—

Équilibre mixte : q*

—

Formule contre dichotomie sur le croisement des droites

—

Indifférence à l'équilibre : |écart entre les deux gains|

—

Nombre d'équilibres (purs + mixtes)

—

Jeu fictif : distance à l'équilibre le plus proche

—

Le principe d'indifférence. À l'équilibre mixte, chaque joueur tire au sort de façon à rendre l'autre indifférent entre ses deux choix : sinon l'autre jouerait à coup sûr le meilleur et le tirage n'aurait plus de raison d'être. Conséquence surprenante dans le jeu du contrôleur : la probabilité de fraude d'équilibre vaut p* = coût du contrôle ÷ gain de la fraude, sans l'amende. Faites varier l'amende : seule la fréquence des contrôles change (q* = gain ÷ (gain + amende)), la fraude reste la même. C'est le « paradoxe de Tsebelis ». Le nombre total d'équilibres est toujours impair (1 ou 3 ici), comme l'annonce le théorème de Wilson pour les jeux non dégénérés. Le jeu fictif (chacun répond au mieux à la fréquence passée des coups adverses) spirale vers l'équilibre : Miyasawa a démontré en 1961 qu'il converge toujours dans les jeux 2 × 2.

Planche 3

Jouer chacun son tour : l'arbre et l'induction à rebours

Quand les coups se succèdent, le jeu se dessine comme un arbre : chaque nœud est un moment de décision, chaque branche un choix, chaque feuille une issue avec ses gains. Pour le résoudre, on part de la fin : au dernier nœud, le joueur choisit sa meilleure branche ; on remplace ce nœud par le résultat, et l'on remonte. C'est l'induction à rebours (Zermelo, 1913). Elle sélectionne parmi les équilibres de Nash ceux qui restent rationnels à chaque étape : les équilibres parfaits en sous-jeux (Selten, 1965).

Un Entrant (bleu) hésite à entrer sur le marché d'un Titulaire (violet), qui menace de déclencher une guerre des prix. Gains notés (Entrant ; Titulaire).

Gain du Titulaire en cas de guerre des prix

Le même jeu écrit comme un tableau (forme normale) :

Équilibres de Nash du tableau

—

Équilibre parfait (induction à rebours)

—

La menace de guerre des prix

—

Une menace n'engage que celui qui y croit. Tant que la guerre des prix coûte au Titulaire (gain inférieur à 4, le gain du partage), le tableau possède deux équilibres de Nash : (Entrer, Partager) et (Rester dehors, Guerre). Le second repose sur une menace que le Titulaire n'exécuterait jamais une fois l'Entrant installé : elle n'est pas crédible, et l'induction à rebours l'écarte. Poussez le curseur au-delà de 4 : la guerre devient rentable pour le Titulaire, la menace devient crédible, et l'Entrant reste dehors.

Le mille-pattes de Rosenthal (1981). À chaque nœud, le joueur peut prendre (descendre : le jeu s'arrête) ou passer (aller à droite : le pot grossit ; « prendre » en rouge une fois l'induction faite). Au nœud k, celui qui prend reçoit k + 1 et l'autre k − 1 ; si tout le monde passe jusqu'au bout, chacun reçoit n.

Nombre de nœuds n

Issue de l'induction à rebours

—

Si tous deux passent jusqu'au bout

—

Profils de stratégies examinés un par un

—

Équilibres de Nash trouvés / dont l'issue est l'arrêt au 1ᵉʳ nœud

—

Le paradoxe du mille-pattes. Au dernier nœud, prendre rapporte n + 1 au lieu de n : on prend. Donc à l'avant-dernier, passer ne rapporterait que n − 1 au lieu de n : on prend aussi. De proche en proche, le premier joueur prend tout de suite et repart avec 2, alors que la patience aurait donné n à chacun. L'examen exhaustif de tous les profils de stratégies confirme que tous les équilibres de Nash — pas seulement l'équilibre parfait — s'arrêtent au premier nœud. Dans les expériences, pourtant, la plupart des gens passent plusieurs fois : la rationalité supposée « connue de tous, à tous les niveaux » est une hypothèse très forte.

Planche 4

Le jeu qui se répète : la coopération peut naître

Joué une seule fois, le dilemme du prisonnier mène à la trahison. Mais si les mêmes joueurs se retrouvent à chaque tour, trahir aujourd'hui expose à des représailles demain. En 1980, Robert Axelrod organise un tournoi : des stratégies écrites par des chercheurs s'affrontent deux à deux pendant 200 tours. Le gagnant est la plus simple : Donnant-donnant — coopérer au premier tour, puis refaire ce que l'autre a fait au tour précédent. Rejouez le tournoi ci-dessous : chaque stratégie rencontre toutes les autres (et son propre double). Gains par tour : 3 chacun si l'on coopère, 1 chacun si l'on trahit, et en cas de désaccord T pour le traître et 0 pour la victime.

Classement : gain moyen par tour, toutes rencontres confondues.

Gain moyen par tour de la stratégie en ligne contre celle en colonne (plus c'est foncé, plus c'est élevé).

Tentation T (gain du traître)

Nombre de tours par rencontre

Bruit : probabilité qu'un coup soit mal exécuté

Une rencontre au ralenti

Rencontrecontre

Les 50 premiers tours : ■ coopérer, ■ trahir, ● coup déformé par le bruit. Mettez un peu de bruit et regardez Donnant-donnant contre lui-même : une seule erreur déclenche un écho de représailles que Pavlov, lui, sait éteindre.

Vainqueur du tournoi

—

Taux de coopération dans le tournoi

—

Contrôle : Traître contre Donnant-donnant sans bruit, simulé / formule

—

Seuil de patience du Rancunier δ* = (T − 3)/(T − 1)

—

À δ*, coopérer toujours contre trahir une fois : écart des gains actualisés

—

Pourquoi la répétition change tout. Si l'on accorde au gain de demain le poids δ (entre 0 et 1) par rapport à celui d'aujourd'hui, coopérer pour toujours rapporte 3/(1 − δ) ; trahir rapporte T une fois, puis 1 à chaque tour quand l'autre ne pardonne plus : T + δ/(1 − δ). La coopération tient dès que δ dépasse (T − 3)/(T − 1) : avec T = 5, il suffit d'accorder à l'avenir la moitié du poids du présent. Les qualités de Donnant-donnant selon Axelrod : il est bienveillant (ne trahit jamais le premier), susceptible (riposte aussitôt), indulgent (pardonne dès que l'autre revient) et transparent. Notez qu'il ne gagne aucune rencontre individuelle — au mieux il fait jeu égal — mais il gagne le tournoi. Le bruit change le palmarès : avec 1 ou 2 % de coups mal exécutés, Généreux passe en tête, car il sait pardonner une erreur ; à 5 % et au-delà, les représailles deviennent si fréquentes que les stratégies dures (Traître à 5 %, Rancunier à 10 %, avec le tirage par défaut) reprennent l'avantage.

Planche 5 — signature

Quand les gains deviennent des descendants : les jeux évolutionnaires

En 1973, John Maynard Smith et George Price ont une idée radicale : supprimer la rationalité. Des animaux programmés pour une stratégie se rencontrent au hasard ; leur gain se traduit en nombre de descendants. Les stratégies qui rapportent plus que la moyenne se répandent. Cette règle s'appelle la dynamique du réplicateur : le taux de croissance de la part x_i d'une stratégie est son gain moins le gain moyen de la population. Et pourtant, la population finit souvent… sur un équilibre de Nash, que personne n'a calculé. Une stratégie évolutivement stable (SES) est un état qu'aucun petit groupe de mutants ne peut envahir.

Deux animaux se disputent une ressource de valeur V. Le faucon attaque toujours ; la colombe parade puis s'enfuit si on l'attaque. Deux faucons se battent : chacun gagne la ressource une fois sur deux mais risque une blessure de coût C, d'où (V − C)/2 en moyenne. Deux colombes partagent : V/2 chacune. Un faucon face à une colombe prend tout : V contre 0. Ici, 400 individus (par défaut) se rencontrent au hasard huit fois par génération puis se reproduisent proportionnellement à leurs gains.

La population : ▲ faucons, ● colombes. Les traits fins sont quelques combats de la génération en cours.

Part des faucons au fil des générations : population simulée, dynamique du réplicateur (population infinie), équilibre prédit.

Valeur de la ressource V

Coût d'une blessure C

Faucons au départ

Taille de la population

Génération

—

Équilibre prédit : part de faucons V/C (ou 1 si V ≥ C)

—

Part moyenne simulée (générations 150 à 300)

—

Réplicateur après 300 générations : écart à la prédiction

—

Gains égaux à l'équilibre : faucon − colombe

—

Ni tous faucons, ni tous colombes. Dans une population de colombes, un faucon rafle tout : il prospère. Dans une population de faucons, une colombe ne se blesse jamais et fait mieux que des combattants qui s'estropient quand C > V. La population se fixe donc sur un mélange où les deux stratégies rapportent autant : une part V/C de faucons. C'est précisément la probabilité d'attaquer dans l'équilibre de Nash mixte du jeu (planche 2) — ici obtenue sans qu'aucun animal ne calcule rien. Si V ≥ C, la blessure ne fait plus peur et les faucons envahissent tout. Une mutation de 0,2 % par naissance empêche le hasard d'éteindre définitivement une espèce. Sur 300 générations, la moyenne simulée fluctue d'environ un à deux points autour de V/C ; sur 20 000 générations (cinq tirages, V = 4, C = 10), elle tombe entre 40,1 et 40,3 %, la mutation tirant très légèrement vers 50 %.

Avec trois stratégies, l'état de la population est un point d'un triangle : chaque sommet est une population pure, et la distance aux côtés donne les proportions. Les flèches indiquent le sens de l'évolution. Touchez le triangle pour lâcher une population et suivre son destin.

Triangle des stratégies. ● point de repos stable (SES), ○ point de repos instable, ● gris : neutre ; une arête grise épaisse est faite de points de repos.

Jeu

Valeur V

Coût C

Tours par rencontre

Points de repos stables (SES)

—

Valeurs propres aux sommets : formule A_ji − A_ii contre jacobienne numérique

—

Dérive de x₁ + x₂ + x₃ le long des trajectoires

—

Ce que l'évolution sait faire… et ne sait pas faire. Le Bourgeois se bat s'il est propriétaire du territoire et cède s'il est intrus : en respectant une convention arbitraire, il évite les combats coûteux, et son sommet attire tout le triangle (SES) dès que C > V. Avec le dilemme du prisonnier répété, Donnant-donnant résiste aux traîtres, mais l'arête Coopérateur–Donnant-donnant est faite de points neutres : quand tout le monde coopère, rien ne distingue celui qui sait riposter de celui qui ne sait pas. Les coopérateurs naïfs peuvent alors s'infiltrer par simple dérive… et rouvrir la porte aux traîtres. Les valeurs propres aux sommets, lues sur la matrice des gains, coïncident avec celles de la jacobienne calculée numériquement.

Repères

Deux siècles de théorie des jeux

1838Antoine-Augustin Cournot décrit un duopole où chaque producteur répond au mieux à l'autre : la première idée d'équilibre.
1913Ernst Zermelo montre que les échecs sont « déterminés » : l'un des joueurs a une stratégie gagnante ou chacun peut forcer la nulle — l'induction à rebours est née.
1921Émile Borel introduit les stratégies mixtes et pose la question du meilleur tirage au sort.
1928John von Neumann démontre le théorème du minimax pour les jeux à somme nulle.
1944Von Neumann et Oskar Morgenstern publient Theory of Games and Economic Behavior : la discipline est fondée.
1950John Nash démontre que tout jeu fini possède un équilibre, éventuellement en stratégies mixtes. Merrill Flood et Melvin Dresher font jouer l'expérience que Albert Tucker baptisera « dilemme du prisonnier ».
1951George Brown propose le jeu fictif ; Julia Robinson prouve sa convergence pour les jeux à somme nulle (Miyasawa l'étendra aux jeux 2 × 2 en 1961).
1965Reinhard Selten définit l'équilibre parfait en sous-jeux, qui écarte les menaces non crédibles.
1967John Harsanyi traite les jeux à information incomplète.
1971Robert Wilson démontre que le nombre d'équilibres d'un jeu non dégénéré est impair.
1973John Maynard Smith et George Price inventent la stratégie évolutivement stable (faucons et colombes).
1980Tournois de Robert Axelrod : victoire de Donnant-donnant, proposé par Anatol Rapoport.
1981Robert Rosenthal présente le mille-pattes.
1994Prix Nobel d'économie à Nash, Harsanyi et Selten ; suivront Aumann et Schelling (2005), Shapley et Roth (2012).

Synthèse

Ce qu'il faut retenir

L'équilibre n'est pas l'optimum

Un équilibre de Nash dit seulement que personne ne regrette son choix seul. Il peut être collectivement désastreux (dilemme du prisonnier), multiple (coordination) ou n'exister qu'en tirant au sort (pile ou face).

Le hasard est une stratégie

À l'équilibre mixte, on tire au sort pour rendre l'autre indifférent. D'où des conclusions contre-intuitives : alourdir l'amende réduit les contrôles nécessaires, pas la fraude.

Le temps change le jeu

Jouer en séquence oblige à des menaces crédibles ; se rencontrer souvent rend la coopération rationnelle. Et des populations sans aucune rationalité retrouvent, par la sélection, les équilibres des stratèges.

Pour aller plus loin

Les autres pages de la série approfondissent chacune une notion : le jeu à somme nulle et le minimax (pierre-papier-ciseaux), la stratégie mixte et la dynamique des réplicateurs à trois stratégies, le duopole et le triopole de Cournot, le jeu de l'ultimatum, la congestion routière, la tragédie des biens communs, le jeu de Nim et la théorie de Sprague-Grundy, ainsi que les jeux de bridge et d'échecs.

Ce que la page simplifie. Les gains sont supposés connus de tous (information complète) ; les jeux bayésiens de Harsanyi lèvent cette hypothèse. Les équilibres mixtes « partiellement » mélangés des jeux dégénérés ne sont pas tracés. La simulation des faucons et des colombes utilise le modèle de Wright-Fisher : la génération suivante est tirée au sort, chaque parent ayant une chance proportionnelle à son gain augmenté d'un gain de base positif.

Lectures. R. Axelrod, Donnant donnant (Odile Jacob) ; J. Maynard Smith, Evolution and the Theory of Games (1982) ; M. Yildizoglu, Introduction à la théorie des jeux (Dunod) ; R. Gibbons, A Primer in Game Theory (1992), d'où vient l'exemple d'élimination en cascade de la planche 1.