A Multiple Negotiations Model Considering Interdependence between Discrete Issues Across Negotiations

Abstract

The research of multiple negotiations considering issue interdependence across negotiations is considered as a complex research topic in agent negotiation. In the multiple negotiations scenario, an agent conducts multiple negotiations with opponents for different negotiation goals, and issues in a single negotiation might be interdependent with issues in other negotiations. Moreover, the utility functions involved in multiple negotiations might be nonlinear, e.g., the issues involved in multiple negotiations are discrete. Considering this research problem, the current work may not well handle multiple interdependent negotiations with complex utility functions, where issues involved in utility functions are discrete. Regarding utility functions involving discrete issues, an agent may not find an offer exactly satisfying its expected utility during the negotiation process. Furthermore, as sub-offers on issues in every single negotiation might be restricted by the interdependence relationships with issues in other negotiations, it is even harder for the agent to find an offer satisfying the expected utility and all involved issue interdependence at the same time, leading to a high failure rate of processing multiple negotiations as a final outcome. To resolve this challenge, this paper presents a negotiation model for multiple negotiations, where interdependence exists between discrete issues across multiple negotiations. By introducing the formal definition of “interdependence between discrete issues across negotiations”, the proposed negotiation model applies the multiple alternating offers protocol, the clustered negotiation procedure and the proposed negotiation strategy to handle multiple interdependent negotiations with discrete issues. In the proposed strategy, the “tolerance value” is introduced as an agent’s consideration to balance between the overall negotiation goal and the negotiation outcomes. The experimental results show that, 1) the proposed model well handles the multiple negotiations with interdependence between discrete issues, 2) the proposed approach is able to help agents in the decision-making process of proposing acceptable offers, 3) an agent can choose a proper “tolerance value” to balance between the success rate of multiple negotiations and its expected utility.

Keywords

multiple negotiations / discrete issues / interdependence relationships / nonlinear utility functions

References

[1] Alam M, Rogers A, Ramchurn S. Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

[2] Faratin P, Sierra C, Jennings N. Negotiation decision functions for autonomous agents. Robotics and Autonomous Systems, 1998, 24(3): 159-182.

[3] Fatima S, Wooldridge M, Jennings N. Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems, 2002

[4] Fatima S, Wooldridge M, Jennings N. An agenda-based framework for multi-issue negotiation. Artificial Intelligence, 2004, 152(1): 1-45.

[5] Fatima S, Wooldridge M, Jennings N. Multi-issue negotiation with deadlines. Journal of Artificial Intelligence Research, 2006, 27: 381-417.

[6] Fatima S, Wooldridge M, Jennings N. Proceedings of the 8th International Workshop on Agent Mediated Electronic Commerce, 2006

[7] Hu Y, Gao Y, An B. Multiagent reinforcement learning with unshared value functions. IEEE Transactions on Cybernetics, 2015, 45(4): 647-662.

[8] Ito T, Klein M, Hattori H. Proceedings of the 21st National Conference on Artificial Intelligence, 2006

[9] Ito T, Hattori H, Klein M. Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007

[10] Ito T, Klein M, Hattori H. A multi-issue negotiation protocol among agents with nonlinear utility functions. Multiagent and Grid Systems, 2008, 4(1): 67-83.

[11] Lai G, Sycara K, Li C. A decentralized model for multi-attribute negotiations with incomplete information and general utility functions. Multiagent and Grid Systems, 2008, 4(1): 45-65.

[12] Mansour K, Kowalczyk R, Wosko M. Knowledge Engineering and Management, 2014

[13] Mansour K, Kowalczyk R. An approach to one-to-many concurrent negotiation. Group Decision and Negotiation, 2014, 24(1): 1-22.

[14] Mansour K, Kowalczyk R. Coordinating the bidding strategy in multiissue multiobject negotiation with single and multiple providers. IEEE Transactions on Cybernetics, 2015, 45(10): 2261-2272.

[15] Niu L, Ren F, Zhang M. Proceedings of 17th International Conference on Autonomous Agents and Multiagent Systems, 2018

[16] Nguyen T, Jennings N. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004

[17] Paurobally S, Turner P, Jennings N. Automating negotiation for m-services. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2003, 33(6): 709-724.

[18] Ren F, Zhang M. Bilateral single-issue negotiation model considering nonlinear utility and time constraint. Decision Support Systems, 2014, 60: 29-38.

[19] Ren F, Zhang M, Miao C, Shen Z. Optimization of multiple related negotiation through multi-negotiation network. Engineering and Management, 2010

[20] Rubinstein A. Perfect equilibrium in a bargaining model. Econometrica, 1982, 50(1): 97-109.

[21] Williams C, Robu V, Gerding E, Jennings N. Proceedings of 20th European Conference on Artificial Intelligence, 2012

[22] Zhang X, Lesser V. Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems, 2002

[23] Zhang X, Lesser V. Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, 2007

[24] Zhang X, Lesser V, Podorozhny R. Multidimensional, multistep negotiation. Autonomous Agents and Multi-Agent Systems, 2005, 10(1): 5-40.