Negotiation and Search*
                                         (Abstract)


                                         Carles Sierra

                                IIIA, Barcelona, Catalonia, Spain


   Most existing negotiation algorithms only work for bilateral negotiations with lin-
ear additive utility functions. Most real-world negotiations however are much more
complex. I introduce in this talk a new family of negotiation algorithms that is appli-
cable 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 solu-
tion 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 simulta-
neously and therefore strongly influence each other. It applies a new time-based nego-
tiation 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.




*
    AT2012, 15-16 October 2012, Dubrovnik, Croatia. Copyright held by the authors.