Modelos e Sistemas de Reputação

Viviane Torres da Silvaviviane.silva@ic.uff.br

http://www.ic.uff.br/~viviane.silva/isma

Modelos e Sistemas de Reputação

O que são?

Modelos centralizados x descentralizados x híbridos

Regret FIRE Report

Motivação

Sistemas multi-agentes aberto– São sociedades de agentes heterogêneos e desenvolvidos por diferentes

desenvolvedores que pode interagir para alcançar objetivos comuns ou diferentes

Agentes necessitam saber quais são os agentes nos quais podem confiar

– Agente A deseja um serviço que C sabe executar– A nunca interagiu com C– A não sabe se C é confiável ou não

Como saber se um agente é confiável ou não?

ISMA

Sistemas de Reputação

Agentes avaliam o comportamento de outros agentes– Mal comportamento → má reputação– Bom comportamento → boa reputação

Sistemas de reputação clássicos– eBay e Amazon– Recebem informação sobre a satisfação com as interações, i.e., recebem

as reputações dos agentes• São pessoas que enviam estas informações

Sistemas de Reputação

Objetivo: avaliar o comportamento dos agente e proporcionar as reputações dos agentes

Modelo de Reputação Centralizado

Modelo de Reputação Descentralizado

Modelo de Reputação Centralizado

A

B

Rep

utat

ion

Syst

em

B’s reputation = **

A’s reputation = ***

CA’s reputation ?

***

Exemplo: eBay e Amazon

Modelo de Reputação Centralizado

Vantagens: A reputação é sempre conhecida A reputação está sempre atualizada pois é calcula através da

informação que recebem de outros agentes

Desvantagens: Os agentes não são capazes de armazenar as reputações dos

agentes com os quais interagiram Não existe nenhum mecanismo para verificar se a informação

fornecida é verdadeira ou falsa Oferecem uma única reputação global, não consideram

contextos diferentes

Modelo de Reputação Simples e Descentralizado

A B

B’s reputation A’s reputation = 0,7

CA’s reputation ?

Vantagens: Os agentes, que podem estar executando em um sistema multi-

agentes de larga escapa e distribuído, não necessitam se comunicar com um mecanismo centralizado

Cada agente é capaz de armazenar a reputação dos outros agente desde seu ponto de vista

Desvantagens: É necessário interagir com o agente primeiro para depois

conhecer sua reputação A reputação que um agente conhece de outro agente pode não

estar atualizada se faz tempo que os agentes não interagem

Modelo de Reputação Simples e Descentralizado

Modelo de Reputação Baseado em Testemunhos

A B

B’s reputation A’s reputation = 0,7

C

A’s re

puta

tion

?0,7

X

X

XX

X

XX

X

X

Vantagens: Possibilidade de conhecer a reputação de um agente antes de

interagir com eleDesvantagens: Em sistemas com muitos agentes pode custar muito encontrar

agentes que já interagiram com o agente desejado As reputação dos agentes são baseadas no ponto de vista do

agente que está fazendo a avaliação Pode ser difícil interagir muito com um agente para poder

fornecer uma reputação consistente Se um agente não conhece o agente que está enviando a

reputação, como confiar na reputação recebida?

Modelo de Reputação Baseado em Testemunhos

Modelo de Reputação Baseado em Reputações Certificadas

A B

CA’s reputation ?

0,9

A’s reputation inD’s point of view

D

D’s reputation inA’s point of view

0,9

A’s reputation inB’s point of view

B’s reputation inA’s point of view

0,7

Vantagens: Não é necessário buscar agentes que já tenham interagido com

o agente desejado

Desvantagens: A reputação do agente pode estar superestimada As reputações certificadas são influenciadas pelo ponto de

vista do agente que as calculou

Modelo de Reputação Baseado em Reputações Certificadas

Modelo de Reputação Híbrido

A

B

Sist

ema

Cen

tral

izad

oB’s reputation = *

A’s reputation = ***

CA’s reputation ?

**

B’s reputation

A’s reputation

***

Modelo de Reputação Híbrido Os agentes não são capazes de armazenar as reputações dos agentes com os

quais interagiram Não existe nenhum mecanismo para verificar se a informação fornecida é

verdadeira ou falsa Oferecem uma única reputação global, não consideram contextos diferentes É necessário interagir com o agente primeiro para depois conhecer sua

reputação A reputação que um agente conhece de outro agente pode não estar

atualizada se os agentes interagiram a muito tempo Em sistemas com muitos agentes pode custar muito encontrar agentes que

já interagiram com o agente desejado As reputações dos agentes são baseadas no ponto de vista do avaliador Pode ser difícil interagir muito com um agente para poder fornecer uma

reputação relevante Se um agente não conhece o agente que está enviando a reputação, como

confiar na reputação recebida? A reputação de agente pode estar superestimada As reputações certificadas são influenciadas pelo ponto de vista do agente

que as calculou

Cen

tral

izad

oSi

mpl

esT

este

mun

hos

Cer

tific

ada

Des

vant

agen

s de

out

ros m

odel

os

Sistema de Reputação Regret [1]

Dimensão Individual– Modelagem das interações diretas dos agentes– Confiança direta: avalia cada elemento do contrato– Ex: qualidade do produto, preço, data de entrega, …

Dimensão Social– Utiliza testemunhos enviados por outros agentes– Reputação baseada em testemunhos: reputação construída com

informações enviadas por outros agentes– Reputação baseada no sistema: reputação atribuída com base em

comportamento de outros agentes desempenhando os mesmos papéis

Sistema de Reputação Regret [1]

Dimensão Ontológica– Combina diferentes reputações

Modelo descentralizado simples:– Dimensão individual

Modelo descentralizado baseado em testemunhos:– Reputação baseada em testemunhos

Sistema de Reputação FIRE [2]

Reputação de interação (ou direta):– Modela as interações diretas

Reputação por papel:– Atribui uma reputação ao agente se baseando em reputações de

interações que obteve quando interagiu com outros agentes desempenhando o mesmo papel

Reputação por testemunha:– Reputação construída se baseando na informação enviada por outros

agentes Reputação certificada:

– Informação enviada por outros agentes sobre seu comportamento em interações passadas

Sistema de Reputação FIRE [2]

Modelo descentralizada simples:– Reputação por interação– Reputação por papel

Modelo descentralizado baseado em testemunhos:– Reputação por testemunho

Modelo descentralizado baseado em reputação certificada:– Reputação certificada

Sistema Híbrido para Governar os Agentes [4]

O sistema governa o comportamento dos agentes através de um conjunto de normas (ou leis)

O sistema estabelece um conjunto de normas Os agentes executam de acordo com as normas ou violando as

normas Quando um agente viola una norma, outro agente envia para o

sistema seu testemunho sobre a violação

Os agentes podem mentir!!

Sistema Híbrido para Governar os Agentes [4]

Judgment System Reputation SystemREGRET

Punishment SystemApplication

B: A violated norm N1

A B

B’s and A’s reputations?

B = 0,6 A = 0,8

A is 90% guilt of violating N1

A is 90% guilt of violating N1

A’s reputation?0,5

A’s punishment C

Sistema de Reputação Report [3]

Recebe um veredicto do sistema de julgamento com a probabilidade do agente ter violado a norma

– Veredicto: agente + probabilidade + norma

Calcula a reputação do agente– A reputação de um agente pode variar entre [0,1]

Armazena a reputação dos agentes– Armazena por contexto: reputação por cada norma violada, reputação

por cada papel desempenhado quando violou a norma, e reputação global

Sistema de Reputação Report [3]

Tipos de reputação Reputação por papel:

– Reputação de um agente quando desempenha um papel– Ex: a reputação do agente como vendedor é 0,8

Reputação por norma:– Reputação do agente em relação a una norma– Ex: a reputação do agente em relação a norma “entregar na data” é 0,6

Reputação global:– Reputação do agente independentemente do papel ou da norma– Ex: a reputação do agente (como vendedor e comprador) é 0,7

Sistema de Reputação Report: Calculando a reputação [3]

Grau de certeza da violação:– A probabilidade do agente ser culpado da violação (ex.: 80%)

O poder da norma: – Normas diferentes influenciam a reputação do agente de maneira diferente– Quanto mais importante é a norma mais influenciará na reputação do agente

que violou a norma (ex.: Matar a alguém é pior que roubar a alguém)

Dias de punição restantes:– Por quanto tempo a violação irá influenciar a reputação do agente?– Normas violadas recentemente influenciam mais a reputação do agente que

normas violadas a muito tempo. (ex.: Por matar: 8 anos na prisão; por roubar: 3 anos)

Reincidência: – A influência de una norma na reputação de um agente pode crescer com a

reincidência (ex.: Se é a segunda vez que a mesma pessoa rouba, 5 anos na prisão)

Trocando informação sobre reputação: principais características da abordagem I/V [5]

1) Todos os sistemas utilizam valores quantitativos para indicar a reputação de um agente– Mas o quê aconteceu? Por que o agente tem esta reputação?– O mesmo comportamento pode ser avaliado de maneiras diferentes.

Proposta: associar valores de reputação com…– Normas violadas ou cumpridas– Fatos que violaram ou cumpriram com as normas

2) A fonte de reputação é conhecida– O valor da reputação está associado com a identificação do agente que

está provendo a informação

Valor de reputação + Norma + Fatos [5]

Informação da reputação: RI ≡ (Pq, (I)LSr, Rep)– Provedor: agente que provê a reputação do outro agente:

Pq Є A – Situação (i)legal: (I)LSr Є (I)LS – Valor de reputação: Rep=[-1,+1]

Situação (i)legal: (I)LS ≡ (Sl, Nm, Fn)– Situação ilegal: situação onde a norma foi violada + o(s) fato(s) que

violaram a norma– Situação legal: situação onde a norma foi violada + o(s) fato(s) que

cumpriram com a norma

Situação: S ≡ (Ai, Rj , Ik, t)– Agente desempenhando um papel em uma interação no instante t

Principais características II / V [5]

3) Agentes podem definir normas especializando normas organizacionais

– Normas individuais

Enquando avaliam o comportamento de outros agentes, os dois tipos de normas podem ser consideradas

Exemplo: Norma organizacional x Individual [5]

Alice desempenha o papel de cliente e Bob de vendedor de passagens aéreas

Alice fez uma reserva de uma passagem mas Bob cancelou a reserva logo após a data limite de pagamento

ON1 : Proibição vendedores cancelar uma reserva se a data limite de pagamento ainda não chegouINAlice1 : Proibição vendedor cancelar uma reserva no dia seguinte ao data limite de pagamento

Bob não violou ON1 mas violou INAlice1

RepAlice→Bob = [0,+1)

Principais características III/ V [5]

4) Tipos de Reputação diferentes Reputação como servidor de um serviço:

– Quão bom foi o serviço provido por outro agente?– O grau de satisfação que o agente obteve após fazer uma interação– Tanto normas organizacionais quanto individuais são consideradas

Reputação como fornecedor de reputações:– Quão boa foi a informação que o agente recebeu sobre a reputação de

outro agente?– O grau de satisfação que um agente obteve do resultado de perguntar

sobre a opinião de outros agentes– Só existe uma norma para regular tal comportamento:

• “Agentes não podem mentir sobre a reputação de outros agentes”

Principais características IV/ V [5]

5) Mecanismo centralizado deixa disponível reputações contextualizadas e vários rankings

Reputações:– Reputação de Ai como provedor de serviço (do ponto de vista de Pq)

– Reputação de Ai desempenhando Rj (do ponto de vista de Pq)

– Reputação de Ai provendo serviço Ik (do ponto de vista de Pq)

– Reputação de Ai considerando Nm (do ponto de vista de Pq)

– Reputação de Ai como fonte de reputações– …

Rankings: – Melhor agente provedor de um determinado serviço– Melhor agente sendo provedor de serviços– ...

Principais características V / V [5]

6) Todo agente é motivado a aumentar seu prestígio social

Prestígio social: imagem que um agente pode oferecer para outros agentes do sistema sobre si mesmo

O agente contribui para o sistema:– Advertindo outros sobre aqueles em quem podem confiar sendo

provedores de serviço ou sendo provedores de reputação

Referências

1. Fire: T. Huynh, N. Jennings, and N. Shadbolt. Fire: An integrated trust and reputation model for open multi-agent systems. In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI), pages 18–22, 2004.

2. Regret: J. Sabater and C. Sierra. Reputation and social network analysis in multi-agent systems. In Proceedings of First International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 475–482, 2002.

3. Report: Guedes, J.; Silva, V.; Lucena, C. “A Reputation Model Based on Testimonies” In: Kolp, M.; Garcia, A.; Ghoze, C.; Bresciani, P.; Henderson-Sellers, B.; Mouratidis, A. (Eds.), Agent Oriented Information Systems IV: Proc. of the 8th International Bi-Conference Workshop (AOIS@AAMAS 2006 post-proceedings), LNCS 4898, Springer-Verlag, pp. 37-52, 2008.

4. V. Silva, F. Duran, J. Guedes, and C. Lucena. Governing multi-agent systems. Journal of Brazilian Computer Science, 2(13):19–34, 2007.

5. Silva, V; Hermoso, R.; Centeno, R. “A Hybrid Reputation Model Based on the Use of Organization”, COIN@AAMAS 2007 post-proceedings, LNAI 5428, Springer-Verlag, pp. 111-125, 2009.