An analysis of formal inter-agent dialogues.
This paper studies argumentation-based dialogues between agents. It defines a set of locutions by which agents can trade arguments, a set of agent attitudes which relate what arguments an agent can build and what locutions it can make, and a set of protocols by which dialogues can be carried out. The paper then considers some properties of dialogues under the protocols, in particular termination and complexity, and shows how these relate to the agent attitudes.
INTRODUCTION
When building multi-agent systems, we take for granted
the fact that the agents which make up the system will need
to communicate. They need to communicate in order to
resolve dierences of opinion and con
icts of interest, work
together to resolve dilemmas or nd proofs, or simply to
inform each other of pertinent facts. Many of these communication
requirements cannot be fullled by the exchange of
single messages. Instead, the agents concerned need to be
able to exchange a sequence of messages which all bear upon
the same subject. In other words they need the ability to
engage in dialogues. As a result of this requirement, there
has been much work on providing agents with the ability
to hold such dialogues. Recently some of this work has considered
argument-based approaches to dialogue, for example
the work by Dignum et al. [5], Parsons and Jennings [15],
Reed [18], Schroeder et al. [19] and Sycara [20].
Reed's work built on an in
uential model of human dialogues
due to argumentation theorists Doug Walton and
Krabbe [21], and we also take their dialogue typology
as our starting point. Walton and Krabbe set out to analyze
the concept of commitment in dialogue, so as to \pro-
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Copyright 2000 ACM 1-58113-480-0/02/0007 .$5.00
vide conceptual tools for the theory of argumentation" [21,
page ix]. This led to a focus on persuasion dialogues, and
their work presents formal models for such dialogues. In
attempting this task, they recognized the need for a characterization
of dialogues, and so they present a broad typology
for inter-personal dialogue. They make no claims for its
comprehensiveness.
Their categorization identies six primary types of dialogues
and three mixed types. The categorization is based
upon: rstly, what information the participants each have at
the commencement of the dialogue (with regard to the topic
of discussion); secondly, what goals the individual participants
and, thirdly, what goals are shared by the partic-
ipants, goals we may view as those of the dialogue itself. As
dened by Walton and Krabbe, the three types of dialogue
we consider here are:
Information-Seeking Dialogues: One participant seeks
the answer to some question(s) from another partic-
ipant, who is believed by the rst to know the an-
swer(s).
Inquiry Dialogues: The participants collaborate to answer
some question or questions whose answers are not
known to any one participant.
Persuasion Dialogues: One party seeks to persuade another
party to adopt a belief or point-of-view he or she
does not currently hold. These dialogues begin with
one party supporting a particular statement which the
other party to the dialogue does not, and the rst seeks
to convince the second to adopt the proposition. The
second party may not share this objective.
In previous work [2], we began to investigate how these
dierent types of dialogue can be captured using a formal
model of argumentation. Here we extend this work, examining
some of the possible forms of information seeking, inquiry
and persuasion dialogues which are possible, and identifying
how the properties of these dialogues depend upon
the properties of the agents engaging in them.
Note that, despite the fact that the types of dialogue we
are considering are drawn from the analysis of human dia-
logues, we are only concerned here with dialogues between
articial agents. Unlike [9] for example, we choose to focus
in this way in order to simplify our task|doing this allows
us to deal with articial languages and avoid much of the
complexity inherent in natural language dialogues.
2. BACKGROUND
In this section we brie
y introduce the formal system of
argumentation which forms the backbone of our approach.
This is inspired by the work of Dung [6] but goes further
in dealing with preferences between arguments. Further details
are available in [1] We start with a possibly inconsistent
knowledge base  with no deductive closure. We assume
contains formulas of a propositional langage L. ' stands for
classical inference and  for logical equivalence. An argument
is a proposition and the set of formulae from which it
can be inferred:
Definition 1. An argument is a pair
h is a formula of L and H a subset of  such that:
1. H is consistent;
2.
3. H is minimal, so no subset of H satisfying both 1. and
2. exists.
H is called the support of A, written
h is the conclusion of A written
We talk of h being supported by the argument (H ; h)
In general, since  is inconsistent, arguments in A(),
the set of all arguments which can be made from , will
con
ict, and we make this idea precise with the notion of
undercutting:
Definition 2. Let A1 and A2 be two arguments of A().
undercuts
clusion(A1 ).
In other words, an argument is undercut if and only if there
is another argument which has as its conclusion the negation
of an element of the support for the rst argument.
To capture the fact that some facts are more strongly believed
1 we assume that any set of facts has a preference order
over it. We suppose that this ordering derives from the fact
that the knowledge base  is stratied into non-overlapping
sets such that facts in  i are all equally preferred
and are more preferred than those in  j where j > i .
The preference level of a nonempty subset H of , level(H ),
is the number of the highest numbered layer which has a
member in H .
Definition 3. Let A1 and A2 be two arguments in A().
is preferred to A2 according to Pref i level(Support(A1
level(Support(A2 )).
By  Pref we denote the strict pre-order associated with
. If A1 is preferred to A2 , we say that A1 is stronger
than A2 2 . We can now dene the argumentation system we
will use:
Definition 4. An argumentation system (AS) is a triple
A() is a set of the arguments built from ,
1 Here we only deal with beliefs, though the approach can also handle
desires and intentions as in [16] and could be extended to cope with
other mental attitudes.
We acknowledge that this model of preferences is rather restrictive
and in the future intend to work to relax it.
Undercut is a binary relation representing defeat relationship
between arguments, Undercut  A()A(),
and
Pref is a (partial or complete) preordering on A()
A().
The preference order makes it possible to distinguish dier-
ent types of relation between arguments:
Definition 5. Let A1 , A2 be two arguments of A().
If A2 undercuts A1 then A1 defends itself against A2
Otherwise, A1 does not defend itself.
A set of arguments S defends A i: 8 B undercuts A
and A does not defend itself against B then 9 C 2 S
such that C undercuts B and B does not defend itself
against C .
Henceforth, CUndercut;Pref will gather all non-undercut arguments
and arguments defending themselves against all
their undercutting arguments. In [1], it was shown that the
set S of acceptable arguments of the argumentation system
is the least xpoint of a function F :
defended by Sg
Definition 6. The set of acceptable arguments for an
argumentation system hA(); Undercut ; Pref i is:
F i0 (;)
An argument is acceptable if it is a member of the acceptable
set.
An acceptable argument is one which is, in some sense,
proven since all the arguments which might undermine it
are themselves undermined.
3. LOCUTIONS
As in our previous work [2, 4], agents use the argumentation
mechanism described above as a basis for their reasoning
and their dialogues. Agents decide what they themselves
know by determining which propositions they have acceptable
arguments for. They trade propositions for which they
have acceptable arguments, and accept propositions put forward
by other agents if they nd that the arguments are
acceptable. The exact locutions and the way that they are
exchanged dene a formal dialogue game which agents engage
in.
Dialogues are assumed to take place between two agents,
P and C 3 . Each agent has a knowledge base, P and C
respectively, containing their beliefs. In addition, each agent
has a further knowledge base, accessible to both agents, containing
commitments made in the dialogue. These commitment
stores are denoted CS (P) and CS (C ) respectively,
and in this dialogue system (unlike that of [4] for exam-
ple) an agent's commitment store is just a subset of its
knowledge base. Note that the union of the commitment
3 The names stemming from the study of persuasion dialogues|P
argues \pro" some proposition, and C argues \con".
stores can be viewed as the state of the dialogue at a given
time. Each agent has access to their own private knowledge
base and both commitment stores. Thus P can make use of
and C can make use of
All the knowledge bases contain propositional formulas
and are not closed under deduction, and all are stratied
according to degree of belief as discussed above. Here we
assume that these degrees of belief are static and that both
the players agree on them, though it is possible [3] to combine
dierent sets of preferences, and it is also possible to
have agents modify their beliefs on the basis of the reliability
of their acquaintances [14].
With this background, we can present the set of dialogue
moves that we will use. For each move, we give what we
call rationality rules and update rules. These are based on
the rules suggested by [11]. The rationality rules specify the
preconditions for playing the move. Unlike those in [2, 4]
these are not absolute, but are dened in terms of the agent
attitudes discussed in Section 4. The update rules specify
how commitment stores are modied by the move.
In the following, player P adresses the move to player C.
We start with the assertion of facts:
assert(p). where p is a propositional formula.
rationality the usual assertion condition for the
agent.
update CS i
Here p can be any propositional formula, as well as the special
character U , discussed below.
assert(S). where S is a set of formulas representing the
support of an argument.
rationality the usual assertion condition for the
agent.
update CS i
The counterpart of these moves are the acceptance moves:
accept(p). p is a propositional formula.
rationality The usual acceptance condition for
the agent.
update CS i
accept(S). S is a set of propositional formulas.
rationality the usual acceptance condition for
every s 2 S .
update CS i
There are also moves which allow questions to be posed.
4 Which, of course, is the same as hA(P [ CS(P) [
challenge(p). where p is a propositional formula.
rationality
update CS i
A challenge is a means of making the other player explicitly
state the argument supporting a proposition. In contrast, a
question can be used to query the other player about any
proposition.
question(p). where p is a propositional formula.
rationality
update CS i
We refer to this set of moves as the set M 0
DC since they are
a variation on the set MDC from [2]|the main dierence
from the latter is that there are no \dialogue conditions".
Instead we explicitly dene the protocol for each type of
dialogue in Section 5. The locutions in M 0
DC are similar
to those discussed in legal reasoning [7, 17] and it should
be noted that there is no retract locution. Note that these
locutions are ones used within dialogues. Further locutions
such as those discussed in [13] would be required to frame
dialogues.
4. AGENT ATTITUDES
One of the main aims of this paper is to explore how
the kinds of dialogue in which agents engage depends upon
features of the agents themselves (as opposed, for instance,
to the kind of dialogue in which the agents are engaged or
the information in the knowledge-bases of the agents). In
particular, we are interested in the eect of these features
on the way in which agents determine what locutions can
be made within the connes of a given dialogue protocol
through the application of diering rationality conditions.
As is clear from the denition of the locutions, there are
two dierent kinds of rationality conditions|one which determines
if something may be asserted, and another which
determines whether something can be accepted. The former
we call assertion conditions, the latter we call acceptance
conditions and talk of agents having dierent attitudes
which relate to particular conditions.
Definition 7. An agent may have one of two assertion
attitudes.
a condent agent can assert any proposition p for which
it can construct an argument (S ; p).
a thoughtful agent can assert any proposition p for
which it can construct an acceptable argument (S ; p).
Thus a thoughtful agent will only put forward propositions
which, so far as it knows, are correct. A condent agent
won't stop to check that this is the case. It might seem
worthwhile also dening what we might call a thoughtless
agent, which can assert any proposition which is either in,
or may be inferred from, its knowledge base, but it is easy
to show that:
Proposition 1. The set of non-trivial propositions which
can be asserted by a thoughtless agent using an argumentation
system exactly the set which
can be asserted by a condent agent using the same argumentation
system.
Proof. Consider a condent agent G and a thoughtless
agent H with the same argumentation system. G can assert
exactly those propositions that it has an argument for. So
by Denition 1 it can assert any p which it can infer from a
minimal consistent subset of , including all the propositions
q in  (these are the conclusions of the arguments (fqg; q)).
H can assert any proposition which is either in  (which will
be exactly the same as those G can assert) or can be infered
from it. Those propositions which are non-trivial will be
those that can be inferred from a consistent subset of .
These latter will clearly be ones for which an argument can
be built, and so exactly those that can be asserted by G.
Thus the idea of a thoughtless agent adds nothing to our
classication.
At the risk of further overloading some well-used terms
we can dene acceptance conditions:
Definition 8. An agent may have one of three acceptance
attitudes.
a credulous agent can accept any proposition p if it is
backed by an argument.
a cautious agent can accept any proposition p if it is
unable to construct a stronger argument for :p.
a skeptical agent can accept any proposition p if there
is an acceptable argument for p.
With a pair of agents that are thoughtful and skeptical, we
recover the rationality conditions of the dialogue system in
[2].
skeptical agents are more demanding than credulous
ones in terms of the conditions they put on accepting
information. Typically, a skeptical agent which is presented
with an assertion of p will challenge p to obtain the argument
for it, and then validate that this argument is acceptable
given what it knows. We can consider even more
demanding agents. For example, we can imagine a querelous
agent which will only accept a proposition if it can not only
validate the acceptability of the argument for that propo-
sition, but also the acceptability of arguments for all the
propositions in that argument, and all the propositions in
those arguments, and so on.
However, it turns out that:
Proposition 2. The set of propositions acceptable to a
skeptical agent using an argumentation system hA(); Undercut ;
exactly the same as the set of propositions acceptable
to a querelous agent using the same argumentation system.
Proof. Consider a thoughtful agent G and a querelous
agent H with the same argumentation system. By denition,
G can accept any proposition p whose support S is either
not attacked by any argument which is built from , or is
defended by an argument which is part of the acceptable set
of A(). In other words, G will only accept p if all the s 2
are themselves supported by acceptable arguments (which
might just be (fsg; s) if there is no argument for :s). This
is exactly the set of conditions under which H will accept
p.
In other words once we require an argument to be accept-
able, we also require that any proposition which is part of
the support for that argument is also acceptable. Thus the
notion of a querelous agent adds nothing to our classica-
tion.
5. DIALOGUE TYPES
With the agent attitudes specied, we can begin to look
at dierent types of dialogue in detail giving protocols for
These protocols are intentionally simple, to make it
possible to provide a detailed analysis of them as a baseline
from which more complex protocols can be examined. An
important feature common to all these protocols is that no
agent is allowed to repeat a locution. If this prevents the
agent from making any locution, the dialogue terminates.
5.1 Information-seeking
In an information seeking dialogue, one participant seeks
the answer to some question from another participant. If the
information seeker is agent A and the other agent is B , then
we can dene the protocol IS for an information seeking
dialogue about a proposition p as follows:
1. A asks question(p).
2. B replies with either assert(p), assert(:p), or assert(U).
Which will depend upon the contents of its knowledge-base
and its assertion attitude. U indicates that, for
whatever reason B cannot give an answer.
3. A either accepts B 's response, if its acceptance attitude
allows, or challenges. U cannot be challenged and as
soon as it is asserted, the dialogue terminates without
the question being resolved.
4. B replies to a challenge with an assert(S ), where S
is the support of an argument for the last proposition
challenged by A.
5. Go to 3 for each proposition in S in turn.
Note that A accepts whenever possible, only being able to
challenge when unable to accept|\only" in the sense of only
being able to challenge then and challenge being the only
locution other than accept that it is allowed to make. More
exible dialogue protocols are allowed, as in [2], but at the
cost of possibly running forever 5 .
There are a number of interesting properties that we can
prove about this protocol, some of which hold whatever acceptance
and assertion attitudes the agents have, and some
of which are more specic. We have:
Proposition 3. When subject to challenge(p) for any p
it has asserted, a condent or thoughtful agent G can always
respond.
Proof. In order to respond to a challenge(p), the agent
has to be able to produce an argument (S ; p). Since, by
denition, both condent and thoughtful agents only assert
propositions for which they have arguments, these arguments
can clearly be produced if required. This holds even for the
propositions in S . For a proposition to be in S by Deni-
tion 1 it must be part of a consistent, minimal subset of G
which entails p. Any such proposition q is the conclusion
of an argument (fqg; q) and this argument is easily generated

This rst result ensures that step 4 can always follow from
step 3, and the dialogue will not get stuck at that point.
5 The protocol in [2] allows an agent to interject with question(p) for
any p at virtually any point, allowing the dialogue to be llibusted
by issuing endless questions about arbitrary formulae.
It also leads to another result|since with this protocol our
agents only put forward propositions which are backed by
arguments, a credulous agent would have to accept any pro-
postion asserted by an agent:
Proposition 4. A credulous agent G operating under protocol
IS will always accept a proposition asserted by a condent
or thoughtful agent H .
Proof. When H asserts p, G will initially challenge it
(for p to be acceptable it must be backed by an argument,
but no argument has been presented by H and if G had an
argument for p it would not have engaged in the information
seeking dialogue). By Proposition 3, H will always be able
to generate such an argument, and by the denition of its
acceptance condition and the protocol IS, G will then accept
it.
This result is crucial in showing that if A is a credulous
agent, then the dialogue will always terminate, but what if
it is more demanding? Well, it turns out that:
Proposition 5. An information-seeking dialogue under
protocol IS between a credulous, cautious or skeptical agent
G and a condent or thoughtful agent H will always terminate

Proof. At step 2. of the protocol H either replies with
p, :p or U. If it is U, the dialogue terminates. G then
considers p. If G is creduous, then by Corollary 4, G will
accept the proposition and the dialogue will terminate.
If G is cautious, then at step 3, it will either accept p, or
have an argument for :p. In the former case the dialogue
terminates immediately. In the latter case G will challenge
p and by Proposition 3 receive the support S . If G doesn't
have an argument against any of the s 2 S , then they will
be accepted, but this will not make G accept p. The only locution
that G could utter is challenge(p), but it is prevented
from doing this, and the dialogue terminates. If G does have
an argument for the negation of any of the s 2 S , then it
will challenge them. As in the proof of Proposition 3 this will
produce an argument (fsg; s) from H , and G will not be able
to accept this. It also cannot challenge this since this would
repeat its challenge of s, and the dialogue will terminate.
If G is skeptical, then the process will be very similar. At
step 3, G will not be able to accept p (for the same kind of
reason as in the proof of Proposition 4), so will challenge it
and receive the support S . This support may mean that G
has an acceptable argument for p in which case the dialogue
terminates. If this argument is not acceptable, then G will
challenge the s 2 S for which it has an undercutting argu-
ment. Again, this will produce an argument (fsg; s) from
H which won't make the argument for p acceptable. G cannot
make any further locutions, and the dialogue will terminate

While this result is a good one, because of the guarantee of
termination, the proof illustrates a limitation of the dialogue
protocol.
Whether G is skeptical or cautious, it will either immediately
accept p or never accept it whatever H says. That
is H will never persuade G to change its mind. The reason
for this is that the dialogue protocol neither makes G assert
into CS(G) the grounds for not accepting p (thus giving H
the opportunity to attack the relevant argument), nor gives
H the chance to do anything other than assert arguments
which support p.
This position can be justied since IS is intended only
to capture information seeking. If we want H to be able
to persuade G, then the agents are engaging in a persuasion
dialogue, albeit one that is embedded in an information
seeking dialogue as in [13], and this case is thus dealt with
below.
5.2 Inquiry
In an inquiry dialogue, the participants collaborate to answer
some question whose answer is not known to either.
There are a number of ways in which one might construct
an inquiry dialogue (for example see [12]). Here we present
one simple possibility. We assume that two agents A and
have already agreed to engage in an inquiry about some
proposition p by some control dialogue as suggested in [13],
and from this point can adopt the following protocol I:
1. A asserts q ! p for some q or U .
2. B accepts q ! p if its acceptance attitude allows, or
challenges it.
3. A replies to a challenge with an assert(S ), where S
is the support of an argument for the last proposition
challenged by B .
4. Goto 2 for each proposition s 2 S in turn, replacing
5. B asserts q , or r ! q for some r , or U .
6. If A(CS (A)[CS(B)) includes an argument for p which
is acceptable to both agents, then the dialogue terminates
successfully.
7. Go to 5, reversing the roles of A and B and substituting
r for q and some t for r .
This protocol is basically a series of implied IS dialogues.
First A asks \do you know of anything which would imply
were it known?". B replies with one, or the dialogue
terminates with U . If A accepts the implication, B asks
\now, do you know q , or any r which would imply q were
it known?", and the process repeats until either the process
bottoms out in a proposition which both agents agree on, or
there is no new implication to add to the chain. Because of
this structure, it is easy to show that:
Proposition 6. An inquiry dialogue I between two agents
G and H with any acceptance and assertion attitudes will
terminate.
Proof. The dialogue starts with an implied IS dialogue.
By Proposition 5 this dialogue will terminate. If it terminates
with a result other than U, then it is followed with
a second IS dialogue in which the roles of the agents are
reversed. Again by Proposition 5 this dialogue will termi-
nate, possibly with a proof that is acceptable to both agents.
If this second dialogue does not end with a proof or a U,
then it is followed with another IS dialogue in which the
roles of the agents are again reversed. This third dialogue
runs just like the second. The iteration will continue until
either one of the agents responds with a U, or the chain of
implications is ended. One or other will happen since the
agents can only build a nite number of arguments (since
arguments have supports which are minimal consistent sets
of the nite knowledge base), and agents are not allowed to
repeat themselves. When the iteration terminates, so does
the dialogue.
However, it is also true that this rather rigid protocol may
prevent a proof being found even though one is available to
the agents if they were to make a dierent set of assertions.
More precisely, we have:
Proposition 7. Two agents G and H which engage in
a inquiry dialogue for p, using protocol I, may nd the dialogue
terminates unsuccessfully even when A(G [H ) provides
an argument p which both agents would be able to accept

Proof. Consider G has
has frg. Clearly together both agents can produce
p), and this will be acceptable to both agents no
matter their acceptance attitude, but if G starts by asserting
the agents will never nd this proof.
Of course, it is possible to design protocols which don't suer
from this problem, by allowing an agent to assert all the r !
q which are relevant at any point in the dialogue (turning the
dialogue into a breadth-rst search for a proof rather than
a depth rst one) or by allowing the dialogue to backtrack.
Another thing to note is that, in contrast to the information
seeking dialogue, in inquiry dialogues the relationship
between the agents is symmetrical in the sense that both are
asserting and accepting arguments. Thus both an agent's
assertion attitude and acceptance attitude come into play.
As a result, in the case of a condent but skeptical agent, it
is possible for an agent to assert an argument that it would
not nd acceptable itself. This might seem odd at rst, but
on re
ection seems more reasonable (consider the kind of inquiry
dialogue one might have with a child), not least when
one considers that a condent assertion attitude can be seen
as one which responds to resource limitations|assert something
that seems reasonable and only look to back it up if
there is a reason (its unacceptability to another agent) which
suggests that it is problematic.
5.3 Persuasion
In a persuasion dialogue, one party seeks to persuade another
party to adopt a belief or point-of-view he or she does
not currently hold. The dialogue game DC, on which the
moves in [2] are based, is fundamentally a persuasion game,
so the protocol below results in games which are very like
those described in [2]. This protocol, P, is as follows, where
agent A is trying to persuade agent B to accept p.
1. A asserts p.
2. B accepts p if its acceptance attitude allows, if not B
asserts :p if it is allowed to, or otherwise challenges
p.
3. If B asserts :p, then goto 2 with the roles of the agents
reversed and :p in place of p.
4. If B has challenged, then:
(a) A asserts S , the support for
(b) Goto 2 for each s 2 S in turn.
If at any point an agent cannot make the indicated move,
it has to concede the dialogue game. If A concedes, it fails
to persuade B that p is true. If B concedes, then A has
succeeded in persuading it. An agent also concedes the game
if at any point if there are no propositions made by the other
agent that it hasn't accepted.
Once again the form of this dialogue has much in common
with inquiry dialogues. The dialogue starts as if B has asked
A if p is true, and A's response is handled in the same way
as in an inquiry unless B has a counter-argument in which
case it can assert it. This assertion is like spinning
separate IS dialogue in which A asks B if :p is true. Since
we already have a termination result for IS dialogues, it is
simple to show that:
Proposition 8. A persuasion dialogue under protocol P
between two agents G and H will always terminate.
Proof. A dialogue under P is just like an information
seeking dialogue under IS in which agents are allowed to
reply to the assertion of a proposition p with the assertion
of :p as well as the usual responses. Since we know that
a dialogue under IS always terminates, it suces to show
that the assertion of :p does not lead to non-termination.
Since the only dierence between the sub-dialogue spawned
by the assertion of :p and a IS dialogue is the possibility
of the agent to which :p is asserted asserting p in response,
then this is the only way in which non-termination can oc-
cur. However, this assertion of p is not allowed since it
would repeat the assertion that provoked the :p and so the
dialogue would terminate. Thus a P dialogue will always
terminate.
Again there is some symmetry between the agents, but there
is also a considerable asymmetry which stems from the fact
that A is eectively under a burden of proof so it has to win
the argument in order to convince B , while B just has to
fail to lose to not be convinced. Thus if A and B are both
condent-cautious and one has an argument for p and the
other has one for :p, and neither argument is stronger than
the other, despite the fact that the arguments \draw", A
will lose the exchange and B will not be convinced. This is
exactly the same kind of behaviour that is exhibited by all
persuasion dialogues in the literature.
6. COMPLEXITY OF DIALOGUES
Having examined some of the properties of the dialogues,
we consider their computational complexity. Since the protocols
are based on reasoning in logic we know that the
complexity will be high|our aim in this analysis is to establish
exactly where the complexity arises so that we can
try and reduce it,for example, as in [22], but suitable choice
of language.
To study this issue, we return to Denition 1. Given a
knowledge base , we will say there is a prima facie argument
for a particular conclusion h if  ' h, i.e., if it is
possible to prove the conclusion from the knowledge base.
The existence of a prima facie argument does not imply the
existence of a \usable" argument, however, as  may be in-
consistent. Since establishing proof in propositional logic is
co-NP-complete, we can immediately conclude:
Proposition 9. Given a knowledge base  and a conclusion
h, determining whether there is a prima facie argument
for h from  is co-NP-complete.
We will say a is a consistent prima facie argument
over  if H is a consistent subset of  and H ' h.
Determining whether or not there is a consistent prima facie
argument for some conclusion is immediately seen to be
harder.
Proposition 10. Given a knowledge base  and conclusion
h, determining whether there is a consistent prima facie
argument for h over  is  p-complete.
Proof. The following  palgorithm decides the problem:
1. Existentially guess a subset H of  together with a
valuation v for H .
2. Verify that v
3. Universally select each valuation v 0 of H , and verify
that v 0
The algorithm has two alternations, the rst being an ex-
istential, the second a universal, and so it is indeed a  palgorithm. The existential alternation involves guessing a
support for h together with a witness to the consistency of
this support. The universal alternation veries that H ! h
is valid, and so H ' h. Thus the problem is in  pTo show the problem is  p-hard, we do a reduction from
the qbf2;9 problem [10, p96]. An instance of qbf2;9 is given
by a quantied boolean formula with the following structure:
where  is a propositional logic formula over Boolean variables
. Such a formula is true if there
are values we can give to such that for all values
we can give to l , the formula  is true. Here is an
example of such a formula.
Formula (2) in fact evaluates to true. (If x1 is true, then
for all values of x2 , the overall formula is true.)
Given an instance (1) of qbf2;9 , we dene the conclusion
h to be dene the knowledge base  as
where > and ? are logical constants for truth and falsehood
respectively. Any consistent subset of  denes a consistent
partial valuation for the body of (1); variables not given a
valuation by a subset are assumed to be \don't care". We
claim that input formula (1) is true i there exists a consistent
prima facie argument for h given knowledge base .
Intuitively, in considering subsets of , we are actually examining
all values that may be assigned to the existentially
quantied variables . Since the reduction is clearly
polynomial time, we are done.
Now, knowing that there exists a consistent prima facie
argument for conclusion h over  implies the existence of a
minimal argument for h over  (although it does not tell us
what this minimal argument is). We can thus conclude:
Corollary 1. Given a knowledge base  and conclusion
h, determining whether there is an argument for h (i.e., a
minimal consistent prima facie argument for h | Deni-
tion 1) over  is  p-complete.
The next obvious question is as follows: given (H ; h), where
h, is it minimal?
Corollary 2. Given a knowledge base  and prima facie
argument the problem of determining
whether (H ; h) is minimal is  p-complete.
Proof. For membership of  p, consider the following  palgorithm, which decides the complement of the problem:
1. Existentially select a subset H 0 of H and a valuation
2. Verify that v
3. Universally select each valuation v 0 for H 0 .
4. Verify that v 0
The algorithm contains two alternations, an existential followed
by an universal, and so is indeed a  palgorithm. The
algorithm works by guessing a subset H 0 of H , showing that
this subset is consistent, and then showing that H 0 ! h is a
tautology, so H 0 ' h. Since the complement of the problem
under consideration is in  p, and co- p=  p, it follows
that the problem is in  pTo show completeness, we reduce the qbf 2;9 to the complement
of the problem, i.e., to showing that an argument
is not minimal. If an argument (H ; h) is not minimal, then
there will exist some consistent subset H 0 of H such that
The reduction is identical to that above: we set
We then ask whether there is a consistent subset H 0 of H
such that H 0 ' h. Since we have reduced a  p-complete problem
to the complement of the problem under consideration,
it follows that the problem is  p-hard.
These results allow us to handle the complexity of dialogues
involving condent, credulous and cautious agents, which
are only interested in whether arguments can be built for
given propositions. For thoughtful and skeptical agents we
need to consider whether an argument is undercut.
Proposition 11. Given a knowledge base  and an argument
the problem of showing that (H ; h)
has an undercutter is  p-complete.
Proof. The following  palgorithm decides this problem:
1. Existentially guess (i) a subset H 0 of ; (ii) a support
to undercut; and (iii) a valuation v .
2. Verify that v
3. Universally select each valuation v 0 of H 0 .
4. Verify that (i) v 0
For hardness, there is a straightforward reduction from the
qbf 2;9 problem, essentially identical to the reductions given
in proofs above | we therefore omit it.
As a corollary, the problem of showing that (H ; h) has no
undercutter is  p-complete.
These results are sucient to demonstrate the worst-case
intractability of argumentation-based approaches for skepi-
cal and thoughtful agents using propositional logic. They
thus motivate the investigation of the behaviour of agents
with dierent attitudes and the use of other logics. These
matters are explored in an extended version of this paper.
7. CONCLUSIONS
This paper has examined three types of argumentation-based
dialogue between agents|information seeking, inquiry
and persuasion, from the typology of [21]|dening a precise
protocol for each and examining some important properties
of that protocol. In particular we have shown that each protocol
leads to dialogues that are guaranteed to terminate,
and we have considered some aspects of the complexity of
these dialogues. The exact form of the dialogues depends on
what messages agents send and how they respond to messages
they receive. This aspect of the dialogue is not specied
by the protocol, but by some decision-making apparatus
in the agent. Here we have considered this decision to be
determined by the agents' attitude, and we have shown how
this attitude aects their behaviour in the dialogues they
engage in.
Both of these aspects extend previous work in this eld. In
particular, they extend the work of [2] by precisely dening a
set of protocols (albeit quite rigid ones) and a range of agent
attitudes|in [2] only one protocol, for persuasion, and only
one attitude, broadly thoughtful-skeptical, were considered.
More work, of course, remains to be done in this area.
Particularly important is determining the relationship between
the locutions we use in these dialogues and those of
agent communication languages such as the FIPA ACL, examining
the eect of adding new locutions (such as retract)
to the language, and identifying additional properties of the
dialogues (such as whether the order in which arguments
are made aects the outcome of the dialogue). We are currently
investigating these matters along with further dialogue
types, more complex kinds of the dialogue types studied
here, such planning dialogues [8], and additional complexity
issues (including the eect of languages other than
propositional logic).

Acknowledgments

This work was partly funded by the EU funded Project IST-
1999-10948.
8.



--R

On the acceptability of arguments in preference-based argumentation framework
Modelling dialogues using argumentation.
Agent dialogues with con icting preferences.


On the acceptability of arguments and its fundamental role in nonmonotonic reasoning
The pleadings game.
The evolution of sharedplans.

A catalog of complexity classes.
A generic framework for dialogue game implementation.
Risk agoras: Dialectical argumentation for scienti
Games that agents play: A formal framework for dialogues between autonomous agents.
An approach to using degrees of belief in BDI agents.
Negotiation through argumentation
Agents that reason and negotiate by arguing.
Relating protocols for dynamic dispute with logics for defeasible argumentation.
Dialogue frames in agent communications.
Ultima ratio: should Hamlet kill Claudius.
Planning other agents' plans.
Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning.
Languages for negotiation.
--TR
Attention, intentions, and the structure of discourse
A catalog of complexity classes
The Pleadings Game
On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and <italic>n</italic>-person games
Ultima ratio (poster)
Games That Agents Play
Risk Agoras
Agent Theory for Team Formation by Dialogue
Agent Dialogues with Conflicting Preferences
Dialogue Frames in Agent Communication
Modeling Dialogues Using Argumentation

--CTR
Pieter Dijkstra , Floris Bex , Henry Prakken , Kees De Vey Mestdagh, Towards a multi-agent system for regulated information exchange in crime investigations, Artificial Intelligence and Law, v.13 n.1, p.133-151, January 2005
Pieter Dijkstra , Henry Prakken , Kees de Vey Mestdagh, An implementation of norm-based agent negotiation, Proceedings of the 11th international conference on Artificial intelligence and law, June 04-08, 2007, Stanford, California
Laurent Perrussel , Jean-Marc Thvenin , Thomas Meyer, Mutual enrichment through nested belief change, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
Simon Parsons , Michael Wooldridge , Leila Amgoud, On the outcomes of formal inter-agent dialogues, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
Yuqing Tang , Simon Parsons, Argumentation-based dialogues for deliberation, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
Eva Cogan , Simon Parsons , Peter McBurney, What kind of argument are we going to have today?, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
Paul E. Dunne , Peter McBurney, Optimal utterances in dialogue protocols, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
Henry Prakken, Formal systems for persuasion dialogue, The Knowledge Engineering Review, v.21 n.2, p.163-188, June 2006
Pietro Baroni , Massimiliano Giacomin , Giovanni Guida, Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems, Artificial Intelligence, v.165 n.2, p.187-259, July 2005
N. Maudet , B. Chaib-Draa, Commitment-based and dialogue-game-based protocols: new trends in agent communication languages, The Knowledge Engineering Review, v.17 n.2, p.157-179, June 2002
Iyad Rahwan , Sarvapali D. Ramchurn , Nicholas R. Jennings , Peter Mcburney , Simon Parsons , Liz Sonenberg, Argumentation-based negotiation, The Knowledge Engineering Review, v.18 n.4, p.343-375, December
agent communication;argumentation;dialogue games