Efficient Deal Identification by Constraint Relaxation for Collaborative Decision Making Using Negotiation

Raiye Hailu; Takayuki Ito

doi:10.20965/jaciii.2014.p0608

single-jc.php

« previous

JACIII Vol.18 No.4 pp. 608-615

doi: 10.20965/jaciii.2014.p0608

(2014)

Paper:

Views over last 60 days: 885

Efficient Deal Identification by Constraint Relaxation for Collaborative Decision Making Using Negotiation

Raiye Hailu and Takayuki Ito

Nagoya Institute of Technology, Nagoya shi, Showa-ku, Gokiso-cho, Aichi 466-8555, Japan

Received:

July 24, 2013

Accepted:

February 27, 2014

Published:

July 20, 2014

Keywords:

negotiation, interdependent issues, multi agent, artificial society and economy, auction, optimization

Abstract

Negotiation is one means for making decision collaboratively. We propose efficient protocols for identifying deals in such negotiations. Specifically we focus on situations in which the negotiators must agree upon one option from among many. This work proposes solutions to problems faced when automating negotiations over multiple and interdependent issues. When negotiations are over issues that are interdependent, previous and future decisions concerning other issues affect how one decides the current issue. Therefore generally we must deal with all of the issues at the same time. To identify deals for negotiations over multiple and interdependent issues previous work has proposed a bidding based protocol that works well only when there is a high probability that agents in the negotiation have local maxima at similar positions in the contract space. This happens only when the contract space is small and the number of agents in the negotiation is low. Otherwise the protocol fails to identify deals. We propose a multi round bidding approach in which agents submit supersets of their bids from earlier rounds. A superset of a bid is created by relaxing the constraints that it satisfies. We will use the same concept of negotiation using relaxed constraints to extend a Hill Climbing (HC) protocol. HC has a linear execution time cost. Ordinarily it can not be used for complex negotiations. But we modify it so that it is used optimally and efficiently for such negotiations.

Cite this article as:

R. Hailu and T. Ito, “Efficient Deal Identification by Constraint Relaxation for Collaborative Decision Making Using Negotiation,” J. Adv. Comput. Intell. Intell. Inform., Vol.18 No.4, pp. 608-615, 2014.

Data files:

References

[1] C. Faratin, C. Sierra, and N. R. Jennings, “Using similarity criteria to make issue trade-offs in automated negotiations,” Artificial Intelligence, Vol.142, pp. 205-237, 2002.
[2] M. Fatima, M. Wooldridge, and N. R. Jennings, “Optimal negotiation of multiple issues in incomplete information settings,” The 3rd Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 1080-1087, 2004.
[3] K. Hindriks, C. Jonker, and D. Tykhonov, “Eliminating Interdependencies between Issues for Multi-issue Negotiation,” Cooperative Information Agents X (CIA2006), 2011.
[4] R. Y. K. Lau, “Towards genetically optimized multi-agent multi- issue negotiations,” The 38th Hawaii Int. Conf. On System Sciences, pp. 1080-1087, 2005.
[5] R. J. Lin and S. T. Chou, “Bilateral multi-issue negotiations in a dynamic environment,” The Agent-Mediated Electronic Commerce, 2003.
[6] M. Klein, P. Faratin, H. Sayama, and Y. Bar-yam, “Negotiating Complex Contracts,” MIT Sloan Research Paper No.4196, 2001.
[7] T. Baarslag, K. V. Jonker, and R. Lin, “The First Automated Negotiating Agents Competition (ANAC 2010),” Studies in Computational Intelligence. LNCS, Vol.383, 2010.
[8] T. Ito, H. Hattori, and M. Klein, “Multi-issue Negotiation Protocol for Agents Exploring Nonlinear Utility Spaces,” Int. Joint Conf. on Artificial Intelligence (IJCAI07), pp. 1347-1352, 2007.
[9] M. Klein, P. Faratin, H. Sayama, and Y. Bar-Yam, “The Dynamics of Collaborative Design Insights From Complex Systems and Negotiation Research,” Concurrent Engineering Research and Applications, Vol.12, 2003.
[10] K. Fujita, T. Ito, H. Hattori, and M. Klein, “An Approach to Implementing A Threshold Adjusting Mechanism in Very Complex Negotiations A Preliminary Result,” Int. Conf. on Knowledge, Information and Creativity Support Systems (KICSS2007), pp. 185-192, 2007.
[11] K. Fujita, T. Ito, H. Hattori, andM. Klein, “Effects of Revealed Area based Selection Method for Representative-based Protocol,” Agentbased Complex Automated Negotiations (ACAN2008), 2008.
[12] H. Hattori, M. Klein, and T. Ito, “Using Iterative Narrowing to enable multi-party negotiations with multiple Interdependent Issues,” Proc. of the 6th Int. Joint Conf. on Autonomous Agents and Multiagent Systems, pp. 1043-1045, 2007.
[13] I. Marsa-Maestre, M. A. Lopez-Carmona, J. Velasco, and E. hoz, de-la, “Effective Bidding and Deal Identification for Negotiations in Highly Nonlinear Scenarios,” Proc. of 8th Int. conf. on Autonomous Agents and Multi agent Systems (AAMAS), pp. 1057-1064, 2009.
[14] R. Hailu and T. Ito, “Efficient Deal Identification For the Constraints Based Utility Space Model,” The AAMAS Workshop on Agent-based Complex Automated Negotiations (ACAN2011).

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] C. Faratin, C. Sierra, and N. R. Jennings, “Using similarity criteria to make issue trade-offs in automated negotiations,” Artificial Intelligence, Vol.142, pp. 205-237, 2002.

[2] [2] M. Fatima, M. Wooldridge, and N. R. Jennings, “Optimal negotiation of multiple issues in incomplete information settings,” The 3rd Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 1080-1087, 2004.

[3] [3] K. Hindriks, C. Jonker, and D. Tykhonov, “Eliminating Interdependencies between Issues for Multi-issue Negotiation,” Cooperative Information Agents X (CIA2006), 2011.

[4] [4] R. Y. K. Lau, “Towards genetically optimized multi-agent multi- issue negotiations,” The 38th Hawaii Int. Conf. On System Sciences, pp. 1080-1087, 2005.

[5] [5] R. J. Lin and S. T. Chou, “Bilateral multi-issue negotiations in a dynamic environment,” The Agent-Mediated Electronic Commerce, 2003.

[6] [6] M. Klein, P. Faratin, H. Sayama, and Y. Bar-yam, “Negotiating Complex Contracts,” MIT Sloan Research Paper No.4196, 2001.

[7] [7] T. Baarslag, K. V. Jonker, and R. Lin, “The First Automated Negotiating Agents Competition (ANAC 2010),” Studies in Computational Intelligence. LNCS, Vol.383, 2010.

[8] [8] T. Ito, H. Hattori, and M. Klein, “Multi-issue Negotiation Protocol for Agents Exploring Nonlinear Utility Spaces,” Int. Joint Conf. on Artificial Intelligence (IJCAI07), pp. 1347-1352, 2007.

[9] [9] M. Klein, P. Faratin, H. Sayama, and Y. Bar-Yam, “The Dynamics of Collaborative Design Insights From Complex Systems and Negotiation Research,” Concurrent Engineering Research and Applications, Vol.12, 2003.

[10] [10] K. Fujita, T. Ito, H. Hattori, and M. Klein, “An Approach to Implementing A Threshold Adjusting Mechanism in Very Complex Negotiations A Preliminary Result,” Int. Conf. on Knowledge, Information and Creativity Support Systems (KICSS2007), pp. 185-192, 2007.

[11] [11] K. Fujita, T. Ito, H. Hattori, andM. Klein, “Effects of Revealed Area based Selection Method for Representative-based Protocol,” Agentbased Complex Automated Negotiations (ACAN2008), 2008.

[12] [12] H. Hattori, M. Klein, and T. Ito, “Using Iterative Narrowing to enable multi-party negotiations with multiple Interdependent Issues,” Proc. of the 6th Int. Joint Conf. on Autonomous Agents and Multiagent Systems, pp. 1043-1045, 2007.

[13] [13] I. Marsa-Maestre, M. A. Lopez-Carmona, J. Velasco, and E. hoz, de-la, “Effective Bidding and Deal Identification for Negotiations in Highly Nonlinear Scenarios,” Proc. of 8th Int. conf. on Autonomous Agents and Multi agent Systems (AAMAS), pp. 1057-1064, 2009.

[14] [14] R. Hailu and T. Ito, “Efficient Deal Identification For the Constraints Based Utility Space Model,” The AAMAS Workshop on Agent-based Complex Automated Negotiations (ACAN2011).