[MUD-Dev] Advogato

[J. Michael Ashley]

On Sat, 6 May 2000, Raph Koster wrote:
> > -----Original Message-----
> > From: [J C Lawrence]
> > Sent: Friday, May 05, 2000 11:38 PM
> > Subject: [MUD-Dev] Advogato
> >
> > The main point of my interest however was his trust metric model as
> > documented at:
> >
> >   http://www.advogato.org/trust-metric.html
> >
>
> Verrry interesting. I wonder how computationally scalable it is? Anyone
> savvier on the tech side than I able to give an assessment?

As a historical aside, the idea of a trust/judgement/certification
network has been around for a while.  The earliest example I know is
Pretty Good Privacy's (PGP) web of trust model for public key management.

Ford-Fulkerson is expensive for large graphs with thousands of nodes
and edges.  Consulting "Introduction to Algorithms" by Cormen, Leiserson,
and Rivest, there are a few different ways to implement Ford-Fulkerson.
If V is the number of nodes (vertices) in the graph and E is the number
of edges then there are algorithms that run in time proportional to V*E^2
(V times E squared), V^2*E and V^3.

I wouldn't let that discourage anyone, however.  A peer-based judgement
network is a powerful idea.  Reputation systems such as the UO reputation
system depend on tracking behavior that can be mechanically identified,
e.g., looting and murder.  A peer-based system, however, lets the players
judge themselves using their own standards and values.  The morals of
the *player community* are woven into the network.

Having said that, I'm pretty sure that designing a peer-based judgement
system that cannot be abused and can be implemented efficiently is a
nontrivial problem.  Here is what I would like to see in the system:

  1) a way for a player A to "judge" player B, say from -10 to 10, and
  2) a way for player B's judged reputation to be made known to other
     players.

Part 1) is easy to implement.  Part 2) is difficult.  If players take
judgements at face value, then you have the problem that player B (a
PK) gets his friends to judge him as a good guy.  Unknowing players see
those judgements and are caught by surprise when player B harasses them.
Sure, the harassers will judge him negatively, but the more friends he
has then the longer he can go causing trouble.  Conversely, a harasser
and his friends can cast negative judgements on an otherwise nice guy,
causing him trouble when he meets strangers.

The problem is that the judgements were taken at face value.  What is
needed is a system by which judgements are passed among players who
trust each other.  For example, suppose players A and C cast judgements
on player B.  Player D trusts player A but does not trust player C.  Then
player A's judgement is more meaningful to player D than player C's
judgement.

Here is a straw proposal for a system for assigning trust and propagating
judgements among players.

Start proposal
--------------

1. Each player maintains a judgement list of other players.
2. Each player maintains a trust list of other players.  The trust
is a weight.

Take each player as a node and use the trust lists as weighted edges to
other nodes.  To compute player's A opinion of B use the following
recursive algorithm:

1. If player B is in A's judgement list, that judgement is taken.
2. Otherwise, compute the weighted average of B's reputation among all
the other players that A trusts, i.e., all the players to which there
is an edge from A.

Details like cycles in the graph are noise right now.

End proposal
------------

This works, but it has two obvious problems:

1. There is no "decay" in judgements.  Each edge of the graph is like
passing reputation word of mouth from one person to the next.  As a
judgement passes over edges, it's value needs to decay.  This is easy
to build into the algorithm, but I left it out to make things simpler.

2. Maintaining the lists is a lot of work.  Each player has to maintain
his judgement list and his trust list.  It's important to maintain it,
though, since the player will want accurate reputations to be computed,
and he'll want others to be able to depend on him as a reliable source
of information about reputations.  As an aside, a player role-playing
a bartender would be *really* interested in keeping his trusts and
judgements accurate.

Any other problems I'm missing?

As for the computational cost of such a system, it it may be possible
to devise cheaper, incremental algorithms for updating the trust graphs.
It may also be possible to amortize the update cost over consultations of
the graph.  I have a lot more confidence in finding a good implementation
right now than I do in finding the right design.

Mike





_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev