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)
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 ?
Agente A precisa de um serviço
oferecido por um agente C mas
nunca interagiu com ele
A
C
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)

Exemplos: eBay,
Amazon Auctions e Sporas
A
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.
© LES/PUC-Rio
Avaliação de B = **
Avaliação de A = ***
B
Qual a reputação de A ?
C
***
Sistema de Reputação
– a reputação de um agente é sempre
conhecida pelo sistema de reputação
– reúne todas as avaliações de um mesmo
agente
Modelo de Reputação Descentralizado I/III

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

Modelo descentralizado
simples
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
© LES/PUC-Rio
Qual a reputação de A ?
Modelo de Reputação Descentralizado II/III

Vantagem:
Modelo de reputação
baseado em testemunhos
– agentes podem saber a reputação de
outros agentes sem ter interagido
anteriormente com eles

X
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.
X
© LES/PUC-Rio
X
X
X
X
X
X
X
Reputação do
Agente A do ponto
de vista do agente B
Modelo de Reputação Descentralizado III/III

Vantagem:
Modelo de reputação
baseado em reputação certificada
– 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
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
Organizações

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
1
Org1.1
5
6
2
3
4
8
7
9
© LES/PUC-Rio
Org1
Org1.2
Org1.2.1
Organizações

Exemplo:
Normas da Org1
01. Consolidador deve entregar a carga para o
importador no local determinado e no prazo
estabelecido
02. O consolidador não pode alterar a data do embarque
divulgada na programação de navios
03. O exportador tem que entregar a mercadoria ao
consolidador contratado pelo importador dentro do
prazo estabelecido
Normas da Org1.1
04. O exportador tem que entregar a mercadoria ao
importador dentro do prazo estabelecido
© 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
julgamento;
ii. fazer o atendimento ao subsistema de julgamento e aos agentes
sistema, respondendo as requisições sobre as reputações dos agentes;
iii. calcular e armazenar as reputações dos agentes de acordo com
veredictos dos testemunhos. Os veredictos são classificados
armazenados como violação de norma ou falso testemunho;
iv. manter as reputações atualizadas.
© LES/PUC-Rio
de
do
os
e
Framework para Cálculo de Reputações
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
Normas
normPower
01. Consolidador deve entregar a carga para o
importador no local determinado e no prazo
estabelecido
02. O consolidador não pode alterar a data do
embarque divulgada na programação de navios
© LES/PUC-Rio
totalTime
confession
1,0
60
1,0
0,5
10
0,5
Framework para Cálculo de Reputações
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))
© 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
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
© 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
Em andamento

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
© LES/PUC-Rio
Em andamento

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
© 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
Experimentos

A opção de fazer experimentos comparativos do nosso sistema de reputação com o Regret devese 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:
© 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.

© LES/PUC-Rio