Sistemas Multiagente
Sesión 2:
Coordinación  Negociación y Argumentación
Curso 2010/2011
Ramón Hermoso Traba
02/10/2015
1
La Coordinación en los Sistemas
Multiagente
Indice:
1. Introducción
2. Negociación y Argumentación
3. Bibliografía
02/10/2015
2
¿Qué es la Coordinación?
 Concepto “universal”:
 Ciencias Sociales, Economía, Biología, …
 Robótica, Ingeniería del Software, Lenguajes de
Programación, Inteligencia Artificial (Distribuida), …
 Semántica “borrosa”:
 Múltiples definiciones
 ¡Esto no es coordinación!
 Coordinación en los Sistemas Multiagente (SMA):
 la coordinación es un problema clave en la
construcción de SMAs
 la capacidad para coordinarse es una característica
esencial de un agente
02/10/2015
3
La coordinación en los SMA:
perspectivas diferentes
Interés del diseñador en la coordinación
Diseño a nivel micro
Diseño
Diseño aa nivel
nivel macro
macro
– construir sistemas de múltiples
agentes con características deseadas
Varios diseñadores de agentes
“La coordinación es la integración y el ajuste
del trabajo individual con el fin de
alcanzar una meta mayor”
(B. Singh)
02/10/2015
Un
Un diseñador
diseñador de agentes
– agentes benévolos
– diseñar todo un sistema de
resolución de problemas
4
Coordinación a nivel macro: Resolución
Dist. de Problemas
• Ejemplo: Gestión de tráfico rodado
– red de autopistas urbanas
– Construir un sistema que genere
planes de señalización en función
del estado del tráfico
02/10/2015
5
Coordinación a nivel macro: Resolución
Dist. de Problemas
Arquitectura TRYS (Cuena et al.):
 agentes de resolución de
problemas
 cada agente es responsable de un
área problema
 genera planes alternativos de
señalización local y los
comunica al agente
coordinador
 agente coordinador
 resuelve las interdependencias
entre los planes locales
 envía los planes locales
adaptados a los agentes para su
ejecución
02/10/2015
La coordinación en los SMA: perspectivas
diferentes
Interés del diseñador en la coordinación
Diseño a nivel micro
micro
– en un entorno abierto con
múltiples agentes
– diseñar un agente adicional
con características deseadas
Varios diseñadores de agentes
“La coordinación es una forma
Diseño a nivel macro
de adaptarse al entorno”
– construir sistemas de múltiples agentes
(von Martial)
con características deseadas
Un diseñador de agentes
– agentes benévolos
– diseñar todo un sistema de
resolución de problemas
02/10/2015
7
Coordinación a nivel micro
Ejemplo:
 Agente R1 ha de vigilar una zona
 existen dos puntos de observación (P1 y P2)
Valor: 2
Valor: 4
P1
P2
 suponen un valor (altura) y un coste (distancia)
 acciones: A1 (ir a P1), A2 (ir a P2) y N (nada) Coste: 1
R1
Coste: 1
Coste:2
R2
• Mundo multiagente junto con R2:
– Utilidad: URi(Ai) = valor ({Pi,Pj}) – coste(Ai)
– R1 conoce sus tres acciones alternativas y sus consecuencias
– R1 no sabe si R2 es consciente de tener la alternativa A2
02/10/2015
8
Coordinación a nivel micro
Método RMM (Gmytrasievicz y Durfee):
Modelo de R1 de su
propia situación
R2
A1 A2 N
p=0.75
A1 1
R1 A2 4
N 2
5
1 4
2
2
4
0
R2 sabe de P2
R2 no sabe de P2
R1
A1 A2 N
Modelo de R1 sobre las
posibles acciones de R2
R1 no sabe qué modelo
R2 tiene de él
02/10/2015
A1 0
R2 A2 –
N 2
–
0
–
–
–
0 1
[0.5, 0.5]
p=0.25
R1
A1 A2 N
A1 0 4 0
R2 A2 5 3 3 11/3
N 2 4 0
[0.25, 0.75]
[1/3, 1/3, 1/3]
9
La coordinación en los SMA: perspectivas
diferentes
Interés del diseñador en la coordinación
“Coordinar es gobernar la interacción”
(Wegener )
Diseño
Diseño aa nivel
nivel micro
micro
Diseño a nivel macro
– en un entorno abierto con
múltiples agentes
– diseñar un agente adicional
con características deseadas
– construir sistemas de múltiples agentes
con características deseadas
02/10/2015
Varios diseñadores
diseñadores de
de agentes
agentes
Un diseñador de agentes
– no se puede ejercer un control
directo sobre los agentes
– diseñar el contexto del sistema
– agentes benévolos
– diseñar todo un sistema de
resolución de problemas
10
Coordinación a nivel macro: Sociedades
de Agentes
• Ejemplo: Comercio Electrónico (Rosenschein y Zlotkin):
– asignación de llamadas telefónicas a compañías de telecomunicación
– objetivo: evitar comportamiento estratégico entre compañías
• Mecanismo de subasta:
– un agente usuario comunica las características
de la llamada a los distintos agentes empresa
– cada agente empresa contesta con una oferta
(precio por minuto)
– el agente usuario elige una oferta en base a una
convención
02/10/2015
11
Coordinación a nivel macro: Sociedades
de Agentes
 Convención 1:
 elegir la mejor compañía y pagar
el precio de la oferta más baja
 problema: promociona el
comportamiento estratégico
02/10/2015
 Convención 2:
 elegir la mejor compañía y pagar
el precio de la segunda oferta
más baja
 elimina incentivos para el
comportamiento estratégico
12
La Coordinación en los Sistemas
Multiagente
Indice:
1. Introducción
2. Negociación y Argumentación
3. Bibliografía
02/10/2015
13
Coordinación
02/10/2015
14
Coordinar es Gestionar Dependencias
Coordinación: gestión de dependencias (Malone y Crowston)
Agente 1
Agente 2
t
t2
t1
t1, t1,
1
2
t1,
3
t'1
t3
local
t'2
type A
t3, t3, t3,
1
t'
2
3
t'1,1 t'1,2 t'1,3
t'2,1 t'2,2 t'2,3
type B
Tareas de coordinación:
 definición del contexto de coordinación: agentes, metas, tareas,
capacidades, etc.
 detección de dependencias: recursos compartidos, productor/consumidor
etc.
 decisión de gestión: secuenciación temporal, selección de recursos etc.
02/10/2015
15
La coordinación en entornos abiertos
Diseño de estrategias
Diseño de Sistemas de Agentes para Negociación
Diseño a nivel micro
Diseño a nivel macro
– en un entorno abierto con
múltiples agentes
– diseñar un agente adicional
con características deseadas
– construir sistemas de múltiples agentes
con características deseadas
Varios diseñadores de agentes
Un diseñador de agentes
– no se puede ejercer un control
directo sobre los agentes
– diseñar el contexto del sistema
– agentes benévolos
– diseñar todo un sistema de
resolución de problemas
Diseño de protocolos
02/10/2015
16
Situaciones con múltiples decisores:
Juegos
Modelos cuantitativos de coordinación
 Las dependencias se compilan en funciones de utilidad multi-atributo
 Un agente sólo controla un subconjunto de atributos (o sólo uno)
Juegos:
 En su versión más simple, se considera un juego  en forma normal
una tripleta (I,S,U), tal que
 I es un conjunto de n agentes (jugadores)
 S es el espacio de acciones (estrategias) conjuntas, pudiendo elegir cada
agente de un conjunto finito de acciones (estrategias) individuales
 U es un conjunto de funciones de utilidad Ui para cada jugador tal que
Ui :S  
02/10/2015
17
Escenarios antagónicos: Juegos de
suma nula
 Un juego es de suma nula cuando en toda
estrategia conjunta s se compensan
exactamente las ganancias de unos jugadores
con las pérdidas de otros, es decir:
n
 U s   0
 Si consideremos el caso particular de un juego
bipersonal de suma nula, la fórmula anterior se
reduce a la siguiente afirmación:
s  S .
i
i 1
 (s 1 , s 2 )  S .
02/10/2015
U 1 (s 1 , s 2 )   U 2 (s 1 , s 2 )
18
Escenarios parcialmente cooperativos:
Juegos de suma no constante
 Juegos de suma no constante:
 representan entornos en los que los intereses de los jugadores no son
totalmente antagónicos
 hay estrategias conjuntas de las que se pueden beneficiar ambos
jugadores:
n
 s ,s   S .
n
 U s    U s  
i
i 1
i
i 1
 Matriz de juego:
 representación de un juego de suma no constante con dos jugadores
 las filas representan las posibles acciones del agente 1, mientras que
las columnas indican las posibilidades de elección del jugador 2
 las celdas de la matriz contienen pares de números, que indican los
valores de utilidad de cada uno de los jugadores
02/10/2015
19
Escenarios parcialmente cooperativos:
Juegos de suma no constante
Ejemplo: Dilema de Prisionero
 Dos cautivos, de los que existe suficiente evidencia incriminatoria, son sometidos
de forma separada a un interrogatorio.
 Estrategias alternativas de actuación:
 confesar el crimen del que se le acusa (“defect”, D )
 callarse (“cooperate”,C ).
 Resultados de la actuación:
 ninguno confiesa: serán condenados a un año en la cárcel por una fechoría menor
 ambos confiesan: afrontarán 5 años de cárcel
 uno confiesa y el otro se calla: al primero se le perdonará la fechoría menor, y será liberado
gracias a su colaboración, mientras que el último será recluido durante 10 años
Nota:
 Muchas situaciones de la vida real tienen las características del Dilema de los
Prisioneros (“arms-race”, “free-rider”, etc.)
02/10/2015
Escenarios parcialmente cooperativos:
Juegos de suma no constante
Utilidades
 Interpretando los años en la cárcel como valores negativos de utilidad
 U1(D,D) = -5
U1(D,C) = 0
U1(C,D) = -10
 U2(D,D) = -5
U2(D,C) = -10
U2(C,D) = 0
Matriz del juego:
C
D
C
(-1,-1)
(-10,0)
D
(0,-10)
(-5,-5)
U1(C,C) = -1
U2(C,C) = -1
Preferencias
•
•
02/10/2015
Agente 1: (D,C) >1
Agente 2: (C,D) >2
(C,C) >1
(C,C) >2
(D,D) >1 (C,D)
(D,D) >2 (D,C)
Evaluación del Dilema del Prisionero
Contexto:
 los agentes no pueden comunicarse, y en particular
 no pueden llegar a acuerdos respecto a las acciones que tomar, o al reparto de las
utilidades obtenidas.
Estrategia racional: cada convicto prefiere confesar (D) en
vez de callarse (C).
 Seguridad: Si elige C corre el riesgo de ser recluido por 10 años, mientras que al
hacer D la penalización máxima es de 5 años.
 D domina a C:
 Si el compañero juega D, lo mejor que puede hacer el agente es jugar D también, puesto que
en este caso sólo iría 5 y no 10 años a la cárcel.
 Si el otro convicto se calla (C), la mejor opción será confesar (D), puesto que así la potencial
condena de un año se convierte en nada
02/10/2015
Equilibrio de Nash
Definición:
 Un conjunto de acciones está en equilibrio de Nash si ningún agente tiene
incentivos para desviarse de él de forma individual
 ningún agente puede incrementar su utilidad cambiando unilateralmente
su acción.
 Formalmente, si s* es un equilibrio de Nash entonces
i  I s i  S i .
U i s 1 ,..., s i ,..., s n   U i s 1 ,..., s i ,..., s n 
*
*
*
*
*
 Dependiendo del juego puede haber uno, varios, o ningún equilibrio de
Nash
02/10/2015
Soluciones al Dilema del Prisionero
Dilema del Prisionero:
 El único equilibrio de Nash es (D,D), por lo que ambos acusados
acabarán por 5 años en la cárcel
 Pero la opción (D,D) no es (Pareto-)eficiente …
 (C,C) domina a (D,D)
 Cada agente podría estar mejor sin que el otro estuviera peor
Soluciones:
 Modificar el concepto de racionalidad: altruismo, generosidad, etc.
 Dilema del Prisionero Iterado (con futuro “abierto”):
 Torneo de Axelrod: gana la estrategia “Tit-for-Tat”
 Establecer condiciones para que se pueda llegar a “acuerdos creíbles”
02/10/2015
Modelos de Negociación
Indice:
1. Introducción
2. Modelos de Negociación
2.1. Subastas
2.2. Regateo
2.3. Argumentación
3. Bibliografía
02/10/2015
25
Negociación
 Objetivo:
 determinar (las condiciones
de) un acuerdo entre, al
menos, dos agentes
 Tipos de negociación:
 Subastas
 Adjudicar productos y tareas a
través de un “mercado”
 n participantes, transacción
entre 2
 Regateo
 Llegar a un acuerdo entre
todos los participantes
 Argumentación
 Resolver (supuestos)
conflictos a través del debate
02/10/2015
“Rules of Encounter”
Rosenschein and Zlotkin, 1994
26
Subastas
 Mecanismo estructurado para forjar acuerdos
 Protocolo: semi-distribuido, con diferentes roles

1 subastador

N subasteros
 Estrategias:

“pujas” de los subasteros

Precio inicial, precio de reserva, etc., del subastador
 No muy frecuentes en la realidad, pero sí bastante
populares en Comercio Electrónico (p.e. eBay)
02/10/2015
27
Subasta inglesa
 Inicio:
 el subastador ofrece un producto a un precio inicial
(usualmente por debajo de un precio mínimo privado)
 Apuestas:
 los subasteros van ofertando precios (ninguna, una, o varias
veces)
 cada oferta tiene que superar todas las anteriores
 el ciclo de apuestas termina cuando no hay más ofertas
 Adjudicación:
 si la última oferta alcanza el precio mínimo (privado) del
subastador, el producto es adjudicado al subastero de la oferta
más alta
 de lo contrario no se vende el producto (el subastador tiene la
última palabra!!!)
02/10/2015
28
Subasta holandesa
 Se usa en mercados de flores holandesas para
determinar el precio de una cantidad de flores
 Inicio:
 el subastador ofrece una cantidad de un producto
a un precio inicial (usualmente por encima de un
precio mínimo privado)
 Apuestas:
 cada tiempo (Dt) disminuye el precio en una
cantidad (D$)
 cada oferta especifica la cantidad del producto a
comprar al precio actual
 el subastador determina el final de la subasta (o
bien porque toda la cantidad ha sido adjudicada, o
bien porque se alcanza el precio mínimo privado)
 Adjudicación:
 la adjudicación de cada oferta a los subasteros es
directa
 el subastador informa del final de la subasta
02/10/2015
30
Ejemplos de subasta “one-shot”
Subastas “one-shot”
• Sólo hay una oportunidad para hacer ofertas (i.e. el proceso no es
iterativo)
• Ejemplo de la asignación de llamadas telefónicas (véase
introducción)
 Subasta first-price sealed bid:
 elegir la mejor compañía y pagar
el precio de la oferta más baja
02/10/2015
 Subasta Vickrey:
 elegir la mejor compañía y pagar
el precio de la segunda oferta más
baja
32
Subastas de venta y de compra
Subastas de venta:
 1 vendedor, n compradores
 Ejemplos:
 subasta inglesa y holandesa
“tradicionales”
Subastas de compra
• 1 comprador, n vendedores
• variaciones de las subastas descritas:
– subasta inglesa de precio descendente
– subasta holandesa de precio ascendente
02/10/2015
34
Tipos de Protocolos de Subasta
 Tipo de ofertas:
 abierto (open-cry): los subasteros conocen mutuamente sus ofertas
 privado/cerrado (sealed-bid): los subasteros sólo conocen sus propias
ofertas
 Proceso de ofertas:
 una vuelta (one-shot): los subasteros sólo dan una oferta
 directa (forward): el precio de las ofertas va ascendiendo
 inversa (reverse): el precio de las ofertas va descendiendo
 Proceso de adjudicación:
 ¿Qué oferta se usa para determinar el precio que ha de pagar el
ganador? (first-price, second-price, …)
 Ejemplos:
 Subasta inglesa (tradicional): first-price open-cry (forward)
 Subasta holandesa (tradicional): first-price open-cry (reverse)
 Subasta Vickrey: one-shot second-price sealed-bid
02/10/2015
35
Tipos de Escenarios de Subasta
 valor público (común):
 el valor del producto sólo depende de las preferencias de los demás
subasteros (valor consiste únicamente en la reventa)
 p.e.: billete de un dólar
 valor privado:
más propicios al análisis formal
 el valor del producto sólo depende de las propias preferencias del
subastero (no hay posibilidad de reventa)
 p.e. billete de un dólar gastado por John Lennon
 valor correlado:
mayoría de las escenarios reales
(p.e. Comercio Electrónico)
 el valor del producto depende de las preferencias tanto del propio
subasteros como de los demás
 p.e.: una obra de arte que sirve como decoración y como inversión
02/10/2015
36
Problemas
Subastas Vickrey:
 subastador mentiroso:
 el subastador tiene incentivos para mentir respecto al precio de la segunda oferta
más alta (ya que el subastero ganador la desconoce)
 revelación de información privada:
 los subasteros revelan su precio real, lo cual podrá ser utilizado por los demás
subasteros en subastas futuras (de otro tipo)
Todas las subastas:
 colusión entre subasteros:
 si los subasteros se conocen, hay incentivos para coordinar sus ofertas
 costes computacionales:
 costes de “búsqueda” en subastas interrelacionadas
 costes de recabar información en situaciones de incertidumbre
02/10/2015
38
Plataformas para subastas
 Fishmarket: http://www.iiia.csic.es/Projects/fishmarket/
 Trading Agent Competition (TAC):
 http://www.sics.se/tac/
 http://tac.eecs.umich.edu/
…
02/10/2015
Negociación: Regateo
 Características:
•
•
•
posibilidad de forjar acuerdos globales (“creíbles”) entre n agentes
todos los agentes pueden beneficiarse de un acuerdo
pero hay una diferencia de opinión con respecto a las características del
acuerdo (qué acuerdo elegir)
 Elementos de un escenario de regateo

Conjunto (espacio) de negociación:



Protocolo de negociación:



Reglas que determinan el proceso de negociación:
 ¿Cómo, cuándo, y qué ofertas se pueden hacer?
 ¿Cuándo termina la negociación y cuál es el resultado?
Ejemplo: “No se puede ‘empeorar’ una oferta ya hecha”
Estrategia de negociación:


02/10/2015
Todos los posibles acuerdos a los que se pueden llegar
Ejemplo: todos los precios entre las expectativas iniciales de un comprador y un
vendedor
Cómo elegir entre las diferentes acciones que permite el protocolo
Ejemplo: “Mejorar mi última oferta en un 10% cada 5 minutos”
40
Objetivos de Diseño
Diseño de estrategias:
 Racionalidad: maximizar las ganancias esperadas
 Eficiencia: minimizar el coste computacional para determinar una acción
 …
Diseño de protocolos:
 Distribución: evitar que haya un “cuello de botella” (punto de fallo)
 Convergencia: garantizar que se llega a un acuerdo (o desacuerdo) en
tiempo finito
 Simplicidad: fomentar que se llegue rápido a un acuerdo (o desacuerdo)
 Eficiencia: si se llega a un acuerdo, este no “desperdicia” utilidad
 Estabilidad: motivar a los agentes para elegir estrategias con características
deseadas
(estrategias dominantes, equilibrios de Nash)
 …
02/10/2015
41
Negocación: Regateo

Regateo como proceso de oferta y contraoferta
Oferta
Contraoferta
Agente Ai acepta
Agente Ai

Regateo como proceso de concesiones mutuas
Ofertas de Ai
02/10/2015
Agente Aj
Punto de acuerdo/
transacción
Ofertas de Aj
42
El protocolo de concesiones
monótonas (PCM)
Protocolo PCM:
 El regateo se realiza por rondas
 En la ronda 1, cada agente propone simultáneamente un trato del conjunto de
negociación
 Se llega a un acuerdo, si un agente considera que el trato propuesto por el otro
es al menos tan bueno (para él) como el suyo.
 Si no hay acuerdo, se realiza una nueva ronda de propuestas. En la ronda u+1,
ningún agente puede realizar una propuesta peor que en la ronda u.
 Si ningún agente cede, el regateo termina en desacuerdo.
Diseño de estrategias:
 ¿Con qué propuesta empezar?
 ¿Cuándo (en qué ronda) hay que ceder?
 ¿Cuánto hay que ceder?
02/10/2015
43
La propuesta inicial
Leo Baekeland sold the rights to his invention, Velox
photographic printing paper, to Eastman Kodak in
1899. It was the first commercially successful
photographic paper and he sold it to Eastman Kodak
for $1 million. Baekeland had planned to ask
$50.000 and to go down to $25.000 if necessary, but
fortunately for him, Eastman spoke first.
(Asimov, 1982)
02/10/2015
44
El factor “riesgo”
Idea de estrategia:
 Empezar con el trato más favorable para uno mismo
 Determinar cuándo (y cuánto) ceder dependiendo de cuánto se puede perder en
caso de conflicto (riesgo)
Cuánto estoy
dispuesto a
arriesgar un
conflicto?
pérdida máxima en caso de conflicto
pérdida máxima
en caso de concesión
trato conflicto
mejor trato
para Ai
02/10/2015
mejor trato
para Aj
45
La estrategia de Zeuthen
Disposición para arriesgar el conflicto:
•
Riesgo: pérdida relativa máxima si el agente A cede en la ronda t
Riesgo(A,t) =
•
Pérdida máxima de A si cede (y acepta la oferta de B)
Pérdida máxima de A (si no cede y se llega a un conflicto)
Idea: el agente con el menor riesgo (el que realizaría la menor perdida
relativa máxima) debería ceder
La estrategia de Zeuthen:
•
Calcular el propio Riesgo(A,t) y el del contrario (Riesgo(B,t))
•
Si el propio riesgo es igual o más pequeño que el del contrario, entonces
hacer la oferta mínima suficiente
– suficiente: cambia la balanza de riesgos (después el contrario tiene el menor
riesgo)
– mínima: elegir la oferta que minimice la propia pérdida de utilidad
•
De lo contrario, no ceder (repetir la misma oferta)
02/10/2015
46
Dominios orientados a tareas:
Ejemplos
• Dominios orientados a tareas:
–
Un grupo de agentes puede redistribuir tareas entre sí (sin efectos secundarios)
–
pueden beneficiarse si llegan a un acuerdo, pero cada uno prefiere un acuerdo diferente
• Repartición de correo:
–
Varios repartidores de correo han de
entregar cartas en diferentes partes de
la ciudad. Cada repartidor quiere
minimizar el camino que tiene que
recorrer, y una forma de hacerlo es
intercambiar cartas con sus compañeros
• Consultas en Bases de Datos:
–
02/10/2015
Varios agentes tienen acceso a una Base de Datos común, y cada uno ha de realizar una
serie de consultas. Podrán coordinar sus (sub-)queries para maximizar la eficiencia de sus
consultas (Join, Proyección, Unión, Intersección, …) .
50
Dominios Orientados a Tareas
Definición:
 Un dominio orientado a tareas (DOT) es una tripleta (T, Ag, c) tal
que:

T es un conjunto finito tareas;

Ag = {A1, A2,…, An} es un conjunto finito de agentes;

c:(T)R+, c() = 0, es una función mónotona creciente que define
el coste para ejecutar cualquier subconjunto de tareas
Nótese:
02/10/2015

Quedarse quieto no cuesta nada (c() = 0)

Cuánto más tareas se ejecutan, más coste se genera (c es
monótona creciente)

El coste de ejecutar cada subconjunto de tareas no depende de
quién las lleva a cabo (situación idealizada)
51
Utilidad de Tratos
Definición: dado un DOT con dos agentes (T, {A1,A2}, c),
 un encuentro dentro del DOT es un vector (T1, T2)
tal que para todo k, Tk  T.
 un trato d = (D1, D2) en un encuentro (T1, T2) es
una redistribución de tareas entre agentes, tal que
D1  D2 = T1  T2
 el trato  = (T1, T2) se llama trato conflicto
Nótese:
 el trato conflicto  modela que no hay acuerdo
entre agentes (autonomía)
02/10/2015
52
Ejemplo: DOT
Ejemplo:
• dominio: ({a,b},{1,2},c)
• encuentro: ({a},{a,b})
• función de coste c:
c()=0
c({a})=1
c({b})=1
c({a,b)}=3
Posibles tratos:
({a}, {b})
({b}, {a})
({a,b}, )
(, {a,b})
trato conflicto
({a}, {a,b})
({b}, {a,b})
({a,b}, {a})
inicio
({a,b}, {b})
1
tarea a
02/10/2015
1
({a,b}, {a,b})
tarea b
53
Utilidad de Tratos
Definición: dado el DOT (T, {A1,A2}, c) y un trato d = (D1, D2)
 el coste Costk() del trato d para el agente k es
Costk()=c(Dk)
 la utilidad Utilityk() del trato d para el agente k es
Utilityk()= c(Tk) - Costk()
Nótese:
 el coste del trato conflicto es el de realizar sus
tareas sin ayuda (stand alone cost)
 la utilidad del trato conflicto para todos los agentes
k es Utilityk()= 0
02/10/2015
54
Ejemplo: Función de Utilidad de los
agentes
Agente 1:
Agente 2:
Utility1({a}, {b}) = 0
Utility2({a}, {b}) =2
Utility1({b}, {a}) = 0
Utility2 ({b}, {a}) = 2
Utility1({a,b}, ) = -2
Utility2 ({a,b}, ) = 3
Utility1(, {a,b}) = 1
Utility2 (, {a,b}) = 0
Utility1({a}, {a,b}) = 0
Utility2 ({a}, {a,b}) = 0
Utility1({b}, {a,b}) = 0
Utility2 ({b}, {a,b}) = 0
Utility1({a,b}, {a}) = -2
Utility2 ({a,b}, {a}) = 2
Utility1({a,b}, {b}) = -2
Utility2 ({a,b}, {b}) = 2
Utility1({a,b}, {a,b}) = -2
Utility2 ({a,b}, {a,b}) = 0
02/10/2015
55
Conjunto de Negociación
Definición:
 Un trato  domina el trato ' si  es mejor para al menos uno de los agentes,
y no es peor para el otro, es decir  > ' si
(1) k{1,2}, Utilityk() Utilityk(')
(2) k{1,2}, Utilityk()> Utilityk(')
y
 Trato  domina débilmente a ' (  ' ) si se cumple al menos la condición
(1)
Definición:
 Un trato  es individualmente racional si domina débilmente al trato
conflicto, es decir si   
 Un trato  es Pareto-óptimo si no existe otro trato ' que lo domine
.  (  ' )
 El conjunto S de todos los tratos individualmente racionales y Paretoóptimos se llama conjunto de negociación
02/10/2015
56
Ejemplo: Función de Utilidad de los agentes
Posibles tratos:
Pareto-óptimos:
Ind. racionales:
({a}, {b})
({a}, {b})
({b}, {a})
(, {a,b})
({a,b}, )
({a}, {b})
({b}, {a})
(, {a,b})
({b}, {a})
({a,b}, )
(, {a,b})
({a}, {a,b})
({b}, {a,b})
({a}, {a,b})
({b}, {a,b})
({a,b}, {a})
({a,b}, {b})
({a,b}, {a,b})
02/10/2015
Cjto de Negociación
({a}, {b})
({b}, {a})
(, {a,b})
Utilidad
(0,2)
(0,2)
(1,0)
57
Ejemplo de forma gráfica
Área de tratos
individualmente
racionales
Utility2
Trato conflicto
Trato ind. racional
Trato Pareto-óptimo.
Utility1
02/10/2015
Trato en conjunto
de negociación
58
El protocolo de concesiones
monótonas en los DOT
 Proceso de negociación:
 En cada instante t ≥ 0, el agente A ofrece el trato d(A,t) and B ofrece d(B,t), tal que
Ambos tratos d(i,t) pertenecen al conjunto de negociación S
 UtilityB( d(A,t) ) ≥ UtilityB( d(A,t-1) )
 UtilityA( d(B,t) ) ≥ UtilityA( d(B,t-1) )
 Un agente “cede” si la relación es estricta

 Final de negociación:
 Conflicto: en algún instante t ningún agente cede
Los agentes reciben la utilidad correspondiente al trato conflicto  (en los TOD: 0)
 Acuerdo: en algún instante t $ji{A,B}, Utilityj(d(i,t)) ≥ Utilityj(d(j,t))
 La cond. se cumple para A  el resultado es d(B,t)
 La cond. se cumple para B  el resultado es d(A,t)
 La cond. se cumple para ambos  elige d(k,t) tal que P(d(k,t))=max{P(d(A,t)),P(d(B,t))}

02/10/2015
59
La estrategia de Zeuthen en los DOT
Riesgo:
Risk i , t  
 ( i , t )   Utility i  ( k , t ) 
Utility i  ( i , t )   Utility i  
Utility
i
 En los DOT, Utilityi( ) = 0
 en cualquier instante t del proceso de negociación: 0  Risk(i,t)  1
 en cualquier instante t, si i cede entonces Risk(k,t) baja más que Risk(i,t)
Ronda inicial:
 d(i,0) = arg max {Utilityi( d ): dS }
Demás rondas:
 d(i,t) = d(i,t-1)
si Risk(i,t-1) > Risk(k,t-1)
 d(i,t) = arg max{Utilityi(d): dS  Risk(k,t)  Risk(i,t) } si Risk(i,t-1)  Risk(k,t-1)
02/10/2015
Negociación con la estrategia de
Zeuthen
Ejemplo:
 11 tratos en el conjunto de negociación,
denominados de d0 a d10
 Utilidad del trato di : Utility  i   i , (10  i ) 2 
t Utility((A,t)) Risk(A,t) ((A,t)) Utility((B,t)) Risk(B,t) ((B,t))
1
(10,0)
1,00
0
(0,100)
1,00
0
Ambos ceden
2
(9,1)
0,89
9
(1,81)
0,99
81
A cede
(8,4)
0,88
32
(1,81)
0,95
81
insuficiente
(7,9)
0,86
63
(1,81)
0,89
81
insuficiente
3
(6,16)
0,83
96
(1,81)
0,80
81
B cede
4
(6,16)
0,67
96
(2,64)
0,75
128
A cede
(5,25)
0,60
125
(2,64)
0,61
128
insuficiente
5
(4,36)
0,50
144
(2,64)
0,44
128
B cede
6
(4,36)
0,25
144
(3,49)
0,27
147
A cede
7
(3,49)
0,00
147
(3,49)
0,00
147
compromiso
02/10/2015
Utilidad de Tratos Mixtos
Definición: dado un DOT con dos agentes (T, {A1,A2}, c),
 un trato mixto [(D1,D2) : p] equivale
 al trato (D1,D2) con probabilidad p
 al trato (D2,D1) con probabilidad 1p
 el coste de un trato mixto [(Dk,Dj) : p] para el agente k es
Costk([(Dk,Dj) : p] )= p c(Dk) + (1p) c(Dj)
 la utilidad de un trato mixto [d : p] para el agente k es
Utilityk([d : p])= c(Tk) - Costk([d : p])
 las nociones de Racionalidad Individual, Optimalidad de
Pareto, y Conjunto de Negociación S siguen igual
02/10/2015
62
Ejemplo de forma gráfica
Utility2
[ ({a},{a,b}) : 0.5 ]
Trato conflicto
Tratos individualmente
racionales
Trato ind. racional
Trato Pareto-óptimo.
Utility1
Trato en conjunto
de negociación
Conjunto
de negociación con
tratos mixtos
02/10/2015
63
El resultado de proceso de regateo
Teorema (Harsanyi):
 Si ambos agentes utilizan la estrategia de Zeuthen, llegarán a un acuerdo
que maximiza el producto de sus respectivas utilidades
Protocolo de paso único:
 Los dos agentes hacen simultáneamente una única oferta
 Sólo se permiten ofertas que maximicen el producto de las utilidades
 Si ambas ofertas la maximizan, se elige una de forma arbitraria
Propiedades
 este protocolo es estable y más eficiente, aunque menos intuitivo…
02/10/2015
64
Información incompleta
Dominio de los carteros:
 Dos agentes, A1 y A2, cada uno con un conjunto de cartas que entregar
 Coste de un agente: entregar todas sus cartas desde la oficina de correos
(casilla a), y volver allí (distancia entre casillas igual a 1)
 En principio, los agentes sólo conocen su propio conjunto de cartas, por lo que
no pueden computar un trato directamente
 Se intercambia la información respecto a las cartas de cada uno antes de
“negociar”
Situación 1: los dos dicen la verdad
•
•
los dos tendrían que dar toda la vuelta
Resultado (según Teorema de Nash):
 = [({b,e,f},{}): 1/2] y UtilityA1() = 4
b
Posibilidades de engañar:
•
Tareas ocultas: no declarar tareas que uno tiene asignadas
•
Tareas fantasma: pretender tener que realizar tareas que no le han sido asignados a uno
02/10/2015
Engaño: tareas ocultas
Situación 2a: A1 miente y no declara f
•
pero sólo se permiten tratos puros
– A2 tendría que dar toda la vuelta, mientras que A1
sólo tendría que ir a f y volver
– A2 llevaría la carta de A1, puesto que esto beneficia
a A1 sin perjudicar a A2 (Optimalidad de Pareto)
– Resultado (perspectiva de A2): * = ({},{e,f})
– Luego, A1 sólo tendrá que llevar la carta oculta a b
(coste 2)
– Resultado (perspectiva de A1):
UtilityA1() = 8  2 = 6
– ¡Mentir es beneficioso!
02/10/2015
Engaño: tareas ocultas
Situación 2b: A1 miente y no declara f
•
y se permiten tratos mixtos
– Teorema de Nash: se elige * = [({e,f},{}): p]
tal que p maximiza la función
p*(-2,8) + (1-p)(6,0)
– Resultado (perspectiva de A2): * = [({e,f},{}): 3/8]
– En realidad:
• Stand alone cost real de A1 : 8
• Coste real del trato para A1: 3/8 * 8 + 5/8 * 2
– Resultado (perspectiva de A1):
UtilityA1() = 8  (34/8) = 33/4
– ¡En este caso, mentir no beneficia a A1!
02/10/2015
Engaño: tareas fantasma
Ejemplo: Dominio de los carteros
 Dos agentes, A1 y A2, cada uno con dos cartas que entregar en b y c respectivamente
 Coste para un agente: en función de la distancia recorrida (diferentes para las distintas
casillas)
 Si ambos declaran la verdad: se tira una moneda para asignar las tareas
•
02/10/2015
A1 miente en tratos puros:
•
A1 miente en tratos mixtos:
68
Otros dominios
 La características de una negociación no sólo
dependen del mecanismo (protocolo) empleado, sino
también del dominio
 Dominios orientados a metas (goal-oriented domains):
 Efectos laterales cualitativos de las acciones
 Ejemplo: mundo (síncrono) de los bloques
 Dominios orientados al valor (worth-oriented domains):
 Efectos laterales cuantitativos de las acciones
 Ejemplo: escenarios económicos
02/10/2015
69
Argumentación
Argumentación:
 Muchas veces un conflicto de interés es sólo aparente
 porque a un agente le falta información
 porque a un agente no llegar a una conclusión cierta/ ha sacado una
conclusión equivocada de su información
 La argumentación es el proceso de intentar convencer a los demás de
la veracidad de un hecho
Modos de argumentación (Gilbert,1994):
1. Modo lógico: “Si aceptas A y que A implica B, entonces debes aceptar B”
2. Modo emocional: “Cómo te sentirías si eso te sucediera a ti?”
3. Modo visceral : “¡Cretino!”
4. Modo “Kisceral”: “¡Esto es un dogma cristiano!”
02/10/2015
70
Modelo Lógico de Argumentación
Definición: un argumento Δ |- (Sentencia, Razones) consta
de tres partes:

Δ es un conjunto de formulas lógicas (probablemente
inconsistente)

Sentencia es una formula lógica conocida como conclusión

Razones es un conjunto de formulas lógicas tal que:
•
Razones  Δ; y
•
Sentencia se puede derivar de Razones
Definición: sean (f1, G1) y (f2, G2) argumentos apoyados en
alguna Δ D, entonces (f2, G2) puede ser rechazado (atacado)
de dos formas:
• (f1, G1) refuta (rebuts) (f2, G2) si f1  f2
• (f1, G1) mina (undercuts) (f2, G2) si f1  y2 para algún y  G2
Los dos casos se resumen bajo el término ataque
02/10/2015
71
Modelo Lógico de Argumentación

Humano ( Heracles ),

Arg 1  
Mortal
(
Heracles
),




 x Humano ( x )  Mortal ( x ) 

Ejemplo:


Humano ( Heracles )


Padre ( Heracles , Zeus )



Padre ( Apollo , Zeus )




   x Humano ( x )  Mortal ( x ) 



 x Divino ( x )   Mortal ( x ) 

 x Padre ( x , Zeus )  Divino ( x )  





x
Padre
(
x
,
Zeus
)

Divino
(
x
)





Padre ( Heracles , Zeus ),




Arg 2   Mortal ( Heracles ),  x Padre ( x, Zeus )  Divino ( x ) ,



 x Divino ( x )   Mortal ( x ) 






Arg
  x Padre ( x , Zeus )  Divino ( x ) ,  x Padre ( x, Zeus )  Divino ( x ) 
3

 Los argumentos Arg1 y Arg
 2 se refutan mutuamente
 El argumento Arg3 mina al argumento Arg2
 Sobre esta base se puede definir diferentes clases que definen la “fuerza” de los
argumentos …
 Se usa esencialmente en sistemas de diálogos para argumentación
02/10/2015
Otros mecanismos para lograr acuerdos
 Protocolos de Votación (voting mechanisms):
 cada agente tiene una relación de preferencia sobre un conjunto de posibles
acuerdos
 se elige una alternativa según un protocolo de votación
 Formación de coaliciones:
 agentes pueden formar coaliciones (subgrupos)
 cooperan con los miembros de su coalición, y compiten con los demás
 cuestiones:



¿Cuál es la estructura de coaliciones?
¿Cuál es el valor de cada coalición?
¿Cómo se reparte el valor de una coalición entre sus miembros?
 Mecanismos de mercado:
 búsqueda distribuida para el equilibrio general de un mercado
 ejemplo: Distributed price tâtonnement
02/10/2015
73
La Coordinación en los Sistemas
Multiagente
Indice:
1. Introducción
2. Negociación y Argumentación
3. Bibliografía
74
02/10/2015
74
Bibliografía General
 Ana Mas: Agentes software y sistemas multiagente.
Conceptos, arquitecturas y aplicaciones; Pearson, 2004,
Capítulo 4
 Wooldridge, M.: An Introduction to Multiagent Systems,
Wiley, 2002. Capítulos 6, 7, y 9.
 Rosenschein, J.; Zlotkin, G.: Rules of Encounter. MIT
Press, 1994. Capítulos 3 y 4
02/10/2015
75
Discusión próxima semana (2)
 “Co-ordination in Multi-Agent Systems”. H.S. Nwana, L. Lee and
N.R. Jennings. Software Agents and Soft Computing 1997: págs.:
42-58
 “The Interdisciplinary Study of Coordination”. Thomas W. Malone
and Kevin Crowston. ACM Computing Surveys, Vol. 26, No. 1,
March 1994
02/10/2015
76
Propuestas de Trabajo (i)
 Gmytrasiewicz, P.; Durfee, E.; Wehe, D. (1991): The Utility of
Communication in Co-ordinating Intelligent Agents. Proc. Nat. Conf.
on Artificial Intelligence (AAAI-91), pp. 166–172
 Gmytrasiewicz, P.; Durfee, E. (2000). Rational Coordination in
Multiagent Systems. Autonomous Agents and Multi-Agent
Systems Vol. 3, No. 4, Springer, 319-350
 Gmytrasiewicz, P.; Durfee, E. (2001). Rational Communication in
Multiagent Systems. Autonomous Agents and Multi-Agent
Systems Vol. 4, No. 3, Springer , 233-272
02/10/2015
77
Propuestas de Trabajo (ii)
 Rosenschein, J.; Zlotkin, G.: Rules of Encounter. MIT
Press, 1994. Capítulos 5 y 6
 Zlotkin, G. and Rosenschein, J.S.: Mechanisms for
Automated Negotiation in State Oriented Domains.
Journal of Artificial Intelligence Research, Volume 5,
1996, pp. 163-238.
02/10/2015
78
Propuestas de Trabajo (iii)
 Wooldridge, M.: An Introduction to Multiagent Systems, Wiley, 2002,
págs 148-159
 Sycara, K.: Persuasive Argumentation in Negotiation, Theory and
Decision, Vol.28, No. 3, May, 1990, págs. 203-242. .
 Jennings, N. et al.: Automated Negotiation: Prospects, methods,
challenges. Int. Journal of Group Decision and Negotiation 10(2).
2001, págs 199-215
 Reed, C.: Dialogue frames in agent communications. Proc. Inf. Conf
on Multiagent Systems (ICMAS), 1998, págs. 246-253
 Amgoud, L. et al.: Modelling dialogues using argumentation. Proc. Inf.
Conf on Multiagent Systems (ICMAS), 2000, págs. 31-38
02/10/2015
79
Otras propuestas
 Combinatorial Auctions.
 Mecanismos de votación.
 Market-based mechanisms.
02/10/2015
80
Descargar

Coordinación (Negociación y Argumentación)