Twin .NET du notebook GameTheory-02-NormalForm-Python (Python/nashpy). Ce notebook implemente les concepts fondamentaux de la théorie des jeux stratégique from-scratch en C#/.NET, sans librairie externe.
Complementarite (.NET from-scratch ↔︎ Python/nashpy), pas workaround (#3801)
calculer vite un equilibre sur des jeux quelconques
.NET (this)
implementation from-scratch en C#
comprendre la meilleure reponse, la dominance et le principe d’indifference de l’interieur
Il n’existe pas d’equivalent NuGet maintenu et didactique a nashpy en .NET. Le twin .NET tire parti de cette absence pour demontrer les algorithmes a la main — c’est précisément l’occasion pedagogique (cf Search-11 SA, Tweety-5 Dung : même demarche complementaire).
Objectifs d’apprentissage (tranche 1)
A la fin de cette tranche, vous saurez : 1. Modeliser un jeu sous forme normale a 2 joueurs (matrices de gains) 2. Calculer la meilleure reponse (best response) et identifier les equilibres de Nash purs 3. Appliquer l’elimination iteree des stratégies strictement dominees (IESDS) 4. Deriver l’equilibre de Nash mixte d’un jeu 2x2 (formule close par indifference) 5. Distinguer les jeux a equilibre unique, multiples, ou sans equilibre pur
GameTheory-1 (Setup) — context general de la théorie des jeux
Duree estimee : 45 minutes
Note : Un equilibre de Nash (Nash, 1950) est un profil de stratégies dont aucun joueur n’a intérêt a devier unilateralement. C’est le concept central de la théorie des jeux non-cooperatifs. Etonnamment, Nash a prouve que tout jeu fini admet au moins un equilibre (pur ou mixte) — un résultat d’existence puissant.
// Setup : aucune dépendance externe — théorie des jeux 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;// Culture invariant pour les formats numeriques (eviter "0,5" vs "0.5").CultureInfo.CurrentCulture= CultureInfo.InvariantCulture;"Environnement pret — theorie des jeux strategique 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 pret — theorie des jeux strategique from-scratch (BCL .NET seule).
1. Jeux sous forme normale
Un jeu sous forme normale a 2 joueurs est défini par : - Les ensembles d’actions\(A_1\) (joueur ligne) et \(A_2\) (joueur colonne), - Deux matrices de gains\(u_1 \in \mathbb{R}^{|A_1| \times |A_2|}\) et \(u_2 \in \mathbb{R}^{|A_1| \times |A_2|}\), ou \(u_1[a_1, a_2]\) est le gain du joueur 1 quand il joue \(a_1\) et le joueur 2 joue \(a_2\).
Un profil\((a_1, a_2)\) est un choix d’action pour chaque joueur. Le jeu est bimatrice : on note \(G = (A_1, A_2, u_1, u_2)\).
Convention
Les gains sont a maximiser. Dans un jeu a somme nulle (zero-sum), \(u_2 = -u_1\) (ce que gagne l’un, l’autre le perd). Sinon le jeu est a somme non-nulle.
// Jeu sous forme normale a 2 joueurs. Matrices de gains indexees [action_joueur1, action_joueur2].class NormalFormGame{publicstring[] Acts1, Acts2;// labels des actionspublicdouble[,] U1, U2;// gains joueur 1 et joueur 2 (U1[a1,a2], U2[a1,a2])publicNormalFormGame(string[] acts1,string[] acts2,double[,] u1,double[,] u2){ Acts1 = acts1; Acts2 = acts2; U1 = u1; U2 = u2;}publicint N1 => Acts1.Length;publicint N2 => Acts2.Length;// Format invariant (point decimal) — evite la collision virgule-decimal / virgule-tuple// dans les sorties (ex. "(3.0, 3.0)" clair, pas "(3,0,3,0)" ambigu en culture FR).staticstringFI(double x,string fmt ="F1")=> x.ToString(fmt, CultureInfo.InvariantCulture);// Affichage de la bimatrice.publicoverridestringToString(){var sb =newStringBuilder(); sb.Append("".PadRight(14));foreach(var b in Acts2) sb.Append((b +"").PadLeft(13)); sb.AppendLine();for(int i =0; i < N1; i++){ sb.Append((Acts1[i]+"").PadRight(14));for(int j =0; j < N2; j++) sb.Append($"({FI(U1[i,j])},{FI(U2[i,j])})".PadLeft(13)); sb.AppendLine();}return sb.ToString();}}"Classe NormalFormGame prete (bimatrice U1/U2, affichage (u1,u2) par cellule).".Display();
Classe NormalFormGame prete (bimatrice U1/U2, affichage (u1,u2) par cellule).
2. Jeux classiques 2x2
Quatre jeux canoniques couvrent les configurations d’equilibre : - Dilemme du Prisonnier : un seul equilibre (Defect, Defect) — la defection domine. - Bataille des Sexes : deux equilibres purs de coordination (asymetrique). - Pile ou Face (Matching Pennies) : zero-sum, aucun equilibre pur — il faut du mixte. - Jeux de coordination purs : deux equilibres symetriques.
// Quatre jeux classiques 2x2 (gains a maximiser).var PD =newNormalFormGame(new[]{"Coop","Defect"},new[]{"Coop","Defect"},new[,]{{3.0,0.0},{5.0,1.0}},// U1 : ligne = joueur 1new[,]{{3.0,5.0},{0.0,1.0}});// U2 : colonne = joueur 2var BoS =newNormalFormGame(new[]{"Opera","Foot"},new[]{"Opera","Foot"},new[,]{{2.0,0.0},{0.0,1.0}},new[,]{{1.0,0.0},{0.0,2.0}});var MP =newNormalFormGame(// Pile ou Face (zero-sum)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 Coord =newNormalFormGame(new[]{"Left","Right"},new[]{"Left","Right"},new[,]{{1.0,0.0},{0.0,1.0}},new[,]{{1.0,0.0},{0.0,1.0}});var sb =newStringBuilder();sb.AppendLine("=== Dilemme du Prisonnier ==="); sb.AppendLine(PD.ToString());sb.AppendLine("=== Bataille des Sexes ==="); sb.AppendLine(BoS.ToString());sb.AppendLine("=== Pile ou Face (zero-sum) ==="); sb.AppendLine(MP.ToString());sb.AppendLine("=== Coordination ==="); sb.AppendLine(Coord.ToString());sb.ToString().Display();
=== Dilemme du Prisonnier ===
Coop Defect
Coop (3.0,3.0) (0.0,5.0)
Defect (5.0,0.0) (1.0,1.0)
=== Bataille des Sexes ===
Opera Foot
Opera (2.0,1.0) (0.0,0.0)
Foot (0.0,0.0) (1.0,2.0)
=== Pile ou Face (zero-sum) ===
Heads Tails
Heads (1.0,-1.0) (-1.0,1.0)
Tails (-1.0,1.0) (1.0,-1.0)
=== Coordination ===
Left Right
Left (1.0,1.0) (0.0,0.0)
Right (0.0,0.0) (1.0,1.0)
Lecture : Les matrices affichées montrent la structure des gains pour quatre jeux 2x2 canoniques. Le Dilemme du Prisonnier a un équilibre (Defect,Defect) à (1,1), la Bataille des Sexes a deux équilibres purs (Opera,Opera) et (Foot,Foot), Pile ou Face est un jeu à somme nulle sans équilibre pur, et Coordination a deux équilibres symétriques (Left,Left) et (Right,Right).
3. Meilleure reponse et equilibre de Nash pur
La meilleure reponse du joueur 1 a l’action \(a_2\) du joueur 2 est : \[BR_1(a_2) = \arg\max_{a_1 \in A_1} u_1[a_1, a_2]\] L’ensemble des actions qui maximisent le gain de 1 sachant que 2 joue \(a_2\) (il peut y en avoir plusieurs, en cas d’ex-aequo).
Un profil \((a_1^*, , a_2^*)\) est un equilibre de Nash pur si : \[a_1^* \in BR_1(a_2^*) \quad \text{ET} \quad a_2^* \in BR_2(a_1^*)\] Intuitivement : chacun joue une meilleure reponse a l’autre — aucun n’a intérêt a devier unilateralement.
// Meilleure reponse du joueur 1 a l'action a2 du joueur 2 (argmax sur la colonne).static List<int>BestResponse1(NormalFormGame g,int a2){double best =double.NegativeInfinity;var res =new List<int>();for(int a1 =0; a1 < g.N1; a1++){if(g.U1[a1, a2]> best){ best = g.U1[a1, a2]; res.Clear(); res.Add(a1);}elseif(g.U1[a1, a2]== best) res.Add(a1);}return res;}// Meilleure reponse du joueur 2 a l'action a1 du joueur 1 (argmax sur la ligne).static List<int>BestResponse2(NormalFormGame g,int a1){double best =double.NegativeInfinity;var res =new List<int>();for(int a2 =0; a2 < g.N2; a2++){if(g.U2[a1, a2]> best){ best = g.U2[a1, a2]; res.Clear(); res.Add(a2);}elseif(g.U2[a1, a2]== best) res.Add(a2);}return res;}// Equilibres de Nash purs : profils (a1,a2) ou chacun est meilleure reponse de l'autre.static List<(int a1,int a2)>PureNashEquilibria(NormalFormGame g){var nash =new List<(int,int)>();for(int a1 =0; a1 < g.N1; a1++)for(int a2 =0; a2 < g.N2; a2++)if(BestResponse1(g, a2).Contains(a1)&&BestResponse2(g, a1).Contains(a2)) nash.Add((a1, a2));return nash;}staticstringFmtNash(NormalFormGame g, List<(int a1,int a2)> eqs)=> eqs.Count==0?"(aucun equilibre pur)":string.Join(", ", eqs.Select(e => $"({g.Acts1[e.a1]},{g.Acts2[e.a2]})"));var sb =newStringBuilder();sb.AppendLine("=== Equilibres de Nash purs ===");sb.AppendLine($"Dilemme du Prisonnier : {FmtNash(PD, PureNashEquilibria(PD))}");sb.AppendLine($"Bataille des Sexes : {FmtNash(BoS, PureNashEquilibria(BoS))}");sb.AppendLine($"Pile ou Face : {FmtNash(MP, PureNashEquilibria(MP))}");sb.AppendLine($"Coordination : {FmtNash(Coord, PureNashEquilibria(Coord))}");sb.ToString().Display();
=== Equilibres de Nash purs ===
Dilemme du Prisonnier : (Defect,Defect)
Bataille des Sexes : (Opera,Opera), (Foot,Foot)
Pile ou Face : (aucun equilibre pur)
Coordination : (Left,Left), (Right,Right)
Interpretation : pourquoi ces equilibres
Dilemme du Prisonnier : un seul equilibre (Defect, Defect) = (1,1), alors que (Coop, Coop) = (3,3) donnerait mieux aux deux. Illustration parfaite de la non-optimalite parcimonieuse de Nash : l’equilibre individuellement rationnel est collectivement sous-optimal.
Bataille des Sexes : deux equilibres (Opera,Opera) et (Foot,Foot) — les joueurs veulent se coordonner mais preferent des coordres opposes. Illustre la sélection d’equilibre (quel equilibre choisir ?).
Pile ou Face : aucun equilibre pur — chaque profil est deviable. Ce jeu zero-sum exige un equilibre mixte (randomisation).
Coordination : deux equilibres symetriques (Left,Left) et (Right,Right) — pure question d’alignement.
Lecture : La détection des équilibres de Nash purs confirme que le Dilemme du Prisonnier a un unique équilibre (Defect,Defect), la Bataille des Sexes en a deux (Opera,Opera) et (Foot,Foot), Pile ou Face n’en a aucun (jeu à somme nulle), et Coordination en a deux symétriques (Left,Left) et (Right,Right).
4. Dominance et elimination iteree (IESDS)
Une action \(a\) est strictement dominee pour le joueur 1 par une action \(b\) si : \[u_1[b, a_2] > u_1[a, a_2] \quad \forall a_2 \in A_2\] Une action dominee n’est jamais une meilleure reponse : un joueur rationnel ne la jouera pas. On peut donc l’eliminer, reduisant le jeu — puis re-evaluer la dominance dans le jeu reduit, et iterer. C’est l’IESDS (Iterated Elimination of Strictly Dominated Stratégies).
Si l’IESDS converge vers un profil unique, le jeu est dominance-solvable (et ce profil est le seul equilibre de Nash).
// b domine-t-elle strictement a pour le joueur 1 ? (U1[b,a2] > U1[a,a2] pour tout a2)staticboolStrictlyDominated1(NormalFormGame g,int a,int b){for(int a2 =0; a2 < g.N2; a2++)if(g.U1[b, a2]<= g.U1[a, a2])returnfalse;returntrue;}// symetric pour joueur 2staticboolStrictlyDominated2(NormalFormGame g,int a,int b){for(int a1 =0; a1 < g.N1; a1++)if(g.U2[a1, b]<= g.U2[a1, a])returnfalse;returntrue;}// IESDS : elimine iterativement les actions strictement dominees.// Retourne (actionsSurvivantesJ1, actionsSurvivantesJ2).static(List<int>, List<int>)IESDS(NormalFormGame g){var alive1 = Enumerable.Range(0, g.N1).ToList();var alive2 = Enumerable.Range(0, g.N2).ToList();bool changed =true;while(changed){ changed =false;// Cherche une action dominee chez joueur 1 (par une action survivante)var toRemove1 =new List<int>();foreach(var a in alive1){bool dominated =false;foreach(var b in alive1){if(b == a)continue;bool dom =true;foreach(var a2 in alive2)if(g.U1[b, a2]<= g.U1[a, a2]){ dom =false;break;}if(dom){ dominated =true;break;}}if(dominated) toRemove1.Add(a);}var toRemove2 =new List<int>();foreach(var a in alive2){bool dominated =false;foreach(var b in alive2){if(b == a)continue;bool dom =true;foreach(var a1 in alive1)if(g.U2[a1, b]<= g.U2[a1, a]){ dom =false;break;}if(dom){ dominated =true;break;}}if(dominated) toRemove2.Add(a);}if(toRemove1.Count>0|| toRemove2.Count>0){ changed =true;foreach(var r in toRemove1) alive1.Remove(r);foreach(var r in toRemove2) alive2.Remove(r);}}return(alive1, alive2);}var sb =newStringBuilder();sb.AppendLine("=== IESDS (actions survivantes) ===");var(pd1, pd2)=IESDS(PD);sb.AppendLine($"Dilemme du Prisonnier : J1={{{string.Join(",", pd1.Select(i=>PD.Acts1[i]))}}}, J2={{{string.Join(",", pd2.Select(i=>PD.Acts2[i]))}}} -> profil unique (Defect,Defect) = dominance-solvable");var(bos1, bos2)=IESDS(BoS);sb.AppendLine($"Bataille des Sexes : J1={{{string.Join(",", bos1.Select(i=>BoS.Acts1[i]))}}}, J2={{{string.Join(",", bos2.Select(i=>BoS.Acts2[i]))}}} -> rien elimine (aucune dominance)");sb.ToString().Display();
Quand un jeu 2x2 n’a pas d’equilibre pur (ex. Pile ou Face), l’equilibre est mixte : les joueurs randomisent. Le principe d’indifference dit qu’a l’equilibre, l’adversaire est indifferent entre ses actions pures — sinon il devierait.
Pour le joueur 2 qui melange \(\beta\) sur sa 1ere action (et \(1-\beta\) sur la 2e), le joueur 1 est indifferent quand : \[\beta \cdot u_1[0,0] + (1-\beta) \cdot u_1[0,1] = \beta \cdot u_1[1,0] + (1-\beta) \cdot u_1[1,1]\] On resout en \(\beta\), symetriquement pour \(\alpha\) (melange du joueur 1).
Ce calcul a la main est précisément ce que cache l’appel nashpy.Game(payoffs).support_enumeration() dans le twin Python.
// Equilibre mixte 2x2 par indifference. Retourne (alpha=proba j1 sur action0, beta=proba j2 sur action0).// beta rend le joueur 1 indifferent ; alpha rend le joueur 2 indifferent.static(double alpha,double beta)?MixedNash2x2(NormalFormGame g){if(g.N1!=2|| g.N2!=2)returnnull;// beta : proba que j2 joue action 0. Indifference du joueur 1 :// beta*U1[0,0] + (1-beta)*U1[0,1] = beta*U1[1,0] + (1-beta)*U1[1,1]double denomB =(g.U1[0,0]- g.U1[1,0])-(g.U1[0,1]- g.U1[1,1]);double denomA =(g.U2[0,0]- g.U2[0,1])-(g.U2[1,0]- g.U2[1,1]);if(Math.Abs(denomA)<1e-12|| Math.Abs(denomB)<1e-12)returnnull;// pas d'interieurdouble beta =(g.U1[1,1]- g.U1[0,1])/ denomB;double alpha =(g.U2[1,1]- g.U2[1,0])/ denomA;// Une strategie mixte valide exige des probabilites dans [0, 1] ; hors de cet// intervalle il n'y a pas d'equilibre mixte interieur (ex. Dilemme du Prisonnier,// ou Defect domine strictement Coop -> seul (Defect,Defect) est equilibre).if(alpha <-1e-9|| alpha >1+1e-9|| beta <-1e-9|| beta >1+1e-9)returnnull;return(alpha, beta);}staticstringFmtMixed(NormalFormGame g,(double alpha,double beta) m){stringf(double x)=> x.ToString("F3", CultureInfo.InvariantCulture);return $"J1 joue {g.Acts1[0]} à {f(m.alpha)} / {g.Acts1[1]} à {f(1-m.alpha)} ; J2 joue {g.Acts2[0]} à {f(m.beta)} / {g.Acts2[1]} à {f(1-m.beta)}";}var sb =newStringBuilder();sb.AppendLine("=== Equilibres mixtes 2x2 (principe d'indifference) ===");var mpMix =MixedNash2x2(MP);if(mpMix.HasValue) sb.AppendLine($"Pile ou Face : {FmtMixed(MP, mpMix.Value)} (chaque joueur 1/2-1/2, valeur 0)");var bosMix =MixedNash2x2(BoS);if(bosMix.HasValue) sb.AppendLine($"Bataille des Sexes : {FmtMixed(BoS, bosMix.Value)} (3e equilibre, mixte)");var pdMix =MixedNash2x2(PD);sb.AppendLine($"Dilemme Prisonnier : {(pdMix.HasValue ? FmtMixed(PD, pdMix.Value) : "pas d'equilibre mixte interieur(Defect domine — seul(Defect,Defect) est equilibre)")}");sb.ToString().Display();
=== Equilibres mixtes 2x2 (principe d'indifference) ===
Pile ou Face : J1 joue Heads à 0.500 / Tails à 0.500 ; J2 joue Heads à 0.500 / Tails à 0.500 (chaque joueur 1/2-1/2, valeur 0)
Bataille des Sexes : J1 joue Opera à 0.667 / Foot à 0.333 ; J2 joue Opera à 0.333 / Foot à 0.667 (3e equilibre, mixte)
Dilemme Prisonnier : pas d'equilibre mixte interieur (Defect domine — seul (Defect,Defect) est equilibre)
Lecture : L’absence d’équilibre mixte intérieur pour le Dilemme du Prisonnier illustre le théorème de dominance. Lorsque une stratégie domine strictement toutes les autres, elle est jouée avec probabilité 1 à l’équilibre, ce qui explique pourquoi (Defect,Defect) est le seul équilibre de Nash (pur ou mixte) de ce jeu.
Interpretation : les trois equilibres de la Bataille des Sexes
La Bataille des Sexes admet 3 equilibres de Nash au total : les 2 purs (Opera,Opera) et (Foot,Foot), plus un equilibre mixte. C’est un cas exemplaire de la multiplicite des equilibres — un defi central de la théorie des jeux : si plusieurs equilibres coexistent, comment les joueurs se coordonnent-ils ?
Pour Pile ou Face, l’equilibre mixte (1/2, 1/2) est l’unique equilibre : c’est aussi la valeur du jeu (esperance 0 pour chacun, par symetrie du zero-sum). Randomiser rend chaque action de l’adversaire equivalente — c’est le but d’un melange inexploitable.
6. Jeux a somme nulle et valeur du jeu
Dans un jeu zero-sum (\(u_2 = -u_1\)), la théorie de von Neumann (1928) garantit l’existence d’une valeur\(v\) : le joueur 1 peut garantir \(\ge v\), le joueur 2 peut limiter a \(\le v\). A l’equilibre, l’esperance est exactement \(v\).
Pour Pile ou Face, \(v = 0\) (jeu equitable). Les jeux zero-sum sont plus simples strategiquement : un seul equilibre (le minimax), pas de problème de coordination.
// Esperance de gain du joueur 1 au profil mixte (alpha sur action0 de j1, beta sur action0 de j2).staticdoubleExpectedPayoff1(NormalFormGame g,double alpha,double beta){// j1 joue action0 a alpha, action1 a 1-alpha ; j2 joue action0 a beta, action1 a 1-betadouble p00 = alpha * beta, p01 = alpha *(1- beta), p10 =(1- alpha)* beta, p11 =(1- alpha)*(1- beta);return p00 * g.U1[0,0]+ p01 * g.U1[0,1]+ p10 * g.U1[1,0]+ p11 * g.U1[1,1];}// Verif : Pile ou Face a l'equilibre mixte (0.5, 0.5) — esperance joueur 1 = 0 (jeu equitable).var sb =newStringBuilder();sb.AppendLine("=== Verification de la valeur du jeu (Pile ou Face) ===");var(a, b)=MixedNash2x2(MP).Value;stringfi(double x,string fmt="F3")=> x.ToString(fmt, CultureInfo.InvariantCulture);sb.AppendLine($"Profil mixte equilibre : alpha={fi(a)}, beta={fi(b)}");sb.AppendLine($"Esperance joueur 1 = {fi(ExpectedPayoff1(MP, a, b), "F4")} (attendu = 0, jeu zero-sum equitable)");sb.AppendLine($"Esperance joueur 2 = {fi(-ExpectedPayoff1(MP, a, b), "F4")} (zero-sum : u2 = -u1)");sb.AppendLine();sb.AppendLine(">>> Deviation test : si j1 joue Heads toujours (alpha=1) face au melange equilibre beta=0.5 :");sb.AppendLine($" E[payoff j1 | alpha=1, beta=0.5] = {fi(ExpectedPayoff1(MP, 1.0, 0.5), "F4")} (pas meilleur que l'equilibre = inexploitabilite)");sb.ToString().Display();
=== Verification de la valeur du jeu (Pile ou Face) ===
Profil mixte equilibre : alpha=0.500, beta=0.500
Esperance joueur 1 = 0.0000 (attendu = 0, jeu zero-sum equitable)
Esperance joueur 2 = -0.0000 (zero-sum : u2 = -u1)
>>> Deviation test : si j1 joue Heads toujours (alpha=1) face au melange equilibre beta=0.5 :
E[payoff j1 | alpha=1, beta=0.5] = 0.0000 (pas meilleur que l'equilibre = inexploitabilite)
Lecture : Le test de déviation confirme l’inexploitabilité de l’équilibre mixte (0.5,0.5) pour Pile ou Face. Si le joueur 1 joue Heads à 100% face au mélange du joueur 2, son espérance reste à 0.0000, ce qui valide que l’équilibre mixte est bien un équilibre de Nash où aucun joueur ne peut améliorer son gain en déviant unilatéralement.
Lecture : Pour Pile ou Face, l’équilibre mixte est (0.5,0.5) pour chaque joueur, donnant une valeur espérée de 0 (jeu équitable). Pour la Bataille des Sexes, l’équilibre mixte additionnel est J1: Opera à 0.667/Foot à 0.333, J2: Opera à 0.333/Foot à 0.667, confirmant que le Dilemme du Prisonnier n’a pas d’équilibre mixte intérieur car Defect domine strictement.
7. Au-dela du 2x2 : Pierre-Feuille-Ciseaux (3x3)
RPS est zero-sum, sans equilibre pur (chaque action est battue par une autre). L’equilibre mixte est uniforme\(\left(\tfrac13, \tfrac13, \tfrac13\right)\) par symetrie. Notre IESDS ne reduit rien (aucune dominance pure), et il n’y a pas d’equilibre pur — seul le mixte resout le jeu. La formule close 2x2 ne s’applique pas ; la resolution générale (support enumeration) est l’objet de la tranche 2.
// Pierre-Feuille-Ciseaux (3x3, zero-sum). Ligne = joueur 1, gains du joueur 1.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 sb =newStringBuilder();sb.AppendLine("=== Pierre-Feuille-Ciseaux (3x3 zero-sum) ===");sb.AppendLine(RPS.ToString());sb.AppendLine($"Equilibres de Nash purs : {FmtNash(RPS, PureNashEquilibria(RPS))}");var(r1, r2)=IESDS(RPS);sb.AppendLine($"IESDS survivants : J1={{{string.Join(",", r1)}}}, J2={{{string.Join(",", r2)}}} (aucune dominance -> IESDS ne reduit rien)");sb.AppendLine();sb.AppendLine(">>> RPS n'a pas d'equilibre pur et aucune dominance. Resolution = equilibre mixte (1/3,1/3,1/3)");sb.AppendLine(" par symetrie. La formule close 2x2 ne s'applique pas -> support enumeration (tranche 2).");sb.ToString().Display();
=== Pierre-Feuille-Ciseaux (3x3 zero-sum) ===
R P S
R (0.0,0.0) (-1.0,1.0) (1.0,-1.0)
P (1.0,-1.0) (0.0,0.0) (-1.0,1.0)
S (-1.0,1.0) (1.0,-1.0) (0.0,0.0)
Equilibres de Nash purs : (aucun equilibre pur)
IESDS survivants : J1={0,1,2}, J2={0,1,2} (aucune dominance -> IESDS ne reduit rien)
>>> RPS n'a pas d'equilibre pur et aucune dominance. Resolution = equilibre mixte (1/3,1/3,1/3)
par symetrie. La formule close 2x2 ne s'applique pas -> support enumeration (tranche 2).
8. Verification croisee avec nashpy (oracle SOTA Python)
Le twin Python de ce notebook (GameTheory-02-NormalForm-Python) calcule ses equilibres de Nash avec nashpy (nash.Game(A, B).support_enumeration()), la bibliotheque de reference des equilibres de Nash en Python. Cette tranche C# implemente les memes calculs from-scratch (BCL .NET seule). Pour prouver la parite lib-vs-lib (issue #10382), on fait dialoguer les deux : on invoque nashpy depuis C# via un pont CLI Process.Start (axe 3 de la checklist SOTA, cf. verdict twin_pairs — le meme schema que le pont Gambit de la tranche 2).
nashpy resout les MEMES jeux que les cellules precedentes (PD, BoS, MP, RPS) par enumeration de supports, et on compare numeriquement ses equilibres a ceux du from-scratch :
Jeu
From-scratch (C#)
nashpy attendu
RPS 3x3
equilibre symetrique (1/3,1/3,1/3) par symetrie
1 eq mixte uniforme
Bataille des Sexes
2 purs + mixte (2/3,1/3)
3 eq (2 purs + 1 mixte)
Pile ou Face
mixte (1/2,1/2)
1 eq (1/2,1/2)
Dilemme du Prisonnier
aucun mixte interieur
1 eq pur (Defect,Defect)
// === Pont nashpy CLI : l'oracle SOTA du twin Python valide le from-scratch (BCL .NET) ===// Parite lib-vs-lib (issue #10382) : le twin Python calcule ses equilibres mixtes avec// nashpy (nash.Game(A,B).support_enumeration()). On invoque le MEME moteur depuis C# via// Process.Start (axe CLI de la checklist SOTA, meme schema que le pont Gambit de la tranche 2),// on resout les jeux deja definis (PD, BoS, MP, RPS), puis on compare aux resultats from-scratch.using System.IO;using System.Diagnostics;using System.Text.Json;// --- 1. Resoudre l'interpreteur Python qui importe nashpy (regle F : outil reel, pas un stub) ---staticstringFindPythonWithNashpy(){var candidates =new List<string>();try{var pi =newProcessStartInfo("where","python"){ RedirectStandardOutput =true, RedirectStandardError =true, UseShellExecute =false, CreateNoWindow =true};var p = Process.Start(pi);string outp = p.StandardOutput.ReadToEnd(); p.WaitForExit(3000);foreach(var line in outp.Split('\n', StringSplitOptions.RemoveEmptyEntries)) candidates.Add(line.Trim());}catch{} candidates.Add("python"); candidates.Add("python3");// Linux et macOS sans alias `python`foreach(var exe in candidates){try{var pi =newProcessStartInfo(exe,"-c \"import nashpy\""){ RedirectStandardOutput =true, RedirectStandardError =true, UseShellExecute =false, CreateNoWindow =true};var p = Process.Start(pi); p.StandardOutput.ReadToEnd(); p.WaitForExit(5000);if(p.ExitCode==0)return exe;}catch{}}thrownewFileNotFoundException("nashpy introuvable. Installer la lib SOTA Python : python -m pip install nashpy (regle F : reparer, pas contourner).");}string pythonExe =FindPythonWithNashpy();// --- 2. Serialiser les bimatrices (PD, BoS, MP, RPS) pour nashpy ---staticstringBimatrixToJson(NormalFormGame g){stringmat(double[,] m){var sb =newStringBuilder("[");for(int i =0; i < g.N1; i++){if(i >0) sb.Append(','); sb.Append('[');for(int j =0; j < g.N2; j++){if(j >0) sb.Append(','); sb.Append(m[i, j].ToString("G6", CultureInfo.InvariantCulture));} sb.Append(']');}return sb.Append(']').ToString();}return $"{{\"A\": {mat(g.U1)}, \"B\": {mat(g.U2)}}}";}var bridgeGames =new(string name, NormalFormGame game)[]{("PD", PD),("BoS", BoS),("MP", MP),("RPS", RPS)};var inp =newStringBuilder("{");for(int k =0; k < bridgeGames.Length; k++){if(k >0) inp.Append(','); inp.Append($"\"{bridgeGames[k].name}\": {BimatrixToJson(bridgeGames[k].game)}");}inp.Append('}');string inputPath = Path.Combine(Path.GetTempPath(),"gt2_nashpy_input.json");File.WriteAllText(inputPath, inp.ToString());// --- 3. Script nashpy : support_enumeration sur chaque jeu, resultats en JSON sur stdout ---string script = @"import json, sysimport nashpy as nashimport numpy as npinp = json.load(open(sys.argv[1],'r'))out={}for name, g in inp.items(): A = np.array(g['A'], dtype=float) B = np.array(g['B'], dtype=float) eqs =[]for s1, s2 in nash.Game(A, B).support_enumeration(): eqs.append([['%.6f' % x for x in s1],['%.6f' % x for x in s2]])out[name]= eqsjson.dump(out, sys.stdout)";string scriptPath = Path.Combine(Path.GetTempPath(),"gt2_nashpy_bridge.py");File.WriteAllText(scriptPath, script);var psi =newProcessStartInfo(pythonExe, $"\"{scriptPath}\"\"{inputPath}\""){ RedirectStandardOutput =true, RedirectStandardError =true, UseShellExecute =false, CreateNoWindow =true};var p2 = Process.Start(psi);string stdout = p2.StandardOutput.ReadToEnd();p2.WaitForExit(30000);if(p2.ExitCode!=0)thrownewInvalidOperationException("nashpy a echoue:\n"+ stdout + p2.StandardError.ReadToEnd());// --- 4. Comparaison numerique : nashpy vs from-scratch ---var doc = JsonDocument.Parse(stdout);// pas de using-declaration en top-level notebookdouble[]ToVec(JsonElement el)=> el.EnumerateArray().Select(x =>double.Parse(x.GetString(), CultureInfo.InvariantCulture)).ToArray();staticdoubleMaxDiff(double[] a,double[] b){double m =0;for(int i =0; i < a.Length; i++) m = Math.Max(m, Math.Abs(a[i]- b[i]));return m;}// Exploitabilite d'un profil = somme des meilleurs gains de deviation unilaterale ; 0 <=> equilibre.staticdoubleExploitability(NormalFormGame g,double[] s1,double[] s2){double e1mix =0, br1 =double.MinValue;for(int a1 =0; a1 < g.N1; a1++){double e =0;for(int a2 =0; a2 < g.N2; a2++) e += g.U1[a1, a2]* s2[a2]; e1mix += s1[a1]* e; br1 = Math.Max(br1, e);}double e2mix =0, br2 =double.MinValue;for(int a2 =0; a2 < g.N2; a2++){double e =0;for(int a1 =0; a1 < g.N1; a1++) e += g.U2[a1, a2]* s1[a1]; e2mix += s2[a2]* e; br2 = Math.Max(br2, e);}return(br1 - e1mix)+(br2 - e2mix);}var sb =newStringBuilder();sb.AppendLine($"=== Pont nashpy : from-scratch (BCL .NET) vs nashpy ({Path.GetFileName(pythonExe)}) ===");sb.AppendLine("Les deux moteurs calculent TOUS les equilibres de Nash (purs et mixtes) par enumeration de supports.");sb.AppendLine();int okTotal =0;foreach(var(name, game)in bridgeGames){var root = doc.RootElement.GetProperty(name);var profiles =new List<(double[] s1,double[] s2)>();foreach(var el in root.EnumerateArray()) profiles.Add((ToVec(el[0]),ToVec(el[1]))); sb.AppendLine($"--- {name} ({game.N1}x{game.N2}) : nashpy={profiles.Count} equilibre(s) ---");foreach(var(s1, s2)in profiles) sb.AppendLine($" nashpy [{string.Join(",", s1.Select(x => x.ToString("F3", CultureInfo.InvariantCulture)))}] "+ $"[{string.Join(",", s2.Select(x => x.ToString("F3", CultureInfo.InvariantCulture)))}] "+ $"-> exploitabilite={Exploitability(game, s1, s2).ToString("F6", CultureInfo.InvariantCulture)}");bool ok;if(name =="RPS"){var uni1 =new[]{1.0/3,1.0/3,1.0/3}; ok = profiles.Count==1&&MaxDiff(profiles[0].s1, uni1)<1e-3&&MaxDiff(profiles[0].s2, uni1)<1e-3; sb.AppendLine($" >>> {(ok ? "CORRESPOND" : "DIVERGENCE")} : nashpy retrouve l'equilibre symetrique uniforme (1/3,1/3,1/3)"); sb.AppendLine(" annonce par symetrie en section 7 -> meme resultat que le twin Python (support_enumeration).");}elseif(name =="BoS"){var m =MixedNash2x2(BoS).Value;// alpha, beta du from-scratch (formule close de la section 5)var exp1 =new[]{ m.alpha,1- m.alpha};var exp2 =new[]{ m.beta,1- m.beta};var interior = profiles.Where(p => p.s1.All(x => x >1e-6&& x <1-1e-6)).ToList(); ok = profiles.Count==3&& interior.Count==1&&MaxDiff(interior[0].s1, exp1)<1e-3&&MaxDiff(interior[0].s2, exp2)<1e-3; sb.AppendLine($" >>> {(ok ? "CORRESPOND" : "DIVERGENCE")} : nashpy = 2 purs + 1 mixte ; le mixte "+ $"[{string.Join(",", exp1.Select(x => x.ToString("F3", CultureInfo.InvariantCulture)))}] "+ $"x [{string.Join(",", exp2.Select(x => x.ToString("F3", CultureInfo.InvariantCulture)))}] "+"= la formule close 2x2 de la section 5.");}elseif(name =="MP"){var half =new[]{0.5,0.5}; ok = profiles.Count==1&&MaxDiff(profiles[0].s1, half)<1e-3&&MaxDiff(profiles[0].s2, half)<1e-3; sb.AppendLine($" >>> {(ok ? "CORRESPOND" : "DIVERGENCE")} : nashpy retrouve (1/2,1/2) x (1/2,1/2) de la section 5.");}else// PD{bool hasInterior = profiles.Any(p => p.s1.All(x => x >1e-6&& x <1-1e-6)&& p.s2.All(x => x >1e-6&& x <1-1e-6)); ok = profiles.Count==1&&!hasInterior &&!MixedNash2x2(PD).HasValue; sb.AppendLine($" >>> {(ok ? "CORRESPOND" : "DIVERGENCE")} : unique equilibre pur (Defect,Defect), aucun mixte interieur"); sb.AppendLine(" -> coherent avec la formule close qui renvoie 'pas d'equilibre mixte interieur'.");}if(ok) okTotal++;}sb.AppendLine();sb.AppendLine($">>> Bilan : {okTotal}/{bridgeGames.Length} jeux concordent. L'oracle SOTA nashpy (moteur du twin Python)");sb.AppendLine(" valide le from-scratch BCL .NET : les deux implementent la meme notion d'equilibre de Nash.");sb.ToString().Display();
=== Pont nashpy : from-scratch (BCL .NET) vs nashpy (python) ===
Les deux moteurs calculent TOUS les equilibres de Nash (purs et mixtes) par enumeration de supports.
--- PD (2x2) : nashpy=1 equilibre(s) ---
nashpy [0.000,1.000] [0.000,1.000] -> exploitabilite=0.000000
>>> CORRESPOND : unique equilibre pur (Defect,Defect), aucun mixte interieur
-> coherent avec la formule close qui renvoie 'pas d'equilibre mixte interieur'.
--- BoS (2x2) : nashpy=3 equilibre(s) ---
nashpy [1.000,0.000] [1.000,0.000] -> exploitabilite=0.000000
nashpy [0.000,1.000] [0.000,1.000] -> exploitabilite=0.000000
nashpy [0.667,0.333] [0.333,0.667] -> exploitabilite=0.000001
>>> CORRESPOND : nashpy = 2 purs + 1 mixte ; le mixte [0.667,0.333] x [0.333,0.667] = la formule close 2x2 de la section 5.
--- MP (2x2) : nashpy=1 equilibre(s) ---
nashpy [0.500,0.500] [0.500,0.500] -> exploitabilite=0.000000
>>> CORRESPOND : nashpy retrouve (1/2,1/2) x (1/2,1/2) de la section 5.
--- RPS (3x3) : nashpy=1 equilibre(s) ---
nashpy [0.333,0.333,0.333] [0.333,0.333,0.333] -> exploitabilite=0.000000
>>> CORRESPOND : nashpy retrouve l'equilibre symetrique uniforme (1/3,1/3,1/3)
annonce par symetrie en section 7 -> meme resultat que le twin Python (support_enumeration).
>>> Bilan : 4/4 jeux concordent. L'oracle SOTA nashpy (moteur du twin Python)
valide le from-scratch BCL .NET : les deux implementent la meme notion d'equilibre de Nash.
Exercice 1 : Chicken (Hawk-Dove)
Le jeu Chicken (Hawk-Dove) modèle le bras de fer automobile : deux joueurs s’engagent sur une collision ; celui qui refuse (Dove) perd la face, celui qui persiste (Hawk) gagne si l’autre cede, mais si les deux persistent, collision (perte enorme). Matrice :
Hawk
Dove
Hawk
(0, 0)
(3, 1)
Dove
(1, 3)
(2, 2)
Completez le stub pour : (1) construire le jeu, (2) enumerer les equilibres de Nash purs, (3) calculer l’equilibre mixte. Combien d’equilibres au total ?
// Exercice 1 : Chicken / Hawk-Dove (etudiant a completer)// Indice 1 : construire NormalFormGame avec la bimatrice ci-dessus.// Indice 2 : appeler PureNashEquilibria + MixedNash2x2, afficher avec FmtNash / FmtMixed.// Étape 1 : var chicken = new NormalFormGame(...)// Étape 2 : PureNashEquilibria(chicken) + MixedNash2x2(chicken)// TODO etudiant"Exercice 1 a completer — Chicken : enumerer equilibres purs + mixte.".Display();
Lecture : Pierre-Feuille-Ciseaux est un jeu cyclique 3x3 à somme nulle sans équilibre pur. L’IESDS ne réduit pas l’espace d’actions (aucune dominance stricte), confirmant que la solution doit passer par un équilibre mixte où chaque action a une probabilité de 1/3.
Exercice 2 : Dominance solvability du Dilemme du Prisonnier
Verifiez firsthand que le Dilemme du Prisonnier est dominance-solvable : appliquez IESDS manuellement étape par étape. Combien d’étapes faut-il pour converger vers (Defect, Defect) ? L’equilibre obtenu par IESDS coincide-t-il avec l’equilibre de Nash ? (Theoreme : si IESDS donne un profil unique, c’est l’unique equilibre de Nash.)
// Exercice 2 : trace IESDS étape par étape sur le Dilemme du Prisonnier (étudiant à compléter)// Indice : la fonction IESDS retourne l'état final ; pour tracer les étapes, ajouter un affichage// intermediaire dans la boucle while, ou reimplementer une version qui log chaque elimination.// TODO etudiant"Exercice 2 a completer — tracer les etapes IESDS sur le Dilemme du Prisonnier.".Display();
Exercice 2 a completer — tracer les etapes IESDS sur le Dilemme du Prisonnier.
Exercice 3 : Stag Hunt
Le jeu Stag Hunt (chasse au cerf) : deux chasseurs peuvent cooperer pour attraper un cerf (gros gain) ou chasser seul le lievre (gain modere mais sur). Matrice :
Stag
Hare
Stag
(4, 4)
(0, 3)
Hare
(3, 0)
(3, 3)
Completez le stub pour enumerer les equilibres de Nash purs. Comparez au Dilemme du Prisonnier : Stag Hunt a-t-il un equilibre cooperatif (Stag,Stag) ? Pourquoi est-il pourtant fragile (risque de coordination) ?
// Exercice 3 : Stag Hunt (etudiant a completer)// Indice : construire la bimatrice, enumerer PureNashEquilibria, comparer au Dilemme du Prisonnier.// Question : (Stag,Stag) est-il equilibre ? Et (Hare,Hare) ? Quel est le risque ?// TODO etudiant"Exercice 3 a completer — Stag Hunt : equilibres purs et risque de coordination.".Display();
Exercice 3 a completer — Stag Hunt : equilibres purs et risque de coordination.
Conclusion (tranche 1)
Cette tranche a pose les concepts fondamentaux de la théorie des jeux stratégique from-scratch en C#/.NET : forme normale, meilleure reponse, equilibre de Nash pur, IESDS, equilibre mixte 2x2.
PureNashEquilibria (intersection des meilleures reponses)
Dominance stricte
StrictlyDominated1/2 (inegalite sur toutes les actions adverses)
IESDS
IESDS (elimination iterative jusqu’a point fixe)
Equilibre mixte 2x2
MixedNash2x2 (principe d’indifference, formule close)
Esperance mixte
ExpectedPayoff1 (produit des melanges)
Points cles
Complementarite from-scratch ↔︎ nashpy : le twin Python utilise nashpy (support enumeration exact, Lemke-Howson), ce twin .NET demontre les concepts a la main (comprendre meilleure reponse + indifference). Deux angles pedagogiques complementaires (#3801 Prong B).
Equilibre != optimum : le Dilemme du Prisonnier montre qu’un equilibre de Nash (Defect,Defect)=(1,1) peut etre strictement pire qu’un profil non-equilibre (Coop,Coop)=(3,3). C’est le coeur du concept : rationalite individuelle ≠ optimalite collective.
Multiplicite et absence : la Bataille des Sexes a 3 equilibres (2 purs + 1 mixte), Pile ou Face n’en a aucun pur. Nash (1950) garantit seulement l’existence d’au moins un equilibre (souvent mixte).
Tranches suivantes (marathon #4956)
Tranche 2 : support enumeration general (equilibre mixte de jeux NxN comme RPS), via resolution des systèmes d’indifference.
Tranche 1 du twin .NET⇄Python (#4956 marathon). Théorie des jeux stratégique = 1er concept. from-scratch = la valeur pedagogique de ce twin, complementaire au solveur nashpy.