Opponent modelling in automated multi-issue negotiation using Bayesian learning

ABSTRACT

The efficiency of automated multi-issue negotiation depends on the availability and quality of knowledge about an opponent. We present a generic framework based on Bayesian learning to learn an opponent model, i.e. the issue preferences as well as the issue priorities of an opponent. The algorithm proposed is able to effectively learn opponent preferences from bid exchanges by making some assumptions about the preference structure and rationality of the bidding process. The assumptions used are general and consist among others of assumptions about the independency of issue preferences and the topology of functions that are used to model such preferences. Additionally, a rationality assumption is introduced that assumes that agents use a concession-based strategy. It thus extends and generalizes previous work on learning in negotiation by introducing a technique to learn an opponent model for multi-issue negotiations. We present experimental results demonstrating the effectiveness of our approach and discuss an approximation algorithm to ensure scalability of the learning algorithm.

REFERENCES

• 1: Tibor Bosse , Catholijn M. Jonker, Human vs. Computer Behaviour in Multi-Issue Negotiation, Proceedings of the Rational, Robust, and Secure Negotiation Mechanisms in Multi-Agent Systems (RRS'05) on Multi-Agent Systems, p.11, July 25-25, 2005 [doi>10.1109/RRS.2005.8]
• 2: Robert M. Coehoorn , Nicholas R. Jennings, Learning on opponent's preferences to make effective multi-issue negotiation trade-offs, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands [doi>10.1145/1052220.1052229]
• 3: Koen Hindriks , Catholijn M. Jonker , Dmytro Tykhonov, Analysis of Negotiation Dynamics, Proceedings of the 11th international workshop on Cooperative Information Agents XI, September 19-21, 2007, Delft, The Netherlands [doi>10.1007/978-3-540-75119-9_3]
• 4: Faratin, P., Sierra, C., and Jennings, N. R. 1998. Negotiation Decision Functions for Autonomous Agents, in: Int. Journal of Robotics and Autonomous Systems, 24 (3--4) 159--182.
• 5: Faratin, P., Sierra, C., and Jennings, N. R. 2003. Using Similarity Criteria to Make Negotiation Trade-Offs, Journal of Artificial Intelligence, 142 (2), pp. 205--237.
• 6: Catholijn M. Jonker , Valentin Robu , Jan Treur, An agent architecture for multi-attribute negotiation using incomplete preference information, Autonomous Agents and Multi-Agent Systems, v.15 n.2, p.221-252, October 2007 [doi>10.1007/s10458-006-9009-y]
• 7: Lin R., Kraus, S., Wilkenfeld, J., Barry, J. 2006. An Automated Agent for Bilateral Negotiation with Bounded Rational Agents with Incomplete Information. ECAI 2006, pp. 270--274.
• 8: Narayanan, V., Jennings, N. R. 2006. Learning to Negotiate Optimally in Non-stationary Environments, CIA 2006, LNAI 4149, pp. 288--300.
• 9: Niimura, T., Ozawa, K., Hirano, O., 2001. Fuzzy Set-based Decision Support System for Transactions of Electricity in A Deregulated Environment, IFSA World Congress, pp. 87--92.
• 10: Osborne, M. J. and Rubinstein, A. 1994, A Course in Game Theory, The MIT Press.
• 11: Raiffa, H. 1982. The Art and Science of Negotiation, Harvard University Press.
• 12: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 13: Dajun Zeng , Katia Sycara, Bayesian learning in negotiation, International Journal of Human-Computer Studies, v.48 n.1, p.125-141, Jan., 1998 [doi>10.1006/ijhc.1997.0164]
• 14: Zeng, D., and Sycara, K. 1997. Benefits of Learning in Negotiation, in Proc. of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), Providence, RI.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Economics, Experimentation, Performance, Theory

Keywords:
Bayesian learning, automated multi-issue negotiation, opponent modelling, preference profiles