Transcript Dung Argumentation and AGM Belief Revision

Dung-style Argumentation and
AGM-style Belief Revision
Guido Boella, Celia da Costa
Pereira, Andrea Tettamanzi and
Leon van der Torre.
Position Statement
Formal study of Dung-style argumentation and
AGM-style belief revision is useful
Reinstatement in argumentation can formally be
related to recovery-related principles in revision
This has been suggested also by Guillermo
Simari, Tony Hunter, Fabio Paglieri, and others
This presentation explains the problem, all
comments or references are highly appreciated.
7/16/2015
ARGMAS 2008
2
Dung and AGM
Formal foundations of both theories
E.g., reinstatement and recovery
Argument revision
E.g., politics: we should increase taxes (for the rich)
Arguing about revision
E.g., you should believe in God, given Pascal’s wager
Strategic argumentation
E.g., use conventional wisdom to persuade
Thus, a common framework is useful
7/16/2015
ARGMAS 2008
3
Dung – Non-Monotonic Logic - AGM
Dung – Non-monotonic logic
Explanatory non-monotonic logic
Non-monotonic logic – AGM
Shoham – KLM tradition
“Relating two kinds of
NML is open problem”

7/16/2015
ARGMAS 2008
4
The Intuition: Dung and AGM are Related
Dung’s reinstatement
If  attacked by  &  attacked by , then  reinstated
AGM recovery, Darwiche and Pearl, etc
If p 2 K , then (K-p)+p = K
DW1: If q ² p, then (K*p)*q = K*q
DW2: If q ² : p, then (K*p)*q = K*q
DW3: If p 2 K*q, then p 2 (K*p)*q
DW4: If : p 2 K*q, then : p 2 (K*p)*q
In this presentation, we focus on DW2
7/16/2015
ARGMAS 2008
5
The Problem: How to Formalize Relation?
 Use of arguments / propositions
 Propositional argumentation
 In Dung’s approach, reinstatement is built in
 Take a more general theory, like dominance theory
 “The dominance relation need not generally be transitive and may even
contain cycles. This makes that the common concept of maximality or
optimality is no longer tenable with respect to the dominance relation and
new concepts have to be developed to take over its function of singling
out elements that are in some sense primary. Von Neumann and
Morgenstern considered this phenomenon as one of the most
fundamental problems the mathematical social sciences have to cope
with (see von Neumann and Morgenstern, 1947, Ch. 1).“ BH08
 No dynamics in argumentation / dominance
 Dynamics in dialogue proof theories
7/16/2015
ARGMAS 2008
6
Baroni and Giacomin, AIJ 2007
Framework for the evaluation of extensionbased argumentation semantics.
Solves the latter two problems:
Definitions of reinstatement in this framework
Dynamics, because A = arguments produced by a
reasoner at a given instant of time
7/16/2015
ARGMAS 2008
7
Baroni and Giacomin, AIJ 2007
 h A,! i is Dung argumentation framework
A is finite,
``independently of the fact that the underlying
mechanism of argument generation admits the
existence of infinite sets of arguments.’’
We make the set of all arguments explicit
U is set of arguments which can be generated,
U for the universe of arguments.
7/16/2015
ARGMAS 2008
8
Baroni and Giacomin, AIJ 2007
``An extension-based argumentation semantics
is defined by specifying the criteria for deriving,
for a generic argumentation framework, a set of
extensions, where each extension represents a
set of arguments considered to be acceptable
together. Given a generic argumentation
semantics S, the set of extensions prescribed
by S for a given argumentation framework AF is
denoted as ES(AF).''
7/16/2015
ARGMAS 2008
9
A Formal Definition
 Let U be the universe of arguments.
 An acceptance function ES:U x 2UxU ->22U is
1. a partial function which is defined for each
argumentation framework h A, ! i with finite
A µ U and ! µ AxA, and
2. which maps an argumentation framework
hA,!i to sets of subsets of A: ES (hA,!i)µ 2A
 (Do we need A in argumentation framework?)
7/16/2015
ARGMAS 2008
10
Do Baroni and Giacomin extend Dung’s?
Baroni and Giacomin do not present their
framework as a generalization of Dung's,
Many papers claim to generalize Dung's,
for example with support relations, preferences,
values, nested attack relations, etc.
Implicitly, Baroni and Giacomin define
argumentation at another abstraction level.
7/16/2015
ARGMAS 2008
11
Reinstatement, [BG07, definition 15]
A semantics S satisfies the reinstatement
criterion if 8 AF 2 DS, 8 E 2 ES(AF) it holds that
(8  2 parAF() E! ) )  2 E
“Intuitively, an argument  is reinstated if its
defeaters are in turn defeated and, as a
consequence, one may assume that they
should have no effect on the justification state
of .”
7/16/2015
ARGMAS 2008
12
Weak reinstatement, definition 13+16
Given an argumentation framework AF=h A,!i, 
2 A and S µ A, we say that  is strongly
defended by S, denoted as sd(,S), iff
8 2 parAF() 9 2 S \ {}:  !  & sd(,S \ {})
A semantics S satisfies the weak reinstatement
criterion if 8 AF 2 DS, 8 E 2 ES(AF) it holds that
sd(,E) )  2 E
7/16/2015
ARGMAS 2008
13
Propositional argumentation
 We associate proposition with each argument
 prop: A ! L, where L is propositional language
 Belief set = propositions of justified arguments
 K(S) = { prop() j  2 S}
 Problems:
1. Argument extensions, unique belief set
 Solutions for non-deterministic belief revision
2. Consistency of belief set difficult to ensure
7/16/2015
ARGMAS 2008
14
Literal Argumentation
We associate with argument a set of literals
prop:U! Lit, where Lit set of literals built from atoms
8 ,  2 U, if prop() Æ prop() inconsistent,
(i.e.,  and  contain a complementary literal),
then either  attacks  or  attacks  (or both)
K(S) = { prop() j  2 S}
Property: for a set S, if each pair of S is
consistent, then S is consistent
7/16/2015
ARGMAS 2008
15
Argument Runs
 Run = Sequence of argumentation frameworks
Abstraction of dialogue among players
 Expansion based argumentation run
Only add arguments and attack relations
 Persistence of relation among arguments
Only add attack relations involving newly added argument
 New is better
Only add attacks from new arguments to older ones
 Minimal attack
New attack old argument if and only if conflicting
7/16/2015
ARGMAS 2008
16
Constructability
Constructible argumentation framework
= framework which can be reached from empty
framework in a finite number of steps
New is better leads to cycle free frameworks
 See S. Kaci, L. van der Torre and E. Weydert, On the acceptability fof
conflicting arguments. Proceedings of ECSQARU07, Springer, 2007.
7/16/2015
ARGMAS 2008
17
Lemma 1: Reinstatement ! DW2
If
reinstatement
expansion, persistence, new are better, minimality
constructible
Then
DW2: If q ² : p, then (K*p)*q = K*q
Proof sketch: extension is uniquely determined
7/16/2015
ARGMAS 2008
18
Lemma 2: DW2 ! Reinstatement
If
DW2: If q ² : p, then (K*p)*q = K*q
expansion, persistence, new are better, minimality
constructible
trivial reinstatement: if no attackers, then accepted
Then
reinstatement
7/16/2015
ARGMAS 2008
19
A Theorem and Our Research Problem
If
expansion, persistence, new are better, minimality
constructible
trivial reinstatement: if no attackers, then accepted
Then
reinstatement iff DW2: If q ² : p, then (K*p)*q = K*q
Cycle-free frameworks are not very interesting
Our problem: how to generalize this result?
7/16/2015
ARGMAS 2008
20
Generalization 1: Minimality in Attack
Suppose a new argument can attack arguments
which are not conflicting
E.g., in assumption based reasoning
Additional independence assumption:
 8 , 2 A, whether  attacks  depends only on 
and , not on the other arguments
(Compare, e.g., the language independence
principle of Baroni and Giacomin)
7/16/2015
ARGMAS 2008
21
Generalization 2: Constructability
Suppose an argumentation framework does not
have to be constructible
E.g., for general argumentation frameworks
Additional (strong) abstraction assumption:
 If an argument is not in any extension, then if we
abstract from it, then the extensions remain the same
(Compare, e.g., the directionality criterion of
Baroni and Giacomin.)
7/16/2015
ARGMAS 2008
22
Generalization 3: Constructability
Suppose a framework can contain cycles
Revise the constructability assumption:
An argumentation framework is constructed in a
proponent – opponent game (TPI)
(compare, e.g., the dialogue games of Prakken
and Vreeswijk)
7/16/2015
ARGMAS 2008
23
Other Formal Foundations?
Success postulate
7/16/2015
ARGMAS 2008
24
Argument Revision
 For example, a kid does not want to go upstairs since he is afraid of a
monster - clearly you - the father - do not believe this. you can say to him
that there is daylight (which is true), since the kid believes monsters do not
like daylight. Alternatively you can say that upstairs is safe, and the child has
to give up the argument that there are monsters (ie remove the argument).
 If his brother said there are monsters and dad says otherwise, the argument
of the father is a motivation for canceling the first argument, since dad is
more reliable (until I discover how much he cheated to me).
 Maybe if, instead, mom said to him that there are monsters - rather than his
brother - he just overshadows (it is defeated but not cancelled) the argument
pro monsters, till she adds more information.
 However the reliability issue of brother vs mother is relative and it could
become subject to another level of argumentation (like Sanjay proposes?):
one can attack the fact that the father is more reliable than the brother
(maybe the kid heard mom said so while quarreling with father)
7/16/2015
ARGMAS 2008
25
Common Framework
 Arguing about revision, strategic argumentation
 “When an agent uses an argument to persuade
another one, he must consider not only the proposition
supported by the argument, but also the overall impact
of the argument on the beliefs of the addressee.
Different arguments lead to different belief revisions by
the addressee. We propose an approach whereby the
best argument is defined as the one which is both
rational and the most appealing to the addressee.”
 G. Boella, C. da Costa Pereira, A. Tettamanzi and L/ van der Torre. Making
Others Believe What They Want. Proceedings of IFIP-AI 2008
7/16/2015
ARGMAS 2008
26
Summary
Dung reinstatement – AGM recovery
Intuition, example result for cycle free
Problem is how to generalize
Minimality, constructability: new principles needed
Other formal foundations of both theories?
Argument revision?
Arguing about revision, strategic arguing?
A common framework for Dung and AGM?
7/16/2015
ARGMAS 2008
27