Navigation : << GameTheory-2 tranche 1 | Twin .NET | Index
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.
| Twin | Outil | Valeur pédagogique |
|---|---|---|
| Python (this) | énumération des supports + Gauss + vérification | comprendre chaque étape de l’algorithme |
| nashpy (vérification) | Game.support_enumeration() |
un appel, tous les équilibres d’un jeu quelconque |
| .NET (C#) | idem, BCL seule | twin cross-langage, même 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).
À 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 vérifier contre nashpy
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) 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 numpy (stdlib numérique).
# nashpy n'est importé qu'à la fin, comme vérification indépendante (le vrai outil SOTA).
import numpy as np
from itertools import combinations
from typing import List, Tuple, Optional
np.set_printoptions(precision=4, suppress=True)
print("Environnement pret - support enumeration from-scratch (numpy seul).")Environnement pret - support enumeration from-scratch (numpy seul).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:
'''Jeu sous forme normale a 2 joueurs : actions pures + bimatrices de gains.'''
def __init__(self, acts1, acts2, U1, U2):
self.acts1 = list(acts1)
self.acts2 = list(acts2)
self.U1 = np.asarray(U1, dtype=float) # shape (N1, N2)
self.U2 = np.asarray(U2, dtype=float)
self.N1 = len(self.acts1)
self.N2 = len(self.acts2)
def __repr__(self):
lines = []
header = "".ljust(14) + "".join(a.ljust(10) for a in self.acts2)
lines.append(header)
for i in range(self.N1):
row = self.acts1[i].ljust(14)
for j in range(self.N2):
row += f"({self.U1[i,j]:.1f},{self.U2[i,j]:.1f})".ljust(12)
lines.append(row)
return "\n".join(lines)
print("NormalFormGame pret.")NormalFormGame pret.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]\]
À 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.
def expected_vs_mixed1(g: NormalFormGame, a1: int, sigma2: np.ndarray) -> float:
return float(np.dot(sigma2, g.U1[a1, :]))
# Esperance de a2 (joueur 2) face a sigma1.
def expected_vs_mixed2(g: NormalFormGame, a2: int, sigma1: np.ndarray) -> float:
return float(np.dot(sigma1, g.U2[:, a2]))
# Prenons RPS et verifions : si j2 joue uniforme (1/3,1/3,1/3), j1 indifferent entre R/P/S.
RPS = NormalFormGame(
["R", "P", "S"], ["R", "P", "S"],
[[0.0, -1.0, 1.0], [1.0, 0.0, -1.0], [-1.0, 1.0, 0.0]],
[[0.0, 1.0, -1.0], [-1.0, 0.0, 1.0], [1.0, -1.0, 0.0]])
uniform = np.array([1/3, 1/3, 1/3])
print("Esperances de j1 (R/P/S) face a sigma2 uniforme :")
for i, a in enumerate(RPS.acts1):
print(f" v1({a}; uniform) = {expected_vs_mixed1(RPS, i, uniform):.4f}")
print(">>> Toutes egales (0.0) : j1 indifferent, comme attendu par symetrie.")Esperances de j1 (R/P/S) face a sigma2 uniforme :
v1(R; uniform) = 0.0000
v1(P; uniform) = 0.0000
v1(S; uniform) = 0.0000
>>> Toutes egales (0.0) : j1 indifferent, comme attendu par symetrie.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-1\) équations indépendantes (égalité des espérances, 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 None si singuliere.
def solve_linear(A: np.ndarray, b: np.ndarray) -> Optional[np.ndarray]:
A = np.asarray(A, dtype=float).copy()
b = np.asarray(b, dtype=float).copy()
n = len(b)
M = np.hstack([A, b.reshape(-1, 1)]) # matrice augmentee [A | b]
# Elimination avant avec pivot partiel
for col in range(n):
piv = col + int(np.argmax(np.abs(M[col:, col])))
if abs(M[piv, col]) < 1e-12:
return None # singuliere
if piv != col:
M[[col, piv]] = M[[piv, col]]
for r in range(col + 1, n):
f = M[r, col] / M[col, col]
M[r, col:] -= f * M[col, col:]
# Retro-substitution
x = np.zeros(n)
for i in range(n - 1, -1, -1):
s = M[i, n] - np.dot(M[i, i+1:n], x[i+1:n])
x[i] = s / M[i, i]
return x
# Sanity check : resout le systeme trivial 2x2.
A = np.array([[2.0, 1.0], [1.0, -3.0]])
b = np.array([3.0, -2.0])
x = solve_linear(A, b)
print(f"Test Gauss : 2x + y = 3 ; x - 3y = -2 -> x={x[0]:.4f}, y={x[1]:.4f} (attendu x=1, y=1)")Test Gauss : 2x + y = 3 ; x - 3y = -2 -> x=1.0000, y=1.0000 (attendu x=1, y=1)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 :
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.
def subsets_of_size(n: int, k: int) -> List[Tuple[int, ...]]:
return list(combinations(range(n), k))
# Verif : sous-ensembles de taille 2 de {0,1,2} = {0,1},{0,2},{1,2}.
s2 = subsets_of_size(3, 2)
print(f"Sous-ensembles de taille 2 de {{0,1,2}} : {[set(s) for s in s2]} (attendu 3 paires)")Sous-ensembles de taille 2 de {0,1,2} : [{0, 1}, {0, 2}, {1, 2}] (attendu 3 paires)La brique est posée (subsets_of_size) ; la cellule suivante assemble le solveur complet. Pour chaque paire de supports \((S_1, S_2)\) de même taille \(k\), il résout le système d’indifférence de chaque joueur (les \(k-1\) équations d’espérances égales, plus la normalisation), puis applique le double test du point 3 de l’algorithme : positivité stricte des probabilités sur le support, et best-response hors-support.
# Support enumeration : trouve TOUS les equilibres de Nash (purs et 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.
def support_enumeration(g: NormalFormGame) -> List[Tuple[np.ndarray, np.ndarray]]:
equilibria: List[Tuple[np.ndarray, np.ndarray]] = []
K = min(g.N1, g.N2)
for k in range(1, K + 1):
for S1 in subsets_of_size(g.N1, k):
for S2 in subsets_of_size(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
A2 = np.zeros((k, k))
b2 = np.zeros(k)
for i in range(1, k):
for jj in range(k):
a2 = S2[jj]
A2[i - 1, jj] = g.U1[S1[i], a2] - g.U1[S1[0], a2]
A2[k - 1, :] = 1.0 # normalisation
b2[k - 1] = 1.0
sol2 = solve_linear(A2, b2)
if sol2 is None or np.any(sol2 < -1e-9):
continue # singuliere ou probabilite negative
# --- sigma1 : rend j2 indifferent sur S2 ---
A1 = np.zeros((k, k))
b1 = np.zeros(k)
for j in range(1, k):
for ii in range(k):
a1 = S1[ii]
A1[j - 1, ii] = g.U2[a1, S2[j]] - g.U2[a1, S2[0]]
A1[k - 1, :] = 1.0
b1[k - 1] = 1.0
sol1 = solve_linear(A1, b1)
if sol1 is None or np.any(sol1 < -1e-9):
continue
# --- Reconstruit les vecteurs sigma complets ---
sigma1 = np.zeros(g.N1)
sigma2 = np.zeros(g.N2)
for ii in range(k):
sigma1[S1[ii]] = sol1[ii]
for jj in range(k):
sigma2[S2[jj]] = sol2[jj]
# --- Best-response check : aucune action hors-support ne fait mieux ---
v1sup = expected_vs_mixed1(g, S1[0], sigma2)
v2sup = expected_vs_mixed2(g, S2[0], sigma1)
br_ok = True
for a1 in range(g.N1):
if sigma1[a1] < 1e-9 and expected_vs_mixed1(g, a1, sigma2) > v1sup + 1e-9:
br_ok = False
for a2 in range(g.N2):
if sigma2[a2] < 1e-9 and expected_vs_mixed2(g, a2, sigma1) > v2sup + 1e-9:
br_ok = False
if not br_ok:
continue
equilibria.append((sigma1, sigma2))
return equilibria
print("Support enumeration pret (Gauss + indifference + best-response check).")Support enumeration pret (Gauss + indifference + best-response check).Le solveur est assemblé — reste à le faire voler sur le cas qui a motivé la tranche : un jeu sans équilibre pur ni formule close applicable. Pierre-Feuille-Ciseaux est le candidat canonique, antisymétrique et à somme nulle. La cellule suivante construit le jeu et lance l’énumération ; la lecture du résultat (symétrie, uniformité) suit l’exécution.
# Resolution de Pierre-Feuille-Ciseaux (3x3) via support enumeration.
RPS = NormalFormGame(
["R", "P", "S"], ["R", "P", "S"],
[[0.0, -1.0, 1.0], [1.0, 0.0, -1.0], [-1.0, 1.0, 0.0]],
[[0.0, 1.0, -1.0], [-1.0, 0.0, 1.0], [1.0, -1.0, 0.0]])
eqs = support_enumeration(RPS)
print(f"=== Pierre-Feuille-Ciseaux : {len(eqs)} equilibre(s) de Nash (mixte) ===")
for s1, s2 in eqs:
sig1 = " ".join(f"{RPS.acts1[i]}:{s1[i]:.3f}" for i in range(3))
sig2 = " ".join(f"{RPS.acts2[i]}:{s2[i]:.3f}" for i in range(3))
print(f"sigma1 = {sig1} ; sigma2 = {sig2}")
print(">>> Equilibre uniforme (1/3, 1/3, 1/3) pour les deux joueurs, comme prevu par symetrie.")
print(" Valeur du jeu (zero-sum) : esperance = 0 pour les deux joueurs.")=== 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 les deux joueurs.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 à 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.
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.
Biased = NormalFormGame(
["R", "P", "S"], ["R", "P", "S"],
[[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)
[[0.0, 1.0, -2.0], [-1.0, 0.0, 1.0], [2.0, -1.0, 0.0]])
print("=== RPS biaise (S bat R rapporte double) ===")
print(Biased)
eqs = support_enumeration(Biased)
print(f"Equilibres trouves : {len(eqs)}")
for s1, s2 in eqs:
sig1 = " ".join(f"{Biased.acts1[i]}:{s1[i]:.3f}" for i in range(3))
sig2 = " ".join(f"{Biased.acts2[i]}:{s2[i]:.3f}" for i in range(3))
print(f"sigma1 = {sig1}")
print(f"sigma2 = {sig2}")
v1 = expected_vs_mixed1(Biased, 0, s2)
print(f"Valeur du jeu pour j1 : {v1:.4f}")
print(">>> Paper monte a 50%, R et S tombent a 25% chacun (rupture de symetrie).")=== 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 pour j1 : 0.0000
>>> Paper monte a 50%, R et S tombent a 25% chacun (rupture de symetrie).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 évident à l’intuition que la support enumeration révèle : aucun argument heuristique simple ne dirait « Paper 50 % » sans résoudre le système.
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.
PD = NormalFormGame(
["Coop", "Defect"], ["Coop", "Defect"],
[[3.0, 0.0], [5.0, 1.0]],
[[3.0, 5.0], [0.0, 1.0]])
eqs = support_enumeration(PD)
print(f"=== Dilemme du Prisonnier : {len(eqs)} equilibre(s) ===")
for s1, s2 in eqs:
sig1 = " ".join(f"{PD.acts1[i]}:{s1[i]:.3f}" for i in range(2))
sig2 = " ".join(f"{PD.acts2[i]}:{s2[i]:.3f}" for i in range(2))
print(f"sigma1 = {sig1}")
print(f"sigma2 = {sig2}")
print(">>> Unique equilibre = (Defect, Defect) en strategies pures (support taille 1).")
print(" L'algorithme retrouve l'equilibre pur, pas seulement mixte.")=== 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.
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).
MP = NormalFormGame(
["Heads", "Tails"], ["Heads", "Tails"],
[[1.0, -1.0], [-1.0, 1.0]],
[[-1.0, 1.0], [1.0, -1.0]])
eqs = support_enumeration(MP)
print(f"=== Pile ou Face : {len(eqs)} equilibre(s) ===")
for s1, s2 in eqs:
sig1 = " ".join(f"{MP.acts1[i]}:{s1[i]:.3f}" for i in range(2))
sig2 = " ".join(f"{MP.acts2[i]}:{s2[i]:.3f}" for i in range(2))
print(f"sigma1 = {sig1} ; sigma2 = {sig2}")
print(">>> Melange (0.5,0.5) retrouve, valeur 0 (confirme la tranche 1).")=== 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).
Nos équilibres sont calculés from-scratch (Gauss + indifférence). La marque de véracité : comparer avec nashpy, la bibliothèque de référence pour la théorie des jeux en Python. Si nos résultats coïncident, nous avons la preuve que l’algorithme pédagogique est correct — et nous comprenons maintenant ce que nashpy fait sous le capot.
# Verification SOTA : nashpy support_enumeration sur les 4 jeux.
# nashpy attend deux matrices de gains (j1, j2) et retourne les equilibres.
import nashpy as nash
def nashpy_equilibria(g: NormalFormGame):
game = nash.Game(g.U1, g.U2)
return list(game.support_enumeration())
print("=== Verification from-scratch vs nashpy ===\n")
for name, g in [("RPS", RPS), ("RPS biaise", Biased), ("Prisonnier", PD), ("Pile ou Face", MP)]:
mine = support_enumeration(g)
theirs = nashpy_equilibria(g)
# Comparaison : chaque equilibre from-scratch doit etre proche d'un equilibre nashpy
match = len(mine) == len(theirs)
if match:
for s1m, s2m in mine:
found_close = any(
np.allclose(s1m, np.round(t[0], 3), atol=1e-2) and
np.allclose(s2m, np.round(t[1], 3), atol=1e-2)
for t in theirs)
if not found_close:
match = False
status = "CORRESPOND" if match else "DIVERGENCE"
print(f"[{name}] from-scratch={len(mine)} eq, nashpy={len(theirs)} eq -> {status}")
print("\n>>> Tous les equilibres from-scratch correspondent a ceux de nashpy :")
print(" l'algorithme pedagogique reproduit le vrai outil SOTA (verdict SOTA-OK).")=== Verification from-scratch vs nashpy ===
[RPS] from-scratch=1 eq, nashpy=1 eq -> CORRESPOND
[RPS biaise] from-scratch=1 eq, nashpy=1 eq -> CORRESPOND
[Prisonnier] from-scratch=1 eq, nashpy=1 eq -> CORRESPOND
[Pile ou Face] from-scratch=1 eq, nashpy=1 eq -> CORRESPOND
>>> Tous les equilibres from-scratch correspondent a ceux de nashpy :
l'algorithme pedagogique reproduit le vrai outil SOTA (verdict SOTA-OK).Véracité démontrée (SOTA-OK, #3801). La comparaison terme à terme avec nashpy confirme que notre implémentation from-scratch — Gauss pivot partiel + indifférence + best-response — produit exactement les mêmes équilibres que la bibliothèque de référence. Nous n’avons pas contourné l’outil : nous l’avons reconstruit pour le comprendre, puis vérifié qu’il est fidèle. C’est la complémentarité pédagogique : le twin .NET fait la même chose en C#/BCL, ce twin Python en numpy, et nashpy reste le juge de paix.
Appliquez support_enumeration à 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 : support_enumeration sur la Bataille des Sexes (etudiant a completer)
# Indice 1 : construire le jeu BoS (cf. tranche 1).
# Indice 2 : appeler support_enumeration(BoS) et afficher chaque equilibre.
# Attendu : 3 equilibres (2 purs + 1 mixte).
# TODO etudiant
print("Exercice 1 a completer - Bataille des Sexes : 3 equilibres (2 purs + 1 mixte).")Exercice 1 a completer - Bataille des Sexes : 3 equilibres (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 support_enumeration. 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 support_enumeration.
print("Exercice 2 a completer - RPSLS 5x5 : definir la bimatrice et trouver l'equilibre.")Exercice 2 a completer - RPSLS 5x5 : definir la bimatrice et trouver l'equilibre.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 etudiant
from math import comb
Ns = [2, 4, 6, 8, 10]
print("Exercice 3 a completer - complexite C(2N,N)-1 pour N in {2,4,6,8,10}.")Exercice 3 a completer - complexite C(2N,N)-1 pour N in {2,4,6,8,10}.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.
| Concept | Implémentation Python |
|---|---|
| Espérance vs stratégie mixte | expected_vs_mixed1/2 |
| Élimination de Gauss | solve_linear (pivot partiel + rétro-substitution) |
| Sous-ensembles de taille k | subsets_of_size (itertools.combinations) |
| Support enumeration | support_enumeration (indifférence + best-response) |
| Vérification SOTA | nashpy.Game.support_enumeration |
nashpy — l’algorithme pédagogique est exact.Tranche 2 du twin .NET⇄Python (#4956 marathon). Support enumeration = résolution exacte des équilibres mixtes, pont théorie-jeux ↔︎ algèbre linéaire. Vérifié contre nashpy (SOTA-OK).