Contribución a la negociación automática en espacios de utilidad complejos

Abstract

We can see negotiation as an interaction between two or more parties who intend to reach an agreement about a range of issues which requires to solve a conflict of interests between them. As such, negotiation is present in vastly different aspects of our everyday lives, from personal relationships to economy or international politics. Some negotiation scenarios can be fully or partially automated, thus taking advantage of the efficiency of artificial intelligence techniques. Among the problems which have been successfully adressed in the literature using negotiation, we can cite different negotiation scenarios in e-commerce, and resource or task allocation problems, such as manufacturing chains or load balancing in computing processes. Automatization of negotiation processes allows not only to emulate human negotiation in traditional scenarios, but also to address problems where human negotiation is not feasible, due to the complexity of the scenario, or due to the time constraints over the negotiation process. In this context, there is an increasing research interest in complex negotiation scenarios, such as legal contract negotiations or service level agreements between customers and providers. In these scenarios, negotiations often involve multiple, interdependent issues. The complexity of these problems suggest the partial or full automatization of the process, specially when there are hard negotiation deadlines. However, issue interdependency results in nonlinear utility spaces, making classic negotiation mechanisms not applicable. Even mechanisms specifically designed for nonlinear scenarios may fail when the complexity of the utility spaces increases. Therefore, alternative mechanisms are needed which allow to negotiate in an effective and efficient manner in scenarios involving highly complex utility spaces. This PhD thesis addresses the problem of multilateral automated negotiation for complex utility spaces, in an attempt to fulfil this need. To this end, a negotiation model is proposed, which is specifically designed for these scenarios. The model comprises the representation of the agents’ preferences, the specification of the interaction protocol which governs the negotiation, and the design of heuristic strategies for agent decision making. For agent preferences, constraint based utility functions are chosen, and we present a preference generator which allows to define, giving a set of generation parameters, scenarios of adjusted complexity, both regarding the complexity of the individual agent utility spaces and the corelation between different agents’ utility functions. For the negotiation process, our hypothesis is that, in scenarios involving complex utility spaces, we can improve the process of finding mutually acceptable agreements by balancing the utility-maximizing goals of each individual agent and the social goal of reaching an agreement. Taking this into account, we propose an expressive, iterative, auction-based negotiation protocol, which allows agents to refine their bids at each iteration, making use of the expressive capabilities provided by argumentation techniques. Finally, a set of strategies for agent decision making is proposed. These strategies are intended to balance expected utility and deal probability considering the risk attitudes of the different agents. Once the proposal has been made, an exhaustive experimental evaluation is performed to assess the contribution of the proposed mechanisms in terms of effectiveness and efficiency. Experiments have confirmed our hypothesis and the suitability of our proposal based on the balance between utility and deal probability and the expressive capabilities of the agents, allowing us to draw important conclusions on the field of multilateral, multi-issue automated negotiation for complex utility spaces.