Negotiation and Search

Speaker: Carles Sierra

Affiliation: Artificial Intelligence Research Institute (IIIA) of the Spanish Research Council (CSIC)

Time: Friday 13/07/2012 from 11:00 to 12:00

Venue: Access Grid UWS. Presented from Penrith (Y239), accessible from Parramatta (EB.1.32) and Campbelltown (26.1.50).

Abstract: Most existing negotiation algorithms only work for bilateral negotiations with linear additive utility functions. Most real-world negotiations however are much more complex. I 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 solution is not feasible. This family of algorithms is called NB3 and applies Branch & Bound search to find good plans to propose. 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 assume a negotiation protocol that imposes almost no restrictions and is therefore also applicable to negotiations with humans. To analyze the performance of the algorithm I will present the Negotiating Salesmen Problem (NSP): a new variant of the Traveling Salesman Problem, in which several salesmen need to negotiate with each other in order to minimize the lengths of their trajectories.

Biography:

Prof Carles Sierra is a full professor at the Artificial Intelligence Research Institute (IIIA) of the Spanish Research Council. He is one of the earliest researchers in multi-agent systems, especially in automated negotiation. He is the leader of a number of large European and Spanish projects, named a few: Agreement Technologies, Community-Building Information Technology, Autonomic Software Engineering for online cultural experiences.