Jeux séquentiels et information incomplète

Jeux séquentiels

Les chapitres précédents supposent des décisions simultanées : dans la rue à une seule voie, les deux automobilistes s'engagent ou attendent au même instant. Il suffit que l'un avance d'un mètre avant l'autre pour que le jeu change de nature. Il devient séquentiel, et la matrice du jeu simultané ne suffit plus à le décrire : elle ne dit ni qui a bougé en premier, ni ce que le second a vu avant de choisir.

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 A ; gain de B). Voici le jeu avec la probabilité d'encombrement du chapitre précédent fixée à ${p = 0{,}25}$, c'est-à-dire une chance sur quatre que la voie soit encombrée.

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 du chapitre précédent, calculés en ${p = 0{,}25}$ : celui qui passe seul gagne en moyenne ${3 - 4 \times 0{,}25 = 2}$ minutes. Second point à regarder : les deux nœuds « B » portent le même nom mais ne sont pas le même choix, puisque B y répond à deux situations différentes. C'est précisément ce que la matrice 2 × 2 du jeu simultané ne savait pas représenter.

Résoudre un arbre : l'induction à rebours

On ne résout pas un arbre en partant de la racine. On part des feuilles, à droite de la figure, et l'on remonte vers la racine, à gauche : 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.

Induction à rebours, en trois gestes.

1. Choisir un nœud dont toutes les branches mènent à des feuilles. Le joueur qui y décide n'a plus personne à anticiper : il compare, d'une branche à l'autre, son propre gain, et garde la branche où il est le plus grand.
2. Remplacer ce nœud par le couple de gains de la branche retenue. Le nœud devient une feuille.
3. Recommencer, un cran plus près de la racine, jusqu'à ce que la racine elle-même soit devenue une feuille.

À l'étape 1, chaque joueur maximise son propre gain : pas la somme des deux, et il ne cherche pas non plus à faire perdre l'autre. L'oublier est l'erreur la plus fréquente. C'est aussi pourquoi un arbre peut aboutir à un résultat que les deux joueurs jugent mauvais, sans qu'aucun n'ait intérêt à s'en écarter seul : la section sur le dilemme qui se rejoue en donne un exemple.

Le résultat mérite qu'on s'y arrête. Dans le jeu simultané, deux équilibres purs coexistaient, et rien ne disait lequel serait joué : A pouvait tout aussi bien se retrouver à attendre pendant que B passait, et l'équilibre mixte, où chacun tente sa chance une fois sur deux, ne rapportait rien à personne. En avançant le premier, A s'assure à tous les coups une espérance de 2 minutes, puisque B attendra. C'est ce qu'on appelle un avantage du premier joueur.

Ce que l'arbre montre et que la matrice du jeu simultané cachait : le premier qui bouge ne gagne pas parce qu'il est plus rapide, mais parce que son geste est irréversible et vu de l'autre. B ne choisit plus entre deux équilibres : il répond à une situation déjà fixée, et dans celle-là, s'engager lui coûterait 2 minutes. L'option existe toujours, elle ne lui rapporte simplement plus rien.

Cet avantage n'a rien d'universel, et l'audit inopiné du chapitre précédent le renverse. Si le contrôleur fixe son créneau le premier, et que l'équipe le connaît avant de choisir le sien, parce que le planning des contrôles est affiché par exemple, elle saute son étape à l'autre moment et gagne à chaque fois : le contrôleur passe de 0 en moyenne, quand il tirait au sort, à $-1$ à coup sûr. Jouer en premier, c'est se dévoiler. Cela paie quand l'autre a intérêt à s'accommoder du coup qu'il voit, comme B qui préfère céder plutôt que provoquer le face-à-face ; cela coûte quand il a intérêt à le contrer, comme l'équipe qui cherche précisément à éviter le contrôleur.

Ce que l'arbre écarte

Pour voir ce que l'arbre écarte, il faut écrire en matrice le jeu séquentiel lui-même. Une stratégie de B n'y est plus une action, mais un plan complet : ce qu'il fait si A s'engage, et ce qu'il fait si A attend. Avec deux choix à chacun de ses deux nœuds, il en a $2 \times 2 = 4$ :

• s'engager toujours : s'engager dans les deux cas ;
• faire le contraire de A : attendre si A s'engage, s'engager si A attend ;
• faire comme A : s'engager si A s'engage, attendre si A attend ;
• attendre toujours : attendre dans les deux cas.

La matrice qui croise ces quatre plans avec les deux choix de A s'appelle la forme normale du jeu séquentiel. Chaque case se remplit en suivant le plan de B dans la branche choisie par A.

La matrice du jeu simultané en est un morceau : ses deux colonnes sont les deux plans qui ne regardent pas ce qu'a fait A, s'engager toujours et attendre toujours. Ce qui lui manquait, ce sont les deux plans du milieu, ceux qui répondent.

Le test de la déviation y trouve trois équilibres de Nash. Dans chacun, A n'a rien à gagner à changer de ligne, et B rien à gagner à changer de colonne dans la ligne jouée.

• (A s'engage, B fait le contraire de A) est celui que l'arbre retient : « le contraire de A » est exactement le plan que l'induction a trouvé nœud par nœud.
• (A attend, B s'engage toujours) est exactement la menace : face à ce plan, A a raison d'attendre, et B, qui n'a jamais à l'exécuter, n'a aucune raison d'en changer.
• (A s'engage, B attend toujours) donne la même partie que le premier : A passe, et la case vaut $(2 ; 0)$. Il n'en diffère que par ce que B ferait si A attendait : il attendrait aussi, et renoncerait aux 2 minutes du passage. C'est une réponse qu'il ne donnerait pas le moment venu, mais comme la partie n'y passe jamais, elle ne lui coûte rien dans la matrice.

L'induction à rebours n'en garde qu'un, parce qu'elle exige un choix optimal à chaque nœud, même à ceux que la partie n'atteint pas. La portion de l'arbre qui part d'un nœud, avec tout ce qui en descend, s'appelle un sous-jeu. La rue en compte trois : l'arbre entier, et les deux petits jeux qui commencent aux nœuds de B, où B choisit seul. Un équilibre parfait en sous-jeux est un couple de plans qui reste un équilibre dans chacun d'eux. Le plan « s'engager toujours » échoue au sous-jeu qui suit « A s'engage » : il y fait jouer $-2$ à B quand $0$ est possible. Le plan « attendre toujours » échoue à celui qui suit « A attend ». Seul « le contraire de A » passe les trois. Tout équilibre parfait est un équilibre de Nash, puisque l'arbre entier est l'un des sous-jeux ; la réciproque est fausse, et c'est par cette brèche que passent les menaces en l'air.

Quand le dilemme se rejoue

La section précédente a montré qu'une menace ne vaut que si son exécution reste avantageuse le moment venu. Un jeu qui se rejoue en fabrique de telles, parce que l'avenir donne à chacun de quoi punir l'autre.

Le premier chapitre a laissé deux fournisseurs pris dans une guerre des prix. Casser son prix y est dominant pour chacun, et tous deux récoltent 4 au lieu des 7 que leur aurait laissés le prix moyen. Il annonçait aussi qu'un appel d'offres qui revient chaque année change la donne. Voici pourquoi, sur le tableau réduit aux deux prix qui comptent.

Joué une seule fois, ce jeu est simultané. Répété, il devient séquentiel, même si chaque appel d'offres se joue à l'aveugle : avant de répondre, chacun sait ce que l'autre a fait les années précédentes. Une stratégie n'est donc plus un prix, c'est un plan qui dit quel prix proposer après chaque histoire possible, exactement comme le plan complet de B dans la rue. Le plus simple : tenir le prix moyen tant que l'autre l'a tenu, et casser ses prix pour toujours dès qu'il a cassé les siens.

Face à un concurrent qui suit ce plan, tenir rapporte 7 cette année, puis 7 chaque année. Trahir rapporte 8 cette année, puis 4 chaque année, une fois la guerre des prix déclenchée. Rien ne garantit pourtant que l'appel d'offres revienne : on note $\delta$ la probabilité qu'il se rejoue l'année suivante, avec le même concurrent. La deuxième année n'a donc lieu qu'avec la probabilité $\delta$, la troisième avec $\delta^2$, et ainsi de suite : le gain espéré de qui tient est la somme d'une suite géométrique.

Celui de qui trahit se compte de la même façon, avec 8 la première année et 4 ensuite :

Après le 8, c'est encore une suite géométrique de raison $\delta$, mais son premier terme est $4\delta$ et non $4$, puisque la deuxième année n'a lieu qu'avec la probabilité $\delta$. Sa somme vaut donc ce premier terme divisé par $1 - \delta$, exactement comme $\dfrac{7}{1 - \delta}$ est le premier terme 7 divisé par $1 - \delta$. Tenir l'emporte dès que

La deuxième ligne multiplie la première par $1 - \delta$, qui est positif. La même inégalité se lit plus directement en ne gardant que ce qui diffère : trahir rapporte 1 point de plus la première année, puis 3 points de moins chaque année suivante, soit $3\,(\delta + \delta^2 + \dots) = \dfrac{3\delta}{1 - \delta}$ points perdus en espérance. Tenir l'emporte quand $\dfrac{3\delta}{1 - \delta} \geq 1$, c'est-à-dire quand $\delta \geq 1/4$. Dès qu'il y a une chance sur quatre de se retrouver, le prix tenu devient un équilibre : le point gagné aujourd'hui ne compense plus les points perdus ensuite, il les égale tout au plus. Le seuil est bas parce que la tentation est faible et la punition lourde : la trahison rapporte 1 point une seule fois, la guerre des prix en coûte 3 chaque année. Et la menace de représailles est crédible, ce qui la distingue de celle de la rue : une fois la guerre déclarée, casser son prix est la meilleure réponse à un concurrent qui casse le sien, si bien que l'exécuter ne coûte rien à celui qui l'a annoncée.

Ce n'est pas un appel à s'entendre, qui serait illicite ; c'est l'explication de ce qu'on observe quand les mêmes acteurs se retrouvent. C'est aussi la raison pour laquelle un client qui veut une vraie concurrence ouvre ses appels d'offres à de nouveaux entrants : chaque fournisseur a alors moins de chances de retrouver le même concurrent l'année suivante, $\delta$ baisse, et le prix tenu cesse d'être un équilibre quand il passe sous 1/4.

Le plan qui casse ses prix pour toujours n'est pas le seul. Le plus connu, donnant-donnant, commence par tenir son prix, puis rejoue simplement ce que l'autre a fait l'année précédente : il répond à chaque trahison par une trahison, et pardonne dès que l'autre revient au prix moyen. C'est lui qui a remporté les tournois de stratégies que Robert Axelrod a organisés et racontés dans The Evolution of Cooperation (1984). Le protocole BitTorrent en applique l'esprit : un pair envoie en priorité à ceux qui lui envoient.

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

L'induction à rebours résout n'importe quel jeu séquentiel fini à information parfaite, c'est-à-dire où chacun voit tous les coups joués avant le sien : c'est le cas de la rue jouée en séquence. Le dilemme répété n'en est pas un, puisque chaque année les deux prix sont fixés à l'aveugle ; l'induction y a fonctionné année par année, parce que chaque année, une fois la suite jouée d'avance, redevient le dilemme simple du premier chapitre. 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.

La règle, en trois lignes. Vingt-et-une allumettes sont posées en rangée. Chacun son tour, un joueur en retire 1, 2 ou 3, jamais zéro. Celui qui prend la dernière allumette gagne.

C'est, à un mot près, le jeu des bâtonnets de Fort Boyard : à la télévision, celui qui prend le dernier bâtonnet perd, et c'est la variante que la section « Changer un mot » étudie. Le maître du jeu y joue en second, et il lui arrive de perdre. La suite explique pourquoi il gagne si souvent.

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é

Reprendre 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 0 allumette, la partie est finie : l'autre vient de prendre la dernière, et celui qui devait jouer a perdu. C'est la position perdante d'où tout part.
• 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 : 0, 4, 8, 12, 16, 20. Ce sont exactement les nombres que la machine rendait, partie après partie.

La stratégie, et la raison qui la rend imparable. Rendre la main à l'adversaire sur un multiple de 4.

La raison tient en une addition. Si l'adversaire retire $k$ allumettes, avec $k \in \{1, 2, 3\}$, on répond en retirant $4 - k$, qui est aussi entre 1 et 3 : le coup est toujours légal. Chaque aller-retour retire donc exactement 4 allumettes, quoi qu'il tente. En partant d'un multiple de 4, on parcourt les multiples de 4 en descendant jusqu'à 0, et c'est l'adversaire qui se retrouve devant la rangée vide.

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.

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

La liste ci-dessus est une induction à rebours : on est parti de la position finale et on a remonté. Mais elle ne porte pas sur l'arbre des parties, elle porte sur les 22 positions du jeu, de 0 à 21. Ce raccourci tient à une remarque : beaucoup de branches différentes mènent à la même position. Prendre 1 puis 2, ou 2 puis 1, laisse dans les deux cas 18 allumettes au même joueur, et la suite de la partie ne dépend que de ces 18 allumettes, pas du chemin qui y a mené. Il suffit donc de résoudre chaque position une fois. L'arbre des parties compte plusieurs centaines de milliers de branches ; les positions, elles, tiennent sur une ligne.

Et la liste elle-même n'a plus besoin d'être retenue. En notant $n$ le nombre d'allumettes devant celui qui doit jouer, elle se résume à une opération : calculer le reste de $n$ dans la division par 4, ce qu'on appelle $n$ modulo 4, et que Python écrit n % 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'à $m$ allumettes, le complément devient $m + 1 - k$, chaque aller-retour retire $m + 1$, et tout se joue modulo $m + 1$ : positions perdantes aux multiples de $m + 1$ en jeu normal, aux nombres dont le reste dans la division par $m + 1$ vaut 1 en misère.

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$ dans la division par $m + 1$. Cette quantité vaut zéro exactement sur les positions perdantes. Depuis une position où elle vaut zéro, tout coup la rend non nulle ; depuis une position où elle ne l'est pas, un coup bien choisi la ramène à zéro.

L'écart se mesure. 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 ce qui résume la position avant de dérouler l'arbre. Quand le nombre d'histoires explose mais que le nombre de positions reste petit, c'est le signe qu'un raisonnement sur la position seule doit exister. La quantité qui le porte, ici le reste de la division, est celle que la bonne stratégie ramène à zéro chaque fois qu'elle joue : on l'appelle un invariant.
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 pourquoi, dans un jeu à somme nulle comme celui-ci, on évalue une stratégie contre le pire adversaire et non contre un adversaire complaisant : le pire pour soi y est le mieux pour l'autre, et c'était déjà le réflexe du maximin du chapitre précédent.

Le jeu de Nim proprement dit, celui de Charles Bouton en 1901, se joue sur plusieurs tas. Sa stratégie tient elle aussi en une quantité calculée sur la position, mais elle s'écrit en binaire.

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

Le jeu de Nim est l'extrême opposé de ce qui vient : tout y est visible, les coups comme les gains, et il ne reste qu'à calculer. Retour à la rue, pour lever la dernière hypothèse que le chapitre a gardée depuis le début : chacun connaît les gains de l'autre.

Jusqu'ici, l'incertitude portait sur le monde : A ignore si la voie est encombrée, et il en fait une espérance. Les gains de B, en revanche, A les connaissait.

Un jeu est à information incomplète quand un joueur ignore une donnée de l'adversaire qui fixe ses gains : son coût, ses contraintes, ses préférences. Ce n'est plus l'état de la voie qui est incertain, ce sont les gains eux-mêmes. Il ne faut pas le confondre avec l'information imparfaite, où l'on ignore le coup de l'adversaire parce qu'il a été joué sans qu'on le voie, comme le prix du concurrent l'année même, dans le dilemme qui se rejoue.

Sur le fil rouge, A a supposé qu'attendre ne coûtait rien à B. C'est vrai pour un automobiliste qui ne compte que son temps ; ce n'est pas le cas de celui que l'attente exaspère, et A n'a aucun moyen de savoir lequel des deux il a en face.

On retient donc deux types. Un B tranquille, pour qui attendre vaut $0$ comme jusqu'ici. Et un B impatient, que l'attente exaspère : rester arrêté à regarder l'autre passer lui pèse plus que le face-à-face, où il aura au moins tenté sa chance. Il chiffre cette attente à $-3$, contre $-2$ pour le face-à-face.

Ce $-3$ n'est pas une durée. En minutes, le face-à-face coûte toujours plus que l'attente, puisqu'il faut ensuite reculer ou laisser l'autre reculer : un B qui ne compterait que son temps attendrait toujours. Le $-3$ chiffre l'agacement, et c'est lui qui change le choix de B.

A estime à $0{,}6$ la probabilité que B soit tranquille, et donc à $0{,}4$ celle qu'il soit impatient. Le jeu reste séquentiel, avec ${p = 0{,}25}$ : A avance d'abord, B répond en sachant, lui, de quel type il est.

L'arbre accueille ce calcul tel quel. Un troisième joueur, le hasard, tire le type de B, avec les probabilités de la croyance de A : $c = 0{,}6$ pour le tranquille, $0{,}4$ pour l'impatient. Le tirage est dessiné après le coup de A : en réalité B est impatient ou non avant que A n'avance, mais A ne le voit pas, et pour lui cela revient au même. B, lui, répond en connaissant son type. À chaque nœud du hasard, la valeur est l'espérance des deux branches, pondérées par cette croyance.

La racine vaut $(0{,}4 ; -0{,}8)$ : 0,4 minute pour A, comme dans le calcul ci-dessus, et une perte moyenne de 0,8 minute pour B, qui paie les face-à-face de son type impatient.

Le mouvement, en une phrase. L'incertitude sur l'adversaire se ramène à l'incertitude sur le monde. On remplace un adversaire inconnu par une loterie entre plusieurs adversaires connus, et le calcul redevient celui qu'on sait faire : une espérance.

Ce que vaut l'information

L'encadré conclut qu'il faut aller chercher l'information qui manque. Encore faut-il savoir combien elle vaut. Si A savait à qui il a affaire avant d'avancer, il s'engagerait face au tranquille, pour 2 minutes en moyenne, et attendrait face à l'impatient, pour 0 au lieu du face-à-face à $-2$. Son espérance passerait à

contre 0,4 sans savoir. L'écart, 0,8 minute, est ce que vaut pour lui l'information sur le type de B.

Ici, prendre le temps de regarder la voiture d'en face vaut la peine tant que cela coûte moins de 0,8 minute. Dans un jeu, en revanche, savoir ne profite pas toujours, parce que l'autre peut s'en servir. Si B sait que A attendra de voir ce qu'il fait avant de choisir, B n'a qu'à s'engager le premier : A, informé, n'a plus qu'à attendre, et perd l'avantage du premier joueur. Rien de tel ici, où l'information porte sur le type de B, que B ne peut pas changer.

La valeur de l'information dépend de la croyance, et elle est la plus grande là où la décision est la plus fragile. Informé, A gagne $2$ face au tranquille et $0$ face à l'impatient, soit $2c$ en moyenne. Sans savoir, il gagne $0$ sous la bascule, en attendant, et $4c - 2$ au-dessus, en s'engageant. La valeur de l'information vaut donc $2c$ sous la bascule et $2c - (4c - 2) = 2 - 2c$ au-dessus : 1 minute en $c = 1/2$, 0,8 en $c = 0{,}6$, 0,2 seulement en $c = 0{,}9$. Une décision robuste n'a presque rien à gagner à une étude ; une décision qui bascule près de l'estimation a le plus à y gagner.

La méthode

1. Dessiner l'arbre avant tout calcul : un nœud par décision, une branche par option, un gain par feuille. Indiquer à chaque nœud qui décide.
2. Partir des feuilles, jamais de la racine. Remonter nœud par nœud en donnant à chacun la valeur que son joueur choisirait, d'après ses propres gains.
3. Chercher d'abord une quantité calculable sur la position, comme le reste d'une division. Quand elle existe, elle rend l'exploration inutile et la stratégie se résume à une ligne.
4. Éprouver toute menace en se plaçant au nœud où elle devrait s'exécuter : elle n'est crédible que si l'exécuter est alors préférable à y renoncer. Un équilibre de Nash qui repose sur une menace en l'air n'est pas parfait en sous-jeux.
5. Sur un jeu qui se rejoue, comparer ce que rapporte la trahison une fois à ce qu'elle coûte ensuite, en pondérant chaque année par la probabilité de se retrouver.
6. Sur une information incomplète, écrire les types possibles et la croyance associée, puis calculer une espérance sur les types. Chercher la croyance de bascule, et chiffrer la valeur de l'information avant de payer pour l'obtenir.
7. Conclure en français, en disant ce que fait chaque joueur et pourquoi il n'a pas intérêt à faire autrement.

Mettre en pratique

Chaque question reprend un geste du chapitre sur des nombres un peu différents : la réponse ne se relit pas, elle se refait.

La troisième question dit pourquoi la forme normale ne sert qu'aux petits arbres. Avec deux actions par nœud, un joueur qui décide à dix nœuds a déjà $2^{10} = 1\,024$ plans complets, et la matrice devient illisible bien avant l'arbre, que l'induction à rebours parcourt en visitant chaque nœud une seule fois. La dernière dit ce que vaut la tentation : plus la trahison rapporte sur le moment, plus il faut de chances de se revoir pour que le prix tenu résiste.