Tech Reports

ULCS-02-028

Optimal Utterances in Dialogue Protocols

Paul E. Dunne and Peter McBurney

---

Abstract

Dialogue protocols have been the subject of considerable attention with respect to their potential applications in multi-agent system environments. Formalisations of such protocols define classes of dialogue locutions, concepts of a dialogue state, and rules under which a dialogue proceeds. One important consideration in implementing a protocol concerns the criteria an agent should apply in choosing which utterance will constitute its next contribution to a discussion in progress: ideally, an agent should select a locution that (by some measure) "optimises" the outcome. The precise interpretation of "optimises" is, however, something that may vary greatly depending on the nature and intent of a dialogue area. Thus, in dialogue models of bidding and bargaining one widely studied concept of "optimality" is that each agent's selected locution affords a particular utility value to that agent, which is "maximal" in the sense that no agent can gain greater utility by unilaterally deviating from its choice. This concept of optimality, while suitable for scenarios such as bargaining, is, arguably, less appropriate for other areas. If we consider "persuasion" protocols, where one agent's intention is to convince others of the validity or invalidity of a specific proposition, then optimality might be better regarded in the sense of "choice of locution that results in a 'minimal length'I> debate": thus the agent defending a hypothesis tries to select utterances that will convince other participants of the validity of this hypothesis after "as few locutions as possible". We present a formal setting for considering the problem of deciding if a particular utterance in the context of a persuasion dialogue is optimal in this sense. We show that, in general, this decision problem is both NP-hard and co-NP-hard. Keywords: Agent Communication Languages, Argumentation and Persuasion, Computational Complexity, Dialogue Protocols, Locution Selection.

[Full Paper]

---

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.