1 Confianza y Reputación en Sistemas Multi-AgenteRamón Hermoso Traba Universidad Rey Juan Carlos

2 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 2

3 1. Introducción Aproximación al problemaConfianza + Coste Riesgo … O: comprar un coche nuevo P1 P2 C1 P3 C1 Conclusión: nosotros tratamos el concepto de confianza, pero hay otros factores que influyen en la toma de decisiones. Acción: Comprar coche a P2 P4 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

4 Confianza y Reputación en Sistemas Multi-Agente1. Introducción Aproximación al problema Human-based metaphores again?... Ok, coordination is fine, but… Any other factor that leads the agent to act? Come on!, this is a course about agents!!! What about “trust” on others? Let me tell you something… bla, bla, bla Bob Alice 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

5 Confianza y Reputación en Sistemas Multi-Agente1. Introducción Definiciones [Gambetta90] “La confianza es la probabilidad subjetiva por la que un individuo A espera que otro individuo B realice una determinada acción de la que el bienestar de A depende” RAE Confianza: esperanza firme que se tiene de alguien o algo Reputación: prestigio o estima en que son tenidos alguien o algo Falta de consenso semántico Confianza ≠ Reputación Trust ≠ Reputation ≠ Confidence ≠ Reliability ≠ Willingness … 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

6 Introuducción DefinicionesDificultad de modelización Medida de la estima o del prestigio Subjetividad ¿Qué es algo bueno? ¿Y para quién? Dificultad para el diseño Medida cuantitativas o cualitativas… tAB = | tBA = | tBC = “bueno” | tBA = k Distintos campos confluyen: informática (modelos computacionales), sociología (redes sociales), psicología (estados mentales), economía (funciones de utilidad, toma de decisiones, etc.), … 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

7 Determinación de acciones1. Introducción Definiciones Modelos de confianza Sirven para estimar la confianza en un agente/situación Predicen el comportamiento en una hipotética interacción confianza = Confianza ≠ Confiar La confianza se usa como factor en procesos de selección de acciones: Confianza Selección de la acción Planificación Determinación de acciones Búsqueda de la acción Negociación / Ejecución 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

8 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 8 8

9 Modelos de confianza ComercialesDominios comerciales o redes sociales Ejemplo: eBay Usado como ayuda al usuario Valoración de opiniones distribuida Visión de valoraciones unívoca Naturaleza de las valoraciones: Suma de opiniones numéricas individuales: +1,0,-1 Comentarios textuales Visión global de la reputación de los usuarios 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

10 Modelos de confianza ComercialesTrip Advisor (www.tripadvisor.es) Opiniones Votaciones Ránkings Positivos (preferencias) Negativos (características a evitar) 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

11 Modelos de confianza ComercialesDominios comerciales o redes sociales Ejemplo: eConcozco, Friendster, Facebook, … Aplicable a todo tipo de interacciones Intercambio de datos Redes P2P Descarga de ficheros Usan valoraciones como indicación al usuario Opiniones Ratings 1..10 “muy bueno” 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

12 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 12 12

13 Modelos de Confianza Tipos de modelosModelos centralizados vs. distribuidos Centralizados Mejor gestión de la información Presunción de autoridad (¿debemos confiar en ella?) Menos flexible / más dependiente Distribuidos Permiten subjetividad Mecanismo adaptativo y autónomo de control social  normas sociales emergentes (sociedades humanas) Antropomorfismo Más robusto Modelos centralizados y distribuidos  ¡¡¡compatibles!!! 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

14 Modelos de Confianza Investigación¿Cómo lograr sistemas estables usando la confianza? Empatía o reciprocidad con los agentes a partir de factores como la disposición o la fiabilidad (otros muchos) Se obtienen y evolucionan por Modelos de Confianza La confianza será una medida para decidir la interacción con otro agente (necesaria pero no suficiente) Interacciones directas e indirectas Información interna (experiencia pasada) o externa (opiniones de terceros) Diseño de protocolos y mecanismos para las interacciones (reglas de encuentro) 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

15 Modelos de Confianza InvestigaciónProblemas Ajuste de la confianza tras una experiencia directa Ajuste de la confianza tras una experiencia indirecta (p.ej. en una organización o grupo) Cómo agregar opiniones de otros a las experiencias locales propias Cómo ajustar la confianza en agentes que han servido como fuentes de reputación Exploración vs. Explotación 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

16 Modelos de confianza InvestigaciónFactores a tener en cuenta: Capacidad Disposición Permisos Utilidad (no sólo económica…) Altruismo Egoísmo Dependencia … 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

17 Modelos de confianza InvestigaciónDos formas de conceptualizar la confianza en sistemas multi-agente Nivel individual: creencia sobre el comportamiento futuro de otro agente en una situación determinada  lo mejor para el agente Nivel de sistema: usada para forzar a los agentes a actuar de forma benevolente (normas de comportamiento emergente)  lo mejor para el sistema Conceptos: honestidad, benevolencia, malicia, incompetencia, altruismo  difíciles de distinguir 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

18 Modelos de confianza InvestigaciónClasificación de modelos de confianza Modelos basados en Aprendizaje y Evolución Modelos basados en Reputación Modelos Socio-Cognitivos Modelos para Organizaciones Alineación semántica 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

19 Modelos de confianza Investigación – Aprendizaje y EvoluciónNo siempre escenarios cooperativos Aunque éstos no son ideales Malevolencia Incompetencia Desconocimiento, … Utilidad vs. Confianza (equilibrio) [Wu,Sun]  Confianza emerge como resultado de la evolución de estrategias en varias interacciones Mayor ganancia a largo plazo para los agentes “buenos” sacrificando parte de su utilidad a corto plazo (Dilema del prisionero) Umbral en el número de interacciones (característico para el cálculo) Variabilidad de los resultados 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

20 Modelos de confianza Investigación – Aprendizaje y Evolución[Birk]  Confianza también emerge del aprendizaje Dar más peso a los objetivos sociales vs. objetivos individuales Metáfora de la sociedad (inversión) Ciclo de actuación 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

21 Modelos de confianza Investigación – Aprendizaje y EvoluciónCiclo de Birk Equilibrio final Aprenden ( beneficio global) Mayoría corrupta Mayoría cooperativa Explotan ( beneficio individual) 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

22 Modelos de confianza Investigación – Aprendizaje y EvoluciónProblemas: Asumen información completa (estrategias, recompensas, utilidades,…) Probados con restricciones fijas, no en el mundo real Resultado de interacciones  valor dicotómico (0 ó 1) 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

23 Modelos de confianza Investigación - ReputaciónOpinión o vista de alguien acerca de algo Confianza ≠ Reputación Reputación es un medio para la Confianza (ej. eBay) Líneas de investigación en Reputación: Métodos para recoger ratings acerca de lo “bueno” que es el agente Métodos de razonamiento para la agregación de esa información Mecanismos de actualización (nuevos pesos) Recuperación y agregación con Redes Sociales Representación mediante grafos (relaciones) Los ratings “fluyen” entre los nodos por los arcos [Schillo et al.] Honestidad y Altruismo Posibilidad para los agentes de adquirir información de otros 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

24 Modelos de confianza Investigación - ReputaciónAgregación Combinación de valores de reputación que llegan a un agente Ejemplo: eBay (+1, -1). Comentarios? Modelos basados en teorías más sólidas: [Yu y Singh]  Teoría de Dempster-Shafer  Funciones de creencia - tres tipos de valores: Trustworthy Untrustworthy Uncertain 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

25 Modelos de confianza Investigación - ReputaciónConcepto de witness Testigos o fuentes de reputación Problema: Asunción de que nunca mienten Cómo elergir las fuentes de reputación Todo intercambio de información implica riesgo de imprecisión (casual o intencionada)  A más intercambio mayor riesgo Soluciones: [Schillo]  honestidad y altruismo [Sen y Dutta]  probabilidad de mentira sobre los testigos 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

26 Modelos de confianza Investigación - Reputación[Sabater y Sierra]  3 dimensiones de la reputación: Dimensión individual Reputación como suma ponderada de impresiones subjetivas que derivan de interacciones directas Dimensión social Impresión del grupo de a1 acerca de a2 Impresión del grupo de a1 acerca del grupo de a2 Impresión de los agentes del grupo de a2 sobre su compañero Dimensión ontológica 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

27 Modelos de confianza Investigación - ReputaciónBúsqueda de un modelo de confianza basado en reputación: Más valor a experiencias propias Cuanto mayor es el intercambio de información mayor es la probabilidad de hacer un razonamiento inexacto (incompetencia – malevolencia) Buscamos un equilibrio entre Razonamiento local  experiencia propia hasta ahora Información externa  reputación Confianza 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

28 Modelos de confianza Investigación – CognitivosCreencias acerca de la valoración del entorno y las características del agente evaluado (estado mental) Cómo se crea y evoluciona la confianza como atributo mental Castelfranchi (ISTC-CNR)  visión cognitiva de la confianza vs. visión cuantitativa (para agentes BDI) Competencia Buena voluntad Persistencia Motivación Problemas Les falta base experiental (“muy sociológico”) Costosos Combinación con modelos probabilísticos 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

29 Modelos de confianza Investigación – Orientados a OVModelos de confianza orientados a organizaciones de agentes Organización  SMAs + restricciones Roles, interacciones, normas, … Aprovechan la información de la organización para mejorar modelos de confianza Similitud de roles/interacciones Argumentación con normas 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

30 Modelos de confianza Investigación – Orientados a organizacionesDefinición de la Organización Proporcionado por la organización Problema de decisión del agente Los agentes deben cumplir objetivos Los agentes deben realizar diversas interacciones para cumplir estos objetivos De entre los agentes capacitados (por su rol) para realizar las interacciones, ¿a cuál de ellos elegir? 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

31 Modelos de confianza Investigación – Orientados a OVLos agentes mantienen una Local Interaction Table (LIT): Estructura de datos que compila los resultados de las interacciones pasadas Indexados por claves del tipo agente/rol/interaction () Con valores asociados de confidence y reliability : unidad atómica “agente X jugando el rol Y en la interación Z” Confidence (cA ): de la propia experiencia del agente Reliability (rA ): mide cómo de seguro está un agente acerca de su propio valor de confidence en la situación 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

32 Modelos de confianza Investigación – Orientados a OVEnfoque básico: “… un agente A jugando el rol Estudiante necesita encontrar un compañero para un tipo de práctica en una asignatura específica” El estudiante mirará en su LIT las interacciones pasadas haciendo ese tipo de prácticas (I) con otros estidiantes (R) El agente A seleccionará a aquel agente con una mayor confidence en su LIT poniendo atención únicamente en aquellas entradas , donde X puede ser cualquier otro agente 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

33 Modelos de confianza Investigación – Orientados a OVProblema: la LIT puede ser incompleta No hay entradas para la situación Existe baja precisión en los valores para las entradas Hipótesis: los agentes se comportan de manera similar cuando juegan roles similares o actúan en interacciones similares Los valores de confidence pueden ser aproximados a partir de las entradas en la LIT del agenteen lugar de preguntar a fuentes de reputación Experiencias con un agente en roles/interacciones similares pueden ser usadas para aproximar mejor valores de confidence Las similitudes pueden ser obtenidas a partir de las taxonomías de roles e interacciones que facilita la organización 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

34 Modelos de confianza Investigación – Orientados a OVBasic trust model aplicado a los datos de la LIT: Sacamos partido a la estructura de la organización (inference trust model): Cálculo de la Similitud: Actualización de confidence: Actualización de la reliability: basado en el número de interacciones y en su variabilidad 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

35 Modelos de confianza Investigación – Alineación semánticaLínea de investigación en dominios SOC Especialmente  Semantic Web Services Cualquier dominio de intercambio de información Solución: definir ontologías ‘ad-hoc’ Problema: mundo de la heterogeneidad ¿Qué es 0.5 en [0..1]? ¿0.7 es bueno para ti? ¿Cómo identificar situaciones iguales o similares? “Traductores” semánticos Entidades intermedias Interpretan lo que quieren decir Como con los lenguajes de representación del conocimiento Técnicas más avanzadas Integración de ontologías a través de reglas … 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

36 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 36 36

37 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Agent, Reputation and Trust (ART) testbed Motivación Excesiva heterogeneidad de las métricas para evaluar modelos de confianza Unificación de perspectivas Entorno común de experimentación La competición hace más llamativa la herramienta 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

38 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

39 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Tasadores reciben clientes que pagan precio fijo por tasación Las pinturas se distribuyen aleatoriamente entre las eras Al pasar rondas los mejores tasadores recibirán más clientes (y por tanto más beneficios) 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

40 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Tasadores saben su nivel de expertise en cada era Tasadores no saben el nivel de los demás Tasadores pueden comprar reputaciones, por un precio fijo, de otros tasadores. Valor de reputación entre 0 y 1, valoración sólo para comunicación entre agentes No se fuerza a usar una representación interna fija 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

41 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

42 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Compra/Venta de opiniones Por cada pintura, un tasador puede pedir opiniones (a un precio fijo) de otros tasadores La simulación genera opiniones sobre las pinturas para los tasadores que aceptan dar opiniones La precisión de la opinión es proporcional al expertise del agente que da la opinión sobre la era del cuadro y al dinero invertido en la opinión 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

43 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Métricas De un agente Dinero del ganador Error medio cometido en las tasaciones Desviación típica del error cometido en las tasaciones Número de cada tipo de mensajes intercambiados De la sociedad de agentes Saldo de cada agente Ganancia de cada agente en cada iteración Número de mensajes y transacciones ocurridas Distribución de transacciones entre agentes 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

44 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

45 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - ART Ventajas Intento de unificar visiones y criterios No fija la representación del conocimiento de los agentes Aceptado por la comunidad (bajando la popularidad  ) Desventajas Orientado a maximizar la función de tasación Teoría de juegos no debería ser el fin En una misma población  Dilema del Prisionero Iterado (más complejo) Resultados “anormales” en las competiciones 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

46 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 46 46

47 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - TOAST Trust Organisational Agent System Testbed (TOAST) Objetivo Proporcionar un soporte experimental para la evaluación de modelos de confianza en organizaciones virtuales  SMAs + algunas restricciones (roles, interacciones, objetivos, normas, …) Características Experimental setup: Definición de la OV: Taxonomías de Roles, Interacciones Número y tipos de objetivos/agentes Experiment generation Generación estocástica de las características de los agentes (capacidad, diversidad) Experiment execution Evaluación cuantitativa de los modelos de confianza 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

48 Confianza y Reputación en Sistemas Multi-Agente3. Testbeds - TOAST Ejemplo de taxonomía de Roles Definición de objetivos … 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

49 Testbeds – TOAST Generación de experimentosGeneración estocástica Asignación Agentes/Objetivos Qué es lo que un agente tiene que hacer Asignación Agentes/Roles Qué funcionalidades ofrecen los agentes Valores de capacidad Agentes/Rol/Interacción Cómo de “bueno” es un agente jugando un rol determinado en una interacción específica Se modela mediante distribuciones de probabilidad normales Media: habilidad del agente para realizar la acción Desviación típica: variaciones sufridas por diferentes situaciones 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

50 Testbeds – TOAST Dinámica de ejecuciónLos objetivos son entregado en las colas de los agentes Los agentes toman los objetivos y les asocian interacciones Los agentes se basan en sus modelos de confianza para elegir un agente de entre los posibles candidatos TOAST determina la utilidad de las interacciones Los agentes actualizan sus modelos 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

51 Confianza y Reputación en Sistemas Multi-AgenteTestbeds – TOAST Dinámica de ejecución Generador de Objetivos Organización Valores capacidad ?? F F {C,E,F,Z} 0.25 Agente A ?? Y Agente C {A,Y} 0.72 Y ?? X Las interacciones de cada uno son diferentes Agente B X 0.64 {A,D,Y,X} 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente 51

52 Contenidos Introducción Modelos de Confianza Testbeds DiscusiónAproximación al problema Definiciones Modelos de Confianza Comerciales Investigación Testbeds ART Testbed TOAST Discusión 12/04/2017 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente Confianza y Reputación en Sistemas Multi-Agente 52 52

53 Confianza y Reputación en Sistemas Multi-Agente4. Posibles trabajos Discusión del próximo día: J.Sabater y C.Sierra. “REGRET: a reputation model for gregarious societies”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs , 2002. 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

54 Confianza y Reputación en Sistemas Multi-Agente4. Posibles trabajos Teóricos Estado del Arte: A Survey of Trust in Computer Science and the Semantic Web. Donovan Artz and Yolanda Gil. A Survey of Trust and Reputation Systems for Online Service Provision. Audun Jøsang, Roslan Ismail, Colin Boyd Trust in Multiagent Systems. S. Ramchurn, T.D. Huynh, N. Jennings. The Knowledge Engineering Review (v.19, págs: 1-25) Modelos probabilísticos: TRAVOS-R  Jigar Patel TRAVOS-C  W.T. Luke Teacy Otros Modelos cognitivos  Castelfranchi, Falcone 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

55 Confianza y Reputación en Sistemas Multi-Agente4. Posibles trabajos Teórico-prácticos Desarrollo teórico y experimental de algún agente en ART Testbed Competición? 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

56 Confianza y Reputación en Sistemas Multi-AgenteBibliografía D. Gambetta. “Trust”. Basil Blackwell, Oxford, 1990 D.J. Wu y Y. Sun. “The emergence of trust in multi-agent bidding: A computational approach”. Proceedings of the 34th Hawaii International Conference on System Sciences, IEEE Computer Society Press, 2001 A. Birk. “Learning to trust”. Trust in Cyber-Societies, págs Springer-Verlag, 2001 C. Castelfranchi y R. Falcone. “Principles of trust for MAS: cognitive anatomy, social importance, and quantification”. Proceedings of International Conference of Multi-Agent Systems (ICMAS’98), págs , 1998 R.Jurca y B.Faltings. “An incentive compatible reputation mechanism”. Proceedings of the IEEE Conference on E-Commerce, págs , 2003 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente

57 Confianza y Reputación en Sistemas Multi-AgenteBibliografía J.Sabater y C.Sierra. “REGRET: a reputation model for gregarious societies”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs , 2002 M.Schilo, P.Funk y M.Rovatsos. “Using trust for detecting deceptive agents in artificial societies”. Applied Artificial Intelligence journal, págs , 2000 S.Sen y P.S.Dutta. “The evolution and stability of cooperative trails”. Proceedins of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs , 2002 B.Yu y M. Singh. “Detecting deception in reputation management”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), 2002 B.Yu y M. Singh. “An evidential model of distributed reputation management”. Proceedings of 2nd International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’03), 2003 12/04/2017 Confianza y Reputación en Sistemas Multi-Agente