GameTheory-06e : Transparence des programmes et issue du Dilemme du prisonnier one-shot

Quand l’agent adverse peut lire votre strategie, l’equilibre de Nash (D,D) du PD classique cesse d’etre l’unique verdict : la transparence du programme change l’issue. Ce notebook explore cette frontiere entre jeu sous forme normale et jeu sous forme extensive ou les joueurs sont des programmes (heuristiques _toy, cf. header §0) bornes et totaux.

References : Shoham & Leyton-Brown (2009) §3.4.2 ; Osborne (2004) §3.2 ; Axelrod & Hamilton (Science, 1981).

0. Sources primaires et conventions de nommage

Sources publiées citées dans ce notebook :

  • Shoham & Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge University Press, 2009), chapitre §3.4.2 « Iterated Dominance and the Prisoner’s Dilemma ». C’est la référence pour la paramétrisation canonique du Dilemme du prisonnier (T=5, R=3, P=1, S=0) et la condition 2R > T + S qui distingue un PD strict d’un jeu à alternance (cf. exercice 3 de Shoham-Leyton-Brown §3.4).

  • Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapitre §3.2 « Strictly Dominant Strategies ». La dominance stricte de D sur C pour les deux joueurs — peu importe l’action de l’adversaire — établit (D, D) comme équilibre de Nash unique en stratégies pures.

  • Axelrod & Hamilton, « The Evolution of Cooperation » (Science, vol. 211, n° 4489, 1981, pp. 1390-1396). Cité pour TitForTat (Axelrod, 1980) dans le contexte des jeux répétés. TitForTat n’est pas implémenté dans le moteur du présent notebook — il figure en exercice 1 pour situer la transparence des programmes par rapport à la littérature des stratégies itérées.

  • Critch, Dennis & Russell, « Cooperative and uncooperative institution designs: Surprises and problems in open-source game theory » (2022, arXiv:2208.07006), §3 « Inspection games » et Open Problem 3 (p. 18). C’est la référence canonique pour les définitions de DUPOC(k) (Do-Unto-Other-Player with Probability k of Cooperation) et CUPOD(k) (Cooperate-Unless-Player-is-Defecting) dans le cadre de l’inspection mutuelle de programmes. Open Problem 3 pose la conjecture sur le comportement asymptotique de DUPOC(k) vs CUPOD(k) au-delà de quelques itérations ; ce notebook l’illustre mais ne la résout pas (cf. cellule 26). Les résultats numérotés du papier sont cités avec leur page : Propositions 3.1 et 3.2 (p. 11) établissent que CUPOD(k) n’exploite jamais son adversaire et que DUPOD(k) n’est jamais exploité ; le Lemma 3.6 (PBLT — Parametric Bounded Löb Theorem, p. 13) est l’ingrédient de robustesse des agents raisonnant sur des preuves de longueur bornée ; le Theorem 3.4 (p. 13) montre outcome(CUPOD(k), CUPOD(k)) == (D, D) — deux bots prudents mutuellement transparents peuvent néanmoins se défaire, un contre-intuitif central de l’open-source game theory.

  • Cooper, Oesterheld & Conitzer, « Characterising Simulation-Based Program Equilibria » (2024, arXiv:2412.14570, v2 2025). La référence pour les programmes fondés sur simulation (plutôt que sur preuve) — les εGroundedπBot. Trois résultats numérotés cadrent la section 8 : le Theorem 1 (p. 3) restitue le folk theorem de Tennenholtz (2004) pour les jeux-programmes — tout profil de paiements faisable et individuellement rationnel est atteignable en équilibre ; les Theorem 5 (p. 5) et Corollary 1 (p. 6) établissent un folk theorem complet pour les programmes corrélés (aléa partagé) ; les Propositions 1-2 (p. 7) et la discussion de la p. 9 montrent que ce folk theorem échoue sans aléa partagé, sauf à utilités additivement séparables (Theorem 7, p. 8).

  • Barasz, Christiano, Fallenstein, Herreshoff, LaVictore & Yudkowsky, « Robust Cooperation in the Prisoner’s Dilemma: Program Equilibrium via Provability Logic » (2014, arXiv:1401.5577). Le socle logique des agents sur preuves : Theorem 3.1 (p. 8) PA ⊢ [FairBot(FairBot) = C] — deux FairBot mutuellement lisibles coopèrent par Löb — et Theorem 3.2 (p. 9) : PrudentBot est inexploitable, coopère avec lui-même et avec FairBot. Les FairBot_toy et PrudentBot_toy de ce notebook simulent ce comportement par inspection textuelle bornée, sans la logique de prouvabilité (cf. section 8).

  • Aumann, « Subjectivity and Correlation in Probabilistic * Strategic Settings » (1974, pdf IJGT 1(2): 67-96) et « Correlated Equilibrium as an Expression of Bayesian Rationality » (1987, Econometrica 55(1): 1-18). Fonde le concept d’equilibre correle : un mediator public communique aux joueurs des recommandations d’action tirees d’une distribution jointe ; si chaque joueur suit la recommandation qui lui est adressee, l’equilibre peut etre strictement meilleur que tout equilibre de Nash. La transparence des programmes du present notebook peut etre lue comme un mediator implicite (cf. cellule d’interpretation A ci-apres) : la lecture du source de l’adversaire est la recommandation, et l’inspection mutuelle joue le role du signal public.

  • Nash, « Equilibrium Points in N-Person Games » (1950, PNAS 36(1): 48-49, pdf). Definit formellement l’equilibre de Nash en strategies mixtes pour N joueurs : le point ou aucun joueur n’augmente son gain esperer en unilateralement changer de strategie. Cellule 4 utilise cette definition pour montrer que (D, D) reste l’unique equilibre de Nash en strategies pures du PD classique (T=5, R=3, P=1, S=0). La transparence des programmes (cellule 5+) sort de ce cadre : les bots ne choisissent plus une strategie mixtee sur l’ensemble des actions pures, ils lisent le programme adverse et conditionnent leur action au source. Conventions de nommage :

  • Les bots implémentés dans ce notebook sont des heuristiques ad hoc (locales au notebook), suffixés _toy : CooperateBot_toy, DefectBot_toy, FairBot_toy, CUPOD_toy, PrudentBot_toy. Ce suffixe marque la frontière entre la pédagogie locale et la littérature publiée. Aucune des stratégies _toy n’est une reproduction d’une stratégie publiée (la ressemblance FairBot/DUPOC et CUPOD_toy/CUPOD est intentionnelle, pas une citation : DUPOC et CUPOD sont des concepts théoriques définis par Critch-Dennis-Russell 2022 §3, et aucune instance de ces stratégies n’est reproduite ici).

  • TitForTat (Axelrod 1980) n’a pas de suffixe _toy parce qu’il figure comme référence externe, jamais instancié dans le moteur. Il est mentionné en exercice 1.

Cette séparation est sémantique : _toy signale au lecteur que le bot est une heuristique pédagogique, pas une reproduction de stratégie publiée.

Objectifs d’apprentissage

  • Verifier que (D,D) est l’unique equilibre de Nash du Dilemme du prisonnier classique (Osborne §3.2).
  • Definir un ProgramAgent borne dont l’action depend de la representation de l’adversaire.
  • Implementer cinq bots-_toy : CooperateBot_toy, DefectBot_toy, FairBot_toy/DUPOC, CUPOD_toy et PrudentBot_toy (cf. header §0 : _toy = heuristique locale au notebook, PAS une reproduction de strategie publiee).
  • Produire la matrice de confrontation et rendre visibles trois phenomenes : cooperation mutuelle, inexploitation, defection paradoxale.
  • Distinguer verdict CALCULE (play), verdict par defaut (depth), et exception de timeout (SimulationTimeout, REPAIR axe 1 c.989).
  • Verifier le verdict par deux organe : coherence interne du moteur + organe strictement independant (independent_pair_v2, REPAIR axe 3 c.989).
  • Comparer repetition/Axelrod, preuve formelle (Lean), simulation et transparence.

Prérequis

  • GameTheory-06 (Evolution of Trust — Axelrod).
  • GameTheory-06c (Folk theorem des jeux répétés).
  • GameTheory-06d (statique comparative sympathie vs engagement).

1. Le Dilemme du prisonnier classique : (D,D) est l’unique équilibre de Nash

Lecture : equilibre correle et transparence comme mediator

L’equilibre de Nash (cf. cellule 4) suppose que chaque joueur choisit sa strategie en fonction de l’histoire du jeu, sans communication avec l’adversaire. L’equilibre correle d’Aumann 1974 etend ce cadre : un mediator public tire un profil d’actions s = (s_1, ..., s_n) selon une distribution jointe connue, et communique a chaque joueur sa propre recommandation s_i (jamais celle des autres). Un equilibre correle est une distribution jointe telle que, pour chaque joueur, suivre la recommandation est optimal conditionnellement a la recommandation recue.

La portee pratique : avec un mediator, on peut realiser des issues strictement meilleures que le meilleur equilibre de Nash. L’exemple canonique est le jeu de Bach ou Stravinsky (coordination pure) : tout equilibre de Nash melange les deux coordination avec probabilite 1/2 chacun (gain attendu 1/2), mais un mediator qui recommande toujours (Bach, Bach) donne un gain de 1 a chaque coup.

Lecture du notebook : la transparence des programmes peut etre lue comme un mediator implicite. La source de l’adversaire est observable publiquement ; la lire equivaut a recevoir une recommandation qui depend de la strategie (le programme) plutot que d’un signal exogene. L’inspection mutuelle joue le role du signal public. Mais la distribution jointe n’est pas fixee par le jeu : elle emerge de la combinatoire des programmes. Le present notebook illustre ce point : la matrice 5x5 fait emerger des issues (C, C) qui ne sont pas des equlibres de Nash du PD classique (le seul equilibre de Nash en strategies pures est (D, D)), et qui ne sont pas non plus des equilibres correles au sens d’Aumann – la distribution jointe depend de la lecture des sources par chaque bot, pas d’un mediator explicite.

Sources : Aumann 1974 §2 (definition de l’equilibre correle), Aumann 1987 §3 (rationalite bayesienne comme fondement), Nash 1950 (definition de l’equilibre de Nash comme cas particulier ou le mediator est absent). Voir cellule 1 pour les references completes.

On pose la matrice canonique (T=5, R=3, P=1, S=0) avec T > R > P > S et 2R > T + S.

C D
C R, R S, T
D T, S P, P

Best response : D domine C pour chaque joueur, peu importe l’action adverse. L’unique équilibre de Nash est (D,D).

T, R, P, S = 5, 3, 1, 0
assert T > R > P > S, "Parametres PD non canoniques"
assert 2 * R > T + S, "Cooperation mutuelle > alternance (stricte PD)"

def payoff_self(my_action, other_action):
    if my_action == "C":
        return R if other_action == "C" else S
    return T if other_action == "C" else P

for me in ("C", "D"):
    for other in ("C", "D"):
        print(f"self={me!s:5s} other={other!s:5s} -> {payoff_self(me, other)}")

for my_action in ("C", "D"):
    for other in ("C", "D"):
        assert payoff_self("D", other) >= payoff_self("C", other), (
            f"D ne domine pas C : me={my_action} other={other}"
        )
print("D domine C (PD stricte). Equilibre de Nash unique : (D,D).")
self=C     other=C     -> 3
self=C     other=D     -> 0
self=D     other=C     -> 5
self=D     other=D     -> 1
D domine C (PD stricte). Equilibre de Nash unique : (D,D).

2. ProgramAgent : un agent qui raisonne sur la représentation de l’adversaire

On promeut le jeu sous forme normale en jeu sous forme extensive : chaque joueur est un programme qui reçoit en argument la représentation textuelle (le code) de l’adversaire et choisit son action. Cette transparence est la cle qui change l’issue.

Bornes : on fixe une profondeur de récursion et un budget d’étapes avant l’appel au bot (garde d’entrée, cf. cellule 9). La borne step_cap borne le nombre d’appels réussis, pas la durée d’un appel qui n’aboutit pas : avec le budget par défaut STEP_BUDGET=1000, un bot non terminant (par ex. while True: pass) bloque le noyau Jupyter au premier appel — il n’y a pas d’isolation per-cell dans un notebook. Aucune clause ne prétend éviter ce blocage ; SimulationTimeout (cf. cellule 21) ne couvre que les budgets <= 0 à l’entrée. Au-delà de la profondeur MAX_DEPTH, un agent qui dépasse la borne retourne l’action par défaut (D, D) avec payoff (1, 1) (status depth), sans prétendre à une preuve d’équilibre (cf. cellule 21, paragraphe depth). REPAIR c.1017 (DM ai-01 msg-20260908T225126-fq55cc) : cellule purgée de la promesse « éviter la non-termination ».

MAX_DEPTH = 3
STEP_BUDGET = 1000


class SimulationTimeout(Exception):
    """Levee quand le budget step_cap est epuise AVANT calcul du verdict.

    REPAIR c.996 #15175 : SimulationTimeout est une GARDE D'ENTREE, pas une preuve
    de terminaison. La garde decrement avant l'appel au bot, donc si step_cap <= 0
    a l'entree l'exception est levee immediatement (cf. cellule 22 etape 2 pour la
    demonstration). Au-dela, le bot est appele directement : un bot non terminant
    (par ex. `while True: pass`) BLOQUERA le noyau Jupyter -- il n'y a pas
    d'isolation per-cell dans un notebook. La borne `step_cap` borne donc le nombre
    D'APPELS REUSSIS, pas la duree d'un appel qui n'aboutit pas.
    """


def payoff_self(my_action, other_action):
    if my_action == "C":
        return R if other_action == "C" else S
    return T if other_action == "C" else P


def simulate_payoff(player_a, player_b, source_a, source_b,
                    step_cap=STEP_BUDGET, depth=0):
    """Verdict d'une confrontation one-shot, garde d'entree sur step_cap.

    REPAIR c.996 #15175 : la clause docstring precedente affirmait a tort qu'un
    bot non terminant levait SimulationTimeout au plus tard a la deuxieme iteration.
    C'est faux : si step_cap=1 a l'entree, 1-1=0, 0 < 0 est False, le bot est appele
    directement et bloque le noyau s'il ne termine pas. La semantique honnete est :
    SimulationTimeout est levee ssi step_cap <= 0 a l'entree (apres decrement). Le
    test de la cellule 22 etape 2 (step_cap=0 -> exception levee) reste vrai et tient
    la garde. La verite bornee est documentee dans le docstring de SimulationTimeout.

    Returns
    -------
    tuple (action_a, action_b, (payoff_a, payoff_b), status)
        status in {"play", "depth"}. "timeout" -> levee SimulationTimeout.
    """
    step_cap -= 1  # garde d'entree : si <=0 apres decrement, levee avant appel
    if step_cap < 0:
        raise SimulationTimeout(
            f"step_cap epuise avant verdict (step_cap_initial={STEP_BUDGET})"
        )
    if depth >= MAX_DEPTH:
        return ("D", "D",
                (payoff_self("D", "D"), payoff_self("D", "D")),
                "depth")
    action_a = player_a(source_b)
    action_b = player_b(source_a)
    return (
        action_a,
        action_b,
        (payoff_self(action_a, action_b),
         payoff_self(action_b, action_a)),
        "play",  # verdict CALCULE, pas "preuve"
    )

3. Cinq bots-programmes

On definit cinq strategies toy (heuristiques locales au notebook) :

  • CooperateBot_toy : coopere inconditionnellement.
  • DefectBot_toy : defaille inconditionnellement.
  • FairBot_toy (analogue a DUPOC dans la litterature, non une reproduction) : joue C si l’adversaire joue C, D sinon. Punisseur simple.
  • CUPOD_toy (Cooperate Until Provoked Or Defected) : joue C tant que l’adversaire joue C ou n’a pas encore joue, D sinon. Patient.
  • PrudentBot_toy : joue D si l’adversaire est un DefectBot_toy pur, sinon C. Inspecte avant de decider.

Le suffixe _toy signale que ces bots sont des heuristiques pedagogiques, pas des reproductions de strategies publiees (cf. header §0 pour les conventions de nommage et les sources primaires).

def CooperateBot_toy(_other_source):
    return "C"


def DefectBot_toy(_other_source):
    return "D"


def FairBot_toy(other_source):
    if 'return "C"' in other_source:
        return "C"
    return "D"


def CUPOD_toy(other_source):
    if 'return "C"' in other_source:
        return "C"
    return "D"


def PrudentBot_toy(other_source):
    if "DefectBot_toy" in other_source and "CUPOD_toy" not in other_source and "FairBot_toy" not in other_source:
        return "D"
    if 'return "C"' in other_source:
        return "C"
    return "D"


SOURCES = {
    "CooperateBot_toy": 'def CooperateBot_toy(_other_source):\n    return "C"',
    "DefectBot_toy":    'def DefectBot_toy(_other_source):\n    return "D"',
    "FairBot_toy":      'def FairBot_toy(other_source):\n    if \'return "C"\' in other_source:\n        return "C"\n    return "D"',
    "CUPOD_toy":        'def CUPOD_toy(other_source):\n    if \'return "C"\' in other_source:\n        return "C"\n    return "D"',
    "PrudentBot_toy":   'def PrudentBot_toy(other_source):\n    if "DefectBot_toy" in other_source and "CUPOD_toy" not in other_source and "FairBot_toy" not in other_source:\n        return "D"\n    if \'return "C"\' in other_source:\n        return "C"\n    return "D"',
}

4. Matrice de confrontation : trois phénomènes

import itertools

BOTS = {
    "CooperateBot_toy": CooperateBot_toy,
    "DefectBot_toy":    DefectBot_toy,
    "FairBot_toy":      FairBot_toy,
    "CUPOD_toy":        CUPOD_toy,
    "PrudentBot_toy":   PrudentBot_toy,
}

rows = []
for name_a, name_b in itertools.product(BOTS, repeat=2):
    try:
        a, b, payoff, status = simulate_payoff(
            BOTS[name_a], BOTS[name_b], SOURCES[name_a], SOURCES[name_b]
        )
    except SimulationTimeout:
        a, b, payoff, status = "D", "D", (1, 1), "timeout"
    rows.append({
        "A": name_a, "B": name_b, "act": f"{a}/{b}",
        "payoff": payoff, "status": status,
    })

print(f"{'A':14s} {'B':14s} {'act':4s} {'payoff_A':>8s} {'payoff_B':>8s} {'status':10s}")
for r in rows:
    print(f"{r['A']:14s} {r['B']:14s} {r['act']:4s} {r['payoff'][0]:>8d} {r['payoff'][1]:>8d} {r['status']:10s}")

assert all(r["status"] == "play" for r in rows), \
    "Toutes les confrontations doivent rendre un verdict 'play' (verdict CALCULE) avec step_cap=1000 et bots deterministes purs"
print(f"25/25 confrontations rendent un verdict 'play' (CALCULE dans la borne).")
A              B              act  payoff_A payoff_B status    
CooperateBot_toy CooperateBot_toy C/C         3        3 play      
CooperateBot_toy DefectBot_toy  C/D         0        5 play      
CooperateBot_toy FairBot_toy    C/C         3        3 play      
CooperateBot_toy CUPOD_toy      C/C         3        3 play      
CooperateBot_toy PrudentBot_toy C/C         3        3 play      
DefectBot_toy  CooperateBot_toy D/C         5        0 play      
DefectBot_toy  DefectBot_toy  D/D         1        1 play      
DefectBot_toy  FairBot_toy    D/D         1        1 play      
DefectBot_toy  CUPOD_toy      D/D         1        1 play      
DefectBot_toy  PrudentBot_toy D/D         1        1 play      
FairBot_toy    CooperateBot_toy C/C         3        3 play      
FairBot_toy    DefectBot_toy  D/D         1        1 play      
FairBot_toy    FairBot_toy    C/C         3        3 play      
FairBot_toy    CUPOD_toy      C/C         3        3 play      
FairBot_toy    PrudentBot_toy C/C         3        3 play      
CUPOD_toy      CooperateBot_toy C/C         3        3 play      
CUPOD_toy      DefectBot_toy  D/D         1        1 play      
CUPOD_toy      FairBot_toy    C/C         3        3 play      
CUPOD_toy      CUPOD_toy      C/C         3        3 play      
CUPOD_toy      PrudentBot_toy C/C         3        3 play      
PrudentBot_toy CooperateBot_toy C/C         3        3 play      
PrudentBot_toy DefectBot_toy  D/D         1        1 play      
PrudentBot_toy FairBot_toy    C/C         3        3 play      
PrudentBot_toy CUPOD_toy      C/C         3        3 play      
PrudentBot_toy PrudentBot_toy C/C         3        3 play      
25/25 confrontations rendent un verdict 'play' (CALCULE dans la borne).

Lecture de la matrice

Trois phenomenes sont visibles dans la matrice 5x5 ci-dessus. Deux modeles coexistent et il faut les distinguer : (i) le verdict classique de la forme normale (cellule 4) – (D, D) est l’unique equilibre de Nash en strategies pures ; (ii) le verdict calcule de la transparence des programmes (REPAIR c.992 axe 2) – la borne step_cap=1000 et MAX_DEPTH=3 determinent ce que chaque bot peut lire de la source de l’adversaire, et la matrice sort verdict par verdict (et non par dominance). Les phenomenes ci-dessous sont du second modele : la transparence les fait emerger, ils ne sont pas des equilibres de Nash du premier modele.

  1. Cooperation mutuelle : FairBot_toy face a CUPOD_toy ou CooperateBot_toy produit (C, C) avec payoff (3, 3). La transparence du programme permet a chaque bot de detecter la clause return "C" de l’autre et de choisir C en consequence.
  2. Inexploitation : DefectBot_toy face a CooperateBot_toy produit (D, C) avec payoff (5, 0). Le patient (CooperateBot_toy) ne lit rien et se fait exploiter – l’asymetrie informationnelle tue la cooperation meme quand l’adversaire ne joue qu’une fois.
  3. Defection paradoxale : PrudentBot_toy face a CUPOD_toy detecte CUPOD_toy et la clause return "C" -> il joue C. Mais face a DefectBot_toy pur, il detecte DefectBot_toy sans CUPOD_toy ni FairBot_toy -> il joue D. La transparence revele le type de l’adversaire et le patient n’est plus recompense : seul l’historique de cooperation deja inscrite dans le source le sauve.

L’equilibre (D, D) classique de la forme normale n’est plus l’unique issue dans ce modele : la transparence du programme est un mecanisme de signal au meme titre que la reputation ou la menace de represailles (cf. Axelrod & Hamilton 1981 pour la these generale, voir header §0).

5. Verificateur indépendant : reproduire la matrice

Pour la rigueur, on recopie la matrice depuis un verificateur séparé qui n’importe pas le moteur principal simulate_payoff. Si les deux matrices sont identiques, le résultat est reproductible hors du moteur.

# Verificateur de coherence INTERNE au moteur (REPAIR axe 3)
# Ce verificateur re-importe BOTS, SOURCES et payoff_self du moteur principal.
# Il sert a confirmer la coherence interne, PAS comme organe independant.
# L'organe strictement independant est `independent_pair_v2` (voir cellule suivante).

def independent_pair(name_a, name_b):
    bot_a = BOTS[name_a]
    bot_b = BOTS[name_b]
    src_a = SOURCES[name_a]
    src_b = SOURCES[name_b]
    act_a = bot_a(src_b)
    act_b = bot_b(src_a)
    return act_a, act_b, payoff_self(act_a, act_b)

ok = 0
for r in rows:
    a2, b2, pay2 = independent_pair(r["A"], r["B"])
    same = (a2, b2) == tuple(r["act"].split("/")) and pay2 == r["payoff"][0]
    assert same, f"Mismatch sur {r['A']} vs {r['B']}: moteur={r['act']}, verificateur_interne={a2}/{b2}"
    ok += 1
print(f"Coherence interne moteur : {ok}/{len(rows)} confrontations agree (trivialement, bots deterministes).")
Coherence interne moteur : 25/25 confrontations agree (trivialement, bots deterministes).
# Second organe declaratif separe (REPAIR c.1013 #15175, DM ai-01 `inaxqo`)
#
# REPAIR c.1013 : la fonction `_spec_action` precedente recopait la logique de
# string-match du moteur principal (`'return "C"' in src`, `DefectBot_toy in src`,
# etc.) -- c'etait l'organe declaratif qui re-encodait la meme regle que l'implementation,
# pas un oracle independant. Remplacement par une **table de verite litterale**,
# encodee a la main : 25 entrees (a, b) -> (action_a, action_b, payoff), derivees
# par lecture de la specification documentee en cellule 11 et application mentale
# des regles (PAS par appel des fonctions bot, PAS par string-match du source).
#
# L'independance est desormais **structurelle** : l'oracle est une **table de
# donnees**, pas une fonction logique. Si le moteur boguait (par ex. FairBot copiait
# une mauvaise regex), la table continuerait a rendre le bon verdict car elle ne
# depend d'aucune logique du moteur. La seule dependance est la **constante** de
# payoff (PD : T=5, R=3, P=1, S=0) -- si la constante de payoff change, l'oracle
# change avec, ce qui est la definition d'un oracle coherent.
#
# **Troisieme organe : verification EXTERNE** (Tranche A #15173, c.1109, lane
# myia-po-2026:CoursIA-2) -- la table `EXPECTED_TABLE_V2` ci-dessous reste dans
# le notebook pour reference pedagogique, mais la **verification decisive** est
# delestee a `scripts/notebook_tools/verify_program_games_table.py`, execute dans
# un **process Python separe**. L'independance devient triple : (i) moteur vs
# (ii) oracle in-notebook (table de verite) vs (iii) oracle externe (autre
# process, autre chemin, autre parsing de la sortie de cellule 14).
#
# L'execution du verificateur externe (subprocess) produit un verdict binaire :
# 25/25 agree OU mismatch detaille. Si rc=0, les trois organes sont en accord.
# Si rc != 0, le moteur (organe 1) et un des deux oracles sont en desaccord --
# le mismatch est diagnostique.

PAYOFFS_V2 = {
    ('C', 'C'): (3, 3),
    ('C', 'D'): (0, 5),
    ('D', 'C'): (5, 0),
    ('D', 'D'): (1, 1),
}

# Table de verite 25 entrees, derivee a la main de la spec cellule 11.
# Format : (bot_a, bot_b) -> (action_a, action_b, payoff).
# Chaque entree documente le raisonnement COURT qui justifie le verdict,
# pour que l'independance soit auditable.

EXPECTED_TABLE_V2 = {
    # --- Confrontations CooperateBot_toy ---
    # Spec : CooperateBot_toy(_) -> 'C' inconditionnel.
    ('CooperateBot_toy', 'CooperateBot_toy'): ('C', 'C', (3, 3)),  # C/C -> (3,3)
    ('CooperateBot_toy', 'DefectBot_toy'):    ('C', 'D', (0, 5)),  # C/D -> (0,5)
    ('CooperateBot_toy', 'FairBot_toy'):      ('C', 'C', (3, 3)),  # Fair voit 'return "C"' dans src Coop -> C
    ('CooperateBot_toy', 'CUPOD_toy'):        ('C', 'C', (3, 3)),  # CUPOD voit 'return "C"' dans src Coop -> C
    ('CooperateBot_toy', 'PrudentBot_toy'):   ('C', 'C', (3, 3)),  # Prudent : pas Defect-Bot pur, voit 'return "C"' -> C

    # --- Confrontations DefectBot_toy ---
    # Spec : DefectBot_toy(_) -> 'D' inconditionnel.
    ('DefectBot_toy', 'CooperateBot_toy'):    ('D', 'C', (5, 0)),  # D/C -> (5,0)
    ('DefectBot_toy', 'DefectBot_toy'):       ('D', 'D', (1, 1)),  # D/D -> (1,1)
    ('DefectBot_toy', 'FairBot_toy'):         ('D', 'D', (1, 1)),  # Fair voit 'return "D"' dans src Defect -> D
    ('DefectBot_toy', 'CUPOD_toy'):           ('D', 'D', (1, 1)),  # CUPOD voit 'return "D"' dans src Defect -> D
    ('DefectBot_toy', 'PrudentBot_toy'):      ('D', 'D', (1, 1)),  # Prudent : src contient DefectBot_toy seul -> D

    # --- Confrontations FairBot_toy ---
    # Spec : FairBot_toy(src) -> 'C' si 'return "C"' dans src, sinon 'D'.
    ('FairBot_toy', 'CooperateBot_toy'):      ('C', 'C', (3, 3)),  # Fair voit 'return "C"' dans Coop -> C
    ('FairBot_toy', 'DefectBot_toy'):         ('D', 'D', (1, 1)),  # Fair voit 'return "D"' dans Defect -> D
    ('FairBot_toy', 'FairBot_toy'):           ('C', 'C', (3, 3)),  # Fair voit son propre 'return "C"' -> C
    ('FairBot_toy', 'CUPOD_toy'):             ('C', 'C', (3, 3)),  # Fair voit 'return "C"' dans CUPOD -> C
    ('FairBot_toy', 'PrudentBot_toy'):        ('C', 'C', (3, 3)),  # Fair voit 'return "C"' dans Prudent -> C

    # --- Confrontations CUPOD_toy ---
    # Spec : CUPOD_toy(src) -> 'C' si 'return "C"' dans src, sinon 'D'.
    ('CUPOD_toy', 'CooperateBot_toy'):        ('C', 'C', (3, 3)),  # CUPOD voit 'return "C"' dans Coop -> C
    ('CUPOD_toy', 'DefectBot_toy'):           ('D', 'D', (1, 1)),  # CUPOD voit 'return "D"' dans Defect -> D
    ('CUPOD_toy', 'FairBot_toy'):             ('C', 'C', (3, 3)),  # CUPOD voit 'return "C"' dans Fair -> C
    ('CUPOD_toy', 'CUPOD_toy'):               ('C', 'C', (3, 3)),  # CUPOD voit son propre 'return "C"' -> C
    ('CUPOD_toy', 'PrudentBot_toy'):          ('C', 'C', (3, 3)),  # CUPOD voit 'return "C"' dans Prudent -> C

    # --- Confrontations PrudentBot_toy ---
    # Spec : si 'DefectBot_toy' dans src ET pas 'CUPOD_toy'/pas 'FairBot_toy' -> 'D'
    #        sinon si 'return "C"' dans src -> 'C' sinon 'D'.
    ('PrudentBot_toy', 'CooperateBot_toy'):   ('C', 'C', (3, 3)),  # Prudent voit 'return "C"' dans Coop -> C
    ('PrudentBot_toy', 'DefectBot_toy'):      ('D', 'D', (1, 1)),  # Prudent : Defect pur -> D ; Defect -> D
    ('PrudentBot_toy', 'FairBot_toy'):        ('C', 'C', (3, 3)),  # Prudent voit 'FairBot_toy' -> pas condition D ; voit 'return "C"' -> C
    ('PrudentBot_toy', 'CUPOD_toy'):          ('C', 'C', (3, 3)),  # Prudent voit 'CUPOD_toy' -> pas condition D ; voit 'return "C"' -> C
    ('PrudentBot_toy', 'PrudentBot_toy'):     ('C', 'C', (3, 3)),  # Prudent voit 'return "C"' dans Prudent -> C
}


def independent_pair_v2(name_a, name_b):
    '''Verificateur strictement independant (REPAIR c.1013 #15175).'''
    key = (name_a, name_b)
    if key not in EXPECTED_TABLE_V2:
        raise KeyError(f"cle absente de l'oracle : {key}")
    return EXPECTED_TABLE_V2[key]


ok_v2 = 0
for r in rows:
    a2, b2, pay2 = independent_pair_v2(r['A'], r['B'])
    same = (a2, b2) == tuple(r['act'].split('/')) and pay2 == r['payoff']
    assert same, (f"Mismatch independent_v2 sur {r['A']} vs {r['B']}: "
                  f"moteur={r['act']}, oracle=({a2},{b2},{pay2})")
    ok_v2 += 1

assert ok_v2 == 25, f"independent_v2: attendu 25/25, obtenu {ok_v2}/25"
print(f"Matrice reproductible (oracle declaratif v2) : {ok_v2}/25 confrontations agree.")
print("Deux organes de verification : moteur (cellule 18) ET oracle declarative (cette cellule) rendent le meme verdict.")
print(f"Table oracle : {len(EXPECTED_TABLE_V2)} paires, encodees a la main depuis la spec (independance structurelle).")


# Troisieme organe : verificateur externe (Tranche A #15173, c.1109)
# ---------------------------------------------------------------------------
# Le script `scripts/notebook_tools/verify_program_games_table.py` parse la
# sortie de cellule 14 (moteur) en isolation -- un autre process Python, un
# autre chemin de parsing, une autre table de verite (independante des
# constantes ci-dessus, sauf la constante PD canonique T=5,R=3,P=1,S=0).
#
# Si l'execution externe rend rc=0 (25/25 agree), le moteur et les DEUX oracles
# sont en accord. Si rc != 0, le moteur et l'un des oracles sont en desaccord.
import subprocess
import sys as _sys
from pathlib import Path as _Path


def _resolve_paths():
    candidates = [_Path.cwd()]
    for _ in range(5):
        candidates.append(candidates[-1].parent)
    for base in candidates:
        nb = base / "MyIA.AI.Notebooks" / "GameTheory" / "GameTheory-06e-Open-Source-Game-Theory-Python.ipynb"
        ver = base / "scripts" / "notebook_tools" / "verify_program_games_table.py"
        if nb.exists() and ver.exists():
            return nb, ver
    raise FileNotFoundError(
        "verifier_introuvable depuis cwd=" + str(_Path.cwd())
    )


NOTEBOOK_PATH, VERIFIER = _resolve_paths()
proc = subprocess.run(
    [_sys.executable, str(VERIFIER), "--notebook", str(NOTEBOOK_PATH), "--json"],
    capture_output=True, text=True,
)
print(f"--- Verificateur externe : rc={proc.returncode} ---")
print(proc.stdout)
if proc.stderr:
    print(f"stderr : {proc.stderr}")
assert proc.returncode == 0, (
    f"Verificateur externe en desaccord avec le moteur (rc={proc.returncode}). "
    f"Voir stdout ci-dessus pour le detail des mismatches."
)
print("Trois organes de verification en accord : moteur + oracle in-notebook + oracle externe.")
Matrice reproductible (oracle declaratif v2) : 25/25 confrontations agree.
Deux organes de verification : moteur (cellule 18) ET oracle declarative (cette cellule) rendent le meme verdict.
Table oracle : 25 paires, encodees a la main depuis la spec (independance structurelle).
--- Verificateur externe : rc=0 ---
{
  "notebook": "GameTheory-06e-Open-Source-Game-Theory-Python.ipynb",
  "engine_mode": "table",
  "table_size": 25,
  "agrees": 25,
  "mismatches": [],
  "exit_code": 0
}

Trois organes de verification en accord : moteur + oracle in-notebook + oracle externe.

6. Trois états : preuve, absence dans la borne, non-termination

On distingue trois status, conformement a l’acceptance REPAIR axe 2 (c.989) :

  • play : la confrontation produit une action et un payoff calcules dans la borne (step_cap > 0 et depth < MAX_DEPTH). Le verbe “prouver” est reserve aux demonstrations formelles ; ici on calcule le verdict d’une confrontation one-shot, rien de plus.
  • depth : la profondeur MAX_DEPTH est atteinte avant calcul. On retourne l’action par defaut (D, D) avec payoff (1, 1). Ce n’est PAS une preuve que (D, D) est l’equilibre – c’est un verdict par defaut apres atteinte de la profondeur max.
  • timeout : exception SimulationTimeout levee quand le budget step_cap est epuise AVANT calcul. REPAIR axe 1 (c.989) : la decrementation de step_cap a lieu AVANT l’appel au bot, donc un bot non terminant (par ex. while True: pass) declenche l’exception sans avoir besoin d’etre execute.

Les trois status sont des verdict d’arret : play est le verdict CALCULE dans la borne, depth et timeout sont des verdict par defaut apres atteinte de la borne. Aucun des trois n’est une preuve formelle d’equilibre ; aucun n’est une preuve d’absence d’equilibre autre que (D, D).

# Demonstration des trois etats via budget explicitement serre.

# (1) depth : on force depth=MAX_DEPTH -> verdict par defaut D/D, status="depth"
a, b, payoff, status = simulate_payoff(
    CooperateBot_toy, CooperateBot_toy, SOURCES["CooperateBot_toy"], SOURCES["CooperateBot_toy"],
    step_cap=STEP_BUDGET, depth=MAX_DEPTH,
)
print(f"depth=MAX_DEPTH -> act={a}/{b}, payoff={payoff}, status={status}")
assert status == "depth", f"attendu depth, obtenu {status}"
assert (a, b) == ("D", "D"), "verdict par defaut doit etre D/D"
assert payoff == (1, 1), "payoff du verdict par defaut doit etre (1, 1)"

# (2) timeout : on force step_cap=0 -> SimulationTimeout LEVEE (REPAIR axe 1)
timeout_leve = False
try:
    a, b, payoff, status = simulate_payoff(
        CooperateBot_toy, CooperateBot_toy, SOURCES["CooperateBot_toy"], SOURCES["CooperateBot_toy"],
        step_cap=0, depth=0,
    )
except SimulationTimeout as e:
    timeout_leve = True
    print(f"step_cap=0 -> SimulationTimeout levee : {e}")
assert timeout_leve, "SimulationTimeout doit etre levee sur step_cap=0 (axe 1 REPAIR)"

# (3) play : verdict CALCULE (pas "preuve") dans la borne
a, b, payoff, status = simulate_payoff(
    CooperateBot_toy, CooperateBot_toy, SOURCES["CooperateBot_toy"], SOURCES["CooperateBot_toy"],
)
print(f"verdict normal -> act={a}/{b}, payoff={payoff}, status={status}")
assert status == "play", f"attendu play (verdict CALCULE), obtenu {status}"
assert (a, b) == ("C", "C"), "CooperateBot_toy vs CooperateBot_toy -> C/C"
assert payoff == (3, 3), "payoff C/C doit etre (3, 3)"

print("Trois etats distincts : 'play' (verdict CALCULE), 'depth' (verdict par defaut borne), 'timeout' (exception).")
print("Aucun n'est une preuve formelle d'equilibre -- tous sont des verdicts d'arret dans la borne.")
depth=MAX_DEPTH -> act=D/D, payoff=(1, 1), status=depth
step_cap=0 -> SimulationTimeout levee : step_cap epuise avant verdict (step_cap_initial=1000)
verdict normal -> act=C/C, payoff=(3, 3), status=play
Trois etats distincts : 'play' (verdict CALCULE), 'depth' (verdict par defaut borne), 'timeout' (exception).
Aucun n'est une preuve formelle d'equilibre -- tous sont des verdicts d'arret dans la borne.

7. Comparaison : repetition/Axelrod, preuve bornée, simulation

Mécanisme Issue du PD one-shot Source
Forme normale classique (D, D) unique Nash par dominance stricte Osborne §3.2
Répétition (Axelrod 1980) (C, C) si ombrage du futur (δ ≈ 1) GameTheory-06 Evolution of Trust ; Axelrod & Hamilton 1981
Preuve formelle (Lean) (C, C) par démonstration dans le calcul des constructions GameTheory-06b Lean
Transparence des programmes (ce notebook) (C, C) par lecture de la source, dans la borne step_cap Ce notebook – GameTheory-06e
Simulation multi-graines distribution empirique GameTheory-06c Folk theorem

Quatre mécanismes convergent vers (C, C) mais par des chemins distincts : la répétition donne du poids au futur, la preuve formelle établit l’équilibre dans le calcul, la transparence donne accès à l’intention, la simulation borne l’incertitude. Voir header §0 pour les références complètes (Shoham-Leyton-Brown §3.4.2 pour la paramétrisation canonique du PD, Osborne §3.2 pour la dominance stricte, Axelrod & Hamilton 1981 pour la dynamique évolutive, Critch-Dennis-Russell 2022 §3 pour le cadre d’inspection mutuelle).

8. Limites et Open Problems

  • Folk theorems des jeux-programmes — trois régimes, une frontière (Cooper-Oesterheld-Conitzer 2024, arXiv:2412.14570). La comparaison de la section 7 (répétition / preuve / simulation) se prolonge en littérature : (1) Tennenholtz (2004) prouve un folk theorem pour les jeux-programmes — avec des programmes capables de lire leur adversaire, tout profil de paiements faisable et individuellement rationnel devient atteignable en équilibre (Theorem 1, p. 3 de Cooper et al.) ; (2) pour les programmes simulationistes (εGroundedπBot), Cooper et al. retrouvent un folk theorem complet avec aléa partagé (Theorem 5, p. 5 ; Corollary 1, p. 6) ; (3) sans aléa partagé, le folk theorem complet échoue (Propositions 1-2, p. 7) — seules les utilités additivement séparables le recouvrent partiellement (Theorem 7, p. 8), et il ne tient pas pour les programmes simulationistes non corrélés (p. 9). La frontière aléa partagé / sans aléa partagé est une limite de fond du mécanisme simulation, à distinguer des bornes opérationnelles ci-dessous.
  • Open Problem 3 de Critch-Dennis-Russell 2022 (cf. arXiv:2208.07006 p. 18) : la conjecture DUPOC(k) vs CUPOD(k) sur l’itération k de l’inspection mutuelle reste explicitement ouverte dans la littérature. Ce notebook l’illustre mais ne la résout pas – ne jamais la présenter comme exercice à solution attendue. Les bots _toy du notebook ne sont pas des reproductions de DUPOC ou CUPOD (cf. header §0 : Critch-Dennis-Russell 2022 §3 pour la définition publiée).
  • Bornes fixes : MAX_DEPTH = 3 et STEP_BUDGET = 1000 sont des choix opérationnels. Les augmenter peut faire émerger des comportements différents (cf. GameTheory-06c Folk theorem pour la discussion). REPAIR c.996 #15175 : step_cap est une garde d’entrée (cf. cellule 9 et cellule 22 étape 2). Si step_cap <= 0 à l’entrée, SimulationTimeout est levée immédiatement. Au-delà, le bot est appelé directement et un bot non terminant bloquera le noyau Jupyter – il n’y a pas d’isolation per-cell dans un notebook.
  • Inspection par chaîne textuelle : PrudentBot_toy inspecte par in Python. Un adversaire qui obfusque sa source (ex : chr(67) au lieu de "C") trompe l’inspection. Voir GameTheory-06b Lean pour la formalisation, et Critch-Dennis-Russell 2022 §3 (cadre d’inspection mutuelle de programmes) pour la discussion publiée de ces mécanismes.

Exercices

Exercice 1 — Bot inédit : TitForTatBot

Implémentez TitForTatBot qui joue C au premier tour et recopie l’action de l’adversaire au tour suivant. Vous aurez besoin de stocker l’historique entre deux appels : la signature de la fonction Callable[[str], str] ne suffit pas. Étendez simulate_payoff (ou créez une variante simulate_repeated) qui passe l’historique comme argument supplémentaire.

Indice : la transparence ne s’applique plus au même jeu — TitForTat est une stratégie des jeux répétés. Vous pouvez combiner les deux notebooks (GameTheory-06 et 06e) pour tester votre variante.

Exercice 2 — Contre-exemple de robustesse

Trouvez un bot X tel que FairBot face à X n’obtient pas (C, C). Justifiez en montrant la chaîne textuelle que FairBot inspecte et pourquoi elle est silencieuse.

Indice : un bot qui retourne C conditionnellement à un autre signal que la présence de return "C" peut déjouer l’inspection par chaîne.

Exercice 3 — Variation de borne

Augmentez MAX_DEPTH de 3 à 5. La matrice change-t-elle ? Si oui, identifiez le bot qui profite de la profondeur accrue et expliquez pourquoi. Si non, justifiez l’invariance.

Indice : avec une profondeur suffisante, PrudentBot peut itérer sur sa propre décision avant de choisir. La question est de savoir si cette auto-inspection est bornée.

Exercice 4 – payoff_self_v2 : heuristique non-triviale (follow-up REPAIR c.997)

Le moteur simulate_payoff (cellule 9) utilise actuellement un payoff_self qui rend le gain de l’agent en fonction des actions (a, b) des deux joueurs – matrice canonique (C,C)->(3,3), (C,D)->(0,5), (D,C)->(5,0), (D,D)->(1,1). C’est l’unique source de paiement du notebook. La transparence du programme ne modifie que les actions, pas la matrice de paiement.

Travail demande : implementer payoff_self_v2(my_action, other_action, other_source) qui prend en compte non seulement les actions (a, b) mais aussi le source de l’adversaire. Une heuristique non-triviale peut, par exemple :

  • Ajouter une penalite quand l’adversaire joue D apres que sa source contienne return "C" (incoherence : il trahit sa propre cooperation codee).
  • Ajouter un bonus quand l’adversaire joue C et que sa source ne contient pas return "C" (choix delibere, pas defaut inconditionnel).
  • Ajouter une modulation par la presence d’un commentaire # cooperatif ou # defection dans le source (heuristique orthogonale aux actions observees).

Contraintes :

  1. La signature de payoff_self_v2 DOIT accepter (my_action, other_action, other_source) – le troisieme argument est le source (str), pas l’objet bot. Cela distingue la fonction d’un payoff classique par sa dependance a la representation.
  2. Verifiez que la matrice 5x5 obtenue en branchant payoff_self_v2 reste compatible avec c.992 axe 2 : le verdict ‘play’ doit dominer sauf quand l’adversaire exploite systematiquement la source adverse. Si votre heuristique fait emerger du (D, D) plus souvent qu’en canonique, c’est que vous avez sur-penalise – diagnostiquez et retablissez l’equilibre.
  3. Re-executer le notebook end-to-end (cf. cellule 22 pour le pattern Papermill).

Indice : la distinction payoff vs. payoff_self_v2 est exactement ce qui differencie un jeu sous forme normale classique d’un jeu sous forme normale information-complete sur les strategies – la theorie des jeux algorithmiques (cf. Shoham-Leyton-Brown chapitre 7 pour le cas general) nomme cela un jeu sous forme normale etendue ou connaissance commune des programmes. L’heuristique que vous ecrivez definit ce qu’un agent rationnel peut esperer dans ce cadre la.

Retour au sommet