Résumé Technique : Diversité des Extensions en Argumentation Abstraite

Définition du Problème

L'argumentation abstraite modélise le raisonnement via des Cadres d'Argumentation (AF), représentés comme des graphes orientés où les nœuds sont des arguments et les arêtes représentent des attaques. La sémantique d'un AF définit des « extensions » — des ensembles d'arguments satisfaisant des conditions de cohérence spécifiques (par exemple, absence de conflit, admissibilité, stabilité). Bien que les tâches de raisonnement standard déterminent l'existence d'extensions ou le statut d'acceptation d'arguments individuels (croyance ou scepticisme), elles échouent souvent à quantifier la distance structurelle entre ces extensions. Dans des scénarios impliquant la négociation ou la prise de décision, comprendre si des points de vue alternatifs (extensions) sont marginalement différents ou fondamentalement incompatibles est crucial. Les concepts existants, tels que la sélection de points de vue représentatifs ou le comptage des extensions, ne mesurent pas explicitement la « diversité » ou la dissimilarité entre des extensions entières.

Ce papier comble cette lacune en introduisant une notion quantitative de diversité des extensions basée sur la différence symétrique ($A \triangle B = (A \cup B) \setminus (A \cap B)$). Le problème central consiste à déterminer si un AF admet deux extensions différant exactement par $k$ arguments, par au moins $k$ arguments, ou par au plus $k$ arguments, et à calculer la diversité maximale possible ($k_{max}$) pour un cadre donné.

Méthodologie

Les auteurs abordent le problème à travers trois piliers principaux : définition formelle, analyse de la complexité computationnelle et évaluation expérimentale.

1. Définitions Formelles

La diversité entre deux extensions $S$ et $T$ est définie comme $d(S, T) = |S \triangle T|$. Le papier définit plusieurs problèmes de décision et d'optimisation :

• $k$-Div-Arg$_\sigma$ : Étant donnés des arguments $a, b$, existe-t-il deux $\sigma$-extensions $S, T$ telles que $a \in S$, $b \in T$, et $d(S, T) = k$ ?
• $k$-Div-Ext$_\sigma$ : L'AF admet-il deux $\sigma$-extensions avec une distance $k$ ?
• Variantes : Des problèmes sont également définis pour une diversité $\ge k$ et $\le k$, ainsi que des problèmes d'optimisation visant à trouver le $k$ maximal ($max$-$k$-Div).

2. Analyse de Complexité

Le papier fournit une classification systématique de la complexité computationnelle de ces problèmes pour diverses sémantiques :

• Sémantiques sans conflit et Naïve : Les problèmes sont généralement NP-complets. Notamment, alors que le raisonnement standard (par exemple, l'existence d'extension) est polynomial pour les sémantiques sans conflit, la détermination de la diversité est NP-difficile.
• Sémantiques Admissible, Complète et Stable : La complexité s'aligne sur l'acceptation croyante, restant NP-complète.
• Sémantiques Semi-stable, Étape et Préférée : Ces sémantiques de niveau supérieur augmentent la complexité à $\Sigma_2^P$-complet pour les problèmes de décision impliquant des arguments et des extensions spécifiques.
• Diversité Maximale : Déterminer le seuil exact de diversité maximale s'avère DP-complet pour les sémantiques de niveau inférieur et DP$_2$-complet pour les sémantiques semi-stable et étape. Cela implique de vérifier à la fois l'existence d'une solution avec une diversité $k$ et la non-existence de solutions avec une diversité $> k$.

Les auteurs utilisent des réductions à partir de problèmes de complexité standards (3SAT, Ensemble Dominant, SAT-UNSAT et Formules Booléennes Quantifiées) pour établir ces résultats de dureté.

3. Évaluation Expérimentale

Une implémentation prototype a été développée utilisant la Programmation par Réponse d'Ensemble (ASP) et le solveur ASPARTIX. Le système calcule les valeurs de diversité minimale et maximale pour des AF. Des expériences ont été menées sur 270 instances de la suite de référence ICCMA 2025 (restreinte aux cadres avec $\le 1000$ arguments) sous les sémantiques admissible, complète et stable.

Contributions Clés

1. Introduction de la Diversité par Différence Symétrique : Le papier formalise une nouvelle métrique pour l'argumentation abstraite qui quantifie le désaccord entre des points de vue alternatifs (extensions) plutôt que simplement leur existence.
2. Paysage de Complexité Complet : Les auteurs fournissent une classification approfondie de la complexité du raisonnement sur la diversité. Ils démontrent que pour certaines sémantiques (sans conflit, naïve), le raisonnement sur la diversité est strictement plus difficile que le raisonnement d'acceptation standard, tandis que pour d'autres, il correspond à la complexité de l'acceptation croyante.
3. Prototype et Évaluation : Le papier présente une implémentation fonctionnelle et des résultats empiriques initiaux, montrant que le calcul des niveaux de diversité est réalisable pour des cadres de taille moyenne, bien que le temps d'exécution varie considérablement en fonction de la sémantique et de l'objectif de diversité spécifique (min vs max).

Résultats

• Complexité : L'étude révèle que le raisonnement sur la diversité n'est pas uniformément facile. Pour les sémantiques sans conflit, il est NP-complet, contrastant avec la résolubilité en temps polynomial de l'existence standard d'extension. Pour les sémantiques semi-stable et étape, le problème saute au deuxième niveau de la hiérarchie polynomiale ($\Sigma_2^P$).
• Résultats Expérimentaux : Les expériences indiquent que les valeurs de diversité varient considérablement d'une instance à l'autre. Alors que de nombreux cadres ont des extensions structurellement proches (faible diversité), un sous-ensemble admet des extensions fondamentalement différentes (forte diversité). Les temps d'exécution moyens pour calculer la diversité maximale étaient généralement inférieurs à 2 secondes pour les instances testées, suggérant une faisabilité pratique pour des problèmes de taille moyenne.
• Non-Monotonie : Les auteurs notent que la diversité n'est ni monotone ni anti-monotone, ce qui signifie que l'ajout d'arguments à un cadre n'augmente ni ne diminue de manière prévisible la diversité maximale.

Signification et Revendications

Le papier revendique que sa contribution principale est de rendre explicite à quel point des points de vue alternatifs et internes cohérents dans un AF divergent. En allant au-delà de la simple acceptation ou du comptage, cette mesure quantitative permet une analyse plus fine des situations argumentatives.

Les auteurs positionnent ce travail comme un outil pour :

• Négociation et Prise de Décision : Identifier si les désaccords sont superficiels (faible diversité) ou fondamentaux (forte diversité).
• Analyse de Robustesse : Une forte diversité implique une faible robustesse des conclusions, car le cadre soutient des positions radicalement différentes.
• Directions Futures : Les auteurs suggèrent modestement que cette notion pourrait être étendue à l'argumentation basée sur la logique et appliquée à la réponse de requêtes cohérentes dans les bases de connaissances, mais ils ne revendiquent pas que ces applications sont actuellement réalisées. Ils identifient également des cas de complexité ouverts (par exemple, diversité minimale) et le potentiel d'approches de complexité paramétrée comme travail futur.

Le papier conclut que, bien que le coût computationnel puisse être élevé pour certaines sémantiques, la capacité à quantifier la « distance » entre les points de vue offre une nouvelle dimension précieuse pour l'analyse des cadres d'argumentation abstraite.