GameTheory-10 — Équilibres Parfaits de Sous-Jeux et Induction Avant (Twin C#)

Jumeau C# (.NET Interactive) de GameTheory-10-ForwardInduction-SPE-Python.ipynb — marathon parité .NET ⇄ Python (#4956).

Ce notebook réimplémente from-scratch en C# pur (BCL .NET 9, 0 NuGet) les raffinements d’équilibre sur la forme extensive : équilibre parfait de sous-jeux (SPE via backward induction), analyse des menaces crédibles, perfection en mains tremblantes (trembling-hand), induction avant (forward induction, logique de Cho-Kreps) et signal par brûlage (burn money).

L’original Python s’appuie sur numpy/matplotlib pour les calculs et graphes ; ce twin traduit les algorithmes en type system C# + HashSet/LINQ, et restitue les résultats en tables console. La valeur ajoutée n’est pas un miroir : c’est un moteur de théorie des jeux extensifs typé, où l’arbre de jeu, la récursion de backward induction et la détection des sous-jeux vivent dans le système de types.

Voir aussi : GameTheory-10 (Python) · marathon #4956 · registre SOTA #3801.

Objectifs d’apprentissage

1. Définir un jeu sous forme extensive (arbre, nœuds de décision, nœuds terminaux, paiements).
2. Calculer l’équilibre parfait de sous-jeux (SPE) par backward induction (récursion sur l’arbre).
3. Distinguer menace crédible vs non-crédible (pourquoi certains équilibres de Nash ne survivent pas).
4. Appliquer la perfection en mains tremblantes (perturbation ε).
5. Maîtriser l’induction avant (forward induction) : déduire les intentions d’un joueur de ses actions hors-chemin.
6. Analyser le signal par brûlage (burn money).

Prérequis

• Théorie de l’équilibre de Nash (cf. GameTheory-4).
• Forme extensive (cf. GameTheory-7).

// Setup : types de base pour un jeu sous forme extensive.
#nullable enable
using System;
using System.Collections.Generic;
using System.Linq;

// Helper d'affichage (headless-safe : .Display() capture text/plain).
public static void Show(object? o) => (o?.ToString() ?? "<null>").Display();

// Noeud d'un arbre de jeu extensif (information parfaite : singleton info-set).
public sealed class GameNode
{
    public int Id { get; }
    public int Player { get; }               // joueur qui decide (-1 = terminal)
    public List<GameNode> Children { get; } = new();
    public List<string> Actions { get; } = new();   // etiquette d'action par enfant
    public double[]? Payoffs { get; }        // paiement terminal (null si decision)
    public bool IsTerminal => Player < 0;
    public GameNode(int id, int player, double[]? payoffs = null)
    { Id = id; Player = player; Payoffs = payoffs; }
    public GameNode AddChild(string action, GameNode child) { Actions.Add(action); Children.Add(child); return this; }
}

// Un jeu extensif = racine + nombre de joueurs.
public sealed class ExtensiveFormGame
{
    public GameNode Root { get; }
    public int NPlayers { get; }
    public string[] PlayerNames { get; }
    public ExtensiveFormGame(GameNode root, int n, string[]? names = null)
    { Root = root; NPlayers = n; PlayerNames = names ?? Enumerable.Range(0,n).Select(i=>$"J{i+1}").ToArray(); }
}

Show("Types charges : GameNode (arbre), ExtensiveFormGame, helper Show().");

Types charges : GameNode (arbre), ExtensiveFormGame, helper Show().

1. Sous-jeux et équilibre parfait (SPE)

1.1 Définition d’un sous-jeu

Un sous-jeu est un sous-arbre commençant à un nœud de décision et contenant tous ses descendants (sans couper d’information). En information parfaite, tout nœud de décision est racine d’un sous-jeu.

1.2 SPE par backward induction

L’équilibre parfait de sous-jeux (Selten 1965) est un profil de stratégie qui forme un équilibre de Nash dans chaque sous-jeu. On le calcule par backward induction : à chaque nœud de décision, le joueur choisit l’action maximisant son paiement sachant que la suite se jouera selon le SPE des sous-jeux plus profonds.

Le SPE élimine les menaces non crédibles : un équilibre de Nash peut reposer sur une action hors-chemin qu’un joueur rationnel ne jouerait jamais si le nœud était atteint. Le SPE, lui, exige la rationalité à tous les nœuds.

// Backward induction : retourne les paiements SPE + le chemin d'actions.
#nullable enable
public static (double[] payoffs, List<(int nodeId, string action)> path) BackwardInduction(GameNode n)
{
    if (n.IsTerminal) return (n.Payoffs!, new List<(int,string)>());
    double[]? best = null;
    int bestIdx = 0;
    for (int i = 0; i < n.Children.Count; i++)
    {
        var (cp, _) = BackwardInduction(n.Children[i]);
        if (best == null || cp[n.Player] > best[n.Player] + 1e-12)
        { best = cp; bestIdx = i; }
    }
    var path = new List<(int,string)> { (n.Id, n.Actions[bestIdx]) };
    var (_, sub) = BackwardInduction(n.Children[bestIdx]);
    path.AddRange(sub);
    return (best!, path);
}

// Enumere tous les sous-jeux (racines = tous les nœuds de decision, info parfaite).
public static List<GameNode> AllDecisionNodes(GameNode n, List<GameNode>? acc = null)
{
    acc ??= new();
    if (!n.IsTerminal) acc.Add(n);
    foreach (var c in n.Children) AllDecisionNodes(c, acc);
    return acc;
}

Show("BackwardInduction + enumeration des sous-jeux definis.");

BackwardInduction + enumeration des sous-jeux definis.

Interprétation : SPE sur le jeu d’entrée (entrant vs incumbent)

Le jeu d’entrée canonique : un entrant décide d’Entrer (In) ou Rester dehors (Out). S’il entre, l’incumbent choisit Accommoder (Acc) ou Combattre (Fight).

• Out → entrant 1, incumbent 2
• In → Acc → entrant 2, incumbent 1
• In → Fight → entrant −1, incumbent −1

L’incumbent a une menace (« je combattrai »), mais au nœud incumbent, Accommoder (1) domine strictement Combattre (−1) : la menace est non crédible.

// Construction de l'arbre du jeu d'entree.
var nOut = new GameNode(3, -1, new double[]{ 1.0, 2.0 });
var nAcc = new GameNode(4, -1, new double[]{ 2.0, 1.0 });
var nFight = new GameNode(5, -1, new double[]{ -1.0, -1.0 });
var incumbent = new GameNode(2, 1);  // joueur 2 (incumbent) decide
incumbent.AddChild("Acc", nAcc).AddChild("Fight", nFight);
var entrant = new GameNode(1, 0);   // joueur 1 (entrant) decide
entrant.AddChild("Out", nOut).AddChild("In", incumbent);

var entryGame = new ExtensiveFormGame(entrant, 2, new[]{ "Entrant", "Incumbent" });

var (spePay, spePath) = BackwardInduction(entryGame.Root);
var subgames = AllDecisionNodes(entryGame.Root);

var sb = new System.Text.StringBuilder();
sb.AppendLine("Jeu d'entree (entrant vs incumbent)");
sb.AppendLine($"  Joueurs : {string.Join(", ", entryGame.PlayerNames)}");
sb.AppendLine($"  Sous-jeux (racines) : {subgames.Count} (nœuds {string.Join(", ", subgames.Select(s=>s.Id))})");
sb.AppendLine();
sb.AppendLine("SPE (backward induction) :");
foreach (var (nid, act) in spePath) sb.AppendLine($"  Nœud {nid} -> {act}");
sb.AppendLine($"  Paiement SPE = ({spePay[0]}, {spePay[1]})  (Entrant, Incumbent)");
sb.AppendLine();
sb.AppendLine("Analyse menace (Fight) : au nœud incumbent (joueur 1),");
sb.AppendLine($"  Acc = {nAcc.Payoffs![1]}, Fight = {nFight.Payoffs![1]}  -> Accommoder domine strictement.");
sb.AppendLine("  => 'Fight' est une menace NON CRÉDIBLE (hors-chemin SPE).");
Show(sb.ToString());

Jeu d'entree (entrant vs incumbent)
  Joueurs : Entrant, Incumbent
  Sous-jeux (racines) : 2 (nœuds 1, 2)

SPE (backward induction) :
  Nœud 1 -> In
  Nœud 2 -> Acc
  Paiement SPE = (2, 1)  (Entrant, Incumbent)

Analyse menace (Fight) : au nœud incumbent (joueur 1),
  Acc = 1, Fight = -1  -> Accommoder domine strictement.
  => 'Fight' est une menace NON CRÉDIBLE (hors-chemin SPE).

Lecture : Le jeu d’entrée (entrant vs incumbent) a un unique SPE (In,Acc) avec paiement (2,1). L’analyse montre que ‘Fight’ est une menace non crédible car Accommodate domine strictement Fight au nœud incumbent (1 > -1), illustrant le principe que les menaces hors-chemin ne sont pas crédibles en induction rétrograde.

Interprétation des résultats

Le SPE est (In, Acc) avec paiement (2, 1). Le profil (Out, Fight) — où l’entrant reste dehors par peur de la menace — est un équilibre de Nash (l’entrant sort car il croit à Fight ; l’incumbent annonce Fight, jamais testé car l’entrant sort). Mais ce n’est pas un SPE : si l’entrant entrait quand même, l’incumbent rationnel accommoderait. C’est le cœur de la distinction Nash vs SPE.

Le nombre de sous-jeux = 2 (nœuds 1 et 2) : la racine et le nœud incumbent.

// Pont vers Gambit (.efg) : valider le SPE avec un solveur externe (lib-vs-lib, #10382).
// Memes vehicule et discipline que GT-4 (.nfg) : Process.Start CLI, PAS de NuGet,
// pour respecter la GPL-2.0 de Gambit. Le pont .efg (forme extensive) est la suite
// naturelle du pont .nfg (forme normale) : il resout le SPE directement sur l'arbre.
using System.Diagnostics;
using System.Globalization;
using System.IO;

// Serialise un ExtensiveFormGame au format .efg (EFG 2, forme extensive Gambit).
// Parcours DFS preorder (l'ordre attendu par le parseur EFG). Information parfaite :
// chaque noeud de decision est son propre ensemble d'information (infoset singleton).
public static string ToEfg(ExtensiveFormGame game)
{
    var sb = new System.Text.StringBuilder();
    sb.Append($"EFG 2 R \"Extensive game\" {{ ");
    for (int p = 0; p < game.NPlayers; p++) sb.Append($"\"{game.PlayerNames[p]}\" ");
    sb.AppendLine("}");
    sb.AppendLine("\"\"");
    sb.AppendLine();
    var isetCount = new int[game.NPlayers + 1];  // infosets par joueur (1-indexe)
    int outcome = 0;
    void Emit(GameNode n)
    {
        if (n.IsTerminal)
        {
            outcome++;
            var pays = n.Payoffs!;
            var payStr = string.Join(", ", pays.Select(v => v.ToString("0.0##############", CultureInfo.InvariantCulture)));
            sb.AppendLine($"t \"\" {outcome} \"o{outcome}\" {{ {payStr} }}");
        }
        else
        {
            int pl = n.Player + 1;  // 0-indexe (GameNode) -> 1-indexe (EFG)
            isetCount[pl]++;
            var acts = string.Join(" ", n.Actions.Select(a => $"\"{a}\""));
            sb.AppendLine($"p \"\" {pl} {isetCount[pl]} \"\" {{ {acts} }} 0");
            foreach (var c in n.Children) Emit(c);
        }
    }
    Emit(game.Root);
    return sb.ToString();
}

// Cherche l'executable Gambit (.efg) : GAMBIT_HOME d'abord, puis installs
// Windows connues (utilisateur local, Program Files), puis emplacements Unix
// (Linux /usr/bin et /usr/local/bin ; macOS homebrew). Sur Unix les binaires
// Gambit n'ont pas de suffixe .exe. Pattern candidats de GT-5, etendu (#10643).
public static string FindGambitEfg(string solver)
{
    bool win = OperatingSystem.IsWindows();
    string exe = win ? solver + ".exe" : solver;
    var candidates = new List<string>();
    var home = Environment.GetEnvironmentVariable("GAMBIT_HOME");
    if (!string.IsNullOrEmpty(home)) candidates.Add(Path.Combine(home, exe));
    if (win)
    {
        candidates.Add(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.LocalApplicationData), "Gambit", "Gambit", exe));
        candidates.Add($@"C:\Program Files (x86)\Gambit\{exe}");
        candidates.Add($@"C:\Program Files\Gambit\{exe}");
    }
    else
    {
        candidates.Add("/usr/bin/" + exe);
        candidates.Add("/usr/local/bin/" + exe);
        candidates.Add("/opt/homebrew/bin/" + exe);
    }
    foreach (var c in candidates)
        if (File.Exists(c)) return c;
    throw new FileNotFoundException(
        $"Binaire Gambit introuvable : {solver}. Cherche (GAMBIT_HOME, installs locales) :\n  - " +
        string.Join("\n  - ", candidates) +
        "\nInstaller Gambit (http://www.gambit-project.org/) ou definir GAMBIT_HOME.");
}

// Invoque un solveur Gambit sur le .efg, retourne les profils (NE behavioral ou strategique).
public static List<double[]> RunGambitEfg(ExtensiveFormGame game, string solver, bool strategic = false)
{
    string exe = FindGambitEfg(solver);
    string tmp = Path.GetTempFileName();
    File.WriteAllText(tmp, ToEfg(game));
    // gambit-enumpure (NE purs, strategies entieres) rejette -d ; -S = forme strategique.
    // - strategic=true            -> " -S"  (conversion vers la forme strategique)
    // - enumpure, strategic=false -> ""     (forme agent : enumeration SUR l'arbre, sans conversion)
    // - lcp, strategic=false      -> " -d 6" (decimales pour les probas comportementales)
    string sFlag = strategic ? " -S" : (solver.Contains("enumpure") ? "" : " -d 6");
    var psi = new ProcessStartInfo
    {
        FileName = exe,
        Arguments = $"-q{sFlag} \"{tmp}\"",
        RedirectStandardOutput = true, RedirectStandardError = true,
        UseShellExecute = false, CreateNoWindow = true,
    };
    using var proc = Process.Start(psi);
    string stdout = proc.StandardOutput.ReadToEnd();
    proc.WaitForExit();
    File.Delete(tmp);
    var result = new List<double[]>();
    foreach (var line in stdout.Split('\n', StringSplitOptions.RemoveEmptyEntries))
        if (line.StartsWith("NE,"))
        {
            var v = line.Substring(3).Split(',')
                .Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray();
            result.Add(v);
        }
    return result;
}

// --- Validation 1 : SPE behavioral (forme extensive, pivotage lcp) ---
var speBehav = RunGambitEfg(entryGame, "gambit-lcp");
$"gambit-lcp (forme extensive, pivotage) : {speBehav.Count} equilibre(s)".Display();
foreach (var eq in speBehav)
    $"  Probas (Out, In, Acc, Fight) = [{string.Join(", ", eq.Select(v => v.ToString("F4", CultureInfo.InvariantCulture)))}]".Display();
// Cross-validation : le backward induction (cellule precedente) a donne SPE = (In, Acc), payoff (2, 1).
string efgVerdict = (speBehav.Count >= 1
    && Math.Abs(speBehav[0][0]) < 1e-3 && Math.Abs(speBehav[0][1] - 1.0) < 1e-3
    && Math.Abs(speBehav[0][2] - 1.0) < 1e-3 && Math.Abs(speBehav[0][3]) < 1e-3)
    ? "OK -- gambit-lcp confirme le SPE (In, Acc) du backward induction"
    : "MISMATCH";
$"Cross-validation vs backward induction : {efgVerdict}".Display();

// --- Prong-B : (Out, Fight) est-il un Nash de l'arbre lui-meme ? ---
// gambit-enumpure SANS -S enumere les NE purs directement en forme agent (comportementale),
// SANS conversion vers la forme strategique. Contre-preuve decisive : si (Out, Fight) y
// apparait, ce n'est pas un artefact de la conversion en matrice -- c'est un Nash de la
// forme extensive elle-meme (le noeud incumbent n'etant jamais atteint, Fight y est une
// meilleure reponse faible).
var neAgent = RunGambitEfg(entryGame, "gambit-enumpure", strategic: false);
$"\ngambit-enumpure (forme agent, SUR l'arbre) : {neAgent.Count} NE purs".Display();
string[] actionLabels = { "Out", "In", "Acc", "Fight" };
foreach (var eq in neAgent)
{
    var played = new List<string>();
    for (int i = 0; i < eq.Length; i++) if (eq[i] > 0.5) played.Add(actionLabels[i]);
    bool isPerfect = played.Contains("In") && played.Contains("Acc");
    string tag = isPerfect ? "  <- SPE (sous-jeu-parfait)" : "  <- Nash NON sous-jeu-parfait (menace non credible hors-chemin)";
    $"  ({string.Join(", ", played)}){tag}".Display();
}

// Meme enumeration apres conversion strategique (-S) : la matrice rend le meme ensemble.
var neStrategic = RunGambitEfg(entryGame, "gambit-enumpure", strategic: true);
$"\ngambit-enumpure -S (forme strategique equivalente) : {neStrategic.Count} NE purs (idem -> la conversion ne fabrique rien)".Display();

// --- Bilan : aucun solveur ne filtre les menaces non credibles ---
// L'ecart 1-vs-2 oppose UN equilibre trouve par pivotage (lcp s'arrete au premier point
// complementaire) a TOUS les equilibres enumeres (enumpure). La forme extensive ne filtre
// rien : (Out, Fight) est un Nash de l'arbre. La perfection en sous-jeux est un raffinement
// qu'on IMPOSE (le backward induction de la cellule precedente), pas un don du solveur.
$"\nBilan : gambit-lcp (pivotage) = {speBehav.Count} eq ; gambit-enumpure (enumeration) = {neAgent.Count} Nash.".Display();
"La perfection en sous-jeux est un raffinement qu'on impose (backward induction), pas un filtrage du solveur.".Display();

gambit-lcp (forme extensive, pivotage) : 1 equilibre(s)

  Probas (Out, In, Acc, Fight) = [0.0000, 1.0000, 1.0000, 0.0000]

Cross-validation vs backward induction : OK -- gambit-lcp confirme le SPE (In, Acc) du backward induction

gambit-enumpure (forme agent, SUR l'arbre) : 2 NE purs

  (In, Acc)  <- SPE (sous-jeu-parfait)

  (Out, Fight)  <- Nash NON sous-jeu-parfait (menace non credible hors-chemin)

gambit-enumpure -S (forme strategique equivalente) : 2 NE purs (idem -> la conversion ne fabrique rien)

Bilan : gambit-lcp (pivotage) = 1 eq ; gambit-enumpure (enumeration) = 2 Nash.

La perfection en sous-jeux est un raffinement qu'on impose (backward induction), pas un filtrage du solveur.

Lecture : La validation croisée avec gambit-lcp confirme le SPE (In,Acc) trouvé par backward induction. Le solveur externe gambit-enumpure identifie deux équilibres de Nash purs : (In,Acc) qui est SPE, et (Out,Fight) qui n’est pas sous-jeu-parfait car il repose sur la menace non crédible ‘Fight’. Ceci illustre que la perfection en sous-jeux est un raffinement plus strict que l’équilibre de Nash.

Pourquoi les deux solveurs ne renvoient pas le même nombre d’équilibres

Les deux solveurs Gambit ci-dessus travaillent sur le même arbre de jeu, mais ne renvoient pas le même ensemble d’équilibres :

• gambit-lcp (sans -S) résout le jeu directement sur la forme extensive (forme séquentielle de Koller–Megiddo–von Stengel) et calcule des équilibres en stratégies comportementales (une probabilité par action à chaque nœud de décision). Il n’en renvoie qu’un seul : l’algorithme de complémentarité linéaire s’arrête au premier point complémentaire atteint par pivotage. Ici (In, Acc) — qui se trouve être le SPE, mais lcp ne l’a pas choisi pour sa perfection.
• gambit-enumpure -S convertit l’arbre en forme stratégique (la matrice des plans d’action contingents) puis énumère tous les équilibres de Nash en stratégies pures : ici 2, dont (Out, Fight).

Le point à retenir : (Out, Fight) est un équilibre de Nash de la forme extensive elle-même, pas un artefact de la conversion vers la forme stratégique. Le nœud de l’incumbent n’étant jamais atteint (l’entrant joue Out), Fight y est une meilleure réponse faible — tout écart est sans conséquence. Et l’entrant obtient 1 avec Out, contre −1 s’il déviait vers In (où l’incumbent accommode). Aucun des deux ne gagne à dévier : c’est un Nash.

Aucun solveur ne filtre les menaces non crédibles : la perfection en sous-jeux est un raffinement qu’on impose — ici par le BackwardInduction de la cellule précédente, qui exige l’optimalité à chaque sous-jeu, y compris celui que (Out, Fight) n’atteint jamais (et où Acc bat Fight). L’écart 1-vs-2 oppose donc un équilibre trouvé par pivotage à tous les équilibres énumérés — non la forme extensive à la forme stratégique.

C’est précisément la leçon de Selten (1965) : l’équilibre de Nash ne suffit pas en présence de menaces hors-chemin ; il faut un raffinement (le SPE) pour les écarter. Le pont .efg le rend mécanique — le solveur externe (Gambit, la référence du domaine pour la théorie des jeux) confirme le verdict du backward induction from-scratch écrit plus haut, et l’option -S rend visibles les Nash non-parfaits que ce backward induction élimine.

Parité lib-vs-lib et axes de pont (#10382) : le pont C# ci-dessus invoque le vrai solveur Gambit (moteur C++) via sa ligne de commande (Process.Start sur gambit-lcp.exe) — l’axe « binaire CLI » de la taxonomie de parité. Gambit expose aussi un binding Python (pygambit) ; un chemin alternatif pour le côté C# serait l’interopérabilité CLR PythonNet → pygambit → Gambit C++ (axe « PythonNet », déjà certifié SOTA-OK ailleurs dans le dépôt). Le choix de la CLI ici suit la même discipline que le pont .nfg de GT-4 : zéro dépendance runtime Python, conformité GPL-2.0 préservée (pas de liaison NuGet vers la bibliothèque), invocation idiomatique de .NET. À noter : le jumeau Python de ce notebook reste from-scratch (il n’invoque pas encore pygambit) — le pont C# ouvre donc le déploiement lib-vs-lib côté .NET, et le Python pourrait suivre la même voie.

2. Menaces et promesses crédibles

2.1 Menace non crédible

On parle de menace non crédible quand un joueur annonce une action punitive qui n’est pas dans son intérêt une fois le nœud atteint. Le SPE l’élimine automatiquement (rationalité à tous les nœuds).

2.2 Rendre une menace crédible

Pour rendre une menace crédible, un joueur peut s’engager (brûler ses ponts, signer un contrat, déléguer à un agent). En modifiant l’arbre (par exemple en retirant l’option Accommoder), la menace devient rationnelle au nœud atteint, donc survit au SPE.

// Rendre la menace credible : l'incumbent s'engage publiquement a Combattre.
// On modifie l'arbre : l'incumbent n'a plus que 'Fight' (Acc retire).
var nAcc2 = new GameNode(4, -1, new double[]{ 2.0, 1.0 });
var nFight2 = new GameNode(5, -1, new double[]{ -1.0, 3.0 });  // Fight desormais rentable (engagement)
var incumbentCommit = new GameNode(2, 1);
incumbentCommit.AddChild("Acc", nAcc2).AddChild("Fight", nFight2);
var entrantCommit = new GameNode(1, 0);
entrantCommit.AddChild("Out", new GameNode(3,-1,new double[]{1.0,2.0}))
            .AddChild("In", incumbentCommit);

var (spe2, path2) = BackwardInduction(entrantCommit);

var sb = new System.Text.StringBuilder();
sb.AppendLine("Variante 'engagement' : Fight rapporte desormais 3 a l'incumbent (engagement credible).");
sb.AppendLine($"  Au nœud incumbent : Acc = {nAcc2.Payoffs![1]}, Fight = {nFight2.Payoffs![1]} -> Fight domine.");
sb.AppendLine("  => Menace rendue credible, le SPE bascule :");
foreach (var (nid, act) in path2) sb.AppendLine($"    Nœud {nid} -> {act}");
sb.AppendLine($"  Paiement SPE = ({spe2[0]}, {spe2[1]})");
sb.AppendLine();
sb.AppendLine("Leçon : changer la structure de paiements (engagement) transforme une menace");
sb.AppendLine("non credible en credible, et modifie l'issue du jeu (l'entrant prefere sortir).");
Show(sb.ToString());

Variante 'engagement' : Fight rapporte desormais 3 a l'incumbent (engagement credible).
  Au nœud incumbent : Acc = 1, Fight = 3 -> Fight domine.
  => Menace rendue credible, le SPE bascule :
    Nœud 1 -> Out
  Paiement SPE = (1, 2)

Leçon : changer la structure de paiements (engagement) transforme une menace
non credible en credible, et modifie l'issue du jeu (l'entrant prefere sortir).

Lecture : En modifiant le paiement de Fight à 3 pour l’incumbent (engagement crédible), Fight domine maintenant Accommodate au nœud incumbent, ce qui fait basculer le SPE vers (Out,Out) avec paiement (1,2). Ceci démontre comment un engagement visible peut rendre une menace crédible et changer l’issue du jeu.

Le paradoxe de l’engagement

Paradoxe : se lier les mains (retirer une option, s’engager à une action coûteuse ex ante) peut augmenter le paiement d’un joueur. C’est le principe de la dissuasion par engagement (Schelling) : la crédibilité d’une menace vient de l’impossibilité de revenir en arrière.

3. Induction avant (Forward Induction)

3.1 Principe

L’induction avant (Cho-Kreps 1987) déduit les intentions d’un joueur de ses actions passées, en supposant qu’il est rationnel : si un joueur renonce à une option sûre pour entrer dans un sous-jeu, il signale qu’il a l’intention de jouer l’équilibre qui justifie ce renoncement.

Contrairement au SPE (qui ne regarde que les sous-jeux en partant de la fin), l’induction avant exploite la logique de signal des actions hors-chemin.

3.2 Exemple : Chasse au Cerf avec option extérieure

• Le joueur 1 choisit d’abord : Out (paiement garanti 3 pour les deux) ou In (entrer dans la Chasse au Cerf).
• Chasse au Cerf : Stag/Stag = (4,4), Stag/Hare = (0,3), Hare/Stag = (3,0), Hare/Hare = (2,2).

Logique d’induction avant : si P1 renonce à Out (3) pour jouer In, la seule façon d’obtenir plus que 3 est de jouer Stag (si P2 joue Stag, on obtient 4 > 3 ; Hare ne donne que 2 < 3). P2, voyant que P1 a renoncé à Out, infère que P1 jouera Stag → P2 joue Stag → (Stag, Stag).

Cet équilibre n’est pas sélectionné par le seul SPE (qui admet aussi (Hare, Hare) dans le sous-jeu).

// Forward induction sur Stag Hunt + option exterieure (Cho-Kreps).
// Matrice du sous-jeu Stag Hunt (lignes = P1, colonnes = P2) : [Stag, Hare]
double[,] stagHunt = {
    { 4.0, 0.0 },   // P1 Stag : (vs Stag=4, vs Hare=0)
    { 3.0, 2.0 }    // P1 Hare : (vs Stag=3, vs Hare=2)
};
// P2 (colonne) paiements :
double[,] stagHuntP2 = {
    { 4.0, 3.0 },   // P2 vs P1=Stag : (Stag=4, Hare=3)
    { 0.0, 2.0 }    // P2 vs P1=Hare : (Stag=0, Hare=2)
};
string[] actions = { "Stag", "Hare" };
double outPayoff = 3.0;  // option exterieure garantie

// Equilibres de Nash du sous-jeu (strategies pures) : identifier les best-responses croises.
var bestP1 = new List<int>();   // meilleure reponse de P1 a chaque action de P2
var bestP2 = new List<int>();
for (int j = 0; j < 2; j++)
{
    int bi = 0;
    for (int i = 1; i < 2; i++) if (stagHunt[i, j] > stagHunt[bi, j]) bi = i;
    bestP1.Add(bi);
}
for (int i = 0; i < 2; i++)
{
    int bj = 0;
    for (int j = 1; j < 2; j++) if (stagHuntP2[i, j] > stagHuntP2[i, bj]) bj = j;
    bestP2.Add(bj);
}
var nashPure = new List<(int i, int j)>();
for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
        if (bestP1[j] == i && bestP2[i] == j)
            nashPure.Add((i, j));

var sb = new System.Text.StringBuilder();
sb.AppendLine("Stag Hunt + option exterieure (Out = 3)");
sb.AppendLine("Equilibres de Nash purs du sous-jeu Stag Hunt :");
foreach (var (i, j) in nashPure)
    sb.AppendLine($"  ({actions[i]}, {actions[j]}) -> paiement ({stagHunt[i,j]}, {stagHuntP2[i,j]})");
sb.AppendLine();
sb.AppendLine("Induction avant (Cho-Kreps) :");
sb.AppendLine($"  P1 renonce a Out ({outPayoff}) pour jouer In.");
sb.AppendLine($"  - Si P1 comptait jouer Hare, son paiement max serait {Math.Max(stagHunt[1,0], stagHunt[1,1])} (= {outPayoff} de Out), pas strictement superieur -> renoncer a Out pour Hare n'est jamais rentable.");
double stagBest = Math.Max(stagHunt[0,0], stagHunt[0,1]);  // P1 Stag vs best of P2
sb.AppendLine($"  - Seul Stag peut justifier le renoncement (paiement max Stag = {stagBest}, et {stagHunt[0,0]} > {outPayoff} si P2 joue Stag).");
sb.AppendLine($"  => P2 infere P1 = Stag -> P2 joue Stag (best response a Stag = {actions[bestP2[0]]}).");
sb.AppendLine($"  => Forward induction selectionne (Stag, Stag) = ({stagHunt[0,0]}, {stagHuntP2[0,0]}).");
sb.AppendLine();
sb.AppendLine("Comparaison : SPE admet (Stag,Stag) ET (Hare,Hare) comme sous-jeu-NE ;");
sb.AppendLine("forward induction selectionne (Stag,Stag) en exploitant le signal du renoncement a Out.");
Show(sb.ToString());

Stag Hunt + option exterieure (Out = 3)
Equilibres de Nash purs du sous-jeu Stag Hunt :
  (Stag, Stag) -> paiement (4, 4)
  (Hare, Hare) -> paiement (2, 2)

Induction avant (Cho-Kreps) :
  P1 renonce a Out (3) pour jouer In.
  - Si P1 comptait jouer Hare, son paiement max serait 3 (= 3 de Out), pas strictement superieur -> renoncer a Out pour Hare n'est jamais rentable.
  - Seul Stag peut justifier le renoncement (paiement max Stag = 4, et 4 > 3 si P2 joue Stag).
  => P2 infere P1 = Stag -> P2 joue Stag (best response a Stag = Stag).
  => Forward induction selectionne (Stag, Stag) = (4, 4).

Comparaison : SPE admet (Stag,Stag) ET (Hare,Hare) comme sous-jeu-NE ;
forward induction selectionne (Stag,Stag) en exploitant le signal du renoncement a Out.

Lecture : L’induction avant de Cho-Kreps (1987) repose sur l’idée que les croyances hors-chemin doivent être fondées. Dans Stag Hunt avec option extérieure, seul Stag peut justifier le renoncement à Out car son paiement maximal (4) dépasse le seuil de 3, tandis que Hare ne peut justifier ce renoncement (paiement maximal 2 < 3), ce qui élimine l’équilibre (Hare,Hare).

Pourquoi l’induction avant est puissante

L’induction avant sélectionne parmi plusieurs SPE celui cohérent avec la rationalité passée. Elle capture l’idée que les actions communiquent : renoncer à une option sûre est un acte de signal. C’est la base des jeux de signal (Spence) et du raffinement des équilibres en information incomplète.

4. Perfection en mains tremblantes (Trembling-hand perfection)

4.1 Motivation

Le SPE exige la rationalité à tous les nœuds, mais un nœud hors-chemin n’est jamais atteint : on peut y mettre n’importe quelle action. La perfection en mains tremblantes (Selten 1975) exige que l’équilibre soit robuste à de petites erreurs (tremblements) : chaque joueur joue chaque action avec une probabilité ε > 0, et l’équilibre est la limite quand ε → 0.

4.2 Définition

Un profil est trembling-hand parfait s’il est la limite d’une suite d’équilibres ε-perturbés où toutes les actions sont jouées avec probabilité positive.

4.3 Conséquences

La perfection élimine les équilibres qui nécessitent qu’un joueur soit certain qu’un nœud hors-chemin ne sera jamais atteint.

// Trembling-hand : on perturbe le jeu d'entree par epsilon (l'entrant peut 'trembler').
// Entrant joue In avec (1-eps), Out avec eps. Au nœud incumbent, on calcule le paiement
// esperé de Acc vs Fight, pour verifier la robustesse du SPE sous tremblement.
double eps = 0.10;   // 10% de tremblement
// Au nœud incumbent (atteint avec proba 1-eps), les paiements Acc/Fight sont inchanges
// (le tremblement est sur le choix de l'entrant, pas sur l'incumbent).
double accIncumbent = 1.0;     // paiement si Accommodate
double fightIncumbent = -1.0;  // paiement si Fight
bool accDominates = accIncumbent > fightIncumbent;

// Esperance pour l'entrant sous (In->Acc) avec tremblement Out :
double entrantInAcc = (1 - eps) * 2.0 + eps * 1.0;   // In(2) w.p. 1-eps, Out(1) w.p. eps
double entrantOut = 1.0;
bool inPreferred = entrantInAcc > entrantOut;

var sb = new System.Text.StringBuilder();
sb.AppendLine($"Trembling-hand perfection (eps = {eps}) sur le jeu d'entree");
sb.AppendLine($"  Au nœud incumbent : Acc = {accIncumbent}, Fight = {fightIncumbent}");
sb.AppendLine($"    -> Accommodate domine : {accDominates} (robuste sous tremblement, le dominant reste dominant).");
sb.AppendLine($"  Esperance entrant (In->Acc) avec tremblement Out = {entrantInAcc:F3}");
sb.AppendLine($"    vs Out pur = {entrantOut}  -> In preferable : {inPreferred}");
sb.AppendLine();
sb.AppendLine("Verdict : le SPE (In, Acc) est trembling-hand parfait. Meme avec 10% de chance");
sb.AppendLine("de 'trembler' vers Out, Accommodate reste strictement dominant pour l'incumbent,");
sb.AppendLine("et In reste preferable pour l'entrant. L'equilibre ne s'appuie sur aucune certitude");
sb.AppendLine("qu'un nœud hors-chemin serait evite.");
Show(sb.ToString());

Trembling-hand perfection (eps = 0,1) sur le jeu d'entree
  Au nœud incumbent : Acc = 1, Fight = -1
    -> Accommodate domine : True (robuste sous tremblement, le dominant reste dominant).
  Esperance entrant (In->Acc) avec tremblement Out = 1,900
    vs Out pur = 1  -> In preferable : True

Verdict : le SPE (In, Acc) est trembling-hand parfait. Meme avec 10% de chance
de 'trembler' vers Out, Accommodate reste strictement dominant pour l'incumbent,
et In reste preferable pour l'entrant. L'equilibre ne s'appuie sur aucune certitude
qu'un nœud hors-chemin serait evite.

Interprétation des résultats numériques

La perfection en mains tremblantes confirme le SPE (In, Acc) : parce que Accommodate domine strictement Fight, aucun tremblement ne renverse la préférence de l’incumbent. À l’inverse, un équilibre qui s’appuierait sur une indifférence ou une menace non crédible serait éliminé par le tremblement (l’erreur infime renverse le calcul).

La lecture de la sortie le confirme des deux côtés : avec ε = 0.1 de tremblement vers Out, In reste préférable pour l’entrant (espérance 1,900 contre 1 pour Out pur), et côté incumbent Acc = 1 domine Fight = -1.

5. Application : le jeu du « Burn Money »

Le burn money (brûler de l’argent) est un mécanisme de signal par coût auto-infligé : un joueur peut, avant un jeu simultané, brûler un montant c. Brûler est coûteux mais signe la force (seul un joueur comptant jouer l’action agressive a intérêt à brûler, car le gain futur compense le coût).

C’est une illustration directe de l’induction avant : l’action de brûler, bien que coûteuse, communique l’intention et modifie l’équilibre sélectionné.

// Burn money : modele simplifie en deux etapes.
// Etape 1 : P1 choisit Burn (cout c) ou Not.
// Etape 2 : jeu de coordination (Battle of Sexes simplifie).
//   P1 signale sa 'force' : si Burn, P2 infere que P1 jouera l'action preferee de P1.
// Matrice BoS : [Opera, Football] -- P1 prefere Opera, P2 prefere Football.
double[,] bosP1 = { { 3.0, 0.0 }, { 0.0, 2.0 } };  // P1 (Opera, Football) vs P2 (Opera, Football)
double[,] bosP2 = { { 2.0, 0.0 }, { 0.0, 3.0 } };
double c = 1.0;   // cout du burn

// Deux equilibres purs du BoS : (Opera, Opera)=(3,2), (Football, Football)=(2,3).
// Sans burn : coordination ambigue (deux equilibres).
// Avec burn : P1 'achete' la credibilite d'Opera (3 - c = 2 >= 2 de Football).
double p1OperaBurn = bosP1[0,0] - c;    // 3 - 1 = 2
double p1FootballNoBurn = bosP1[1,1];   // 2
bool burnProfitable = p1OperaBurn >= p1FootballNoBurn;

var sb = new System.Text.StringBuilder();
sb.AppendLine("Burn Money (signal par cout auto-inflige)");
sb.AppendLine($"  BoS : (Opera,Opera)=({bosP1[0,0]},{bosP2[0,0]}), (Football,Football)=({bosP1[1,1]},{bosP2[1,1]})");
sb.AppendLine($"  Cout du burn c = {c}");
sb.AppendLine($"  P1 : Opera+Burn = {p1OperaBurn} (>= Football sans burn = {p1FootballNoBurn}) -> burn rentable : {burnProfitable}");
sb.AppendLine();
sb.AppendLine("Logique d'induction avant appliquee :");
sb.AppendLine("  Si P1 brule c, il signale qu'il jouera Opera (sinon bruler serait pur gaspillage).");
sb.AppendLine("  P2, voyant le burn, infere P1=Opera -> P2 joue Opera (son 2e meilleur, mais coherent).");
sb.AppendLine($"  => Selection de l'equilibre (Opera, Opera) = ({bosP1[0,0]}, {bosP2[0,0]}), P1 payant le cout.");
sb.AppendLine();
sb.AppendLine("Condition de credibilite du signal : le cout c doit etre tel que bruler n'est");
sb.AppendLine("rentable QUE si P1 compte jouer l'action signalee (condition de separabilite).");
Show(sb.ToString());

Burn Money (signal par cout auto-inflige)
  BoS : (Opera,Opera)=(3,2), (Football,Football)=(2,3)
  Cout du burn c = 1
  P1 : Opera+Burn = 2 (>= Football sans burn = 2) -> burn rentable : True

Logique d'induction avant appliquee :
  Si P1 brule c, il signale qu'il jouera Opera (sinon bruler serait pur gaspillage).
  P2, voyant le burn, infere P1=Opera -> P2 joue Opera (son 2e meilleur, mais coherent).
  => Selection de l'equilibre (Opera, Opera) = (3, 2), P1 payant le cout.

Condition de credibilite du signal : le cout c doit etre tel que bruler n'est
rentable QUE si P1 compte jouer l'action signalee (condition de separabilite).

Le paradoxe du « Burn Money »

Le burn money semble irrationnel (détruire de la valeur), mais il modifie l’équilibre sélectionné en faveur du joueur qui brûle. C’est une illustration frappante du pouvoir de l’engagement coûteux : un signal crédible doit être coûteux à imiter (principe de Spence).

6. Comparaison des raffinements

Les raffinements d’équilibre forment une hiérarchie : chaque raffinement elimine strictement plus d’équilibres que le précédent.

Raffinement	Idée	Élimine
Nash	Aucun n’a intérêt à dévier unilatéralement	(référence, le plus permissif)
SPE	Nash dans chaque sous-jeu (backward induction)	menaces non crédibles
Trembling-hand	Robuste à de petites erreurs (ε)	équilibres fragiles à un nœud hors-chemin
Forward induction	Actions passées = signaux d’intention	SPE incohérents avec la rationalité passée

// Synthese : hierarchie des raffinements sur nos exemples.
var sb = new System.Text.StringBuilder();
sb.AppendLine("Hierarchie des raffinements (du plus permissif au plus exigeant)");
sb.AppendLine(new string('-', 60));
sb.AppendLine($"{"Raffinement",-22}{"Jeu d'entree",-20}{"Stag Hunt+Out",-18}");
sb.AppendLine(new string('-', 60));
sb.AppendLine($"{"Nash",-22}{"(In,Acc),(Out,F)",-20}{"3 eq. (Stag,Hare,mix)",-18}");
sb.AppendLine($"{"SPE",-22}{"(In,Acc) seul",-20}{"(Stag,Stag),(Hare,Hare)",-18}");
sb.AppendLine($"{"Trembling-hand",-22}{"(In,Acc) robuste",-20}{"elimine mixte",-18}");
sb.AppendLine($"{"Forward induction",-22}{"(In,Acc)",-20}{"(Stag,Stag) seul",-18}");
sb.AppendLine(new string('-', 60));
sb.AppendLine();
sb.AppendLine("Chaque raffinement est un SUR-ENSEMBLE d'exigences :");
sb.AppendLine("  Nash subset SPE subset Trembling-hand subset Forward-induction-coherent.");
sb.AppendLine("Plus on raffine, plus on 'selecte' parmi les equilibres de Nash.");
Show(sb.ToString());

Hierarchie des raffinements (du plus permissif au plus exigeant)
------------------------------------------------------------
Raffinement           Jeu d'entree        Stag Hunt+Out     
------------------------------------------------------------
Nash                  (In,Acc),(Out,F)    3 eq. (Stag,Hare,mix)
SPE                   (In,Acc) seul       (Stag,Stag),(Hare,Hare)
Trembling-hand        (In,Acc) robuste    elimine mixte     
Forward induction     (In,Acc)            (Stag,Stag) seul  
------------------------------------------------------------

Chaque raffinement est un SUR-ENSEMBLE d'exigences :
  Nash subset SPE subset Trembling-hand subset Forward-induction-coherent.
Plus on raffine, plus on 'selecte' parmi les equilibres de Nash.

Interprétation du tableau comparatif

• Sur le jeu d’entrée, Nash admet (Out, Fight) (menace non crédible) ; SPE et au-delà l’éliminent.
• Sur Stag Hunt + Out, le SPE admet deux équilibres purs ; l’induction avant en sélectionne un seul (Stag, Stag).
• Le trembling-hand perfection est plus exigeant que le SPE : il élimine les équilibres mixtes qu’aucun tremblement ne soutient.

Aucun raffinement n’est « universellement le bon » : le choix dépend du contexte (erreurs réelles → trembling-hand ; signaux → forward induction). Ces raffinements sélectionnent des équilibres plus raisonnables en excluant les menaces non crédibles et les croyances non fondées.

7. Exercices

Les exercices ci-dessous sont des stubs à compléter. Ils utilisent pass/return null (jamais throw) : le notebook s’exécute de bout en bout même non complété (règle C.1).

Exercice 1 — Beer-Quiche Game

Le jeu Beer-Quiche (Cho-Kreps 1987) : un joueur de type Fort ou Faible choisit de manger Bière ou Quiche ; l’autre joueur observe le choix (pas le type) et décide Combattre ou Ne pas combattre. Implémenter l’arbre et identifier l’équilibre de signal.

// Exercice 1 — Beer-Quiche (a completer).
#nullable enable
// TODO etudiant : construire l'arbre (nature choisit type Fort/Naible, P1 choisit Beer/Quiche,
// P2 observe l'action puis choisit Fight/NotFight) et identifier l'equilibre separateur vs melange.
// Indice : l'equilibre pooling (les deux types jouent Beer) survit si P2 croit "Fort" voyant Beer.
// Etape 1 : definir les nœuds et paiements.
// Etape 2 : appliquer BackwardInduction sur chaque sous-jeu d'information (ici, hors scope info imparfaite).
Console.WriteLine("Exercice 1 (Beer-Quiche) a completer.");

Exercice 1 (Beer-Quiche) a completer.

Exercice 2 — Négociation avec options extérieures

Deux joueurs négocient (jeu séquentiel type Rubinstein) avec des options extérieures. Montrer comment une option extérieure crédible améliore le paiement d’un joueur.

// Exercice 2 — Negociation avec options exterieures (a completer).
#nullable enable
// TODO etudiant : modeliser un jeu de negotiation a 2 tours avec options exterieures.
// Indice : l'option exterieure borne le paiement minimum (outside option principle).
// Etape 1 : construire l'arbre a 2 tours. Etape 2 : backward induction.
Console.WriteLine("Exercice 2 (Negociation) a completer.");

Exercice 2 (Negociation) a completer.

Exercice 3 — Engagement séquentiel

Un joueur peut s’engager séquentiellement (capacité de production, R&D) avant un jeu de marché. Implémenter l’arbre et mesurer la valeur de l’engagement.

// Exercice 3 — Engagement sequentiel (a completer).
#nullable enable
// TODO etudiant : arbre a deux etages (engagement puis competition Cournot/Stackelberg).
// Indice : Stackelberg = engagement de capacite, le leader gagne plus qu'en Cournot simultane.
Console.WriteLine("Exercice 3 (Engagement) a completer.");

Exercice 3 (Engagement) a completer.

Exercice 4 — Jeu d’entrée avec signal de prix

Un entrant signale sa qualité par un prix d’introduction bas (limit pricing). Implémenter la logique de signal.

// Exercice 4 — Signal de prix (a completer).
#nullable enable
// TODO etudiant : modele de signal (qualite haute/basse) avec cout du signal croise.
// Indice : signal credible = cout plus faible pour haute qualite que pour basse (condition de Spence).
Console.WriteLine("Exercice 4 (Signal prix) a completer.");

Exercice 4 (Signal prix) a completer.

Exercice 5 — Identification des SPE

Étant donné un arbre de jeu (fourni), énumérer tous les SPE (pas seulement celui de backward induction pur — gérer les égalités).

// Exercice 5 — Tous les SPE (a completer).
#nullable enable
// TODO etudiant : etendre BackwardInduction pour enumerer TOUS les SPE (en cas d'egalite de paiement),
// en retournant l'ensemble des profils optimaux a chaque nœud.
// Indice : au lieu d'un argmax unique, collecter tous les argmax a chaque nœud puis faire le produit cartesien.
Console.WriteLine("Exercice 5 (Tous les SPE) a completer.");

Exercice 5 (Tous les SPE) a completer.

8. Résumé

Points clés

• SPE (backward induction) = équilibre de Nash dans chaque sous-jeu ; élimine les menaces non crédibles.
• Menace crédible = action punitive rationnelle au nœud atteint ; on peut la créer par engagement (changer l’arbre).
• Trembling-hand perfection = robustesse aux petites erreurs (ε).
• Forward induction = les actions passées signalent les intentions (logique Cho-Kreps).
• Burn money = signal coûteux auto-infligé ; modifie l’équilibre sélectionné.

Hiérarchie

Nash ⊂ SPE ⊂ Trembling-hand ⊂ Forward-induction-coherent — chaque raffinement sélectionne strictement moins d’équilibres.

Prochaine étape

• GameTheory-11 (Bayésien) : information incomplète.
• GameTheory-12 (Réputation) : jeux répétés et signal.

---

Twin C# .NET Interactive du notebook Python GameTheory-10-ForwardInduction-SPE-Python.ipynb. Implémentation from-scratch (BCL .NET 9, 0 NuGet) — marathon #4956, registre SOTA #3801.