Negotiations over large agreement spaces

Abstract

En aquesta tesi investiguem algorismes de negociació en dominis amb funcions d'utilitat no linials i en els quals l'espai d'acords possibles és tan gran que l'ús de cerca exhaustiva és inviable. A més, explorem la relació entre les àrees de negociació automàtica, teoria de jocs, institucions electròniques i optimització amb restrictions. Presentem tres casos d'estudi de complexitat creixent. Primer, proposem un negociador automàtic basat en algorismes genètics i l'apliquem a un domini on el conjunt d'acords possibles es dóna en forma explícita com un espai vectorial i on, encara que les funcions d'utilitat són no linials, el valor d'utilitat de qualsevol acord es pot calcular ràpidament resolent una equació linial. Segon, presentem un algorisme de negociació general anomenat NB3, basat en la tècnica de Branch & Bound. Apliquem aquest algorisme a un nou cas de prova on el valor d'un acord es pot determinar únicament resolent un problema NP-dur. El tercer cas d'ús és el joc Diplomacy, que és encara més difícil que els casos anteriors ja que un acord no determina completament les accions d'un agent. La utilitat obtinguda per un agent depèn també de les accions triades pels altres agents, de manera que es necessita tenir en consideració aspectes de teoria de jocs. Justi quem que en aquest model basat en teoria de jocs no existeix una definició satisfactòria del concepte `valor de reserva', a diferència dels models comunment emprats en la teoria de regateig clàssica. A més, justifiquem que les negociacions requereixen d'un mecanisme, conegut com a Institució Electrònica, per garantir que els acords siguin respectats. Un entorn per al desenvolupament d'Institucions Electròniques és EIDE i proposem una extensió d'EIDE que proporciona una interfície que permet als humans d'interaccionar en institucions electròniques. També plantegem que en el futur serà possible per als humans i els agents de negociar quins protocols fer servir a una institució electrònica. Això podria ser especialment útil en el desenvvolupament de noves xarxes socials on els usuaris puguin determinar les regles de comportament particulars d'una comunitat privada. Ja que l'entorn EIDE és massa complicat per ser emprat per usuaris normals, sense les capacitats d'un enginyer informàtic, introduïm un nou llenguatge per a la definició de protocols que és similar al llenguatge natural i per tant pot ser usat i entès per qualsevol persona.

In this thesis we investigate negotiation algorithms for domains with non-linear utility functions and where the space of possible agreements is so large that the application of exhaustive search is impossible. Furthermore, we explore the relationship between the fields of Automated Negotiations, Game Theory, Electronic Institutions, and Constraint Optimization. We present three case studies with increasing complexity. Firstly, we introduce an automated negotiator based on Genetic Algorithms, which is applied to a domain where the set of possible agreements is explicitly given as a vector space and, although the utility functions are non-linear, the utility value of any given deal can be calculated quickly by solving a linear equation. Secondly, we introduce a general purpose negotiation algorithm called NB3, which is based on Branch & Bound. We apply this to a new negotiation test case in which the value of any given deal can only be determined by solving an NP-hard problem. Our third case involves the game of Diplomacy, which is even harder than the previous test cases, because a given deal usually does not entirely x the agent's possible actions. The utility obtained by an agent thus also depends on the actions it performs after making the deal. Moreover, its utility also depends on the actions chosen by the other agents, so one needs to take Game Theoretical considerations into account. We argue that in this Game Theoretical model there no longer exists a satisfactory de nition of a reservation value, unlike the models commonly used in classical bargaining theory. Furthermore, we argue that negotiations require a mechanism, known as an Electronic Institution, to ensure that agreements are obeyed. One framework for the development of Electronic Institutions is EIDE and we introduce a new extension to EIDE that provides a user interface so that humans can interact within such Electronic Institutions. Moreover, we argue that in the future it should be possible for humans and agents to negotiate which protocols to follow in an Electronic Institution. This could be especially useful for the development of a new kind of social network in which the users can set the rules for their own private communities. Finally, we argue that the EIDE framework is too complicated to be used by average people who do not have the technical skills of a computer scientist. We therefore introduce a new language for the definition of protocols, which is very similar to natural language so that it can be used and understood by anyone.