A speech-act-based negotiation protocol: design, implementation, and test use

ABSTRACT

Existing negotiation protocols used in Distributed Artificial Intelligence (DAI) systems rarely take into account the results from negotiation research. We propose a negotiation protocol, SANP (Speech-Act-based Negotiation Protocol), which is based on Ballmer and Brennenstuhl's speech act classification and on negotiation analysis literature. The protocol is implemented as a domain-independent system using Strudel, which is an electronic mail toolkit. A small study tested the potential use of the protocol. Although a number of limitations were found in the study, the protocol appears to have potential in domains without these limitations, and it can serve as a building block to design more general negotiation protocols.

REFERENCES

• 1: AUSTIn, J.L. 1962 How to Do Things wzth Words. Oxford University Press. Oxibrd, England.
• 2: BALLMER, T. AND BRENNENSTUHL, W. 1981. Speech Act Class~/~catton: A Study zn the Lextcal Analysis o/Enghsh Speech Actlvzty Verbs. Springer-Verlag, Berlin.
• 3: BOND, A. H. AND GASSER, L. 1988. An analysis of problems and research in DAI. In Reading tn Dtstributed Art~l~clal Intelligence, A. H. Bond and L. Gasser, Eds. Morgan Kaufmann, San Mateo, Calif., 3 35.
• 4: CHANG, M. K. AND WOO, C.C. 1992. SANP: A communication level protocol for negotiations In Decentralized A.I.Y. Demazeau and E. Werner, Eds. Vol. 3, Elsevier Science, Amsterdam, Netherlands, 31-54.
• 5: Susan E. Conry , Robert A. Meyer , Victor R. Lesser, Multistage negotiation in distributed planning, Distributed Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 6: Peter C. Cramton, Dynamic bargaining with transaction costs, Management Science, v.37 n.10, p.1221-1233, Oct. 1991
• 7: DAVIS, R. AND SMITH, R.G. 1983. Negotiation as a metaphor for distributed problem solving. Art. Intell. 20, 1, 63-109.
• 8: Edmund H. Durfee , Victor R. Lesser, Negotiating task decomposition and allocation using partial global planning, Distributed artificial intelligence: vol. 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 9: Edmund H. Durfee , Victor R. Lesser, Using partial global plans to coordinate distributed problem solvers, Distributed Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 10: FAURE, G. O. AND LE DONG, V. 1990. Social-emotional aspects of negotiation. Eur. J. Oper. Res. 46, 177-180.
• 11: GALLIERS, J. R. 1990. The positive role of conflict m cooperative multiagent systems. In Decentralized A.I., Y. Demazeau and J. P. Muller, Eds. Elsewer Science, Amsterdam, Netherlands, 33 46.
• 12: Elihu M. Gerson , Susan Leigh Star, Analyzing due process in the workplace, ACM Transactions on Information Systems (TOIS), v.4 n.3, p.257-270, July 1986 [doi>10.1145/214427.214431]
• 13: GULLIVER, P. H. 1979. Disputes and Negotations: A Cross-Cultural Perspective. Academic Press, New York.
• 14: Carl Hewitt, Open information systems semantics for distributed artificial intelligence, Artificial Intelligence, v.47 n.1-3, p.79-106, Jan. 1991 [doi>10.1016/0004-3702(91)90051-K ]
• 15: Carl Hewitt, Offices are open systems, ACM Transactions on Information Systems (TOIS), v.4 n.3, p.271-287, July 1986 [doi>10.1145/214427.214432]
• 16: Gregory E. Kersten , Wojtek Michalowski , Stan Szpakowicz , Zbig Koperczak, Restructurable representations of negotiation, Management Science, v.37 n.10, p.1269-1290, Oct. 1991
• 17: Charles C. Koo, A commitment-based communication model for distributed office environments, Proceedings of the ACM SIGOIS and IEEECS TC-OA 1988 conference on Office information systems, p.291-298, March 23-25, 1988, Palo Alto, California, United States
• 18: LEVINSON, S.C. 1983. Pragmatics. Cambridge University Press, New York.
• 19: Thomas W. Malone , Kenneth R. Grant , Kum-Yew Lai , Ramana Rao , David Rosenblitt, Semistructured messages are surprisingly useful for computer-supported coordination, ACM Transactions on Information Systems (TOIS), v.5 n.2, p.115-131, April 1987 [doi>10.1145/27636.27637]
• 20: MAYNARD, D.W. 1984. The structure of discourse in misdemeanor plea bargaining. Law Soc. Rev. 18, 1, 75-104.
• 21: PINSONNEAULT, A. AND KRAEMER, K. L. 1990. The effects of electronic meetings on group processes and outcomes. Eur. J. Oper. Res. 46, 143-161.
• 22: PRUITT, D.G. 1981. Negotiation Behavior. Academic Press, New York.
• 23: PUTNAM, L. L. AND POOLE, M.S. 1987. Conflict and negotiation. In Handbook of Organizational Communication: An Interdisctplinary Perspective, F. M. Jablin, et al., Eds. Sage, Newbury Park, Calif., 549-599.
• 24: RAHIM, M.A. 1986. Managing Conflict in Organization. Praeger, New York.
• 25: William F. Samuelson, Final-offer arbitration under incomplete information, Management Science, v.37 n.10, p.1234-1247, Oct. 1991
• 26: SE~LE, J.R. 1975. A taxonomy of illocutionary acts. In Language, Mind and Knowledge. Minnesota Studies in the Philosophy of Science, vol. 7, K. Gunderson, Ed. University of Minnesota Press, Minneapolis, 344-369.
• 27: SEARLE, J.R. 1969. Speech Acts: An Essay in the Philosophy of Language. Cambridge University Press, New York.
• 28: Allan Shepherd , Niels Mayer , Allan Kuchinsky, Strudel—an extensible electronic conversation toolkit, Proceedings of the 1990 ACM conference on Computer-supported cooperative work, p.93-104, October 07-10, 1990, Los Angeles, California, United States [doi>10.1145/99332.99345]
• 29: DMITH, 1%. U. l~SO. The contract net protocol: ii}gh level communlcatmn and control in a distributed problem solver. IEEE Troll'ls. Comput. C-29, 12, 1104 1113.
• 30: Katia P. Sycara, Problem restructuring in negotiation, Management Science, v.37 n.10, p.1248-1268, Oct. 1991
• 31: Katia P. Sycara, Multiagent compromise via negotiation, Distributed artificial intelligence: vol. 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 32: TOULMIN, S.E. 1969. The Uses of Argument. Cambridge University Press, Cambridge, Mass.
• 33: VAN EEMEREN, F. H. ANn GROOTENDORST, R. 1983. Speech Acts m Argumentoltwe Dtscussmns. Foris Publication, Dordrecht.
• 34: vAN EEMEREN, F. H., GROOTENDORS% R., AND KRmGER, T. 1984 The Study of Argumentation. Irvington, New York.
• 35: Terry Winograd , Fernando Flores, Understanding computers and cognition, Ablex Publishing Corp., Norwood, NJ, 1986
• 36: ZENG, T. 1990. An organizational communication protocol based on speech acts: Design, verification and formal specification. M.Sc. thesis, Dept. of Computer Science, Univ. of British Columbia, Vancouver, Canada.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Languages and structures

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Office automation
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

General Terms:
Design, Experimentation

Keywords:
negotiation, organizational computing systems, speech act theory