Facing the Challenge of Automated Negotiation with Humans

Abstract

El camp de recerca en negociació ha estat estudiat des de diferents perspectives. Entre elles: la teoria de jocs, la psicologia, els negocis, la neuro-economia, i la psico-farmacologia. L'estudi computacional de la negociació s'anomena negociació automàtica. La majoria de les feines sobre negociació automàtica assumeixen que els agents són racionals, i els problemes estàtics. En canvi, els éssers humans són racionalment limitats, i els problemes acostumen a ser dinàmics. Sovint resulta impossible explorar l'espai de negociació complet degut a l'esgotament del temps i al dinamisme del problema. En el moment en què es troba una solució òptima, aquesta ja ha deixat de ser òptima des de fa temps. Els actuals bancs de proves disponibles sobre negociació automàtica es troben amb els mateixos problemes. Els que pretenen ser compatibles amb agents humans assumeixen que aquests són racionals, o utilitzen dominis artificials que requereixen una instrucció intensiva dels éssers humans per tal que puguin participar en els experiments. Aquesta tesi contribueix a la negociació automàtica definint una arquitectura d'agent adequada per a negociar amb els humans, i un banc de proves que resol els problemes existents a l'hora d'incloure humans en els experiments. L'arquitectura d'agent s'anomena HANA, permet múltiples negociacions bilaterals sobre accions a realitzar, i s'ocupa de la pre-negociació tot cercant bons conjunts d'accions i ofertes. Es tracta d'una arquitectura modular basada en un model ecològic de la racionalitat. L'estat mental de l'agent es representa amb graus de creences, desitjos dinàmics i intencions generals. Utilitzem una nova tècnica de cerca&negociació on la cerca i la negociació van de la mà: una proporcionant ofertes per a proposar, i l'altra compromisos per a podar l'espai de cerca, i informació per a afinar l'avaluació de les ofertes. Es defineixen diverses estratègies de negociació que es poden combinar dinàmicament. L'arquitectura és extensible permetent la incorporació de nous models de comportament. El banc de proves s'anomena DipGame i es basa en un joc de taula molt popular on ser un bon negociador és crucial per a guanyar. Aquest banc de proves permet l'estudi de les relacions, les emocions i les coalicions que tenen lloc durant successives negociacions entre éssers humans. Hi ha moltes oportunitats d'estudi en diversos temes de recerca, tots ells vinculats a la negociació. L'estudi d'un tema o d'un altre es selecciona restringir el llenguatge utilitzat durant el joc. El banc de proves proporciona un marc pel desenvolupament d'agents i diverses eines de negociació per a la representació dels missatges i la comunicació entre ells. DipGame dóna suport a l'execució d'experiments utilitzant un programa anomenat GameManager, i facilita la inclusió dels éssers humans amb un altre programa anomenat ChatApp. A més, es dóna suport a l'anàlisi dels resultats amb un programa diferent anomenat DipTools. Aquesta tesi es completa amb una definició formal del problema, una especificació formal del joc i l'aplicació del treball a la indústria dels jocs

The research field of negotiation has been studied from many different perspectives, among them: game theory, psychology, business, neuroeconomics, and psychopharmacology. The computational study of negotiations is denoted by automated negotiation. Most works on automated negotiation assume rational agents and static negotiation problems. However, humans are rationally bounded, and their negotiations are usually dynamic. It is often impossible to explore the complete negotiation space due to time limitations and the dynamics of the problem. By the time that an optimal solution is found, the solution is not optimal any more. Currently available testbeds on automated negotiation share the same shortcomings. Those testbeds that intend to involve humans in experiments assume that humans are rational, or are defined over artificial domains that require intense instruction of experiment participants. This thesis contributes to automated negotiation defining an agent architecture suitable to negotiate with humans, and a testbed that allows for an easy participation of humans in experiments. We denote the agent architecture by HANA. It allows multiple bilateral negotiations about actions, and deals with pre-negotiation looking for good enough sets of actions and offers. It is a modular architecture based on an ecological model of rationality. The mental state of the agent is represented as graded beliefs, dynamic desires and general intentions. We use a novel search&negotiation technique where search and negotiation go hand in hand: the former providing offers to propose, and the later providing commitments for pruning the search space, and information for fine-tuning the evaluation of offers. Several negotiation strategies are provided that can be dynamically combined. The architecture is extensible, allowing the incorporation of new behavioural models. The name of the testbed is DipGame. It is based on a popular board game where being a skilled negotiator is crucial for winning. DipGame allows the study of relationships, emotions, and coalitions that take place during successive negotiations involving humans. There are many research opportunities in different topics all of them connected to negotiation. The study of a topic or another is selected constraining the negotiation language used during the game. The testbed provides a framework for agent development, and several negotiation utilities for the representation of messages and communication among agents. It assists the execution of experiments using a graphical software application called GameManager. It facilitates the inclusion of humans with another application called ChatApp. Moreover, the analysis of results is supported by a different application called DipTools. This thesis is completed with a formal definition of the problem, a formal specification of the game, and the application of the work to the game industry.