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.
| Identifer | oai:union.ndltd.org:TDX_UAB/oai:www.tdx.cat:10803/295709 |
| Date | 29 May 2015 |
| Creators | Jonge, Dave de |
| Contributors | Sierra García, Carles, González Sabaté, Jordi, Universitat Autònoma de Barcelona. Departament de Ciències de la Computació |
| Publisher | Universitat Autònoma de Barcelona |
| Source Sets | Universitat Autònoma de Barcelona |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 198 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/, info:eu-repo/semantics/openAccess |
Page generated in 0.0058 seconds