Abstract Argumentation

Origin. Phan Minh Dung introduced abstract argumentation frameworks (1995). Arguments are abstract entities; the focus is on attack relations and acceptable sets. Unified view subsuming logic programming, default logic, and other non-monotonic systems. Foundation for computational argumentation in AI, law, and multi-agent systems.

Models. Arguments attacking other arguments. An argumentation framework is a directed graph: nodes are arguments, edges are attacks. Which arguments can be jointly accepted? Various semantics define acceptable sets (extensions). Abstract: no internal structure of arguments, only attacks matter.

Formalism.

Argumentation framework: AF = (A, R) where:

A: set of arguments
R ⊆ A × A: attack relation
(a,b) ∈ R means "a attacks b"

Key concepts:

S ⊆ A is conflict-free iff no a,b ∈ S with (a,b) ∈ R
a is defended by S iff for all b attacking a, some c ∈ S attacks b
S is admissible iff conflict-free and defends all its members

Extension semantics:

Complete: admissible and contains all arguments it defends
Preferred: maximal complete extension
Grounded: minimal complete extension (unique, skeptical)
Stable: conflict-free and attacks all non-members
Hierarchy: Stable ⊆ Preferred ⊆ Complete ⊇ Grounded

Labeling semantics: Assign each argument: in (accepted), out (rejected), undec (undecided).

in: all attackers are out
out: some attacker is in
undec: neither applies

Reasoning modes:

Credulous: argument is in some extension
Skeptical: argument is in all extensions

Example: A = {a, b, c}, R = {(a,b), (b,a), (b,c)}

a and b attack each other
b attacks c
Preferred extensions: {a,c} and {b}
Grounded: {} (no unattacked argument)
Stable: {a,c} and {b}

Symbols.

Symbol	Unicode	Name	Meaning
→	U+2192	Rightwards arrow / Attack	a → b : a attacks b
↔	U+2194	Left right arrow / Mutual attack	Attack running in both directions
⊆	U+2286	Subset	Extension inside A; attack relation inside A × A
⊇	U+2287	Superset	Direction of containment in the semantics hierarchy
×	U+00D7	Multiplication sign / Cartesian product	Attacks are ordered pairs of arguments
∈	U+2208	Membership	Argument in an extension, or pair in the attack relation
A	—	Arguments	Nodes of the framework
R	—	Attack relation	Edges of the framework
S	—	Candidate set	Set of arguments tested for conflict-freeness or admissibility
E	—	Extension	Set of arguments accepted under a semantics
GE	—	Grounded extension	Least complete extension; unique and always exists
PR	—	Preferred extensions	Maximal admissible sets
ST	—	Stable extensions	Conflict-free sets attacking every non-member
in	—	Label	Accepted: every attacker is labelled out
out	—	Label	Rejected: some attacker is labelled in
undec	—	Label	Undecided: neither condition applies

Metatheory. Dung (1995) observed that the characteristic function F(S) = {a : S defends a} is monotone, so by Knaster–Tarski it has a least fixpoint; that fixpoint is the grounded extension, which is consequently unique, always exists, and is computable in polynomial time. The semantics form a hierarchy — every stable extension is preferred, every preferred extension is complete, and the grounded extension is the least complete one — and preferred extensions always exist whereas stable ones need not, a single self-attacking argument having none. Caminada (2006) proved complete labellings to correspond bijectively with complete extensions, the other semantics being recovered by maximizing or minimizing the in, out and undec sets, so the two presentations carry the same information. Complexity is settled for the standard semantics: credulous acceptance is polynomial for grounded and NP-complete for complete, stable and preferred, while skeptical acceptance is polynomial for grounded, coNP-complete for stable, and Π₂ᵖ-complete for preferred (Dunne and Bench-Capon 2002). Dung's reductive claim was that stable extensions of an instantiated framework are exactly the stable models of the corresponding logic program and the extensions of the corresponding default theory, with the grounded extension answering to the well-founded model.

Applies to. AI reasoning systems. Legal argumentation. Multi-agent dialogue. Decision support. Explainable AI. Deliberation and debate modeling. Defeasible reasoning.

Limitations. Abstraction is the design and also the cost: the framework records that a attacks b but neither what the arguments claim nor why the attack succeeds, so nothing constrains which graphs are legitimate and instantiations resting on quite different underlying logics can yield the same graph. The choice of semantics is not settled from inside — the standard ones disagree on the same framework, stable extensions may fail to exist, and where they do the stable-skeptical relation collapses into vacuous totality. Odd-length attack cycles are the recurring source of trouble: a self-attacking argument admits no stable extension, and a three-cycle leaves the grounded extension empty with every argument undecided. Only attack is primitive; support, preference and joint attack are not definable and require separate frameworks with semantics of their own. Frameworks are static, so a single added argument can alter every extension, and the theory says nothing about how the graph is revised.