GameTheory 4c - Théorème d’Existence de Nash (C#)

Jumeau C# du notebook GameTheory-04c-NashExistence-Python.ipynb. Marathon parité .NET ⇄ Python (#4956), EPIC #3801 Prong B. Théorème de Brouwer (point fixe) ⇒ existence d’un équilibre de Nash en stratégies mixtes, implémenté from-scratch en C# pur (pas de lib externe, visualisations en ASCII).

Navigation : << 4-NashEquilibrium | 4b-Lean-NashExistence | Twin Python | Index

Kernel : .NET 9.0 + dotnet-interactive (.net-csharp)

Introduction

Ce notebook C# accompagne le notebook Lean 4b (théorème formel). Il fournit :

Illustrations numériques du théorème de Brouwer (recherche de points fixes par itération)
Algorithmes de points fixes 1D et sur le simplexe
Exemple concret : Matching Pennies, meilleure réponse perturbée
Dynamique de meilleure réponse convergeant vers l’équilibre de Nash

Pourquoi le théorème de Brouwer implique Nash

Le théorème de Brouwer dit que toute fonction continue f : Δ → Δ d’un convexe compact (le simplexe Δ) dans lui-même admet un point fixe x* = f(x*). Nash (1950) montre que la meilleure réponse d’un joueur, vue comme correspondance multivaluée, peut être transformée en une fonction continue sur le simplexe des profils mixtes — dont le point fixe est un équilibre de Nash. On l’illustre ici numériquement.

Objectifs d’apprentissage

Implémenter la recherche de point fixe par itération (1D et simplexe).
Projeter sur le simplexe (clipping + normalisation).
Calculer le gain espéré d’un profil mixte contre une matrice de gains.
Définir la meilleure réponse perturbée (regret matching) — continue, garant de Brouwer.
Démontrer la convergence vers l’équilibre de Matching Pennies (0.5, 0.5).

Prérequis

Notions de théorie des jeux (stratégie mixte, matrice de gains, meilleure réponse).
.NET 9.0 + dotnet-interactive.
Avoir suivi GameTheory-04-NashEquilibrium-Python.

Durée estimée : 45 minutes

Références

Nash, J. Equilibrium Points in n-Person Games (1950).
Brouwer, L. E. J. Über Abbildung von Mannigfaltigkeiten (1911).
Notebook Python : GameTheory-04c-NashExistence-Python.ipynb.

1. Point fixe en dimension 1

Un point fixe de f est x* tel que f(x*) = x*. On le cherche par itération : x_{n+1} = f(x_n). Si f est contractante, la suite converge.

using System.Linq;

// Recherche d'un point fixe par iteration, 1D.
(double fixedPoint, List<double> history) FindFixedPoint1D(Func<double,double> f,
        double x0 = 0.5, double tol = 1e-6, int maxIter = 100) {
    double x = x0;
    var history = new List<double>{x};
    for (int i = 0; i < maxIter; i++) {
        double xNew = f(x);
        history.Add(xNew);
        if (Math.Abs(xNew - x) < tol) return (xNew, history);
        x = xNew;
    }
    return (x, history);
}

// Exemple : f(x) = 0.5 * (x + 1/x) converge vers 1 (moyenne babylonienne).
Func<double,double> f = x => 0.5 * (x + 1.0 / Math.Max(x, 0.01));
var (fixedPt, history) = FindFixedPoint1D(f, x0: 2.0);
Console.WriteLine($"Point fixe trouve   : {fixedPt:F10}");
Console.WriteLine($"Verification f(x*)  : {f(fixedPt):F10}");
Console.WriteLine($"Iterations          : {history.Count}");
Console.WriteLine($"|f(x*) - x*|        : {Math.Abs(f(fixedPt) - fixedPt):E2}");

Point fixe trouve   : 1,0000000000
Verification f(x*)  : 1,0000000000
Iterations          : 6
|f(x*) - x*|        : 1,11E-015

Lecture : le point fixe comme équation soluble par itération

La sortie vaut pour la méthode autant que pour le résultat : chercher x* tel que f(x*) = x* en répétant x <- f(x) converge ici en 6 itérations vers 1,0000000000, avec un résidu |f(x*) - x*| = 1,1E-15 — l’ordre de grandeur de la précision machine. Ce n’est pas un hasard de l’exemple : pour une fonction contractante, chaque itération réduit l’écart d’un facteur constant, et la convergence est géométrique. Le théorème de point fixe de Brouwer — l’outil central de l’existence de Nash — garantit l’EXISTENCE d’un point fixe sur un compact convexe ; l’itération, elle, en donne un moyen numérique. Le notebook construit ce lien en trois paliers : dimension 1 ici, simplexe 2D ensuite, meilleure réponse enfin.

2. Point fixe sur le simplexe

Le simplexe Δ = {x ∈ ℝⁿ : x_i ≥ 0, Σ x_i = 1} est convexe compact. On projette après chaque itération : clip des négatifs + normalisation.

// Projection sur le simplexe : clip negatifs + normalisation.
double[] ProjectSimplex(double[] x) {
    var proj = x.Select(v => Math.Max(0, v)).ToArray();
    double s = proj.Sum();
    if (s < 1e-12) return Enumerable.Range(0, x.Length).Select(_ => 1.0 / x.Length).ToArray();
    return proj.Select(v => v / s).ToArray();
}

// Norme euclidienne.
double Norm(double[] v) => Math.Sqrt(v.Select(a => a * a).Sum());

// Recherche de point fixe sur le simplexe (dimension n-1 implicite via x.Length).
(double[] fixedPoint, List<double[]> history) FindFixedPointSimplex(
        Func<double[],double[]> f, double[]? x0 = null, int n = 2,
        double tol = 1e-6, int maxIter = 1000) {
    double[] x = (double[])(x0 ?? Enumerable.Range(0, n).Select(_ => 1.0 / n).ToArray()).Clone();
    var history = new List<double[]> { (double[])x.Clone() };
    for (int i = 0; i < maxIter; i++) {
        double[] xNew = ProjectSimplex(f(x));
        history.Add((double[])xNew.Clone());
        if (Norm(Sub(xNew, x)) < tol) return (xNew, history);
        x = xNew;
    }
    return (x, history);
}
double[] Sub(double[] a, double[] b) => a.Zip(b, (u, v) => u - v).ToArray();
string FmtV(double[] v) => "[" + string.Join(", ", v.Select(x => x.ToString("F4"))) + "]";

// Exemple : contraction vers (0.5, 0.5).
double[] center = {0.5, 0.5};
Func<double[],double[]> exampleMap = x => x.Zip(center, (u, c) => 0.9 * u + 0.1 * c).ToArray();
var (fixed2d, hist2d) = FindFixedPointSimplex(exampleMap, x0: new[]{0.1, 0.9});
Console.WriteLine($"Point fixe 2D : {FmtV(fixed2d)}");
Console.WriteLine($"Somme         : {fixed2d.Sum():F6}");
Console.WriteLine($"Iterations    : {hist2d.Count}");

Point fixe 2D : [0,5000, 0,5000]
Somme         : 1,000000
Iterations    : 106

Lecture : du segment au simplexe — et `106` itérations au lieu de `6`

Le problème change de nature : les stratégies mixtes vivent sur le simplexe (des probabilités qui somment à 1), pas sur un segment. La projection affichée — clipper les négatifs puis normaliser — ramène tout point de R^2 sur ce triangle, et l’itération du point fixe y trouve [0,5 ; 0,5], somme exactement 1. Notez le coût : 106 itérations contre 6 en dimension 1.

L’écart ne vient ni de la dimension ni d’un défaut de contraction : la carte itérée x ↦ 0,9·x + 0,1·(0,5 ; 0,5) est exactement une contraction, de rapport mesuré 0,9000000000 constant sur toute la trajectoire — contractante, et non « seulement non expansive ». La projection, elle, reste inerte : le clip ne se déclenche 0 fois sur 105 itérations, et la renormalisation ne déplace le point que d’un ULP (2,2E-16, nul 91 fois sur 105) — l’itéré ne quitte jamais le simplexe.

Le coût vient donc de la vitesse comparée des deux itérations. En dimension 1, 0,5(x + 1/x) est la moyenne babylonienne, une itération de Newton : son erreur est quadratique (e(k+1) ≈ e(k)²/2), d’où cinq itérations pour 6 points d’historique. Ici le rapport est fixe et linéaire : l’erreur décroît géométriquement, donc lentement. Et le nombre d’itérations n’est pas seulement mesuré, il est prédit : le pas d’une itération vaut un dixième de la distance au centre, laquelle décroît à ce rapport constant — le seuil 1E-6 est franchi à l’itération d’indice 104, exactement celle que le programme a trouvée. C’est la leçon transposable : c’est le rapport qui décide du coût, et le cas réel de Nash en hérite — jusqu’à Matching Pennies, où la dynamique s’arrête net.

3. Matching Pennies — matrice de gains et meilleure réponse

Matching Pennies : le joueur 1 veut matcher (même face), le joueur 2 veut mismatcher. L’équilibre de Nash est le profil mixte uniforme (0.5, 0.5).

	Pile (J2)	Face (J2)
Pile (J1)	(+1, −1)	(−1, +1)
Face (J1)	(−1, +1)	(+1, −1)

La meilleure réponse perturbée (regret matching) ajoute du poids aux actions dont le regret est positif — c’est une fonction continue du profil, donc Brouwer s’applique.

// Matrices de gains (2x2). U1 = joueur 1 (match), U2 = joueur 2 (mismatch).
double[,] U1 = {{1, -1}, {-1, 1}};
double[,] U2 = {{-1, 1}, {1, -1}};

// Gain espere : sigma1 . U . sigma2
double ExpectedPayoff(double[] sigma1, double[] sigma2, double[,] U) {
    double s = 0;
    for (int i = 0; i < sigma1.Length; i++)
        for (int j = 0; j < sigma2.Length; j++)
            s += sigma1[i] * U[i, j] * sigma2[j];
    return s;
}

// Meilleure reponse perturbee (regret matching, continue).
double[] PerturbedBR(double[] sigma, double[,] U, double epsilon = 0.1) {
    double current = ExpectedPayoff(sigma, sigma, U);
    var regrets = new double[sigma.Length];
    for (int a = 0; a < sigma.Length; a++) {
        var pure = new double[sigma.Length]; pure[a] = 1.0;
        double gainA = ExpectedPayoff(pure, sigma, U);
        regrets[a] = Math.Max(0, gainA - current);
    }
    var perturbed = sigma.Zip(regrets, (s, r) => s + epsilon * r).ToArray();
    return ProjectSimplex(perturbed);
}

double[] sigmaUniform = {0.5, 0.5};
Console.WriteLine(new string('=', 50));
Console.WriteLine("MATCHING PENNIES - Point fixe");
Console.WriteLine(new string('=', 50));
Console.WriteLine($"Strategie initiale     : {FmtV(sigmaUniform)}");
Console.WriteLine($"Gain espere J1 (U1)    : {ExpectedPayoff(sigmaUniform, sigmaUniform, U1):F4}");
Console.WriteLine($"Gain espere J2 (U2)    : {ExpectedPayoff(sigmaUniform, sigmaUniform, U2):F4}");
Console.WriteLine();
var br1 = PerturbedBR(sigmaUniform, U1);
Console.WriteLine($"BR perturbee J1        : {FmtV(br1)}");
bool isFixed = sigmaUniform.Zip(br1, (a, b) => Math.Abs(a - b) < 1e-6).All(t => t);
Console.WriteLine($"Est un point fixe ?    : {isFixed}");

==================================================
MATCHING PENNIES - Point fixe
==================================================
Strategie initiale     : [0,5000, 0,5000]
Gain espere J1 (U1)    : 0,0000
Gain espere J2 (U2)    : 0,0000

BR perturbee J1        : [0,5000, 0,5000]
Est un point fixe ?    : True

Lecture : Matching Pennies — le point fixe égalisateur

La sortie résume la machinerie complète sur le jeu qui n’avait aucun équilibre pur : parti de [0,5 ; 0,5], l’itérateur calcule les gains espérés (0,0000 chacun), évalue les meilleures réponses, les perturbe — et rend Est un point fixe ? True. La lecture stratégique : à cinquante-cinquante, aucun des deux joueurs ne peut dévier avec profit, parce que TOUTE déviation se fait contrer. Le gain espéré nul des deux côtés dit que ce n’est pas un hasard d’égalité — c’est la VALEUR du jeu : symétrique et strictement compétitive, Matching Pennies ne peut pas rendre un côté strictement meilleur que l’autre. L’équilibre que la section Nash-pure du notebook 03 cherchait en vain existe donc bel et bien — mais sur la frontière des stratégies mixtes, exactement là où le théorème de Nash dit de le chercher.

4. Dynamique de meilleure réponse — convergence vers Nash

On itère la dynamique σ_{n+1} = ½·(BR₁(σ_n) + BR₂(σ_n)) depuis plusieurs points de départ. Tous convergent vers (0.5, 0.5) = équilibre de Nash de Matching Pennies. (Le notebook Python trace la trajectoire en matplotlib ; ici on l’affiche en table.)

// Dynamique de meilleure reponse (moyenne des BR des 2 joueurs).
double[] NashDynamicsStep(double[] sigma, double[,] u1, double[,] u2, double epsilon = 0.2) {
    var br1 = PerturbedBR(sigma, u1, epsilon);
    var br2 = PerturbedBR(sigma, u2, epsilon);
    return br1.Zip(br2, (a, b) => 0.5 * (a + b)).ToArray();
}

double[][] startingPoints = {
    new[]{0.9, 0.1}, new[]{0.1, 0.9}, new[]{0.7, 0.3},
};

Console.WriteLine("Convergence vers Nash (0.5, 0.5) depuis 3 departs :");
Console.WriteLine($"{"Depart",-14} | {"Apres 5 it",-14} | {"Apres 20 it",-14} | {"Apres 50 it",-14}");
Console.WriteLine(new string('-', 66));
foreach (var s0 in startingPoints) {
    double[] s = (double[])s0.Clone();
    var t5 = s; var t20 = s; var t50 = s;
    for (int i = 1; i <= 50; i++) {
        s = NashDynamicsStep(s, U1, U2);
        if (i == 5) t5 = (double[])s.Clone();
        if (i == 20) t20 = (double[])s.Clone();
        if (i == 50) t50 = (double[])s.Clone();
    }
    Console.WriteLine($"{FmtV(s0),-14} | {FmtV(t5),-14} | {FmtV(t20),-14} | {FmtV(t50),-14}");
}
Console.WriteLine();
Console.WriteLine(">>> Tous les points de depart convergent vers (0.5, 0.5) = equilibre de Nash.");
Console.WriteLine(">>> C'est l'illustration numerique du theoreme de Brouwer :");
Console.WriteLine(">>> la dynamique continue BR a un point fixe sur le simplexe.");

Convergence vers Nash (0.5, 0.5) depuis 3 departs :
Depart         | Apres 5 it     | Apres 20 it    | Apres 50 it   
------------------------------------------------------------------
[0,9000, 0,1000] | [0,6507, 0,3493] | [0,5531, 0,4469] | [0,5233, 0,4767]
[0,1000, 0,9000] | [0,3493, 0,6507] | [0,4469, 0,5531] | [0,4767, 0,5233]
[0,7000, 0,3000] | [0,6098, 0,3902] | [0,5470, 0,4530] | [0,5220, 0,4780]

>>> Tous les points de depart convergent vers (0.5, 0.5) = equilibre de Nash.
>>> C'est l'illustration numerique du theoreme de Brouwer :
>>> la dynamique continue BR a un point fixe sur le simplexe.

Lecture : trois départs, un seul attracteur — et une symétrie miroir

Le tableau fait converger la dynamique de meilleure réponse continue depuis trois départs distincts, et le résultat est net : après 50 itérations, tous frôlent (0,5 ; 0,5) — 0,5233, 0,4767, 0,5220. Les deux premières lignes sont en miroir exact (0,6507 / 0,3493 contre 0,3493 / 0,6507 à l’itération 5) : la dynamique ne dépend pas du point de départ mais hérite sa symétrie de celle du jeu. Deuxième lecture, plus fine : la convergence est LENTE — après 50 itérations, l’écart résiduel est encore de 0,02. Brouwer garantit l’existence d’un point fixe, jamais la vitesse d’approche ; ici chaque itération rapproche d’un facteur modestement inférieur à 1, d’où une décroissance géométrique de queue longue. La figure suivante rend cette lenteur visible : elle ne retient que deux des trois départs, tracés comme chemins qui se lovent vers le même point.

Dernier détail du tableau, à ne pas rater : les trois départs n’avancent pas à la même vitesse — [0,7 ; 0,3] est déjà à 0,6098 après cinq itérations, plus près du but que [0,9 ; 0,1] au même horizon. La dynamique ralentit à mesure qu’elle approche du point fixe : les meilleures réponses deviennent presque indiscernables quand les croyances s’égalisent, et le pas effectif rétrécit. C’est le comportement attendu d’un flot dont le point fixe est attractif mais faiblement — l’équilibre se mérite.

5. Visualisation ASCII de la trajectoire

Le notebook Python trace la trajectoire 2D sur le simplexe [P(Heads), P(Tails)]. En C# pur (sans matplotlib), on visualise la convergence avec une grille ASCII : chaque # est un pas de la trajectoire, N est le Nash, D le départ.

// Visualisation SVG statique de la trajectoire sur le simplexe 2D (zero-dependance, EPIC #3801 Prong A).
// Chaque depart converge vers l'equilibre de Nash (0.5, 0.5) : illustration du theoreme du point fixe de Brouwer.
// Helper canon SvgChartHelper.cs (#6942 MERGED) ; Overlay multi-series (#6958 MERGED) pour les 3 traces partageant
// l'axe X numerique P(Heads). Migration SVG inline (#6927) : ancien CDN Plotly blanc en statique.
#load "../Probas/Infer/SvgChartHelper.cs"

// Trajectoire de n iterations de la dynamique de meilleure reponse depuis un point de depart.
List<(double x, double y)> Trajectory(double[] start, int n = 50) {
    var pts = new List<(double, double)> { (start[0], start[1]) };
    double[] s = (double[])start.Clone();
    for (int i = 0; i < n; i++) { s = NashDynamicsStep(s, U1, U2); pts.Add((s[0], s[1])); }
    return pts;
}

var t1 = Trajectory(new[] { 0.9, 0.1 });
var t2 = Trajectory(new[] { 0.1, 0.9 });

SvgChartHelper.Overlay(
    "Convergence vers l'equilibre de Nash (Matching Pennies)",
    "P(Heads) joueur 1", "P(Heads) joueur 2",
    new[] {
        new SvgSeries("Depart (0.9, 0.1)", t1.Select(p => p.x).ToArray(), t1.Select(p => p.y).ToArray(),
                      TraceStyle.LineMarkers, "#4C72B0"),
        new SvgSeries("Depart (0.1, 0.9)", t2.Select(p => p.x).ToArray(), t2.Select(p => p.y).ToArray(),
                      TraceStyle.LineMarkers, "#55A868"),
        new SvgSeries("Nash (0.5, 0.5)", new[] { 0.5 }, new[] { 0.5 },
                      TraceStyle.Markers, "#C44E52"),
    })

Lecture : la trajectoire rendue visible — deux chemins, un seul bassin

La figure trace sur le simplexe ce que le tableau précédent chiffre : deux trajectoires, partant des points intérieurs (0,9 ; 0,1) et (0,1 ; 0,9), s’enroulant vers le même point central (0,5 ; 0,5) — que le troisième tracé signale d’un simple marqueur, sans trajectoire : c’est la cible, pas un départ. La lecture visuelle confirme les deux propriétés mesurées — l’attracteur unique (les deux chemins mènent au même point) et la symétrie du flot (les deux trajectoires sont l’image miroir l’une de l’autre). C’est aussi le contrepoint utile du théorème : Brouwer est une affirmation d’EXISTENCE — il dit qu’un point fixe est là, quelque part sur le compact — et la dynamique itérative en est la version constructive, qui le trouve mais à sa vitesse. Les exercices qui suivent testent les limites des deux : Chicken (équilibre mixte ailleurs qu’au centre), Battle of Sexes (trois équilibres — deux purs, un mixte — et donc un choix de bassin), Dilemme (équilibre rejeté au bord du simplexe).

Exercice 1 : équilibre de Chicken (Guerre froide)

Appliquez FindFixedPointSimplex au jeu Chicken ( Hawk-Dove) :

	Dove (J2)	Hawk (J2)
Dove (J1)	(3, 3)	(1, 4)
Hawk (J1)	(4, 1)	(0, 0)

Définissez les matrices U1_chicken / U2_chicken.
Itérez la dynamique NashDynamicsStep depuis (0.9, 0.1).
Vérifiez que la limite est l’équilibre mixte (1/3, 2/3) (Dove, Hawk).

Indice : Chicken a deux équilibres purs (Hawk, Dove) et (Dove, Hawk) plus un mixte. La dynamique perturbée converge vers le mixte car elle ne saute jamais exactement aux stratégies pures.

// EXERCICE 1 : equilibre mixte de Chicken
// double[,] U1_chicken = {{3, 1}, {4, 0}};
// double[,] U2_chicken = {{3, 4}, {1, 0}};
// TODO etudiant : iterer NashDynamicsStep depuis (0.9, 0.1) sur ces matrices
//                 et verifier la limite (1/3, 2/3).
Console.WriteLine("Exercice Chicken a completer (voir indice ci-dessus).");

Exercice Chicken a completer (voir indice ci-dessus).

Exercice 2 : Battle of the Sexes — multiplicité d’équilibres

Contrairement à Chicken (un seul équilibre mixte intérieur), le jeu de coordination Battle of the Sexes possède trois équilibres de Nash : deux purs (les deux joueurs coordonnent sur le même choix) et un mixte. C’est l’occasion de vérifier que le théorème de Nash garantit l’existence d’au moins un équilibre, sans garantir l’unicité — la dynamique de meilleure réponse converge alors vers différents points fixes selon le point de départ.

// EXERCICE 2 : Battle of the Sexes — 3 équilibres (2 purs + 1 mixte)
// Matrices (Opéra=0, Foot=1). U1 = préférences époux 1, U2 = époux 2.
// double[,] U1_bos = {{2, 0}, {0, 1}};
// double[,] U2_bos = {{1, 0}, {0, 2}};
// Indice : il existe 2 NE purs — (Opéra,Opéra) = (1,0)×(1,0) et (Foot,Foot) = (0,1)×(0,1) —
//          plus 1 NE mixte intérieur en (2/3, 1/3) pour chaque joueur.
// Étapes :
//   1. Itérer NashDynamicsStep depuis (0.9, 0.1) : vers quel équilibre converge-t-on ?
//   2. Itérer depuis (0.1, 0.9) : confirme-t-on l'autre équilibre pur ?
//   3. Itérer depuis (0.5, 0.5) : la dynamique reste-t-elle au voisinage du NE mixte ?
// TODO étudiant
Console.WriteLine("Exercice 2 (Battle of the Sexes) à compléter : itérez NashDynamicsStep depuis 3 départs.");

Exercice 2 (Battle of the Sexes) à compléter : itérez NashDynamicsStep depuis 3 départs.

Exercice 3 : Dilemme du prisonnier — équilibre dominant au bord du simplexe

Le Dilemme du Prisonnier illustre le cas où une stratégie strictement dominante pousse l’unique équilibre de Nash au bord du simplexe (stratégie pure), sans aucun équilibre mixte intérieur. La dynamique de meilleure réponse doit donc converger vers un sommet — c’est encore une illustration du théorème d’existence de Nash, mais le point fixe se situe sur la frontière plutôt qu’à l’intérieur du simplexe.

// EXERCICE 3 : Dilemme du prisonnier — vérifier l'absence de NE mixte intérieur
// Matrices (Coopérer=0, Défector=1). La défection domine strictement la coopération.
// double[,] U1_pd = {{3, 0}, {5, 1}};
// double[,] U2_pd = {{3, 5}, {0, 1}};
// Indice : (Défector, Défector) = (0,1)×(0,1) est l'unique équilibre de Nash (pur).
// Étapes :
//   1. Itérer NashDynamicsStep depuis (0.8, 0.2) : la trajectoire converge-t-elle vers (0, 1) ?
//   2. Vérifier qu'aucun point fixe intérieur n'existe (la limite est un sommet du simplexe).
//   3. Comparer avec Chicken : pourquoi Chicken admet un NE mixte intérieur mais pas PD ?
//      (Indice : anti-coordination vs dominance stricte.)
// TODO étudiant
Console.WriteLine("Exercice 3 (Dilemme du prisonnier) à compléter : vérifiez la convergence vers le NE pur (0, 1).");

Exercice 3 (Dilemme du prisonnier) à compléter : vérifiez la convergence vers le NE pur (0, 1).

// EXERCICE 2 (supplementaire) : dynamique de meilleure reponse ALTERNEE.
// Au lieu de moyenner BR1 et BR2 simultanement (NashDynamicsStep), alternez-les :
// J1 joue sa BR courante, puis J2 repond a la BR de J1, puis J1 repond a J2, etc.
// Question : la convergence vers (0.5, 0.5) differe-t-elle de la dynamique simutanee ?
// Pourquoi la simultaneite (moyenne des BR) est-elle plus proche de la preuve de Nash
// (qui invoque Brouwer sur f = moyenne des BR) que l'alternance ?
// Indice : PerturbedBR(sigma, U, epsilon=0.1) calcule la BR d'UN joueur (cellule 6).
//          L'alternance = J1 fixe sigma1, J2 repond via PerturbedBR(sigma, U2),
//          puis on recombine (sigma1, sigma2_repondu) -- une etape = 2 sous-etapes.
//          Comparer le nombre d'iterations pour atteindre |sigma - (0.5,0.5)| < 0.01.

// TODO etudiant : iterer une dynamique alternee (J1 puis J2) depuis (0.9, 0.1)
//                 et comparer la vitesse de convergence a NashDynamicsStep.
double[] NashDynamicsStepAlternate(double[] sigma, double[,] u1, double[,] u2, double epsilon = 0.2) {
    // Etape 1 : J1 joue sa BR courante (PerturbedBR sur u1).
    // Etape 2 : J2 repond a la BR de J1 (PerturbedBR sur u2, avec le sigma mis a jour).
    // Etape 3 : recombinez (sigma1_new, sigma2_new) et projetez sur le simplexe.
    return (double[])sigma.Clone();  // TODO etudiant : remplacer par la dynamique alternee
}

Console.WriteLine("Exercice 2 a completer : dynamique alternee vs simultanee.");

Exercice 2 a completer : dynamique alternee vs simultanee.

// EXERCICE 3 (supplementaire) : verificateur d'hypotheses de Brouwer.
// Brouwer exige pour f : Delta -> Delta : (a) continue, (b) Delta convexe compact,
// (c) f(Delta) subset Delta. Implementez un verificateur qui teste ces 3 proprietes
// sur une fonction donnee, puis testez sur PerturbedBR (qui les satisfait) et sur
// une fonction discontinue (qui les viole).
// Indice : Delta = simplexe 2D {(p, 1-p) : p in [0,1]}.
//   (a) continuite : discretisez [0,1] en N pas, verifiez |f(p1)-f(p2)| petit quand
//       |p1-p2| petit (test Lipschitz numerique).
//   (b) Delta convexe compact : toujours vrai pour le simplexe (fait Mathlib/theorique).
//   (c) f(Delta) subset Delta : verifiez ProjectSimplex(f(p)) ~ f(p) sur la grille.
//   Discontinu test : f(p) = p < 0.5 ? (1,0) : (0,1) -- saut, viole (a).

// TODO etudiant : implementez VerifierBrouwer(f, N) renvoyant (continue, stable_simplexe).
(bool continuous, bool stableSimplex) VerifierBrouwer(Func<double[], double[]> f, int N = 50) {
    // Etape 1 : discretisez p in [0,1] en N pas, sigma = (p, 1-p).
    // Etape 2 : continuite -> max |f(p1)-f(p2)| / |p1-p2| borne (test Lipschitz).
    // Etape 3 : stableSimplexe -> ProjectSimplex(f(sigma)) ~ f(sigma) pour tout p.
    return (false, false);  // TODO etudiant
}

Console.WriteLine("Exercice 3 a completer : verificateur d'hypothese de Brouwer.");

Exercice 3 a completer : verificateur d'hypothese de Brouwer.

Bilan

Ce notebook a présenté le théorème d’existence de Nash via Brouwer, jumeau C# du notebook Python :

Point fixe 1D par itération de fonction (convergence des contractions).
Point fixe sur le simplexe avec projection (clipping + normalisation).
Matching Pennies : matrice de gains + gain espéré σ₁·U·σ₂.
Meilleure réponse perturbée (regret matching) — continue, Brouwer s’applique.
Dynamique convergeant vers (0.5, 0.5) = équilibre de Nash.
Visualisation ASCII des trajectoires (équivalent matplotlib du twin Python).

Parité : jumeau C# de GameTheory-04c-NashExistence-Python.ipynb. Les mêmes algorithmes from-scratch (pas de nashpy/pygambit). matplotlib remplacé par visualisation ASCII (Prong B : on enseigne l’algorithme en C# pur). Marathon parité .NET ⇄ Python (#4956), EPIC #3801 (Prong B).

Exercices supplémentaires

Exercice 2 : dynamique de meilleure réponse alternée

Au lieu de moyenner BR₁ et BR₂ simultanément, alternez-les (J1 joue, puis J2 répond, etc.). La convergence diffère-t-elle ? Pourquoi la simultanéité est-elle plus proche de la preuve originale de Nash ?

Exercice 3 : vérificateur d’hypothèses de Brouwer

Implémentez une fonction qui vérifie qu’une fonction f : Δ → Δ satisfait les hypothèses de Brouwer : (a) continue, (b) Δ convexe compact, (c) f(Δ) ⊆ Δ. Tester sur perturbedBR (qui les satisfait) et sur une fonction discontinue (qui les viole — peut ne pas converger).

Références

Nash, J. Equilibrium Points in n-Person Games (PNAS 1950).
Brouwer, L. E. J. Über Abbildung von Mannigfaltigkeiten (1911).
Notebook Python : GameTheory-04c-NashExistence-Python.ipynb.
Marathon parité : #4956.

Retour au sommet

Introduction

Pourquoi le théorème de Brouwer implique Nash

Objectifs d’apprentissage

Prérequis

Durée estimée : 45 minutes

Références

1. Point fixe en dimension 1

Lecture : le point fixe comme équation soluble par itération

2. Point fixe sur le simplexe

Lecture : du segment au simplexe — et 106 itérations au lieu de 6

3. Matching Pennies — matrice de gains et meilleure réponse

Lecture : Matching Pennies — le point fixe égalisateur

4. Dynamique de meilleure réponse — convergence vers Nash

Lecture : trois départs, un seul attracteur — et une symétrie miroir

5. Visualisation ASCII de la trajectoire

Lecture : la trajectoire rendue visible — deux chemins, un seul bassin

Exercice 1 : équilibre de Chicken (Guerre froide)

Exercice 2 : Battle of the Sexes — multiplicité d’équilibres

Exercice 3 : Dilemme du prisonnier — équilibre dominant au bord du simplexe

Bilan

Exercices supplémentaires

Exercice 2 : dynamique de meilleure réponse alternée

Exercice 3 : vérificateur d’hypothèses de Brouwer

Références

Lecture : du segment au simplexe — et `106` itérations au lieu de `6`