Reasoning about commitments in multiple concurrent negotiations

ABSTRACT

Automated negotiation by software agents is a key enabling technology for agent mediated e-commerce. To this end, this paper considers an important class of such negotiations - namely those in which an agent engages in multiple concurrent bilateral negotiations for a good or service. In particular, we consider the situation in which a buyer agent is looking for a single service provider from a number of available ones in its environment. By bargaining simultaneously with these providers and interleaving partial agreements that it makes with them, a buyer can reach good deals in an efficient manner. However, a key problem in such encounters is managing commitments since an agent may want to make intermediate deals (so that it has a definite agreement) with other agents before it gets to finalize a deal at the end of the encounter. To do this effectively, however, the agents need to have a flexible model of commitments that they can reason about in order to determine when to commit and to decommit. This paper provides and evaluates such a commitment manager and integrates it into the negotiation model.

References

1. M. Andersson and T. Sandholm. Leveled commitment contracts with myopic and strategic agents. In In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 38--44, 1998.
2. A. Byde, M. Yearworth, K. Y. Chen, and C. Bartolini. Autona: A system for automated multiple 1-1 negotiation. In Proceedings of the 2003 IEEE International Conference on Electronic Commerce, pages 59--67, Newport Beach, CA, USA, 2003. IEEE Computer Society.
3. P. Cohen. Empirical Methods for Artificial Intelligence. MIT Press, Cambridge, Massachusetts, 1995.
4. C. B. Excelente-Toledo, R. A. Bourne, and N. R. Jennings. Reasoning about commitments and penalties for coordination between autonomous agents. In Proceedings of the 5th Int Conf on Autonomous Agents (Agents-2001), pages 131--138, Montreal, Canada, 2001.
5. P. Faratin. Automated Service Negotiation Between Autonomous Computational Agents. PhD thesis, Queen Mary College, London, England, 2001.
6. P. Faratin, C. Sierra, and N. Jennings. Negotiation decision functions for autonomous agents. Robotics and Autonomous Systems, 24(3-4):159--182, 1997.
7. N. R. Jennings. Commitments and conventions: The foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8(3):223--250, 1993.
8. S. Kraus. Strategic Negotiation in Multi-Agent Environments. MIT Press, Cambridge, USA, 2001.
9. S. E. Lander and V. R. Lesser. Sharing meta-information to guide cooperative search among heterogeneous reusable agents. IEEE Trans. Knowl. Data Eng., 9(2):193--208, 1997.
10. A. R. Lomuscio, M. Wooldridge, and N. R. Jennings. A classification scheme for negotiation in electronic commerce. Int. J. of Group Decision and Negotiation, 12(1):31--56, 2003.
11. T. D. Nguyen and N. R. Jennings. A heuristic model for concurrent bi-lateral negotiations in incomplete information settings. In Proceedings of the 18th International Joint Conference on AI, pages 1467--1469, Acapulco, Mexico, 2003.
12. T. D. Nguyen and N. R. Jennings. Coordinating multiple concurrent negotiations. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multi Agent Systems (to appear), pages 1064--1071, New York, USA, 2004.
13. T. J. Norman, A. Preece, S. Chalmers, N. R. Jennings, M. Luck, V. D. Dang, T. D. Nguyen, V. Deora, J. Shao, A. Gray, and N. Fiddian. Agent-based formation of virtual organisations. Int. J. Knowledge Based Systems (to appear), 17(2-4):103--111, 2004.
14. I. Rahwan, R. Kowalczyk, and H. H. Pham. Intelligent agents for automated one-to-many e-commerce negotiation. Twenty-Fifth Australian Computer Science Conference, 4:197--204, 2002.
15. H. Raiffa. The Art and Science of Negotiation. Havard University Press, Cambridge, USA, 1982.
16. J. S. Rosenschein and G. Zlotkin. Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT Press, Cambridge, USA, 1994.
17. A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97--109, 1982.
18. T. W. Sandholm and V. R. Lesser. Leveled commitment contracts and strategic breach. Games and Economic Behavior, 35:212--270, 2001.
19. S. Sen and E. Durfee. The role of commitment in cooperative negotiation. International Journal on Intelligent and Cooperative Information Systems, 3(1):67--81, 1994.
20. R. G. Smith. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, 29(12):1104--1113, 1980.