Technische Samenvatting: Diversiteit van Extensies in Abstracte Argumentatie

Probleemdefinitie

Abstracte argumentatie modelleert redenering via Argumentatiekaders (AF's), weergegeven als gerichte grafen waarbij knopen argumenten zijn en randen aanvallen voorstellen. De semantiek van een AF definiëren "extensies"—verzamelingen van argumenten die aan specifieke coherentievoorwaarden voldoen (bijvoorbeeld conflictvrijheid, toelaatbaarheid, stabiliteit). Hoewel standaardredeneertaken de existentie van extensies of de acceptatiestatus van individuele argumenten (kredibel of sceptisch) bepalen, slagen ze er vaak niet in om de structurele afstand tussen deze extensies te kwantificeren. In scenario's die betrekking hebben op onderhandeling of besluitvorming is het cruciaal om te begrijpen of alternatieve standpunten (extensies) marginaal verschillend zijn of fundamenteel incompatibel. Bestaande concepten, zoals het selecteren van representatieve standpunten of het tellen van extensies, meten niet expliciet de "diversiteit" of ongelijkheid tussen volledige extensies.

Dit artikel vult deze leemte door een kwantitatieve notie van diversiteit van extensies in te voeren, gebaseerd op de symmetrische verschil ($A \triangle B = (A \cup B) \setminus (A \cap B)$). Het kernprobleem is om te bepalen of een AF twee extensies toestaat die precies $k$ argumenten verschillen, ten minste $k$ argumenten, of ten hoogste $k$ argumenten, en om de maximaal mogelijke diversiteit ($k_{max}$) voor een gegeven kader te berekenen.

Methodologie

De auteurs benaderen het probleem via drie hoofdpijlers: formele definitie, analyse van de computationele complexiteit en experimentele evaluatie.

1. Formele Definities

De diversiteit tussen twee extensies $S$ en $T$ wordt gedefinieerd als $d(S, T) = |S \triangle T|$. Het artikel definieert verschillende beslissings- en optimalisatieproblemen:

• $k$-Div-Arg$_\sigma$: Gegeven argumenten $a, b$, bestaan er twee $\sigma$-extensies $S, T$ zodat $a \in S, b \in T$, en $d(S, T) = k$?
• $k$-Div-Ext$_\sigma$: Staart de AF twee $\sigma$-extensies toe met afstand $k$?
• Varianten: Problemen worden ook gedefinieerd voor diversiteit $\ge k$ en $\le k$, evenals optimalisatieproblemen om de maximale $k$ te vinden ($max$-$k$-Div).

2. Complexiteitsanalyse

Het artikel biedt een systematische classificatie van de computationele complexiteit voor deze problemen over diverse semantiek:

• Conflictvrije en Naïeve Semantiek: De problemen zijn over het algemeen NP-compleet. Opmerkelijk is dat, hoewel standaardredenering (bijvoorbeeld extensie-existentie) polynomiaal is voor conflictvrije semantiek, het bepalen van diversiteit NP-moeilijk is.
• Toelaatbare, Volledige en Stabiele Semantiek: De complexiteit komt overeen met kredibel acceptatie en blijft NP-compleet.
• Semi-stabiele, Stage- en Preferente Semantiek: Deze hogere semantiek verhogen de complexiteit tot $\Sigma_2^P$-compleet voor beslissingsproblemen die specifieke argumenten en extensies betrekken.
• Maximale Diversiteit: Het bepalen van de exacte maximale diversiteitsdrempel blijkt DP-compleet te zijn voor lagere semantiek en DP$_2$-compleet voor semi-stabiele en stage-semantiek. Dit houdt in dat zowel de existentie van een oplossing met diversiteit $k$ als het niet-bestaan van oplossingen met diversiteit $> k$ wordt gecontroleerd.

De auteurs maken gebruik van reducties vanuit standaard complexiteitsproblemen (3SAT, Dominating Set, SAT-UNSAT en Gequantificeerde Boolese Formules) om deze hardheidsresultaten vast te stellen.

3. Experimentele Evaluatie

Een prototype-implementatie is ontwikkeld met behulp van Answer Set Programming (ASP) en de solver ASPARTIX. Het systeem berekent minimale en maximale diversiteitswaarden voor AF's. Experimenten zijn uitgevoerd op 270 instanties uit de ICCMA 2025 benchmark-suite (beperkt tot kaders met $\le 1000$ argumenten) onder toelaatbare, volledige en stabiele semantiek.

Belangrijkste Bijdragen

1. Introductie van Symmetrisch-Verschil-Diversiteit: Het artikel formaliseert een nieuwe metriek voor abstracte argumentatie die de meningsverschillen tussen alternatieve standpunten (extensies) kwantificeert, in plaats van alleen hun existentie.
2. Uitgebreid Complexiteitslandschap: De auteurs bieden een grondige classificatie van de complexiteit van redeneren over diversiteit. Zij tonen aan dat voor bepaalde semantiek (conflictvrij, naïef) redeneren over diversiteit strikt moeilijker is dan standaard acceptatieredenering, terwijl het voor andere semantiek overeenkomt met de complexiteit van kredibel acceptatie.
3. Prototype en Evaluatie: Het artikel presenteert een werkende implementatie en eerste empirische resultaten, waaruit blijkt dat het berekenen van diversiteitsniveaus haalbaar is voor kaders van gemiddelde grootte, hoewel de runtime aanzienlijk varieert afhankelijk van de semantiek en het specifieke diversiteitsdoel (min versus max).

Resultaten

• Complexiteit: De studie onthult dat redeneren over diversiteit niet uniform eenvoudig is. Voor conflictvrije semantiek is het NP-compleet, in contrast met de oplosbaarheid in polynomiale tijd van standaard extensie-existentie. Voor semi-stabiele en stage-semantiek springt het probleem naar het tweede niveau van de polynomiale hiërarchie ($\Sigma_2^P$).
• Experimentele Bevindingen: De experimenten geven aan dat diversiteitswaarden aanzienlijk variëren tussen instanties. Hoewel veel kaders extensies hebben die structureel dicht bij elkaar liggen (lage diversiteit), staat een subset extensies toe die fundamenteel verschillend zijn (hoge diversiteit). De gemiddelde looptijden voor het berekenen van maximale diversiteit lagen over het algemeen onder de 2 seconden voor de geteste instanties, wat wijst op praktische haalbaarheid voor problemen van middelgrote schaal.
• Niet-monotonie: De auteurs merken op dat diversiteit noch monotoon noch anti-monotoon is, wat betekent dat het toevoegen van argumenten aan een kader de maximale diversiteit niet voorspelbaar doet toenemen of afnemen.

Betekenis en Claims

Het artikel claimt dat de primaire bijdrage is het expliciet maken van hoe sterk alternatieve, intern coherente standpunten in een AF uiteenlopen. Door verder te gaan dan eenvoudige acceptatie of telling, maakt deze kwantitatieve maatstaf een fijnmazigere analyse van argumentatieve situaties mogelijk.

De auteurs positioneren dit werk als een hulpmiddel voor:

• Onderhandeling en Besluitvorming: Het identificeren of meningsverschillen oppervlakkig zijn (lage diversiteit) of fundamenteel (hoge diversiteit).
• Robuustheidsanalyse: Hoge diversiteit impliceert lage robuustheid van conclusies, aangezien het kader radicaal verschillende posities ondersteunt.
• Toekomstige Richtingen: De auteurs suggereren bescheiden dat deze notie kan worden uitgebreid naar op logica gebaseerde argumentatie en kan worden toegepast op consistent query-antwoorden in kennisbanken, maar zij claimen niet dat deze toepassingen momenteel zijn verwezenlijkt. Zij identificeren ook open complexiteitsgevallen (bijvoorbeeld minimale diversiteit) en de potentieel voor geparametriseerde complexiteitsbenaderingen als toekomstig werk.

Het artikel concludeert dat, hoewel de computationele kosten voor bepaalde semantiek hoog kunnen zijn, het vermogen om de "afstand" tussen standpunten te kwantificeren een waardevolle nieuwe dimensie biedt voor het analyseren van abstracte argumentatiekaders.