Stable Extension

In an Argumentation Framework, an admissible set that attacks every argument outside it. A stable extension may not exist (e.g. an odd-length attack cycle defeats stability); when it does, it coincides with one of the preferred extensions. Dung’s central correspondence theorem: stable extensions of an AF coincide with the stable models of the corresponding normal logic program (Gelfond–Lifschitz semantics) — the fact that established Dung’s framework as the unifying abstraction across nonmonotonic reasoning.

In this vault

Backlinks

Linked Pages

Stable Model Semantics

Gelfond & Lifschitz’s (1988) semantics for normal logic programs with negation-as-failure: a stable model of a program P is a model M of the reduct P^M (the positive program obtained by deleting clauses whose negative body fails in M and stripping the surviving negative literals). The standard semantics for Answer Set Programming (ASP). Dung (1995) proved that stable models of P coincide with stable extensions of the corresponding Argumentation Framework — establishing nonmonotonic argumentation and ASP as the same theory under different syntax.

In this vault

Argumentation Framework

Dung’s (1995) abstraction: a directed graph (A, R) whose nodes are arguments and whose edges R ⊆ A × A are attacks. The semantics is content-free — what an argument is is supplied by the instantiating theory — but the family of extensions (Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, complete) is universal. The substrate for ASPIC+, ABA, DeLP, multi-agent dialogue protocols, legal reasoning systems, and (recently) LLM-agent debate.

In this vault

On the Acceptability of Arguments

On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games

Reference: Dung, P. M. (1995). On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2), pp. 321–357. DOI · Open access PDF (CUNY)

Summary

Dung shows that an enormous span of problems in AI — nonmonotonic reasoning, logic programming, n-person game theory — share a single underlying abstraction: a directed graph whose nodes are arguments and whose edges are attacks. He calls this an abstract argumentation framework (AF) and develops, in 30 pages, the entire theory of argument acceptability that has dominated computational argumentation ever since. The headline definitions: a set of arguments is conflict-free if it contains no attacker-attackee pair; admissible if it is conflict-free and defends each of its members against every attacker (an argument is defended if every attacker on it is itself attacked by something in the set); complete if it is admissible and contains every argument it defends; grounded (the unique smallest complete extension), preferred (a maximal admissible set), stable (admissible and attacks every argument outside it). Dung then proves the unifying results: the stable extensions of an AF coincide with the stable models of the corresponding logic program (Gelfond–Lifschitz); preferred extensions correspond to the preferred logic-programming semantics; default-logic extensions arise as stable extensions of an AF derived from default rules; and (the n-person game result) the stable extensions of a game’s argumentation graph correspond to the stable strategies of the game. The framework is content-agnostic — what an “argument” is is left to the instantiating theory — which is precisely what makes it apply across so many domains. Three decades later it is the substrate for legal reasoning systems, multi-agent dialogue protocols, structured argumentation calculi (ASPIC+, ABA, DeLP), and the theoretical underpinning of LLM-agent debate frameworks.

Key Ideas

Argument as a black box, attack as a binary relation: the AF (A, R) with A a set of arguments and R ⊆ A × A is the entire syntactic apparatus. All domain-specific structure (premises, conclusions, defeasible rules) is internalised when the AF is instantiated.
Defence as the operative concept: an argument a is defended by a set S iff every attacker of a is itself attacked by some member of S. Acceptability is “S defends every member of S.”
Family of extensions: admissible (defends itself), complete (admissible + closure), grounded (least complete — sceptical), preferred (maximal admissible — credulous), stable (admissible + attacks everything outside).
Universal correspondences: stable extensions ⇔ stable models of normal logic programs; preferred extensions ⇔ preferred semantics of logic programs; default-logic extensions ⇔ stable extensions of the AF generated by the defaults; the stable extensions of a 2-person game’s defeat graph ⇔ winning strategies.
Inference as fixed-point computation: each semantics is the fixed point of a characteristic operator on 2^A; the order-theoretic structure (complete partial order of admissible sets) makes the theory algorithmically tractable.
Sceptical vs credulous reasoning: every AF supports both — a is sceptically accepted iff in every preferred extension; credulously accepted iff in some preferred extension. The choice is a downstream policy decision.
Why it works as a unifier: nonmonotonic reasoning, default logic, logic programming with negation-as-failure, and game-theoretic equilibria all reduce to “find a coherent set of accepted positions in the presence of mutual challenge” — which is exactly what Dung’s framework computes.

Connections

Conceptual Contribution

Claim: Acceptability of arguments under attack is the abstraction common to nonmonotonic reasoning, logic programming with negation-as-failure, default logic, and equilibrium notions in n-person games. A single, content-free framework — a directed graph of arguments and attacks plus a fixed family of acceptability conditions — captures all of them.
Mechanism: Abstract argumentation framework (A, R); characteristic function F_AF : 2^A → 2^A mapping a set to the arguments it defends; admissible / complete / grounded / preferred / stable extensions defined as fixed points of F_AF under various conditions; instantiation theorems mapping logic-programming and default-logic problems to AFs and proving extension-correspondence.
Concepts introduced/used: Argumentation Framework, Attack Relation, Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, Defence (Argumentation), Sceptical Reasoning, Credulous Reasoning.
Stance: foundational technical paper.
Relates to: Conceptually the missing companion of Circumscription - A Form of Nonmonotonic Reasoning (McCarthy 1980) — both address nonmonotonicity, but Dung gives an argumentation-graph framing that plays directly with logic-programming semantics where circumscription works at the level of model-theoretic minimisation. Provides the formal substrate beneath the dialogue-game tradition: a Persuasion Dialogue (Walton & Krabbe) is operationally a process for constructing the attack edges of a shared AF and computing extensions over it. The structured-argumentation systems (ASPIC+, ABA, DeLP, defeasible logic programming) instantiate Dung’s abstract framework with rule-based languages — and the SPL/Hence defeasible-logic engine used elsewhere in this vault is in this same family. In the LLM-agent era, multi-agent debate / self-consistency protocols recapitulate Dung’s machinery: agents generate arguments, attacks are mined from contradictions, and grounded/preferred extensions correspond to convergent / multi-modal answers. The paper’s reach into n-person games supplies a bridge to the game-theoretic / mechanism-design strands of Pact - A Choreographic Language for Agentic Ecosystems and Deals Among Rational Agents.