Aproximaciones a la aplicación de políticas de consenso en escenarios de negociación automática compleja

Abstract

Negotation can be defined as the discussion between conflicting parties in order to reach an agreement from an initial situation of interest divergence. During the last years, automated negotiation has been attracting great interest in the artificial intelligence research communitiy. This has been motivated by the increasing presence and importance of autonomous agent systems, managed by different individuals and groups, that must reach an agreement using negotiation. In many of these scenarios, the agreement search is complex and expensive enough so that the automation of negotiation process is justified. Automated negotiation has been sucessfully applied to different environments such as electronic commerce or task or resource allocation problems, in supply chains or load balancing in computer networks. Automation allows tackling problem that are not affordable to humans, because of its complexity. In complex scenarios, it is common the appearance of multiple interdependent attributes. In multiattribute negotiation, it is usual that there exist different offers that provide the agent with the same utility level. For a negotiating agent, choose one of those offers is not a trivial task. That selection should be done taking into account the offer that is most likely to maximize the utility of the opponent. For making this selection, similarity criteria are usually employed as a key componente in many negotiation models. Similarity is based on evaluating how alike is one offer to the previously received offers from the opponent. It seems reasonable that the most similar the offer we send to the previously received offers, the most likely the offer will be accepted. In non-monotonic or discontiniuous preference structures, this criterium weakens because of the lack of information about the opponent's preference structure. As the first contribution, this work proposes a negotiation protocol able to effciently work in high complexity utility spaces where the similarity-based approaches fail. This works will focus on high-complexity preference spaces. In the context of complex multi-attribute negotiation, the complexity of the preference space can depend on the number of attributes under negotiation, the interdependence degree among preferences, the posibility of changing in the negotiation context during the process and finally on the method employed for preference description. For instance, a constrain-based preference space can have discontinuities that may deem classical approaches as useless. Even the suitability of many of proposals tailored for non-linear spaces may be restricted to low-complexity scenarios or for certain preference structures. This work presents negotiation mechanisms for dealing with complex multiattribute negotiation under non-differentiable preference spaces. The proposed protocol builds on some principles from pattern-search optimization methods to perform a distributed search in the solution space. In order to include the basic iterative pattern-search principle, a move from an interaction protocol based on contract exchanges to region exchanges. The protocol defines a recursive joint exploration process. This means that when the agents agree on an offer (in this case, a region proposed by an agent), a new bargaining process is started in lower-sized regions, contained in the previously accepted region. This process can be seen as an iterative contraction of the solution space. Once that the working region is small enough to be seen as an only contract, the agent may finish the negotiation. The extension of these negotiation mechanisms to a multilateral negotiation environment requires the inclusion of a procedure for aggregating the preferences of the agents. In this context, and taking into account the privacy and escalability requirements, it seems natural to move to a mediated approach. In mediated approaches, the mediator tries to optimize some kind of social welfare metrics. However, few works have included any social welfare criterium in the seach process. For this kind of environments, the definition of new social welfare concepts is required. This works presents also negotiation mechanisms that allow to include consensus policies in the search process, which can be defined in linguistic terms, making it easier to specify the kind of consensus needed. For the validation of the contributions of this work, an extensive experimental evaluation has been performed, using both random and non-random scenarios. These experiments show that this proposal based on pattern-search principles is able to overcome the limitation of similarity-based approached and reach agreements according to consensus policies defined by the mediatior, in an effective way. This opens the door to new line of research for design of mechanisms for multilateral multiattribute automated negotiation in highly-complex utility spaces. Finally, an exploration of the applicability of negotiation protocolos to highly-complex utility spaces is presented. The frequency assignment problem for Wi-Fi networks is estudied, where several network providers must agree on the frequency allocation to the access points under its control. This work is, to our knowledge, the frst application of this kind of protocol to real-world environments. The results show that it is possible to reach agreements that improved those obtained by enterprise heuristics currently in use and even from completeinformation optimizers.