Transcript The Beta Reputation System

The Beta Reputation System
Audun Jøsang and Roslan Ismail
[1]
Presented by
Hamid Al-Hamadi
CS 5984, Trust and Security, Spring 2014
Outline
•Introduction
•Building Blocks in the Beta Reputation System
•Performance of the Beta Reputation System
•Conclusion
2
Introduction
• Many existing reputation systems
• Applicability in e-commerce systems:
•Enforcement is needed in order for contracts and
agreements to be respected
•Traditionally rely on legal procedures to rectify
disagreement.
•Hard to enforce in e-commerce
• unclear which jurisdiction applies
• cost of legal procedures
3
Introduction
•Reputation systems
• As a substitute to traditional Reputation systems can be
used to encourage good behavior and adherence to contracts
• Fostering trust amongst strangers in e-commerce
transactions
• Gathers, distributes, and aggregates feedback about
participants behavior
• Incentive for honest behavior and help people make
decisions about who to trust.
•Without a reputation system taking account past
experiences, strangers might prefer to act deceptively for
immediate gain instead of behaving honestly.
4
Introduction
• Online auction sites were the first to introduce
reputation schemes e.g. eBay.com
• Others include company reputation rating sites such
as BizRate.com, which ranks merchants on the basis of
customer ratings
• The internet is efficient in capturing and distributing
feedback, unlike the physical world.
• Some challenges:
• An entity can attempt to change its identity to erase prior
Feedback
• Restart after it builds a bad reputation
• Not enough feedback provided by surrounding entities
• Negative feedback hard to elicit
• Difficult to ensure feedback is honest
5
Introduction
• Example of dishonesty through reputation systems:
•Three men attempt to sell a fake painting on eBay
for $US135,805
•Two of the fraudsters actually had good Feedback
Forum ratings as they rated each other favorably
and engaged in honest sales prior to fraudulent
attempt.
•Sale was abandoned just prior to purchase, buyer
became suspicious
6
Introduction
• Fundamental aspects:
•Reputation engine
• Calculates users’ reputation ratings are from various inputs
including feedback from other users
• Simple or complex mathematical operations
•Propagation mechanism
• Allows entities to obtain reputation values
•Two approaches:
•Centralized (e.g. eBay)
•Reputation values are stored in a central server
•Users forward their query to the central server for the
reputation value whenever there is a need
•Decentralized
•Everybody keeps and manages reputation of other
people themselves
•Users can ask others for the required reputation values
7
Introduction
• Authors propose a new reputation engine based on the
beta probability density function called the beta reputation
system
• strongly based on theory of statistics
• paper describes centralized approach, but the reputation system
can also be used in a distributed setting
8
Building Blocks in the Beta
Reputation System
• The Beta Density Function
•Can be used to represent probability distributions of binary events
•The beta-family of probability density functions is a continuous
family of functions indexed by the two parameters α and β .
9
Building Blocks in the Beta
Reputation System
• “When observing binary processes with two possible
outcomes
, the beta function takes the integer
number of past observations of and to estimate the
probability of , or in other words, to predict the expected
relative frequency with which will happen in the future.”
10
Building Blocks in the Beta
Reputation System
11
Building Blocks in the Beta
Reputation System
•Example:
•process with two possible outcomes
•Produced outcome 7 times
•Produced outcome 1 time
•Will have beta function as
plotted below:
12
Building Blocks in the Beta
Reputation System
•Example (cont’):
• represents the probability of an event
•
represents the
probability that the first-order
variable has a specific value
•Curve represents the
uncertain probability that the
process will produce outcome
during future observations
•probability expectation value
-> the most likely value of the
relative frequency of outcome
is 0.8
8 / (8 + 2)
13
Building Blocks in the Beta
Reputation System
• The Reputation Function
In e-commerce an agent’s perceived satisfaction after a
transaction is not binary - not the same as statistical
observations of a binary event.
• Let positive and negative feedbacks be given as a pair
of continuous values.
Degree of satisfaction
Degree of dissatisfaction
14
Building Blocks in the Beta
Reputation System
•
Compact notation :
•
15
Building Blocks in the Beta
Reputation System
• T’s reputation function by X is subjective (as seen by X)
Superscript (X): feedback provider
Subscript (T): feedback target
16
Building Blocks in the Beta
Reputation System
• The Reputation Rating
• Simpler representation to communicate to humans that a reputation function
•Given as a probability value – within a range
•Neutral value is in middle of range
• Scale the rating to be in the range [-1,+1]
• A measure of reputation and how an entity is expected to behave in the future
17
Building Blocks in the Beta
Reputation System
• Combining Feedback
• Can combine positive and negative feedback from multiple sources e.g.
combine feedback from X and Y about target T
Combine positive feedback
Combine negative feedback
Operation is both commutative and associative
18
Building Blocks in the Beta
Reputation System
• Discounting
• Used to vary the weight of the feedback based on the agents reputation
• Described in the context of belief theory
•Jøsang’s belief model uses a metric called opinion to describe beliefs about the
truth of statements
•
•
•
interpreted as probability that proposition x is true
interpreted as probability that proposition x is false
interpreted as inability to assess the probability value of x
19
Building Blocks in the Beta
Reputation System
• Y has opinion about T, gives it to X
• X has opinion about Y
Then X can express its opinion about T taking into account its opinion about Y’s advice
, as follows:
Given by Y (its opinion about T)
Apply X’s opinion
about Y
20
Building Blocks in the Beta
Reputation System
• The opinion metric can be interpreted equivalently to the beta function
• mapping between the two representations defined by:
• Using previous eq., discounting operator for reputation functions is obtained:
Associative but not
commutative
21
Building Blocks in the Beta
Reputation System
• Forgetting
• Old feedback less relevant for actual reputation rating
• Behavior changes over time
• Old feedback is given less weight than new feedback
• Can use an adjustable forgetting factor
Order of feedback
processing matters
• If λ=1 -> no forgetting factor, nothing is forgotten
• If λ=0 -> only last feedback, all others forgotten
22
Building Blocks in the Beta
Reputation System
• Forgetting (cont’)
• To avoid saving all of the feedback tuples (Q) forever, a recursive
algorithm can be used instead:
23
Building Blocks in the Beta
Reputation System
• Providing and collecting feedback:
• After each transaction, a single agent can provide both positive
and negative feedback simultaneously:
• Feedback can be partly satisfactory, and given as a pair
• The sum
can be interpreted as the weight of the feedback
• Minimum weight of feedback is r + s = 0, equivalent to not providing
feedback
• Alternatively, define a normalization weight denoted by so that the
sum of the
parameters satisfy
• Feedback can be provided as a single value with values within a specified
range
• If we have such that
then the
can be derived
using
and as follows:
• Weight can reflect importance of transactions (high importance -> high
)
24
Building Blocks in the Beta
Reputation System
• Feedback is received and stored by a feedback collection centre C
• Assumed that all agents are authenticated and that no agent can change identity
• Agents provide feedback about transaction
• C discounts received feedback based on providers reputation and updates the
target’s reputation function and rating accordingly
• C provides updated reputation ratings to requesting entities
25
Performance
• Example A: Varying Weight
• This example shows how the reputation rating evolves as a function
of accumulated positive feedback with varying weight w
• Let C receive a sequence Q of n identical feedback values v=1 about target T
• Then:
Reputation parameters:
Reputation rating:
Derived from previous equations:
26
Performance
w=1
w=0
27
Performance
• Example B: Varying Feedback
• This example shows how the reputation rating evolves as a function of
accumulated feedback with fixed weight w = 1 and varying feedback value v
V=1
•For v=1 the rating approaches 1,
and for v=-1 the rating
approaches -1.
V=-1
28
Performance
• Example C: Varying Discounting
• This example shows how the reputation rating evolves as a function of
accumulated feedback with fixed weight w = 1 and varying discounting
• C receives a sequence Q of n identical feedback values v =1 about target T
• Forgetting is not considered
• Each feedback tuple
with fixed value (1, 0) is discounted based on
the feedback provider’s reputation function defined by
Reputation parameters:
Reputation rating:
29
Performance
• Example C: Varying Discounting (cont’)
practically equivalent
to no discounting at all
Varying Feedback provider’s
reputation function parameters
• As X’s reputation function gets
weaker T’s rating is less influenced
by the feedback From X
• with r=0, s=0 , T’s rating not
influenced by X’s rating
30
Performance
• Example D: Varying Forgetting Factor
• This example shows how the reputation rating evolves as a function of
accumulated feedback with fixed weight w = 1 and varying forgetting factor λ
• C receives a sequence Q of n identical feedback values v =1 about target T
• Discounting is not considered
Using previous equations, the reputation parameters and rating can be
expressed as a function of n and λ according to:
31
Performance
• Example D: Varying Forgetting Factor (cont’)
32
Performance
• Example E: Varying Feedback and Forgetting Factor
• This example shows how the reputation rating evolves as a function of
accumulated feedback with fixed weight w = 1.
• Let there be a sequence Q of 50 feedback inputs about T, where the first 25
have value
, and the subsequent 25 inputs have value
•Using previous equations, the reputation parameters and rating can be
expressed as a function of n, v, and λ according to:
In more
explicit
form:
33
Performance
• Example E: Varying Feedback and Forgetting Factor (cont’)
In more explicit form:
34
Performance
• Example E: Varying Feedback and Forgetting Factor (cont’)
v=1
• Two phenomena can be
observed when the forgetting
factor is low (i.e. when feedback
is quickly forgotten):
•Firstly the reputation rating
reaches a stable value more
quickly, and
•secondly the less extreme the
stable reputation rating becomes.
v=-1
35
Conclusion
• Reputation systems can be used to encourage good
behavior and adherence to contracts in e-commerce
• Authors propose a beta reputation system which is based
on using beta probability density functions to combine
feedback and derive reputation ratings
•Strong foundation on the theory of statistics
•Assumed a centralized approach, although it is possible to
adapt the beta reputation system in order to become
decentralized
•flexibility and simplicity makes it suitable for supporting
electronic contracts and for building trust between players in
e-commerce
36
References
[1] A. Josang, and R. Ismail, "The Beta Reputation System,” 15th Bled
Electronic Commerce Conference, Bled, Slovenia, June 2002, pp. 1-14.
37