Concurrent Negotiations with Global Utility Functions

Automated Negotiation is attracting more attention from researchers recently as it is becoming more relevant to industrial and business applications with increased reliance on automated systems. Most research in this area assumes either a single negotiation thread with a well-defined utility function for each agent involved or a set of concurrent negotiations with an ordering of outcomes in each local negotiation. In this paper, we consider an agent engaged in a set of concurrent negotiations with a utility function defined only for the complete set of agreements in all of them and no locally defined ordering of outcomes in any negotiation independent from what happens in the others. We argue that this problem setting is interesting both from the academic and the industrial points of view. The paper then presents an algorithm that allows such agent to maximize its expected global utility by orchestrating its behavior in all negotiation threads. The performance of the proposed method is analyzed theoretically and empirically using simulation.