A Machine Learning Approach for Mechanism Selection in Complex Negotiations

Abstract

Automated negotiation mechanisms can be helpful in contexts where users want to reach mutually satisfactory agreements about issues of shared interest, especially for complex problems with many interdependent issues. A variety of automated negotiation mechanisms have been proposed in the literature. The effectiveness of those mechanisms, however, may depend on the characteristics of the underlying negotiation problem (e.g. on the complexity of participant’s utility functions, as well as the degree of conflict between participants). While one mechanism may be a good choice for a negotiation problem, it may be a poor choice for another. In this paper, we pursue the problem of selecting the most effective negotiation mechanism given a particular problem by (1) defining a set of scenario metrics to capture the relevant features of negotiation problems, (2) evaluating the performance of a range of negotiation mechanisms on a diverse test suite of negotiation scenarios, (3) applying machine learning techniques to identify which mechanisms work best with which scenarios, and (4) demonstrating that using these classification rules for mechanism selection enables significantly better negotiation performance than any single mechanism alone.

Keywords

Automated negotiation / mechanism selection / scenario metrics

References

[1] Aydoğan, R., Festen, D., Hindriks, K. & Jonker, C. M. (2017). Alternating offers protocol for multilateral negotiation. In K. Fujita, Q. Bai, T. Ito, M. Zhang, F. Ren, R. Aydoğan, & R. Hadfi (eds), Modern Approaches to Agent-based Complex Automated Negotiation, pp. 153–167, Springer.

[2] Alpaydin E.. Introduction to Machine Learning, 2009.

[3] Aydoğan, R., Hindriks, K. & Jonker, C. (2014). Multilateral mediated negotiation protocols with feedback. In I. Marsa-Maestre, M. A. Lopez-Carmona, T. Ito, M. Zhang, Q. Bai, & K. Fujita (eds), Novel Insights in Agent based Complex Automated Negotiation, Studies in Computational Intelligence, pp. 43–59, Springer.

[4] Bai Q., Zhang M., Sim K. M.. Flexible negotiation modelling by using coloured Petri Nets. Journal of Information Technology Research, 2009, 2(3): 1-17.

[5] Chen S., Ammar H., Tuyls K., Weiss G.. Transfer learning for bilateral multi-issue negotiation. In Proceedings of the 24th Benelux Conference on Artificial Intelligence (BNAIC), 2012 59-66.

[6] Endriss U.. Monotonic concession protocols for multilateral negotiation. In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, 2006 392-399.

[7] Fujita K., Ito T., Klein M.. A secure and fair protocol that addresses weaknesses of the Nash bargaining solution in nonlinear negotiation. Group Decision and Negotiation, 2012, 21(1): 29-47.

[8] Guerri A., Milano M.. Learning techniques for automatic algorithm portfolio selection. In Proceedings of the 16th European Conference on Artificial Intelligence, 2004 475-479.

[9] Ilany L., Gal Y.. Algorithm selection in bilateral negotiation. Autonomous Agents and Multi-Agent Systems, 2016, 30(4): 697-723.

[10] Ito T., Klein M.. A consensus optimization mechanism among agents based on genetic algorithm for multi-issue negotiation problems. In Proceedings of Joint Agent Workshops and Symposium (JAWS), 2009 286-293.

[11] Ito T., Hattori H., Klein M.. Multi-issue negotiation protocol for agents: exploring nonlinear utility spaces. In Proceedings of International Joint Conference on Artificial Intelligence, 2007 1347-1352.

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

[13] Jonge D. d, Sierra C.. Nb3: A multilateral negotiation algorithm for large, nonlinear agreement spaces with limited time. Autonomous Agents and Multi-Agent Systems, 2015, 29(5): 896-942.

[14] Jonker C. M., Aydogan R., Baarslag T., Fujita K., Ito T., Hindiks K.. Automated Negotiating Agents Competition (ANAC). In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 2017 5070-5072.

[15] K V. V., Fogarty T. C., Miller J. F.. Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. In Advances in Evolutionary Computing, 2003 3-44.

[16] Kersten G. E., Lai H.. Negotiation support and e-negotiation systems: an overview. Group Decision and Negotiation, 2007, 16(6): 553-586.

[17] Klein M., Faratin P., Sayama H., Bar-Yam Y.. Protocols for negotiating complex contracts. IEEE Intelligent Systems, 2003, 18: 32-38.

[18] Kraus S.. Strategic Negotiation in Multi-Agent Environments, 2001.

[19] Lai G., Sycara K.. A generic framework for automated multi-attribute negotiation. International Journal of Group Decision and Negotiation, 2009, 18(2): 169-187.

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

[21] Leo Breiman J. F.. Classification and Regression Trees, 1984.

[22] Leyton-Brown K., Nudelman E., Shoham Y.. Learning the empirical hardness of optimization problems: The case of combinatorial auctions, 2002 556-572.

[23] Leyton-Brown K., Nudelman E., Andrew G., McFadden J., Shoham Y.. A portfolio approach to algorithm select. In Proceedings of the 18th International Joint Conference on Artificial intelligence, 2003 1542-1543.

[24] Lin R.. Bilateral multi-issue contract negotiation for task redistribtion using a mediation service. In Proceedings of Agent Mediated Electronic Commerce VI, 2004

[25] Lin R., Kraus S., Baarslag T., Tykhonov D., Hindriks K., Jonker C. M.. Genius: An integrated environment for supporting the design of generic automated negotiators. Computational Intelligence, 2014, 30(1): 48-70.

[26] Marsa-Maestre I., Klein M., de la Hoz E., Lopez-Carmona M. A.. Negowiki: A set of community tools for the consistent comparison of negotiation approaches. In Proceedings of International Conference on Principles and Practice of Multi-Agent Systems, 2011, 2011: 424-435.

[27] Marsa-Maestre I., Klein M., Jonker C. M., Aydogan R.. From problems to protocols: towards a negotiation handbook. Decision Support Systems, 2014, 60(1): 39-54.

[28] Marsa-Maestre I., Lopez-Carmona M. A., Klein M., Ito T., Fujita K.. Addressing utility space complexity in negotiations involving highly-uncorrelated, constraint-based utility spaces. Computational Intelligence, 2012, 30(1): 1-29.

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

[30] Ren F., Zhang M.. A single issue negotiation model for agents bargaining in dynamic electronic markets. Decision Support Systems, 2014, 60: 55-67.

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

[32] Sanchez-Anguix V., Aydoğan R., Julian V., Garcia-Fornes A., Jonker C. M.. Unanimously acceptable agreements for negotiation teams in unpredictable domains. Electronic Commerce Research and Applications, 2014, 13(4): 243-265.

[33] Tomassini M., Vanneschi L., Collard P., Clergue M.. A study of fitness distance correlation as a difficulty measure in genetic programming. Evolutionary Computation, 2005, 13(2): 213-239.

[34] Williams C. R. R. V., Gerding E. H., Jennings N. R.. Negotiating concurrently with unknown opponents in complex, real-time domains. Proceedings of 20th European Conference on Artificial Intelligence, 2012 834-839.

[35] Williams C. R., Robu V., Gerding E. H., Jennings N. R.. Using gaussian processes to optimise concession in complex negotiations against unknown opponents. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 2011 432-438.

[36] Wong T., Fang F.. A multi-agent protocol for multilateral negotiations in supply chain management. International Journal of Production Research, 2010, 48(1): 271-299.