Discovering Inconsistency through Examination Dialogues

1 Introduction

One important class of dialogue not found in the influential typology of [Walton and Krabbe, 1995] is the examination dialogue. In such dialogues one party - the Questioner Q - elicits statements and opinions from another - the Responder R - with the aim of discovering R's position on some topic, either to gain insight into R's understanding and knowledge of the topic, or to expose an inconsistency in R's position. Examples include education by the Socratic method, viva voce examination, cross examination of witnesses, and political interviews. In contrast to information seeking or inquiry dialogues, Q may already have beliefs on the topic: unlike persuasion dialogues, Q may have no intention of converting R to his position. Examination dialogues may, however, be nested within information seeking dialogues: probing for inconsistency increases confidence in the veracity of R's beliefs; similarly, in persuasion dialogues, exposing inconsistency is a useful prelude to persuasion.

In examination dialogues the dialogue process occurs within an environment of relevant facts, arguments, and related issues that is (at least implicitly) recognised and understood by both parties, e.g. common knowledge of the subject in educational settings, matters of specific policies and legislation in political interviews; issues of evidence and witness testimony in trials; details of incidents under investigation in questioning suspects. In this paper our aim is to describe a generic abstract model within which the evolution of such examination dialogues can be analysed. In addition we outline an approach intended to aid Q in selecting questions.

The foundational element for our model is provided by the Value-based Argument Frameworks (VAFs) of [BenchCapon, 2003], a development of the classical argument systems of [Dung, 1995], which offer a richer interpretation of the concept of an argument x "attacking" an argument y. In addition to the computational advantages outlined in [BenchCapon, 2003], further indications that VAFs provide a suitable mechanism for our analysis is presented by the methods discussed in [Dunne and Bench-Capon, 2004b]. A brief overview of VAFs is given in Section 2 and our model of examination dialogue presented in Section 3. In Section 4 we outline some algorithmic aspects involving argument selection in this scheme. Conclusions are presented in Section 5.

2 Value-Based Argument Frameworks

Value-based argumentation frameworks are introduced in [Bench-Capon, 2003] as a development of the model of argument systems via directed graphs H = 〈X,A〉 proposed in [Dung, 1995]. A value-based argumentation framework (VAF) is defined as 〈X,A, V, η〉, where 〈X,A〉 is an argument system, V = {v1, v2, . . . , vk} is a set of k values, and η : X → V associates a value η(x) ∈ V with each argument x ∈ X . An audience ϑ for a VAF 〈X , A, V, η〉 is a transitive and irreflexive binary relation on V. A pair 〈vi, vj〉 in ϑ is referred to as 'vi is preferred to vj' with respect to ϑ.

Ideas analogous to those in Dung's argument system are now defined relative to some audience: S ⊆ X is conflict-free w.r.t. ϑ if ∀ x, y ∈ S: 〈x, y〉 ∈ A ⇒ 〈η(y), η(x)〉 ∈ ϑ; x is acceptable to S w.r.t. ϑ if ∀y ∈ X: 〈y, x〉 ∈ A ⇒ (〈η(x), η(y)〉 ∈ ϑ or ∃ z ∈ S s.t. 〈z, y〉 ∈ A and 〈η(y), η(z)〉 /∈ ϑ); S is admissible w.r.t ϑ if each x ∈ S is acceptable to S w.r.t. ϑ.

3 Examination Dialogues in VAFs

In keeping with the observation that debates of interest take place within some recognised context, we view this context as a VAF G = 〈X,A, V, η〉. A debate in the context of G is a sequence µ1µ2 . . . µj of at most 2|X |+1 moves: odd indexed moves being played by Q and even indexed moves by R.

Suppose the next move to be made is µ2i-1 (i ≥ 1). The options for the next move(s) - µ2i-1 · µ2i - are,

• (a) µ2i-1 = ASK(p): Q asks R their view on p ∈ X ; ASK(p) is legal provided that it has not occurred at an earlier point in the debate, i.e. ∀ j < i µ2j-1 ̸= ASK(p). The response µ2i is one of ACCEPT(p) (R agrees with p); DENY(p) (R does not agree with p); or NO-COMMENT(p) (R refuses to say anything about p).
• (b) µ2i-1 = FOUND(p, STAT(p)): here p is an argument to which R has responded NO-COMMENT(p) after ASK(p) earlier. Q expresses a claim to know R's view of p as accepted (STAT = ACCEPT) or otherwise (STAT = DENY).
• (c) µ2i-1 = RESOLVE(S): S is a set of arguments all of which have been asked about with none receiving a "NOCOMMENT" reply. Q asserts that at least one of these replies cannot be correct with respect to the context G.
• (d) µ2i-1 = CONCEDE: Q can neither determine R's view in respect of NO-COMMENT arguments nor expose inconsistencies in the collection of "definite" responses.

The debate ends once one of the moves (b)-(d) is played. Noting that we assume (b) or (c) can be played only if Q may justify the claimmade, these result in a "win" for Q, whereas (d) results in a "win" for R.

As a very simple example consider: X = {x, y, z}; A = {〈x, y〉, 〈y, z〉, 〈z, x〉}; V = {A, B}; and η(x) = η(z) = A; η(y) = B. If R replies NO-COMMENT(y) or DENY(y) to ASK(y) then Q wins (by playing FOUND(y, ACCEPT) or RESOLVE(y)) since, regardless of whether R's audience includes 〈A, B〉 or 〈B, A〉, R must accept y. On the other hand - assuming R replies ACCEPT(y) - the only responses regarding R's view of {x, z} that could lead to a win for Q are when exactly one NO-COMMENT occurs; or it is claimed both are accepted; or both denied. Notice that may R report 〈ACCEPT(x), DENY(z)〉 (or vice versa) despite believing otherwise and Q will be unable to detect this.

In general, within such debate contexts, both players have a number of non-trivial strategic issues to resolve. In particular, assuming that R wishes to hide information (and therefore will either respond "NO-COMMENT" and/or misreport some views), R may have to form a partition of X determining those queries to which false and true responses will be given. We note that, as indicated in the small example above, refusing to comment on any argument or misreporting the status of every argument may fail to be a successful strategy; moreover it is an easy consequence of [Dunne and Bench-Capon, 2004a] that the decision problem faced by R determining if classifying p as NO-COMMENT loses, is coNP-complete.

4 Choosing Arguments

We conclude the brief technical discussion, by outlining an approach to query selection that is based on a translation to propositional formulae. Given 〈X,A, V, η〉, in order for p ∈

X to be accepted w.r.t. at least one audience ϑ, it must belong to an admissible w.r.t. ϑ set S ⊆ X . Consider disjoint sets of propositional variables Z and W = {wi,j : 1 ≤ i ̸= j ≤ k}. Define the function, f(Z,W) via: f(α, β) = ⊤ if and only if the subset S of X indicated by α, i.e. xi ∈ S ⇔ αi = ⊤, is admissible with the binary relation ϑ encoded in β, i.e. 〈vi, vj〉 ∈ ϑ ⇔ βi,j = ⊤ and this relationship is an audience, i.e. irreflexive and transitive. This function can be described by a "short" propositional formula Φf(Z,W) of length O(|A| + k3 ) that with the addition of at most O(|A|) auxiliary variables (D) translates to an equivalent CNF formula, Ψf (Z, W, D) with O(|A| + k3 ) clauses, the longest of which contains at most 2 +maxx∈X |{y : 〈y, x〉 ∈ A}| literals. Using Ψf the strategy pursued by Q will be to obtain responses from R that result in Ψf evaluating to ⊥ (i.e. R is inconsistent) or to infer the unique instantiation of zi that satisfies Ψf with the replies already given.

5 Conclusions and Development

We have introduced a class of question-response dialogues - examination dialogues - and modelled them using VAF schemata as the basis for representing related knowledge. A number of issues - both theoretical and applicative - form the subject of work in progress. In addition to on-going empirical investigations of argument selection strategies employing the propositional translation briefly outlined in Section 4 there are several questions of interest regarding properties of the model when the protagonists are "limited" in different ways. Thus, to what extent is Q at an advantage if an upper bound is placed on the number of "NO-COMMENT" and/or false responses R can make? Similarly, if Q is restricted to some maximum number of questions (rather than being allowed to ask about the status of every argument in X) it is likely that Q must adopt a dynamic selection mechanism (rather than choosing a set to query in advance) so as to adapt effectively to R's responses.