GameTheory-19 : L’abstraction a dette mesurable

Navigation : << 18b-Casser-la-Composition | Index | 20-Chemin-Minimal-Robinson-Goforth >>

Le retournement

Face a un jeu trop grand pour etre resolu, on construit un jeu abstrait plus petit, on le resout, puis on retransporte la strategie vers le jeu original. Le geste ordinaire s’arrete a “l’abstraction semble bonne”. Kroer & Sandholm ne s’y arretent pas : ils bornent la qualite de la solution apres retour dans le jeu d’origine.

G --alpha--> G_tilde --solve--> sigma_tilde --rho--> sigma_G
       avec        Exploitabilite(sigma_G) <= epsilon(alpha, rho, ...)

D’ou le retournement de la question :

plus “cette representation compresse-t-elle ?” mais “QU’AI-JE LE DROIT D’OUBLIER SANS PERDRE LA PROPRIETE QUI M’INTERESSE ? »

K  <->  abstraction  <->  perte controlee  <->  DETTE DE REPRESENTATION

C’est la forme respectable de ce que le depot appelait “passage entre lentilles” – avec, cette fois, une dette chiffrable.

Le notebook

Trois exemples guides (resolus), chacun suivi d’un exercice non resolu, sur un jeu petit mais non trivial (2 joueurs, somme nulle, 6 etats) :

  1. Abstraire – fusionner des etats ou des actions ; mesurer la taille gagnee.
  2. Resoudre et relever – resoudre dans l’abstrait, retransporter, mesurer l’exploitabilite dans le jeu d’origine. C’est tout le point.
  3. La courbe de dette – faire varier la grosserete de l’abstraction et tracer taille contre exploitabilite. La forme de cette courbe est le livrable.

La frontiere honnete

Les bornes theoriques de Kroer & Sandholm sont RAPPORTEES (la digestion elle-meme signale qu’elle schematise le resultat plutot que sa formulation theorematique exacte). Le notebook mesure son cas ; il ne redemontre pas la borne. La distinction s’ecrit.

Prerequis

  • GameTheory-13-ImperfectInfo-CFR-Python.ipynb (information imparfaite)
  • Notions de strategie mixte, exploitabilite, regret

Duree estimee : 35 minutes

# Cellule 1 -- Construction du jeu d'origine G (2 joueurs, zero-sum, 6 etats)

import itertools
import random

# TRANCHAGE (ce qu'est G, explicitement) : G est la SOMME de 6 duels 2x2 independants,
# un duel par etat. Dans chaque etat s, chaque joueur choisit une action a in {0, 1}
# (strategie comportementale). Le gain total du joueur 1 est la somme des gains des
# 6 duels ; u2 = -u1 (zero-sum). Ce choix rend tout calculable EXACTEMENT : chaque
# duel 2x2 se resout par enumeration de supports, et G se resout duel par duel.
# C'est le socle sur quoi la dette d'abstraction se mesurera (exemples guides 2 et 3).

N_STATES = 6
N_PLAYERS = 2
N_ACTIONS = 2  # actions par joueur et par etat

random.seed(42)  # graine fixe : reproductibilite
PAYOFFS = {}
for state in range(N_STATES):
    for a_pair in itertools.product(range(N_ACTIONS), repeat=N_PLAYERS):
        v = random.randint(-3, 3)
        PAYOFFS[(state, a_pair)] = v  # gain du joueur 1 ; u2 = -v (zero-sum)

def duel_matrix(s):
    # Matrice du duel de l'etat s : M_s[a1][a2] = gain du joueur 1.
    return [[PAYOFFS[(s, (a1, a2))] for a2 in range(N_ACTIONS)] for a1 in range(N_ACTIONS)]

print(f"Jeu G : somme de {N_STATES} duels 2x2 independants (zero-sum), graine 42.")
print(f"Une strategie est comportementale : une action mixte par etat et par joueur.")
print()
print("Les 6 duels (ligne = action du joueur 1, colonne = action du joueur 2) :")
for s in range(N_STATES):
    print(f"  M_{s} = {duel_matrix(s)}")
Jeu G : somme de 6 duels 2x2 independants (zero-sum), graine 42.
Une strategie est comportementale : une action mixte par etat et par joueur.

Les 6 duels (ligne = action du joueur 1, colonne = action du joueur 2) :
  M_0 = [[2, -3], [-3, 2]]
  M_1 = [[-1, -2], [-2, -2]]
  M_2 = [[2, -3], [2, 2]]
  M_3 = [[1, -3], [1, 0]]
  M_4 = [[-3, -3], [-3, -2]]
  M_5 = [[-2, 1], [1, -3]]

Exemple guide 1 – Abstraire

Ce que fait l’exemple : sur le jeu G a 6 etats, une abstraction par fusion d’etats. Concretement :

  • Choisir une partition des 6 etats en 3 paires : {{s0, s1}, {s2, s3}, {s4, s5}}.
  • Definir le jeu abstrait G_tilde : chaque bloc devient un etat abstrait, muni d’un duel 2x2 moyenne des duels fusionnes.
  • Mesurer la taille gagnee : |G| = 6 etats vs |G_tilde| = 3 etats abstraits.

Ce qu’est G_tilde (tranchage explicite) : G_tilde est un jeu a etats, de meme forme que G – un duel 2x2 (moyenne) par etat abstrait, payoff total = somme. Comme le payoff de G est additif par etat, cette forme a la meme valeur que le jeu a une etape sur meta-actions (ou chaque joueur choisit d’un coup son action dans chaque etat abstrait) ; c’est la forme a etats que nous retenons, car la retransportation vers G y est naturelle : l’etat abstrait fournit une action mixte, chaque etat originel du bloc la recopie.

Sortie attendue : - G_tilde exhibe en toutes lettres (3 duels moyens 2x2). - Le facteur de reduction |G| / |G_tilde| = 2.

Note pedagogique : on n’a pas encore mesure la qualite de la solution. C’est l’exemple guide 2.

# Exemple guide 1 : construire G_tilde (fusion d'etats, duels moyennes)

PARTITION = [(0, 1), (2, 3), (4, 5)]  # 3 blocs de fusion
N_ABSTRACT = len(PARTITION)

def abstract_state(s, partition=PARTITION):
    # Index du bloc (etat abstrait) contenant l'etat originel s.
    for k, block in enumerate(partition):
        if s in block:
            return k
    return None  # inaccessible : la partition couvre tous les etats

def abstract_matrix(k, partition=PARTITION):
    # Duel abstrait du bloc k : MOYENNE des duels des etats fusionnes du bloc.
    block = partition[k]
    return [[sum(PAYOFFS[(s, (a1, a2))] for s in block) / len(block)
             for a2 in range(N_ACTIONS)]
            for a1 in range(N_ACTIONS)]

ABSTRACT_M = {k: abstract_matrix(k) for k in range(N_ABSTRACT)}

print(f"Jeu abstrait G_tilde : {N_ABSTRACT} etats abstraits (un duel 2x2 moyen par bloc), zero-sum.")
for k in range(N_ABSTRACT):
    rounded = [[round(x, 3) for x in row] for row in ABSTRACT_M[k]]
    print(f"  M~_{k} (bloc {PARTITION[k]}) = {rounded}")

reduction = N_STATES / N_ABSTRACT
print(f"\nFacteur de reduction : {N_STATES} etats / {N_ABSTRACT} etats abstraits = {reduction}")
Jeu abstrait G_tilde : 3 etats abstraits (un duel 2x2 moyen par bloc), zero-sum.
  M~_0 (bloc (0, 1)) = [[0.5, -2.5], [-2.5, 0.0]]
  M~_1 (bloc (2, 3)) = [[1.5, -3.0], [1.5, 1.0]]
  M~_2 (bloc (4, 5)) = [[-2.5, -1.0], [-1.0, -2.5]]

Facteur de reduction : 6 etats / 3 etats abstraits = 2.0

Exercice 1 – Une autre partition, une autre reduction

L’exemple guide 1 a fusionne les etats en 3 paires regulieres. Une abstraction a 4 etats existe aussi : la partition P4 = {0,1} {2} {3} {4,5} – deux blocs fusionnes, deux singletons.

Enonce : construisez le jeu abstrait G_tilde(P4) – un duel moyen par bloc, les singletons gardant leur duel tel quel – et affichez les 4 duels abstraits puis le facteur de reduction |G| / |G_tilde(P4)|.

Sortie attendue : 4 matrices (blocs + duels moyennees, arrondis a 3 decimales) et un facteur de reduction non entier.

Indices :

  • # Indice : abstract_matrix(k, partition) et abstract_state(s, partition) acceptent la partition en argument – l’exemple guide 1 les a definies generiques.
  • # Etape 1 : poser la partition sous la forme d’une liste de tuples, comme PARTITION dans l’exemple guide 1.
  • # Etape 2 : boucler sur les blocs, afficher la matrice moyenne arrondie.
  • # Etape 3 : le facteur de reduction est N_STATES / len(...).
# Exercice 1 : G_tilde pour la partition P4 -- a completer

PARTITION_4 = [(0, 1), (2,), (3,), (4, 5)]  # 4 etats abstraits : 2 blocs fusionnes, 2 singletons

# TODO etudiant : afficher les 4 duels abstraits de P4 (matrices moyennees, arrondies)
# puis le facteur de reduction |G| / |G_tilde(P4)|.
# Indice : abstract_matrix(k, partition) fait deja la moyenne d'un bloc.

print("Exercice a completer : construire G_tilde(P4) et mesurer la reduction.")
resultat = None  # TODO etudiant
Exercice a completer : construire G_tilde(P4) et mesurer la reduction.

Exemple guide 2 – Resoudre et relever

Ce que fait l’exemple : resoudre le jeu abstrait G_tilde exactement, retransporter la strategie vers le jeu d’origine (chaque etat originel d’un bloc joue la strategie de l’etat abstrait), puis mesurer l’exploitabilite de la strategie retransportee DANS le jeu d’origine.

Critere d’acceptation : l’exploitabilite est mesuree dans le jeu d’origine, jamais dans l’abstrait. C’est tout le point.

Resolution exacte, pas d’approximation iterative : chaque duel 2x2 est resolu par enumeration de supports – recherche d’un point selle pur (4 profils), sinon equilibre a support complet (formule fermee). Les duels de G_tilde etant independants (payoff additif), le resoudre bloc par bloc le resout exactement.

Definition (unique, reutilisee telle quelle par l’exemple guide 3) – l’exploitabilite d’une paire de strategies (sigma_1, sigma_2) dans un jeu zero-sum est la somme des gains des deux meilleures reponses :

expl(sigma_1, sigma_2) = max_{pi_1} u_1(pi_1, sigma_2)  +  max_{pi_2} u_2(sigma_1, pi_2)

Elle est nulle si et seulement si la paire est un equilibre de Nash. Comme u_2 = -u_1, elle se decompose autour de la valeur v du jeu :

expl = (BR_1 - v) + (BR_2 + v)

chaque terme mesurant ce qu’un joueur gagne a devier – la dette se lit des deux cotes.

# Exemple guide 2 : solve exact de G_tilde, retransport, mesure DANS G

def solve_2x2(m):
    """Equilibre EXACT d'un duel 2x2 zero-sum, par ENUMERATION DE SUPPORTS.
    Retourne (p, q, val) : p[a1] = proba de ligne a1 (joueur 1),
    q[a2] = proba de colonne a2 (joueur 2), val = valeur du duel."""
    a, b, c, d = m[0][0], m[0][1], m[1][0], m[1][1]
    # Supports purs : point selle (maximum de sa colonne ET minimum de sa ligne)
    for (i, j) in itertools.product(range(N_ACTIONS), repeat=2):
        if m[i][j] == max(m[x][j] for x in range(N_ACTIONS)) and \
           m[i][j] == min(m[i][y] for y in range(N_ACTIONS)):
            p = [1.0, 0.0] if i == 0 else [0.0, 1.0]
            q = [1.0, 0.0] if j == 0 else [0.0, 1.0]
            return p, q, m[i][j]
    # Support mixte complet : formule fermee (denominateur non nul car pas de selle)
    den = a - b - c + d
    p_star, q_star = (d - c) / den, (d - b) / den
    assert 0 <= p_star <= 1 and 0 <= q_star <= 1
    return [p_star, 1 - p_star], [q_star, 1 - q_star], (a * d - b * c) / den

# Valeur exacte de G : somme des valeurs des 6 duels (ils sont independants).
VALUE_G = sum(solve_2x2(duel_matrix(s))[2] for s in range(N_STATES))

# Resolution EXACTE de G_tilde : un equilibre par etat abstrait.
SIGMA_TILDE = {k: solve_2x2(ABSTRACT_M[k]) for k in range(N_ABSTRACT)}

# Retransport : l'etat originel s recopie la strategie de son bloc.
def sigma_1(s, a):
    return SIGMA_TILDE[abstract_state(s)][0][a]

def sigma_2(s, a):
    return SIGMA_TILDE[abstract_state(s)][1][a]

# UNE fonction d'exploitabilite -- definition de l'enonce, employee aussi par l'exemple guide 3.
def best_response_terms(payoffs, sig1, sig2, n_states=N_STATES):
    """Les deux termes de l'exploitabilite :
    (max_pi1 u_1(pi_1, sig_2), max_pi2 u_2(sig_1, pi_2))."""
    br1 = sum(max(sum(sig2(s, a2) * payoffs[(s, (a1, a2))] for a2 in range(N_ACTIONS))
                  for a1 in range(N_ACTIONS))
              for s in range(n_states))
    br2 = sum(max(sum(sig1(s, a1) * (-payoffs[(s, (a1, a2))]) for a1 in range(N_ACTIONS))
                  for a2 in range(N_ACTIONS))
              for s in range(n_states))
    return br1, br2

def exploitability(payoffs, sig1, sig2, n_states=N_STATES):
    """expl(sig_1, sig_2) = max_pi1 u_1(pi_1, sig_2) + max_pi2 u_2(sig_1, pi_2).
    Nulle si et seulement si (sig_1, sig_2) est un equilibre de Nash (zero-sum)."""
    br1, br2 = best_response_terms(payoffs, sig1, sig2, n_states)
    return br1 + br2

br1, br2 = best_response_terms(PAYOFFS, sigma_1, sigma_2)
expl = exploitability(PAYOFFS, sigma_1, sigma_2)

print(f"Valeur exacte de G (somme des 6 duels) : v(G) = {VALUE_G:.4f}")
print()
print("Resolution exacte de G_tilde (enumeration de supports, bloc par bloc) :")
for k in range(N_ABSTRACT):
    p, q, val = SIGMA_TILDE[k]
    print(f"  bloc {PARTITION[k]} : p* = [{p[0]:.3f}, {p[1]:.3f}]"
          f"  q* = [{q[0]:.3f}, {q[1]:.3f}]  val = {val:+.3f}")
print()
print("Mesure DANS G de la strategie retransportee :")
print(f"  BR_1 = max_pi1 u_1(pi_1, sigma_2) = {br1:.4f}"
      f"   (v(G) = {VALUE_G:.4f}, ecart = {br1 - VALUE_G:+.4f})")
print(f"  BR_2 = max_pi2 u_2(sigma_1, pi_2) = {br2:.4f}"
      f"   (-v(G) = {-VALUE_G:.4f}, ecart = {br2 + VALUE_G:+.4f})")
print(f"  expl = (BR_1 - v) + (BR_2 + v) = {br1 - VALUE_G:.4f} + {br2 + VALUE_G:.4f} = {expl:.4f}")
print()
print(f"Exploitabilite = {expl:.4f} > 0 : la strategie retransportee n'est PAS un equilibre de G.")
print("La perte causee par l'abstraction est chiffree, des deux cotes du jeu.")
Valeur exacte de G (somme des 6 duels) : v(G) = -4.2143

Resolution exacte de G_tilde (enumeration de supports, bloc par bloc) :
  bloc (0, 1) : p* = [0.455, 0.545]  q* = [0.455, 0.545]  val = -1.136
  bloc (2, 3) : p* = [0.000, 1.000]  q* = [0.000, 1.000]  val = +1.000
  bloc (4, 5) : p* = [0.500, 0.500]  q* = [0.500, 0.500]  val = -1.750

Mesure DANS G de la strategie retransportee :
  BR_1 = max_pi1 u_1(pi_1, sigma_2) = -2.8182   (v(G) = -4.2143, ecart = +1.3961)
  BR_2 = max_pi2 u_2(sigma_1, pi_2) = 4.7273   (-v(G) = 4.2143, ecart = +0.5130)
  expl = (BR_1 - v) + (BR_2 + v) = 1.3961 + 0.5130 = 1.9091

Exploitabilite = 1.9091 > 0 : la strategie retransportee n'est PAS un equilibre de G.
La perte causee par l'abstraction est chiffree, des deux cotes du jeu.

Lecture du resultat (exemple guide 2)

La dette de 1.9091 se decompose de facon inegale : le joueur 1 perd 1.3961 a ne pas devier (ecart BR_1 - v), le joueur 2 seulement 0.5130. En moyennant les duels de chaque bloc, l’abstraction produit une strategie que chaque adversaire peut exploiter – les deux ecarts sont strictement positifs. Et le solve est exact : 6 duels originels (pour v(G)) et 3 duels abstraits resolus par enumeration de supports, aucun processus iteratif.

Exercice 2 – L’atlas des paires : quelle fusion coute cher ?

La conclusion de l’exemple guide 3 le dit : la dette ne depend pas que de la taille de l’abstraction, mais de quels etats on fusionne. Verifiez-le systematiquement.

Enonce : pour chacune des 15 paires {s, t} d’etats, construisez la partition a 5 blocs qui fusionne exactement cette paire (les 4 autres etats restent des singletons), resolvez-la exactement, retransportez, mesurez l’exploitabilite dans G. Affichez le classement des 15 paires par dette croissante et repondez : quelles fusions sont gratuites (exploitabilite nulle), laquelle coute le plus cher ?

Sortie attendue : un tableau {s, t} -> exploitabilite, trie, puis une phrase de verdict.

Indices :

  • # Indice : itertools.combinations(range(N_STATES), 2) enumere les 15 paires.
  • # Indice : le schema est celui de solve_and_transport dans l’exemple guide 3 – partition, solve bloc par bloc, retransport, exploitability.
  • # Etape 1 : construire la partition blocs_fusionnes + singletons restants pour chaque paire.
  • # Etape 2 : collecter (paire, exploitabilite), trier, afficher.
  • # Indice : au moins une paire devrait rendre une exploitabilite nulle – souvenez-vous de la ligne constante de M_2.
# Exercice 2 : atlas des paires -- quelle fusion coute cher ? -- a completer

# TODO etudiant : pour chaque paire {s, t} parmi les 15, partition a 5 blocs fusionnant
# exactement cette paire, solve exact + retransport + exploitability dans G,
# puis classement des paires par dette croissante.

print("Exercice a completer : l'atlas des paires (15 fusions, 15 exploitabilites).")
resultat = None  # TODO etudiant
Exercice a completer : l'atlas des paires (15 fusions, 15 exploitabilites).

Exemple guide 3 – La courbe de dette

Ce que fait l’exemple : faire varier la grossierete de l’abstraction et tracer la courbe de dette : taille du jeu abstrait (nombre d’etats abstraits) en abscisse, exploitabilite de la strategie retransportee dans le jeu d’origine en ordonnee. A chaque point : resolution exacte de G_tilde, retransport, mesure par la meme fonction exploitability qu’a l’exemple guide 2.

Les 4 partitions forment une chaine de raffinement – chaque bloc d’une partition grossiere est une reunion de blocs de la partition fine :

Point Partition Blocs
6 etats P6 {0} {1} {2} {3} {4} {5}
4 etats P4 {0,1} {2} {3} {4,5}
3 etats P3 {0,1} {2,3} {4,5}
2 etats P2 {0,1,2,3} {4,5}

Sur une chaine, l’argument qualitatif tient : partition plus grossiere = strategie retransportee plus contrainte. Mais la monotonie ne se decrete pas – le point a 6 etats doit rendre exactement 0 (sanity check : resoudre G puis retransporter ne change rien), et la forme des points suivants sera nommee d’apres la sortie, pas annoncee a l’avance.

Sortie attendue : un tableau de 4 points (taille, v(G_tilde), exploitabilite) et la forme mesuree nommee apres coup. La forme de cette courbe est le livrable.

# Exemple guide 3 : courbe de dette sur la chaine P6 < P4 < P3 < P2

PARTITIONS = [
    (6, [(0,), (1,), (2,), (3,), (4,), (5,)]),
    (4, [(0, 1), (2,), (3,), (4, 5)]),
    (3, [(0, 1), (2, 3), (4, 5)]),
    (2, [(0, 1, 2, 3), (4, 5)]),
]

# Verification de la chaine : chaque bloc de la partition fine est inclus
# dans un bloc de la partition grossiere qui la suit.
def refines(fine, coarse):
    return all(any(set(fb) <= set(cb) for cb in coarse) for fb in fine)

print("Verification de la chaine de raffinement :")
for (n_fine, p_fine), (n_coarse, p_coarse) in zip(PARTITIONS, PARTITIONS[1:]):
    ok = refines(p_fine, p_coarse)
    assert ok, f"P{n_fine} ne raffine pas P{n_coarse}"
    print(f"  P{n_fine} raffine P{n_coarse} : OK")
print()

def solve_and_transport(partition):
    # Solve exact de G_tilde pour la partition donnee, puis retransport vers G.
    sigma_tilde = {k: solve_2x2(abstract_matrix(k, partition)) for k in range(len(partition))}
    where = {s: k for k, block in enumerate(partition) for s in block}
    sig1 = lambda s, a: sigma_tilde[where[s]][0][a]
    sig2 = lambda s, a: sigma_tilde[where[s]][1][a]
    value_tilde = sum(sigma_tilde[k][2] for k in sigma_tilde)
    return sig1, sig2, value_tilde

print("Courbe de dette (solve exact + retransport + exploitability dans G) :")
print(f"  {'|G_tilde|':>9}  {'v(G_tilde)':>10}  {'exploitability':>14}")
points = []
for n_abs, partition in PARTITIONS:
    sig1, sig2, v_tilde = solve_and_transport(partition)
    e = exploitability(PAYOFFS, sig1, sig2)
    points.append((n_abs, e))
    print(f"  {n_abs:>9}  {v_tilde:>10.4f}  {e:>14.4f}")

# Sanity check : sans abstraction, l'exploitabilite doit etre EXACTEMENT nulle.
assert abs(points[0][1]) < 1e-12, "P6 doit rendre 0 : solve exact + retransport identiques"

# Verdict : forme nommee D'APRES LA SORTIE.
non_dec = all(points[i][1] <= points[i + 1][1] + 1e-9 for i in range(len(points) - 1))
plateau = abs(points[1][1] - points[2][1]) < 1e-9
forme = ("monotone non-decroissante" if non_dec else "NON monotone") + \
        (" avec un palier P4 = P3" if plateau else "")
print(f"\nForme mesuree : {forme}")

# Diagnostic du palier : contribution de chaque etat a l'exploitabilite, P4 vs P3.
def per_state_expl(sig1, sig2):
    contrib = {}
    for s in range(N_STATES):
        br1_s = max(sum(sig2(s, a2) * PAYOFFS[(s, (a1, a2))] for a2 in range(N_ACTIONS))
                    for a1 in range(N_ACTIONS))
        br2_s = max(sum(sig1(s, a1) * (-PAYOFFS[(s, (a1, a2))]) for a1 in range(N_ACTIONS))
                    for a2 in range(N_ACTIONS))
        contrib[s] = br1_s + br2_s
    return contrib

sig1_4, sig2_4, _ = solve_and_transport(PARTITIONS[1][1])
sig1_3, sig2_3, _ = solve_and_transport(PARTITIONS[2][1])
d4 = per_state_expl(sig1_4, sig2_4)
d3 = per_state_expl(sig1_3, sig2_3)
print("\nDiagnostic du palier P4 = P3 (contribution de chaque etat) :")
for s in range(N_STATES):
    print(f"  etat {s} : P4 -> {d4[s]:+.4f}   P3 -> {d3[s]:+.4f}")
m2 = duel_matrix(2)
print(f"\nExplication : M_2 = {m2}, sa ligne 1 (action du joueur 1) est constante")
print(f"[{m2[1][0]}, {m2[1][1]}] : entre P4 et P3 la colonne retransportee pour l'etat 2")
print("passe de 0 a 1, sans qu'aucun gain ne bouge -- la fusion de {2} et {3} est gratuite.")
Verification de la chaine de raffinement :
  P6 raffine P4 : OK
  P4 raffine P3 : OK
  P3 raffine P2 : OK

Courbe de dette (solve exact + retransport + exploitability dans G) :
  |G_tilde|  v(G_tilde)  exploitability
          6     -4.2143          0.0000
          4     -0.8864          1.9091
          3     -1.8864          1.9091
          2     -1.9342          6.4211

Forme mesuree : monotone non-decroissante avec un palier P4 = P3

Diagnostic du palier P4 = P3 (contribution de chaque etat) :
  etat 0 : P4 -> +0.4545   P3 -> +0.4545
  etat 1 : P4 -> +0.4545   P3 -> +0.4545
  etat 2 : P4 -> +0.0000   P3 -> +0.0000
  etat 3 : P4 -> +0.0000   P3 -> +0.0000
  etat 4 : P4 -> +0.5000   P3 -> +0.5000
  etat 5 : P4 -> +0.5000   P3 -> +0.5000

Explication : M_2 = [[2, -3], [2, 2]], sa ligne 1 (action du joueur 1) est constante
[2, 2] : entre P4 et P3 la colonne retransportee pour l'etat 2
passe de 0 a 1, sans qu'aucun gain ne bouge -- la fusion de {2} et {3} est gratuite.

Exercice 3 – Meme taille, autre dette

L’exemple guide 3 a mesure une chaine de raffinement – chaque partition grossiere reunissait des blocs de la fine. Rien n’oblige une abstraction de vivre sur cette chaine.

Enonce : construisez une partition P3B de 3 blocs hors de la chaine (par exemple {0,4} {1,5} {2,3}), resolvez-la exactement, retransportez, mesurez l’exploitabilite dans G, et comparez a celle de P3 (1.9091). Meme taille de jeu abstrait, meme taille seulement ? Concluez en une phrase.

Sortie attendue : les 3 duels abstraits de P3B, son exploitabilite dans G, et la comparaison avec P3.

Indices :

  • # Indice : les fonctions generiques (abstract_matrix, solve_2x2, exploitability) marchent pour toute partition – la chaine n’etait qu’un choix.
  • # Etape 1 : poser PARTITION_3B = [(0, 4), (1, 5), (2, 3)].
  • # Etape 2 : meme schema que l’exemple guide 3 – solve bloc par bloc, retransport, mesure dans G.
  • # Etape 3 : la comparaison se fait a taille egale (3 etats abstraits dans les deux cas).
# Exercice 3 : une partition de taille 3 hors de la chaine -- a completer

PARTITION_3B = [(0, 4), (1, 5), (2, 3)]  # 3 blocs, hors chaine de raffinement

# TODO etudiant : solve exact de G_tilde(P3B), retransport vers G, mesure de
# l'exploitabilite, comparaison avec P3 (1.9091) et verdict en une phrase.

print("Exercice a completer : la dette de P3B contre celle de P3, a taille egale.")
resultat = None  # TODO etudiant
Exercice a completer : la dette de P3B contre celle de P3, a taille egale.

Conclusion : la dette de representation

L’abstraction n’est pas un raccourci gratuit : c’est un emprunt que l’agent fait sur la qualite de la solution. La courbe de dette chiffre cet emprunt (solve exact partout, meme fonction exploitability, mesure dans G) :

Taille abstraite v(G_tilde) Exploitabilite dans G
6 (pas d’abstraction) -4.2143 0.0000 (sanity check exact)
4 -0.8864 1.9091
3 -1.8864 1.9091
2 -1.9342 6.4211

La forme mesuree : monotone non-decroissante, avec un palier P4 = P3. Le palier n’est pas un artefact – le diagnostic par etat l’explique : la dette se concentre sur les blocs {0,1} (0.4545 par etat) et {4,5} (0.5000 par etat), tandis que la fusion {2},{3} -> {2,3} est gratuite (la ligne 1 de M_2 est constante : la colonne retransportee change sans qu’aucun gain ne bouge). Lecon operationnelle : la dette ne depend pas que de la taille de l’abstraction, mais de quels etats on fusionne. Deux abstractions de meme taille peuvent avoir des dettes tres differentes – et sur une autre chaine, ou une autre graine, un decrochement local (non-monotonie) est possible ; ce notebook mesure SA chaine, il ne decrete pas une loi.

Noter aussi la colonne v(G_tilde) : la valeur du jeu abstrait derive elle aussi (-0.89 pour P4, contre v(G) = -4.21) – une preuve de plus que la qualite d’une abstraction se mesure dans le jeu d’origine (critere d’acceptation de l’exemple guide 2), jamais dans l’abstrait.

La frontiere honnete

Les bornes theoriques de Kroer & Sandholm 2014, 2016 – exploitabilite apres abstraction bornee par un terme en O(sqrt(kappa)) ou O(sqrt(N)) selon le contexte – sont RAPPORTEES, pas redemontrees. Le notebook mesure son cas precis (fusion d’etats, zero-sum, 6 etats, solve exact) : 4 points sur UNE chaine de raffinement et UNE graine. C’est une mesure, pas une preuve de borne ; et la courbe est non-decroissante ICI, sur cette chaine – le palier P4 = P3 rappelle que la stricte monotonie n’est pas garantie en general.

NOTION PORTEUSE : Exploitabilite <= epsilon(alpha, rho, ...).    (Kroer-Sandholm, rapportee)
NOTION MESUREE  : Exploitabilite_observee = f(|G_tilde|).        (ce notebook, 4 points)

Le notebook ne pretend pas que f est lineaire en 1/|G_tilde| ; il observe la tendance sur 4 points, ce qui est une preuve de tendance, pas une preuve de borne.

Suite (hors scope ce notebook, questions ouvertes)

  • Compagnon Lean : la non-decroissance sur chaine de raffinement observee ici merite un statut formel – la prouver sur un domaine jouable (2 etats, 2 partitions), ou y exhiber un contre-exemple. La question est laissee ouverte.
  • Compagnon de la strate 7 : la question “qu’ai-je le droit d’OUBLIER” presuppose un critere deja choisi. La strate 7 demande : “comment APPARAIT un critere qui n’existait pas encore ?” – voir GameTheory-03g-Deux-Especes-de-Fleches-Python.

Refs : #12229 · Kroer & Sandholm 2014, 2016 (abstraction et bornes de qualite) · Brown & Sandholm 2017 (safe subgame solving) · Vervaeke #11488 (extraire les primitives)

Retour au sommet