Argumentation abstraite de Dung — sémantiques grounded, preferred, stable

Notebook fondationnel (non-agentique) de la série Argument_Analysis. Il précède et éclaire l’aperçu de 2-formal §6 et l’utilisation du solveur Tweety dans Tweety-5.

Pourquoi ce notebook

Le notebook 2-formal §6 invoque la sémantique grounded de Dung via le solveur Tweety (JVM) comme une boîte noire : on appelle SimpleGroundedReasoner, on récupère une extension. Mais que calcule exactement ce solveur, et pourquoi existe-t-il plusieurs sémantiques concurrentes (grounded, preferred, stable) qui ne donnent pas toujours le même verdict ?

Ce notebook répond à cette question en construisant les sémantiques de zéro, en pur Python standard, sans JVM ni solveur externe. L’objectif n’est pas de remplacer Tweety (moins performant, non utilisable en production sur de grands graphes) mais de rendre transparent ce que le solveur fait — de façon à ce que l’appel getModels(theory) du notebook 2-formal cesse d’être magique.

Référence : Dung, On the Acceptability of Arguments and its Fundamental Rôle in Nonmonotonic Reasoning, Logic Programming and n-Person Games (Artificial Intelligence, 1995). Le formalisme y est introduit dans sa forme la plus abstraite, indépendante de toute structure interne des arguments.

1. Cadre d’argumentation abstrait (Dung 1995)

Un abstract argumentation framework (AF) est un couple \(F = \langle A, R \rangle\) où :

• \(A\) est un ensemble fini d’arguments (des symboles opaques — on ne s’intéresse pas à leur contenu interne, seulement à qui attaque qui) ;
• \(R \subseteq A \times A\) est une relation d’attaque : \((a, b) \in R\) se lit « \(a\) attaque \(b\) ».

L’abstraction est délibérée : la théorie de Dung porte sur la structure du débat (graphe d’attaque), pas sur le sens des arguments. Deux débats aux graphes identiques reçoivent le même verdict d’acceptabilité, quelle que soit leur matière. C’est cette abstraction qui rend les sémantiques calculables et comparables.

Implémentons le cadre :

from itertools import chain, combinations


class AF:
    """Cadre d'argumentation abstrait de Dung : <args, attacks>."""

    def __init__(self, args, attacks):
        self.args = set(args)
        self.attacks = set(attacks)  # ensemble de couples (attaquant, attaque)

    def attackers(self, x):
        """Arguments qui attaquent directement x."""
        return {a for (a, b) in self.attacks if b == x}

    def __repr__(self):
        att = ", ".join(f"{a}->{b}" for (a, b) in sorted(self.attacks))
        return f"AF(args={sorted(self.args)}, attacks=[{att}])"


# Un petit exemple ludique pour démarrer : a et b s'attaquent mutuellement.
af0 = AF({"a", "b"}, {("a", "b"), ("b", "a")})
print(af0)
print("Attaquants de a :", af0.attackers("a"))

AF(args=['a', 'b'], attacks=[a->b, b->a])
Attaquants de a : {'b'}

2. De la conflictualité à l’admissibilité

Toute la théorie repose sur une chaîne de définitions emboîtées. Chaque notion prépare la suivante.

2.1 Sans conflit interne

Un ensemble \(S\) est sans conflit (conflict-free) si aucun de ses membres n’en attaque un autre : \(\nexists a, b \in S\) tels que \((a, b) \in R\).

C’est la condition minimale de cohérence : un ensemble qui se contredit n’est pas une position défendable.

def is_conflict_free(af, S):
    """True si aucun argument de S n'en attaque un autre dans S."""
    S = set(S)
    for (a, b) in af.attacks:
        if a in S and b in S:
            return False
    return True


print("a,b se battent -> {a,b} sans conflit ?", is_conflict_free(af0, {"a", "b"}))
print("{a} seul  -> sans conflit ?", is_conflict_free(af0, {"a"}))

a,b se battent -> {a,b} sans conflit ? False
{a} seul  -> sans conflit ? True

2.2 Défait et défendu

Pour aller plus loin que la simple absence de conflit, il faut formaliser la notion de défense :

• \(S\) défait un argument \(x\) (noté \(S \rightsquigarrow x\)) si au moins un membre de \(S\) attaque \(x\) : \(\exists a \in S, (a, x) \in R\).
• \(S\) défend un argument \(x\) si \(S\) défait tous les attaquants de \(x\) : \(\forall b\) tel que \((b, x) \in R\), \(S\) défait \(b\).

Autrement dit : \(x\) est défendu par \(S\) si toute attaque contre \(x\) est contrée par une attaque venant de \(S\). C’est le cœur du raisonnement argumentatif — on accepte un argument non parce qu’il est vrai, mais parce qu’on peut le protéger.

def defeats(af, S, x):
    """True si S défait x (au moins un membre de S attaque x)."""
    return any((a, x) in af.attacks for a in S)


def defends(af, S, x):
    """True si S défend x : tout attaquant de x est défait par S."""
    return all(defeats(af, S, b) for b in af.attackers(x))


print("Dans af0, {a} défend-il a ?", defends(af0, {"a"}, "a"))
print("  (a est attaqué par b ; {a} défait-il b ? a->b :", ("a", "b") in af0.attacks, ")")

Dans af0, {a} défend-il a ? True
  (a est attaqué par b ; {a} défait-il b ? a->b : True )

2.3 Admissible

Un ensemble \(S\) est admissible s’il est sans conflit et si chacun de ses membres est défendu par \(S\) :

\[S \text{ admissible} \iff S \text{ sans conflit} \;\land\; \forall a \in S, \; S \text{ défend } a\]

L’admissibilité capture l’idée d’une position auto-cohérente et auto-défendable : aucune contradiction interne, et chaque membre résiste aux attaques extérieures.

def is_admissible(af, S):
    """True si S est admissible : sans conflit et chacun de ses membres est défendu."""
    S = set(S)
    if not is_conflict_free(af, S):
        return False
    return all(defends(af, S, a) for a in S)


for cand in [set(), {"a"}, {"b"}, {"a", "b"}]:
    print(f"{{{' '.join(sorted(cand)) or '∅'}}} admissible ? {is_admissible(af0, cand)}")

{∅} admissible ? True
{a} admissible ? True
{b} admissible ? True
{a b} admissible ? False

3. Les trois sémantiques

L’admissibilité définit un spectre d’ensembles acceptables. Les sémantiques sélectionnent, parmi les ensembles admissibles, ceux qui méritent d’être appelés « extensions » (le verdict final). Dung en définit trois principales, qui encodent des attitudes de raisonnement distinctes :

Sémantique	Attitude	Définition
Grounded	sceptique (le strict minimum certain)	L’unique extension complète minimale ; obtenue par point fixe : on part de \(\emptyset\) et on ajoute itérativement tout argument défendu.
Preferred	crédule (le maximum défendable)	Les extensions complètes maximales (par inclusion) ; il peut y en avoir plusieurs, incompatibles entre elles.
Stable	auto-suffisante (elle statut sur tout)	Une extension admissible qui défait tout argument extérieur : \(\forall x \notin S, S \rightsquigarrow x\).
Semi-stable (§ 4bis)	pragmatique (statuer au maximum)	Les admissibles qui maximisent la portée \(S \cup S^+\) ; existe toujours, et coïncide avec la stable quand celle-ci existe.
Idéale (§ 4bis)	sceptique maximale (verdict unique)	La plus grande admissible contenue dans toutes les preferred ; unique, avec \(\text{grounded} \subseteq \text{idéale} \subseteq \bigcap \text{preferred}\).

Ces trois sémantiques ne sont pas redondantes : elles répondent à la question « quels arguments accepter ? » sous trois régimes de prudence différents. Le théorème central de Dung garantit l’inclusion grounded \(\subseteq\) preferred, mais stable peut ne pas exister, et preferred peut compter plusieurs extensions incompatibles.

Implémentons les trois par énumération (la théorie garantit que pour un AF fini, le nombre d’extensions est fini ; l’énumération des \(2^{|A|}\) sous-ensembles reste tractable pour les petits graphes pédagogiques).

def powerset(args):
    """Tous les sous-ensembles de args, par taille croissante."""
    args = list(args)
    return list(chain.from_iterable(
        combinations(args, r) for r in range(len(args) + 1)
    ))


def grounded(af):
    """Extension grounded : point fixe à partir de l'ensemble vide.

    On ajoute itérativement tout argument défendu par l'ensemble courant, jusqu'à
    ce qu'aucun ajout ne soit plus possible. Le résultat est unique (théorème de Dung).
    """
    S = set()
    changed = True
    while changed:
        changed = False
        for x in af.args:
            if x not in S and defends(af, S, x):
                S.add(x)
                changed = True
    return frozenset(S)


def preferred(af):
    """Extensions preferred : ensembles admissibles maximaux par inclusion."""
    adm = [frozenset(S) for S in powerset(af.args) if is_admissible(af, S)]
    # maximal : aucun autre admissible ne le contient strictement
    return [a for a in adm if not any(a < b for b in adm)]


def stable(af):
    """Extensions stables : admissibles qui défont tout argument hors de l'extension."""
    out = []
    for S in powerset(af.args):
        S = set(S)
        if is_admissible(af, S) and all(
            defeats(af, S, x) for x in af.args if x not in S
        ):
            out.append(frozenset(S))
    return out


def resume(af, label=""):
    """Calcule et affiche les trois sémantiques d'un AF."""
    g = grounded(af)
    p = preferred(af)
    s = stable(af)
    print(f"=== {label or af} ===")
    print(f"  grounded  : {{{', '.join(sorted(g)) or '∅'}}}   (unique, sceptique)")
    print(f"  preferred : {[sorted('{' + ','.join(sorted(e)) + '}') and '{' + ','.join(sorted(e)) + '}' for e in p]}   ({len(p)} ext., crédule)")
    if s:
        print(f"  stable    : {[ '{' + ','.join(sorted(e)) + '}' for e in s]}   ({len(s)} ext.)")
    else:
        print(f"  stable    : AUCUNE (pas d'extension stable)")
    print()
    return g, p, s

4. Le cas canonique : grounded \(\neq\) preferred \(\neq\) stable

Pour que l’écart entre les trois sémantiques soit visible, il faut un AF assez riche pour que les trois attitudes divergent. Considérons :

\[F = \langle \{a, b, c, d\}, \; \{(a,b), (b,a), (c,c)\} \rangle\]

• \(a\) et \(b\) s’attaquent mutuellement : ni l’un ni l’autre n’est attaqué par un tiers, aucun n’est défendu « gratuitement ». Ce sont des arguments flottants — on peut en accepter un (si l’on prend parti) mais pas les deux (ils se contredisent).
• \(c\) s’attaque lui-même : un argument auto-réfuté ne peut jamais appartenir à un ensemble sans conflit (il violerait la cohérence minimale).
• \(d\) est isolé : non attaqué, il sera accepté partout (point de référence stable).

Cet AF est non trivial précisément parce qu’aucune sémantique ne se réduit à une évidence : on ne peut pas « prendre tous les non-attaqués » (ça donnerait \(\{d\}\) en ignorant les flottements) ni « tout ce qui se défend » (ça mélangerait \(a\) et \(b\)).

# AF canonique : flottement a/b + auto-attaque c + isolé d
af1 = AF(
    args={"a", "b", "c", "d"},
    attacks={("a", "b"), ("b", "a"), ("c", "c")},
)
print(af1)
print()
g1, p1, s1 = resume(af1, "F = <{a,b,c,d}, {(a,b),(b,a),(c,c)}>")

AF(args=['a', 'b', 'c', 'd'], attacks=[a->b, b->a, c->c])

=== F = <{a,b,c,d}, {(a,b),(b,a),(c,c)}> ===
  grounded  : {d}   (unique, sceptique)
  preferred : ['{b,d}', '{a,d}']   (2 ext., crédule)
  stable    : AUCUNE (pas d'extension stable)

Lecture du verdict

Les trois sémantiques donnent des résultats différents sur ce graphe :

Sémantique	Résultat	Interprétation
Grounded	\(\{d\}\)	Seul \(d\) est certainement acceptable : il est le seul non attaqué. On refuse de trancher entre \(a\) et \(b\) (aucun n’est défendu sans prendre parti), et \(c\) s’exclut de lui-même. Attitude sceptique : on n’accepte que l’incontestable.
Preferred	\(\{a, d\}\) et \(\{b, d\}\)	Deux positions maximales défendables, incompatibles : soit on accepte \(a\) (qui défait \(b\)), soit \(b\) (qui défait \(a\)). Attitude crédule : on admet chaque position auto-défendable maximale, même s’il en existe une contradictoire.
Stable	(aucune)	Aucune extension stable n’existe. Pourquoi ? Une extension stable devrait défaire tout argument extérieur. Mais \(c\) n’est attaqué par personne d’autre que lui-même : aucun argument ne peut le défaire « de l’extérieur », donc aucune extension stable ne peut le statuer. Le graphe porte un argument « indécidable de l’extérieur » → la sémantique stable échoue à exister.

C’est précisément le théorème de Dung rendu visible : - grounded \(\subset\) preferred (\(\{d\} \subset \{a,d\}\)) ; - preferred \(\ne\) stable (preferred existe, stable n’existe pas) ; - la sémantique stable n’est pas garantie d’existence — c’est sa fragilité théorique, et la raison pour laquelle les solveurs pratiques (Tweety inclus) calculent en priorité grounded et preferred.

# Vérification programmatique : les trois sémantiques divergent bien.
print("grounded == {d} ?", set(g1) == {"d"})
print("preferred == {{a,d},{b,d}} ?",
      set(frozenset(e) for e in p1) == {frozenset({"a", "d"}), frozenset({"b", "d"})})
print("stable existe ?", bool(s1))
print()
print(">>> grounded ⊊ preferred :", set(g1) < set(next(iter(p1))))
print(">>> preferred existe ET stable n'existe pas (divergence) :", bool(p1) and not bool(s1))

grounded == {d} ? True
preferred == {{a,d},{b,d}} ? True
stable existe ? False

>>> grounded ⊊ preferred : True
>>> preferred existe ET stable n'existe pas (divergence) : True

4bis. Quand stable n’existe pas : semi-stable et idéale

Le verdict de la section 4 laisse un problème ouvert : sur af1, la sémantique stable n’existe pas — \(c\), l’auto-attaqué, ne peut être statué par aucune extension. C’est la « fragilité » relevée plus haut, et le curriculum la rencontrera à nouveau : Tweety-5 la constatera sur un cycle impair, où il introduira CF2 — une réponse qui abandonne l’admissibilité. Or la littérature dispose d’une réparation qui reste dans le cadre : deux sémantiques, absentes de ce notebook jusqu’ici.

• Semi-stable (Caminada 2006) : parmi les ensembles admissibles, ceux qui maximisent la portée \(S \cup S^+\) — les arguments acceptés ou attaqués par \(S\). Statuer sur le maximum : c’est la stable « autant que possible ». Trois propriétés la désignent comme la réparation canonique :
  1. elle existe toujours pour un AF fini — le défaut constaté sur af1 est réparé par construction ;
  2. elle coïncide avec la stable dès qu’une extension stable existe — rien n’est perdu ;
  3. elle reste admissible — elle ne quitte pas le cadre construit en section 2.
• Idéale (Dung, Mancarella & Toni 2007) : la plus grande extension admissible contenue dans toutes les extensions preferred. C’est le point manquant de l’axe sceptique/crédule du tableau de la section 3 : un verdict unique — comme la grounded — mais moins timide, puisqu’il inclut tout ce qui est défendable dans chacune des positions crédules. Elle vérifie l’encadrement \(\text{grounded} \subseteq \text{idéale} \subseteq \bigcap \text{preferred}\).

Implémentons les deux par-dessus la machinerie des sections 2-3 (powerset, is_admissible, preferred) — quelques lignes chacune, aucune dépendance nouvelle.

def fmt(E):
    """Affichage compact d'un ensemble d'arguments : {a,d}."""
    return "{" + ",".join(sorted(E)) + "}"


def range_of(af, S):
    """S ∪ S+ : la portée de S — les arguments acceptés par S ou attaqués par S."""
    S = set(S)
    return S | {b for (a, b) in af.attacks if a in S}


def semi_stable(af):
    """Extensions semi-stables : les admissibles qui maximisent |S ∪ S+| (Caminada 2006)."""
    adm = [frozenset(S) for S in powerset(af.args) if is_admissible(af, S)]
    best = max(len(range_of(af, S)) for S in adm)
    return [S for S in adm if len(range_of(af, S)) == best]


# Retour sur l'AF canonique af1 — là où la sémantique stable n'existe pas.
ss1 = semi_stable(af1)
print("=== af1 : le défaut et sa réparation ===")
print("  stable      : " + ("AUCUNE" if not s1 else str([fmt(e) for e in s1])))
print("  semi-stable : %s   (%d ext.)" % ([fmt(e) for e in ss1], len(ss1)))
print()
print("semi-stable existe là où stable n'existe pas :", bool(ss1) and not bool(s1))
print("sur af1, semi-stable == preferred            :", set(ss1) == set(p1))

=== af1 : le défaut et sa réparation ===
  stable      : AUCUNE
  semi-stable : ['{b,d}', '{a,d}']   (2 ext.)

semi-stable existe là où stable n'existe pas : True
sur af1, semi-stable == preferred            : True

# Propriété 2 : quand la stable existe, la semi-stable coïncide avec elle.
# af3 : un AF acyclique (DAG d'attaque) — la stable y existe toujours.
af3 = AF(args={"a", "b", "c"}, attacks={("a", "b")})
s3, ss3 = stable(af3), semi_stable(af3)
p3 = preferred(af3)
print("=== af3 = AF(args={a,b,c}, attacks={a->b}) — la stable existe ===")
print("  stable      : %s" % [fmt(e) for e in s3])
print("  semi-stable : %s" % [fmt(e) for e in ss3])
print("  preferred   : %s" % [fmt(e) for e in p3])
print()
print("coïncidence semi-stable == stable (setwise) :", set(ss3) == set(s3))

=== af3 = AF(args={a,b,c}, attacks={a->b}) — la stable existe ===
  stable      : ['{a,c}']
  semi-stable : ['{a,c}']
  preferred   : ['{a,c}']

coïncidence semi-stable == stable (setwise) : True

Lecture du verdict : la réparation en action

Là où la stable affichait « AUCUNE », la semi-stable rend \(\{a,d\}\) et \(\{b,d\}\) — exactement les preferred de af1. Ce n’est pas un hasard : une extension qui statue sur un maximum d’arguments est nécessairement crédule-maximale. La différence entre les deux notions se joue sur \(c\) : personne ne l’attaque « de l’extérieur » (il ne s’attaque que lui-même, et cela ne compte pas pour la portée d’une autre extension), donc aucune portée ne couvre \(c\) — la semi-stable ne décide pas \(c\), elle décide tout le reste et laisse \(c\) explicitement indécidable. C’est le compromis exact : maximiser les arguments statués sans jamais sacrifier l’admissibilité — là où CF2 (Tweety-5) paiera l’existence en quittant le cadre admissible.

(On montre — c’est l’esprit de l’Exercice 1 — que ces ensembles de portée maximale sont automatiquement complets.)

La sémantique idéale : un verdict unique sur l’axe sceptique

La preferred est crédule : elle rend plusieurs verdicts incompatibles. La grounded est sceptique : elle n’ose que l’incontestable — parfois \(\emptyset\), comme sur les témoins ci-dessous. Entre les deux, la sémantique idéale répond à la question que pose le pipeline agentique de la série : quelle position unique peut tenir un système qui doit trancher sans prendre parti entre les extensions preferred ? La réponse : tout ce qui est défendable dans chacune des positions crédules — l’admissible maximale contenue dans toutes les preferred. Elle existe toujours, est unique, et l’encadrement \(\text{grounded} \subseteq \text{idéale} \subseteq \bigcap\text{preferred}\) se vérifie programmatiquement — sur deux témoins où l’écart est visible de part et d’autre.

def ideal(af):
    """L'extension idéale : la plus grande admissible contenue dans TOUTES les preferred.

    (Dung, Mancarella & Toni 2007.) Toujours existante et unique : l'union d'admissibles
    deux à deux compatibles est admissible, donc le plus grand candidat est l'unique maximal.
    """
    prefs = preferred(af)
    inter = set.intersection(*[set(e) for e in prefs])
    cands = [frozenset(S) for S in powerset(inter) if is_admissible(af, S)]
    return max(cands, key=len)


# Témoin 1 : a et b flottent ; x et y se défendent mutuellement contre eux.
af_id1 = AF(
    args={"a", "b", "x", "y"},
    attacks={("a", "b"), ("b", "a"), ("a", "x"), ("y", "a"), ("b", "y"), ("x", "b")},
)
# Témoin 2 : a et b flottent ; w (auto-attaqué) menace z, que seuls a et b savent défaire.
af_id2 = AF(
    args={"a", "b", "w", "z"},
    attacks={("a", "b"), ("b", "a"), ("w", "w"), ("w", "z"), ("a", "w"), ("b", "w")},
)

for name, afi in [("af_id1", af_id1), ("af_id2", af_id2)]:
    g, i = grounded(afi), ideal(afi)
    inter = set.intersection(*[set(e) for e in preferred(afi)])
    print("=== %s ===" % name)
    print("  preferred   : %s" % [fmt(e) for e in preferred(afi)])
    print("  grounded    : %s" % fmt(g))
    print("  idéale      : %s" % fmt(i))
    print("  ∩ preferred : %s" % fmt(inter))
    print("  encadrement g ⊆ i ⊆ ∩pref :", set(g) <= set(i) <= inter)
    print("  les trois ne coïncident pas :", not (set(g) == set(i) == inter))
    print()

=== af_id1 ===
  preferred   : ['{x,y}']
  grounded    : {}
  idéale      : {x,y}
  ∩ preferred : {x,y}
  encadrement g ⊆ i ⊆ ∩pref : True
  les trois ne coïncident pas : True

=== af_id2 ===
  preferred   : ['{b,z}', '{a,z}']
  grounded    : {}
  idéale      : {}
  ∩ preferred : {z}
  encadrement g ⊆ i ⊆ ∩pref : True
  les trois ne coïncident pas : True

Lecture des deux témoins : le sandwich rendu visible

Sur af_id1, \(x\) et \(y\) se défendent mutuellement (\(y\) défait l’attaquant de \(x\), \(x\) défait celui de \(y\)) : aucun n’est défendu à partir de \(\emptyset\), donc la grounded reste vide — mais ensemble ils sont admissibles, et présents dans l’unique extension preferred. L’idéale accepte alors \(\{x,y\}\) là où la grounded ne disait rien : moins timide, pour le même prix — un verdict unique.

Sur af_id2, l’argument \(z\) est présent dans chaque preferred — que l’on choisisse \(a\) ou \(b\) comme parti pris, l’un des deux défait \(w\), l’agresseur de \(z\). Donc \(z \in \bigcap\text{preferred}\). Mais cette intersection n’est pas admissible : \(z\) n’y est défendu par personne (\(w\) n’est défait que par \(a\) ou par \(b\), jamais ensemble dans une même extension). L’idéale retombe alors sur \(\emptyset\) : elle ne promet que ce qui est défendable sans choisir de camp.

Les deux témoins ensemble situent exactement la sémantique : strictement au-dessus de la grounded dès qu’existe une défense mutuelle universelle, strictement sous l’intersection dès qu’un argument commun n’est défendu que par des partis pris. Construire un AF où les trois diffèrent deux à deux est l’objet de l’Exercice 4.

5. Retour au solveur Tweety

Maintenant que les sémantiques sont transparentes, relisons l’appel du notebook 2-formal §6 :

reasoner_d = SimpleGroundedReasoner()
models = reasoner_d.getModels(theory)   # Collection<Extension>

getModels renvoie la collection des extensions selon la sémantique du reasoner. Pour SimpleGroundedReasoner, c’est exactement le point fixe calculé par notre fonction grounded ci-dessus — une seule extension, la plus prudente. Les reasoners SimplePreferredReasoner et SimpleCompleteReasoner implémentent les autres colonnes du tableau. Le pont JPype ne fait rien d’autre qu’appeler, en JVM, l’algorithme que nous venons de reconstruire à la main.

Ce que ce notebook apporte au-delà de Tweety-5 : la compréhension de l’algorithme, pas seulement son usage. C’est la différence entre invoquer un vérificateur formel (le pipeline agentique de la série) et comprendre ce qu’il calcule (ce notebook).

Pour les preuves formelles des théorèmes d’inclusion et d’existence (grounded est l’extension complète minimale, stable peut être vide), voir le notebook Lean Tweety-5b.

6. Exercices

Les quatre exercices suivants approfondissent la théorie. Ils sont laissés incomplets par construction (stub) : à vous de les remplir. Le notebook s’exécute de bout en bout même non complété — vos implémentations remplaceront les pass / return None.

Exercice 1 — Complétude vs admissibilité

Une extension complète est admissible et contient tout argument qu’elle défend : \(S\) complète \(\iff\) \(S\) admissible et \(\forall x \in A\), si \(S\) défend \(x\) alors \(x \in S\). La grounded est l’unique complète minimale, les preferred sont les complètes maximales.

Objectif : implémenter is_complete(af, S) et vérifier que la grounded et les preferred de af1 sont bien complètes (mais qu’un admissible non-maximal comme \(\{a\}\) ne l’est pas — pourquoi ?).

Indice : un argument défendu mais absent de \(S\) suffit à le disqualifier.

# Exercice 1 : compléter cette fonction
def is_complete(af, S):
    """True si S est complet : admissible ET contient tout argument qu'il défend."""
    # Etape 1 : vérifier l'admissibilité (déjà disponible : is_admissible).
    # Etape 2 : pour tout x défendu par S, x doit appartenir à S.
    # TODO etudiant
    return None


# Test (à décommenter une fois complété) :
# print("grounded complet ?", is_complete(af1, set(g1)))
# print("preferred complet ?", all(is_complete(af1, set(e)) for e in p1))
# print("{a} (admissible non-maximal) complet ?", is_complete(af1, {"a"}))

Exercice 2 — Un AF où la sémantique stable existe

Sur af1, la sémantique stable n’existait pas (à cause de l’auto-attaque de \(c\)). Construisez un AF sans auto-attaque ni cycle impair où la stable existe et coïncide avec la preferred.

Objectif : définir af2 et vérifier que stable(af2) == preferred(af2) (même collection d’extensions).

Indice : un AF acyclique (les arguments forment un DAG d’attaque) admet toujours une unique extension stable, qui coïncide avec la grounded et la preferred.

# Exercice 2 : définir un AF où stable == preferred
af2 = AF(
    args=set(),       # TODO etudiant : choisir args
    attacks=set(),    # TODO etudiant : choisir attacks (sans auto-attaque)
)
# Test (à décommenter une fois complété) :
# g2, p2, s2 = resume(af2, "af2 (votre AF)")
# print("stable == preferred ?",
#       set(s2) == set(p2))

Exercice 3 — Étiquetage IN / OUT / UNDEC

Les sémantiques admettent une formulation équivalente en étiquetages : chaque argument reçoit l’étiquette IN (accepté), OUT (rejeté) ou UNDEC (indécidable), avec les règles : (i) \(x\) est OUT si un IN l’attaque ; (ii) \(x\) est IN si tous ses attaquants sont OUT. Le labeling grounded de af1 devrait donner \(d\)=IN, \(c\)=UNDEC (auto-attaqué, mais rejeté par aucun IN), et \(a, b\)=UNDEC (le flottement non tranché).

Objectif : implémenter grounded_labeling(af) renvoyant un dict {arg: "IN"/"OUT"/"UNDEC"}, et vérifier qu’il est cohérent avec grounded(af) (IN \(=\) l’extension grounded, du moins quand aucun argument n’est UNDEC dans la grounded).

Indice : OUT = attaqué par un IN ; IN = non attaqué, ou tous ses attaquants OUT ; UNDEC = ni IN ni OUT (le reste). Itérez jusqu’à stabilisation, comme pour le point fixe.

# Exercice 3 : compléter le labeling grounded
def grounded_labeling(af):
    """Renvoie {arg: 'IN'|'OUT'|'UNDEC'} selon le labeling grounded."""
    labels = {a: "UNDEC" for a in af.args}
    # Etape 1 : IN = argument dont tous les attaquants sont OUT (ou sans attaquant).
    # Etape 2 : OUT = argument attaqué par au moins un IN.
    # Etape 3 : itérer jusqu'au point fixe (comme grounded).
    # TODO etudiant
    return labels


# Test (à décommenter une fois complété) :
# lab = grounded_labeling(af1)
# print("Labeling grounded de af1 :", lab)
# print("Cohérent avec grounded={d} ?", set(a for a, l in lab.items() if l == "IN") == set(g1))

Exercice 4 — L’axe sceptique complet : grounded, idéale, \(\bigcap\)preferred

Le § 4bis a montré deux témoins : sur af_id1, l’idéale dépasse la grounded (\(\emptyset \subsetneq \{x,y\}\)) mais égale l’intersection ; sur af_id2, elle égale la grounded (\(\emptyset\)) mais reste sous l’intersection (\(\{z\}\)). Dans chacun, deux des trois coïncident.

Objectif : construire un AF où les trois ensembles diffèrent deux à deux — \(\text{grounded} \subsetneq \text{idéale} \subsetneq \bigcap\text{preferred}\), strictement.

Indices : - Indice 1 : pour dépasser la grounded, il faut de la défense mutuelle — des arguments défendus seulement par d’autres arguments eux-mêmes non défendus à partir de \(\emptyset\), mais présents dans toutes les preferred. - Indice 2 : pour rester sous l’intersection, il faut un argument commun à toutes les preferred mais défendu uniquement par des arguments qui changent selon l’extension. - Etape 1 : écrire af4 (les deux mécanismes des témoins peuvent coexister dans un même AF) ; Etape 2 : décommenter le test ; Etape 3 : vérifier que les trois ensembles forment bien une chaîne strictement croissante.

# Exercice 4 : construire un AF où grounded, idéale et ∩preferred diffèrent DEUX À DEUX
af4 = AF(
    args=set(),       # TODO etudiant : choisir args
    attacks=set(),    # TODO etudiant : choisir attacks
)
# Test (à décommenter une fois complété) :
# g4, i4 = grounded(af4), ideal(af4)
# inter4 = set.intersection(*[set(e) for e in preferred(af4)])
# print("grounded :", fmt(g4), "| idéale :", fmt(i4), "| ∩preferred :", fmt(inter4))
# print("différences deux à deux :",
#       len({frozenset(g4), frozenset(i4), frozenset(inter4)}) == 3)
print("Exercice a completer : axe sceptique grounded / idéale / ∩preferred")

Exercice a completer : axe sceptique grounded / idéale / ∩preferred

Aller plus loin — la trajectoire d’étiquetage

Tout ce qui précède calcule un étiquetage sur un AF déjà complet : tous les arguments sont posés, toutes les attaques sont connues, on cherche le point fixe. Mais un débat réel n’arrive pas d’un bloc — les arguments sont énoncés l’un après l’autre, et un argument ne peut pas être attaqué par un argument pas encore prononcé.

Étiquetons donc après chaque arrivée, et regardons la suite d’étiquetages plutôt que le seul étiquetage final. Deux propriétés s’opposent :

• l’étiquetage final ne dépend pas de l’ordre d’arrivée — Dung est order-blind ;
• la trajectoire, elle, en dépend.

La trajectoire porte donc exactement l’information que l’étiquetage statique jette : quand un argument a basculé, et sous l’effet de quelle arrivée. C’est aussi le lieu où se voit la non-monotonie — un argument accepté peut redevenir indécidable quand son attaquant arrive.

# Raccourci assumé : on lit les étiquettes depuis `grounded()`, déjà fourni plus haut.
# ⚠ Ce n'est PAS la solution de l'Exercice 3, qui demande la formulation par point fixe
# (itération IN/OUT jusqu'à stabilisation) — celle-là reste à écrire.
def labelling_depuis_grounded(af):
    """{arg: 'IN'|'OUT'|'UNDEC'} dérivé de l'extension grounded de `af`."""
    ext = grounded(af)
    labels = {}
    for x in af.args:
        if x in ext:
            labels[x] = "IN"
        elif any((a, x) in af.attacks for a in ext):
            labels[x] = "OUT"
        else:
            labels[x] = "UNDEC"
    return labels


def trajectoire(af, ordre_arrivee):
    """Étiquetage après chaque arrivée, sous un ordre de délivrance donné.

    Une attaque ne devient ACTIVE que lorsque ses deux extrémités sont arrivées.
    """
    if set(ordre_arrivee) != af.args:
        raise ValueError("ordre_arrivee doit énumérer exactement af.args")
    etapes = []
    for k in range(1, len(ordre_arrivee) + 1):
        arrives = set(ordre_arrivee[:k])
        actives = {(a, b) for (a, b) in af.attacks if a in arrives and b in arrives}
        etapes.append(labelling_depuis_grounded(AF(arrives, actives)))
    return etapes


def montre(af, ordre):
    print(f"Ordre d'arrivée : {' -> '.join(ordre)}")
    etapes = trajectoire(af, ordre)
    for k, lab in enumerate(etapes, start=1):
        vue = "   ".join(f"{a}={lab[a]}" for a in ordre[:k])
        print(f"  étape {k} : {vue}")
    return etapes[-1]


fin_1 = montre(af1, ["d", "c", "a", "b"])
print()
fin_2 = montre(af1, ["a", "b", "c", "d"])
print()
print("Étiquetage FINAL identique ?", fin_1 == fin_2)
print("Trajectoires identiques    ?",
      trajectoire(af1, ["d", "c", "a", "b"]) == trajectoire(af1, ["a", "b", "c", "d"]))

Ordre d'arrivée : d -> c -> a -> b
  étape 1 : d=IN
  étape 2 : d=IN   c=UNDEC
  étape 3 : d=IN   c=UNDEC   a=IN
  étape 4 : d=IN   c=UNDEC   a=UNDEC   b=UNDEC

Ordre d'arrivée : a -> b -> c -> d
  étape 1 : a=IN
  étape 2 : a=UNDEC   b=UNDEC
  étape 3 : a=UNDEC   b=UNDEC   c=UNDEC
  étape 4 : a=UNDEC   b=UNDEC   c=UNDEC   d=IN

Étiquetage FINAL identique ? True
Trajectoires identiques    ? False

Ce que la trajectoire montre

Les deux ordres convergent vers le même étiquetage final — \(d\)=IN, \(c\)=UNDEC, \(a\) et \(b\)=UNDEC — mais par des chemins différents. Dans l’ordre \(a \to b \to c \to d\), l’argument \(a\) est IN tant qu’il est seul, puis bascule en UNDEC dès que son attaquant \(b\) arrive : l’acceptation est révisée, pas raffinée. C’est la non-monotonie, rendue visible par le seul fait d’avoir regardé la suite plutôt que sa limite.

Deux remarques pour la suite :

• \(c\) est UNDEC, pas OUT. L’argument auto-attaqué n’est rejeté par personne — il s’exclut lui-même sans qu’un IN ne l’attaque. La règle « OUT \(=\) attaqué par un IN » ne s’applique donc pas à lui, et c’est bien ce que l’énoncé de l’Exercice 3 anticipe.
• L’ordre est un paramètre, pas un détail. Si la trajectoire dépend de l’ordre d’arrivée, alors comparer deux protocoles de débat revient à comparer deux trajectoires sur le même AF — ce que l’étiquetage final, à lui seul, ne permet pas.

Lien avec le substrat 2025-EPITA-IS

Cette construction existe sous forme outillée dans le dépôt 2025-Epita-Intelligence-Symbolique, en abs_arg_dung/aif_adapter.py : aif_labelling_trajectory construit la même suite d’étiquetages à partir d’un flux d’arguments et d’attaques AIF (undercut / undermine / rebut), avec aif_label_transitions pour extraire les basculements et render_aif_trajectory pour l’affichage. Chaque étape y est vérifiée contre les backends Dung (natif et TweetyProject) qui se servent mutuellement d’oracle.

Le vocabulaire de sortie est le même à la casse près (in / out / undec), de sorte que les étiquetages produits ici et là-bas se comparent directement. La cellule ci-dessus reste volontairement autonome — Python standard, aucune dépendance — pour que le notebook s’exécute sans installer quoi que ce soit.

Une conséquence de cette autonomie mérite d’être dite, pour que le motif de démo ne soit pas pris pour l’algorithme de production : trajectoire recalcule grounded de zéro à chaque arrivée, et grounded énumère les parties de l’ensemble d’arguments — le coût est donc exponentiel à chaque étape. C’est sans conséquence sur les quatre arguments canoniques, et rédhibitoire sur un flux réel. Le substrat 2025-EPITA-IS procède par propagation incrémentale des étiquettes : il met à jour l’étiquetage à partir du précédent au lieu de le recalculer, ce qui est précisément ce que la structure de trajectoire rend possible.

Conclusion

Ce notebook a reconstruit, de zéro et en Python standard, les trois sémantiques fondatrices de l’argumentation abstraite de Dung :

• Grounded — l’unique extension complète minimale, attitude sceptique.
• Preferred — les extensions complètes maximales, attitude crédule (potentiellement multiples et incompatibles).
• Stable — les extensions admissibles qui statuent sur tout argument extérieur ; non garantie d’existence.

Le cas canonique \(\langle \{a,b,c,d\}, \{(a,b),(b,a),(c,c)\} \rangle\) a montré les trois verdicts diverger simultanément : grounded \(= \{d\}\), preferred \(= \{\{a,d\}, \{b,d\}\}\), stable inexistante. C’est la richesse structurelle qui justifie l’existence de trois sémantiques plutôt qu’une seule : aucune ne capte à elle seule toutes les nuances de l’acceptabilité argumentative.

Le § 4bis complète ce tableau : la semi-stable (Caminada 2006) répare le défaut constaté — elle existe toujours et coïncide avec la stable quand celle-ci existe — et l’idéale (Dung, Mancarella & Toni 2007) fournit le verdict unique sceptique \(\text{grounded} \subseteq \text{idéale} \subseteq \bigcap\text{preferred}\), celui qu’exige un pipeline qui doit trancher.

Prochaines étapes

• Utiliser le solveur : Tweety-5 applique ces sémantiques via TweetyProject (JVM) sur des AF plus grands, où l’énumération exhaustive devient prohibitif. Le notebook 2-formal §6 en fait usage dans le pipeline agentique.
• Prouver les théorèmes : Tweety-5b-Lean formalise en Lean les inclusions (\(\text{grounded} \subseteq \text{preferred}\)) et les conditions d’existence de la sémantique stable.
• Argumentation structurée : le formalisme abstrait de Dung ignore le contenu des arguments. ASPIC+, ABA et DeLP (accessibles via Tweety) reconstruisent la relation d’attaque à partir d’une logique sous-jacente — la série Tweety les explore.