Specifications for Peer-to-Peer Argumentation Dialogues
Bas Testerink and Floris J. Bex
Department of Information and Computing Sciences, Utrecht University, The Netherlands

Abstract. In this paper, we propose a generic specification framework for argumentation dialogue protocols in an open multi-agent system. The specification
framework is based on reusable elements – dialogue templates – which are realized as an open-source implementation. We provide operational semantics andshow formally how templates can be used to determine the possible dialogues.
Furthermore, for open multi-agent systems we need to be able to specify peer-topeer dialogues, where the agents themselves are in a position to know whether
their dialogue actions are legal according to the protocol without relying on central entities, institutes or middleware. We prove that all protocols that can be
specified in our framework are peer-to-peer suitable.

1

Introduction

Dialogue games attempt to capture aspects of structured, mixed-initiative communication with the aim of understanding, improving, and automatically recreating such communication. Particularly for more complex tasks such as software design discussions[7], argument-based negotiation [23], collaborative learning [17] or legal argument [22],it is imperative that the agents’ behaviour is constrained by so-called dialogue protocols, so that the agents can argue, inform, investigate and negotiate in a regulated way.
We believe that argumentation dialogue games [15] are particularly suited for more
complex dialogues, as they nicely straddle the divide between the naturalistic dialogues
from the intelligent user interface community [12] and the more rigid multi-agent communication protocols [18]. Furthermore, argumentation dialogue games allow for many
features of realistic dialogues, such as agent dialogue strategies and the construction ofunderlying argument structures, to be captured.
There are several protocol proposals for argumentation dialogue games, many ofwhich have been analysed for their formal properties (see e.g. [1, 21, 9]). The wide rangeof possible dialogue protocols has given rise to an effort to define generic, executablespecification languages for notating protocols [25, 5, 6]. The motivation behind thesegeneric specification languages is twofold. First, these specification languages allow us
to represent the syntax and update semantics of any arbitrary dialogue game we care
to define in a common language. This allows us to move away from the case-by-caseapproach common in the literature on computational argumentation and move towards
a class-of-systems approach. Second, generic specification languages allow for the development of general purpose execution engines for dialogue games (such as DGEP
[3], which has been proposed as an execution engine for DGDL [25]). Such execution
engines not only allow us to empirically analyse and compare different protocols, butalso take dialogue games out of the academic lab and deploy them in realistic, largescale settings. Unfortunately, existing specification languages either have no formal operational semantics that allow us to formally study protocols [25, 5], or they lack animplemented execution engine for handling protocol execution [6].
A more general problem of existing argumentation dialogue games in the literatureis that, from the perspective of open multi-agent systems, dialogue games are too rigid:
dialogues are mostly one-on-one where it is assumed that the participants see all thecommunication, there is a strict turntaking order and communication is instantaneous,
agents are assumed to never fail and always behave according to the protocol, and it isassumed that the internal states of the agents participating in the dialogues is known.
These assumptions do not hold in realistic systems, where different dialogues may run
in parallel, agents can only be assumed to observe the messages that they themselves
send and receive and communication is peer-to-peer rather than governed by a central
entity, institute or middleware [16, 10, 8, 3].
As a case-in-point, consider the prototype multi-agent system for the Dutch National Police that we are currently developing [4]. In this system, various agents work
together to build a case regarding internet trade fraud (e.g. scammers on eBay or fake
online stores). We have agents that interact with human users (victims, police detectives), agents that exchange information with external services (banks, trade sites) andagents that automatically combine and reason with information from these different
sources. This distributed, open, peer-to-peer multi-agent system is needed because (i)the police uses strict privacy policies that make it undesirable to centrally gather andreason with data; and (ii) not all participating agents in the system are known beforehand: for instance, the human users that file online complaints are initially unknown.
Removing the usual assumptions of argumentation dialogue games brings extra
challenges in the design of these games. Because individual agents each have theirview on a dialogue that only includes the messages they themselves sent or received,and because the agents cannot rely on a third-party or control mechanism to determine
which dialogue moves are legal, the agent itself then needs to be in a position to knowwhether its actions break protocol in order to plan a dialogue or formulate strategies.
In order for this to work, the protocols need to be peer-to-peer suitable. Take, as an
example from our implementation domain, the situation where two software agents, A
and B, are talking to a human user about one or more criminal complaints. What we do
not want is for A to make claims that contradict something B has said , as this would
make the police, as an organization, to come across as inconsistent to the human user.
If we simply specify the protocol to be ‘A may not contradict a claim that B made towards the user and vice versa’, then this is not peer-to-peer suitable. When A wants tomake a claim, then it is not guaranteed to know which messages B sent to the user, andhence whether A’s claim contradicts an earlier claim from B. For the protocol regulating the communication between A, B and the user to be peer-to-peer suitable it would
need to include explicit mechanisms to ensure that A and B are consistent (e.g. only
allow a claim to be made in the dialogue with the user of which one agent is certainthat the other agent agrees). Note that peer-to-peer suitability of a protocol implies thatthe protocol can be followed without violations by agents, but does not guarantee that
there will be no violations. Hence in open multi-agent systems where some agents arenot trusted, we may still want to realize a controlling proxy interface to check those
untrusted agents.
To summarize, we need a generic, formally underpinned framework for expressing
dialogues, protocols and the ways in which those protocols update dialogue structures.
Importantly, the protocols expressed in this framework need to be peer-to-peer suitable,that is, the protocols should allow agents to, given their view on a dialogue, determine
their legal actions themselves. Inspired by [5], we propose a specification framework for
dialogue protocols based on reusable elements called dialogue templates1 , and we showformally how templates can be used to determine the possible dialogues. We furthermore define peer-to-peer suitable protocols for dialogues between individual agents,and show that all protocols that can be specified using dialogue templates are in factpeer-to-peer suitable. Our framework includes an execution engine and is part of an
open-source multi-agent system.
The rest of this paper is organized as follows. Section 2 discusses related research.
In Section 3.1 we formalize the notion of protocol and peer-to-peer suitability. Our specification framework itself is presented in Section 3.2. Finally, in Section 4 we provide
conclusions and future work.

2

Related Work

Conversational agents have experienced a resurgence as of late, with much of the work
focusing on (spoken) language interpretation issues [12] or on dialogue learning policies for more simple recommendation or negotiation tasks [24]. However, these dialogues are lacking in formal (logical) semantics, which is needed if we want to regulate and formally verify the behaviour of agents in dialogues about more complex andinformation-rich tasks.
Among the most prominent proposals for the specification of formal protocols for
multi-agent systems is Agent UML [2, 18] which has been formally analysed withcoloured petri-nets [14, 20]. Formal semantics for these protocols investigate the properties of protocols when they are followed or how agents can interpret locutions, but toour knowledge have not been analysed for determining whether agents are guaranteed
to know whether their own behaviour violates a protocol. The work by Pitt and Mamdani [19] focuses on the agent perspective of communication and specifies protocols
using finite state machines, but does not address and analyse the protocol specifications
directly.
There have recently been various proposals for generic specification languages forargumentation dialogue protocols, such as Dialogue Interaction Diagrams (DID) [13],which can be verified with coloured Petri nets, and the Framework for Dialogical Argumentation (FDA) [6], which defines protocols in an executable logic and simulatesdialogues using finite state machines. Whilst these approaches thus allow for the specification and theoretical analysis of different argumentation dialogue protocols, they
are not suitable for peer-to-peer argumentation dialogue specifications in implemented
open multi-agent systems, for various reasons. First, no mention is made of peer-to-peer
1Black and Hunter [6] use a similar concept which they call action rules.

suitability in either approach, and hence they cannot guarantee that for a protocol designed in their respective specification language an agent can determine what the legal
moves are given its view on the dialogue. Second, both DID and FDA lack implemented
engines for execution protocols, and do not concern themselves with apects such as, forexample, connections to software agents and human-computer interfaces.
Recent work that does provide an execution engine for argumentation dialogues is
the Dialogue Game Execution Platform (DGEP) [3]. However, this execution platform
is not suited for peer-to-peer dialogues in open multi-agent systems, as it uses middleware to provide the agents participating in a dialogue the next possible legal moves,from which the agents have to pick a choice. This ‘black box’ approach makes it hard
for an individual agent to plan ahead: it has to learn a model of the black box or it has torun ‘simulations’ of dialogues on the black box (if possible) to see possible outcomesof certain strategies. The first option requires a learning phase and offers no guarantees whereas the second option will likely have to deal with an exponential blow-up of
simulations. Furthermore, DGEP uses a central knowledge base, the AIFdb [11], andprovides the agents with arguments from this central knowledge base; an agent thus
cannot use its own private knowledge base to determine which types of utterances canbe made in a dialogue. A second shortcoming of DGEP is that as its specification language, DGEP uses the dialogue game description language DGDL [25] and DGDL+[3], the latter of which is based on the dialogue templates of [5]. While DGDL(+) isvery rich and allows for the specification of many different types of dialogue protocols,
it has no formal operational semantics. Hence, the outcomes of executing a dialogue
protocol with certain knowledge bases and parameters cannot be formally checked oranalysed. In this paper we present a template-based protocol specification language inspired by [5], provide operational semantics, and show that all protocols that can be
specified in this language allow agents to determine their legal actions themselves.

3

Protocol Specification

In this section we specify our framework. We first model dialogue systems and protocols, and then define the specification of protocols through reusable dialogue templates.
3.1

Peer-to-Peer Protocols

A dialogue system is an abstract description of agents, modelled by atoms, and thelocutions, also modelled by atoms, that they may utter.
Definition 1 (Dialogue System, D). A dialogue system D is specified by (A, L), where
A and L are sets of agent and locution atoms, respectively.
Example 1 (Dialogue System). We will use the same dialogue system throughout our
examples. The example scenario is an interaction between some user and expert agent.
We will make the scenario quite simple in order to not over complicate full formal specifications of all the aspects of the scenario. We have made a demonstration of a more

advanced example publicly available2 . This demonstration contains implementation examples of the proposed framework, a dialogue among nine different agents, visual representations, and more expanded argumentation-specific aspects of dialogues such ascommitments and bookkeeping of arguments that were made. For the remainder of thispaper, our example dialogue system D is specified by (A, L) where A = {user, expert}
and L = {claim(x)|x ∈ P } ∪ {why(x)|x ∈ P } ∪ {support(x, y)|x, y ∈ P } such thatP = {p, q, r, s}. The elements of P are logical atoms, claim(x) can be read as that x
is stated to be true, why(x) can be read as a question why x was stated to be true andfinally support(x, y) can be read that x follows from y and y is true.
A dialogue system allows for dialogue events, which are the events of sending or
receiving a message. An event is specified by its type (sending/receiving), the subject(the sender/recipient), the message (a locution) and the object (the recipient/sender).
Definition 2 (Dialogue Event, e). Let D = (A, L) be a dialogue system. A dialogue
event e is specified by either s(a, l, a0 ) or r(a, l, a0 ), where a, a0 ∈ A and l ∈ L.
Example 2 (Dialogue Event). An example event for our scenario is s(expert, claim(p),user) which can be read as “The expert sends locution claim(p) to the user”. Similarly,r(user, claim(p), expert) can be read as “The user receives the locution claim(p) fromthe expert”.
Dialogue events do not need to occur in sequential order, because agents may reason
and communicate in parallel with other agents. We model a dialogue as a sequence ofsets of events (we name these sets moments). If multiple events are in the same moment,
then we interpret this as those events happening simultaneously. Non-instantaneouscommunication is captured by the constraint that a moment in which a message is received has to be preceded by some moment in the past where the message was sent.
The constraint takes into account that a message might be sent at different moments.
Therefore, a message should not be received more often than that it was sent.
Definition 3 (Dialogue, d). Let D = (A, L) be a dialogue system and E be all possible
dialogue events given D. A dialogue d = M1 ...Mk is a finite sequence of sets of events,
referred to as moments, such that for each moment Mi ⊆ E, i ∈ [1, k], if r(a, l, a0 ) ∈ Mi
then the number of moments Mj , j ∈ [1, i − 1], such that r(a, l, a0 ) ∈ Mj is less than
the number of moments Mn , n ∈ [1, i − 1], such that s(a0 , l, a) ∈ Mn .
Example 3 (Dialogue). Consider a dialogue where the expert claims p, the user asks
why the expert thinks p is true, and the expert responds with a support for p by arguing that “p because q”. This dialogue could be captured by the moments/dialogue:
M1 M2 M3 where M1 = {s(expert,claim(p), user)}, M2 = {r(user,claim(p), expert),s(user, why(p), expert)}, M3 = {r(expert, why(p), user), s(expert, support(p, q),user)}.
Consider an alternative sequence of moments M01 M02 where M01 = {s(expert,
claim(p),user), r(user, claim(p), expert)}, M02 = {r(user, claim(p), expert)}. This
is not a dialogue for two reasons: (1) the send action in moment one was simultaneously2

https://git.science.uu.nl/B.J.G.Testerink/OO2APL-P2PArgumentationDialogDemo

received, and (2) the second moment contains a receive event without there being a message that still had to be received.
A protocol specifies how a dialogue ought to be conducted. Hence we can view aprotocol as a specification that divides a set of dialogues into those dialogues that follow the protocol and those dialogues that violate it. We note that a protocol violation ina dialogue means that any extension of that dialogue is also a dialogue with a protocol
violation. This constraint is captured by requiring that if a dialogue obeys a protocol
then all its prefixes do so too (item one in Definition 4). Finally, we add a constraintthat receiving a message never violates the protocol. An agent has no control over themessages that it receives, and no control over when a sent message is received. If receiving a message would violate the protocol then the sending agent therefore potentiallycannot determine beforehand whether the arrival of the message will break protocol,and the receiving agent cannot avoid the protocol violation since it cannot prevent themessage from being received. Hence allowing the receipt of messages to break protocol can bring about situations where the legality of actions is uncertain. If a dialogue
violates the protocol, then it must have a smallest prefix (possibly the dialogue itself)that violates the protocol. The final moment of that prefix contains the dialogue events
that brought about the violation. If receiving a message cannot violate a protocol, thenremoving all the send actions from that final moment should give us a dialogue which
does not violate the protocol (item two in Definition 4).
Definition 4 (Protocol, P). Let D be all possible dialogues given a dialogue system D.
A protocol P ⊆ D for D is a set of dialogues, such that:
1. ∀M1 ...Mk ∈ P, i ∈ [1, k] : M1 ...Mi ∈ P.
2. For each d ∈ D if d 6∈ P and M1 ...Mk is the shortest prefix of d that is not in P,
then d0 ∈ P where d0 = M1 ...Mk−1 M0k such that M0k = {r(a, l, a0 ) ∈ Mk }.
Example 4 (Protocol). As an example protocol we want to specify that a why(x)locution for some propositional atom x ∈ {p, q, r, s} can only be uttered by the user
and only as a response to some earlier claim or support that involved x. Similarly, theprotocol also specifies that support locutions can only be uttered for supporting earlier
claim or support locutions (which in turn are only allowed for the expert). Our example protocol P therefore contains a dialogue d iff for each agent a, a0 ∈ A: (a) each
send action s(a, why(x), a0 ) in the dialogue is preceded by some previous momentin which r(a, claim(x), a0 ) or r(a, support(y, x), a0 ) is contained and a = user and(b) each send action s(a, support(x, y), a0 ) in the dialogue is preceded by some previous moment in which s(a, claim(x), a0 ) or s(a, support(z, x), a0 ) is contained, wherex, y, z ∈ {p, q, r, s} and a = expert. In summary, protocol P allows the expert to makeclaims at any time, the user to request support of previously made claims and the expert
to support past claims/supports of itself.
To illustrate the second item of Definition 4, consider the dialogue M1 M2 such that
M1 = {s(expert, claim(p), user)} and M2 = {r(user, claim(p), expert), s(user,
claim(r), expert)}. This dialogue is illegal because the user may not send the claim.
The shortest prefix of this dialogue that is not in the protocol is M1 M2 itself. Let M02 be
M2 , except that we remove the send actions (i.e., s(user, claim(r), expert)). ClearlyM1 M02 satisfies the protocol.

Agents do not have a total view of the dialogue. In fact, only those events where
they send or receive a message can be assumed to be observable by them. We model
this view of an agent on a dialogue as a function that filters the moments of the dialogue
to those events that concern that agent. Hence, the view of an agent on a dialogue is asequence of moments where each event has that agent as the subject.
Definition 5 (View, va ). Let D be all possible dialogues given a dialogue system D =(A, L), a ∈ A be an agent and d = M1 ...Mk ∈ D be a dialogue. For a moment M andagent a let M↓a = {x(a, l, a0 ) ∈ M|x ∈ {s, r}}. The view of a on a moment M in d,notated va (M), is the single-moment sequence M↓a if M↓a 6= ∅ and the empty sequence
ε otherwise. The view of a on d, notated va (d), is the concatenation of the views of each
moment: va (d) = va (M1 )...va (Mk ).
Example 5 (View). The view of the user on the dialogue M1 M2 M3 from Example 3
is vuser (M1 )vuser (M2 )vuser (M3 ) = εM02 ε = M02 , where M02 = {r(user, claim(p),expert), s(user, why(p), expert)}. Hence, from the user’s point of view only one moment has passed in the dialogue, where it responded to a claim with a why question.
We will next specify the class of peer-to-peer suitable protocols. These protocols
guarantee that an agent is always in a position to know that its send actions are notviolating the protocol. If an agent wants to check whether a dialogue is violating theprotocol, then it has to do this using its view on the dialogue. Many different dialogues
will look the same to an agent given its view. For each specific agent we want to specify
a personal set of dialogues such that the agent can distinguish with its view whether adialogue is in or out of that set. If a dialogue is out of an agent’s dialogue set, then the
dialogue violates the protocol (but not necessarily the other way around). A protocol
is peer-to-peer suitable if we can define such a set for each agent and furthermore, if a
dialogue violates the protocol then there must be at least one agent that can detect this(i.e. the dialogue falls out of that agent’s personal set). The latter constraint is captured
by requiring that the intersection of all the personal dialogue sets is the protocol itself.
Definition 6 (Peer-to-Peer Suitable). Let D be all possible dialogues given a dialoguesystem D = (A, L) and P be a protocol for D. P is peer-to-peer
suitable iff for eachTagent a ∈ A there exists a subset Pa ⊆ D such that P = a∈A Pa and for each d, d0 ∈ D
if va (d) = va (d0 ) then d, d0 ∈ Pa or d, d0 6∈ Pa .
Example 6 (Peer-to-Peer Suitable). Our example protocol P from Example 4 is peerto-peer suitable. We can make Puser such that a dialogue is in Puser iff each sendaction s(user, why(x), a) in the dialogue is preceded by some previous moment inwhich r(user, claim(x), a) or r(user, support(y, x), a) is contained, and there is no
occurence of s(user, claim(x), a) or s(user, support(x, y), a), for a ∈ {user, expert}.
We can make Pexpert such that a dialogue is in Pexpert iff each send action s(expert,
support(x, z), a) in the dialogue is preceded by some previous moment in whichs(expert, claim(x), a) or s(expert, support(y, x), a) is contained, and there is no occurence of r(expert, why(x), a), for a ∈ {user, expert}. The intersection Puser ∩Pexpert forms the protocol. A violation is detected when either agent sends illegally amessage. For instance, if the sender violates a protocol, then it sent a why question,
which clearly is not allowed by Pexpert .

Consider another protocol in which the agents must take turns but there are no further restrictions. This protocol could be defined by specifying that each dialogue in the
protocol contains only moments where at most one agent sends messages. This protocol
is not peer-to-peer suitable. Intuitively, the view of an agent does not allow the agent todistinguish between moments where it alone sends a message and moments where others send messages as well. Therefore, no agent can detect a violation. A solution would
be to introduce a special turn-yielding locution in the dialogue system, and specify that(a) an agent may only send messages if it has received the yield-turn locution and has
not yet send it after the last time that the locution was received (or if the agent is thestarting agent and no messages have been sent yet), (b) sending the yield-turn locution
is only allowed if the agent has not sent it since the last time the locution was received(note that this implies that the agent can only yield the turn to a single peer, and it is not
restricted which peer this is). We note that turn taking brings with it the risk of agents
not yielding their turn and thereby threatening the liveness of a dialogue application.
Hence, unlike many protocol specification frameworks for argumentation, we do notassume that turn taking is always part of the protocol.
We show that a peer-to-peer suitable protocol violation can always be detected by
one of the agents, that is, one of the agents can, given its view on the violating dialogue,
determine that the protocol is violated. At the same time, if the dialogue is not violated,then it is not violated given the views of all the agents. We show this by constructing
a set of views per agent that is based on the personal set of dialogues in the definitionof peer-to-peer suitability. Given that the protocol is the intersection of the personalsets, we know that a violating dialogue is outside of at least one personal dialogue set.
Given further that the personal sets of dialogues are closed under the views of agents,
we know that at least one agent can distinguish a bad dialogue from the good ones. If a
dialogue is not violating the protocol then it is contained in each personal dialogue set.
If we define the set of views per agent as the views on the dialogues in the personal sets,then it follows immediately that a correct dialogue is always in all the sets of views per
agent.
Proposition 1. Let D be all possible dialogues given a dialogue system D = (A, L)
and P be a peer-to-peer suitable protocol for D. For each agent a ∈ A there exists a setof views Va ⊆ {va (d)|d ∈ D} such that (a) if d 6∈ P then there is an agent a0 ∈ A andva0 (d) 6∈ Va0 and (b) if d ∈ P then for each agent a ∈ A : va (d) ∈ Va .
Proof. From the definition of peer-to-peer suitable
we know that for each agent a ∈ A
Tthere exists a subset Pa ⊆ D such that P = a∈A Pa and for each d, d0 ∈ D if va (d) =va (d0 ) then d, d0 ∈ Pa or d, d0 6∈ Pa . Let for each agent a ∈ A the set Va be definedas {va (d)|d ∈ Pa }. For a dialogue d ∈ D if d 6∈ P and there is no T
agent a ∈ A suchthat d 6∈ Pa , then it means that d is in each Pa0 , a0 ∈ A, i.e., dT∈ a∈A Pa (d would
be deemed legal by all agents). This cannot be the case as P = a∈A Pa . Therefore, if
d 6∈ P then there is an agent a ∈ A such that d 6∈ Pa . From the peer-to-peer suitability
definition we also know that there cannot be a dialogue d0 ∈ Pa such that v(d) = v(d0 )if d 6∈ Pa . Therefore if d 6∈ Pa then va (d) 6∈ Va , thus proving (a). If d ∈ P, then d ∈ Pa
for each agent a ∈ A, and therefore va (d) ∈ Va for each agent a ∈ A, thus proving (b).

We note that there exist peer-to-peer suitable protocols where only the agent thatcauses the violation can see the violation. The notion of peer-to-peer suitability could
be expanded such that it guarantees that if some send action causes a violation that thenthe receipt of that message allows the recipient to determine the protocol violation as
well. Such an expansion falls out of the scope of this paper.
3.2

Templates for Argumentation Dialogues

We observe that most dialogue systems, such as argumentation dialogue systems, require information about whether a received locution is a response to some past locution.
This is not always as straightforward as saying that the last locution is a response to thepenultimate locution. In an argumentation dialogue an agent can, for instance, utter an
extra support locution in a response to some past question. Since the coherence relation
among locutions cannot be derived solely from the legality conditions of a protocol, we
include the coherence relation as part of our protocol specification framework. We opt
to capture dialogue coherence with graphs in order to accommodate a wide variety ofcoherence structures (linear lists, trees, and arbitrary graphs). We refer to such a graphas a dialogue graph and assume that a dialogue graph is what agents use to decide upon
their next locution(s). As always, a graph consists of nodes and edges. We do not assume any structure on nodes. We add the agent that belongs to a graph to the graph’s
specification.
Definition 7 (Dialogue Graph, g). Let A be a set of agents. A dialogue graph g is
specified by (a, N, E), where a ∈ A, N is a set of nodes and E ⊆ N × N are the edges.
We use ga∅ for the empty graph (a, ∅, ∅).
Example 7 (Dialogue Graph). For our example scenario we use dialogue events as
nodes in dialogue graphs. As an example graph consider g = (user, N, E) where N ={e1 , e2 , e3 , e4 } and E = {(e1 , e3 ), (e3 , e4 )} such that e1 = r(user, claim(p), expert),
e2 = r(user, claim(q), expert), e3 = s(user, why(p), expert), e4 = r(user,
support(p, q), expert). This graph represents the user’s view on a dialogue where theexpert has claimed both p and q in the dialogue. The user has also asked why p is thecase, which is why this event is connected to the claim of p. Then, the answer of theexpert, that q supports p, is connected to the why question.
As reusable high-level elements for dialogue system specifications we propose dialogue templates [5]. A dialogue template tells for a specific locution under which circumstances it might be sent or received and how this updates the dialogue graph of thesender (or receiver, respectively). The condition of a template is specified by a functionthat takes a dialogue graph and returns the agents to which the locution might be sent
(or from whom it might be received, respectively). The update of a graph is conditionedon the graph that is being updated and the agent to which the locution is sent (or fromwhom it is received). An update must furthermore produce a graph for the same agent
that belongs to the input graph of the function. We can interpret the update function asa specification for how new locutions are related to previous locutions in a dialogue.

Fig. 1. Example dialogue graph. See Example 7.

Definition 8 (Dialogue Template, t). Let L be a set of locutions, A be a set of agent
atoms, and G be a set of dialogue graphs. A dialogue template t for L, A and G is
specified by either ts (l, c, u) or tr (l, c, u), where l ∈ L, c : G → 2A returns to which
agents l might be sent (or received, respectively) and u : G×A → G specifies a dialogue
graph update given a dialogue graph and recipient (or sender, respectively) such thatu((a, N, E)) = (a, N0 , E0 ).
Example 8 (Dialogue Templates). For all possible dialogue events E given our example
scenario we define the set of all dialogue graphs G to be G = {(a, N, E)|a ∈ A ∧ N ⊆E∧E ⊆ N×N}. In the following we use x and y as placeholders for values in {p, q, r, s}.
We also abbreviate the expert and user to e and u, respectively.
For our example scenario we specify the protocol from Example 4 with a set of six
dialogue templates. We specify a receive and a send template for each of the locutions.
In general there can be multiple templates for receiving/sending the same locution. The
templates T for our example scenario are given by:– ts (claim(x), c4 , us,claim(x) ), tr (claim(x), c3 , ur,claim(x) )– ts (why(x), c1x , us,why(x) ), tr (why(x), c4 , ur,why(x) )– ts (support(x, y), c2x,y , us,support(x,y) ), tr (support(x, y), c3 , ur,support(x,y) )Formally, for a graph g = (a, N, E) the condition functions are defined as: {e} ∃r(u, claim(x), e) ∈ N
c1x (g) = {e} ∃r(u, support(y, x), e) ∈ N∅ otherwise
c2x,y (g) ={u} ∃s(e, claim(x), u) ∈ N∅ otherwise
c3 (g) = {e}c4 (g) = {u}So for instance tr (support(x, y), c3 , ur,support(x,y) ) says that support(x, y) can bereceived from the expert and if it is received, then the update function ur,support(x,y) is
applied to the agent’s dialogue graph (specified below).
Intuitively, for a specific agent the update functions specify that sending a why
question is a response to either an earlier received claim or received support utterance,
receiving a why question is a response to an earlier sent claim or sent support utterance,
sending a support utterance is a response to a received why question and receiving a
support utterance is a response to an earlier sent why question. We parametrize the update functions with a communication mode (send or receive) and a locution. Formally,
for a locution l, a graph g = (a, N, E) and an agent a0 the update functions are definedas:us,l (g, a0 ) = (a, N ∪ {s(a, l, a0 )}, E0 )ur,l (g, a0 ) = (a, N ∪ {r(a, l, a0 )}, E0 )such that (e1 , e2 ) ∈ E0 iff:
e1 = r(a, claim(x), a0 ) ∈ N and e2 = s(a, why(x), a0 ) ∈ N,or e1 = r(a, support(y, x), a0 ) ∈ N and e2 = s(a, why(x), a0 ) ∈ N,or e1 = s(a, claim(x), a0 ) ∈ N and e2 = r(a, why(x), a0 ) ∈ N,or e1 = s(a, support(y, x), a0 ) ∈ N and e2 = r(a, why(x), a0 ) ∈ N,or e1 = r(a, why(x), a0 ) ∈ N and e2 = s(a, support(x, y), a0 ) ∈ N,or e1 = s(a, why(x), a0 ) ∈ N and e2 = r(a, support(x, y), a0 ) ∈ N.
A template-based dialogue system is a dialogue system that is extended with possible dialogue graphs and templates.
Definition 9 (Template-Based System, D+ ). A template-based dialogue system D+ is
specified by (A, L, G, T) where A and L are sets of agent and locution atoms, respectively, G is a set of dialogue graphs such that ga∅ ∈ G for each a ∈ A and T is a set of
dialogue templates for L, A and G.
We will next specify the operational semantics of a template-based dialogue systemwith Plotkin style transition rules. These rules give insight in how exactly a dialoguesystem can transition and help us and agents to reason about possible dialogues that may
result from the specification. The runtime configuration of a dialogue system consistsof the history of moments that have already passed, the messages that are to be received
now or in the future (notated τ1 , these messages were sent in earlier moments), themessages that are to be received in the future (notated τ2 , these messages are being sentin the current moment) and the dialogue graphs of each agent. There are four possible
transition rules that apply for a transition: an agent receives a message for which a
template is specified, an agent receives a message for which no template is specified (inwhich case the message has no effect), an agent sends a message or the moment passes.
An agent can receive a message if that message was sent in an earlier moment. If there
is a template specified for the reception of the message, then this template is used to
update the dialogue graph. An agent can only send a message if there is a template thatallows this. Finally, if the current moment passes, then all sent messages of the current
moment can be received during the following moments.
Definition 10 (Dialogue Operational Semantics, cD+ ). Let D+ = (A, L, G, T) be atemplate-based dialogue system where A = {a1 , ..., ak }. A runtime configuration of

D+ is specified by cD+ = (d, M, τ1 , τ2 , g1 ...gk ), where d ∈ (2E )∗ is a sequence of setsof dialogue events, M ⊆ E is a set of dialogue events, τ1 and τ2 are sets of receive eventsand gi , i ∈ [1, k], is a dialogue graph (ai , Ni , Ei ). The initial runtime configuration of
D+ is (ε, ∅, ∅, ∅, ga∅1 ...ga∅k ). The operational semantics of D+ is given by:r(ai , l, a0 ) ∈ τ1 & ∃tr (l, c, u) ∈ T : a0 ∈ c(gi ) & u(gi , a0 ) = gi0r(ai ,l,a0 )(d, M, τ1 , τ2 , g1 ...gi ...gk ) −−−−−→d (d, M0 , τ10 , τ2 , g1 ...gi0 ...gk )(Dialogue Receive 1)
where M0 = M ∪ {r(ai , l, a0 )} and τ10 = τ1 \ {r(ai , l, a0 )}r(ai , l, a0 ) ∈ τ1 & 6 ∃tr (l, c, u) ∈ T : a0 ∈ c(gi )r(ai ,l,a0 )(d, M, τ1 , τ2 , g1 ...gi ...gk ) −−−−−→d (d, M0 , τ10 , τ2 , g1 ...gi ...gk )(Dialogue Receive 2)
where M0 = M ∪ {r(ai , l, a0 )} and τ10 = τ1 \ {r(ai , l, a0 )}∃ts (l, c, u) ∈ T : a0 ∈ c(gi ) & u(gi , a0 ) = gi0s(ai ,l,a0 )(Dialogue Send)(d, M, τ1 , τ2 , g1 ...gi ...gk ) −−−−−→d (d, M0 , τ1 , τ20 , g1 ...gi0 ...gk )where M0 = M ∪ {s(ai , l, a0 )} and τ20 = τ2 ∪ {r(a0i , l, ai )}τ10 = τ1 ∪ τ2
moment(d, M, τ1 , τ2 , g1 ...gk ) −−−−−→d (dM, ∅, τ10 , ∅, g1 ...gk )(Dialogue Moment)

Example 9 (Operational Semantics). For our scenario we specify D+ as (A, L, G, T),
where the elements are drawn from the previous examples. In Table 1 we show the transitions that take place in the dialogue M1 M2 M3 such that M1 = {s(e, claim(p), u)},M2 = {r(u, claim(p), e), s(u, why(p), e)}, M3 = {r(e, why(p), u), s(e, support(p, q),u)}. The transitions are enabled by the dialogue templates T. In the initial state thegraphs of the expert and user are their empty graphs (ge0 and gu0 ). Then the sender sends
a claim to the user. This causes its graph to be updated with the us,claim(x) function,
resulting in ge1 (where the locution is added to its nodes). The send event is added to thecurrent moment and the corresponding receive event to τ2 . This means that somewherein the future the message will be received. The second transition passes the moment.
The receive event switches to τ1 , meaning that the message can be received in the current moment. The other transitions further handle the other messages and moments. The
result is intuitively that the operational semantics allow for a dialogue to take place. In
the rest of this section we show that the transitions indeed allow for dialogues and thatthe set of all possible allowed dialogues specifies a peer-to-peer suitable protocol.
Given the operational semantics of a template-based dialogue system we may specify the set of sequences of sets of dialogue events that may result from those transitions,which is called the language of that template-based dialogue system. A sequence of setsof dialogue events d is in the language of a template-based dialogue system if and only
if from the initial runtime configuration we can make transitions such that we reach aruntime configuration where d is the first argument of the state.

DMτ1 τ2 ge gu Transitionε∅∅∅ ge0 gu0
Send
ε
{e1 }
∅ {e2 } ge1 gu0 Moment
M1∅{e2 } ∅ ge1 gu0 Receive1
M1
{e2 }
∅
∅ ge1 gu1Send
M1{e2 , e3 } ∅ {e4 } ge1 gu2 Moment
M1 M2∅{e4 } ∅ ge1 gu2 Receive1
M1 M2
{e4 }
∅
∅ ge2 gu2
Send
M1 M2 {e4 , e5 } ∅ {e6 } ge3 gu2 Moment
M1 M2 M3∅
{e6 } ∅ ge3 gu2
Table 1. Example transitions (see Example 9). A row indicates the left hand side state of a transition and ends with the name of the transition rule that is used to transition to the next row. The
events are e1 = s(e, l1 , u), e2 = r(u, l1 , e), e3 = s(u, l2 , e), e4 = r(e, l2 , u), e5 = s(e, l3 , u),e6 = r(u, l3 , e), where the locutions are l1 = claim(p), l2 = why(p) and l3 = support(p, q).

Definition 11 (Dialogue Language, LD+ ). Let D+ = (A, L, G, T) be a template-based
dialogue system. The language of D+ , notated LD+ are all sequences of sets of dialogue
events d such that there is a sequence of transitions cD+ →d ... →d c0D+ possible wherecD+ is the initial runtime configuration of D+ and c0D+ = (d, M, τ1 , τ2 , g1 ...gk ).
As intended, each element in the language of a template-based dialogue system is adialogue.
Proposition 2. Let D+ = (A, L, G, T) be a template-based dialogue system. Each element in LD+ is a dialogue.
Proof. By definition 3, a sequence of sets of dialogue events d = M1 ...Mk is a dialogue
iff for each moment Mi , i ∈ [1, k], if r(a, l, a0 ) ∈ Mi then the number of moments Mj ,j ∈ [1, i − 1], such that r(a, l, a0 ) ∈ Mj is less than the number of moments Mn ,n ∈ [1, i − 1], such that s(a0 , l, a) ∈ Mn . The operational semantics only allow a receive
transition for an event r(a, l, a0 ) if a corresponding send transition took place for the
event s(a0 , l, a) in a previous moment. Furthermore, if a receive transition takes place,then the event is removed from the runtime configuration. Hence for a new receive event
it is required that first a new send transition for that event takes place. This means that a
receive event r(a, l, a0 ) can only be in the current moment Mi if the corresponding send
event s(a0 , l, a) is in a past moment Mj , j < i, and in between those two moments noreceive event took place: ∀n ∈ [j + 1, i − 1] : r(a, l, a0 ) 6∈ M0n . Hence any possible
sequence of sets of dialogue events of role based dialogue system fits the definitionof a dialogue, and therefore the language of a role based dialogue system is a set of
dialogues.
The language of a template-based dialogue system is a protocol. This means that atemplate-based dialogue system can be seen as a protocol specification.
Proposition 3. Let D+ = (A, L, G, T) be a template-based dialogue system. LD+ is a
protocol.

Proof. By definition 4, LD+ is a protocol iff:
1. ∀M1 ...Mk ∈ LD+ , i ∈ [1, k] : M1 ...Mi ∈ LD+ .
2. For each d ∈ D if d 6∈ LD+ and M1 ...Mk is the shortest prefix of d that is not in
LD+ , then d0 ∈ LD+ where d0 = M1 ...Mk−1 M0k such that M0k = {r(a, l, a0 ) ∈ Mk }.
Point 1 is easily verifiable; a dialogue d ∈ LD+ is possible due to a number ofconsecutive transitions. Hence, all prefixes of d are also in LD+ since we can obtain eachprefix by executing only an initial segment of the consecutive transitions that create theprefix.
Point 2 follows from the fact that a receive transition can always be made, even
if there is no template specified (rule Dialogue Receive 2). The transitions that create M1 ...Mk−1 result in a configuration cD+ = (M1 ...Mk−1 , M, τ1 , τ2 , g1 ...gk ) where
necessarily all the receive events from Mk are in τ1 . Therefore, we can make receive
transitions until a configuration c0D+ = (M1 ...Mk−1 , M0 , τ10 , τ2 , g10 ...gk0 ) is reached suchthat M0 = {r(a, l, a0 ) ∈ Mk }. If we follow this transition with a moment transition, thenM1 ...Mk−1 M0 is created, which is thus in LD+ , which proves point 2.
Finally our main theorem formulates the goal of this paper: the language of atemplate-based dialogue system is a peer-to-peer suitable protocol. This means that we
can use a specification of a template-based dialogue system as a protocol specificationthat is suitable for open multi-agent systems.
Theorem 1. Let D+ = (A, L, G, T) be a template-based dialogue system. LD+ is apeer-to-peer suitable protocol.
Proof. LD+ is a protocol, hence we only need to proveTthat we can make for each agenta ∈ A a set of dialogues Pa ⊆ D such that LD+ = a∈A Pa and for each d, d0 ∈ D
if va (d) = va (d0 ) then d, d0 ∈ Pa or d, d0 6∈ Pa . First, let Pa for each agent a ∈ A be
defined as Pa = {d ∈ D|∃d0 ∈ LD+ : va (d) = va (d0 )}. By this construction it follows
immediately that for each agent a ∈ A if va (d) = va (d0 ) then d, d0 ∈ Pa or d, d0 6∈ Pa .
A dialogue d is not in LD+ iff there is no sequence of transitions cD+ →d ... →dc0D+ where cD+ is the initial runtime configuration of D+ and c0D+ = (d, M, τ1 , τ2 , g1 ...gk ).
Necessarily at least one unallowed send transition for some event s(a, l, a0 ) is required
to make d (receive and moment transitions are always possible). This means that given
the view of a there cannot be a dialogue d0 ∈ LD+ such that va (d) = va (d0 ). And thus if
d 6∈ LD+ then there is an agent a ∈ A such that d 6∈ Pa . Furthermore, for each d ∈ LD+
and agent a ∈ A it holds Tthat va (d) = va (d), hence if d ∈ LD+ then d ∈ Pa for eacha ∈ A. Therefore LD+ = a∈A Pa .
We can see a template-based dialogue system as a protocol specification because
the language of a template-based dialogue system is a peer-to-peer suitable protocol.
The protocol handles the legality of locutions, but does not address the ‘low-level’ concerns such as ensuring that messages will arrive. The templates ought to be notated ina human/machine readable format in order to make them interpretable for the agents.
An agent can, given the protocol, determine all the views on all the dialogues that areallowed by the protocol and use this to strategise. For instance, in a strict turn-based
dialogue system it may build a game tree and apply classic decision mechanisms fordeciding upon a locution. We note that the templates can formally be quite involved,
but at the same time might be quite straightforward in their manifestation as programs.
Similarly, the maintenance of dialogue graphs in the formal semantics implies that thegraph can grow indefinitely as the dialogue grows, but in an implementation this might
not always be the case.

4

Conclusion

In this paper we have presented a formal framework for specifying communication protocols for open multi-agent systems. Our main reusable building blocks for specifying
protocols are dialogue templates, which we have provided with a formal operationalsemantics. In open multi-agent systems we cannot assume that agents have knowledge
about the messages that are exchanged among other agents, and an agent can also notassume any order on which messages are received when it sends messages. We formalised such concerns as peer-to-peer dialogues and presented a specification methodto specify protocols that guarantee that each agent is in a position to know whether anaction from itself causes a protocol violation.
With respect to argumentation, future work consists of further developing the framework to specify argumentation dialogue protocols which specify illocutionary force,that is, how argumentation dialogues can be used to build and analyse logical argument
structures. Further work includes adapting the multitude of dialogue protocols specified
in DGDL [25] to the current specification framework, representing common elements
such as turntaking, commitments, and so on in our framework.
Not enforcing a protocol through a proxy agent or middleware brings up numerous
interesting situations for argumentation dialogue systems. In this paper we focus on ensuring that agents can determine whether their own behaviour causes a violation of a
protocol. In the future we want to investigate under which conditions it can be guaranteed that an agent can determine that another agent violated the protocol. The current
work also assumes that agents adhere to the same protocol, but how does an agent determine the protocol under which it is communicating with other agents when there isno middleware? For which types of protocols/moves and under which conditions areagents guaranteed to pick up protocol violations from other agents? Is it possible toinduce which protocols other agents are using from their behaviour? These are all questions we want to answer in future research.

Acknowledgements
This research is part of the project Intelligence Amplification for Cybercrime which has
been funded by the Dutch National Police Innovation Programme.

References
1. L. Amgoud, N. Maudet, and S. Parsons. Modelling dialogues using argumentation. In
Proceedings of the 4th Conference on Multi-Agent Systems, pages 31–38. IEEE, 2000.

2. B. Bauer, J. P. Müller, and J. Odell. Agent UML: A formalism for specifying multi-agent
software systems. International journal of software engineering and knowledge engineering,
11(03):207–230, 2001.
3. F. Bex, J. Lawrence, and C. Reed. Generalising argument dialogue with the dialogue gameexecution platform. In Proceedings of COMMA 2014, volume 266 of Frontiers in Artificial
Intelligence and Applications, pages 141 – 152. IOS Press, 2014.
4. F. Bex, J. Peters, and B. Testerink. A.I. for online criminal complaints: From natural dialogues to structured scenarios. In Workshop A.I. for Justice - Proceedings of ECAI 2016,
pages 22–29, 2016.
5. F. Bex and C. Reed. Dialogue templates for automatic argument processing. In Proceedingsof COMMA 2012, volume 245 of Frontiers in Artificial Intelligence and Applications, pages
366–377. IOS Press, 2012.
6. E. Black and A. Hunter. Executable logic for dialogical argumentation. In Proceedings of
ECAI, pages 15–20. IOS Press, 2012.
7. E. Black, P. McBurney, and S. Zschaler. Towards agent dialogue as a tool for capturing software design discussions. In International Workshop on Theory and Applications of Formal
Argumentation, pages 95–110, 2013.
8. M. Dastani, D. Grossi, J. C. Meyer, and N. A. M. Tinnemeier. Normative multi-agent programs and their logics. In First International Workshop on Knowledge Representation forAgents and Multi-Agent Systems, pages 16–31, 2008.
9. X. Fan and F. Toni. A general framework for sound assumption-based argumentation dialogues. Artificial Intelligence, 216:20–54, 2014.
10. M. Hannoun, O. Boissier, J. S. Sichman, and C. Sayettat. Moise: An organizational model
for multi-agent systems. In Advances in Artificial Intelligence, pages 156–165. Springer,
2000.
11. J. Lawrence, F. Bex, C. Reed, and M. Snaith. Aifdb: Infrastructure for the argument web. In
Proceedings of COMMA 2012, pages 515–516, 2012.
12. O. Lemon and O. Pietquin, editors. Data-Driven Methods for Adaptive Spoken Dialogue
Systems: Computational Learning for Conversational Interfaces. Springer-Verlag New York,2012.
13. A. Maghraby, D. Robertson, A. Grando, and M. Rovatsos. Automated deployment of argumentation protocols. In Proceedings of COMMA 2012, volume 245 of Frontiers in Artificial
Intelligence and Applications, pages 197–204, 2012.
14. H. Mazouzi, A. E. F. Seghrouchni, and S. Haddad. Open protocol design for complex interactions in multi-agent systems. In Proceedings of the first international joint conference on
Autonomous agents and multi-agent systems: part 2, pages 517–526. ACM, 2002.
15. P. McBurney and S. Parsons. Dialogue games for agent argumentation. In Argumentation in
artificial intelligence, pages 261–280. Springer, 2009.
16. N. Minsky and V. Ungureanu. Law-governed interaction: A coordination and control mechanism for heterogeneous distributed systems. TOSEM, ACM Transactions on Software Engineering and Methodology, 9:273–305, 2000.
17. O. Noroozi, A. Weinberger, H. J. Biemans, M. Mulder, and M. Chizari. Argumentation-based
computer supported collaborative learning (abcscl): A synthesis of 15 years of research.
Educational Research Review, 7(2):79–106, 2012.
18. J. J. Odell, H. V. D. Parunak, and B. Bauer. Representing agent interaction protocols in
UML. In Agent-oriented software engineering, pages 121–140. Springer, 2001.
19. J. Pitt and A. Mamdani. A protocol-based semantics for an agent communication language.
In Proceedings of IJCAI 99, pages 486–491, 1999.
20. D. Poutakidis, L. Padgham, and M. Winikoff. Debugging multi-agent systems using design
artifacts: The case of interaction protocols. In Proceedings of the first international joint

conference on Autonomous agents and multiagent systems: part 2, pages 960–967. ACM,
2002.
21. H. Prakken. Coherence and flexibility in dialogue games for argumentation. Journal of logic
and computation, 15(6):1009–1040, 2005.
22. H. Prakken. A formal model of adjudication dialogues. Artificial Intelligence and Law,
16(3):305–328, 2008.
23. I. Rahwan, S. D. Ramchurn, N. R. Jennings, P. Mcburney, S. Parsons, and L. Sonenberg.
Argumentation-based negotiation. The Knowledge Engineering Review, 18(4):343–375,
2003.
24. J. Schatzmann, K. Weilhammer, M. Stuttle, and S. Young. A survey of statistical user simulation techniques for reinforcement-learning of dialogue management strategies. The knowledge engineering review, 21(2):97–126, 2006.
25. S. Wells and C. Reed. A domain specific language for describing diverse systems of dialogue.
Journal of Applied Logic, 10(4):309–329, 2012.