Jeux séquentiels et information incomplète

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.

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.

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.

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.

À calculer soi-même

Une position de Nim se juge par une division, et la stratégie entière tient dans le reste de cette division. Le vérifier en quelques lignes vaut mieux que de la retenir.

La dernière réponse dit pourquoi l'induction à rebours ne suffit pas toujours. Trente-et-un nœuds se parcourent à la main ; un jeu d'échecs en compterait davantage qu'il n'y a d'atomes dans l'univers observable. C'est exactement pourquoi le jeu de Nim vaut la peine : il possède une quantité calculable sur la position, le reste modulo 4, qui rend toute exploration inutile.

Où la démarche dérape

Une induction à rebours menée dans le bon sens, et une conclusion tirée du mauvais nœud.

Vérification

Exercices type

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.
3. Chercher d'abord une quantité calculable sur la position, comme le reste modulo un entier. 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.
5. Sur une information incomplète, écrire les types possibles et la croyance associée, puis calculer une espérance sur les types.
6. Conclure en français, en disant ce que fait chaque joueur et pourquoi il n'a pas intérêt à faire autrement.

Synthèse

• Un jeu séquentiel se représente par un arbre : nœuds de décision, branches, gains aux feuilles.
• L'induction à rebours remonte des feuilles vers la racine, et donne à chaque nœud la valeur que son joueur choisirait.
• Une menace non crédible est une annonce que son auteur n'exécuterait pas le moment venu. L'arbre la disqualifie ; la forme normale ne la voyait pas.
• Rendre une menace crédible suppose de changer les gains, pas de la répéter plus fort.
• Une position perdante est celle d'où tous les coups mènent à une position gagnante pour l'autre. Au Nim de plafond $k$, ce sont les multiples de $k + 1$.
• Une quantité calculable sur la position remplace toute l'exploration de l'arbre, et c'est ce qui rend un jeu résoluble sans machine.
• Sous information incomplète, l'inconnue n'est plus le coup de l'adversaire mais l'adversaire lui-même : on le modélise par des types et une croyance.

Et ensuite

Les croyances de la dernière section sont des probabilités posées sans être calculées. Lois discrètes et analyse de risque installe les lois qui les produisent, et Superviser un système montre ce qu'elles deviennent sur des mesures réelles.