Théorie des jeux et décision stratégique

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 (l'espérance, vue dans le chapitre sur les probabilités) à 4 000 € de dépense certaine, on double la machine, et c'est réglé. La météo, la panne, le hasard : ils ne réagissent pas à la décision.

Il suffit de changer une seule chose. Le prix du serveur de secours n'est plus affiché : il est négocié avec un fournisseur qui sait qu'on a besoin de lui, et qui sait qu'on sait qu'il le sait. Le calcul d'espérance ne tient plus, parce que le prix qui y figure est lui-même le résultat d'une décision prise par quelqu'un qui observe celle de l'acheteur.

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 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.

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€ :

A \ B	Élevé	Moyen	Cassé
Élevé	2,2	1,3	0,4
Moyen	3,1	4,4	2,5
Cassé	4,0	5,2	3,3

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

Ce qu'il faut regarder ensuite n'est pas la case la plus confortable, mais la façon dont une marge bouge quand un seul des deux fournisseurs change d'avis. Le tableau se lit alors comme le marché fonctionne :

• 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 4 à 5 ;
• deux prix élevés font fuir les gros clients vers les importations : (2, 2), moins que les (4, 4) du prix moyen ;
• deux prix cassés partagent le marché à marge réduite : (3, 3), moins bien que (4, 4) également.

La case la plus confortable pour les deux à la fois est donc (Moyen, Moyen), à $(4, 4)$. La section suivante montre que ce n'est pas elle que le marché atteint.

Le fil rouge : le groupe électrogène

Voici une situation type. À une semaine de la cérémonie d'ouverture des Jeux olympiques, une couverture nuageuse dense menace de réduire de moitié la production solaire. Marc, responsable du réseau, veut sécuriser l'alimentation. Une panne coûterait 150 k€.

Marc propose de louer un groupe électrogène à 50 k€ au lieu des 70 k€ habituels, avec une clause : le groupe ne sera mis en marche que si la production solaire est insuffisante. Nicole, responsable commerciale de Diesel Pro, peut accepter ces 50 k€ ou insister sur 70 k€, mais dans ce cas Marc annonce qu'il fera tourner le groupe de toute façon, nuages ou pas.

Faire tourner le groupe coûte 55 k€ à Diesel Pro. Les deux écrivent leur prix simultanément : Marc écrit $x$, Nicole écrit $y$. Si $x \geq y$, la location se fait au prix $\min(x, y)$ ; si $x < y$, il n'y a pas de location.

On note $p$ la probabilité que le ciel soit couvert, donc que la production solaire soit insuffisante.

Construire les gains

C'est l'étape qui décide de tout le reste, et c'est celle qu'on bâcle. Côté Marc d'abord, quand la location se fait au prix $c$ :

• avec la probabilité $p$, le ciel est couvert : le groupe évite une panne à 150 k€, mais Marc paie $c$. Son gain vaut $150 - c$ ;
• avec la probabilité $1 - p$, le ciel est dégagé : le groupe ne servait à rien, Marc a payé $c$ pour rien. Son gain vaut $-c$.

Son espérance de gain est donc :

$E = p(150 - c) + (1 - p)(-c) = 150p - c$

Et s'il n'y a pas de location, Marc subit la panne avec la probabilité $p$ : son espérance vaut $-150p$.

Pour Nicole, il faut lire la clause avec attention :

• location à 50 k€ : le groupe ne tourne que si le ciel est couvert. Avec la probabilité $p$, elle encaisse 50 et dépense 55, soit $-5$ ; avec la probabilité $1 - p$, elle encaisse 50 sans rien dépenser. Espérance : $p(-5) + (1 - p)(50) = 50 - 55p$ ;
• location à 70 k€ : plus de clause, le groupe tourne dans tous les cas. Elle encaisse 70 et dépense 55, soit $15$ de façon certaine ;
• pas de location : $0$.

La matrice

Il reste à ranger ces trois résultats dans le tableau. Marc choisit la ligne (le prix $x$ qu'il écrit), Nicole la colonne (le prix $y$). Chaque case dit d'abord ce qui se passe, puis donne le couple (gain espéré de Marc ; gain espéré de Nicole), en k€.

Chaque case se lit (gain de Marc ; gain de Nicole), la formule en haut, sa valeur pour p = 0,5 en dessous.

Marc \ Nicole	y = 50	y = 70
x = 50	location à 50 k€ $150p - 50$;$50 - 55p$ 25;22,5	pas de location $-150p$;$0$ −75;0
x = 70	location à 50 k€ $150p - 50$;$50 - 55p$ 25;22,5	location à 70 k€ $150p - 70$;$15$ 5;15

p0,5

Trois remarques pour lire le tableau sans se tromper :

• Une seule case sans location, en haut à droite : c'est la seule où $x < y$. Marc y garde le risque de panne, d'où $-150p$, et Nicole ne gagne rien.
• Les deux cases de la colonne de gauche sont identiques. Dès que Nicole écrit 50, le prix retenu est $\min(x, y) = 50$, que Marc ait écrit 50 ou 70. Ce que Marc écrit ne change alors plus rien.
• Seule la case en bas à droite ne dépend pas de $p$ pour Nicole. À 70 k€, le groupe tourne dans tous les cas : ses $15$ sont certains, alors qu'à 50 k€ elle parie sur le ciel.

Le curseur fixe $p$ et recalcule la valeur de chaque gain. On s'en servira plus bas pour la discussion.

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 2 en restant élevé, 3 au prix moyen, 4 en cassant son prix.
• Si B passe au prix moyen (colonne Moyen), A dégage 1 en restant élevé, 4 au prix moyen, 5 en cassant son prix.
• Si B casse son prix (colonne Cassé), A dégage 0 en restant élevé, 2 au prix moyen, 3 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.

É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.

A \ B	Nord	Centre	Sud
Nord	3,1	1,2	2,0
Centre	2,1	3,3	0,2
Sud	1,4	0,2	4,1

Ici, ce ne sont pas les cases qu'il faut regarder une à une, mais les lignes et les colonnes entières. Une ligne dont tous les gains sont inférieurs à ceux d'une autre ligne est une zone où A ne s'installera jamais, quoi que fasse B, et elle sort du tableau. Le déroulé alterne les deux joueurs, un tour chacun.

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, 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 cette case est son unique équilibre : les deux enseignes s'installent au centre de l'axe, à quelques sorties l'une de l'autre. C'est un résultat classique, qu'on observe aussi bien pour des stations-service que pour des commerces dans une rue. Deux concurrents qui se disputent une même clientèle finissent souvent côte à côte, au milieu de la zone la plus fréquentée, plutôt que de se partager l'axe.

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, on cherche les situations stables.

La méthode tient en trois gestes, et elle est mécanique.

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.

Elle s'applique ici à 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 3 au lieu de 5. Deux cases changent, (Moyen, Cassé) et (Cassé, Moyen), et plus aucune stratégie n'est dominante :

A \ B	Élevé	Moyen	Cassé
Élevé	2,2	1,3	0,4
Moyen	3,1	4,4	2,3
Cassé	4,0	3,2	3,3

Comparer ce tableau au précédent case par case : seules les deux cases où l'un casse son prix face à un concurrent au prix moyen ont changé. Cette seule inversion suffit à faire disparaître la stratégie dominante, et c'est pour cela que le tableau ne se résout plus à vue.

Souligner d'abord au brouillon, puis demander la correction à la figure : c'est ce geste-là qu'il faut savoir refaire, pas la lecture du résultat. Colonne Élevé, le meilleur gain de A est 4, sur la ligne Cassé. Colonne Moyen, c'est 4, sur la ligne Moyen. Colonne Cassé, c'est 3, sur la ligne Cassé. Puis on recommence ligne par ligne pour B, et l'on ne garde que les cases doublement soulignées.

Deux équilibres de Nash en stratégies pures, donc : (Moyen, Moyen) qui rapporte $(4, 4)$ et (Cassé, Cassé) qui rapporte $(3, 3)$. 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. Au passage, la stratégie Élevé est strictement dominée par Moyen pour chacun des deux joueurs ($3 > 2$, $4 > 1$, $2 > 0$) 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 meilleures réponses.

Le faire faire par la machine

La méthode 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 dominées, les meilleures réponses et les équilibres. Remplacer MATRICE par une autre matrice et relancer : on obtient de quoi vérifier son propre soulignage.

1.Dans une case notée (3, 1), le 3 est le gain…

du joueur des lignesdu joueur qui commencedu joueur des colonnes

2.Un équilibre de Nash garantit…

l'unicité de la solutionqu'aucun joueur ne gagne à changer seul de stratégiele meilleur résultat pour les deux joueurs

3.Une stratégie strictement dominée…

est toujours l'équilibre du jeurapporte plus dans la moitié des casne sera jamais jouée par un joueur rationnel

4.Le dilemme du prisonnier a un équilibre de Nash qui n'est pas le meilleur résultat collectif. Que montre-t-il ?

Que la rationalité individuelle et l'optimum collectif peuvent divergerQue les joueurs se sont trompés de calculQue l'équilibre de Nash est mal défini

5.Dans un jeu séquentiel, l'induction à rebours consiste à…

comparer tous les chemins possiblessuivre l'arbre de la racine vers les feuillesrésoudre les décisions finales d'abord, puis remonter vers la racine

Jeux à somme nulle

Un jeu est à somme nulle quand ce que l'un gagne, l'autre le perd : $g_A + g_B = 0$ dans chaque case, où $g_A$ et $g_B$ sont les gains des deux joueurs. On n'écrit alors qu'un seul nombre par case, celui du joueur des lignes.

Jusqu'ici, chaque joueur cherchait sa meilleure réponse à ce que fait l'autre. Ici, une autre méthode apparaît, et il faut dire pourquoi on en change.

Dans un jeu à somme nulle, tout gain de l'un est exactement la perte de l'autre. Aucune case ne peut donc convenir aux deux, et il n'existe aucune entente possible : l'adversaire n'a pas seulement des intérêts différents, il a l'intérêt opposé. Supposer qu'il choisira toujours le coup le plus défavorable à l'autre joueur n'est plus une hypothèse pessimiste, c'est la seule hypothèse cohérente.

De là vient le changement de méthode. Plutôt que de répondre à un coup supposé, chaque joueur se demande ce qu'il peut se garantir quoi qu'il arrive.

Le joueur des lignes raisonne en maximin : pour chaque ligne il regarde son pire cas, puis choisit la ligne dont le pire cas est le meilleur. Il s'assure ainsi un gain plancher, que l'adversaire ne peut pas lui retirer. Le joueur des colonnes raisonne symétriquement en minimax : il choisit la colonne qui limite le mieux le gain maximal de l'autre.

Quand les deux valeurs coïncident, la case correspondante est un point selle : c'est l'équilibre de Nash du jeu, et la valeur commune est la valeur du jeu.

Un jeu à somme nulle typique est celui de la sécurité informatique. Cette nuit, l'équipe de défense (A) ne peut renforcer la surveillance que d'une zone : le réseau, la messagerie ou les postes de travail. Un attaquant (B) choisit son mode d'attaque : intrusion, hameçonnage ou rançongiciel. Chaque case donne le bilan de la nuit pour la défense, en k€ : ce que la défense gagne, l'attaquant le perd.

A \ B	Intrusion	Hameçonnage	Rançongiciel
Réseau	3	−1	2
Messagerie	2	1	4
Postes	5	0	−2

Deux balayages suffisent à lire ce tableau : relever le plus petit nombre de chaque ligne, puis le plus grand de chaque colonne. Les pires cas des lignes valent $-1$, $1$ et $-2$ : le maximin vaut 1, sur la ligne Messagerie. Les pires cas des colonnes, vus par l'attaquant, sont les maximums de chaque colonne, $5$, $1$ et $4$ : le minimax vaut 1, sur la colonne Hameçonnage. Maximin $=$ minimax $= 1$ : la case (Messagerie, Hameçonnage) est un point selle, et la valeur du jeu vaut 1.

La lecture métier est immédiate. Surveiller la messagerie garantit à la défense le meilleur plancher, quelle que soit l'attaque ; face à cette défense, l'hameçonnage est l'attaque qui limite le mieux les pertes de l'attaquant. Aucun des deux n'a intérêt à changer seul : c'est pour cela que le point selle est un équilibre.

Retour au fil rouge : décider sous incertitude

Retour à la matrice de Marc et Nicole. Les gains dépendent de $p$, donc l'équilibre aussi. Il faut discuter.

Les meilleures réponses de Marc. Si Nicole joue $y = 50$, les deux lignes lui donnent $150p - 50$ : il est indifférent. Si Nicole joue $y = 70$, il compare $150p - 70$ (louer à 70) à $-150p$ (pas de location) :

$$150p - 70 \geq -150p \iff 300p \geq 70 \iff p \geq \frac{7}{30} \approx 0{,}23$$

Cette inégalité se lit ainsi : payer 70 k€ devient préférable à subir la panne dès que le risque de ciel couvert dépasse $7/30$, soit un peu moins d'une chance sur quatre.

Les meilleures réponses de Nicole. Face à $x = 50$, elle compare son espérance $50 - 55p$ au $0$ qu'elle obtient sans location. Elle accepte tant que $50 - 55p \geq 0$, c'est-à-dire $55p \leq 50$, soit $p \leq 50/55 = 10/11 \approx 0{,}91$. Face à $x = 70$, elle compare cette même espérance aux $15$ certains de la location à 70 : $50 - 55p \geq 15$ donne $55p \leq 35$, soit $p \leq 35/55 = 7/11 \approx 0{,}64$. Plus le ciel menace, moins accepter 50 k€ lui rapporte, puisque le groupe tournera vraiment.

En croisant les deux listes :

• $p \leq 7/11$ : Nicole accepte 50 dans les deux cas. Comme Marc est indifférent face à $y = 50$, les équilibres sont $(50, 50)$ et $(70, 50)$, mais ils donnent le même résultat concret : location à 50 k€ ;
• $7/11 < p \leq 10/11$ : deux équilibres, $(50, 50)$ et $(70, 70)$. Le risque est devenu assez élevé pour que Nicole tienne bon face à un Marc qui demande 70 ;
• $p > 10/11$ : la panne est quasi certaine, Nicole n'a plus aucune raison de céder. Équilibre unique $(70, 70)$.

Pour le vérifier, remonter à la matrice : placer le curseur de part et d'autre de $0{,}64$, puis de $0{,}91$, et demander à chaque fois la vérification. Les équilibres changent exactement à ces deux seuils. Pile sur un seuil, Nicole est indifférente et les équilibres des deux zones voisines coexistent : en $p = 7/11$, il y en a trois.

Le code ci-dessous construit la matrice et cherche les équilibres pour quelques valeurs de $p$. Il suffit de modifier la liste des valeurs et de relancer.

Et voici la lecture graphique : l'espérance de gain de Marc, selon $p$, pour chacune de ses deux stratégies face à une Nicole qui insiste sur 70.

Les deux droites se croisent en $p = 7/30$. À gauche, Marc préfère renoncer à la location ; à droite, il préfère payer 70 k€.

Stratégies mixtes

Que se passe-t-il quand il n'y a pas d'équilibre en stratégies pures ? Personne ne peut se permettre d'être prévisible : il faut tirer au sort sa stratégie.

Le calcul repose sur une observation qui surprend toujours :

Retour à la seconde matrice des fournisseurs. La stratégie Élevé est strictement dominée par Moyen pour les deux joueurs ($3 > 2$, $4 > 1$, $2 > 0$) : on l'élimine. Il reste un jeu 2 × 2 :

A \ B	Moyen	Cassé
Moyen	4,4	2,3
Cassé	3,2	3,3

Ce tableau ne se réduit plus. Colonne Moyen, A préfère Moyen, qui lui rapporte 4 contre 3 ; colonne Cassé, il préfère Cassé, qui lui rapporte 3 contre 2. Aucune ligne n'est meilleure partout : la bonne réponse de A dépend de ce que fait B, et réciproquement. C'est exactement la situation où être prévisible coûte cher.

Soit $q$ la probabilité que A joue Moyen. Pour que B soit indifférent :

• gain de B s'il joue Moyen : $4q + 2(1 - q) = 2 + 2q$
• gain de B s'il joue Cassé : $3q + 3(1 - q) = 3$

$2 + 2q = 3$ donne $2q = 1$, soit $q = 1/2$. Par symétrie du tableau, B joue Moyen avec la probabilité $1/2$ également, et chacun obtient une espérance de $3$. Traduit sur le marché : les deux fournisseurs alternent, un appel d'offres sur deux au prix moyen, sans que le concurrent puisse anticiper lequel.

Ce jeu a donc trois équilibres : deux purs et un mixte. Le mixte n'est pas une curiosité. Le théorème de Nash garantit qu'un jeu fini possède toujours au moins un équilibre, éventuellement en stratégies mixtes, et c'est lui qui prend le relais quand aucune case n'est stable.

Vérification

1.Un jeu n'a aucun équilibre de Nash en stratégies pures. Que conclure ?

Aucun joueur ne peut décider rationnellementIl en possède au moins un en stratégies mixtes, c'est le théorème de NashLe jeu est mal posé

2.À l'équilibre en stratégies mixtes, chaque joueur choisit ses probabilités pour…

rendre l'adversaire indifférent entre ses propres optionsmaximiser son gain moyen à lui, indépendamment de l'autreégaliser les gains des deux joueurs

3.Une stratégie strictement dominée peut-elle apparaître dans un équilibre de Nash ?

Non, jamais : une autre lui est préférable quoi que fasse l'adversaireOui, en stratégies mixtes seulementOui, si l'adversaire joue mal

4.Dans un jeu à somme nulle, que devient le gain de l'un quand l'autre gagne ?

Il augmente aussi, les deux joueurs coopèrentIl diminue d'autant : les deux gains se compensent exactementIl reste inchangé

Jeux séquentiels

Tout ce qui précède suppose des décisions simultanées : chacun écrit son prix sans voir celui de l'autre. Si Nicole voit la proposition de Marc avant de répondre, le jeu change de nature. Il devient séquentiel, et la matrice ne suffit plus à le décrire : une matrice ne sait pas dire qui parle en premier.

La forme qui convient est l'arbre, au sens où l'entend le chapitre sur les arbres : un sommet de départ, la racine, et des branches qui ne se rejoignent jamais. Chaque nœud porte le nom du joueur qui décide à cet instant, chaque branche une action possible, chaque feuille le couple de gains qui en résulte, (gain de Marc ; gain de Nicole). Voici le jeu avec $p = 0{,}8$, c'est-à-dire quatre chances sur cinq que le ciel soit couvert.

Sur un arbre, ce sont les feuilles qu'il faut lire en premier, jamais la racine. Les quatre couples de droite sont les seules données du problème, et ce sont exactement les gains de la matrice, calculés en $p = 0{,}8$. Second point à regarder : les deux nœuds « Nicole » portent le même nom mais ne sont pas le même choix, puisqu'elle y répond à deux propositions différentes. C'est précisément ce que la matrice ne savait pas représenter.

Résoudre un arbre : l'induction à rebours

On ne résout pas un arbre en partant du haut. On part des feuilles, et l'on remonte : c'est l'ordre d'un parcours en profondeur qui traite les enfants d'un nœud avant le nœud lui-même, comme dans le chapitre sur les parcours.

L'erreur la plus fréquente : à l'étape 1, chaque joueur maximise son propre gain, pas la somme des deux. C'est pour cela qu'un arbre peut aboutir à un résultat que les deux joueurs jugent mauvais sans qu'aucun ne puisse en dévier seul.

Le résultat mérite qu'on s'y arrête. Dans le jeu simultané, avec ce même $p = 0{,}8$, deux équilibres coexistaient et Marc pouvait fort bien se retrouver à payer 70. En jouant le premier, il obtient 70 de gain au lieu de 50 : parler d'abord lui rapporte. C'est ce qu'on appelle un avantage au premier joueur, et il n'a rien d'universel ; d'autres jeux le renversent complètement.

Le jeu de Nim : jouer d'abord, on expliquera après

L'induction à rebours résout n'importe quel jeu séquentiel à information parfaite. Elle a un coût : il faut remonter l'arbre entier. Sur le fil rouge, quatre feuilles suffisaient. Sur un jeu un peu long, l'arbre devient impraticable, et la vraie question devient : peut-on trouver le bon coup sans dérouler l'arbre ?

La réponse est oui, parfois, et la seule façon honnête de s'en convaincre est de se faire battre.

Règlela dernière fait gagnerla dernière fait perdreAdversaireNoviceApprentiStratègeImbattablevous 0 · 0 machine

Il reste 21 allumettes.

Je retire123

À vous de jouer : retirez 1, 2 ou 3 allumettes. Commencer contre le novice, puis monter d'un cran après chaque victoire.

Un indice ? (jouez d'abord une partie)

Rien n'est caché, il n'y a aucun hasard, et pourtant le jeu ne se devine pas. Ce qui frappe, quand on perd plusieurs fois de suite, c'est que l'adversaire ne semble jamais réfléchir longtemps ni tendre de piège : il se contente de répondre. La partie paraît se décider bien avant la fin, sans qu'on voie où.

Ce que la partie a montré

Reprenons le jeu par où il se termine, comme un arbre qu'on remonte depuis ses feuilles. Sauf qu'ici, une position se résume à un seul nombre : combien d'allumettes restent devant celui qui doit jouer.

• Devant 1, 2 ou 3 allumettes, on prend tout et on gagne. Ces trois positions sont gagnantes.

• Devant 4, tout est perdu. On en retire 1, 2 ou 3, donc on en laisse 3, 2 ou 1 : dans les trois cas, l'adversaire se trouve devant une position gagnante et rafle la mise.

• Devant 5, 6 ou 7, il suffit de ramener l'adversaire à 4, ce qui est toujours possible. Positions gagnantes.

• Devant 8, même impasse qu'à 4 : on laisse 7, 6 ou 5, et l'adversaire ramène la position à 4.

• Devant 9, 10 ou 11, on ramène à 8. Et ainsi de suite.

Le motif se referme : trois positions gagnantes, une perdante, trois gagnantes, une perdante. Les positions perdantes reviennent tous les quatre crans : 4, 8, 12, 16, 20. Ce sont exactement les nombres que la machine rendait, partie après partie.

La même figure, avec cette fois les positions condamnées en évidence. Le calcul affiché est simplement la division euclidienne par 4 : ce qui compte n'est pas le quotient, c'est le reste.

Règlela dernière fait gagnerla dernière fait perdreAdversaireNoviceApprentiStratègeImbattablevous 0 · 0 machine

Il reste 21 allumettes.

Je retire123

21 = 5 × 4 + 1 : le reste ne vaut pas 0, donc la position est gagnante. Retirer 1 allumette laisse 20, et 20 est un multiple de 4.

0123456789101112131415161718192021

En ambre, les positions perdues pour celui qui doit jouer : les nombres ≡ 0 modulo 4. Toute la stratégie consiste à y renvoyer l'adversaire, tour après tour.

Ce qu'on vient de faire, en langage d'induction à rebours

Le tableau G/P ci-dessus est une induction à rebours : on est parti des positions finales et on a remonté. Mais au lieu de porter sur un arbre de parties, il porte sur les 21 positions du jeu, ce qui n'est pas la même chose du tout. L'arbre des parties de ce jeu compte plusieurs centaines de milliers de branches ; les positions se comptent sur les doigts de deux mains et deux pieds.

Et le tableau lui-même n'a plus besoin d'être retenu, puisqu'il se résume à une opération : calculer $n \bmod 4$. On est passé d'une exploration à un calcul, et c'est tout l'objet de ce qui suit.

Changer un mot : la variante misère

Un seul mot change dans la règle : celui qui prend la dernière allumette perd. Rejouer quelques parties avec le sélecteur règle sur « la dernière fait perdre », avant de lire le paragraphe suivant.

Changer le plafond

Rien dans le raisonnement ne tenait au nombre 3. Si l'on peut retirer jusqu'à $p$ allumettes, le complément devient $p + 1 - k$, chaque aller-retour retire $p + 1$, et tout se joue modulo $p + 1$ : positions perdantes aux multiples de $p+1$ en jeu normal, aux $n \equiv 1$ en misère.

Règlela dernière fait gagnerla dernière fait perdreAdversaireNoviceApprentiStratègeImbattablevous 0 · 0 machine

Il reste 20 allumettes.

Je retire12345

20 = 3 × 6 + 2 : le reste ne vaut pas 0, donc la position est gagnante. Retirer 2 allumettes laisse 18, et 18 est un multiple de 6.

01234567891011121314151617181920

En ambre, les positions perdues pour celui qui doit jouer : les nombres ≡ 0 modulo 6. Toute la stratégie consiste à y renvoyer l'adversaire, tour après tour.

Ce que ce jeu enseigne

L'induction à rebours donnait la réponse, mais au prix d'une exploration. Elle s'est résumée à une quantité calculée directement sur la position : le reste de $n$ modulo $p+1$. Cette quantité vaut zéro exactement sur les positions perdantes, tout coup la rend non nulle, et un bon coup la ramène à zéro.

Mesurons l'écart. Depuis 21 allumettes, l'arbre complet compte 223 317 parties distinctes, et une partie dure de 7 à 21 coups : le dérouler à la main est hors de question. Mais la position, elle, ne prend que 22 valeurs, de 0 à 21. C'est la différence entre lire 223 317 histoires et lire une division par 4, et c'est le même écart que celui mesuré dans le chapitre sur la complexité.

Deux leçons à en tirer, qui dépassent largement les allumettes.

1. Chercher l'invariant avant de dérouler l'arbre. Quand le nombre d'histoires explose mais que le nombre d'états reste petit, c'est le signe qu'un raisonnement sur l'état seul doit exister. La même question se pose devant un cache, un protocole de consensus ou un ordonnanceur.
2. Jouer contre un adversaire faible n'apprend rien. On bat le novice sans comprendre le jeu. L'information est venue de l'adversaire qui ne se trompe jamais, et elle est venue des défaites, pas des victoires. C'est aussi pour cette raison qu'on évalue une stratégie contre le pire cas, et non contre un cas moyen complaisant : le maximin du début de chapitre était déjà ce réflexe-là.

Information incomplète : ignorer l'adversaire lui-même

Jusqu'ici, l'incertitude portait sur le monde : Marc ignore si le ciel sera couvert, et il en fait une espérance. Les gains, en revanche, étaient connus des deux joueurs.

Un jeu est à information incomplète quand un joueur ignore une donnée de l'adversaire : son coût, ses contraintes, ses préférences. Ce n'est plus le ciel qui est incertain, ce sont les gains eux-mêmes.

Sur le fil rouge, Marc a supposé que faire tourner le groupe coûte 55 k€ à Diesel Pro. En réalité il ne connaît pas ce chiffre : c'est une donnée interne du fournisseur.

On retient deux types possibles. Un fournisseur au matériel récent, dont le coût de mise en marche est de 40 k€, et un fournisseur au matériel ancien, à 70 k€. Marc estime à 0,6 la probabilité du premier cas. Le jeu reste séquentiel, avec $p = 0{,}8$ : Marc propose, Nicole répond en connaissant son propre coût.

Exercices type

Dans la guerre des prix entre les deux fournisseurs (première version), montrer que Cassé est dominante pour A

Ligne Cassé : $(4, 5, 3)$. Ligne Moyen : $(3, 4, 2)$. Ligne Élevé : $(2, 1, 0)$.

Colonne par colonne : $4 > 3 > 2$, $5 > 4 > 1$, $3 > 2 > 0$. Cassé rapporte strictement plus que les deux autres dans chaque colonne, donc quelle que soit la décision de B : elle est strictement dominante.

Le tableau étant symétrique, Cassé est aussi dominante pour B. L'unique équilibre est (Cassé, Cassé), qui rapporte $(3, 3)$, alors que (Moyen, Moyen) aurait donné $(4, 4)$.

Un joueur peut-il avoir deux stratégies dominantes ?

Non, pas au sens strict. Si $S$ domine strictement toutes les autres et $T$ aussi, alors $S$ rapporte strictement plus que $T$ et $T$ strictement plus que $S$ : contradiction.

La dominance faible (avec $\geq$ au lieu de $>$, et au moins une inégalité stricte) est plus souple, et le fil rouge en donne un exemple. Face à $y = 50$, les deux stratégies de Marc rapportent le même gain ; face à $y = 70$, écrire 70 rapporte plus dès que $p > 7/30$. Pour $p > 7/30$, $x = 70$ est donc faiblement dominante : jamais moins bonne, parfois meilleure. Pour $p < 7/30$, c'est $x = 50$. Les deux ne rapportent exactement la même chose partout qu'en $p = 7/30$.

Combien d'équilibres de Nash peut avoir un jeu 2 × 2 en stratégies pures ?

Tant qu'aucun joueur n'est indifférent entre deux cases qu'il compare, zéro, un ou deux.

• Zéro : l'audit inopiné (le jeu de « pile ou face », matching pennies), où le contrôleur veut tomber au même moment que l'écart, et l'équipe contrôlée veut l'éviter.
• Un : le dilemme du prisonnier.
• Deux : les jeux de coordination, comme la seconde matrice réduite du chapitre.

Trois ou quatre ne sont possibles qu'avec des égalités de gains. Le fil rouge en donne un cas : en $p = 7/11$, Nicole est indifférente face à $x = 70$, et $(50, 50)$, $(70, 50)$ et $(70, 70)$ sont tous trois des équilibres. Quatre équilibres demandent qu'aucun des deux joueurs ne puisse jamais gagner à changer, par exemple quand tous les gains sont égaux.

En comptant les mixtes, un jeu de coordination à deux équilibres purs en a trois au total.

Le fil rouge avec p = 0,3 : quels sont les équilibres ?

$0{,}3 < 7/11 \approx 0{,}64$, donc Nicole accepte 50 quelle que soit la proposition de Marc.

Marc étant indifférent face à $y = 50$, les équilibres sont $(50, 50)$ et $(70, 50)$. Dans les deux cas le résultat concret est identique : location à 50 k€, Marc gagne $150 \times 0{,}3 - 50 = -5$ et Nicole $50 - 55 \times 0{,}3 = 33{,}5$.

Marc perd 5 k€ en espérance par rapport à la référence « ni panne ni dépense ». Mais sans location il perdrait $150 \times 0{,}3 = 45$ k€ : la location lui fait gagner 40 k€ par rapport à cette option. Un gain négatif ne dit pas qu'une décision est mauvaise, il dit seulement où se trouve la référence.

L'audit inopiné : un contrôleur qualité (A) passe le matin ou le soir ; une équipe (B) saute une étape de procédure le matin ou le soir. A gagne 1 s'il tombe sur l'écart, B gagne 1 sinon. Trouver l'équilibre.

A \ B	Matin	Soir
Matin	1,−1	−1,1
Soir	−1,1	1,−1

Aucun équilibre pur, et le dessin le dit : aucune case ne porte les deux soulignages. Si le contrôleur passe toujours le matin, l'équipe triche le soir ; s'il passe toujours le soir, elle triche le matin. Toute habitude se fait exploiter.

Soit $q$ la probabilité que A passe le matin. Gain de B s'il triche le matin : $-q + (1 - q) = 1 - 2q$. S'il triche le soir : $q - (1 - q) = 2q - 1$. Indifférence : $1 - 2q = 2q - 1 \iff q = 1/2$.

Par symétrie, B choisit le matin avec la probabilité $1/2$. Chacun tire au hasard, comme à pile ou face, et l'espérance de gain est nulle pour les deux. C'est le seul équilibre du jeu, et c'est la raison pour laquelle un audit sérieux est tiré au sort : un calendrier prévisible ne contrôle rien.

Pourquoi Marc a-t-il intérêt à consulter la météo avant d'ouvrir la négociation ?

Parce que la structure de l'équilibre change au passage de $p = 7/11$. En dessous, il obtient le prix de 50 k€ ; au-dessus, Nicole peut tenir bon à 70 k€.

Connaître $p$ lui dit dans quel jeu il se trouve, donc s'il peut se permettre d'annoncer 50 en espérant que Nicole cède. C'est le sens de la modélisation : elle ne fabrique pas la décision, elle indique quelle information a réellement de la valeur, ici, une prévision météo qui ne coûte rien.

La méthode

1. Identifier les joueurs et leurs stratégies avant tout calcul. Deux joueurs, deux ou trois stratégies chacun : le tableau doit tenir sur trois lignes.
2. Choisir une référence pour les gains et l'écrire. Tous les gains s'y rapportent, sans exception.
3. Écrire l'espérance case par case quand il y a du hasard, en séparant explicitement les scénarios ($p$ et $1 - p$).
4. Chercher les stratégies dominées en premier : chaque élimination divise la taille du problème.
5. Souligner les meilleures réponses, colonne par colonne pour les lignes, ligne par ligne pour les colonnes. Les cases doublement soulignées sont les équilibres.
6. Discuter selon le paramètre s'il y en a un : écrire les inégalités, les résoudre, et donner les intervalles de $p$ avec l'équilibre correspondant.
7. Sur un jeu séquentiel, partir des feuilles, jamais de la racine, et chercher avant tout si une quantité calculée sur la position rend l'exploration inutile.
8. Conclure en français. « L'équilibre est $(70, 70)$ » ne vaut rien sans « c'est-à-dire que Nicole tient bon et que Marc paie le prix fort, parce que le risque de panne le prive de sa marge de négociation ».

Synthèse

• Un jeu = joueurs + stratégies + gains. On y entre dès que le gain de l'un dépend du choix d'un autre.
• La matrice des gains s'écrit (gain du joueur des lignes, gain du joueur des colonnes). Construire cette matrice est 80 % du travail.
• Un gain se mesure par rapport à une référence explicite, la même dans toutes les cases.
• Une stratégie dominante rapporte plus quel que soit l'adversaire : on élimine les dominées d'abord.
• Équilibre de Nash : personne ne gagne à dévier seul. Méthode des soulignements, systématique.
• Un équilibre n'est ni unique, ni forcément bon pour les joueurs (dilemme du prisonnier).
• Somme nulle : maximin $=$ minimax $\Rightarrow$ point selle, et cette valeur commune est la valeur du jeu.
• Sous incertitude, les gains deviennent des espérances et l'équilibre se discute selon $p$.
• Stratégies mixtes : on choisit ses probabilités pour rendre l'adversaire indifférent. Il en existe toujours un (théorème de Nash).
• Jeu séquentiel : arbre + induction à rebours, en partant des feuilles.
• Toute position est gagnante ou perdante ; on les détermine en remontant depuis la fin de partie, et le bon résultat est le critère qui les distingue, pas la liste.
• Au jeu de Nim (21 allumettes, on en retire 1 à $p$), ce critère est $n \bmod (p+1)$ : rendre la main sur un multiple de $p+1$, parce qu'un aller-retour en retire toujours $p+1$. En misère, la cible glisse à $n \equiv 1$.
• Information incomplète : les types possibles de l'adversaire, pondérés par une croyance, ramènent le problème à une espérance.

Et ensuite

Tout ce chapitre a raisonné « en fonction de $p$ », cette probabilité de panne posée sans jamais être calculée. Elle ne tombe pas du ciel : elle se déduit d'un modèle. Lois discrètes et analyse de risque installe les quatre lois qui la produisent.