Assimilating ontological additions in convergent negotiation protocols

ABSTRACT

We consider negotiation protocols in which each offer contains a price and a description from some given ontology. If the opposing negotiation agents do not share the same version of this ontology, for instance because not all have been made aware of the latest changes, then a fixed communication protocol may be expected to fail when one opponent is faced with an offer including a concept novel to it. However, the communication may proceed if the agent is allowed to ask for, receive and assimilate the missing information. This information may come from the other partner, a trusted source, or the human that the agent is serving. We propose a method whereby assimilation is accomplished dynamically so that existing conversations do not need to be abandoned. Our setting employs negotiation protocols that are required to be convergent, i.e. to make progress by exploring a finite negotiation space and thus terminate, either with a mutually acceptable offer or with an indication that no such offer exists. We show that existing convergent negotiation protocols, when applied in a setting that allows assimilation of monotonic additions, retain the property of convergence despite the permissibility of messages that do not meet the condition of making progress. We motivate the work within an e-marketplace where negotiation is over product features and can lead the conversation deeper into specific features, about which some fact may not be mutually known until more information is shared.

REFERENCES

• 1: Association for the Advancement of Artificial Intelligence. Belief revision, http://www.aaai.org/aitopics/html/belief.html, Accessed 2007 June 12.
• 2: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 3: F. Baader and U. Sattler. An overview of tableau algorithms for description logics. Studia Logica, 69:5--40, 2001.
• 4: S. Buffett, K. Jia, S. Liu, B. Spencer, and F. Wang. Negotiating exchanges of P3P-labeled information for compensation. Computational Intelligence, 20(4):663--677, 2004.
• 5: S. Buffett, N. Scott, B. Spencer, M. M. Richter, and M. W. Fleming. Determining internet users' values for private information. In Second Annual Conference on Privacy, Security and Trust (PSTŠ04), pages 79--88, 2004.
• 6: Scott Buffett , Luc Comeau , Bruce Spencer , Michael W. Fleming, Detecting opponent concessions in multi-issue automated negotiation, Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet, August 13-16, 2006, Fredericton, New Brunswick, Canada [doi>10.1145/1151454.1151472]
• 7: P. C. Fishburn. Utility theory. Management Science, 14:335--378, 1968.
• 8: D. Li and Y. Yue. Negotiation based on plan recognition and fuzzy sets for multiobjective process planning. In Artificial Intelligence and Soft Computing, 2005.
• 9: F. Sadri, F. Toni, and P. Torroni. Logic agents, dialogues and negotiation: an abductive approach. In AISBŠ01 Convention, 2001.
• 10: V. Tamma, M. Wooldridge, and I. Dickinson. An ontology for automated negotiation, 2002.
• 11: Paolo Torroni, A study on the termination of negotiation dialogues, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545103]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms

Keywords:
assimilation, convergent negotiation, negotiating agents, negotiation protocols, ontologies