Effective Automated Negotiation Based on Issue Dendrograms and Partial Agreements

Abstract

Negotiation is both an important topic in multi-agent systems research and an important aspect of daily life. Many real-world negotiations are complex and involve multiple interdependent issues, therefore, there has been increasing interest in such negotiations. Existing nonlinear automated negotiation protocols have difficulty in finding solutions when the number of issues and agents is large. In automated negotiations covering multiple independent issues, it is useful to separate out the issues and reach separate agreements on each in turn. In this paper, we propose an effective approach to automated negotiations based on recursive partitioning using an issue dendrogram. A mediator first finds partial agreements in each sub-space based on bids from the agents, then combines them to produce the final agreement. When it cannot find a solution, our proposed method recursively decomposes the negotiation sub-problems using an issue dendrogram. In addition, it can improve the quality of agreements by considering previously-found partial consensuses. We also demonstrate experimentally that our protocol generates higher-optimality outcomes with greater scalability than previous methods.

Keywords

Multi-issue negotiation / issue dendrogram / partial agreement

References

[1] Chevaleyre Y., Endriss U., Maudet N.. Tractable negotiation in tree-structured domains. Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (AAMAS-2006), 2006 362-369.

[2] Clauset A., Newman M.E., Moore C.. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 066.

[3] De Jonge D., Sierra C.. nb3: a multilateral negotiation algorithm for large, non-linear agree-ment spaces with limited time. Autonomous Agents and Multi-Agent Systems, 2015, 29(5): 896-942.

[4] Eppinger S.D.. Model-based approaches to managing concurrent engineering. Journal of Engineering Design, 1991, 2(4): 283-190.

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

[6] Faratin P., Sierra C., Jennings N.R.. Using similarity criteria to make negotiation trade-offs. Proceedinbgs of 4th International Conference on Multi-Agent Systems, 2000 119-126.

[7] Faratin P., Sierra C., Jennings N.R.. Using similarity criteria to make issue trade-offs in automated negotiations. Artificial Intelligence, 2002, 142: 205-237.

[8] Fujita, K. (2012). The effect of grouping issues in multiple interdependent issues negotiation based on cone-constraints. In: Ito T., Zhang M., Robu V., Fatima S. & Matsuo T. (eds), New Trends in Agent-Based Complex Automated Negotiations, Springer, pp 39–55.

[9] Fujita K.. Efficient automated negotiation approach for non-monotonic utility based on tree representations. Second IIAI International Conference on Advanced Applied Informatics (IIAI AAI-2013), 2013 270-275.

[10] Fujita, K. (2015). Automated negotiations based on monotonic tree representations. In: Fujita K., Ito T., Zhang M. & Robu V. (eds) Next Frontier in Agent-based Complex Automated Negotiation, Springer Japan, pp 59–72.

[11] Fujita K., Ito T., Klein M.. An approach to scalable multi-issue negotiation: Decomposing the contract space. Computational Intelligence, 2014, 30(1): 30-47.

[12] de la Hoz E., Lopez-Carmona M.A., Klein M., Marsa-Maestre I.. Hierarchical clustering and linguistic mediation rules for multiagent negotiation. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012), 2012 1259-1260.

[13] Ito T., Hattori H., Klein M.. Multi-issue negotiation protocol for agents: Exploring nonlinear utility spaces. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), 2007 1347-1352.

[14] Jennings N.R., Faratin P., Lomuscio A.R., Parsons S., Sierra C., Wooldridge M.. Auto-mated negotiation: Prospects, methods and challenges. International Journal of Group Decision and Negotiation, 2001, 10(2): 199-215.

[15] Kakimoto S., Fujita K.. Effective automated negotiations based on recursive partitioning by issue dendrogram, 2017

[16] Klein M., Faratin P., Sayama H., Bar-Yam Y.. Negotiating complex contracts. Group Deci-sion and Negotiation, 2003, 12(2): 58-73.

[17] Kraus S.. Strategic Negotiation in Multiagent Environments, 2001.

[18] Lang F., Fink A.. Learning from the metaheuristics: Protocols for automated negotiations. Group Decision and Negotiation, 2015, 24(2): 299-332.

[19] Lopez-Carmona M., Marsa-Maestre I., Klein M., Ito T.. Addressing stability issues in mediated complex contract negotiations for constraint-based, non-monotonic utility spaces. Autonomous Agents and Multi-Agent Systems, 2010 1-51.

[20] Luo X., Jennings N.R., Shadbolt N., Leung H., Lee J.H.. A fuzzy constraint based model for bilateral, multi-issue negotiations in semi-competitive environments. Artificial Intelligence, 2003, 148: 53-102.

[21] Malone T.W., Klein M.. Harnessing collective intelligence to address global climate change. Innovations Journal, 2007, 2(3): 15-26.

[22] Marsa-Maestre I., Lopez-Carmona M.A., Velasco J.R., de la H. E.. Avoiding the prisoner’s dilemma in auction-based negotiations for highly rugged utility spaces. Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS-2010), 2010 425-432.

[23] Marsa-Maestre I., Lopez-Carmona M.A., Carral J.A., Ibanez G.. A recursive protocol for nego-tiating contracts under non-monotonic preference structures. Group Decision and Negotiation, 2013, 22(1): 1-43.

[24] Rosenschein J.S., Zlotkin G.. Rules of Encounter, 1994.

[25] Russell S.J., Norvig P.. Artificial Intelligence: A Modern Approach, 2002.

[26] Tamura H., Nakamura Y.. Decompositions of multiattribute utility functions based on convex dependence. Operations Research, 1983, 31(3): 488-506.

[27] Zhang X.S., Klein M., Marsa-Maestre I.. Scalable complex contract negotiation with struc-tured search and agenda management. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-2014), 2014 1507-1513.