Optimal utterances in dialogue protocols

ABSTRACT

Dialogue protocols have been the subject of considerable attention with respect to their potential applications in multiagent 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 'optimise' is, however, something that may vary greatly depending on the nature and intent of a dialogue area. 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 regarded in the sense of "choice of locution that results in a 'minimal length' 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.

References

1. T. J. M. Bench-Capon. Specification and implementation of Toulmin dialogue game. In J. C. Hage et al., editor, Legal Knowledge Based Systems, pages 5--20. GNI, 1998.]]
2. T. J. M. Bench-Capon, P. E. Dunne, and P. H. Leng. A dialogue game for dialectical interaction with expert systems. In Proc. 12th Annual Conf. Expert Systems and their Applications, pages 105--113, 1992.]]
3. C. Cayrol, S. Doutre, and J. Mengin. Dialectical proof theories for the credulous preferred semantics of argumentation frameworks. In Sixth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU-2001), pages 668--679. Lecture Notes in A.I., 2143, Springer, 2001.]]
4. V. Conitzer and T. Sandholm. Complexity results about Nash equilibria. Technical Report CMU-CS-02-135, School of Computer Science, Carnegie-Mellon University, May 2002.]]
5. M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. Communications of the ACM, 5:394--397, 1962.]]
6. M. Davis and H. Putnam. A computing procedure for quantification theory. Journal of the ACM, 7:201--215, 1960.]]
7. F Dignum and M. Greaves (editors). Issues in Agent Communication. Springer-Verlag, 2000.]]
8. S. Doutre and J. Mengin. Preferred extensions of argumentation frameworks: Query answering and computation. In First Intern. Joint Conf. Automated Reasoning (IJCAR 2001), pages 272--288. Lecture Notes in A.I., 2083, Springer, June 2001.]]
9. P. E. Dunne. Computability Theory - Concepts and Applications. Ellis-Horwood, 1991.]]
10. P. E. Dunne. Prevarication in dispute protocols. Technical Report ULCS-02-025, Dept. of Comp. Sci., Univ. of Liverpool, 2002.]]
11. P. E. Dunne and T. J. M. Bench-Capon. Two party immediate response disputes: Properties and efficiency. Technical Report ULCS-01-005, Dept. of Comp. Sci., Univ. of Liverpool, (to appear Artificial Intelligence)]]
12. J. Glazer and A. Rubinstein. Debates and decisions: on a rationale of argumentation rules. Games and Economic Behavior, 36(2):158--173, 2001.]]
13. T. F. Gordon. The Pleadings Game: An Artificial Intelligence Model of Procedural Justice. Kluwer Academic, Dordrecht, 1995.]]
14. S. Kraus. Strategic negotiation in multiagent environments. MIT Press, 2001.]]
15. P. Liberatore. On the complexity of choosing the branching literal in DPLL. Artificial Intelligence, 116:315--326, 2000.]]
16. A. R. Lodder. Dialaw: On legal justification and Dialogue Games. PhD thesis, Univ.of Maastricht, 1998.]]
17. P. McBurney, R. van Eijk, S. Parsons, and L. Amgoud. A dialogue-game protocol for agent purchase negotiations. J. Autonomous Agents and Multiagent Systems, in press.]]
18. P. McBurney and S. Parsons. Representing epistemic uncertainty by means of dialectical argumentation. Annals of Mathematics and AI, 32(1--4):125--169, 2001.]]
19. P. McBurney and S. Parsons. Games that agents play: A formal framework for dialogues between autonomous agents. J. Logic, Language and Information, 11:315--334, 2002.]]
20. P. McBurney and S. Parsons. Chance Discovery using dialectical argumentation. In T. Terano et al., editors, New Frontiers in Artificial Intelligence, pages 414--424. Lecture Notes in A.I., 2253, Springer, 2001.]]
21. P. McBurney, S. Parsons, and M. W. Johnson. When are two protocols the same? In M. P. Huget, F. Dignum and J. L. Koning, editors, Agent Communications Languages and Conversation Policies, Proc. AAMAS-02 Workshop, Bologna, Italy, 2002.]]
22. P. McBurney, S. Parsons, and M. J. Wooldridge. Desiderata for agent argumentation protocols. In Proc. First Intern. Joint Conf. on Autonomous Agents and Multiagent Systems, pages 402--409. ACM Press, 2002.]]
23. S. Parsons, C. A. Sierra, and N. R. Jennings. Agents that reason and negotiate by arguing. J. Logic and Computation, 8(3):261--292, 1998.]]
24. S. Parsons, M. J. Wooldridge, and L. Amgoud. An analysis of formal inter-agent dialgoues. In Proc. First Intern. Joint Conf. Autonomous Agents and Multiagent Systems, pages 394--401. ACM Press, 2002.]]
25. H. Prakken. Logical Tools for Modelling Legal Argument. Kluwer Academic, Dordrecht, 1997.]]
26. C. Reed. Dialogue frames in agent communications. In Y. Demazeau, editor, Proc. 3rd Intern. Conf. Multiagent Systems (ICMAS-98), pages 246--253. IEEE Press, 1998.]]
27. G. Vreeswijk and H. Prakken. Credulous and sceptical argument games for preferred semantics. In Proc. JELIA'2000, The 7th European Workshop on Logic for Artificial Intelligence., pages 224--238, Berlin, 2000. Lecture Notes in A.I., 1919, Springer.]]
28. D. N. Walton and E. C. W. Krabbe. Committment in Dialogue: Basic Concepts of Interpersonal Reasoning. SUNY Press, Albany, 1995.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Cooperation and coordination

      • Multi-agent systems

• Theory of computation

  • Computational complexity and cryptography

    • Interactive proof systems

    • Proof complexity

  • Logic

    • Proof theory