English   español
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/130274
Share/Impact:
 SHARE CORE    MendeleyBASE Share your Open Access Story Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL Exportar a otros formatos: Endnote Bibtex csv DataCite
Title

# NB3: a Multilateral Negotiation Algorithm for Large, Non-linear Agreement Spaces with Limited Time

Authors;
KeywordsTraveling salesman problem
Non-linear utility
Negotiating Salesmen Problem
Heuristic algorithms
Negotiation
Multilateral
Search
Issue Date2015
CitationAutonomous Agents and Multi-Agent Systems 29: 896- 942 (2015)
AbstractExisting 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}$$NB3 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}$$NB3 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. © 2014, The Author(s).
URIhttp://hdl.handle.net/10261/130274
DOI10.1007/s10458-014-9271-3
Identifiersdoi: 10.1007/s10458-014-9271-3
issn: 1573-7454