Théorie des jeux et équilibre de Nash

Décider seul, décider contre quelqu'un

Un serveur tombe en panne avec une probabilité de 3 %. Doubler la machine coûte 4 000 €, la panne en coûterait 200 000 €. On compare $0{,}03 \times 200\,000 = 6\,000$ € de perte espérée à 4 000 € de dépense certaine, on double la machine, et c'est réglé. L'espérance, vue dans le chapitre sur les probabilités, est la moyenne des issues pondérées par leurs probabilités, $E = \sum p_i\,g_i$. La météo, la panne, le hasard : ils ne réagissent pas à la décision.

Il suffit de changer une seule chose. L'entreprise ne se contente plus d'acheter : elle répond à un appel d'offres, face à un concurrent qui fixe son prix au même moment qu'elle. Sa marge dépend alors du prix de l'autre, qui raisonne de la même façon, et qui sait qu'elle raisonne ainsi. Le calcul d'espérance ne suffit plus. Pour l'écrire, il faudrait connaître la probabilité de chaque prix du concurrent, et ce prix n'est pas un hasard qu'on mesure : c'est la décision de quelqu'un qui étudie la situation exactement comme on l'étudie, et dont le choix dépend de ce qu'il anticipe de celui de l'entreprise. Une telle probabilité peut encore s'estimer, le chapitre suivant le fera, mais elle ne se mesure pas comme une fréquence de panne. La section suivante en donne le premier exemple.

Le mot « jeu » est trompeur : il n'y a rien de ludique. Une négociation commerciale, un appel d'offres, deux opérateurs qui fixent leurs tarifs, deux équipes qui se partagent une fenêtre de maintenance, tout cela est un jeu au sens technique.

Le critère. On est dans un problème de théorie des jeux dès que le gain d'un acteur dépend de la décision d'un autre acteur qui, lui aussi, choisit. Si l'autre « acteur » est le hasard, on est dans un problème de probabilités, pas de théorie des jeux.

Le jeu sous forme normale

Quand chaque joueur a peu de stratégies et qu'ils décident simultanément, le jeu s'écrit sous forme d'un tableau. Les lignes sont les stratégies du premier joueur, les colonnes celles du second. Chaque case contient le couple de gains : celui du joueur des lignes d'abord, celui du joueur des colonnes ensuite. On sépare les deux gains par un point-virgule, $(8 ; 3)$, et les deux noms de stratégies par une virgule, (Cassé, Moyen).

L'exemple canonique est le dilemme du prisonnier, sous la forme que les entreprises connaissent le mieux : la guerre des prix. Deux fournisseurs d'électricité répondent au même appel d'offres régional. Chacun fixe son prix de vente sans connaître celui de l'autre : élevé, moyen ou cassé. Les gains sont leurs marges mensuelles, en k€ :

Lire une case avant toute analyse. Premier nombre : le gain de A. Second : celui de B. La case qui croise la ligne Cassé et la colonne Moyen contient $(8 ; 3)$. Elle se lit en toutes lettres : A casse son prix, B reste au prix moyen, A dégage 8 k€ de marge mensuelle et B seulement 3. La case (Élevé, Cassé) contient $(1 ; 7)$ : A tient son prix élevé pendant que B casse le sien, A ne dégage plus que 1 k€ et B en dégage 7. Chaque case décrit ainsi un mois complet de marché, une fois les deux prix affichés.

Les nombres ne sont pas tirés au hasard : ils traduisent trois mécanismes du marché, qu'il faut savoir retrouver dans le tableau.

• casser son prix prend des clients à l'autre : face à un concurrent au prix moyen, passer du prix moyen au prix cassé fait monter la marge de 7 à 8 ;
• un prix élevé fait sortir des clients du marché : les gros clients qui le voient affiché vont s'approvisionner à l'étranger, et le marché régional rétrécit pour les deux. C'est pourquoi un fournisseur gagne moins face à un concurrent au prix élevé que face à un concurrent au prix moyen (6 au lieu de 7 s'il est lui-même au prix moyen, 7 au lieu de 8 s'il casse le sien), et pourquoi deux prix élevés ne donnent que $(5 ; 5)$, moins que deux prix moyens ;
• deux prix cassés partagent le marché à marge réduite : $(4 ; 4)$, moins bien que $(7 ; 7)$.

La case la plus confortable pour les deux à la fois est donc (Moyen, Moyen), à $(7 ; 7)$. Ce n'est pourtant pas elle que le marché atteint. La section sur les stratégies dominantes le montre, une fois posé le second exemple du chapitre, la rue à une seule voie.

Le fil rouge : la rue à une seule voie

Voici une situation que tout le monde a vécue. Une rue en travaux, une seule voie laissée libre entre les barrières, et pas de feu pour régler l'alternat. Deux voitures arrivent en même temps, chacune par un bout.

L'automobiliste A et l'automobiliste B décident au même instant, sans pouvoir se parler, sans savoir ce que fait l'autre : s'engager, ou attendre que l'autre passe.

Construire les gains

C'est l'étape qui décide de tout le reste, et c'est celle qu'on bâcle. Il faut d'abord choisir une référence, puis compter par rapport à elle.

La référence ici est « rester à l'entrée de la rue », comptée 0. Tout se mesure donc en minutes gagnées, ou perdues, par rapport à cette attente.

• S'engager seul : le passage se fait d'un trait, et il fait gagner $+3$ minutes sur l'attente.
• S'engager tous les deux : les deux voitures se retrouvent face à face au milieu, l'une doit reculer sur toute la longueur, l'autre attendre qu'elle ait fini, et celles qui se sont rangées derrière compliquent la manœuvre. Le face-à-face vaut $-2$ minutes pour chacun.
• Attendre vaut 0, la référence, que l'autre passe ou que personne n'avance. C'est une hypothèse du modèle, et il faut la dire : on suppose que deux automobilistes qui s'attendent se départagent d'un signe de la main, sans perdre de temps. Le chapitre suivant montre ce qui changerait si ce flottement coûtait une minute.

La matrice

Il reste à ranger ces résultats dans le tableau. A choisit la ligne, B la colonne. Chaque case dit d'abord ce qui se passe, puis donne le couple (gain de A ; gain de B), en minutes.

Trois remarques pour lire le tableau sans se tromper :

• La diagonale est la mauvaise. En haut à gauche les deux s'engagent et se bloquent, en bas à droite personne n'avance : ce sont les deux cases où la rue ne sert à personne.
• Les deux cases hors diagonale sont les mêmes, échangées. Le jeu est parfaitement symétrique : rien ne distingue A de B, et c'est précisément ce qui va rendre le choix difficile.
• Chacun préfère faire le contraire de l'autre. Face à un B qui s'engage, A a intérêt à attendre ($0$ plutôt que $-2$) ; face à un B qui attend, il a intérêt à s'engager ($3$ plutôt que $0$).

Le même jeu se rencontre ailleurs que dans la rue, avec des enjeux plus lourds que trois minutes.

Le tableau ne dit pas encore qui passera. Il faut d'abord les outils des sections suivantes, et la rue y reviendra avec les familles de jeux.

Stratégies dominantes

Avant de chercher un équilibre, on cherche toujours s'il y a plus simple.

Retour au tableau des deux fournisseurs, et cette fois du point de vue de A. Le prix de B n'est pas connu au moment de décider : il faut donc envisager les trois cas, colonne par colonne.

• Si B reste au prix élevé (colonne Élevé), A dégage 5 en restant élevé, 6 au prix moyen, 7 en cassant son prix.
• Si B passe au prix moyen (colonne Moyen), A dégage 2 en restant élevé, 7 au prix moyen, 8 en cassant son prix.
• Si B casse son prix (colonne Cassé), A dégage 1 en restant élevé, 3 au prix moyen, 4 en cassant son prix.

La même stratégie arrive en tête dans les trois cas : casser son prix rapporte le plus, quel que soit le prix de B. Cassé est la stratégie dominante de A. Le tableau étant symétrique, B tient exactement le même raisonnement ligne par ligne, et casse son prix lui aussi.

L'histoire qui a donné son nom au dilemme

La guerre des prix porte un nom qui vient d'ailleurs. Le jeu lui-même a été étudié au début de 1950 par Merrill Flood et Melvin Dresher, à la RAND Corporation ; la même année, le mathématicien Albert Tucker l'a habillé d'une histoire de commissariat pour le faire comprendre à des psychologues de Stanford. Le récit ci-dessous en est la version qu'on raconte aujourd'hui, et il se retient mieux que n'importe quelle matrice.

La figure met la scène sous les yeux. En haut, les deux pièces et le mur qui les sépare ; en bas, les quatre issues possibles, où chaque case colorée est une année de prison. Il n'y a rien à lire pour voir que 5 ans pèsent plus lourd que 1 an.

Le raisonnement de A tient en deux phrases, et il est impeccable. « Si B se tait, dénoncer me fait sortir libre au lieu de faire 1 an. Si B me dénonce, dénoncer me fait faire 3 ans au lieu de 5. » Dans les deux cas, dénoncer réduit la peine : c'est une stratégie dominante, et A n'a même pas besoin de deviner ce que fera B. B tient exactement le même raisonnement dans l'autre pièce.

Le résultat est absurde, et c'est tout le dilemme. Les deux dénoncent et prennent 3 ans chacun, 6 ans à eux deux, alors qu'en se taisant ils n'auraient fait qu'un an chacun, 2 ans à eux deux. Ils le savent parfaitement. Mais la case du silence mutuel est instable : chacun y serait tenté de dénoncer l'autre pour sortir libre, et chacun sait que l'autre le sait.

Les trois ingrédients d'un dilemme du prisonnier.

1. Une tentation : trahir quand l'autre coopère rapporte le plus (sortir libre).
2. Une crainte : coopérer quand l'autre trahit coûte le plus (5 ans).
3. Un gâchis collectif : la coopération mutuelle (1 an chacun) vaut mieux pour tous que la trahison mutuelle (3 ans chacun).

Dès que les trois sont réunis, et quel que soit le détail des nombres, chacun a intérêt à trahir et tous y perdent. Sans l'ordre libre < 1 an < 3 ans < 5 ans, il n'y a plus de dilemme : si se taire seul coûtait moins que la dénonciation mutuelle, par exemple, se taire ne serait plus dominé.

La guerre des prix est la même histoire, traduite mot à mot.

Le mur n'est pas un détail du récit : c'est la condition du piège. Si les deux complices pouvaient se parler et se faire confiance, ils se tairaient. Or même une promesse ne suffit pas : une fois dans sa pièce, chacun garde intérêt à la rompre. Il faut changer le jeu lui-même. Un code d'honneur du milieu, qui punit les dénonciateurs, alourdit la peine de la trahison, comme l'engagement de qualité de service alourdit celle du prix cassé. Et quand le même jeu se rejoue à chaque appel d'offres, la trahison d'aujourd'hui peut se payer demain.

Éliminer, puis recommencer

Supprimer une stratégie dominée change le tableau, et une stratégie qui ne l'était pas peut le devenir. On recommence donc jusqu'à ce que plus rien ne tombe. C'est l'élimination itérée, et elle se fait à la main, sans outil.

Deux enseignes de recharge rapide, A et B, choisissent chacune où installer leur station sur un axe autoroutier : zone Nord, Centre ou Sud. Les gains, en k€ par mois, tiennent compte du trafic de chaque zone et de la clientèle que chaque enseigne capte quand l'autre est proche. A étant la plus connue des deux, le tableau n'est pas symétrique.

Ici, ce ne sont pas les cases qu'il faut regarder une à une, mais les lignes et les colonnes entières. Pour A, une ligne qui lui rapporte strictement moins qu'une autre ligne dans chaque colonne, case par case, est une zone où il ne s'installera jamais, quoi que fasse B : elle sort du tableau. Pour B, même règle en tournant le tableau : une colonne dont les seconds nombres sont strictement plus petits que ceux d'une autre colonne, sur chaque ligne, sort du tableau. Le déroulé alterne les deux joueurs, un tour chacun, et commence par B.

Premier tour, B. Pour B, comparer « s'installer au Sud » à « s'installer au Centre », quel que soit le choix de A : ses gains valent $(0, 2, 1)$ au Sud et $(2, 3, 2)$ au Centre, selon que A est au Nord, au Centre ou au Sud, soit $2 > 0$, $3 > 2$, $2 > 1$. Le Sud est strictement dominé pour B, il tombe. Autrement dit, la zone Sud ne rapporte jamais à B ce que lui rapporterait le Centre : son trafic est trop faible pour compenser, même quand A s'en éloigne. Côté A, rien ne tombe encore : le Sud lui rapporte 4 quand B s'y trouve aussi, plus que le Nord ou le Centre.

Deuxième tour, A. B n'ira plus au Sud. Pour A, le Sud ne vaut alors plus que $(1, 0)$, contre $(3, 1)$ pour le Nord. Le Sud tombe pour A. C'est exactement l'effet annoncé : le Sud n'était pas dominé au départ, il l'est devenu parce que la seule situation qui le sauvait, B au Sud, a disparu. Le Sud n'intéressait A que pour capter la clientèle d'un concurrent installé là ; sans ce concurrent, la zone ne vaut plus rien.

Troisième tour, B. A n'est plus qu'au Nord ou au Centre. Pour B, le Nord rapporte $(1, 1)$ et le Centre $(2, 3)$. Le Nord tombe pour B, alors qu'il lui rapportait 4 face à A au Sud, écarté juste avant.

Quatrième tour, A. B sera au Centre. Pour A, le Nord y rapporte 1 et le Centre 3. Le Nord tombe pour A.

Il reste une seule case, (Centre, Centre), qui rapporte $(3 ; 3)$. Le jeu est dit résoluble par dominance, et la section suivante montre que cette case est alors son unique équilibre : les deux enseignes s'installent au centre de l'axe, à quelques sorties l'une de l'autre. Le tableau a été construit pour l'exemple, mais sa conclusion rejoint une observation classique : deux concurrents qui se disputent une même clientèle finissent souvent côte à côte, au milieu de la zone, parce que chacun y capte des clients des deux côtés. On le voit pour des stations-service comme pour des commerces dans une rue.

Le tableau ne se laisse pas toujours faire. Souvent, l'élimination s'arrête avant d'avoir isolé une case : la seconde matrice des fournisseurs, plus bas, en est un exemple. Il faut alors une méthode qui conclut dans tous les cas, celle des meilleures réponses.

L'équilibre de Nash

Quand il n'y a pas de stratégie dominante, chaque joueur doit deviner ce que fera l'autre, et l'autre en fait autant. Le raisonnement tourne en rond : « s'il fait ceci, je fais cela ; mais s'il sait que je ferai cela, il fera autre chose… ». L'équilibre de Nash coupe ce cercle en posant une question plus simple : quelles situations résistent à ce raisonnement ?

L'idée : une situation sans regret

Imaginer que les deux fournisseurs ont affiché leur prix et découvrent, le lendemain, celui de l'autre. Chacun se demande : « sachant maintenant ce qu'a fait le concurrent, aurais-je dû faire autrement ? » Si la réponse est non pour les deux, la situation est un équilibre de Nash. Si l'un des deux répond oui, elle ne l'est pas : il avait mieux à faire, l'autre restant à sa place, et il le sait.

Deux autres lectures disent la même chose, et chacune éclaire un aspect différent.

• Un accord qui tient tout seul. Si les deux joueurs s'étaient promis de jouer une case, ils ne tiendraient leur promesse, sans contrat ni sanction, que dans une case d'équilibre. Partout ailleurs, l'un au moins aurait intérêt à la rompre.
• Une prophétie qui se réalise. Si chacun s'attend à ce que le jeu aboutisse à une case d'équilibre, chacun a intérêt à jouer sa part de cette case, et l'attente se vérifie. Une prévision qui désigne une case hors équilibre se dément elle-même : quelqu'un a intérêt à la faire mentir.

En clair : la première inégalité fixe la stratégie de B et fait varier celle de A seulement ; aucune ne rapporte plus à A que $s_A^*$. La seconde fait la même vérification pour B. Deux points méritent d'être soulignés dans cette écriture.

• « Seul » est essentiel. On ne compare jamais deux cases où les deux joueurs auraient changé ensemble. Un équilibre peut donc être battu par une autre case, meilleure pour tous les deux : c'est le dilemme du prisonnier.
• Les inégalités sont larges. Un joueur peut être indifférent entre sa stratégie d'équilibre et une autre ; il suffit qu'il ne gagne rien à changer.

Dans ce chapitre, chaque joueur choisit une ligne ou une colonne, et l'on parle d'équilibre en stratégies pures. Le chapitre suivant permet aux joueurs de tirer leur choix au sort, et d'autres équilibres apparaissent.

Le test de la déviation, case par case

La définition se vérifie mécaniquement : pour une case donnée, on regarde ce que chaque joueur gagnerait en changeant seul de stratégie. S'il existe une déviation qui rapporte strictement plus, la case n'est pas un équilibre.

On l'applique à une seconde version de l'appel d'offres. Le client principal exige désormais un engagement de qualité de service qu'un prix cassé tient mal : casser son prix face à un concurrent au prix moyen ne rapporte plus que 6 au lieu de 8. Deux cases changent, (Moyen, Cassé) et (Cassé, Moyen), et plus aucune stratégie n'est dominante :

Dans la colonne Moyen, A préférait casser son prix (8 contre 7) ; il préfère désormais le prix moyen (7 contre 6). Dans la colonne Cassé, il préfère toujours casser (4 contre 3). Sa meilleure ligne dépend donc de la colonne : Cassé n'est plus dominante, il en va de même pour B par symétrie, et le tableau ne se résout plus à vue.

Les neuf cases, testées une à une. Pour chaque case, « Déviation de A » donne la ligne la plus rentable vers laquelle A pourrait passer seul, B gardant son prix ; « Déviation de B » donne la colonne la plus rentable pour B, A gardant le sien. « aucune » signifie que rien ne rapporte plus que la case elle-même.

Deux équilibres de Nash en stratégies pures : (Moyen, Moyen) qui rapporte $(7 ; 7)$ et (Cassé, Cassé) qui rapporte $(4 ; 4)$. Le marché peut donc se stabiliser sur deux régimes : des prix tenus, ou une guerre des prix installée. Les deux sont stables, et la matrice ne dit pas lequel s'installera.

Deux cases méritent qu'on s'y arrête. En (Élevé, Cassé), B est parfaitement satisfait, avec 7 ; il suffit que A ne le soit pas pour que la case tombe. Et en (Cassé, Élevé), c'est l'inverse. Un équilibre exige la satisfaction des deux, pas d'un seul.

Au passage, la stratégie Élevé est strictement dominée par Moyen pour chacun des deux joueurs ($6 > 5$, $7 > 2$, $3 > 1$) et peut être barrée. Mais une fois la stratégie Élevé retirée, plus rien ne tombe : ni Moyen ni Cassé ne domine l'autre, et l'élimination laisse quatre cases. C'est précisément pourquoi il fallait passer par les déviations.

La méthode des soulignements

Le tableau des neuf cases est sûr, mais long : il refait le même travail plusieurs fois. Dans une même colonne, la meilleure ligne de A est toujours la même ; il suffit donc de la chercher une fois par colonne. D'où la méthode, qui tient en trois gestes.

1. Colonne par colonne, souligner le meilleur gain du joueur des lignes.
2. Ligne par ligne, souligner le meilleur gain du joueur des colonnes.
3. Les cases où les deux gains sont soulignés sont les équilibres de Nash.

Sur la matrice ci-dessus : colonne Élevé, le meilleur gain de A est 7, sur la ligne Cassé ; colonne Moyen, c'est 7, sur la ligne Moyen ; colonne Cassé, c'est 4, sur la ligne Cassé. Pour B, ligne par ligne : ligne Élevé, son meilleur gain est 7, dans la colonne Cassé ; ligne Moyen, 7, dans la colonne Moyen ; ligne Cassé, 4, dans la colonne Cassé. Seules (Moyen, Moyen) et (Cassé, Cassé) sont soulignées deux fois : ce sont les deux équilibres du tableau.

Deux propriétés relient dominance et équilibre, et se démontrent de la même façon, en une ligne chacune.

• Si les deux joueurs ont une stratégie dominante, leur croisement est un équilibre. La stratégie dominante de A est sa meilleure réponse à toute stratégie de B, donc en particulier à la stratégie dominante de B ; et réciproquement. Aucun des deux n'a de déviation rentable.
• Une stratégie strictement dominée n'apparaît dans aucun équilibre. Si $T$ est strictement dominée par $S$, alors dans toute case où A joue $T$, passer à $S$ lui rapporte strictement plus : c'est une déviation rentable, et la case n'est pas un équilibre. C'est ce qui autorise l'élimination itérée : barrer une stratégie strictement dominée ne fait perdre aucun équilibre.

Seule la dominance stricte autorise à barrer sans risque. Une stratégie est faiblement dominée quand une autre lui rapporte au moins autant dans chaque colonne, et strictement plus dans l'une au moins. S'il existe une colonne où les deux font jeu égal, elle n'est pas strictement dominée : elle peut alors appartenir à un équilibre, et la barrer peut le faire perdre. Le chapitre suivant en donne un exemple sur la rue à une seule voie.

Voir les équilibres : les flèches de déviation

Le tableau des déviations se dessine. De chaque case, on trace une flèche vers la case voisine chaque fois qu'un joueur gagne à y aller seul : verticale pour le joueur des lignes, qui change de ligne, horizontale pour le joueur des colonnes. Un équilibre de Nash est alors une case d'où ne part aucune flèche.

La figure le fait sur le cœur de la première guerre des prix, réduite aux stratégies Moyen et Cassé.

Le dessin rend visible ce que le tableau disait en chiffres : depuis (Moyen, Moyen), une flèche part vers la droite (B gagne 1 en cassant son prix) et une autre vers le bas (A aussi). La case confortable est quittée ; la case médiocre est atteinte et n'est plus quittée. C'est le dilemme du prisonnier en une image.

Ce procédé, où chacun corrige tour à tour son choix face à celui de l'autre, s'appelle la dynamique des meilleures réponses. Elle ne décrit pas toujours ce que font de vrais concurrents, mais elle fournit une intuition solide : quand elle converge, elle converge vers un équilibre, puisqu'elle ne s'arrête que là où plus personne ne gagne à bouger.

Confier le calcul à la machine

La méthode des soulignements est mécanique, donc programmable, et c'est un bon exercice pour qui a suivi le parcours Python. Le code ci-dessous prend n'importe quelle matrice et en sort les stratégies strictement dominées, les meilleures réponses et les équilibres. Pour un autre jeu, de n'importe quelle taille, remplacer ensemble les trois définitions du haut, LIGNES, COLONNES et MATRICE, puis relancer : on obtient de quoi vérifier ses propres soulignements. Les noms doivent être aussi nombreux que les lignes et les colonnes de la matrice, sinon le programme s'arrête sur une erreur.

Un équilibre n'est ni forcément unique, ni optimal, ni juste. Un jeu peut avoir zéro, un ou plusieurs équilibres de Nash en stratégies pures. Un équilibre peut être mauvais pour les deux joueurs (le dilemme du prisonnier, la concurrence entre hébergeurs plus bas). Et quand il y en a plusieurs, la théorie ne dit pas lequel sera joué : elle dit seulement lesquels sont stables. C'est une réponse plus modeste qu'on ne l'attend, et c'est exactement ce qu'il faut retenir.

Les familles de jeux 2 × 2

Il existe une infinité de jeux à deux joueurs et deux stratégies, mais leurs dessins de déviations n'ont que trois allures, du moment qu'aucune comparaison ne tombe sur une égalité. On appelle puits une case où des flèches arrivent et d'où aucune ne part : c'est un équilibre. Le dessin a soit un seul puits, soit deux, soit aucun, et alors les flèches tournent en cycle. Avec deux puits, on distingue la coordination (les équilibres sont les cases où les deux joueurs font le même choix) de l'anti-coordination (ils font des choix différents). Le dessin donne donc le nombre et la place des équilibres ; il ne dit pas si un équilibre est bon ou mauvais pour les joueurs, et pour cela il faut relire les nombres.

Dans les figures de cette section, les flèches sont cachées. Les tracer d'abord au brouillon, case par case, en se demandant chaque fois qui gagne à bouger seul, puis cliquer « Montrer les déviations » et comparer.

1. Un seul équilibre. Toutes les flèches convergent vers un coin : au moins un des deux joueurs a une stratégie dominante, et le jeu se résout par dominance. Les flèches ne disent pas si ce coin est bon pour les joueurs : il faut relire les nombres.

Quand les deux joueurs ont une stratégie dominante et que le coin opposé est meilleur pour tous les deux, c'est le dilemme du prisonnier, celui de la guerre des prix réduite à Moyen et Cassé : course aux armements, surenchère sur une ressource partagée. Mais le même dessin peut ne cacher aucun dilemme. Deux équipes qui partagent un même code gagnent toutes deux à le tester : $(4 ; 4)$ si les deux testent, $(1 ; 1)$ si aucune, et si une seule le fait, 3 pour elle et 2 pour l'autre.

Tester est dominant pour chacune, les flèches convergent vers (Tester, Tester), et cet équilibre n'est battu par aucune autre case : ce n'est pas un dilemme, il n'y a rien à corriger.

2. La coordination avec un risque : la migration commune. Deux équipes partagent une plateforme. Migrer ensemble vers la nouvelle version rapporte 4 à chacune. Rester ensemble sur l'ancienne rapporte 3 : elle fonctionne, sans plus. Mais une équipe qui migre seule doit maintenir des passerelles vers l'autre et n'y gagne rien (0), tandis que celle qui est restée n'est pas affectée (3).

Deux cases sans flèche sortante, donc deux équilibres : (Migrer, Migrer) et (Rester, Rester). Le premier est meilleur pour les deux, et pourtant le second est tout aussi stable. Ce que l'équipe A pense de l'autre explique pourquoi les équipes restent si souvent sur l'ancienne version. On note $c$ la probabilité que l'équipe A attribue à la migration de l'équipe B : ce n'est pas un hasard de la situation, c'est une croyance sur ce que fera l'autre. En migrant, A gagne 4 si B migre aussi, avec la probabilité $c$, et 0 sinon : en moyenne $4c + 0 \times (1 - c) = 4c$. En restant, elle gagne 3 dans les deux cas. Migrer n'est donc intéressant que si

Il faut être sûr à 75 % que l'autre équipe suivra. Dès que le doute dépasse une chance sur quatre, rester est la meilleure réponse, et chacun reste parce qu'il doute de l'autre. Le chapitre suivant fait de la croyance un outil à part entière.

3. L'anti-coordination : la rue, et les canaux Wi-Fi. C'est la famille du fil rouge, dont la matrice est reprise ci-dessous.

Les flèches fuient la diagonale : depuis (s'engager, s'engager), chacun gagne à attendre ; depuis (attendre, attendre), chacun gagne à s'engager. Il reste deux équilibres, (A s'engage, B attend) et (A attend, B s'engage). Chacun veut faire le contraire de l'autre, l'un des deux gagne 3 minutes pendant que l'autre gagne 0, et rien dans le tableau ne dit lequel des deux passera.

La famille ne se limite pas aux voitures. Deux bornes voisines choisissent chacune un canal, 1 ou 6. Sur le même canal elles se brouillent (1 chacune) ; sur deux canaux différents, chacune a un débit correct (4).

Les équilibres sont sur l'autre diagonale : chacun veut faire le contraire de l'autre. C'est le principe des algorithmes de sélection automatique de canal les plus simples : une borne mesure le brouillage et change de canal si elle y gagne. Quand les bornes corrigent l'une après l'autre, le réseau se stabilise sur un équilibre de Nash sans coordination centrale, et la dynamique des meilleures réponses est alors l'algorithme lui-même. Si elles corrigent toutes au même instant, elles changent de canal ensemble et le brouillage recommence : c'est pourquoi les bornes ne doivent pas corriger en même temps, et pourquoi les réseaux d'entreprise confient souvent le choix des canaux à un contrôleur central. Le chapitre sur le Wi-Fi explique pourquoi on se limite aux canaux 1, 6 et 11.

4. Pile ou face : l'audit inopiné. Un contrôleur passe le matin ou le soir ; une équipe peu scrupuleuse saute une étape de procédure le matin ou le soir. Le contrôleur gagne 1 s'il tombe sur l'écart et perd 1 sinon ; l'équipe, l'inverse.

Les mots « diagonale » et « hors diagonale » supposent que les deux joueurs ont les mêmes stratégies, rangées dans le même ordre : mêmes canaux, mêmes protocoles. Sinon, seule compte la question de savoir si les deux équilibres demandent des choix identiques ou différents.

Choisir entre plusieurs équilibres

Quand un jeu a plusieurs équilibres, la définition de Nash ne dit pas lequel sera joué. Quatre critères aident à trancher, et ils ne désignent pas toujours le même.

• L'efficacité. Un équilibre en domine un autre au sens de Pareto s'il est au moins aussi bon pour chacun et strictement meilleur pour l'un. Ce mot compare ici deux cases, et non deux stratégies d'un même joueur : rien à voir avec la dominance des sections précédentes. (Migrer, Migrer) domine ainsi (Rester, Rester), et (Moyen, Moyen) domine (Cassé, Cassé). C'est l'équilibre que des joueurs qui peuvent se parler visent le plus souvent. L'accord n'est pourtant pas garanti. Quelle que soit son intention, l'équipe A a intérêt à ce que B migre : si A migre, elle y gagne 4 au lieu de 0 ; si A reste, elle touche 3 de toute façon. A annoncerait donc « je migre » même en comptant rester, B le sait, et l'annonce ne prouve rien.
• La prudence. Un équilibre est plus sûr si l'on y risque moins quand l'autre se trompe. Rester garantit 3 quoi que fasse l'autre équipe ; migrer peut rapporter 0. Sans communication, c'est souvent l'équilibre prudent qui l'emporte, et la migration peut ne jamais avoir lieu.
• Le point focal. Faute de mieux, les joueurs se retrouvent sur l'équilibre qui saute aux yeux : une convention, une habitude, un standard d'entreprise, une case que l'énoncé met en évidence. Deux collègues qui doivent se retrouver dans une gare sans pouvoir se joindre vont à l'accueil, à midi. Thomas Schelling a montré que ce critère, qui n'a rien de mathématique, permet très souvent de se coordonner sans se parler. C'est exactement ce que fait un code de la route. La rue à une seule voie a deux équilibres et rien pour désigner celui qui sera joué ; une règle aussi mince que « celui qui a le panneau de priorité passe » en désigne un, et le face-à-face disparaît. La règle ne rend personne plus intelligent : elle rend un des deux équilibres évident pour les deux à la fois. Un feu tricolore va un cran plus loin : au lieu de désigner une fois pour toutes celui qui passe, il alterne, et chacun passe à son tour. Le feu ne contraint personne physiquement. Celui qui a le vert sait que l'autre a le rouge et l'attendra, donc s'engager est sa meilleure réponse ; celui qui a le rouge sait que l'autre s'engage, donc attendre est la sienne. Obéir au signal est un équilibre.
• L'ordre de jeu. Si l'un des joueurs peut s'engager en premier, il choisit l'équilibre qui l'avantage et l'autre suit. C'est l'objet du chapitre sur les jeux séquentiels.

Ce que cela change en pratique. Dans un jeu de coordination, le problème n'est pas de calculer, c'est de se mettre d'accord. Quand aucune option n'est plus sûre que l'autre, comme pour deux collègues qui fixent un lieu de rendez-vous, une réunion de dix minutes suffit : chacun a intérêt à faire ce qu'il a annoncé. Quand l'une est plus sûre, comme rester sur l'ancienne plateforme, une parole ne suffit plus, on l'a vu avec la migration : il faut un geste qui engage, une règle écrite (« par défaut, on fait comme ceci »), une date de bascule commune annoncée publiquement. L'équilibre efficace devient alors le point focal. Dans un dilemme du prisonnier, au contraire, se parler ne suffit jamais : l'accord n'est pas un équilibre, et il faut changer les gains (contrat, pénalité, répétition du jeu) pour qu'il le devienne.

Quand les stratégies sont des nombres

Jusqu'ici, chaque joueur choisissait dans une courte liste. Souvent, la décision est une quantité : un volume de production, une capacité, un budget. L'équilibre se définit de la même façon, et la méthode devient celle des fonctions : chaque joueur a une fonction de meilleure réponse, et l'équilibre est le point où les deux se croisent. Ce modèle porte le nom d'Antoine Augustin Cournot, qui l'a publié en 1838.

La figure montre aussi comment on y arrive. Si B commence à 0, A répond 45 ; B répond alors $(90 - 45)/2 = 22{,}5$ ; A répond $33{,}75$ ; B répond $28{,}1$… Chaque réponse fait un pas en escalier entre les deux droites, et les pas rétrécissent vers le croisement. C'est la dynamique des meilleures réponses, et ici elle converge.

Le point d'entente raconte la même histoire que la guerre des prix. Si les deux hébergeurs s'entendaient sur l'offre totale $Q = x + y$, leur gain total vaudrait $Q\,(90 - Q)$ : ils mettraient $Q = 45$ sur le marché, soit 22,5 chacun, au prix de 55 €, et chacun gagnerait $22{,}5 \times 45 = 1\,012{,}5$ k€, plus que les 900 k€ de l'équilibre. Mais face à un B qui respecte l'entente, la meilleure réponse de A est $x = (90 - 22{,}5)/2 = 33{,}75$. Le prix tombe alors à $100 - 33{,}75 - 22{,}5 = 43{,}75$ €, soit une marge de $33{,}75$ € par machine, et A gagne $33{,}75 \times 33{,}75 \approx 1\,139$ k€ : trahir paie. C'est la mécanique du dilemme du prisonnier, sans stratégie dominante cette fois : l'entente vaut mieux pour les deux, mais chacun gagne à la trahir seul, et c'est pourquoi une entente sur les capacités est instable. Qu'elle soit en plus interdite tient à une autre raison : elle fait payer aux clients 55 € au lieu de 40 €, et le droit de la concurrence prohibe les accords qui limitent ou contrôlent la production.

La méthode

1. Modéliser : nommer les joueurs, leurs stratégies, l'unité des gains et la référence, écrite une fois pour toutes. Dire si les décisions sont simultanées.
2. Construire la matrice, le gain du joueur des lignes d'abord, et relire en français une case où les deux gains diffèrent.
3. Éliminer les stratégies strictement dominées, tour à tour pour chaque joueur, et seulement les strictement dominées : barrer une stratégie seulement faiblement dominée peut faire perdre des équilibres.
4. Chercher les équilibres purs par les soulignements : colonne par colonne pour le joueur des lignes, ligne par ligne pour celui des colonnes.
5. Comparer les issues : laquelle est meilleure pour tous, laquelle est prudente, laquelle saute aux yeux. S'il n'y a qu'un équilibre, regarder si une autre case vaut mieux pour les deux.
6. Conclure en français. « Les équilibres purs sont les deux cases hors diagonale » ne vaut rien sans « c'est-à-dire que l'un passe et que l'autre attend, que les deux solutions sont également stables, et que rien dans le jeu ne désigne laquelle des deux voitures passera ».

Mettre en pratique