An algorithm for distributed or decentralised reputation/trust

Question

Does anyone know of an algorithm for computing how much you 'trust' another user (their reputation) in a decentralised system.

Sites like this one use a centralised authority to track reputation points, but when you can't trust an authority to maintain this list impartially, or the infrastructure doesn't exist, how can you rank your peers' reputation?

I'm imagining something akin to PageRank - I trust my friend Alice, she trusts her friend Bob, therefore I have some transitive trust for Bob. If my other friend Carol also trusts Bob, then my trust for Bob increases.

Is there some way of computing this globally, or does each user have to track their own network?

I was thinking you could just 'declare' who you trust, which would give each person a corresponding set of incoming trust links, but I feel this would be easy to game by creating many zombie users who just create reputation points, like link farms in search results. And that may be the kernel of the problem: if Google still has problems with people generating bogus PageRank scores, it might not be a problem easily solved :)

Answer 1

Take a look at the EigenTrust algorithm:

The EigenTrust Algorithm for Reputation Management in P2P Networks - S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina

This algorithm assigns each peer in the network a global trust value.

Answer 2

The web site Advogato implements a distributed trust metric. The source code is available. Here is the FAQ, and a description of the trust metric.

Answer 3

it might not be a problem easily solved

You got that right. This is a very actively researched area, especially in a P2P environment. A quick google search for trust p2p network turns out quite a few papers on it.

This one in particular brings up a good list of things to consider, (and provides an algorithm of sorts).

Overcoming Reentry and Entry Barrier - How do you prevent bad people from making a new nickname and rejoining a network?

Creating incentives to rate - What is the incentive for a large P2P network to rate other users for trust?

It is often much simpler for a single authorized server to manage trust/reputation between users. You will have to come up with a good reason why you would want it to be decentralized.

Answer 4

I think possibly a system by which each user tracks and serves their own trust uplinks could work in a situation like this. For example; say user A trusts user B and rates them a 5 in trust (out of 10). Let's say I don't know whether or not to trust user A or user B; if user A does something that causes me to trust them, I can mark them as trusted, and they can tell me who THEY trust; then I would get User A's ranking of User B, and I can adjust the trust as I see fit; if I have high trust in User A, I might give user B a rating of 5 (based entirely upon user A's rating of them); if I trust user A just a little, I might give user B a rating of 1 (better than no trust, but not as trusted as User A finds them to be). In that way, users determine the first order of trust by trustworthy things (upvoting their posts, or the like) and then can have "associated" trust from those users they explicitly trust come through; there's a "second order" network effect going on. I'd specifically say that when a user gets trust information for other users from someone, they should only grant "implicit trust" to those users who were granted "explicit trust" by that user they're getting the trust information from.

Answer 5

Perhaps "An Algebra for Assessing Trust in Certification Chains."

However, trust is a hard human problem that can be at best approximated with an algorithm like the one mentioned in the paper.

Further recommended reading:

• Web of Trust (e.g. CAcert.org)
• Key Signing Party
• Reflections on Trusting Trust