Um Framework para Cálculo de Reputações de Agentes de Software Baseado em Testemunhos

José Guedes (PUC-Rio)

Viviane Torres da Silva (UCM)

Carlos Lucena (PUC-Rio)

© LES/PUC-Rio

Agenda

Motivação Definição do problema Sistemas de Reputação Modelos Centralizados e Descentralizados Modelo Proposto Framework para Cálculo de Reputações Em andamento Referências

© LES/PUC-Rio

Motivação

Sistemas multi-agentes abertos

sociedades onde entidades heterogêneas e projetadas de forma independente podem trabalhar com fins semelhantes ou diferentes.

Agentes precisam saber se outros agentes são confiáveis

Como saber se um agente é confiável antes de interagir com ele ?

© LES/PUC-Rio

Definição do problema

Como saber se um agente é confiável sem ter interagido com ele ?

A C

Agente A precisa de um serviço oferecido por um agente C mas

nunca interagiu com ele

Agente A não sabe se o agente C é confiável

© LES/PUC-Rio

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, Amazon Auction

– Recebe informações sobre as negociações entre agentes• Nestes casos, agentes são pessoas

– Avalia a reputação dos agentes

– Fornece a reputação de um agente para outro

© LES/PUC-Rio

Modelo de Reputação Centralizado

Vantagens:(considerando sistemas multi-agentes de larga-escala)

– a reputação de um agente é sempre conhecida pelo sistema de reputação

– reúne todas as avaliações de um mesmo agente

Desvantagens:– considera todas as avaliações honestas,

mas agentes podem mentir

– toda informação está centralizada em um único sistema de reputação centralizado

– valor de reputação global. Não considera contextos diferentes.

A

B

Sis

tem

a d

e R

epu

taçã

oAvaliação de B = **

Avaliação de A = ***

CQual a reputação de A ?

***

Exemplos: eBay, Amazon Auctions e Sporas

© LES/PUC-Rio

Vantagens:– o próprio agente é responsável pelo

cálculo e armazenamento das reputações

– cada proprietário programa seu agente de software com estratégias particulares

Desvantagens:– somente é possível saber se um

agente é confiável se já interagiu com ele anteriormente ?

– só considera ações de interação ao medir a confiança

Qual a reputação de A ?

Modelo de Reputação Descentralizado I/III

Modelo descentralizado simples

© LES/PUC-Rio

Modelo de reputação baseado em testemunhos

Vantagem:– agentes podem saber a reputação de

outros agentes sem ter interagido anteriormente com eles

Desvantagens:– o agente não sabe quem já interagiu

anteriormente com um determinado agente

– as reputações fornecidas por um agente são baseadas no ponto de vista deste agente

– pode ser difícil estabelecer uma quantidade de recomendações suficientes para saber se o agente é uma boa testemunha.

– não estarão dispostos a colaborar com seus concorrentes e por isso não irão repassar informações.

0,7

Modelo de Reputação Descentralizado II/III

X

X

X

X

X

X

X

X

X

Reputação do Agente A do ponto de vista do agente B

© LES/PUC-Rio

Modelo de reputação baseado em reputação certificada

Vantagem:– a reputação de um agente

pode ser facilmente conhecida

Desvantagens:– a reputação de um agente

será provavelmente superestimada

– as reputações certificadas estão influenciadas pelo ponto de vista dos agentes que forneceram as reputações

Modelo de Reputação Descentralizado III/III

Reputações do Agente A do ponto de vista dos agentes B e D

© LES/PUC-Rio

Proposta

Modelo de reputação híbrido – combina as características de abordagens centralizadas e descentralizadas

Subsistema de Reputação– implementado através do framework para cálculo de reputações de agentes de

software baseado em testemunhos

© LES/PUC-Rio

Sistemas multi-agentes de larga escala são compostos por grupos ou organizações de agentes

– cada organização define seu próprio conjunto de normas.

– as normas devem ser obedecidas também nas suborganizações

– normas das suborganizações não podem contradizer as normas da superorganização

– podem ser mais restritivas do que as normas de origem

Organizações

2

6 7

4

5

Org1

Org1.1 Org1.2

Org1.2.1

1 3

8

9

2

6 7

4

5

Org1

Org1.1 Org1.2

Org1.2.1

1 3

8

9

© LES/PUC-Rio

Organizações

02. O consolidador não pode alterar a data do embarque divulgada na programação de navios

01. Consolidador deve entregar a carga para o importador no local determinado e no prazo estabelecido

03. O exportador tem que entregar a mercadoria ao consolidador contratado pelo importador dentro do prazo estabelecido

04. O exportador tem que entregar a mercadoria ao importador dentro do prazo estabelecido

Normas da Org1

Normas da Org1.1

Exemplo:

© LES/PUC-Rio

Framework para Cálculo de Reputações

Propósito– Implementar organizações que avaliam a reputação de um agente

baseado nos testemunhos de violações de normas enviados pelos agentes de software.

Responsabilidades: i. receber os veredictos dos testemunhos, enviados pelo subsistema de

julgamento;

ii. fazer o atendimento ao subsistema de julgamento e aos agentes do sistema, respondendo as requisições sobre as reputações dos agentes;

iii. calcular e armazenar as reputações dos agentes de acordo com os veredictos dos testemunhos. Os veredictos são classificados e armazenados como violação de norma ou falso testemunho;

iv. manter as reputações atualizadas.

© LES/PUC-Rio

O que vai exercer influência na reputação ? Gravidade da violação – variáveis definidas ao instanciar o framework

– normPower: normas diferentes influenciam as reputações de modos diferentes– totalTime: por quanto tempo a violação influenciará na reputação

Atenuante e Agravante– confession: a confissão do agente diminui o a influência do poder da norma– relapses: a reincidência de uma mesma norma aumenta a influência do poder

da norma

Normas – Transporte e Consolidação de Cargas

Framework para Cálculo de Reputações

100,502. O consolidador não pode alterar a data do embarque divulgada na programação de navios

601,001. Consolidador deve entregar a carga para o importador no local determinado e no prazo estabelecido

totalTimenormPowerNormas confession

1,0

0,5

© LES/PUC-Rio

O que vai exercer influência na reputação ?

O percentual de culpa do agente– blamePercentage: percentual recebido do sistema de julgamento

A violação é “esquecida” – remainingDays: normas violadas recentemente influenciam mais a

reputação de um agente do que normas violadas a mais tempo

totalTime(ni) – passedDays(aj,ni)

remainingDays(aj,ni) = ------------------------------------------

totalTime (ni)

formulaInfluenceDef(aj) = (normPower * blamePercentage) *

confession * (1/relapse) * remainingDays

formulaReputation (aj) = 1 – (formulaInfluenceDef(aj))

Framework para Cálculo de Reputações

© LES/PUC-Rio

Exemplo: agente violou norma n2 em 01/05

Resultado: true (agente acusado foi considerado culpado) blamePercentage = 0,9 (grau de culpa do agente é de 90%) NormPower = 0,5 (poder da norma n1)

TotalTime = 10 dias Confession = 1 (não houve confissão) Relapse = 1 (primeira vez que o agente violou esta norma)

+

-

normPower* blamePercentage: 90% do poder da norma influenciando na reputação do agente

© LES/PUC-Rio

Framework para Cálculo de Reputações

Hot spot: fórmulas de cálculo da reputação

formulaReputation (aj) = 1 – x

∑0<i<=k [formulaInfluenceDef(aj)], se 0 <= ∑0<i<=k [formulaInfluenceDef(aj)] <= 1

1 , se ∑0<i<=k [formulaInfluenceDef(aj)] > 1

formulaInfluenceDef(aj) = (normPower * blamePercentage) * confession * (1/relapse) * remainingDays

x =

© LES/PUC-Rio

Conclusões

Problemas solucionados com nossa abordagem:i. Agentes não precisam interagir várias vezes com o mesmo agente

para obter reputações consistentes;

ii. Não existe a necessidade de procurar um agente para obter recomendações;

iii. Ao contrário das reputações certificadas, as reputações fornecidas pelas organizações não estão superestimadas;

iv. As reputações fornecidas pelas organizações não estão influenciadas por opiniões de outros agentes e sim por testemunhos de violações de normas. Cada norma descreve de que forma a violação vai influenciar na reputação dos agentes.

© LES/PUC-Rio

Comparação com Regret System– Simulação: interações entre agentes contratantes X consolidadores

– Contratante deve escolher o agente mais confiável

– objetivos• comparar a performance dos mecanismos de reputação, isto é, se os

mecanismos estão permitindo que os agentes façam a melhor escolha em uma negociação.

• demonstrar o melhor aproveitamento na nossa proposta na medida em que aumentam o número de agentes

Em andamento

© LES/PUC-Rio

ART-Testbed – Andrew Costa– Agent Reputation and Trust

• Competição e experimento

• Cada participante, representado por seu agente, precisa interagir com os outros agentes da competição para atingir seu objetivo

Nova versão do framework

Escrita da dissertação

Em andamento

© LES/PUC-Rio

References

1. Abdul-Rahman, A. and S. Hailes: 2000, Supporting Trust in Virtual Communities. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, Vol. 6.

2. Amazon Site. http://www.amazon.com World Wide Web (2006)

3. Castelfranchi, C. and R. Falcone: Social Trust: A Cognitive Approach. In: C. Castelfranchi and Y. Tan (eds.): Trust and Deception in Virtual Societies. Kluwer Academic Publishers (2001) pp. 55–90

4. eBay Site. http://www.ebay.com World Wide Web (2006)

5. Grandison, T., Sloman, M.: A Survey of Trust in Internet Applications. IEEE Communications Surveys & Tutorials 3(4) (2000)

6. Huynh, T. D., Jennings N. R., Shadbolt, N. R.: FIRE: An Integrated Trust and Reputation Model for Open Multi-Agent Systems. In: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI) (2004) pp. 18–22

7. Incoterms Site. Site http://incoterms.atspace.com/index.html, World Wide Web (2006)

8. Resnick, P., Zeckhauser, R., Friedman, E., Kuwabara, K.: Reputation Systems. In: Communications of ACM, vol. 43, number 12, p. 45-48, December 2000.

9. Sabater, J.:Trust and Reputation for Agent Societies. PhD thesis, Universitat Autonoma de Barcelona (UAB) (2003)

© LES/PUC-Rio

References

10. Sabater, J., Sierra, C.: Reputation and Social Network Analysis in Multi-Agent Systems. In: Proceedings of First International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Bologna, Italy (2002) pp. 475-482

11. Silva, V., Lucena, C.: Governance in Multi-Agent Systems Based on Witnesses. Pontifical Catholic University of Rio de Janeiro (PUC-Rio). Rio de Janeiro - Brazil (2005)

12. Skogsrud, H., Benatallah, B., Casati, F.: Model-Driven Trust Negotiation for Web Services. IEEE Internet Computing 7(6) (2003) pp. 45–52

13. Yu, B., Singh, M. P.: Distributed Reputation Management for Electronic Commerce. Computational Intelligence (2002) 18(4) pp. 535-549

14. Yu, B., Singh, M. P.: An Evidential Model of Distributed Reputation Management. In: Proceedings of First International Joint Conference on Autonomous Agents and Multi-Agent Systems (2002) Vol. 1. pp. 294–301

15. Zacharia, G. and P. Maes: 2000, Trust management through reputation mechanisms.Applied Artificial Intelligence 14(9), 881–908.

© LES/PUC-Rio

A opção de fazer experimentos comparativos do nosso sistema de reputação com o Regret deve-se ao fato de ser um dos sistemas de confiança e reputação mais citados por artigos da área.

O objetivo do experimento é verificar a performance dos mecanismos de reputação ao selecionar agentes confiáveis, evitando aqueles agentes consolidadores que oferecem algum risco ao transportar as mercadorias.

Foram executadas cinco simulações, todas com 100 sessões, porém cada uma com uma quantidade diferente de agentes consolidadores. A primeira simulação contou com 36 agentes consolidadores e a cada simulação o número foi duplicado até chegar em 576 agentes consolidadores na quinta e última simulação. O objetivo foi demonstrar a queda de aproveitamento dos agentes contratantes na medida em que aumenta a quantidade de agentes consolidadores. A queda de aproveitamento acontece por causa do aumento do número de agentes consolidadores. As interações diretas entre agentes contratantes e consolidadores ficam cada vez mais escassas, por isso os mecanismos de reputação tornam-se menos eficientes.

A simulação consiste em interações entre agentes contratantes (compradores ou vendedores) e agentes consolidadores, conforme a figura 3. Em cada sessão cada agente contratante tem a missão de escolher o agente mais confiável dentre 6 agentes consolidadores selecionados pelo simulador. São sempre 48 agentes contratantes, 12 de cada tipo de algoritmo de reputação, definidos abaixo:

Experimentos

© LES/PUC-Rio

Experimentos

Agentes Contratantes Random: São agentes que escolhem um agente consolidador de maneira aleatória. Direct Trust: São agentes dotados do mecanismo de cálculo da reputação subjetiva direct trust

do sistema Regret. Utilizam o histórico de interações diretas anteriores para saber se o agente consolidador é confiável ou não.

Direct Trust + Witness Reputation: São agentes dotados do mecanismo direct trust e witness reputation. Na segunda a reputação é obtida através dos testemunhos de outros agentes da sociedade e é utilizada quando o agente contratante nunca interagiu anteriormente com o agente consolidador. Embora na vida real os agentes possam mentir ou então enviar avaliações equivocadas geradas por programas defeituosos ou maliciosos, não estamos considerando estes problemas. Estamos considerando que todas os testemunhos enviados são corretos. O universo de testemunhas é limitado em 5 agentes, no máximo. A quantidade de testemunhas é calculada de forma randômica, de 0 até 5 agentes que já interagiram anteriormente com o agente alvo.

Direct Trust + Reputation Subsystem: São agentes dotados do nosso sistema de reputação, que utiliza os testemunhos de violações de normas para saber se o agente consolidador é confiável ou não. O testemunho e a confissão de uma violação acontecem de forma aleatória.

© LES/PUC-Rio

Experimentos

Os agentes consolidadores variaram de 36 até 576. Na primeira simulação são 36 consolidadores, em seguida 72, 144, 288 e 576. Existem três tipos diferentes de agentes consolidadores, divididos em quantidades iguais dentro de cada simulação, definidos da seguinte forma:

        Random: São agentes consolidadores que às vezes cometem violações.         Bom: São agentes bons, nunca cometem violações.         Ruim: Agentes que sempre cometem uma ou mais violações. Cada sessão da simulação tem 3 etapas: 1        O simulador seleciona 6 agentes consolidadores randomicamente para participarem da

sessão. Pelo menos um agente bom terá que ser selecionado. 2        Cada agente utiliza o seu algoritmo para fazer a escolha do agente mais confiável, dentre

os 6 consolidadores selecionados. O simulador armazena os resultados e cada agente alimenta seu sistema de reputação.

© LES/PUC-Rio

Experimentos

O gráfico 1 apresenta o percentual de aproveitamento dos agentes contratantes nas cinco simulações. Com exceção dos agentes contratantes do tipo Random, que teve baixo aproveitamento em todas as simulações, o aproveitamento dos demais agentes diminuiu na medida em que o número de agentes consolidadores aumentou.

É possível observar também que o melhor aproveitamento, em todas as simulações, foi obtido pelos agentes contratantes que utilizaram o mecanismo direct trust combinado com nosso mecanismo de reputação (DT+Reputation). Na primeira simulação, com 36 agentes consolidadores, o aproveitamento entre os mecanismos foi o mais próximo. A diferença aumentou nas simulações seguintes, quando o número de consolidadores dobrou para 72, 144 e 288, uma vez que as performances dos agentes do tipo Direct Trust e DT+Witness tiveram uma queda mais acentuada.

© LES/PUC-Rio

Experimentos

O gráfico 2 mostra a evolução do grau de satisfação ao longo das sessões da terceira simulação, por tipo de mecanismo de reputação utilizado pelos agentes contratantes. Nesta simulação existiam 144 agentes consolidadores. O eixo y representa a média dos graus de satisfação das últimas 10 sessões, por tipo de mecanismo.

Observamos que já após as dez primeiras sessões o nosso mecanismo de reputação já apresenta um desempenho razoável e atinge níveis próximos do ótimo mais rapidamente do que os demais mecanismos. Significa que os agentes contratantes passam a ter maior conhecimento sobre os agentes com quem precisa interagir e desta forma consegue selecionar agentes mais confiáveis diminuindo os riscos nas interações.