PaperlayerView exact revision on arXiv

Source-linked AI summary

Graduality in Argumentation

C. Cayrol, M. C. Lagasquie-Schiex

arXiv:1107.0045v1cs.AI

TL;DR

The paper addresses the predominance of low-level or binary valuation and acceptability in argumentation systems. It develops gradual interaction-based valuation models and uses them to refine argument selection, while treating graph structures such as cycles explicitly. The resulting valuations distinguish arguments through induced orderings and support multiple acceptability levels.

  • Problem

    Most argumentation proposals offer few valuation levels and usually binary acceptability, limiting representation to selected versus non-selected arguments.

  • Method

    The paper defines gradual interaction-based valuation models for Dung-style attack graphs and applies them to gradual acceptability classes.

  • Results

    The proposed valuations distinguish arguments through a preordering and are used for selecting arguments with different levels of acceptability.

  • Takeaways & Limitations

    Gradual valuation and acceptability provide more differentiated argument selection than binary membership in an acceptable set.

  • Takeaways & Limitations

    Cycles yield infinite tupled values, so the proposed algorithm truncates propagation to obtain finite but incomplete values.

Abstract

from arXiv · show

Argumentation is based on the exchange and valuation of interacting arguments, followed by the selection of the most acceptable of them (for example, in order to take a decision, to make a choice). Starting from the framework proposed by Dung in 1995, our purpose is to introduce 'graduality' in the selection of the best arguments, i.e., to be able to partition the set of the arguments in more than the two usual subsets of 'selected' and 'non-selected' arguments in order to represent different levels of selection. Our basic idea is that an argument is all the more acceptable if it can be preferred to its attackers. First, we discuss general principles underlying a 'gradual' valuation of arguments based on their interactions. Following these principles, we define several valuation models for an abstract argumentation system. Then, we introduce 'graduality' in the concept of acceptability of arguments. We propose new acceptability classes and a refinement of existing classes taking advantage of an available 'gradual' valuation.

1. Introduction

Argumentation frameworks model interacting arguments whose relative strength is valued before selecting acceptable arguments. The paper targets gradual valuation and acceptability to replace predominantly binary selection with multiple levels.

  • Argumentation systems exchange and value interacting arguments before selecting the most acceptable ones for reasoning, decision support, or negotiation.
  • Intrinsic valuation assigns argument values independently of interactions, whereas interaction-based valuation incorporates attackers and defenders.
  • Existing acceptability approaches distinguish individual arguments from acceptable sets, with Dung’s framework supporting binary membership in an acceptable set.
  • Most proposals provide few valuation levels and usually binary acceptability, motivating graduality in both valuation and selection.
  • The paper first formulates principles and models for gradual interaction-based valuation, then applies them to gradual acceptability classes.

2. Dung’s (1995) framework and its graphical representation

The paper adopts Dung’s abstract attack framework and represents it as a directed graph. It defines graph-theoretic notions for attackers, defenders, paths, branches, cycles, and their dependencies.

  • An argumentation system is a set of arguments A together with a binary attack relation R, represented as a directed attack graph.
  • Leaves are arguments without attackers, while attack and defence branches are leaf-to-argument paths with odd and even lengths, respectively.
  • A path is a sequence of attacked arguments, and its length equals the number of edges used.
  • The framework distinguishes dependent, independent, root-dependent, isolated, and interconnected paths or cycles to characterize graph structure.
  • Direct and indirect attackers or defenders are defined through attack paths, with attackers sometimes also serving as defenders.
  • Reinstatement is represented indirectly: a defender increases the value and selection possibility of the argument it protects.

3. Graduality in interaction-based valuations

The paper develops local and global gradual valuations based on attacks and defence branches, extending interaction-based approaches beyond a few discrete values. These valuations induce argument orderings for selection.

  • Two valuation methods are proposed: local valuation uses direct attackers, while global valuation represents all attack and defence branches.
  • Increasing direct attack lowers an argument’s value, whereas stronger defence contributes to a higher value.
  • Local valuation generalizes existing labellings and categorisers by aggregating direct attackers and mapping their combined attack to argument value.
  • The generic local valuation induces a complete preordering, so any two arguments are comparable by their values.
  • For isolated cycles, odd cycles share a common fixpoint value, while even cycles assign values that are fixpoints of an iterated function.
  • The valuation principles make unattacked arguments maximal and account for direct attackers through a non-increasing attack valuation.

D1 D2 D3

The paper develops tuple-based gradual valuations for acyclic argumentation graphs and extends them to cycles through rewriting, while comparing this approach with generic valuations.

  • D1 D2 D3: The generic valuation leaves some arguments incomparable, whereas a concrete valuation can rank A above B1, D1, and C1.The generic constraints are insufficient for comparing A and B1 with other arguments; the Besnard–Hunter instance makes A better than those arguments.
  • D1 D2 D3: For isolated cycles, the generic valuation yields values constrained by a fixpoint of g^2, while the Besnard–Hunter instance gives approximately 0.618.The value solves x^2 + x − 1 = 0, producing the inverse of the golden ratio.
  • D1 D2 D3: The global approach represents an argument by the lengths of all attack and defence branches rooted in it.Defence branches have even lengths, attack branches odd lengths, and tupled values separate these components.
  • D1 D2 D3: For acyclic graphs, tuple valuation assigns each argument a pair of tuples propagated from its direct attackers, with leaves valued [0∞, ()].The even and odd components are computed recursively by shifting and concatenating attackers’ tupled values.
  • D1 D2 D3: In the worked acyclic example, A receives the tupled value [(2, 4), (1, 3)].The example also assigns values to intermediate arguments such as B1, B2, and C3.
  • D1 D2 D3: Cycles require alternative representations because an infinite cycle branch has undefined parity, while treating cycles as infinitely many finite branches yields tupled values.The rewriting process creates acyclic but infinite graph representations and requires newly created arguments.

Example 7 – Unattacked cycle (continuation)

For an unattacked cycle, recursive tuple equations generate infinite even and odd sequences, yielding a uniform valuation for every argument in the cycle.

  • Example 7 – Unattacked cycle (continuation): The rewritten graph produces sequences x_k of infinite even tuples and y_k of infinite odd tuples.The sequences satisfy x_k = (2) ⋆ (x_k+1 ⊕2) and y_k = (1) ⋆ (y_k+1 ⊕2).
  • Example 7 – Unattacked cycle (continuation): Every positive even integer belongs to each x_i tuple, while every odd integer belongs to each y_i tuple.These sequence properties establish the infinite parity-separated structure of the valuation.
  • Example 7 – Unattacked cycle (continuation): The induction proving these sequence properties is performed on p.The result applies to the recursively defined tuple sequences associated with the rewritten cycle.
  • Example 7 – Unattacked cycle (continuation): The same results extend to every unattacked cycle of length n, with n ≥2.The extension is stated for all arguments in such cycles.

Property 8 (Properties of unattacked cycles)

The cycle valuation assigns every argument in an unattacked cycle the same infinite even/odd tupled value, while attacked cycles produce asymmetric values through rewriting.

  • Property 8 (Properties of unattacked cycles): Every argument A in an unattacked cycle receives v(A) = [(2, 4, 6, . . .), (1, 3, 5, . . .)].The even component records all positive even lengths and the odd component all positive odd lengths.
  • Property 8 (Properties of unattacked cycles): The attacked-cycle derivation uses rewritten valuation equations and solved tuple sequences to obtain these values.The empty tuple is explicitly identified in the surrounding derivation.
  • Property 8 (Properties of unattacked cycles): For the attacked-cycle continuation, the rewritten graph gives v(A) = [(), (1, 3, 5, . . .)] and v(B) = [(2, 4, 6, . . .), ()].The downstream arguments receive corresponding values, including v(C) = [(2, 4, 6, . . .), ()] and v(E) = [(), (3, 5, 7, . . .)].
  • Property 8 (Properties of unattacked cycles): Cycle values are infinite, so the algorithm truncates propagation after a parameterized maximum number of runs, producing finite but incomplete tupled values.This computational treatment is presented as necessary because cycles are expensive.

Definition 13 (Lexicographic ordering on tuples)

The paper compares tupled argument values by first counting defence and attack branches, then applying lexicographic ordering, producing a cautious partial preordering with possible incomparability.

  • Definition 13 (Lexicographic ordering on tuples): The generalized lexicographic ordering compares finite or infinite tuples at the first differing position, while allowing equal tuples of equal cardinality.It extends classical lexicographic ordering but is not well-founded.
  • Definition 13 (Lexicographic ordering on tuples): Argument comparison first evaluates branch counts using separate defence and attack criteria, concluding only when one argument has more defence and fewer attacks.This cautious aggregation prevents a positive comparison when the criteria conflict.
  • Definition 13 (Lexicographic ordering on tuples): If branch counts do not decide the comparison, lexicographic ordering compares the even components and odd components of the tupled values.The intended preference is better defence together with weaker attack.
  • Definition 13 (Lexicographic ordering on tuples): Algorithm 1 defines a partial preordering: some tupled values are comparable, while others remain incomparable.The procedure includes equality, strict ordering, reverse ordering, and explicit incomparable cases.
  • Definition 13 (Lexicographic ordering on tuples): The unique maximal tupled value is [0∞, ()], and the unique minimal value is [(), 1∞].The induced ordering on arguments is defined through their tupled values.
  • Definition 13 (Lexicographic ordering on tuples): The valuation principles make unattacked arguments maximal and increase value when defence improves or attack degrades.Conversely, improving attack or degrading defence decreases value.

3.3 Main differences between “local” and “global” valuations

Local valuations assess arguments through nearby attack relationships, whereas global valuations incorporate broader defence structures. The paper’s global approach can reverse local comparisons and treats certain branches independently.

  • Local versus global comparison: In the local approach, B′ is better than B because it suffers one attack instead of two.
  • Local versus global comparison: In the global approach, B is better than B′ because B has at least one defence while B′ has none.
  • Independence of branches: The global approach makes A and A′ equal when their branches yield the same value, even though they root different subgraphs.
  • Independence of branches: The local approach instead gives A at least as good a value as A′ when A has one direct attacker and A′ has two.
  • The paper proposes two gradual valuation models whose induced preorders distinguish arguments and support later selection.

4. Graduality and acceptability

The paper extends Dung’s binary acceptability framework with more gradual collective levels. It refines existential acceptance by considering whether an argument’s attackers are themselves accepted.

  • Collective acceptability: Dung’s collective framework defines an argument as acceptable when it belongs to an acceptable set, or extension.
  • Motivation for refinement: The three classical levels are insufficient when two arguments are exi-accepted while attacking one another.
  • Clean acceptance: A cleanly-accepted argument belongs to at least one extension while none of its attackers belongs to any extension.
  • Acceptability levels: Arguments may be uni-accepted, cleanly-accepted, only-exi-accepted, or not-accepted under a given semantics.
  • Example: Under preferred semantics, D, C2, and G are uni-accepted; I is cleanly-accepted; A and E are only-exi-accepted; and B, C1, F, H, and J are not-accepted.

C1 D C2

The proposed acceptability refinements and gradual valuations do not generally induce compatible partitions. Compatibility emerges only under particular graph and valuation conditions.

  • Single-extension case: When there is only one extension, the uni-, exi-, and cleanly-accepted levels coincide.
  • Compatibility results: Under stable semantics, uni-accepted and cleanly-accepted arguments form the same class.
  • Compatibility results: Under preferred semantics without odd cycles, uni-accepted and cleanly-accepted arguments also coincide.
  • Valuation-based refinement: Gradual valuations can refine each acceptability level by ordering arguments within, for example, the exi-accepted class.
  • Caution: Applying valuation preorders without respecting acceptability levels can make lower-acceptability arguments outrank higher-acceptability ones.
  • General incompatibility: In general, well-defended arguments do not coincide with cleanly-accepted arguments, and some uni-accepted arguments may not be well-defended.

E G H

For finite acyclic argumentation systems, the paper identifies conditions under which acceptability and gradual valuation partitions agree. These conditions differ between global tuple valuations and generic local valuations.

  • Acyclic systems: In finite acyclic systems, preferred and stable semantics have one extension, so uni-, exi-, and cleanly-accepted levels coincide.
  • Global valuation: For tuple-based global valuations, accepted arguments are well-defended under the stated graph condition, but the converse generally fails.
  • Global valuation: A well-defended argument becomes accepted under the tuple valuation when all branches leading to it are defence branches.
  • Local valuation: For generic local valuations satisfying condition (∗), exi-, uni-, and cleanly-accepted arguments are exactly the well-defended arguments.
  • Local valuation limitations: Condition (∗) fails for the Besnard–Hunter local valuation, where individual attacker improvements need not improve the combined valuation.
  • Local valuation limitations: Condition (∗) holds for local valuations using h = max, but not when h can exceed the maximum input value.

5. Conclusion

The paper introduces graduality into argument valuation and acceptability, moving beyond binary selection by using interaction-based valuations and finer acceptability classes.

  • The paper introduces graduality into argument valuation and acceptability as two central issues in argumentation systems.This extends selection beyond the usual binary distinction between selected and non-selected arguments.
  • Valuation: Two interaction-based gradual valuation formalisms are defined for arguments.One is a local generic valuation based on direct attackers; the other is a global labelling based on the whole influencing attack graph.
  • Valuation: Each valuation induces a preordering over arguments, exposing differences between local and global approaches.
  • Acceptability: Collective acceptability is refined by cleanly-accepted arguments, while individual acceptability adds well-defended and not-well-defended levels.The refinement splits exi-accepted arguments into cleanly-accepted and only-exi-accepted sublevels.
  • Acceptability: Gradual valuations provide further gradation within the levels of both collective and individual acceptability.
  • Limitations: The well-defended approach remains open for further investigation, particularly regarding computational aspects.

Appendix A. The proofs

The appendix proves properties of the valuation and acceptability formalisms, including ordering, cycle behavior, and the relationship between cleanly-accepted and uni-accepted arguments.

  • The appendix supplies proofs for the properties introduced in Sections 3 and 4.
  • Valuation properties: A valuation assigns each argument a value from a subset of a completely ordered set.
  • Cycles: For even cycles, valuations may differ across arguments; for odd cycles, all arguments receive the same value, which is a fixpoint of g.
  • Valuation properties: The generic valuation satisfies principles for unattacked arguments, direct attacks, and monotonic degradation through the non-increasing function g.
  • Tupled values: The proofs establish that the tupled-value relation is a partial ordering with unique maximal and minimal elements.The unique maximal element is [0∞, ()], while the unique minimal element is [(), 1∞].

Appendix B. Computation of tupled values

Tupled values are computed by propagating evaluations through attack graphs, treating interconnected cycles as composite meta-cycles and using a dedicated data structure and algorithm.

  • Propagation: The computation evaluates an argument once the values of its direct attackers are known.
  • Cycles: Cycles are treated as meta-arguments and evaluated after their external direct attackers have been evaluated.
  • Data structures: The algorithm uses a data structure L listing cycles, their members, and cycle inputs used for propagating values.
  • Cycles: Interconnected cycles are grouped and processed as a single mcycle for efficiency.An mcycle is formed from interconnected cycles satisfying the stated path condition.
  • Algorithm 2: Algorithm 2 maintains evaluated and unevaluated portions of the graph and repeatedly chooses arguments or mcycles for evaluation.
  • Example: The algorithm was applied to an example after rewriting, without creating new arguments needed for rigorous formalization.
Loading 1107.0045v1…