Opponent Modelling in Persuasion Dialogues

1 Introduction

Agents engaging in persuasion dialogues aim to convince their counterparts to accept propositions that the latter do not currently endorse. As one would expect, agents then strategise based on their assumptions about the beliefs of their counterparts (opponents). This is widely studied in terms of opponent modelling. Essentially, an opponent model (OM) consists of five basic components: an opponent's beliefs; abilities; preferences; objectives, and; strategy. Numerous researchers who deal with the best response problem in dialogues- optimally choosing which move to make - rely on opponent modelling for implementing, and employing strategies [Riveret et al., 2007; 2008; Oren and Norman, 2010; Black and Atkinson, 2011]. The general idea is to rely on such a model, built from an agent's experience, for simulating the possible ways based in which a game may evolve. One may then rely on this simulation to optimally choose, from a number of options, the most suitable option with respect to one's goals. Most approaches exploit an agent's experience in a somewhat monolithic way, assuming that its opponent's beliefs can simply be modelled through collecting the distinct utterances that the latter puts forth in dialogues.

Due to the simplicity of such modelling approaches, the formalisation of an OM is usually left implicit. In addition, such approaches disregard the fact that an agent's accumulated dialogue experience may encode additional information which could also be used for modelling, and so increasing the effectiveness of strategies that rely on OMs.

In this work, we rely on a simple framework for persuasion dialogue with abstract arguments. Participants maintain OMs which are constantly updated with content (arguments) obtained through new dialogues. We propose a mechanism which is used for augmenting such an OM with additional information that is likely to be associated with information already contained in the OM. In other words, we attempt to predict what else is likely to be believed by a particular agent, given: a) what we currently assume the latter believes, and; b) what others with similar beliefs know. To do this we rely on an agent's general history of dialogues, in which we monitor the times that certain opponent arguments (OAs) follow after certain others, thus utilising an agent's experience in a multifaceted way. For example, let two agents, Ag1 and Ag2, engage in a persuasion dialogue in order to decide where is the best place to have dinner:

• Ag1:(A) We should go to the Massala Indian restaurant since a chef in today's newspaper recommended it.
• Ag2:(B) A single chef's opinion is not trustworthy.
• Ag1:(C) This one's is, as I have heard that he won the national best chef award this year.
• Ag2:(D) Indian food is too oily and thus not healthy.
• Ag1:(E) It's healthy, as it's made of natural foods and fats.

The above dialogue is essentially composed of two lines of dispute, {A←B←C} and {A←D←E}. Assume then, that Ag2 engages in a persuasion dialogue with another agent, Ag3, on which is the best restaurant in town. Let us also assume that at some point in the dialogue Ag3 cites the newspaper article, by asserting argument A in the game, as Ag1 did in the previous dialogue. It is then reasonable for Ag2 to expect that to some extent Ag3 is likely to also be aware of the chef's qualifications (argument C). Intuitively, this expectation is based on a relationship between consecutive arguments in the same dispute lines of a dialogue. In this case, the "chef's proposition" (A) is defended against B's attack (i.e., 'supported') by "his qualifications" (C), suggesting some likelihood that awareness of the first implies awareness of the second. This is also the case for arguments A and E. However, assuming such a relationship between the chef's qualifications (C) and the argument on why Indian food is considered healthy (E), seems less intuitive, as these arguments belong in different dispute lines, and so do not support each other. We thus assume that two arguments can be related if they are found in the same dispute lines of a dialogue, where this relationship can be understood in terms of the notion of support, e.g., C supports A against B.

One can then rely on an agent's accumulated dialogue experience to define a graph in which links between OAs asserted in a series of dialogues, indicate support. A participant may then rely on this graph to augment an OM, by adding to it arguments which, according to the graph, are linked with arguments already contained in the OM, and which are thus likely to be known to that opponent. For quantifying this likelihood we rely on how often a certain argument follows after another in an agent's history of dialogues. While this is a simple approach, we believe that it is sufficient for increasing the effectiveness of an agent's strategising. In the future we intend to investigate more complex ways for quantifying this likelihood, accounting for contextual factors such as how common certain information is, or whether an agent is part of a certain group having access to shared information, etc.

Summarising, while an agent's dialogue experience can be utilised in many ways when modelling its opponents, in most cases this is neglected. We thus present an applicable method for updating and augmenting such a model utilising an agent's history of persuasion dialogues, making the following three contributions. In Section 3, we rely on an argumentative persuasion dialogue framework (formalised in Section 2) to define and present two mechanisms responsible for updating and augmenting an OM. Specifically; 1) Section 3.1 formalises a method for building a graph relating supporting arguments, based on an agent's experience; 2) Section 3.1 also provides a method for augmenting an agent's current beliefs about its opponents' beliefs based on these support relations, enabling an agent to additionally account for this information in its strategizing. Section 4 describes our third contribution; we define and analyse a Monte-Carlo simulation approach concerned with the augmentation process, which makes our approach tractable. We also prove convergence and provide supporting experimental results.

2 The Dialogue Framework

In this section we describe a framework for argumentation based persuasion dialogues in which participants exchange arguments constructed in a common language L. Participants submit arguments that attack those of their opponent, and we assume that participants share an understanding of when one argument attacks another, based on the language dependent notion of conflict. The arguments A that are submitted, during the course of a dialogue are then assumed to be organised into a Dung framework, AF = (A, C), where C is the binary relation on A, i.e. C ⊆ A×A. We assume participants take on the roles of proponent and opponent, where the former submits an initial argument X, whose claim is the topic of the dialogue. If X is a justified argument in the AF defined by the dialogue, then the proponent is said to have won the dialogue. We define a dialogue D as a sequence of dialogue moves < DM0, . . . ,DMn >, where the content of DM0 is the initial argument for the topic of the dialogue. We assume that the introduction of moves is contingent upon satisfying certain conditions, defined by a dialogue protocol, which concern: turntaking; backtracking; the legality of a move, and; the game's termination rules. Turntaking specifies the participant to move next and the number of dialogue moves she can make. We assume agents take alternate turns introducing a single move at a time. We assume multi-reply protocols which allow participants to backtrack and reply to previous moves of their interlocutors. Thus, a dialogue D can be represented as a tree T :

Definition 1 Let D =< DM0, . . . , DMn > be a dialogue andM = {DM0, . . . ,DMn} the set of moves in D. Then T = {M, E} is a dialogue tree with root node DM0, and arcs E ⊆M×M, such that:

• for twomoves DMi &DMj, (DMi,DMj)∈E means that DMj is DMi's target (DMi replies to DMj)
• every move inM that is not the target of another move, is a leaf node
• Each distinct path from DM0 to a leaf node of T , is referred to as a dispute.

For a tree with m leaf nodes, ∆ = {d1, . . . , dm} is the set of all disputes in the tree. Each new dispute results from a backtracking move by either of the participants. An example is shown in Figure 1(a), where grey's move DM6 is used as an alternative reply against white's move DM1.

The legality of a dialogue move is regulated by explicit rules that account for the dialogical objective, a participant's role, and a participants commitments. The latter comprise a commitment store (CS) which is updated with the contents of the moves introduced by a participant during the course of the dialogue.

Definition 2 The commitment store of an agent Ag participating in a dialogue D =< DM0, . . . ,DMn >, at turn t = 0 . . . n, is a set CSt = {A0, . . . , Ak}, k < n, containing the arguments introduced into the game by Ag up to turn t, such that CS0 = ∅, and:

where Content(DM) is the argument moved in DM.

Finally, we assume that each agent engages in dialogues in which its strategic selection of moves is based on what it believes its opponent believes. Accordingly each agent maintains a model of the beliefs of its potential opponents in terms of a set of arguments (as in [Oren and Norman, 2010]). Modelling an agent's goals is out of the scope of this work.

Definition 3 Let {Ag1, . . . , Agν} be a set of agents. Then for i = 1 . . . ν, the belief base KB of Agi is a tuple KBi =< A(i,1), . . . ,A(i,ν) > such that for j = 1 . . . ν, each sub-base A(i,j) = {A1, . . . ,Ak}, where k ∈ N, is a set representing an OM expressing what Agi believes is Agj's known arguments; and where A(i,i) represents Agi's own beliefs.

3 Modelling mechanisms

For modelling an agent's opponents' beliefs we rely on the arguments they put forth in a dialogue game. We, assume that agents believe what they utter, while. acknowledging that it is not possible to impose that agents are truthful through protocol restrictions or regulations [Wooldridge, 1999]. However, we believe our approach can readily be adapted to account for notions of trust and its use in argumentation [Y. Tang and S. Parsons, 2010]; a topic to be investigated in future work.

We begin by associating a confidence value c to the arguments of a sub-base A(i,j). For an agent Agi this value expresses the probability of a certain argument in A(i,j) being part of Agj's actual beliefs A(j,j). To compute this value we differentiate between whether information is: a) gathered directly by Agi, on the basis of its opponent's updated CS, or; b) a result of Agi augmenting its current model of Agj. The latter involves incrementing an OM with the addition of arguments likely to also be known to Agi's opponent.

As noted in Section 1, intuitively we expect our opponents to be aware of arguments that are likely to follow in a current dialogue, given that they have appeared in previous dialogues, and relate to what we currently assume our opponents believe. We assume this likelihood to increase as the relation between the contents of an OM and the arguments external to the model becomes stronger. This may be due to the appearance of particular sequences of arguments in dialogues, which relate the two sets. For example, assume Agi (P ) and Agj (O) engage in a persuasion dialogue, represented as the dialogue tree in Figure 1(a). In this case Agi and Agj introduce arguments {A, C, E, G} and {B, D, F, H} respectively. Assume then, that Agi engages in another persuasion dialogue with a different agent Agm who also counters Agi's A with B. It is then reasonable to assume that Agm is likely to be aware of arguments D, H or even F , given that D and H support B, and F supports D. If then Agm does indeed put forth arguments D, H and F in the game, then the likelihood of another agent knowing D,H and F, contingent that this other agent knows B, should increase.

For assigning a confidence value c to the elements of an A(i,j), we assume every agent's set of arguments increase monotonically. This is compatible with the idea that the beliefs from which arguments are constructed are not revised upon incorporation of conflicting beliefs; rather the conflicts are resolved through evaluation of the justified arguments under acceptability semantics [Dung, 1995]. We therefore assume that the confidence value associated with arguments acquired by an an agent Ag from the commitment store of Ag's opponents (which we refer to as arguments 'directly collected by Ag') is equal to 1, which represents the highest level of confidence.

Definition 4 Let A(i,j) ∈ KBi. Then ∀X ∈ A(i,j), c is the confidence level that Agi associates with X (denoted by the tuple < X, c >) such that:

where Pr(X) is the likelihood of X being known to Agj .

Further details on how to determine Pr(X) follow in Section 3.1. To define the mechanism for updating an agent's A(i,j) we first need to define the notion of history:

Definition 5 Let {Ag1, . . . , Agν} be a set of agents. For any two agents Agi and Agj, j ̸= i, h(i,j) = {D 1 , . . . ,D µ } is Agi's history of dialogues with Agj . Then Hi = ⋃νj=1 j̸=i h(i,j) is the set of all histories of Agi with each Agj , j ̸= i.

Commitment store updates to opponent models are then defined as follows:

Definition 6 Let h(i,j) = {D 1 , . . . , D µ} be the dialogue history of Agi and Agj . Given the current version of a sub-base Aµ-1 (i,j) and Agj's commitment store CSj of the latest dialogue D µ , Agi can update its sub-base as follows:

As explained above, in this case directly collected arguments are given a confidence value of 1.

3.1 Building a RG& augmenting the OM

Augmenting an A(i,j) relies on an agent Agi's relationship graph (RG) in which nodes are arguments asserted by Agi's opponents in Hi. Nodes are related by weighted directed arcs which represent support relationships between arguments, while the weights represent the likelihood of these relationships. We assume RGi is empty at the start (when Hi = ∅) and incrementally updated with newly encountered opponent arguments (OAs) as Agi engages in dialogues. In the example shown in Figure 1(a), assuming the grey agent Agi is the modeller, then the OAs (the white's arguments B,D, F and H) can only appear in odd levels of the dialogue tree. Assigning arcs between these arguments relies on how and when an argument appears in a tree.

Essentially, we assume two OAs, X and Y , to be connected in a RG if they are found in the same path of the dialogue tree (i.e., dispute), and are of d-hop distance from each other (distance is measured disregarding the modeller's DMs). For example, in Figure 1(a), B and D are of 1-hop distance from each other, while B and F are of 2-hop distance. Figures 1(b) and 1(c) illustrate two distinct RGs induced by Figure 1(a)'s dialogue tree, for hop distances d = 1 and d = 2 respectively. Through modifying the d value one can strengthen or weaken the connectivity, between arguments in the same dispute, and correspondingly between arguments in the induced RG. Of course, assigning a large d may raise cognitive resources issues, due to the large volume of information that needs to be stored. An example of incrementally building a d = 1 RG after two consecutive persuasion dialogues is illustrated in Figure 2.

Definition 7 Let AH represent the arguments introduced by Ag's opponents in H. Then RG is a directed graph RG = {AH,R}, where R ⊆ AH × AH is a set of weighted arcs representing support relationships. We write rAB to denote the arc (A,B) ∈ R, and denote the arc's weight as wAB obtained via a weighting function w, such that w :R →[0, 1].

Whether two opponent's arguments in an agent's RG are connected is defined as follows:

Condition 1 Let T be a dialogue tree T and d a hop distance. Then rAB ∈ R if there exists a distinct pair of opponent dialogue moves DM1 and DM2 with respective contents A and B, in the same dispute in T , respectively appearing at levels i, j, j > i, where j-i 2 ≤ d;

Lastly, for providing a weight value wAB which will essentially represent the relationship likelihood of an argument A with an argument B, we rely on Definition 8, which is essentially a normalisation that allows us to compute a probability value Pr(rAB) = wAB for arc rAB. We simply count the number of agents that have used, in dialogues, argument A followed by B, and we put them against the total number of agents that have simply put forth argument A in dialogues.

Definition 8 Given an Agi and its RGi = {AHi ,R}, and two arguments A,B elements of AHi then:

is a function that returns a set MAB ⊆ Ags representing the set of agents that have put forth argument A followed by B in the same disputes and at a distance d in distinct dialogues in Hi , satisfying Condition 1 such that rAB ∈ R, then:

Figure 3: (a) RG1, (b), (c), (d) & (e) Possible augmentation A′∅, A′D , A′F , & A′DF respectively.

In the case where B is omitted then MA will represent the set of agents that have simply put forth argument A in distinct dialogues, while it is evident that |MAB| ≤ |MA|.

We should note that there is a problem with the aforementioned approach. Namely, if we consider the example shown in Figure 2, and based on Definition 8, then all the arcs in the induced RG will initially have a weight value of 1. It is apparent that this value does not represent the real likelihood which relates the arguments at either endpoint of the arc. In order to better approach the real likelihood a larger number of dialogues with numerous distinct participants need to be considered. This problem is better known as the cold start problem and is encountered in various other contexts as well [Lashkari et al., 1994].

Having built a RG an agent Agi can then attempt to augment its OM (A(i,j)) of Agj by adding to it the possible arguments (nodes) that are of d-hop distance in RG from those contained in A(i,j). In a trivial case, assume an RG1 induced by Ag1 as it is illustrated in Figure 3(a), where for presentation convenience we assume that the weights on the arcs have received their values after numerous dialogue interactions. Let us assume that based on Ag1's OM of Ag4, Ag1 believes that Ag4 is aware of two arguments A(1,4) = {B,H} (the grey nodes in Figure 3(a)). Hence, Ag1 computes the likelihood of each of the possible augmentations A′(1,4) ∈ P where P = {A′∅,A′D ,A′F ,A′DF }, as those appear in Figures 3(b)(c)(d) and (e), and selects the one with the highest likelihood for augmenting A(1,4) with additional contents. Computing each of these likelihoods is done as illustrated in the following example:

Example 1 Assume we want to calculate the likelihood of augmentation A(1,4) →A′F . In this simple example the likelihood of including belief F is:

The probability of inducing A′F therefore is the probability of including argument F and not including D which is:

Finally, Pr(F) is also used to denote the confidence value c of argument F , as defined in Definition 4.

For providing the general formula for computing the likelihood of a possible augmentation we rely on basic graph theory notation with respect to a node X in a graph RG, such as degree d(X), neighbouring nodes N(X) where |N(X)| = d(X), and adjacent arcs R(X). In addition, assuming a set of arguments A, we define NA such that NA = ⋃X∈A N(X)|{Y ∈ N(X) : Y /∈ A} and RA = ⋃X∈A R(X)|{rXY ∈ R(X) : Y /∈ A}. Essentially, set NA represents the neighbours of the nodes in A, and is formed from the union of the neighbours of every node X in A, excluding those that are already in A, while RA is the adjacent arcs of the nodes in A and is equal to the adjacent arcs of every element X in A, excluding those that connect with arguments already in A. We note that for A(i,j) it reasonably holds that A(i,j) ⊆ AHi , while for convenience we will hence refer to a A(i,j) as A and to its augmentation as A′ . Given these, let P = {A′0 ,A′1 , . . . , } be the set of all possible distinct augmentations of A, then the number of all its possible distinct expansions with respect to neighbouring nodes that are of 1-hop distance fromA, is:

The general formula for computing the likelihood of a possible augmentation A′ with respect to the neighbouring nodes (arguments), i.e. for every X ∈ NA of a set A is:

where R-X (the in-bound arcs) is used to denote the adjacent arcs of X which are of the form (X, Y ), i.e. Y is the arc target. Lastly, since the likelihood of each possible augmentation should define a distribution of likelihoods then it must also hold that ∑A′∈P Pr(A′ ) = 1.

4 The Monte-Carlo Simulation

A drawback of the proposed approach is that, calculating the probability of Equation 5 is of exponential complexity. This makes the approach practically intractable. However, drawing inspiration from the work of Li et al. [Li et al., 2011] we rely on an approximate approach for computing these likelihoods based on a Monte-Carlo simulation. Essentially, the Monte-Carlo simulation attempts to estimate the argument likelihoods for a RG through sampling. In the case of a very large RG this approach is expected to be less expensive than exhaustively computing these likelihoods based on the inclusion-exclusion principle mentioned in Equation 5.

For the case of the 1-hop augmentation we know that the number of possible augmentations is exponential on the size of NA. It is possible to deduce a high likelihood augmentation in linear time, provided we know Pr(Y ) for ∀Y ∈ NA.

Also, Pr(Y ) is calculated through Equation 5 using the inclusion-exclusion principle found in basic algorithm textbooks such as [Knuth, 1997]. However, this is of exponential complexity on the in-degree to calculate. We therefore proceed to sample for Pr(Y ), by describing a method to sample for high likelihood arguments which we will include in our 1-hop augmentation of a set A. We will generally refer to the arguments in A as augmentation nodes. The method we describe is as follows:

• Assume an RG= {AH, R} and a set A
• We begin with a set of nodes A′ = A
• For each argument Y ∈ NA and if ∃rXY ∈ R, where X ∈ A, we accept rXY with probability wXY .
• If an arc rXY is accepted, we then add Y to A′
• At the end of the process A′ contains a possible 1-hop augmentation of A

We denote the probability of accepting an arc as Pr(rXY ) = wXY . We also assume the events of accepting rij and rkm, where rij ̸= rkm to be independent but not mutually exclusive, therefore:

which means that the probability for a node to be added in A′ follows Equation 5. Consequently the probability of obtaining a specific augmentation A′ follows Equation 4, and therefore the described procedure essentially samples from the distribution of augmentations.

Assuming a sampling procedure which generates a number of n samples using the described method, then each node Y is included with probability equal to Pr(Y ). Thus after n independent identically distributed (i.i.d.) samples, a proportion of nPr(Y ) will contain argument Y . We define kY = ∑ni=1 I(Y ∈ A′i ) where I is the indicator function taking the value of 1 if the predicate within is satisfied and A′i is the set of nodes contained in the i-th sampled augmentation. In this case kY is used to denote the number of times we sampled Y . The expected number of augmentations samples which contain Y follows a binomial distribution. Thus the expected number of observations kY , of any given node Y after n tries is E{kY } = nPr(Y ) and the variance is Var{kY } = nPr(Y )(1 - Pr(Y )). This defines a multinomial distribution over the set of nodes. Due to the law of large numbers and the fact that each sample is i.i.d., it holds that:

where ˆ P r(Y ) is our estimate of P r(Y ). The described procedure is a method to sample for the inclusion-exclusion probability. This is done since the exhaustive calculation of this probability is exponential in the number of arcs considered.

The generated random graphs are Poisson graphs, with edge probability set to 50/n (where n is the size of the graph). We selected this probability to ensure there exists a giant connected component and have a graph which is sufficiently dense, justifying the need to use a sampling method to infer the argument likelihoods rather than to directly measure them, but also sufficiently sparse, to be able to use it on a computer with limited capabilities. Due to the lack of benchmarks to compare with, we do not know whether a random graph better corresponds to a realistic argument graph. However, for the purposes of the Monte-Carlo simulation we believe that the graph structure is irrelevant for the purpose of argument likelihood estimation (assuming that the real argument graphs don't have a path-like or grid-like structure).

Figure 4: Error per argument likelihood over n samples

Figure 5: Average error over number of samples n

4.1 Sampling accuracy &Experimental results

The number of samples n required to achieve an accuracy ϵ with confidence δ is given through the following theorem 1 :

Theorem 1 The Monte-Carlo approach to sample the probability distribution of the nodes in NA is at least ϵ, close to convergence with probability at least δ after n = z2 δ 1 4ϵ2 samples.

In essence, Theorem 1 gives us the expected upper bound of the error, which is expected to reach an accuracy equal to ϵ = 0.05, with δ = 0.05 confidence by taking n ≤ z2 0.975 1 4ϵ2 ≈ 385 samples, independently of the size of the RG. Using the described algorithm we can estimate the likelihood of a given set of arguments (by dividing their observations by n) and infer a distribution of arguments. Based on these results we can augment our OM by choosing the set with the highest likelihood. Performing tests on randomly generated graphs of various sizes we have obtained the results of the average error which can be seen in Figure 5. We can see that the average error is upper bounded by the theoretically expected value. In practice the convergence is much quicker than what the theory suggests, resulting in error less than 0.1 after only 15 samples. Additionally in Figure 4 we can see the error per argument likelihood Pr(Y ).

1 Space limitations preclude including proof of Theorem 1, which can be found in [C. Hadjinikolis, 2013].

5 RelatedWork &Conclusions

Specifically, in the context of dialogue games, Riveret et al. [Riveret et al., 2007; 2008] model the possible knowledge of opponents in the form of arguments as we do. They however rely on the simplification that arguers are perfectly informed about all the arguments previously asserted by all their opponents in dialogues. Oren et al. [Oren and Norman, 2010] propose a variant of the min-max algorithm for strategising through relying on models which represent both an agent's knowledge, in the form of arguments, as well as their goals. However, nowhere in the aforementioned work is the problem of acquiring and maintaining, or augmenting an OM addressed. An exception, proposed by Black et al. [Black and Atkinson, 2011], concerns a mechanism that enables agents to model preference information about others-what is important to another agent-and then rely on this information for making proposals that are more likely to be agreeable. In their case the mechanism responsible for developing a model of an agent's preferences is explicitly provided, though they do not model agents' knowledge. A similar approach to our work has been proposed Rovatsos et al. [Rovatsos et al., 2005] who explored how to learn stereotypical sequences of utterances in dialogues for deducing an opponent's strategy, though not relying on OMs. Finally, the work of Emele et al. [Emele et al., 2011] is worth noting, as it is similar to ours in the sense that they also explore the development of an OM but based on what norms or expectations an opponent might have, and not on its general beliefs.

Through this work we have provided a general methodology for updating and augmenting an OM, based on an agent's experience obtained through dialogues. This methodology is based on two mechanisms respectively responsible for updating and augmenting an OM. In relation to the latter, we provided a method for building a graph between related arguments asserted by a modeller's opponents, referred to a RG, and proposed an augmentation mechanism, enabling an agent to augment its current beliefs about its opponents beliefs by including additional information (arguments), that is of high likelihood to be related to what the opponent is currently assumed to know. Thus, we enabled an agent to also account in its strategizing for the possibility that additional information may also be known to its opponents.

Finally, we defined and analysed a Monte-Carlo simulation which enabled us to infer the likelihood of those additional arguments in a tractable and efficient way. We are aware that more investigation is needed with respect to relying on alternative contextual factors for quantifying the likelihood between elements in a RG, such as the level of a participant's membership in a group, and this is something we intend to investigate in the future. We also intend to evaluate the effectiveness of our approach when employed in accordance with trust related semantics [Y. Tang and S. Parsons, 2010] through which one may define the trustworthiness of an agent's utterances against its actual beliefs.