Suite de la tranche 1 : équilibres de Nash purs, IESDS, mixte 2x2. Cette tranche 2 résout le gap signalé — un jeu comme Pierre-Feuille-Ciseaux (3x3) n’a ni équilibre pur ni formule close applicable : il faut l’énumération des supports (support enumeration), l’algorithme exact que nashpy exécute sous le capot.
Complémentarité (.NET from-scratch ↔︎ Python/nashpy), pas workaround (#3801)
Twin
Outil
Valeur pédagogique
Python (nashpy)
Game.support_enumeration()
un appel, tous les équilibres d’un jeu quelconque
.NET (this)
énumération des supports + Gauss + vérification
comprendre chaque étape de l’algorithme
La résolution exacte d’un équilibre mixte NxN se décompose en : (1) énumérer les paires de supports de taille égale, (2) pour chaque paire, résoudre le système d’indifférence de l’adversaire (système linéaire → élimination de Gauss), (3) vérifier que la solution est positive (probabilités valides) et best-response (aucune action hors-support ne fait mieux).
Objectifs d’apprentissage (tranche 2)
À la fin de cette tranche, vous saurez : 1. Définir une stratégie mixte (distribution de probabilité) et son support 2. Formuler l’équilibre de Nash mixte comme un problème de système linéaire (indifférence) 3. Implémenter l’élimination de Gauss et la rétro-substitution from-scratch 4. Énumérer les paires de supports et vérifier les conditions d’équilibre 5. Résoudre Pierre-Feuille-Ciseaux, un jeu 3x3 asymétrique, et comparer à nashpy
Algèbre linéaire (système linéaire, élimination de Gauss)
Durée estimée : 50 minutes
Note : Le théorème de Nash (1950) garantit l’existence d’un équilibre, mais sa recherche est algorithmiquement non-triviale. L’énumération des supports (Dantzig 1963, portrayé par Dickerson & Shepard) est exacte mais exponentielle dans le pire cas — Lemke-Howson (1965) est plus efficace en pratique mais complexe à implémenter. Nous faisons l’énumération, la plus pédagogique.
// Setup : support enumeration from-scratch, uniquement la BCL .NET.using Microsoft.DotNet.Interactive;using System;using System.Collections.Generic;using System.Globalization;using System.Linq;using System.Text;CultureInfo.CurrentCulture= CultureInfo.InvariantCulture;stringFI(double x,string fmt="F4")=> x.ToString(fmt, CultureInfo.InvariantCulture);"Environnement prêt — support enumeration from-scratch (BCL .NET seule).".Display();
The below script needs to be able to find the current output cell; this is an easy method to get it.
Environnement prêt — support enumeration from-scratch (BCL .NET seule).
1. Rappel : forme normale (cf. tranche 1)
On reprend la classe NormalFormGame de la tranche 1 (bimatrice \(U_1, U_2\)). Rappel : un profil \((a_1, a_2)\) donne gain \(U_1[a_1,a_2]\) au joueur 1 et \(U_2[a_1,a_2]\) au joueur 2.
// Rappel tranche 1 : jeu sous forme normale a 2 joueurs (self-contained pour cette partie 2).class NormalFormGame{publicstring[] Acts1, Acts2;publicdouble[,] U1, U2;publicNormalFormGame(string[] a1,string[] a2,double[,] u1,double[,] u2){ Acts1 = a1; Acts2 = a2; U1 = u1; U2 = u2;}publicint N1 => Acts1.Length;publicint N2 => Acts2.Length;publicoverridestringToString(){var sb =newStringBuilder(); sb.Append("".PadRight(14));foreach(var b in Acts2) sb.Append(b.PadLeft(10)); sb.AppendLine();for(int i =0; i < N1; i++){ sb.Append(Acts1[i].PadRight(14));for(int j =0; j < N2; j++) sb.Append($"({U1[i,j]:F1},{U2[i,j]:F1})".PadLeft(12)); sb.AppendLine();}return sb.ToString();}}"NormalFormGame prêt.".Display();
NormalFormGame prêt.
2. Stratégies mixtes et support
Une stratégie mixte du joueur 1 est un vecteur de probabilités \(\sigma_1 \in \Delta(A_1)\) (simplexe). Le support\(\mathrm{supp}(\sigma_1) = \{a_1 \in A_1 : \sigma_1(a_1) > 0\}\) est l’ensemble des actions jouées avec probabilité strictement positive.
L’espérance du joueur 1 contre la stratégie \(\sigma_2\) du joueur 2 : \[v_1(a_1; \sigma_2) = \sum_{a_2} \sigma_2(a_2) \cdot U_1[a_1, a_2]\]
Le théorème d’indifférence
À l’équilibre de Nash, le joueur 1 est indifférent entre toutes les actions de son support : \[v_1(a_1; \sigma_2^*) = v_1(a_1'; \sigma_2^*) \quad \forall a_1, a_1' \in \mathrm{supp}(\sigma_1^*)\] (et ce gain commun \(\ge\) celui de toute action hors-support). C’est ce principe d’indifférence qui se traduit en système linéaire.
// Esperance de gain de l'action pure a1 du joueur 1 face a la strategie mixte sigma2.staticdoubleExpectedVsMixed1(NormalFormGame g,int a1,double[] sigma2){double v =0;for(int a2 =0; a2 < g.N2; a2++) v += sigma2[a2]* g.U1[a1, a2];return v;}// Esperance de a2 (joueur 2) face a sigma1.staticdoubleExpectedVsMixed2(NormalFormGame g,int a2,double[] sigma1){double v =0;for(int a1 =0; a1 < g.N1; a1++) v += sigma1[a1]* g.U2[a1, a2];return v;}// Prenons RPS et verifions : si j2 joue uniforme (1/3,1/3,1/3), j1 indifferent entre R/P/S.var RPS =newNormalFormGame(new[]{"R","P","S"},new[]{"R","P","S"},new[,]{{0.0,-1.0,1.0},{1.0,0.0,-1.0},{-1.0,1.0,0.0}},new[,]{{0.0,1.0,-1.0},{-1.0,0.0,1.0},{1.0,-1.0,0.0}});var uniform =new[]{1.0/3,1.0/3,1.0/3};var sb =newStringBuilder();sb.AppendLine("RPS : si j2 joue uniforme, esperance de j1 pour chaque action pure :");for(int a1 =0; a1 <3; a1++) sb.AppendLine($" {RPS.Acts1[a1]} : {FI(ExpectedVsMixed1(RPS, a1, uniform))}");sb.AppendLine(">>> Les 3 esperances sont egales (0) : j1 indifferent -> principe d'indifference verifie.");sb.ToString().Display();
RPS : si j2 joue uniforme, esperance de j1 pour chaque action pure :
R : 0.0000
P : 0.0000
S : 0.0000
>>> Les 3 esperances sont egales (0) : j1 indifferent -> principe d'indifference verifie.
Lecture chiffree — le principe d’indifference en acte. Face a la strategie uniforme \(\sigma_2 = (1/3, 1/3, 1/3)\), la sortie calcule l’esperance de chacune des trois actions pures du joueur 1 : R : 0.0000, P : 0.0000, S : 0.0000. Les trois esperances sont egales a 0, et la ligne « principe d’indifference verifie » le confirme : le joueur 1 est indifferent entre ses trois actions face a ce profil. Ce n’est pas une coincidence : sur un jeu a somme nulle symetrique, chaque action pure affronte les deux autres dans les deux sens (elle en bat une de 1 et se fait battre par la troisieme de 1), donc son esperance face a l’uniforme vaut toujours \(\frac{1}{3}(0 + 1 - 1) = 0\). Cette egalite des esperances est exactement la precondition que la section 4 transforme en systeme lineaire : a l’equilibre mixte, toutes les actions du support doivent offrir la meme esperance, sinon le joueur deplacerait sa probabilite vers celle qui fait mieux.
3. Outil : élimination de Gauss
Pour résoudre un système linéaire\(Ax = b\), on implémente l’élimination de Gauss avec pivot partiel (stabilité numérique), suivie de la rétro-substitution. C’est l’outil de base pour résoudre le système d’indifférence à chaque paire de supports.
Le système d’indifférence pour un support de taille \(k\) donne \(k\) équations (égalité des espérances) \(+\) 1 équation (les probabilités somment à 1) = \(k+1\) équations pour \(k\) inconnues… En fait, l’égalité des espérances donne \(k-1\) équations indépendantes (toutes égales à la première), plus la contrainte de normalisation \(\sum \sigma = 1\) = \(k\) équations pour \(k\) inconnues → système carré résolvable.
// Elimination de Gauss avec pivot partiel + retro-substitution.// Resout Ax = b pour une matrice carree A (n x n). Retourne x ou null si singuliere.staticdouble[]SolveLinear(double[,] A,double[] b){int n = b.Length;// Copie augmentee [A | b]var M =newdouble[n, n +1];for(int i =0; i < n; i++){for(int j =0; j < n; j++) M[i, j]= A[i, j]; M[i, n]= b[i];}// Elimination avant avec pivot partielfor(int col =0; col < n; col++){int piv = col;for(int r = col +1; r < n; r++)if(Math.Abs(M[r, col])> Math.Abs(M[piv, col])) piv = r;if(Math.Abs(M[piv, col])<1e-12)returnnull;// singuliereif(piv != col)for(int j =0; j <= n; j++)(M[col, j], M[piv, j])=(M[piv, j], M[col, j]);for(int r = col +1; r < n; r++){double f = M[r, col]/ M[col, col];for(int j = col; j <= n; j++) M[r, j]-= f * M[col, j];}}// Retro-substitutionvar x =newdouble[n];for(int i = n -1; i >=0; i--){double s = M[i, n];for(int j = i +1; j < n; j++) s -= M[i, j]* x[j]; x[i]= s / M[i, i];}return x;}// Sanity check : resout le systeme trivial 2x2.var A =newdouble[,]{{2.0,1.0},{1.0,-3.0}};var b =newdouble[]{3.0,-2.0};var x =SolveLinear(A, b);$"Test Gauss : 2x + y = 3 ; x - 3y = -2 -> x={FI(x[0])}, y={FI(x[1])} (attendu x=1, y=1)".Display();
Test Gauss : 2x + y = 3 ; x - 3y = -2 -> x=1.0000, y=1.0000 (attendu x=1, y=1)
Lecture chiffree — le banc d’essai de Gauss. La cellule resout le systeme \(2x + y = 3\) ; \(x - 3y = -2\) par elimination de Gauss a pivot partiel puis retro-substitution, et la sortie affiche \(x = 1.0000\), \(y = 1.0000\) en regard de l’attendu \((1, 1)\). Verification immediate : \(2 \times 1 + 1 = 3\) et \(1 - 3 \times 1 = -2\), le systeme est bien resolu. Deux proprietes que cette sortie porte en creux : le pivot partiel ne permute rien ici (aucun pivot nul dans la diagonale), mais c’est lui qui rendra SolveLinear stable sur les systemes de la section 4, ou les matrices d’indifference ne sont pas garanties bien conditionnees ; et l’affichage tombe exactement sur des entiers malgre le format F4 — les 4 decimales ne masquent aucune erreur d’arrondi sur ce banc. C’est ce solveur que SupportEnumeration appellera une fois par joueur et par paire de supports : chaque systeme aura \(k\) equations (egalite des esperances \(k-1\) + normalisation) pour \(k\) inconnues.
4. Algorithme : énumération des supports
Le théorème d’équilibre (Nash) dit qu’un profil \((\sigma_1^*, \sigma_2^*)\) est un équilibre ssi chaque joueur est indifférent sur son support et ne peut améliorer en déviant hors-support. L’algorithme :
Énumérer toutes les paires de supports \((S_1, S_2)\) avec \(|S_1| = |S_2| = k\) (de 1 à \(\min(N_1, N_2)\)).
Pour chaque paire, résoudre le système d’indifférence :
\(\sigma_2\) rend le joueur 1 indifférent sur \(S_1\) (espérances égales) \(+\)\(\sum_{S_2} \sigma_2 = 1\),
\(\sigma_1\) rend le joueur 2 indifférent sur \(S_2\)\(+\)\(\sum_{S_1} \sigma_1 = 1\).
Vérifier : solution strictement positive (toutes proba \(> 0\) sur le support) ET best-response (aucune action hors-support ne fait mieux que l’espérance du support).
Si oui : \((\sigma_1, \sigma_2)\) est un équilibre de Nash.
// Enumere tous les sous-ensembles de taille k d'un ensemble de n elements.static List<List<int>>SubsetsOfSize(int n,int k){var res =new List<List<int>>();var cur =new List<int>();voidRec(int start,int remaining){if(remaining ==0){ res.Add(new List<int>(cur));return;}for(int i = start; i <= n - remaining; i++){ cur.Add(i);Rec(i +1, remaining -1); cur.RemoveAt(cur.Count-1);}}Rec(0, k);return res;}// Verif : sous-ensembles de taille 2 de {0,1,2} = {0,1},{0,2},{1,2}.var s2 =SubsetsOfSize(3,2);var sb =newStringBuilder();sb.AppendLine($"Sous-ensembles de taille 2 de {{0,1,2}} : {string.Join(",", s2.Select(s => "{"+string.Join(",",s)+"}"))} (attendu 3 paires)");sb.ToString().Display();
Sous-ensembles de taille 2 de {0,1,2} : {0,1}, {0,2}, {1,2} (attendu 3 paires)
De l’enumération combinatoire au test d’équilibre
La fonction SubsetsOfSize ci-dessus est le moteur combinatoire : elle engendre tous les sous-ensembles de taille \(k\) d’un ensemble de \(n\) actions — il y en a \(\binom{n}{k}\). Sur Pierre-Feuille-Ciseaux (\(n=3\)), cela ne fait que \(\binom{3}{1}+\binom{3}{2}+\binom{3}{3} = 7\) supports à examiner par joueur.
Le principe de l’énumération des supports (Mangasarian–Stone, 1964 ; Stengel 2002) est de transformer la recherche d’un équilibre de Nash en une énumération finie : pour chaque paire de supports candidats \((S_1, S_2)\) de même taille, on résout le système d’indifférence (la stratégie adverse rend le joueur indifférent entre les actions de son support) puis on vérifie la positivité et la condition de best-response hors-support. Chaque support donne au plus un équilibre candidat — c’est un algorithme complet qui trouve tous les équilibres, au prix d’une complexité combinatoire.
Lecture chiffree — les trois paires de taille 2. La sortie de SubsetsOfSize(3, 2) materialise l’enumeration : {0,1}, {0,2}, {1,2} — les \(\binom{3}{2} = 3\) paires attendues, le code affichant lui-meme « attendu 3 paires ». Deux details que la sortie montre sans les dire : les indices de chaque paire sont strictement croissants ({0,1}, jamais {1,0}) — la recursion ne genere aucune permutation redondante, chaque support n’apparait qu’une fois ; et les trois paires couvrent la totalite des combinaisons de taille 2, ni plus ni moins. C’est ce generateur que SupportEnumeration pilote pour chaque taille de support allant de 1 a \(\min(N_1, N_2)\), et c’est lui qui fait le cout de l’algorithme : \(\binom{10}{5} = 252\) supports de taille 5 pour un jeu 10 × 10, une croissance combinatoire que les exercices de la fin du notebook demandent de chiffrer.
// Support enumeration : trouve TOUS les equilibres de Nash mixtes d'un jeu.// Pour chaque paire de supports (S1,S2) de meme taille :// - resout le systeme d'indifference (sigma2 rend j1 indifferent sur S1 + normalisation)// - resout le systeme d'indifference (sigma1 rend j2 indifferent sur S2 + normalisation)// - verifie positivite stricte + best-response hors-support.static List<(double[] sigma1,double[] sigma2)>SupportEnumeration(NormalFormGame g){var equilibria =new List<(double[],double[])>();int K = Math.Min(g.N1, g.N2);for(int k =1; k <= K; k++){foreach(var S1 inSubsetsOfSize(g.N1, k))foreach(var S2 inSubsetsOfSize(g.N2, k)){// --- sigma2 : rend j1 indifferent sur S1 + somme a 1 ---// k-1 equations : ExpectedVsMixed1(S1[i]) = ExpectedVsMixed1(S1[0]) pour i=1..k-1// <=> sum_a2 sigma2[a2] * (U1[S1[i],a2] - U1[S1[0],a2]) = 0// 1 equation de normalisation : sum_{a2 in S2} sigma2[a2] = 1// Variables : sigma2[a2] pour a2 in S2 (k inconnues).var A2 =newdouble[k, k];var b2 =newdouble[k];for(int i =1; i < k; i++)for(int jj =0; jj < k; jj++){int a2 = S2[jj]; A2[i -1, jj]= g.U1[S1[i], a2]- g.U1[S1[0], a2];}for(int jj =0; jj < k; jj++) A2[k -1, jj]=1.0;// normalisation b2[k -1]=1.0;var sol2 =SolveLinear(A2, b2);if(sol2 ==null)continue;if(sol2.Any(v => v <-1e-9))continue;// probabilite negative -> invalide// --- sigma1 : rend j2 indifferent sur S2 ---var A1 =newdouble[k, k];var b1 =newdouble[k];for(int j =1; j < k; j++)for(int ii =0; ii < k; ii++){int a1 = S1[ii]; A1[j -1, ii]= g.U2[a1, S2[j]]- g.U2[a1, S2[0]];}for(int ii =0; ii < k; ii++) A1[k -1, ii]=1.0; b1[k -1]=1.0;var sol1 =SolveLinear(A1, b1);if(sol1 ==null)continue;if(sol1.Any(v => v <-1e-9))continue;// --- Reconstruit les vecteurs sigma complets ---var sigma1 =newdouble[g.N1];var sigma2 =newdouble[g.N2];for(int ii =0; ii < k; ii++) sigma1[S1[ii]]= sol1[ii];for(int jj =0; jj < k; jj++) sigma2[S2[jj]]= sol2[jj];// --- Best-response check : aucune action hors-support ne fait mieux ---double v1sup =ExpectedVsMixed1(g, S1[0], sigma2);double v2sup =ExpectedVsMixed2(g, S2[0], sigma1);bool br1ok =true, br2ok =true;for(int a1 =0; a1 < g.N1; a1++)if(sigma1[a1]<1e-9&&ExpectedVsMixed1(g, a1, sigma2)> v1sup +1e-9) br1ok =false;for(int a2 =0; a2 < g.N2; a2++)if(sigma2[a2]<1e-9&&ExpectedVsMixed2(g, a2, sigma1)> v2sup +1e-9) br2ok =false;if(!br1ok ||!br2ok)continue; equilibria.Add((sigma1, sigma2));}}return equilibria;}"Support enumeration prêt (Gauss + indifference + best-response check).".Display();
Support enumeration prêt (Gauss + indifference + best-response check).
Appliquons l’algorithme au jeu symétrique \(3 \times 3\) Pierre-Feuille-Ciseaux. L’antisymétrie de la matrice de gain (\(u_i = -u_j\)) impose qu’aucun joueur n’ait d’avantage systématisque : la théorie prédit l’équilibre uniforme\(\sigma = (1/3, 1/3, 1/3)\) pour les deux joueurs, qui rend chaque action indifférente (espérance nulle) et est l’unique best-response à lui-même.
C’est précisément ce que l’énumération des supports doit retrouver : le support complet \(\{R, P, S\}\) produit, via le système d’indifférence \(3 \times 3\), la solution uniforme — et les supports de taille 1 et 2 sont rejetés (pas d’équilibre en stratégies pures, ni en support réduit). La cellule suivante exécute cette résolution et affiche le vecteur de probabilité trouvé.
// Resolution de Pierre-Feuille-Ciseaux (3x3) via support enumeration.var RPS =newNormalFormGame(new[]{"R","P","S"},new[]{"R","P","S"},new[,]{{0.0,-1.0,1.0},{1.0,0.0,-1.0},{-1.0,1.0,0.0}},new[,]{{0.0,1.0,-1.0},{-1.0,0.0,1.0},{1.0,-1.0,0.0}});var eqs =SupportEnumeration(RPS);var sb =newStringBuilder();sb.AppendLine($"=== Pierre-Feuille-Ciseaux : {eqs.Count} equilibre(s) de Nash (mixte) ===");foreach(var(s1, s2)in eqs){ sb.Append("sigma1 = ");for(int i =0; i <3; i++) sb.Append($"{RPS.Acts1[i]}:{FI(s1[i], "F3")} "); sb.Append("; sigma2 = ");for(int i =0; i <3; i++) sb.Append($"{RPS.Acts2[i]}:{FI(s2[i], "F3")} "); sb.AppendLine();}sb.AppendLine(">>> Equilibre uniforme (1/3, 1/3, 1/3) pour les deux joueurs, comme prevu par symetrie.");sb.AppendLine(" Valeur du jeu (zero-sum) : esperance = 0 pour chacun.");sb.ToString().Display();
=== Pierre-Feuille-Ciseaux : 1 equilibre(s) de Nash (mixte) ===
sigma1 = R:0.333 P:0.333 S:0.333 ; sigma2 = R:0.333 P:0.333 S:0.333
>>> Equilibre uniforme (1/3, 1/3, 1/3) pour les deux joueurs, comme prevu par symetrie.
Valeur du jeu (zero-sum) : esperance = 0 pour chacun.
Interprétation – symétrie et uniformité. L’algorithme retrouve l’équilibre uniforme \((\tfrac{1}{3}, \tfrac{1}{3}, \tfrac{1}{3})\) sans qu’on le lui indique. C’est une conséquence directe de la symétrie de la matrice de paiement : aucune action n’est distinguable a priori, donc aucune ne peut recevoir plus de poids qu’une autre a l’équilibre. La valeur du jeu est nulle (jeu à somme nulle équitable). Le point pédagogique : la support enumeration redécouvre ce résultat par le calcul (résolution du système d’indifférence), et non par un argument de symétrie injecté à la main.
5. Un jeu 3x3 asymétrique
Pour montrer que l’algorithme gère le non-symétrique, prenons un jeu où RPS est biaisé : la matière (Rock) rapporte double. L’équilibre n’est plus uniforme — la résolution exacte le révèle.
// RPS biaise : Rock rapporte double pour j1. Equilibre non-uniforme.var Biased =newNormalFormGame(new[]{"R","P","S"},new[]{"R","P","S"},new[,]{{0.0,-1.0,2.0},{1.0,0.0,-1.0},{-2.0,1.0,0.0}},// j1 : S bat R = +2 (au lieu de +1)new[,]{{0.0,1.0,-2.0},{-1.0,0.0,1.0},{2.0,-1.0,0.0}});var sb =newStringBuilder();sb.AppendLine("=== RPS biaise (S bat R rapporte double) ===");sb.AppendLine(Biased.ToString());var eqs =SupportEnumeration(Biased);sb.AppendLine($"Equilibres trouves : {eqs.Count}");foreach(var(s1, s2)in eqs){ sb.Append("sigma1 = ");for(int i =0; i <3; i++) sb.Append($"{Biased.Acts1[i]}:{FI(s1[i], "F3")} "); sb.AppendLine(); sb.Append("sigma2 = ");for(int i =0; i <3; i++) sb.Append($"{Biased.Acts2[i]}:{FI(s2[i], "F3")} "); sb.AppendLine();// valeurdouble v1 =0;for(int a1 =0; a1 <3; a1++)for(int a2 =0; a2 <3; a2++) v1 += s1[a1]* s2[a2]* Biased.U1[a1, a2]; sb.AppendLine($"Valeur du jeu (esperance j1) = {FI(v1)}");}sb.ToString().Display();
=== RPS biaise (S bat R rapporte double) ===
R P S
R (0,0,0,0) (-1,0,1,0) (2,0,-2,0)
P (1,0,-1,0) (0,0,0,0) (-1,0,1,0)
S (-2,0,2,0) (1,0,-1,0) (0,0,0,0)
Equilibres trouves : 1
sigma1 = R:0.250 P:0.500 S:0.250
sigma2 = R:0.250 P:0.500 S:0.250
Valeur du jeu (esperance j1) = 0.0000
Interprétation – rupture de symétrie, Paper devient modal. Doubler le gain de Rock contre Scissors brise la symétrie : Rock devient une menace renforcée (il bat Scissors de +2 au lieu de +1). Anticipant cela, les deux joueurs déplacent leur probabilité vers Paper – l’action qui bat Rock – qui atteint 50 %, tandis que Rock et Scissors tombent à 25 % chacun. La valeur du jeu reste nulle (le biais est symétrique entre les deux joueurs). Cet équilibre non-uniforme est exactement le genre de résultat non evident à l’intuition que la support enumeration révèle : aucun argument heuristique simple ne dirait “Paper 50 %” sans résoudre le système.
6. Vérification : le Dilemme du Prisonnier
Sur le Dilemme du Prisonnier, la support enumeration doit retrouver (Defect, Defect) comme unique équilibre — un support de taille 1 (stratégie pure). C’est le test que l’algorithme gère aussi les équilibres purs (non seulement mixtes).
// Dilemme du Prisonnier : support enumeration doit retrouver (Defect,Defect) comme unique equilibre.var PD =newNormalFormGame(new[]{"Coop","Defect"},new[]{"Coop","Defect"},new[,]{{3.0,0.0},{5.0,1.0}},new[,]{{3.0,5.0},{0.0,1.0}});var eqs =SupportEnumeration(PD);var sb =newStringBuilder();sb.AppendLine($"=== Dilemme du Prisonnier : {eqs.Count} equilibre(s) ===");foreach(var(s1, s2)in eqs){ sb.Append("sigma1 = ");for(int i =0; i <2; i++) sb.Append($"{PD.Acts1[i]}:{FI(s1[i], "F3")} "); sb.AppendLine(); sb.Append("sigma2 = ");for(int i =0; i <2; i++) sb.Append($"{PD.Acts2[i]}:{FI(s2[i], "F3")} "); sb.AppendLine();}sb.AppendLine(">>> Unique equilibre = (Defect, Defect) en strategies pures (support taille 1).");sb.AppendLine(" L'algorithme retrouve l'equilibre pur, pas seulement mixte.");sb.ToString().Display();
=== Dilemme du Prisonnier : 1 equilibre(s) ===
sigma1 = Coop:0.000 Defect:1.000
sigma2 = Coop:0.000 Defect:1.000
>>> Unique equilibre = (Defect, Defect) en strategies pures (support taille 1).
L'algorithme retrouve l'equilibre pur, pas seulement mixte.
Interprétation – équilibre pur, support de taille 1. Le Dilemme du Prisonnier n’a pas d’équilibre mixte intéressant : son unique équilibre de Nash est la stratégie pure \((\text{Defect}, \text{Defect})\). C’est un support de taille 1. L’intérêt ici est de montrer que la support enumeration ne se limite pas aux mélanges – elle énumère les supports de toutes tailles, et retrouve donc aussi les équilibres purs. La méthode est générale : pas besoin de traiter séparément le cas pur et le cas mixte.
7. Pile ou Face (Matching Pennies) : équilibre mixte 2x2
Sur ce jeu zero-sum sans équilibre pur, la support enumeration doit retrouver le mélange (0.5, 0.5) pour les deux joueurs — confirmant le résultat de la formule close de la tranche 1.
// Pile ou Face : support enumeration doit retrouver (0.5,0.5).var MP =newNormalFormGame(new[]{"Heads","Tails"},new[]{"Heads","Tails"},new[,]{{1.0,-1.0},{-1.0,1.0}},new[,]{{-1.0,1.0},{1.0,-1.0}});var eqs =SupportEnumeration(MP);var sb =newStringBuilder();sb.AppendLine($"=== Pile ou Face : {eqs.Count} equilibre(s) ===");foreach(var(s1, s2)in eqs){ sb.Append("sigma1 = ");for(int i =0; i <2; i++) sb.Append($"{MP.Acts1[i]}:{FI(s1[i], "F3")} "); sb.Append("; sigma2 = ");for(int i =0; i <2; i++) sb.Append($"{MP.Acts2[i]}:{FI(s2[i], "F3")} "); sb.AppendLine();}sb.AppendLine(">>> Melange (0.5,0.5) retrouve, valeur 0 (confirme la tranche 1).");sb.ToString().Display();
=== Pile ou Face : 1 equilibre(s) ===
sigma1 = Heads:0.500 Tails:0.500 ; sigma2 = Heads:0.500 Tails:0.500
>>> Melange (0.5,0.5) retrouve, valeur 0 (confirme la tranche 1).
Interprétation – équilibre mixte 2x2 sans équilibre pur. Pile ou Face (Matching Pennies) n’a aucun équilibre pur (jeu à somme nulle sans point-selle en stratégies pures). L’unique équilibre est le mélange uniforme \((0{,}5\,;\,0{,}5)\) : chaque joueur rend l’autre indifférent entre ses deux actions. La support enumeration retrouve ce résultat sur le support de taille 2, confirmant la formule close de la tranche 1.
Ce notebook démontre ainsi les quatre régimes possibles d’un équilibre de Nash mélange/pur : uniforme par symétrie (RPS), non-uniforme par asymétrie (RPS biaisé), pur par stratégie dominante (Prisonnier), et mixte sans équilibre pur (Pile ou Face).
// === Pont Gambit CLI : gambit-enummixed comme oracle SOTA pour les equilibres de Nash mixtes ===// Usings supplementaires (IO pour File/Path, Diagnostics pour Process) : non declares dans le setup.using System.IO;using System.Diagnostics;// La cellule precedente (BCL .NET seule) implemente le SUPPORT ENUMERATION from-scratch :// enumeration de toutes les paires de supports (S1,S2) + Gauss + best-response check.// Gambit (McKelvey-McLennan-Page, outil de reference GPL-2.0) resout le MEME probleme via CLI.// On serialise le jeu au format .nfg (cf GameTheory-4-NashEquilibrium-Csharp), on invoque// gambit-enummixed, puis on COMPARE numeriquement les deux sorties jeu par jeu.// Axe binding (#10459) : CLI Process.Start pur — AUCUN binding .NET/NuGet, AUCUN P/Invoke,// AUCUNE IKVM, AUCUN PythonNet. Gambit est un executable autonome (verdict SOTA-OK une fois execute).staticstringToNfg(NormalFormGame g,string title){var sb =newStringBuilder(); sb.Append($"NFG 1 R \"{title}\" {{ \"Player 1\"\"Player 2\" }} {{ {g.N1} {g.N2} }}\n");var nums =new List<string>();// Convention .nfg (GameTheory-4) : j2 (colonne) boucle EXTERNE, j1 (ligne) boucle INTERNE,// payoffs INTERLEVES [U1[i,j], U2[i,j]] — j1 varie le plus vite.for(int j =0; j < g.N2; j++)for(int i =0; i < g.N1; i++){ nums.Add(g.U1[i, j].ToString("G6", CultureInfo.InvariantCulture)); nums.Add(g.U2[i, j].ToString("G6", CultureInfo.InvariantCulture));} sb.Append(string.Join(" ", nums));return sb.ToString();}// Resolution portable du binaire (meme recherche que GT-10) : GAMBIT_HOME d'abord, puis les// installations Windows connues, ou /usr/bin, /usr/local/bin et /opt/homebrew/bin sous Linux// et macOS. Les binaires Gambit ne portent le suffixe .exe que sous Windows.staticstringFindGambit(string binary){bool win = OperatingSystem.IsWindows();string exe = win ? binary +".exe": binary;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;thrownewFileNotFoundException( $"{exe} introuvable (GAMBIT_HOME, installations standard). Installer Gambit (gambit-project.org) ou definir GAMBIT_HOME.",string.Join(", ", candidates));}static List<(double[] s1,double[] s2)>RunGambitEnumMixed(NormalFormGame g,string title,int decimals =6){string exePath =FindGambit("gambit-enummixed");string nfgPath = Path.Combine(Path.GetTempPath(), $"{title}_enummixed.nfg"); File.WriteAllText(nfgPath,ToNfg(g, title));var psi =new ProcessStartInfo{ FileName = exePath, Arguments = $"-d {decimals} -q \"{nfgPath}\"", RedirectStandardOutput =true, RedirectStandardError =true, UseShellExecute =false, CreateNoWindow =true,};var p = Process.Start(psi);string stdout = p.StandardOutput.ReadToEnd(); p.WaitForExit(10000);var eqs =new List<(double[] s1,double[] s2)>();foreach(var line in stdout.Split('\n', StringSplitOptions.RemoveEmptyEntries)){var tok = line.Trim().Split(',');if(tok.Length<1+ g.N1+ g.N2|| tok[0]!="NE")continue;var s1 =newdouble[g.N1];var s2 =newdouble[g.N2];for(int i =0; i < g.N1; i++) s1[i]=double.Parse(tok[1+ i], CultureInfo.InvariantCulture);for(int j =0; j < g.N2; j++) s2[j]=double.Parse(tok[1+ g.N1+ j], CultureInfo.InvariantCulture); eqs.Add((s1, s2));}return eqs;}// Exploitabilite d'un profil (s1,s2) = somme des gains de deviation unilateraux.// = [max_a1 E1[a1,s2] - E1[s1,s2]] + [max_a2 E2[s1,a2] - E2[s1,s2]]// A un equilibre de Nash, EXPLOITABILITE = 0 (aucune deviation profitable : 1er principe).staticdoubleExploitability(NormalFormGame g,double[] s1,double[] s2){double br1 =ExpectedVsMixed1(g,0, s2);for(int a1 =1; a1 < g.N1; a1++){double e =ExpectedVsMixed1(g, a1, s2);if(e > br1) br1 = e;}double e1mix =0;for(int a1 =0; a1 < g.N1; a1++) e1mix += s1[a1]*ExpectedVsMixed1(g, a1, s2);double br2 =ExpectedVsMixed2(g,0, s1);for(int a2 =1; a2 < g.N2; a2++){double e =ExpectedVsMixed2(g, a2, s1);if(e > br2) br2 = e;}double e2mix =0;for(int a2 =0; a2 < g.N2; a2++) e2mix += s2[a2]*ExpectedVsMixed2(g, a2, s1);return(br1 - e1mix)+(br2 - e2mix);}// Distance-sup entre deux profils : max|s1-s1'| + max|s2-s2'|.staticdoubleProfileDistance(double[] s1,double[] s2,double[] t1,double[] t2){double d1 =0, d2 =0;for(int i =0; i < s1.Length; i++) d1 = Math.Max(d1, Math.Abs(s1[i]- t1[i]));for(int j =0; j < s2.Length; j++) d2 = Math.Max(d2, Math.Abs(s2[j]- t2[j]));return d1 + d2;}// --- Comparaison from-scratch vs Gambit sur les 4 jeux canoniques ---var games =new[]{("RPS", RPS),("Biased", Biased),("PD", PD),("MP", MP),};var sb =newStringBuilder();sb.AppendLine("=== Pont Gambit : from-scratch (BCL .NET) vs gambit-enummixed (oracle SOTA) ===");sb.AppendLine("Les deux calculent TOUS les equilibres de Nash mixtes par enumeration de supports.");sb.AppendLine();int allMatch =0, allTotal =0;foreach(var(name, game)in games){var scratch =SupportEnumeration(game);var gambit =RunGambitEnumMixed(game, name); sb.AppendLine($"--- {name} ({game.N1}x{game.N2}) : from-scratch={scratch.Count} | gambit={gambit.Count} ---");int matched =0;double maxDist =0;foreach(var(gs1, gs2)in gambit){double best =double.MaxValue;foreach(var(sc1, sc2)in scratch){double d =ProfileDistance(sc1, sc2, gs1, gs2);if(d < best) best = d;}if(best <1e-3) matched++; maxDist = Math.Max(maxDist, best ==double.MaxValue?0: best); sb.AppendLine($" gambit [{string.Join(",", gs1.Select(x => FI(x, "F3")))}] "+ $"[{string.Join(",", gs2.Select(x => FI(x, "F3")))}] "+ $"-> dist_vs_scratch={FI(best == double.MaxValue ? -1 : best, "F6")}, "+ $"exploitabilite={FI(Exploitability(game, gs1, gs2), "F6")}");}bool ok = matched == gambit.Count&& matched == scratch.Count; sb.AppendLine($" >>> {(ok ? "CORRESPOND" : "DIVERGENCE")} : {matched}/{gambit.Count} appareilles "+ $"(dist_max={FI(maxDist, "F6")}, exploit=0 = equilibre de Nash verifie)"); allMatch += matched; allTotal += gambit.Count;}sb.AppendLine();sb.AppendLine($">>> Bilan : {allMatch}/{allTotal} equilibres gambit apparaillent le from-scratch "+ $"(dist < 1e-3). Exploitabilite ~ 0 partout -> ce sont bien des equilibres de Nash.");sb.AppendLine(" Le from-scratch (BCL) et l'oracle SOTA Gambit donnent le MEME resultat :");sb.AppendLine(" l'algorithme de la cellule precedente est correct, valide par l'outil de reference.");sb.ToString().Display();
=== Pont Gambit : from-scratch (BCL .NET) vs gambit-enummixed (oracle SOTA) ===
Les deux calculent TOUS les equilibres de Nash mixtes par enumeration de supports.
--- RPS (3x3) : from-scratch=1 | gambit=1 ---
gambit [0.333,0.333,0.333] [0.333,0.333,0.333] -> dist_vs_scratch=0.000001, exploitabilite=0.000000
>>> CORRESPOND : 1/1 appareilles (dist_max=0.000001, exploit=0 = equilibre de Nash verifie)
--- Biased (3x3) : from-scratch=1 | gambit=1 ---
gambit [0.250,0.500,0.250] [0.250,0.500,0.250] -> dist_vs_scratch=0.000000, exploitabilite=0.000000
>>> CORRESPOND : 1/1 appareilles (dist_max=0.000000, exploit=0 = equilibre de Nash verifie)
--- PD (2x2) : from-scratch=1 | gambit=1 ---
gambit [0.000,1.000] [0.000,1.000] -> dist_vs_scratch=0.000000, exploitabilite=0.000000
>>> CORRESPOND : 1/1 appareilles (dist_max=0.000000, exploit=0 = equilibre de Nash verifie)
--- MP (2x2) : from-scratch=1 | gambit=1 ---
gambit [0.500,0.500] [0.500,0.500] -> dist_vs_scratch=0.000000, exploitabilite=0.000000
>>> CORRESPOND : 1/1 appareilles (dist_max=0.000000, exploit=0 = equilibre de Nash verifie)
>>> Bilan : 4/4 equilibres gambit apparaillent le from-scratch (dist < 1e-3). Exploitabilite ~ 0 partout -> ce sont bien des equilibres de Nash.
Le from-scratch (BCL) et l'oracle SOTA Gambit donnent le MEME resultat :
l'algorithme de la cellule precedente est correct, valide par l'outil de reference.
Pont vers l’outil de reference : Gambit (oracle SOTA)
La cellule precedente implemente l’enumeration de supports “a la main” (BCL .NET seule). Pour valider cet algorithme, on le confronte a Gambit (gambit-project.sourceforge.net), l’outil de reference du calcul d’equilibres de Nash (McKelvey, McLennan, Page), via son binaire gambit-enummixed.
Mecanique du pont. Le jeu est serialise au format .nfg (deja utilise en tranche 4), puis passe au solveur Gambit qui enumere les supports et resout les memes systemes d’indifference. Le pont est un pur appel CLI via Process.Start : aucun binding .NET, aucun NuGet, aucune couche d’interoperabilite. Gambit etant un programme autonome sous licence GPL-2.0, le liaison par ligne de commande evite tout probleme de licence/compatibilite.
Deux metriques chiffrees guident la comparaison :
Distance\(\max_i |\sigma^{\text{BCL}}_i - \sigma^{\text{Gambit}}_i|\) entre profils appareilles : \(< 10^{-3}\) confirme que les deux methodes convergent vers le meme equilibre.
Exploitabilite\(\max_{a_1} E_1[a_1,\sigma_2] - E_1[\sigma_1,\sigma_2]\) (symetrisee pour le joueur 2) : nulle a un equilibre de Nash par construction (aucune deviation unilaterale profitable). C’est un test independant de Gambit : il ne fait que reformuler le premier principe (best-response).
Pourquoi ce pont n’est pas superflu (non-degenerescence). Les 4 jeux canoniques couvrent les cas ou l’equilibre mixte est reellement mixte : RPS (uniformite par symetrie), RPS biaise (equilibre asymetrique\(0{,}25/0{,}50/0{,}25\)), Matching Pennies (melange \(0{,}5/0{,}5\)) et le Dilemme du Prisonnier (equilibre pur retrouve en support de taille 1). L’enumeration de supports est exactement l’outil qui discrimine ces structures — un simple argmax n’y suffirait pas.
Exercice 1 : Bataille des Sexes (3 équilibres)
Appliquez SupportEnumeration à la Bataille des Sexes (cf. tranche 1). Combien d’équilibres trouve-t-on ? Vous devez retrouver les 2 équilibres purs (Opera,Opera) et (Foot,Foot) plus l’équilibre mixte (0.667, 0.333) — soit 3 équilibres au total. Vérifiez firsthand.
// Exercice 1 : SupportEnumeration sur la Bataille des Sexes (etudiant a completer)// Indice 1 : construire le jeu BoS (cf. tranche 1).// Indice 2 : appeler SupportEnumeration(BoS) et afficher chaque equilibre.// Attendu : 3 equilibres (2 purs + 1 mixte).// TODO etudiant"Exercice 1 à compléter — Bataille des Sexes : 3 équilibres (2 purs + 1 mixte).".Display();
Exercice 1 à compléter — Bataille des Sexes : 3 équilibres (2 purs + 1 mixte).
Le jeu RPSLS (5 actions) est zero-sum symétrique. Complétez le stub pour définir la bimatrice 5x5 (règles : Rock écrase Ciseaux/Lézard, Papier couvre Rock/désavoue Spock, Ciseaux coupe Papier/décapite Lézard, Lézard mange Papier/empoisonne Spock, Spock écrase Ciseaux/fait fondre Rock) et lancez SupportEnumeration. L’équilibre attendu est-il uniforme (1/5 chacune) ? Combien d’équilibres le jeu admet-il ?
// Exercice 2 : RPSLS 5x5 via support enumeration (etudiant a completer)// Indice : matrice 5x5 zero-sum, +1 si l'action de ligne bat celle de colonne, -1 sinon, 0 si egal.// Actions : R, P, S, L, Sp.// TODO etudiant : construire la bimatrice et appeler SupportEnumeration."Exercice 2 à compléter — RPSLS 5x5 : définir la bimatrice et trouver l'équilibre.".Display();
Exercice 2 à compléter — RPSLS 5x5 : définir la bimatrice et trouver l'équilibre.
Exercice 3 : Complexité de l’énumération
L’énumération des supports est exponentielle : pour un jeu NxN, le nombre de paires de supports est \(\sum_{k=1}^{N} \binom{N}{k}^2 = \binom{2N}{N} - 1\). Complétez le stub pour calculer ce nombre pour \(N \in \{2, 4, 6, 8, 10\}\) et observer la croissance. À partir de quel \(N\) l’algorithme devient-il impraticable ? (Indice : \(\binom{20}{10} = 184\,756\) paires pour N=10.)
// Exercice 3 : complexite de l'enumeration des supports (etudiant a completer)// Indice : C(2N,N) - 1 = nombre de paires de supports. Calculer pour N in {2,4,6,8,10}.// TODO etudiantint[] Ns ={2,4,6,8,10};"Exercice 3 à compléter — complexité C(2N,N)-1 pour N in {2,4,6,8,10}.".Display();
Exercice 3 à compléter — complexité C(2N,N)-1 pour N in {2,4,6,8,10}.
Conclusion (tranche 2)
Cette tranche 2 a résolu le gap de la tranche 1 : la support enumeration permet de calculer tous les équilibres de Nash (purs et mixtes) d’un jeu quelconque.
Récapitulatif
Concept
Implémentation C#
Espérance vs stratégie mixte
ExpectedVsMixed1/2
Élimination de Gauss
SolveLinear (pivot partiel + rétro-substitution)
Sous-ensembles de taille k
SubsetsOfSize (énumération récursive)
Support enumeration
SupportEnumeration (indifférence + best-response)
Points clés
Indifférence = système linéaire : le principe d’indifférence de Nash se traduit en un système linéaire résolvable par Gauss — c’est le pont entre théorie des jeux et algèbre linéaire.
Équilibres purs et mixtes unifiés : un équilibre pur est un cas particulier de support (taille 1) — la même algorithme les trouve tous.
Complexité exponentielle : le nombre de paires de supports croît comme \(\binom{2N}{N}\) — impraticable au-delà de N≈10. En pratique, on utilise Lemke-Howson (1965), plus rapide mais complexe.