Change in Abstract Argumentation Frameworks: Adding an Argument

Claudette Cayrol; Florence Dupin de Saint-Cyr; Marie-Christine Lagasquie-Schiex

Source-linked AI summary

Change in Abstract Argumentation Frameworks: Adding an Argument

Claudette Cayrol, Florence Dupin de Saint-Cyr, Marie-Christine Lagasquie-Schiex

arXiv:1401.3838v1Jan 16, 2014cs.AI

TL;DR

The paper asks how adding a new argument with interactions changes an abstract argumentation system’s outcome. It formalizes structural and argument-status properties, then characterizes this addition under grounded and preferred semantics. The work generalizes earlier single-interaction analysis and connects properties such as Monotony and Priority to Recency.

Problem
The paper studies how changes to abstract argumentation systems, especially adding an interacting argument, affect their extensions and accepted arguments.
Method
It defines general structural and argument-status properties of change, then analyzes the addition of one argument with potentially multiple interactions under grounded and preferred semantics.
Results
The paper establishes conditions under which the proposed properties hold and extends earlier work from one interaction to several interactions, adding properties such as Monotony.
Takeaways & Limitations
The framework supports comparing argumentation changes by both their effects on extension structure and their effects on argument acceptability.
Takeaways & Limitations
The paper’s connection involving expansive changes and Priority to Recency was checked only for stable, grounded, and preferred semantics and may not hold for other semantics.

Abstract

from arXiv · show

In this paper, we address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called structural when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the evolution of this status during the change, e.g., Monotony and Priority to Recency. All these properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.

1. Introduction

The paper studies how adding a new, interacting argument changes an abstract argumentation system’s extensions. It defines structural and argument-status properties for comparing outcomes, then analyzes them under grounded and preferred semantics.

Motivation: Argumentation frameworks select acceptable sets of arguments, called extensions, according to how arguments attack and defend one another.The outcome may also be characterized by arguments belonging to every extension.
Research focus: The paper examines the addition of a new argument and its interactions with existing arguments, studying the resulting change in the initial extensions.This change is motivated by applications such as widening a debate.
Properties: Change properties compare the new and initial extension sets using cardinality, inclusion, or the status of accepted arguments.The paper distinguishes structural properties from properties concerning accepted arguments.
Analysis: The properties of argument addition are studied under grounded and preferred semantics.The paper gives conditions under which particular properties are satisfied.
Contribution: The generalized addition permits the new argument to interact with any number of previous arguments, extending earlier work restricted to one interaction.The paper adds properties such as Monotony and establishes connections among the proposed properties.

2. Basic Concepts in Argumentation Frameworks

Dung’s abstract framework represents arguments and their attacks, while semantics determine which coherent, defensible sets count as extensions. The section introduces argument status and recalls grounded, preferred, and stable semantics and their basic relationships.

Frameworks: An argumentation framework is a non-empty set of arguments together with a binary attack relation between them.The framework is represented as a directed attack graph whose nodes are arguments and edges are attacks.
Acceptability: Acceptable sets are conflict-free sets that defend their members against attackers, and a semantics selects such sets as extensions.The characteristic function maps a set to the arguments it defends.
Semantics: Preferred extensions are maximal admissible sets, whereas the grounded extension is the least fixed point of the characteristic function.Stable extensions are conflict-free sets attacking every argument outside the set.
Basic results: Every framework has at least one preferred extension and exactly one grounded extension, but it may have zero, one, or multiple stable extensions.Stable extensions are always preferred, while the converse does not generally hold.
Basic results: The grounded extension is included in every preferred extension, and every unattacked argument belongs to the grounded extension.For finite attack relations, the grounded extension can be computed by iterating the characteristic function from the empty set.
Argument status: An argument is skeptically accepted when it belongs to every extension, credulously accepted when it belongs to at least one, and rejected when it belongs to none.Under grounded semantics, credulous and skeptical acceptance coincide.

3. Change in Argumentation

The paper formalizes change in argumentation frameworks and classifies its structural impact on extension sets. It then defines general structural and argument-status properties, illustrated through several change operations.

Change operations: A change may modify the arguments, the attacks, or both, yielding four basic operations involving additions or removals.The operations include adding or removing an interaction and adding or removing an interacting argument.
Change operations: Adding a new argument is nontrivial when it has at least one interaction with an existing argument; adding an isolated argument merely inserts it into each extension.The added argument’s interaction set contains incoming or outgoing attacks involving the new argument.
Property classes: The impact of change is evaluated structurally through extension counts and contents, and substantively through the status of particular arguments.These two viewpoints define two classes of general change properties.
Structural properties: The paper illustrates these definitions for argument addition while treating most property definitions independently of the particular change operation.Table 1 summarizes the structural properties introduced in the section.
Structural properties: Structural properties include decisive change, which produces one non-empty extension when the original framework lacked that outcome, and restrictive change, which reduces multiple extensions while retaining at least two.Restrictive change does not apply under grounded semantics because grounded semantics always has one extension.

Example 3

The examples distinguish structural changes by how they alter the number or content of extensions. They define questioning, destructive, expansive, and conservative changes through explicit before-and-after extension sets.

Questioning change: Questioning change increases the number of extensions, including cases where a framework initially has no extension or only an empty extension.The examples show new alternatives appearing after argument addition.
Destructive change: Destructive change removes all non-empty extensions, leaving no extension or only the empty extension.This represents a decisional dead-end in the paper’s classification.
Expansive change: Expansive change preserves the number of extensions while every new extension strictly includes a corresponding original extension.The example gives E = {{A, C}, {A, D}} and E′ = {{Z, A, C}, {Z, A, D}}.
Conservative change: Conservative change leaves the extension set exactly unchanged before and after the change.It is defined by E = E′.

Example 7

The paper distinguishes structural changes by how extension sets relate, then introduces status-based properties for accepted arguments, including Monotony and Priority to Recency.

Structural properties: Altering change preserves the number of extensions while changing at least one extension.This can occur when corresponding extensions overlap without one including the other.
Structural properties: Structural properties classify changes by comparing the resulting extension set with the initial one using cardinality and inclusion relations.These properties are defined generally for several change operations, including adding or removing interactions or arguments.
Status-based properties: Status-based properties examine how accepted arguments evolve after change, especially previously accepted arguments and the newly added argument.The paper defines Monotony for prior acceptance and Priority to Recency for acceptance of the added argument.
Status-based properties: Monotony is developed for general semantics by considering credulous and skeptical acceptance, including cases with one or multiple extensions.With a single extension, acceptance is determined by membership in that unique extension.

Definition 15 (Monotony)

Monotony requires prior extensions or accepted arguments to remain represented after change, while related properties connect extension structure with argument status. These connections depend partly on the semantics considered.

Monotony definitions: Monotony requires each original extension to be included in at least one resulting extension.Credulous Monotony instead compares unions, while Skeptical Monotony compares intersections of the extension sets.
Monotony relations: Monotony implies Credulous Monotony, but neither Monotony nor Skeptical Monotony generally implies the other.Under semantics with one extension, the three notions coincide.
Monotony relations: Monotony and Credulous Monotony imply Partial Monotony for every original argument, whereas Skeptical Monotony does not.Partial Monotony requires an argument appearing in an original extension to appear in at least one resulting extension.
Priority to Recency: Priority to Recency requires the added argument to belong to every resulting extension, and applies only to argument-addition changes.The paper relates this property to the acceptance of newly added information.
Structural-status connections: Conservative and expansive changes always satisfy Monotony and Skeptical Monotony, while destructive, altering, and restrictive changes never satisfy Monotony.For single-extension semantics, Monotony and Skeptical Monotony hold exactly for decisive, expansive, or conservative changes.
Structural-status connections: Under grounded, stable, and preferred semantics, expansive argument-addition changes always satisfy Priority to Recency.The broader inclusion claim is explicitly limited to these three semantics.

4. Characterizing Argument Addition under Grounded or Preferred Semantics

The paper characterizes how adding one interacting argument changes extensions under grounded and preferred semantics. It derives sufficient conditions for desirable properties and necessary conditions for undesirable ones, including cases where the new argument is accepted, extensions are preserved, or extensions become destructive.

Scope and criteria: The change adds exactly one argument that interacts with at least one existing argument, with conditions depending on the semantics.The analysis focuses on this nontrivial form of argument addition rather than adding an isolated argument.
Scope and criteria: The paper distinguishes structural properties based on the extension set from properties based on which arguments are accepted.Examples include decisive, expansive, conservative, monotonic, questioning, destructive, altering, and Priority to Recency.
Grounded semantics: Under grounded semantics, if the initial grounded extension is empty, an unattacked new argument is included in the new extension together with arguments it indirectly defends.If the new argument is attacked by the grounded extension, the resulting extension remains empty and the change is conservative.
Grounded semantics: Under grounded semantics, when the initial extension is nonempty and the new argument does not attack it, monotony holds; if the extension defends the new argument, Priority to Recency also holds.If the initial extension does not defend the new argument, the change is conservative; if it does, the new extension adds the new argument and possibly arguments indirectly defended by it.
Grounded semantics: Under grounded semantics, the addition is never questioning or restrictive, while it is destructive exactly when the new argument attacks every unattacked existing argument and is itself attacked after the change.The destructive characterization applies when the initial extension is nonempty.
Preferred semantics: Under preferred semantics, if the new argument attacks no existing extension, each extension remains available or can be expanded with the new argument, and the number of extensions is unchanged.If every preferred extension defends the new argument, Priority to Recency holds because the new argument belongs to every resulting extension.

5. Discussion and Future Works

The paper generalizes argument addition to interactions with any number of existing arguments and studies structural and status-based consequences through necessary and sufficient conditions. It distinguishes this abstract, extension-based analysis from belief revision, warrant-prioritized revision, dialogue strategies, and related dynamics work.

The paper studies change by adding a new argument that may interact with previously introduced arguments, establishing conditions for properties of the resulting outcome.
The paper assumes no underlying knowledge from which arguments and interactions are constructed, and argumentation lacks a clear, standard notion of consistency.
The analysis separates structural changes to the set of extensions from changes in argument acceptability, with Tables 4 and 5 summarizing necessary and sufficient conditions.
Unlike standard belief revision, this approach represents knowledge with argumentation frameworks and evaluates outcomes as sets of extensions rather than logical formulae.
The generalized addition extends earlier work from one interaction to any number of interactions and introduces Monotony alongside broader connections among properties.
The approach remains abstract and extension-based, unlike warrant-prioritized revision, which uses structured arguments and aims to ensure the added argument is warranted.
The framework does not define dialogue protocols or strategies; it establishes general conditions for preserving acceptability and accepting a new argument.

Appendix A. Proofs

The appendix establishes that adding a new argument introduces no new cycle when the new argument has no outgoing or no incoming interaction with the existing graph.

If the new argument Z does not attack any existing argument, the addition introduces no new cycle in the revised graph.
If no existing argument attacks Z, the addition likewise introduces no new cycle in the revised graph.
The proof follows directly from the fact that only one argument is added.

Proofs Related to Section 3.4 (Connections between Properties)

These proofs connect extension-structure properties across grounded, preferred, and stable semantics, using inclusion and admissibility arguments for changes involving a new argument.

The appendix records that several propositions follow directly from the definitions of the relevant change properties.
Preferred semantics: Under preferred semantics, an expansive change can produce an extension without the new argument that is not an extension of the original framework.
Preferred semantics: The preferred-semantics argument derives a conflict or failed defense in the original framework when the revised extension strictly exceeds an original extension.
Stable semantics: The stable-semantics proof uses the fact that a strict extension inclusion supplies an argument outside the smaller stable extension, which the smaller extension attacks.

Proofs Related to Section 4.1 (Under the Grounded Semantics)

The grounded-semantics proofs characterize how adding an argument affects the grounded extension through attack relations, defense, and iterated characteristic functions.

If the new argument Z does not indirectly attack an existing argument X, membership of X in the original grounded iteration is preserved after addition.
If Z is not attacked by the existing framework, Z belongs to the revised grounded extension.
When the original grounded extension is empty, whether Z is attacked determines whether the revised grounded extension remains empty or contains Z.
Under grounded semantics, a change is decisive when the original grounded extension is empty and the revised one is nonempty.
If Z does not attack the original grounded extension, the original extension is included in the revised one.
If the original grounded extension defends Z, the revised extension includes the original extension together with Z in the corresponding case.
Under grounded semantics, restrictive and questioning changes cannot occur because there is only one grounded extension.
A destructive change occurs when a nonempty original grounded extension becomes empty after all originally unattacked arguments and Z are attacked.

Proofs Related to Section 4.2 (Under the Preferred Semantics)

The proofs characterize how adding an argument Z affects preferred extensions under conditions on attacks, defense, and cycles. They establish preservation, inclusion, cardinality, monotony, and destructive cases for the resulting framework.

Preferred-extension inclusion: If Z is not attacked by G, every preferred extension of G′ contains Z.This follows because Z remains unattacked after the change and preferred extensions must include it.
Admissibility transfer: If Z attacks no argument of G, removing Z from any non-empty preferred extension of G′ yields an admissible set in G.The proof preserves conflict-freeness and defense for the remaining arguments.
Extension correspondence: When Z attacks no argument of G, each preferred extension of G extends to either an extension of G′ or that extension together with Z, depending on whether it defends Z.If an original extension defends Z, its union with Z is admissible and preferred; otherwise the original extension itself remains an extension.
Structural preservation: Under the same no-outgoing-attack condition, G and G′ have the same number of preferred extensions.Distinct extensions of G cannot be included in one extension of G′, while every extension of G′ maps back to an extension of G.
Monotony: The addition satisfies Monotony when G has no extension or has a non-empty extension whose admissibility is preserved in G′.Each extension of G is included in a preferred extension of G′.
Destructive case: If there are no even-length cycles and all unattacked arguments of G, together with Z, become attacked, the unique extension of G′ is empty, making the change destructive.The proof derives an impossible infinite sequence of distinct arguments if a non-empty extension existed.

Appendix B. Illustration of Properties for the Other Change Operations

The appendix illustrates that the other change operations realize several structural classes and can either satisfy or violate Monotony. The examples distinguish decisive, destructive, altering, conservative, expansive, questioning, and restrictive changes.

Operations violating Monotony: Examples show questioning, destructive, and altering changes that do not satisfy Monotony.The appendix groups these properties across examples 2.1–5.1, 6, and 8.1.
Decisive and destructive changes: Adding (A,C) to a three-argument cycle is decisive, changing the extension set from empty to {{A}}, while the inverse removal is destructive.The addition satisfies Monotony, whereas the inverse operation does not.
Decisive and destructive changes: Adding (C,A) to a chain is destructive, changing {{A,C}} to empty, while the inverse removal is decisive.Here the addition violates Monotony and the inverse operation satisfies it.
Altering and expansive changes: Adding (A,C) to a chain is altering, changing {{A,C}} to {{A}}, while the inverse removal is expansive.The addition fails Monotony, whereas the inverse operation satisfies it.
Further structural cases: Other examples realize conservative, questioning, restrictive, and expansive changes with the stated Monotony outcomes.The appendix gives explicit extension-set transitions for conservative, questioning, restrictive, and expansive cases.