GameTheory-09-BackwardInduction-Python (C#)

Induction arriere et equilibre de sous-jeu parfait (SPE)

Twin C# du notebook GameTheory-09-BackwardInduction-Python (Python + numpy/matplotlib). Marathon parite .NET ⇄ Python (#4956), suite de GameTheory-11-BayesianGames-CSharp. BCL .NET seule, 0 NuGet, from-scratch (Prong B #3801 : comprendre l’algorithme récursif, pas invoquer numpy).

Objectifs

• Modeliser un jeu sous forme extensive (arbre de jeu) en C#
• Implementer l’induction arriere (backward induction) pour resoudre un jeu a information parfaite
• Illustrer les paradoxes classiques : jeu du mille-pattes (centipede), guerre d’usure (war of attrition), chaîne de magasins (chain store)
• Demontrer la notion d’equilibre de sous-jeu parfait (Subgame Perfect Equilibrium, Selten 1965)

Duree estimee : 40 minutes

Plan de route : le notebook construit l’induction arrière from-scratch en C# pur (zéro NuGet — c’est l’algorithme qui est la leçon), puis l’applique aux quatre paradoxes canoniques de Selten. Chaque étape a sa sortie committée : l’Entry Game où la menace de Fight n’est pas crédible (équilibre [1.00, 1.00]), le jeu du mille-pattes à 6 tours qui se déroule entièrement (SPE [1.00, 0.00] contre une coopération à (6, 6)), la table d’efficacité où le ratio perte/coopération croît linéairement (2.0x à 10.0x), la guerre d’usure qui s’arrête au premier tour ([9.00, -0.00]), et le paradoxe de la chaîne de magasins où le monopole cède 3 fois sur 3. Trois exercices closent le parcours (bargaining alterné, ultimatum, Take-Away).

1. Structure de données : arbre de jeu

Un jeu sous forme extensive est un arbre ou : - Chaque noeud appartient a un joueur (ou est terminal, ou est un noeud de chance) - Chaque arete est une action - Les feuilles portent les gains (payoffs) de chaque joueur

On represente cela par deux classes simples : GameNode et ExtensiveFormGame.

Lecture du modèle committé : la sortie confirme Classes definies : GameNode (noeud), ExtensiveFormGame (arbre de jeu). Trois choix de conception à noter avant d’aller plus loin. D’abord l’encodage du joueur : Player = -1 pour un nœud terminal (feuille porteuse des payoffs), 0 pour le joueur 1, >= 1 pour les suivants — simple et extensible à N joueurs. Ensuite Children comme dictionnaire action→nœud (pas une liste) : le nom de l’action (Take, Pass, Fight) fait partie de la structure, ce qui permet à la visualisation ASCII de la section 8 d’afficher les branches étiquetées. Enfin Payoffs ne vaut non-null qu’aux feuilles — la sémantique extensive-form est respectée : les payoffs appartiennent aux issues, pas aux décisions.

using System.Globalization;

// Helper format invariant (Bug marathon #2 : CurrentCulture ne persiste pas entre cells)
static string FI(double x, string fmt = "F2") => x.ToString(fmt, CultureInfo.InvariantCulture);
static string FV(double[] v, string fmt = "F2") => "[" + string.Join(", ", v.Select(x => FI(x, fmt))) + "]";

// Noeud d'un arbre de jeu. player = -1 (terminal), 0 (nature/chance), >= 1 (joueur).
public class GameNode
{
    public string NodeId;
    public int Player;
    public List<string> Actions = new();
    public Dictionary<string, GameNode> Children = new();
    public double[] Payoffs { get; set; }       // non-null uniquement si terminal
    public string Infoset { get; set; }         // ensemble d'information (optionnel)

    public bool IsTerminal() => Player == -1;
    public bool IsChance() => Player == 0;

    public GameNode(string id, int player)
    {
        NodeId = id;
        Player = player;
    }
}

// Jeu sous forme extensive.
public class ExtensiveFormGame
{
    public string Name;
    public int NumPlayers;
    public GameNode Root;
    public Dictionary<string, GameNode> Nodes = new();

    public ExtensiveFormGame(string name, int numPlayers)
    {
        Name = name;
        NumPlayers = numPlayers;
    }

    public void AddNode(GameNode node) { Nodes[node.NodeId] = node; }
    public void SetRoot(GameNode node) { Root = node; AddNode(node); }
}

display("Classes definies : GameNode (noeud), ExtensiveFormGame (arbre de jeu)");

The below script needs to be able to find the current output cell; this is an easy method to get it.

Classes definies : GameNode (noeud), ExtensiveFormGame (arbre de jeu)

2. Algorithme d’induction arriere

Principe (Zermelo 1913, formalise par Selten 1965) : on resout le jeu en partant des feuilles et en remontant vers la racine.

• Noeud terminal : retourner les gains.
• Noeud de chance (nature) : retourner l’esperance ponderee des gains des enfants.
• Noeud de decision (joueur p) : le joueur choisit l’action qui maximise son propre gain ; on enregistre cette action optimale.

Cet algorithme produit un equilibre de sous-jeu parfait (SPE) : la stratégie est rationnelle dans chaque sous-jeu, même hors du chemin d’equilibre. C’est plus fort que l’equilibre de Nash (qui peut reposer sur des menaces non credibles).

L’algorithme en trois cas, lus sur le code : la récursion Solve(node) distingue exactement trois situations par le marqueur Player. (1) Terminal (Player == -1, test IsTerminal()) : base de la récursion, on retourne les payoffs tels quels. (2) Nature/chance (Player == 0, test IsChance()) : espérance sur les fils — poids uniforme 1/n par action de nature, chaque payoff d’équilibre du fils contribue pondéré. Ce cas est implémenté mais jamais exercé par les quatre jeux du notebook, tous déterministes : il rend l’algorithme générique (jeux mixtes avec coup de chance, loteries). (3) Décision (Player >= 1) : pour chaque action, la valeur d’induction du sous-arbre fils ; le joueur du nœud (childPayoffs[player - 1] — joueurs 1-indexés, tableau 0-indexé) retient son maximum strict. Aucun lookahead global : chaque nœud ne voit que ses fils, la complexité est linéaire en la taille de l’arbre. La solution mémorisée dans Dictionary<string, NodeSolution> donne l’action optimale par nœud — c’est ce qui permet d’afficher ensuite la stratégie complète, pas seulement les payoffs.

// Resultat d'induction arriere pour un noeud de decision.
public class NodeSolution
{
    public string OptimalAction;
    public double[] EquilibriumPayoffs;
}

// Induction arriere : resout le jeu par recursion depuis la racine.
// Retourne : (solution par noeud de decision, gains d'equilibre globaux).
public static (Dictionary<string, NodeSolution> solution, double[] eqPayoffs) BackwardInduction(ExtensiveFormGame game)
{
    var solution = new Dictionary<string, NodeSolution>();

    double[] Solve(GameNode node)
    {
        if (node.IsTerminal())
            return node.Payoffs;

        if (node.IsChance())
        {
            // Esperance sur les resultats de nature (payoffs egaux a 1/n ici, mais generique)
            var expected = new double[game.NumPlayers];
            double total = 0.0;
            foreach (var kv in node.Children)
            {
                double w = node.Actions.Contains(kv.Key) ? 1.0 / node.Children.Count : 0.0;
                var cp = Solve(kv.Value);
                for (int i = 0; i < game.NumPlayers; i++) expected[i] += w * cp[i];
                total += w;
            }
            return expected;
        }

        // Noeud de decision : le joueur 'node.Player' maximise son propre gain.
        int player = node.Player;
        string bestAction = null;
        double[] bestPayoffs = null;
        double bestValue = double.NegativeInfinity;

        foreach (var action in node.Actions)
        {
            var childPayoffs = Solve(node.Children[action]);
            double playerValue = childPayoffs[player - 1];  // joueurs 1-indexes, tableau 0-indexe
            if (playerValue > bestValue)
            {
                bestValue = playerValue;
                bestAction = action;
                bestPayoffs = childPayoffs;
            }
        }

        solution[node.NodeId] = new NodeSolution { OptimalAction = bestAction, EquilibriumPayoffs = bestPayoffs };
        return bestPayoffs;
    }

    var eq = Solve(game.Root);
    return (solution, eq);
}

// Affiche la solution d'induction arriere.
public static void DisplayBackwardInduction(ExtensiveFormGame game, Dictionary<string, NodeSolution> solution)
{
    var sb = new StringBuilder();
    sb.AppendLine("Solution par induction arriere : " + game.Name);
    sb.AppendLine(new string('=', 60));
    foreach (var kv in solution)
    {
        var node = game.Nodes[kv.Key];
        var sol = kv.Value;
        sb.AppendLine("  Noeud " + kv.Key + " (J" + node.Player + "): joue '" + sol.OptimalAction + "' -> " + FV(sol.EquilibriumPayoffs));
    }
    display(sb.ToString());
}

display("Fonction BackwardInduction definie");

Fonction BackwardInduction definie

3. Jeu d’entree sur le marche

Un entrant (J1) decide d’entrer (Enter) ou de rester hors du marche (Out). S’il entre, l’incumbent (J2, monopole en place) choisit entre Fight (guerre des prix) et Accommodate (accepter).

Issue	Entrant	Incumbent
Out	0	2
Enter puis Fight	-1	-1
Enter puis Accommodate	1	1

Intuition : la menace “Fight” est-elle credible ?

Prédisez avant d’exécuter : à l’entrée du jeu, l’entrant choisit entre Out (payoffs [0.00, 2.00] — statu quo favorable à l’incumbent) et Enter. S’il entre, l’incumbent choisit Fight ([-1.00, -1.00]) ou Accommodate ([1.00, 1.00]). La menace de guerre est-elle crédible ? Réfléchissez au moment où l’entrant est déjà entré : l’incumbent compare -1 (Fight) à +1 (Accommodate) — un incumbent rationnel cède. L’entrant, anticipant cette cédation, entre. La sortie committée confirme : décision incumbent Accommodate, entrée Enter, équilibre [1.00, 1.00]. C’est l’exemple minimal de la différence Nash vs SPE : le profil (Out, Fight-si-entrée) est un équilibre de Nash (l’entrant n’a pas intérêt à entrer face à la menace), mais la menace n’est pas crédible — l’induction arrière l’élimine.

// Construction du jeu d'entree.
public static ExtensiveFormGame CreateEntryGame()
{
    var game = new ExtensiveFormGame("Entry Game", 2);

    var outT = new GameNode("out", -1); outT.Payoffs = new double[]{0, 2};
    var fightT = new GameNode("fight", -1); fightT.Payoffs = new double[]{-1, -1};
    var accT = new GameNode("accommodate", -1); accT.Payoffs = new double[]{1, 1};

    var incumbent = new GameNode("incumbent", 2);
    incumbent.Actions = new List<string>{"Fight", "Accommodate"};
    incumbent.Children["Fight"] = fightT;
    incumbent.Children["Accommodate"] = accT;
    incumbent.Infoset = "I2";

    var entrant = new GameNode("entrant", 1);
    entrant.Actions = new List<string>{"Enter", "Out"};
    entrant.Children["Enter"] = incumbent;
    entrant.Children["Out"] = outT;
    entrant.Infoset = "I1";

    game.SetRoot(entrant);
    game.AddNode(incumbent); game.AddNode(outT); game.AddNode(fightT); game.AddNode(accT);
    return game;
}

var entryGame = CreateEntryGame();
var (entrySolution, entryEq) = BackwardInduction(entryGame);
DisplayBackwardInduction(entryGame, entrySolution);
display("Gains a l'equilibre : " + FV(entryEq));
display("Interpretation :");
display("  - Si l'Entrant entre, l'Incumbent prefere Accommoder (1 > -1)");
display("  - Sachant cela, l'Entrant prefere Entrer (1 > 0)");
display("  -> La menace 'Fight' n'est PAS credible (non-SPE). L'entree se produit.");

Solution par induction arriere : Entry Game
============================================================
  Noeud incumbent (J2): joue 'Accommodate' -> [1.00, 1.00]
  Noeud entrant (J1): joue 'Enter' -> [1.00, 1.00]

Gains a l'equilibre : [1.00, 1.00]

Interpretation :

  - Si l'Entrant entre, l'Incumbent prefere Accommoder (1 > -1)

  - Sachant cela, l'Entrant prefere Entrer (1 > 0)

  -> La menace 'Fight' n'est PAS credible (non-SPE). L'entree se produit.

4. Le paradoxe du mille-pattes (Centipede)

Deux joueurs passent ou prennent a tour de rôle. La cagnotte grossit a chaque tour. Si un joueur prend (Take), il empoche la grosse part et l’autre la petite. Si tout le monde passe jusqu’au bout, gain egal.

Paradoxe : l’induction arriere dit “Take des le premier tour”, mais empiriquement les humains cooperent longtemps. C’est le conflit classique entre rationalite backward et intuition forward.

Le déroulement complet, chiffre par chiffre : la sortie committée affiche la chaîne node_5 -> node_4 -> node_3 -> node_2 -> node_1 -> node_0 avec Take à chaque nœud, et l’équilibre final [1.00, 0.00]. Reconstruisez la remontée : à node_5 (dernier nœud, joueur 2), Take rapporte [4.00, 6.00] — le gros tas (t+1 = 6) va au preneur. À node_4 (joueur 1), Take donne [5.00, 3.00] contre 4 en passant (continuation [4, 6]) — Take. À node_3 (joueur 2), Take [2, 4] contre 3 en passant — Take. À node_2 (joueur 1), Take [3, 1] contre 2 — Take. À node_1 (joueur 2), Take [0, 2] contre 1 — Take. À node_0 (joueur 1), Take [1, 0] contre 0 — Take. Chaque preneur gagne strictement à prendre maintenant plutôt qu’à laisser grandir le tas : c’est le mécanisme exact du déroulement, et la raison pour laquelle la coopération (6, 6) — passer à chaque tour — n’est jamais un équilibre.

// Construction du jeu du mille-pattes a n_rounds tours.
public static ExtensiveFormGame CreateCentipedeGame(int nRounds = 6)
{
    var game = new ExtensiveFormGame("Centipede (" + nRounds + " tours)", 2);

    // Gains si "Take" au tour t (player qui prend = grosse cagnotte).
    double[] PayoffsAtRound(int t)
    {
        double bigPile = t + 1;
        double smallPile = Math.Max(0, t - 1);
        int player = (t % 2 == 0) ? 1 : 2;
        return (player == 1) ? new double[]{bigPile, smallPile} : new double[]{smallPile, bigPile};
    }

    // Dernier terminal (si tous passent jusqu'au bout).
    var lastPass = new GameNode("end", -1);
    lastPass.Payoffs = new double[]{nRounds, nRounds};
    game.AddNode(lastPass);

    GameNode nextNode = lastPass;
    for (int t = nRounds - 1; t >= 0; t--)
    {
        int player = (t % 2 == 0) ? 1 : 2;
        var payoffs = PayoffsAtRound(t);
        var takeTerminal = new GameNode("take_" + t, -1);
        takeTerminal.Payoffs = payoffs;
        game.AddNode(takeTerminal);

        var decision = new GameNode("node_" + t, player);
        decision.Actions = new List<string>{"Take", "Pass"};
        decision.Children["Take"] = takeTerminal;
        decision.Children["Pass"] = nextNode;
        game.AddNode(decision);
        nextNode = decision;
    }
    game.SetRoot(nextNode);
    return game;
}

var centipede6 = CreateCentipedeGame(6);
var (centSolution, centEq) = BackwardInduction(centipede6);
DisplayBackwardInduction(centipede6, centSolution);
display("Gains a l'equilibre SPE : " + FV(centEq));
display("Paradoxe : bien que les gains cooperatifs (6, 6) soient plus eleves,");
display("l'equilibre de sous-jeu parfait impose Take des le tour 0 (1, 0).");

Solution par induction arriere : Centipede (6 tours)
============================================================
  Noeud node_5 (J2): joue 'Take' -> [4.00, 6.00]
  Noeud node_4 (J1): joue 'Take' -> [5.00, 3.00]
  Noeud node_3 (J2): joue 'Take' -> [2.00, 4.00]
  Noeud node_2 (J1): joue 'Take' -> [3.00, 1.00]
  Noeud node_1 (J2): joue 'Take' -> [0.00, 2.00]
  Noeud node_0 (J1): joue 'Take' -> [1.00, 0.00]

Gains a l'equilibre SPE : [1.00, 0.00]

Paradoxe : bien que les gains cooperatifs (6, 6) soient plus eleves,

l'equilibre de sous-jeu parfait impose Take des le tour 0 (1, 0).

5. Efficacite et rationalite limitee

Comparons le gain SPE (Take immediat) au gain cooperatif (Pass jusqu’au bout). Avec une probabilite d’erreur (rationalite limitee), le comportement change : on peut montrer qu’il devient rationnel de Passer si l’adversaire est susceptible de se tromper.

Lecture de la table committée — et sa leçon contre-intuitive : cinq horizons, n = 2, 4, 6, 8, 10. Colonne SPE : 1.0 constante — quel que soit l’horizon, l’induction arrière donne tout le premier prélèvement au joueur 1 (bigPile au tour 0 vaut t+1 = 1). Colonne coopération : n exactement (le tas final). Colonne ratio : 2.0x, 4.0x, 6.0x, 8.0x, 10.0x — croissance linéaire dans l’horizon. C’est la leçon la plus dérangeante du paradoxe : plus le gâteau coopératif est gros, plus l’écart entre la rationalité individuelle (SPE) et l’optimum social est grand. Le paradoxe ne s’atténue pas avec l’expérience — il s’aggravait. Rosenthal (1981) l’a formulé précisément pour attaquer la rationalnalité de l’induction arrière comme prédiction comportementale : les sujets expérimentaux coopèrent longtemps, et les deux prédictions divergent d’autant plus que le jeu est long.

// Analyse d'efficacite : SPE vs cooperation, en fonction de n_rounds.
var sbEff = new StringBuilder();
sbEff.AppendLine("Efficacite SPE vs Cooperation (Centipede) :");
sbEff.AppendLine(new string('-', 56));
sbEff.AppendLine("  Tours |  SPE (Take t=0) | Cooperatif (fin) | Ratio");
foreach (var n in new[]{2, 4, 6, 8, 10})
{
    var g = CreateCentipedeGame(n);
    var (_, eq) = BackwardInduction(g);
    double speP1 = eq[0];
    double coopP1 = n;  // gain cooperatif du joueur 1
    double ratio = (coopP1 > 0) ? coopP1 / Math.Max(0.001, speP1) : 0;
    sbEff.AppendLine("  " + n.ToString("D5") + " |  " + FI(speP1, "F1") + "          |  " + FI(coopP1, "F1") + "            | " + FI(ratio, "F1") + "x");
}
display(sbEff.ToString());
display("Conclusion : l'ecart d'efficacite SPE vs cooperation CROIT avec le nombre de tours.");
display("C'est pourquoi le paradoxe est si marque dans les versions longues du mille-pattes.");

Efficacite SPE vs Cooperation (Centipede) :
--------------------------------------------------------
  Tours |  SPE (Take t=0) | Cooperatif (fin) | Ratio
  00002 |  1.0          |  2.0            | 2.0x
  00004 |  1.0          |  4.0            | 4.0x
  00006 |  1.0          |  6.0            | 6.0x
  00008 |  1.0          |  8.0            | 8.0x
  00010 |  1.0          |  10.0            | 10.0x

Conclusion : l'ecart d'efficacite SPE vs cooperation CROIT avec le nombre de tours.

C'est pourquoi le paradoxe est si marque dans les versions longues du mille-pattes.

6. Guerre d’usure (War of Attrition)

Deux joueurs s’affrontent ; a chaque tour chacun peut Quit (abandonner) ou Fight (continuer). Le gagnant empoche un prix V, mais chaque tour de combat coute c aux deux joueurs.

Tension : abandonner vite economise les couts, mais si l’autre abandonne d’abord, on gagne V.

Lecture de la sortie committée — et son artefact d’affichage : équilibre [9.00, -0.00] pour V=10, c=1, max_rounds=5. Décomposons. La trace j2_n Quit / j1_n Fight figure à chaque nœud de la remontée : à chaque étage, joueur 2 préfère quitter et joueur 1 préférerait qu’il continue. Sur le chemin d’équilibre, J1 engage le tour 0 (coût c=1 déjà payé), J2 quitte immédiatement (coût 0) : J1 empoche V - 1 = 9, J2 sort à 0. D’où le -0.00 : un zéro négatif en virgule flottante (0.0 issu d’une soustraction 0 - 0.0 ou d’un produit par -1), rendu par le helper FI en InvariantCulture — le signe n’a aucune signification économique, c’est un artefact du formatage F2, pas une valeur négative. À retenir aussi : la sortie du jumeau Python pour ce même jeu diffère ((8, 0)) car sa construction facture à J1 un coût de combat supplémentaire au tour du départ de J2 — voir la section Résumé.

// Guerre d'usure sequentielle (simplifiee) : J1 puis J2 decident a chaque tour.
public static ExtensiveFormGame CreateWarOfAttrition(int maxRounds = 5, double V = 10, double c = 1)
{
    var game = new ExtensiveFormGame("War of Attrition (V=" + FI(V, "F0") + ", c=" + FI(c, "F0") + ")", 2);

    GameNode BuildRound(int round, double cost1, double cost2)
    {
        if (round >= maxRounds)
        {
            var tie = new GameNode("tie_" + round, -1);
            tie.Payoffs = new double[]{ -cost1, -cost2 };
            game.AddNode(tie);
            return tie;
        }
        // J1 abandonne : J2 gagne V.
        var j1Quit = new GameNode("j1_quit_" + round, -1);
        j1Quit.Payoffs = new double[]{ -cost1, V - cost2 };
        game.AddNode(j1Quit);
        // J2 abandonne (si J1 continue) : J1 gagne V, mais a paye un c supplementaire.
        var j2Quit = new GameNode("j2_quit_" + round, -1);
        j2Quit.Payoffs = new double[]{ V - cost1 - c, -cost2 };
        game.AddNode(j2Quit);
        // Tour suivant (les deux continuent).
        var nextRound = BuildRound(round + 1, cost1 + c, cost2 + c);

        var j2Node = new GameNode("j2_" + round, 2);
        j2Node.Actions = new List<string>{"Quit", "Fight"};
        j2Node.Children["Quit"] = j2Quit;
        j2Node.Children["Fight"] = nextRound;
        j2Node.Infoset = "I2_" + round;
        game.AddNode(j2Node);

        var j1Node = new GameNode("j1_" + round, 1);
        j1Node.Actions = new List<string>{"Quit", "Fight"};
        j1Node.Children["Quit"] = j1Quit;
        j1Node.Children["Fight"] = j2Node;
        j1Node.Infoset = "I1_" + round;
        game.AddNode(j1Node);
        return j1Node;
    }

    var root = BuildRound(0, 0, 0);
    game.SetRoot(root);
    return game;
}

var woa = CreateWarOfAttrition(5, 10, 1);
var (woaSolution, woaEq) = BackwardInduction(woa);
DisplayBackwardInduction(woa, woaSolution);
display("Gains a l'equilibre : " + FV(woaEq));
display("Analyse : au dernier tour possible, abandonner domine ; par induction,");
display("la guerre d'usure se termine tot. Le ratio V/c determine la duree d'escalade.");

Solution par induction arriere : War of Attrition (V=10, c=1)
============================================================
  Noeud j2_4 (J2): joue 'Quit' -> [5.00, -4.00]
  Noeud j1_4 (J1): joue 'Fight' -> [5.00, -4.00]
  Noeud j2_3 (J2): joue 'Quit' -> [6.00, -3.00]
  Noeud j1_3 (J1): joue 'Fight' -> [6.00, -3.00]
  Noeud j2_2 (J2): joue 'Quit' -> [7.00, -2.00]
  Noeud j1_2 (J1): joue 'Fight' -> [7.00, -2.00]
  Noeud j2_1 (J2): joue 'Quit' -> [8.00, -1.00]
  Noeud j1_1 (J1): joue 'Fight' -> [8.00, -1.00]
  Noeud j2_0 (J2): joue 'Quit' -> [9.00, -0.00]
  Noeud j1_0 (J1): joue 'Fight' -> [9.00, -0.00]

Gains a l'equilibre : [9.00, -0.00]

Analyse : au dernier tour possible, abandonner domine ; par induction,

la guerre d'usure se termine tot. Le ratio V/c determine la duree d'escalade.

7. Paradoxe de la chaîne de magasins (Chain Store)

Un monopole (J2) fait face a n entrants sequentiellement. Pour chaque entrant, le monopole peut Fight (agressif, cout -1 pour les deux) ou Accommodate (+1 pour les deux). Si le monopole combat, cela dissuade… en théorie.

Paradoxe de Selten : l’induction arriere dit “Accommodate partout” (le dernier entrant n’a rien a craindre, donc l’avant-dernier non plus, etc.), mais intuitivement le monopole a intérêt a construire une reputation agressive.

Lecture de la sortie committée : [0.00, 6.00], avec le compteur Accommodate: 3, Fight: 0. Le monopole cède sur les trois marchés et empoche 6 au total (3 x 2). L’argument de Selten (1978) se lit dans l’ordre inverse de l’entrée des challengers : sur le dernier marché, le monopole n’a plus de réputation à défendre — accéder (payoff 2) domine combattre (-1), donc la menace n’y est pas crédible. Le challenger du marché précédent l’anticipe : combattre ici ne dissuaderait personne plus tard, donc céder domine à nouveau. La cascade remonte les trois marchés : aucun combat n’a lieu à l’équilibre. C’est le paradoxe de la chaîne de magasins : la réputation, rationnellement inutile quand l’horizon est fini et connu, est pourtant observée en pratique — l’écart entre la prédiction SPE et le comportement des monopoles réels a fait couler beaucoup d’encre (réputations bornées, incertitude sur la rationalité de l’entrant, jeux répétés à horizon incertain).

// Chaine de magasins : n entrants sequentiels, monopole Fight/Accommodate a chaque fois.
public static ExtensiveFormGame CreateChainStoreGame(int nEntrants = 3)
{
    var game = new ExtensiveFormGame("Chain Store (" + nEntrants + " entrants)", 2);

    GameNode BuildMarket(int market, double monopolyTotal)
    {
        if (market >= nEntrants)
        {
            var end = new GameNode("end", -1);
            end.Payoffs = new double[]{ 0, monopolyTotal };
            game.AddNode(end);
            return end;
        }
        // Monopole combat sur ce marche.
        var fightContinue = BuildMarket(market + 1, monopolyTotal - 1);
        var fightTerminal = new GameNode("fight_" + market, -1);
        fightTerminal.Payoffs = new double[]{ -1, -1 };
        game.AddNode(fightTerminal);
        // Monopole accepte sur ce marche.
        var accContinue = BuildMarket(market + 1, monopolyTotal + 1);

        var monopole = new GameNode("monopole_" + market, 2);
        monopole.Actions = new List<string>{"Fight", "Accommodate"};
        monopole.Children["Fight"] = fightContinue;
        monopole.Children["Accommodate"] = accContinue;
        monopole.Infoset = "I2_" + market;
        game.AddNode(monopole);

        var entrant = new GameNode("entrant_" + market, 1);
        entrant.Actions = new List<string>{"Stay Out", "Enter"};
        entrant.Children["Stay Out"] = BuildMarket(market + 1, monopolyTotal + 2);
        entrant.Children["Enter"] = monopole;
        game.AddNode(entrant);
        return entrant;
    }

    var root = BuildMarket(0, 0);
    game.SetRoot(root);
    return game;
}

var cs = CreateChainStoreGame(3);
var (csSolution, csEq) = BackwardInduction(cs);
display("Chain Store (3 entrants) - solution synthetique :");
display("  Gains d'equilibre SPE : " + FV(csEq));
int accommodateCount = csSolution.Values.Count(s => s.OptimalAction == "Accommodate");
int fightCount = csSolution.Values.Count(s => s.OptimalAction == "Fight");
display("  Monopole : Accommodate=" + accommodateCount + " fois, Fight=" + fightCount + " fois");
display("Paradoxe : l'induction arriere pousse le monopole a Accommoder a chaque marche.");
display("Une analyse 'forward' suggere pourtant qu'une reputation agressive serait rationnelle.");

Chain Store (3 entrants) - solution synthetique :

  Gains d'equilibre SPE : [0.00, 6.00]

  Monopole : Accommodate=3 fois, Fight=0 fois

Paradoxe : l'induction arriere pousse le monopole a Accommoder a chaque marche.

Une analyse 'forward' suggere pourtant qu'une reputation agressive serait rationnelle.

8. Visualisation ASCII de l’arbre de jeu

Le notebook Python utilise matplotlib ; ce twin C# dessine l’arbre en ASCII (complementaire, Prong B). L’equilibre SPE est marque par une astérisque *.

Comment lire l’arbre ASCII committé : la sortie dessine l’Entry Game en ASCII avec le chemin d’équilibre marqué d’astérisques (*). Trois branches partent du nœud racine (la décision de l’entrant) : Out vers la feuille [0, 2], Enter vers le nœud de l’incumbent, qui se partage en Fight vers [-1, -1] et Accommodate vers [1, 1]. Les astérisques suivent Enter -> Accommodate -> [1.00, 1.00] — le chemin que l’induction arrière sélectionne. Les branches non marquées (Out, Fight) ne sont pas des erreurs : ce sont les contre-chemins hors équilibre, exactement ce que la notion de sous-jeu parfait élimine. La visualisation ASCII est ici un choix pédagogique délibéré (zéro dépendance, lisible dans n’importe quelle console) — le jumeau Python rend le même arbre avec networkx/matplotlib, au prix d’un import graphique.

// Dessine l'arbre de jeu en ASCII avec le chemin SPE marque.
public static void DrawTreeAscii(ExtensiveFormGame game, Dictionary<string, NodeSolution> solution)
{
    var sb = new StringBuilder();
    void Rec(GameNode node, string indent, bool isLast, bool onPath)
    {
        string marker = onPath ? " *" : "  ";
        string branch = (indent.Length == 0) ? "" : (isLast ? " +-- " : " |-- ");
        string label;
        if (node.IsTerminal())
            label = "[" + node.NodeId + "] = " + FV(node.Payoffs);
        else if (node.IsChance())
            label = "(" + node.NodeId + ", Nature)";
        else
            label = "(" + node.NodeId + ", J" + node.Player + ")";
        sb.AppendLine(indent + branch + marker + label);

        string childIndent = indent + (isLast ? "     " : " |    ");
        string optAction = null;
        if (solution.ContainsKey(node.NodeId)) optAction = solution[node.NodeId].OptimalAction;
        int n = node.Actions.Count;
        for (int i = 0; i < n; i++)
        {
            var action = node.Actions[i];
            var child = node.Children[action];
            bool childOnPath = onPath && (action == optAction);
            // edge label
            string edgeMark = (action == optAction) ? " *" : "  ";
            sb.AppendLine(childIndent + (i == n - 1 ? " +-- " : " |-- ") + edgeMark + "[" + action + "]");
            string grandIndent = childIndent + (i == n - 1 ? "     " : " |    ");
            Rec(child, grandIndent, true, childOnPath);
        }
    }
    sb.AppendLine("Arbre de jeu '" + game.Name + "' (* = chemin SPE) :");
    Rec(game.Root, "", true, true);
    display(sb.ToString());
}

DrawTreeAscii(entryGame, entrySolution);

Arbre de jeu 'Entry Game' (* = chemin SPE) :
 *(entrant, J1)
      |--  *[Enter]
      |     +--  *(incumbent, J2)
      |          |--   [Fight]
      |          |     +--   [fight] = [-1.00, -1.00]
      |          +--  *[Accommodate]
      |               +--  *[accommodate] = [1.00, 1.00]
      +--   [Out]
           +--   [out] = [0.00, 2.00]

9. Resume

Points cles

• L’induction arriere resout exactement les jeux a information parfaite en remontant des feuilles vers la racine.
• Elle produit un equilibre de sous-jeu parfait (SPE) : rationnel dans chaque sous-jeu, sans menaces non credibles.
• Les paradoxes (centipede, chain store) montrent la tension entre cette rationalite “backward” et l’intuition “forward” (reputation, cooperation).

Comparaison avec le twin Python

Aspect	Python	C# (ce notebook)
Structure	@dataclass + numpy	class mutable + double[]
Recursion	def solve(node) interne	double[] Solve(GameNode) locale
Visualisation	matplotlib (graphe)	ASCII tree (complementaire)
Dépendance	numpy	BCL seule (0 NuGet)

Applications

• Théorie des jeux extensive (negociations, duree, reputation)
• Economie (entry deterrence, price wars)
• IA : planification adversariale, jeu a somme nulle parfait

Les chiffres et faits à retenir : quatre jeux, quatre sorties committées — Entry Game [1.00, 1.00] avec menace Fight non crédible ; mille-pattes 6 tours déroulé jusqu’à Take au tour 0 (SPE [1.00, 0.00] contre coopération (6, 6)), ratio perte/coopération n (jusqu’à 10.0x) ; guerre d’usure résolue au premier tour ([9.00, -0.00], l’artefact du zéro négatif) ; chaîne de magasins cédant 3 fois ([0.00, 6.00], Accommodate: 3). Note d’honnêteté sur le jumeau : la sortie Python de la guerre d’usure est (8, 0) contre [9, 0] en C# — les deux constructions facturent les coûts de combat différemment au tour du départ de J2 (le builder Python retire un c supplémentaire à J1), asymétrie pré-existante documentée au registre de parité, sans effet sur la leçon commune (l’équilibre s’arrête immédiatement des deux côtés). C’est un exemple utile de la sémantique semantic de la paire : même théorème, implémentations sœurs non identiques.

10. Exercices

Convention : ces cellules sont des stubs a completer (règle C.1 : pas d’erreur volontaire). Le notebook s’execute de bout en bout même si les exercices ne sont pas resolus.

Comment utiliser ces exercices : chaque stub est auto-exécutable (règle C.1 — la sortie affiche « a completer » sans erreur) et réutilise les briques des sections précédentes (GameNode, ExtensiveFormGame, BackwardInduction). Les critères de validation sous chaque énoncé donnent les valeurs attendues — résolvez à la main d’abord (l’induction arrière sur 3 tours se fait de tête), puis vérifiez avec le solveur : c’est l’inverse du notebook principal, où le solveur confirme votre lecture.

Exercice 1 : Jeu de negociation (bargaining) a 3 tours

Deux joueurs se partagent un gain de 4. A chaque tour, celui qui propose fait une offre (x, 4-x) ; l’autre accepte ou refuse. Si refus, le gain diminue (discount 0.5 par tour). Après 3 tours, le jeu s’arrete.

Objectif : construire l’arbre, resoudre par induction arriere, identifier l’offre d’equilibre.

Critère de validation : l’induction remonte les trois tours. Tour 3 (dernier) : pie = 4 x 0.5^2 = 1, le proposant du tour 3 (joueur 1, qui propose aux tours impairs) prend tout — continuation (1, 0). Tour 2 : pie = 2, joueur 2 propose ; le joueur 1 accepte s’il reçoit au moins sa continuation 1 → offre (1, 1). Tour 1 : pie = 4, joueur 1 propose ; le joueur 2 accepte à >= 1 → première offre (3, 1), acceptée immédiatement. Si votre solveur rend autre chose, vérifiez deux pièges : (a) l’hypothèse d’acceptation à l’indifférence (le responder accepte à égalité — sinon l’offre est 3 - epsilon), (b) l’ordre des proposants (alterné strict : J1, J2, J1).

// Exercice 1 : Bargaining a 3 tours (a completer)
// Etape 1 : construire l'arbre ExtensiveFormGame avec discount 0.5 par tour refuse
// Etape 2 : appeler BackwardInduction et afficher l'offre d'equilibre
// Indice : au tour 3 (dernier), l'offreur prend tout le reste ; remontez avec le discount.
// var bargaining = ... ;
// var (bSol, bEq) = BackwardInduction(bargaining);
// DisplayBackwardInduction(bargaining, bSol);
display("Exercice 1 (bargaining) a completer : voir indice ci-dessus.");

Exercice 1 (bargaining) a completer : voir indice ci-dessus.

Exercice 2 : Jeu de l’ultimatum

Le proposeur offre une part x de 10 ; le recepteur accepte (10-x, x) ou refuse (0, 0).

Objectif : determiner l’offre SPE. Quel x le proposeur choisit-il a l’equilibre ?

Critère de validation : quelle que soit la taille du menu (x in 1..5), le receiver accepte tout x >= 1 (refuser rapporte 0). Le proposer, anticipant, offre le minimum acceptable : x = 1, payoffs (9, 1). La variante à essayer ensuite : rendez le receiver rancunier (il refuse tout x < 3) et observez que l’équilibre bascule à (7, 3) — c’est l’argument d’ultimate bargaining à la Guth et al. (1982) : l’équité observée expérimentalement n’est pas irrationnelle si refuser les offres faibles est une menace crédible, ce que l’induction arrière standard ne capture pas.

// Exercice 2 : Jeu de l'ultimatum (a completer)
// Etape 1 : construire l'arbre (proposeur offre parmi {1, 2, ..., 5}, recepteur Accept/Reject)
// Etape 2 : resoudre par induction arriere
// Indice : le recepteur accepte toujours x > 0 (x > 0 > 0 du rejet) ; le proposeur offre donc le minimum.
// var ultimatum = ... ;
display("Exercice 2 (ultimatum) a completer : construire l'arbre puis BackwardInduction.");

Exercice 2 (ultimatum) a completer : construire l'arbre puis BackwardInduction.

Exercice 3 : Take-Away (Nim a 1 tas)

n jetons sur la table. 2 joueurs retirent a tour de rôle 1 a max_take jetons. Celui qui prend le dernier gagne.

Objectif : modeliser comme jeu extensive (arbre), resoudre par induction, identifier les positions gagnantes.

Critère de validation : la clé est la notion de position perdante — un multiple de maxTake + 1. Face à un multiple de 4 (pour maxTake = 3), tout retrait laisse un non-multiple, et l’adversaire peut toujours revenir à un multiple : n = 4 perd, n = 8 perd, n = 12 perd. Face à un non-multiple, on retire n mod (maxTake + 1) et on le laisse en position perdante : n = 5, 6, 7 gagnent (retirer vers 4), n = 9, 10, 11 gagnent (vers 8). Attention à l’affichage de sortie : l’induction arrière sur n = 12, maxTake = 3 construit un arbre à somme_{k=1}^{12} 4^k nœuds si vous modélisez chaque historique — préférez une table des positions gagnantes (programmation dynamique) et n’utilisez l’arbre que pour n <= 8.

// Exercice 3 : Take-Away / Nim a 1 tas (a completer)
// Etape 1 : ecrire une fonction buildTakeAway(n, maxTake) -> ExtensiveFormGame
// Etape 2 : resoudre et determiner pour quels n le joueur 1 gagne
// Indice : les positions perdantes sont les multiples de (maxTake + 1).
// public static ExtensiveFormGame BuildTakeAway(int n, int maxTake) { ... }
display("Exercice 3 (Take-Away) a completer : modeliser l'arbre puis BackwardInduction.");

Exercice 3 (Take-Away) a completer : modeliser l'arbre puis BackwardInduction.

---

See #4956 (marathon parite .NET), #3801 (Prong B : from-scratch), #2161 (exercices). Suite : GameTheory-11-BayesianGames-CSharp (jeux bayesiens).

Pour aller plus loin : la littérature des remèdes au déroulement — réputation (Kreps et Wilson 1982, une petite probabilité d’irrationalité restaure la coopération), jeux à horizon incertain, engagement exogoge (burning money) — fait l’objet de pairs dédiés dans la série GameTheory. Le point d’ancrage commun : l’induction arrière est la solution conceptuelle correcte pour les jeux finis à information parfaite (Kuhn 1953), et c’est précisément parce qu’elle est correcte que ses prédictions contre-intuitives posent question.