Notes taken from ‘Computing ideal sceptical argumentation’ by P. M. Dung, Paolo Mancarella and F. Toni (2006)
1, Introduction
… The semantics of admissible arguments is credulous, in that it sanctions a set as acceptable if it can successfully dispute every argument against it, without disputing itself. However, there might be conflicting admissible sets. In some applications, it is more appropriate to adopt a sceptical semantics, whereby, for example, only beliefs sanctioned by all (maximally) admissible sets of assumptions are held. For example, in the legal domain, different members of a jury could hold different admissible sets of assumptions but a guilty verdict must be the result of sceptical reasoning. Also, in a multi-agent setting, agents may have competing plans for achieving goals (where a plan can be interpreted as an argument for the goal it allows to achieve), and, when negotiating resources, they may decide to give away a resource only if that resource is not needed to support any of their plans. Furthermore, in the same setting, agents may decide to request an “expensive” resource from another agent only if that resource is useful to render all plans for achieving its goal executable.
Several sceptical semantics have been proposed for argumentation frameworks, notably the grounded semantics and the semantics whereby beliefs held within all maximally admissible sets of arguments are drawn, referred to as the sceptically preferred semantics. The grounded semantics can be easily computed but is often overly sceptical. Procedures for the computation of the sceptically preferred semantic exist… However, to the best of our knowledge, no procedure exists for computing the sceptically preferred semantics for non-coherent cases.
The ideal semantics is sceptical, and has the advantage of being easily computable, by a modification of the machinery presented in ‘Dialectic proof procedures for assumption-based, admissible argumentation’, but without being overly sceptical…
2, Argumentation frameworks and semantics
2.1, An abstract argumentation framework is a pair (Arg, attacks) where Arg is a finite set, whose elements are referred to as arguments, and ‘attacks’ is a binary relation over Arg. Given sets X, Y of (Arg) arguments, X attacks Y iff there exists x (in X) and y (in Y) such that (x, y) is a member of ‘attacks’.
… Several notions of “acceptable” sets of arguments can be defined…
2.2, A set X of arguments is
- admissible iff X does not attack itself and X attacks every argument Y such that Y attacks X;
- preferred iff X is maximally admissible;
- complete iff X is admissible and X contains all arguments x such that X attacks all attacks against x;
- grounded iff X is minimally complete;
- ideal iff X is admissible and it is contained in every preferred set of arguments.
The maximal ideal set is less sceptical than the grounded set… It does not always coincide with the intersection of all preferred sets… It can be a proper subset of the intersection of all preferred sets.
(Lemma 2.1) Let X and Y be two ideal sets of arguments. Then ‘X U Y’ is ideal.
The following properties of the ideal semantics hold (Theorem 2.1):
(i) Every abstract argumentation framework admits a unique maximal ideal set of arguments.
(ii) The maximal ideal set of arguments is complete.
(iii) The maximal ideal set of arguments is a superset of the grounded set and is a subset of the intersection of all preferred sets.
(iv) If the intersection of all preferred sets is admissible, then it coincides with the maximal ideal set.
… Concretely, assumption-based argumentation frameworks are concrete instances of abstract argumentation frameworks where arguments in Arg are defined as deductions from assumptions in an underlying logic, viewed as a deductive system, and where attack is defined in terms of a notion of contrary.
2.3, A deductive system is a pair (L, R) where
- L is a formal language consisting of countably many sentences, and
- R is a countable set of inference rules of the form alpha1, …, alphaN / alpha.
alpha (a member of L) is called the conclusion of the inference rule, alpha1, …, alphaN (also members of L) are called the premises of the inference rule and n>=0.
If n=0, then the inference rule represents an axiom. A deductive system does not distinguish between domain-independent axioms/rules, which belong to the specification of the logic, and domain-dependent axioms/rules which represent a background theory.
2.4, Given a selection function f, a (backward) deduction of a conclusion alpha based on (or supported by) a set of premises P is a sequence of multi-sets S1, …, Sm, where S1 = {alpha}, Sm = {P}, and… Each Si is a step in the deduction.
Deductions are the basis for the construction of arguments in assumption-based argumentation frameworks, but to obtain an argument from a backward deduction we restrict the premises to ones that are acceptable as assumptions. Moreover, to specify when one argument attacks another, we need to determine when a sentence is the contrary of an assumption…
2.5, An assumption-based argumentation framework is a tuple (L, R, A, ~) where
- (L, R) is a deductive system.
- A (a subset of L, and not equal to {}) is the set of candidate assumptions.
- If alpha is in the set A, then there is no inference rule of the form ‘alpha <- alpha1, …, alphaN’ in R.
- ~ is a (total) mapping from A into L. ~alpha is the contrary of alpha.
2.6, An argument ‘A |- alpha’ is a deduction of alpha whose premises A are all assumptions (of the set of candidate assumptions).
Given an argument ‘a’ of the form ‘A |- alpha’ we say that a is based upon A.
The notation ‘A |- alpha’ encapsulates the essence of an argument, by focusing attention on its set of assumptions A and its conclusion alpha…
2.7 … the only way to attack an argument is to attack one of its assumptions…
… the abstract framework AF corresponding to an assumption-based argumentation framework ABF is constructed as follows…
… “rebuttal” attacks can be reduced to the “undermining” attacks of assumption-based argumentation frameworks.
2.8, Refined definitions where sets of arguments are replaced by sets of assumptions underlying arguments:
- A set of assumptions A attacks a set of assumptions B iff there exists an argument A’ |- alpha such that A’ is a subset of A and ~alpha is in B.
- A set of assumptions A is admissible iff A does not attack itself and A attacks every set of assumptions B that attacks A.
- A set of assumptions A is preferred iff it is maximally admissible.
- A set of assumptions A is complete iff it is admissible and contains all assumptions x such that A attacks all attacks against {x}.
- A set of assumptions A is grounded iff it is minimally complete.
- A set of assumptions A is ideal iff A is admissible and it is contained in every preferred set of assumptions.
2.9, Let (L, R, A, ~) be an assumption-based argumentation framework and let alpha be in L. Then alpha is an admissible/grounded/ideal belief iff there exists an argument A |- alpha such that A is a subset of an admissible/grounded/ideal set of assumptions.
(Theorem 2.2) Let ABF be an assumption-based argumentation framework, and AF the abstract argumentation framework equivalent to it.
(i) If a set of assumptions A is admissible/grounded/ideal wrt ABF, then the union of all arguments supported by any subset of A is admissible/grounded/ideal wrt AF.
(ii) The union of all sets of assumptions supporting the arguments in an admissible/grounded/ideal set of arguments wrt AF is admissible/grounded/ideal wrt ABF.
3, Computing ideal arguments for abstract argumentation
Ideal sets of arguments can be computed incrementally, in defence of a given, desired argument, by means of admissible dispute trees…
In general, dispute trees can be seen as a way of generating a winning strategy for a proponent to win a dispute against an opponent. The proponent starts by putting forward an initial argument, and then the proponent and the opponent alternate in attacking each other’s previously presented arguments…
3.1, A dispute tree for an initial argument a is a (possibly) infinite tree T such that…
The set of all arguments belonging to the proponent nodes in T is called the defence set of T.
3.2, A dispute tree T is admissible iff no argument labels both a proponent and an opponent node.
(Theorem 3.1) Any dispute tree that has no infinitely long branches is an admissible dispute tree.
(Theorem 3.2) (i) If T is an admissible dispute tree for an argument a then the defence set of T is admissible. (ii) If a is an argument and a is in A where A is an admissible set of arguments then there exists an admissible dispute tree for a with defence set A’ such that A’ is a subset of A and A’ is admissible.
(Theorem 3.3) An admissible set of arguments S is ideal iff for each argument a attacking S there exists no admissible set of arguments containing a.
3.3, An abstract admissible dispute tree T is ideal iff for no opponent node O in T there exists an admissible tree with root O.
(Theorem 3.4) (i) If T is an ideal dispute tree for an argument a then the defence set of T is ideal. (ii) If ‘a’ is an argument and ‘a’ is in A where A is an ideal set of arguments then there exists an ideal dispute tree for ‘a’ with defence set A’ and A’ is a subset of A.
No comments:
Post a Comment