caa a22 4500 605514801 CHVBK 20210128100706.0 cr unu---uuuuu 210128e20150901xx s 000 0 eng 10.1007/s10458-014-9271-3 doi (NATIONALLICENCE)springer-10.1007/s10458-014-9271-3 $$\hbox {NB}^{3}$$ NB 3 [Elektronische Daten] a multilateral negotiation algorithm for large, non-linear agreement spaces with limited time [Dave de Jonge, Carles Sierra] Existing work on automated negotiations has mainly focused on bilateral negotiations with linear utility functions. It is often assumed that all possible agreements and their utility values are given beforehand. Most real-world negotiations however are much more complex. We introduce a new family of negotiation algorithms that is applicable to domains with many agents, an intractably large space of possible agreements, non-linear utility functions and limited time so an exhaustive search for the best proposals is not feasible. We assume that agents are selfish and cannot be blindly trusted, so the algorithm does not rely on any mediator. This family of algorithms is called $$\hbox {NB}^{3}$$ NB 3 and applies heuristic Branch & Bound search to find good proposals. Search and negotiation happen simultaneously and therefore strongly influence each other. It applies a new time-based negotiation strategy that considers two utility aspiration levels: one for the agent itself and one for its opponents. Also, we introduce a negotiation protocol that imposes almost no restrictions and is therefore better applicable to negotiations with humans. We present the Negotiating Salesmen Problem (NSP): a variant of the Traveling Salesman Problem with multiple negotiating agents, as a test case. We describe an implementation of $$\hbox {NB}^{3}$$ NB 3 designed for the NSP and present the results of experiments with this implementation. We conclude that the algorithm is able to decrease the costs of the agents significantly, that the heuristic search is efficient and that the algorithm scales well with increasing complexity of the problem. The Author(s), 2014 Multilateral nationallicence Negotiation nationallicence Search nationallicence Non-linear utility nationallicence Negotiating Salesmen Problem nationallicence de Jonge Dave Artificial Intelligence Research Institute, IIIA-CSIC, Campus de la Universitat Autònoma de Barcelona, Bellaterra, Catalonia, Spain aut Sierra Carles Artificial Intelligence Research Institute, IIIA-CSIC, Campus de la Universitat Autònoma de Barcelona, Bellaterra, Catalonia, Spain aut Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 896-942 1387-2532 29:5<896 2015 29 10458 https://doi.org/10.1007/s10458-014-9271-3 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10458-014-9271-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- de Jonge Dave Artificial Intelligence Research Institute, IIIA-CSIC, Campus de la Universitat Autònoma de Barcelona, Bellaterra, Catalonia, Spain aut NATIONALLICENCE 700 1- Sierra Carles Artificial Intelligence Research Institute, IIIA-CSIC, Campus de la Universitat Autònoma de Barcelona, Bellaterra, Catalonia, Spain aut NATIONALLICENCE 773 0- Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 896-942 1387-2532 29:5<896 2015 29 10458