Agentes y Sistemas Multi-Agentes Acuerdos · I Maximizar el bienestar social.Suma de utilidades. I...

Introduccion Subastas Negociacion

Agentes y Sistemas Multi-AgentesAcuerdos

Dr. Alejandro Guerra-Hernandez

Departamento de Inteligencia ArtificialFacultad de Fısica e Inteligencia Artificial

Universidad [email protected]

http://www.uv.mx/aguerra

Maestrıa en Inteligencia Artificial 2010


Temas

I ¿Como se alcanza un acuerdo en una sociedad de agentesindividualistas?

I Negociacion + Argumentacion = Acuerdos

I Los protocolos [Rosenschein y Zlotkin, 1994] definen las reglasdel encuentro para todos los participantes en una negociacion.

I Dado un protocolo particular ¿Como podemos disenar unaestrategia que los agentes puedan usar cuando negocian? ...Maximizar utilidad en la Practica.


Propiedades de los Protocolos

I Las convencionales: Evitar bloqueos.I Las Multi-Agente:

I Garantizar el exito. Se logra un acuerdo.I Maximizar el bienestar social. Suma de utilidades.I Eficiencia de Pareto. Si un agente mejora, otro empeora.I Racionalidad individual. No hay de otra.I Estabilidad. Todos reciben estimulo (Equilibrio Nash).I Simplicidad. Todos entienden.I Distribucion. Nada es centralizado, comunicacion mınima.

I SMA y Teorıa de Juegos [Shoham y Leyton, 2008].


No son tan ajenas

I Adjudicacion de bienes:Modigiani 52.8 milloneseuros.

I EBAY (http://www.ebay.com)

I Simples.

I Automatizables.

I SMA: Adjudicacion de bienes,tareas y recursos.


Estructura

I Un agente subastador que ofrece un bien.

I Un conjunto de agentes licitadores que desean ese bien.

I El subastador desea maximizar el precio del bien (vıa elprotocolo).

I Los licitadores desean minimizarlo (via la estrategia).


Valoraciones

I Si el bien tiene el mismo valor para todos los licitadores,decimos que su valor es comun.

I Si el bien tiene diferentes valores para diferentes licitadores,decimos que su valor es privado.

I Ejemplo: el ultimo dolar que se gasto Michael Jackson.

I Correlacionada. Combinacion de las anteriores.

I Ejemplo: Marchantes de arte.


Variaciones sobre el mismo tema

I Determinacion del ganador. Precio primero vs. Precio segundo.

I Conocimiento de ofertas. Abiertas vs. Selladas.

I Ofertas. Un tiro vs. Ascenentes / Descendentes.


Subasta inglesa

I El subastador sugiere un precio de reserva para el bien (puedeser cero). Si ningun agente hace una ofera superior, el bien esadjudicado al subastador por ese precio.

I Los demas agentes hacen ofertas, que deben ser superiores ala actual. Todos los agentes pueden ver las ofertas hechas porotros agentes y pueden participar en el proceso, si ası lodesean.

I Cuando ningun agente eleva la oferta, el bien es adjudicado alagente que ha hecho la mas alta oferta por ese precio.


Estrategia y Propiedades

I La estrategia dominante parece ser ofertar sucesivamentepequenas cantidades sobre la oferta actual hasta que la ofertaalcance el precio de la valuacion actual del bien y entoncesretirarse.

I ¿Que sucede cuando el valor del bien subastado no es bienconocido?

I ¿Deberıa estar contento el ganador por obtener el bien por unprecio igual o menor al valor privado? ¿O deberıa preocuparsede que los demas licitadores decidieron retirarse?

I Cuando se da el caso de que el ganador sobrevalorael bien, se habla de la maldicion del ganador.


Subasta holandesa

I El subastador inicia ofreciendo un bien a un precioartificialmente alto.

I El subastador entonces baja continuamente el precio del bienen una pequena cantidad, hasta que un agente hace unaoferta por el, que es igual al valor de la oferta actual.

I El bien se adjudica al agente que hizo la oferta.



I No hay estrategia dominante.

I La maldicion del ganador tambien esta presente.


Subasta primer precio, sellada

I Subasta de un tiro y quiza el caso mas simple.

I Solo hay una ronda de ofertas que los licitantes hacen llegar alsubastador del bien.

I No hay rondas subsecuentes y el bien se adjudica al agenteque haya hecho la oferta mayor.

I El ganador paga el precio de su oferta. No hay por tanto,oportunidad para que los otros licitadores, ofrezcan ofertasmas altas por el bien.

I La estrategia dominante es ofrecer menos que el verdaderovalor del bien ¿Que tanto menos? Depende de lo queofrezcan los otros agentes.

I No hay solucion general para este caso.


Subasta de Vickrey

I Es la menos usada y quiza la menos intuitiva de todas lassubastas vistas.

I Este es el caso de una subasta de segundo precio, sellada.

I Eso significa que solo hay una ronda de negociacion, en lacual cada licitador propone una sola oferta.

I El bien se adjudica al agente que hizo la mayor oferta, peropaga el precio de la segunda mejor oferta.



I Tienen una verdadera estrategia dominante –ofertar elverdadero valor del bien:

I Supongamos que ofertamos mas que el valor real del bien. Enese caso, el bien nos sera adjudicado, pero se corre el riesgo deadquirir el bien a un precio superior a su valor real. Si se ganaen esas circunstancias, la compra fue una perdida.

I Supongamos que ofertamos menos que el valor real del bien.Se reduce la posibilidad de ganar el bien. Pero aun ganando enese caso, haber ofrecido menos no tiene efecto pues el precio apagar es el de la segunda mejor oferta.

I Dan lugar a situaciones anti-sociales: castigar alganador!


Ganancia esperada (subastador)

I Para licitadores neutrales al riesgo, la ganancia esperada esprobablemente identica en los cuatro casos de subastadiscutidos. Esto es, el subastador puede esperar una gananciasimilar en todos los casos.

I Para licitadores con aversion al riesgo, las subastas holandesay de primer precio, sellada, llevan a ganancias mas altas parael subastador.

I Para subastadores con aversion al riesgo, funcionan mejorlas subastas Vickrey e inglesa.


Mentiras y colusiones

I Colusion. Los licitadores pueden aliarse para obtener un preciobajo del bien. Modificar el protocolo para que los licitadoresno se conozcan entre ellos, aunque esto no es posible ensubastas abiertas.

I Honestidad del subastador. En las subastas Vickrey, se puedementir acerca del monto de la segunda mejor oferta, haciendopagar mas de esta forma al ganador. Firmar las ofertas, deforma que el ganador pueda verificar el resultado; o contratara un tercero, confiable, para procesar las ofertas. En subastasabiertas, no hay forma que el subastador mienta.

I Falsos licitadores en las subastas inglesas.


Ejemplo Jason

1 MAS auction {2

3 infrastructure: Centralised4

5 agents: ag1; ag2; ag3;6 auctioneer agentArchClass AuctioneerGUI;7 }


Diagrama General


Subastador (1)

1 /* beliefs and rules */2 all_bids_received(N) :- .count(place_bid(N,_),3).3

4 /* plans */5 +!start_auction(N) : true // created by the GUI6 <- -+auction(N);7 -+winner(N, noone, 0);8 .broadcast(tell, auction(N)).9

10 @pb1[atomic]11 +place_bid(N,V)[source(S)]12 : auction(N) & winner(N,CurWin,CurVl) & V > CurVl13 <- -winner(N,CurWin,CurVl);14 +winner(N,S,V);15 .print("New winner is ",S, " with value ",V);16 !check_end(N).


Subastador (2)

1 @pb2[atomic]2 +place_bid(N,_) : true3 <- !check_end(N).4

5 +!check_end(N)6 : all_bids_received(N) &7 winner(N,W,Vl)8 <- .print("Winner is ",W," with ", Vl);9 show_winner(N,W); // show it in the GUI

10 .broadcast(tell, winner(W));11 .abolish(place_bid(N,_)).12 +!check_end(_).


Licitador 1 (siempre 6)

1 // this agent always bids 62

3 +auction(N)[source(S)] : true4 <- .send(S, tell, place_bid(N,6)).


Licitador 2 (alianza con 3)

1 default_bid_value(4).2 ally(ag3).3

4 +auction(N)[source(S)] : not alliance5 <- ?default_bid_value(B);6 .send(S, tell, place_bid(N,B)).7

8 +auction(N)[source(S)] : alliance9 <- .send(S, tell, place_bid(N,0)).

10

11 +alliance[source(A)]12 : .my_name(I) & ally(A)13 <- .print("Alliance proposed by ", A);14 ?default_bid_value(B);15 .send(A,tell,bid(I,B));16 .send(A,tell,alliance(A,I)).


Licitador 3 (alianza con 2)

1 default_bid_value(3).2 ally(ag2).3 threshold(3).4

5 +auction(N)[source(S)]6 : (threshold(T) & N < T)7 |8 (.my_name(I) & winner(I) & ally(A) & not alliance(

I,A))9 <- !bid_normally(S,N).

10

11 +auction(N)[source(S)]12 : .my_name(I) & not winner(I) & ally(A) & not

alliance(I,A)13 <- !alliance(A);14 !bid_normally(S,N).


Licitador 3...

1 @palliance2 +auction(N)[source(S)]3 : alliance(_,A)4 <- ?default_bid_value(B);5 ?bid(A,C);6 .send(S, tell, place_bid(N,B+C)).7

8 +!bid_normally(S,N) : true9 <- ?default_bid_value(B);

10 .send(S, tell, place_bid(N,B)).11

12 @prop_alliance[breakpoint]13 +!alliance(A) : true14 <- .send(A,tell,alliance).


Casos y componentes

I Dos casos: dominios orientados a tareas y dominos orientadosa valor.

I Para el caso general, se tienen 4 componentes:I Un conjunto de negociacion que representa el espacio de

posibles propuestas que un agente puede hacer.I Un protocolo que define las propuestas legales que los agentes

pueden hacer, en funcion de un historial de negociacionesprevias.

I Una coleccion de estrategias, una por cada agenteparticipante, que determina que propuestas hara cada agente.Normalmente la estrategia que un agente usa es privada.

I Una regla que determina cuando se ha alcanzadoun acuerdo y cual es ese acuerdo.


Multimodalidad

I Las subastas son ejemplos de negociaciones sobre un tema,por ejemplo, el valor de un bien para su venta. En ese caso lapreferencia de los participantes suele ser simetrica, lo que esbueno para el comprador, no suele ser bueno para el vendedor;y en el analisis es facil entender el concepto de concesion.

I Ahora consideren otro ejemplo, cuando compran un auto,aunque el precio es relevante, en realidad negocian muchosotros factores: la duracion de la garantıa, el serviciopost-venta, accesorios incluidos, etc. El concepto deconcesion es menos claro en esos casos.


Espacio de acuerdos posibles

I Exponencial en el numero de variables.

I En un dominio donde los agentes negocian sobre el valor de nvariables booleanas v1, . . . , vn, evidentemente hay 2n tratosposibles en ese problema (asignaciones diferentes de falso overdadero a las variables en cuestion).

I Si los atributos tienen m posibles valores, entonces el espaciode negociacion tienen mn posibles tratos.


¿Cuantos agentes?

I Negociacion uno a uno. Un caso especial es cuando laspreferencias de los agentes son simetricas con respecto atodos los tratos posibles. Ej. Los escenarios de compra venta.

I Negociacion muchos a uno. Es el caso de las subastas. Estoscasos pueden tratarse como iteraciones de negociaciones unoa uno.

I Negociacion muchos a muchos. Por ejemplo en la bolsa devalores. En el peor de los casos habra n agentes participandoactivamente en la negociacion, con lo cual tenemosn(n − 1)/2 hilos de negociacion.


Dominios orientados a Tareas

I Formalmente [Rosenschein y Zlotkin, 1994] se definen comouna tripleta 〈T ,Ag , c〉 donde:

I T es el conjunto (finito) de todas las posibles tareas.I Ag = {1, . . . , n} es el conjunto (finito) de los agentes que

participan en la negociacion.I c : P(T )→ R+ es la funcion que define el costo de ejecutar

cada subconjunto de tareas en terminos de un numero realpositivo.


Ejemplo

I Tienes 3 hijos, hay que llevarlos a diferentes escuelas.

I Su vecino tiene 4 hijos, idem.

I Llevar a un nino puede ser modelado como una tareaindivisible.

I Usted y su vecino pueden discutir la situacion y llegar alacuerdo de lo que es mejor para ambos (por ejemplo, llevar ados ninos que comparten el mismo destino y son de diferentefamilia, para ahorrar un viaje –Costo).

I Acuerdos: Llevar a los ninos en dıas pares y el vecino enimpares; o bien, llevar a 2 ninos y que el vecino seencargue de otros 2, etc.


Costo

I Debe ser monotono en el sentido de que el hecho de agregaruna tarea, nunca decrementa el costo. Formalmente, siT1,T2 ⊆ T son conjuntos de tareas, tales que T1 ⊆ T2

entonces el c(T1) ≤ c(T2).

I El costo de no hacer nada es cero: (c(∅) = 0.


Encuentro

I Ocurre cuando los agentes Ag son asignados con tareas delconjunto T .

I Intuitivamente, cuando un encuentro ocurre, hay un potencialde que los agentes alcancen un acuerdo para volver a asignarlas tareas entre ellos.

I Formalmente un encuentro es una coleccion de tareas〈T1, . . . ,Tn〉, donde para toda i tenemos que i ∈ Ag yTi ∈ T .


Trato

I Concentremos nuestra atencion en escenarios de negociacionuno a uno u asumamos que los agentes son {1, 2}.

I Dado un encuentro 〈T1,T2〉, un trato sera muy similar a unencuentro: una asignacion de las tareas T1 ∪ T2 a los agentes1 y 2. Formalmente, un trato puro es un par 〈D1,D2〉 dondeD1 ∪ D2 = T1 ∪ T2.

I Su semantica es que el agente 1 esta comprometido a llevar acabo las tareas en D1 y el agente 2 las tareas en D2.


Utilidad y trato conflictivo

I El costo asumido por el agente i en un trato δ = 〈D1,D2〉 esc(Di ) y se denota como costoi (δ).

I La utilidad del trato δ para un agente i es la diferencia entreel costo para el agente i de llevar a cabo las tareas Ti , tal ycomo se le asignaron en el encuentro, y el costoi (δ) de lastareas asignadas en el trato:

utilidadi (δ) = c(Ti )− costoi (δ)

I Si es negativa, significa que le conviene mas ejecutar lastareas tal y como le fueron asignadas en el encuentro.

I Lo mismo ocurre si la negociacion falla, por esoΘ = 〈T1,T2〉 denota el trato conflictivo.


Dominancia y tratos

I Un trato δ1 se dice que domina a uno δ2 (se escribe δ1 � δ2)si y solo si:

1. El trato δ1 es al menos tan bueno para todo agente como δ2:

∀i ∈ {1, 2}, utilidadi (δ1) ≥ utilidadi (δ2)

2. El trato δ1 es mejor para algun agente que δ2:

∃i ∈ {1, 2}, utilidadi (δ1) > utilidadi (δ2)


Trato Pareto optimo

I Si el trato δ1 domina a otro trato δ2, entonces deberıa serclaro para todos los participantes que δ1 es mejor que δ2.

I Se dice que el trato δ1 domina debilmente a δ2 (se escribeδ1 � δ2) si al menos la primer condicion se cumple.

I Se dice que un trato que no es dominado por ningun otro espareto optimo. Formalmente, un trato δ es pareto optimo sino existe un trato δ′ tal que δ′ � δ.


Trato individualmente racional

I Se dice que un trato es racional individualmente si dominadebilmente al trato conflicto Θ.

I Si el trato no es racional individualmente, entonces al menosun agente obtiene mas utilidad ejecutando las tareas tal ycomo le fueron asignadas en el encuentro.

I Formalmente, un trato δ es racional individualmente si y solosi δ � Θ.


Conjunto de Negociacion

I Un conjunto de tratos que son racionales individualmente ypareto optimos.

I La idea detras de la primera restriccion es que no tiene casonegociar, si se ofrece un trato tal que uno de los agentesprefiera el trato conflicto;

I la segunda restriccion nos dice que no tiene sentido ofrecer untrato tal que el otro agente puede obtener mas utilidad sindanarme.


Protocolo de concesion monotona

I En la primera ronda u = 0, ambos agentes proponensimultaneamente un trato del conjunto de negociacion.

I Un acuerdo se alcanza si los dos agentes proponen tratos δ1 yδ2 respectivamente, tal que utilidad1(δ2) ≥ utilidad1(δ1),o bien utilidad2(δ1) ≥ utilidad2(δ2).

I Si las ofertas de ambos agentes son iguales o mejores que lasdel encuentro, entonces se elige una al azar. Si no se elige lamejor.

I Si no se logra un acuerdo, se propone a una nueva rondau + 1. Ningun agente puede hacerle una propuesta al otroagente, que sea menos preferida que la ofertada enla ronda u.

I Si ningun agente hace una concesion la negociaciontermina y se adopta el trato conflicto.


Propiedades

I Es claro que este protocolo es efectivamente verificable, en elsentido de que ambas partes pueden ver si las reglas delmismo se estan siguiendo.

I Usando este protocolo se garantiza que la negociacion termina(con o sin acuerdo) en un numero finito de pasos.

I Eso si, el protocolo no garantiza que se llegue a un acuerdorapidamente, puesto que el numero de ofertas posibles esO(2|T |) y por lo tanto es concebible que la negociacioncontinue por un numero de rondas exponencial en elnumero de tareas a ser asignadas.


Estrategia

I No hemos dicho nada sobre la estrategia a seguir por losparticipantes en una negociacion, cuando estamos siguiendo elprotocolo de concesion monotona.

I Estudiando el protocolo, pareciera que hay tres cuestiones aabordar:

I ¿Cual debe ser la primer propuesta de un agente?I Dada una ronda ¿Quien debe conceder?I Si un agente concede ¿Cuando debe conceder?

I La primer pregunta tiene una respuesta casi directa: laprimer propuesta de un agente debe ser sutrato preferido.


Estrategia de Zeuthen

I Con respecto a la segunda pregunta, la idea de la estrategiaZeuthen es medir el disposicion de los agentes por el riesgo aun conflicto.

I Intuitivamente, un agente estara dispuesto al riesgo de unconflicto si la diferencia en la utilidad de la propuesta actual yel trato conflicto es baja.

I En cambio, si la diferencia es grande, entonces el agente tienemas que perder y tratara de evitar el conflicto.


Riesgo

I El riesgo del agente i en la ronda t se mide como sigue:

riesgoti =utilidad i pierde concediendo y aceptando oferta de j

utilidad i pierde no concediendo y causando conflicto

I o su equivalente:

riesgoti =

{1 Si utilidadi (δ

ti ) = 0

utilidadi (δti )−utilidadi (δtj )

utilidadi (δti )

En otro caso


¿Cuanto hay que conceder?

I Solo lo necesario.

I Si concede demasiado poco, en la siguiente ronda el balancede riesgo indicara que aun tiene mas que perder en caso deconflicto y tendra que volver a ceder. Esto es ineficiente.

I Pero si cede demasiado, estara desperdiciando utilidad. Por lotanto, deberıa ceder lo suficiente como para cambiar elbalance de riesgo y que en la siguiente ronda el otro agenteconceda.


Propiedades

I Este protocolo no garantiza exito, pero garantiza terminacion.

I No garantiza maximizar el bienestar social, pero garantiza quesin un acuerdo es alcanzado, este es pareto optimo.

I Es racional individualmente y es descentralizado.

I Un punto interesante es que la combinacion de protocolo yestrategia esta en equilibrio de Nash, por tanto la estrategiapuede hacerse publica (si un agente la usa, lo mejor para otroagente es adoptarla).

I Problemas, cualquier problema real, tendra un espacio detratos demasiado grandes como para computarlos.

I Para n > 2 agentes, las extensiones no son obvias.


Trampeando

I Tareas fantasmas y tramposas. Ej. En el caso de repartirse alos ninos para llevarlos a la escuela, el clasico es –Tengo que iral entierro de mi abuelita. Otra forma de engano es inventarsetareas artificiales dependientes de dominio. Este caso es masdifıcil de detectar que el primero.

I Tareas ocultas. Ej. En el caso de los ninos nuevamente, siresulta que dos ninos van a escuelas vecinas pero lejanas, unagente puede ocultar que debe ir allı.


Dominios Orientados por Valor

I Formalmente se define como una tupla 〈E ,Ag , J, c〉, donde:I E es el conjunto de posibles estados del ambiente.I Ag = {1, . . . , n} es el conjunto de posibles agentes.I J es el conjunto de posibles planes conjuntos.I C : J × Ag → R es una funcion de costo que asigna a cada

plan j ∈ J y a cada agente i ∈ Ag un numero real querepresenta el costo C (j , i) para el agente i ejecutando el plan j .


Encuentros

I Se definen por la tupla 〈e,W 〉 donde:I e ∈ E es el estado inicial del ambiente.I W : E × Ag → R es una funcion de valor, que asigna a cada

estado del ambiente e ∈ E y cada agente i ∈ Ag un numeroreal W (e, i), el valor para el agente i de estar en e.


Hacer lo correcto solitos

I Los planes se escriben con la notacion j : e1 e2; paraindicar que el plan conjunto j nos lleva del estado e1 al estadoe2 del ambiente.

I Ahora, supongamos que el agente i opera solo en su medioambiente, que esta en el estado inicial e0.

I En este caso, no hay necesidad de negociar, basta con que elagente elija el plan j iopt y que el plan sea ejecutable en eo deforma que:

j iopt = arg maxj :e0 e∈E

W (i , e)− C (j , , i)


Con la ayuda de tus amigos

I En el contexto Multi-Agentes, puede parecer que el agente nopuede hacer nada mejor que jopt pero esto no es cierto.

I Un agente puede beneficiarse de la presencia de otros agentes,al ser capaz de ejecutar planes conjuntos y llegar ası a estadosdel ambiente, a los cuales no habrıa podido llegar solo.

I Si no hay planes conjuntos que superen a j iopt , entonces no hayinteraccion y la negociacion no es racional individualmente.

I Por otra parte, si los planes interfieren, no hay mas opcionque negociar. Por ejemplo: si mi mujer y yo necesitamos elauto manana y solo tenemos un auto.


Bibliografıa

J. S. Rosenschein and G. Zlotkin.Rules of Encounter: Designing Conventions for Automated Negociation amongComputers.MIT Press, Cambridge, MA, USA, 1994.

Y. Shoham and K. Leyton-Brown.Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.Cambridge University Press, 2008.

Agentes y Sistemas Multi-Agentes Acuerdos · I Maximizar el bienestar social.Suma de utilidades. I...

Documents

Transcript of Agentes y Sistemas Multi-Agentes Acuerdos · I Maximizar el bienestar social.Suma de utilidades. I...