English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/130274
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


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

AuthorsDe Jonge, Dave; Sierra, Carles
KeywordsTraveling salesman problem
Non-linear utility
Negotiating Salesmen Problem
Heuristic algorithms
Issue Date2015
PublisherKluwer Academic Publishers
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).
Identifiersdoi: 10.1007/s10458-014-9271-3
issn: 1573-7454
uri: http://link.springer.com/article/10.1007/s10458-014-9271-3
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
AAMAS, (2015),v29,pp.896-942..pdf828,41 kBAdobe PDFThumbnail
Show full item record
Review this work

Related articles:

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.