An argumentation framework is a formal structure used in artificial intelligence and knowledge representation to model arguments and the conflicts between them. It provides a mathematical basis for analyzing when a set of arguments can be collectively accepted, even when they contradict one another. The framework abstracts away the internal content of individual arguments, focusing instead on the binary attack relation that holds between them. This abstraction allows for the study of reasoning patterns that are defeasible, meaning conclusions can be withdrawn in the face of new counterarguments, a key feature of human commonsense reasoning.
Introduced by Phan Minh Dung in 1995, the framework has become a cornerstone of computational argumentation. It is used in diverse applications, from legal reasoning and multi-agent systems to natural language processing and decision support. The core idea is simple: given a set of arguments and a relation indicating which arguments attack which, one can define various semantics that specify which arguments are considered acceptable. These semantics are based on the notion of admissibility, where a set of arguments is acceptable if it can defend itself against all attacks.
Formal Definition
Formally, an argumentation framework is a pair ⟨A, R⟩, where A is a finite set of arguments and R is a binary relation on A, i.e., R ⊆ A × A. For two arguments a and b, the notation (a, b) ∈ R (or a R b) means that argument a attacks argument b. The framework is often represented as a directed graph, where nodes are arguments and edges represent attacks. This graph-based representation is central to the framework's appeal, as it allows the application of graph-theoretic algorithms to compute acceptability.
A set S ⊆ A is said to be conflict-free if there are no arguments a and b in S such that a attacks b. An argument a ∈ A is acceptable with respect to S if for every argument b that attacks a, there exists an argument c in S that attacks b. In this case, c is said to defend a against b. A conflict-free set S is admissible if every argument in S is acceptable with respect to S. These definitions form the basis for the various extension-based semantics.
Extension-Based Semantics
Dung's original paper defined several semantics that produce sets of acceptable arguments, called extensions. The most basic is the complete semantics. An admissible set S is a complete extension if it contains all arguments that are acceptable with respect to S. Complete extensions always exist, but there can be multiple. The grounded semantics selects the minimal complete extension (with respect to set inclusion), which is unique. It is computed by starting with the empty set and iteratively adding all acceptable arguments until a fixed point is reached. The grounded extension represents the most skeptical position, containing only arguments that are undefeated even when considering all possible defenses.
The preferred semantics selects maximal (with respect to set inclusion) admissible sets. These extensions represent more credulous positions, as they include as many arguments as possible while maintaining admissibility. The stable semantics, another important one, requires that a conflict-free set S attacks every argument not in S. Stable extensions are preferred extensions but not all preferred extensions are stable. The ideal semantics, introduced later, provides a middle ground between grounded and preferred, selecting the maximal admissible set that is contained in all preferred extensions.
Abstract and Structured Argumentation
The framework described above is abstract because it does not consider the internal structure of arguments. In contrast, structured argumentation approaches, such as ASPIC+ and Defeasible Logic Programming (DeLP), build arguments from a knowledge base using inference rules and then derive an abstract framework from those arguments. This allows for a more fine-grained representation of knowledge, but at the cost of increased computational complexity. The abstract framework remains useful as a high-level analysis tool, and many results about abstract frameworks can be transferred to structured settings.
Computational Properties
Computing extensions under various semantics has been studied extensively. For finite frameworks, the grounded extension can be computed in polynomial time, as it involves a simple iterative process. However, determining whether a given argument is in at least one preferred extension (credulous acceptance) is NP-complete, and determining whether it is in all preferred extensions (skeptical acceptance) is co-NP-complete. Stable semantics are similarly complex, with the existence of a stable extension being NP-complete. These complexity results have motivated the development of algorithms and solvers, often based on reductions to propositional satisfiability (SAT) or answer set programming (ASP). The International Competition on Computational Models of Argumentation (ICCMA) has been held since 2015 to benchmark such solvers.
Applications in AI
Argumentation frameworks have found applications in many areas of Artificial intelligence. In legal reasoning, they help model the pros and cons of a case, where statutes and precedents attack each other. In multi-agent systems, agents can use argumentation to negotiate or reach a consensus, with each agent proposing arguments that attack those of others. In Machine learning, argumentation has been used for explainable AI, where the reasoning behind a model's prediction is represented as an argumentation framework, allowing users to query and challenge the decision. For instance, a classifier's output can be justified by a set of supporting arguments, and counterarguments can be presented as attacks.
In natural language processing, argumentation frameworks are used for argument mining, which is the task of extracting arguments and their relations from text. The extracted structure can then be analyzed using the framework's semantics to determine the overall strength of a position. This has applications in debate analysis, fake news detection, and opinion summarization. The framework's ability to handle conflicting information makes it particularly suited for these tasks, where sources often disagree.
Relationship to Other Formalisms
Argumentation frameworks are closely related to other non-monotonic formalisms, such as default logic and logic programming with negation as failure. In fact, Dung showed that logic programming can be interpreted as a special case of argumentation, where each rule corresponds to an argument and attacks arise from conflicting conclusions. This connection has led to a fruitful exchange of ideas, with algorithms and semantics being transferred between the fields. The framework also relates to game theory, as the acceptability of arguments can be characterized in terms of the existence of winning strategies in a two-player dialogue game, where one player proposes an argument and the other attacks it.
Extensions and Variations
Since its introduction, many extensions to the basic framework have been proposed. Bipolar argumentation frameworks add a second relation for support, allowing arguments to strengthen each other. Weighted argumentation frameworks assign weights to attacks, representing the relative strength of the conflict. Value-based argumentation frameworks incorporate values that arguments promote, allowing for a more nuanced comparison. Probabilistic argumentation frameworks assign probabilities to arguments or attacks, enabling reasoning under uncertainty. These variations increase the expressiveness of the framework but also complicate the semantics and computation.
The framework has also been integrated with other AI techniques. For example, in Deep learning, argumentation has been used to combine the outputs of multiple Neural network models, where each model's prediction is an argument and disagreements are attacks. This ensemble approach can improve robustness and provide a mechanism for conflict resolution. In the context of Large language models, argumentation frameworks could be used to structure the reasoning of a model, making its outputs more transparent and verifiable, though this remains an active area of research.
Current Research Directions
Contemporary research in argumentation frameworks focuses on several fronts. One is the development of efficient algorithms for large-scale frameworks, leveraging parallel computing and heuristics. Another is the integration with Generative AI, where argumentation can serve as a reasoning layer for generating coherent and defensible text. Researchers are also exploring dynamic argumentation, where the framework changes over time as new arguments are added or removed, requiring incremental updates to the extensions. The use of argumentation in explainable AI is a growing field, with the goal of providing human-understandable justifications for automated decisions.
The framework's simplicity and power have made it a lasting contribution to the field of knowledge representation. Its ability to model common-sense reasoning, where conclusions are tentative and subject to revision, remains highly relevant as AI systems are deployed in complex, real-world environments. As of the early 2020s, argumentation frameworks continue to be a vibrant area of research, with applications spanning from legal tech to social media analysis, and they are likely to remain a key tool in the AI toolbox for years to come.