Accepting optimally in automated negotiation with incomplete information

ABSTRACT

When a negotiating agent is presented with an offer by its opponent, it is faced with a decision: it can accept the offer that is currently on the table, or it can reject it and continue the negotiation. Both options involve an inherent risk: continuing the negotiation carries the risk of forgoing a possibly optimal offer, whereas accepting runs the risk of missing out on an even better future offer. We approach the decision of whether to accept as a sequential decision problem, by modeling the bids received as a stochastic process. We argue that this is a natural choice in the context of a negotiation with incomplete information, where the future behavior of the opponent is uncertain. We determine the optimal acceptance policies for particular opponent classes and we present an approach to estimate the expected range of offers when the type of opponent is unknown. We apply our method against a wide range of opponents, and compare its performance with acceptance mechanisms of state-of-the-art negotiation strategies. The experiments show that the proposed approach is able to find the optimal time to accept, and improves upon widely used existing acceptance mechanisms.

References

1. Tim Baarslag, Katsuhide Fujita, Enrico H. Gerding, Koen Hindriks, Takayuki Ito, Nicholas R. Jennings, Catholijn Jonker, Sarit Kraus, Raz Lin, Valentin Robu, and Colin R. Williams. Evaluating practical negotiating agents: Results and analysis of the 2011 international competition. Artificial Intelligence Journal, 2012.
2. Tim Baarslag, Koen Hindriks, Catholijn M. Jonker, Sarit Kraus, and Raz Lin. The first automated negotiating agents competition (ANAC 2010). In New Trends in Agent-based Complex Automated Negotiations, pages 113--135, Berlin, Heidelberg, 2012. Springer-Verlag.
3. Mai Ben Adar, Nadav Sofy, and Avshalom Elimelech. Gahboninho: Strategy for balancing pressure and compromise in automated negotiation. In Complex Automated Negotiations: Theories, Models, and Software Competitions, pages 205--208. Springer Berlin Heidelberg, 2013.
4. Tibor Bosse and Catholijn M. Jonker. Human vs. computer behaviour in multi-issue negotiation. In Proceedings of the Rational, Robust, and Secure Negotiation Mechanisms in Multi-Agent Systems, RRS '05, pages 11--, Washington, DC, USA, 2005. IEEE Computer Society.
5. Robert M. Coehoorn and Nicholas R. Jennings. Learning on opponent's preferences to make effective multi-issue negotiation trade-offs. In Proceedings of the 6th international conference on Electronic commerce, ICEC '04, pages 59--68, New York, USA, 2004. ACM.
6. Morris H. DeGroot. Optimal statistical decisions. McGraw-Hill, New York, 1970.
7. A.S.Y. Dirkzwager, M.J.C. Hendrikx, and J.R. Ruiter. The negotiator: A dynamic strategy for bilateral negotiations with time-based discounts. In Complex Automated Negotiations: Theories, Models, and Software Competitions, pages 217--221. Springer Berlin Heidelberg, 2013.
8. P. Faratin, C. Sierra, and N. R. Jennings. Negotiation decision functions for autonomous agents. Int. Journal of Robotics and Autonomous Systems, 24(3--4):159--182, 1998.
9. S. S. Fatima, M. Wooldridge, and N. R. Jennings. An agenda-based framework for multi-issue negotiation. Artificial Intelligence, 152(1):1--45, 2004.
10. S. Shaheen Fatima, Michael Wooldridge, and Nicholas R. Jennings. Optimal negotiation strategies for agents with incomplete information. In Revised Papers from the 8th International Workshop on Intelligent Agents VIII, ATAL '01, pages 377--392, London, UK, UK, 2002. Springer-Verlag.
11. Asaf Frieder and Gal Miller. Value model agent: A novel preference profiler for negotiation with agents. In Complex Automated Negotiations: Theories, Models, and Software Competitions, pages 199--203. Springer Berlin Heidelberg, 2013.
12. Dhananjay K. Gode and Shyam Sunder. Allocative efficiency in markets with zero intelligence (zi) traders: Market as a partial substitute for individual rationality. Journal of Political Economy, 101(1):119--137, 1993.
13. Shogo Kawaguchi, Katsuhide Fujita, and Takayuki Ito. Agentk2: Compromising strategy based on estimated maximum utility for automated negotiating agents. In Complex Automated Negotiations: Theories, Models, and Software Competitions, pages 235--241. Springer Berlin Heidelberg, 2013.
14. Gregory E. Kersten and Grant Zhang. Mining inspire data for the determinants of successful internet negotiations. InterNeg Research Papers INR 04/01 Central European Journal of Operational Research, 2003.
15. Sarit Kraus, Jonathan Wilkenfeld, and Gilad Zlotkin. Multiagent negotiation under time constraints. Artificial Intelligence, 75(2):297 -- 345, 1995.
16. Thijs Krimpen, Daphne Looije, and Siamak Hajizadeh. Hardheaded. In Complex Automated Negotiations: Theories, Models, and Software Competitions, pages 223--227. Springer Berlin Heidelberg, 2013.
17. Bjorn Leonardz. To stop or not to stop. Some elementary optimal stopping problems with economic interpretations. Almqvist & Wiksell, Stockholm,, 1973.
18. Raz Lin, Sarit Kraus, Tim Baarslag, Dmytro Tykhonov, Koen Hindriks, and Catholijn M. Jonker. Genius: An integrated environment for supporting the design of generic automated negotiators. Computational Intelligence, 2012.
19. Raz Lin, Sarit Kraus, Jonathan Wilkenfeld, and James Barry. Negotiating with bounded rational agents in environments with incomplete information using an automated agent. Artificial Intelligence, 172(6--7):823 -- 851, 2008.
20. Chhaya Mudgal and Julita Vassileva. Bilateral negotiation with incomplete and uncertain information: A decision-theoretic approach using a model of the opponent. In Proceedings of the 4th International Workshop on Cooperative Information Agents IV, The Future of Information Agents in Cyberspace, CIA '00, pages 107--118, London, UK, UK, 2000. Springer-Verlag.
21. Ariel Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97--109, 1982.
22. Santiago Sánchez-Pagés. The use of conflict as a bargaining tool against unsophisticated opponents. ESE discussion papers, Edinburgh School of Economics, University of Edinburgh, 2004.
23. Ingolf Stahl. Bargaining theory. Economic Research Institute, Stockholm, 1972.
24. Colin R. Williams, Valentin Robu, Enrico H. Gerding, and Nicholas R. Jennings. Using gaussian processes to optimise concession in complex negotiations against unknown opponents. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence. AAAI Press, January 2011.
25. Colin R. Williams, Valentin Robu, Enrico H. Gerding, and Nicholas R. Jennings. Iamhaggler: A negotiation agent for complex environments. In New Trends in Agent-based Complex Automated Negotiations, pages 151--158, Berlin, Heidelberg, 2012. Springer-Verlag.
26. D. Zeng and K. Sycara. Bayesian learning in negotiation. International Journal of Human Computer Systems, 48:125--141, 1998.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Intelligent agents

      • Multi-agent systems