May 2000
- Interesting online game Brian Green
- Bayesian statistics Ola Fosheim Grøstad
- Client Technology Jon Morrow
- Client Technology Todd McKimmey
- Client Technology Andrew Wilson
- Client Technology Ben Greear
- Client Technology Greg Munt
- Client Technology Ola Fosheim Grøstad
- Client Technology Joel Dillon
- Advogato J C Lawrence
- Advogato Raph Koster
- 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
- Advogato J. Michael Ashley
- Advogato Bruce
- Advogato J C Lawrence
- Advogato Travis Nixon
- tdbm etc. J C Lawrence
- text user interface Eli Stevens
- text user interface Chris Gray
- Legends of Kesmai, RIP Raph Koster
- Legends of Kesmai, RIP Clevmut@aol.com
- Medievia ads in PCGamer? Schubert, Damion
- Medievia ads in PCGamer? Rasdan
- FIrst LOgin REview (was attracting players) Ola Fosheim Grøstad
- FIrst LOgin REview (was attracting players) adam@treyarch.com
- FIrst LOgin REview (was attracting players) David Bennett
- FIrst LOgin REview (was attracting players) adam@treyarch.com
- FIrst LOgin REview (was attracting players) David Bennett
- FIrst LOgin REview (was attracting players) Chris Gray
- FIrst LOgin REview (was attracting players) Chris Gray
- Addressing newbies Johan J Ingles-le Nobel
- Addressing newbies stoddart@slip.net
- Addressing newbies adam@treyarch.com
- Addressing newbies J C Lawrence
- Addressing newbies Chris Gray
- Addressing newbies Powell, Warren
- Addressing newbies adam@treyarch.com
- Addressing newbies Chris Lloyd
- Addressing newbies adam@treyarch.com
- Addressing newbies Chris Lloyd
- Addressing newbies adam@treyarch.com
- Addressing newbies Christopher Allen
- Addressing newbies J C Lawrence
- Addressing newbies J C Lawrence
- Addressing newbies Raph Koster
- Addressing newbies Christopher Allen
- Addressing newbies adam@treyarch.com
- Addressing newbies J C Lawrence
- Introduction Ian C. Smith
- constructive quests Ola Fosheim Grøstad
- new email address Travis Casey
- [Meta] chest puffing (fwd) J C Lawrence
- [Meta] chest puffing (fwd) J C Lawrence
- [Meta] chest puffing (fwd) Matthew Mihaly
- [Meta] chest puffing (fwd) Ola Fosheim Grøstad
- [Meta] chest puffing (fwd) Par Winzell
- [Meta] chest puffing (fwd) Matthew Mihaly
- [Meta] chest puffing (fwd) Ola Fosheim Grøstad
- [Meta] chest puffing (fwd) Matthew Mihaly
- Critique: Realms of Despair adam@treyarch.com
- Critique: Realms of Despair David Bennett
- Critique: Realms of Despair Kevin Scott London
- Critique: Realms of Despair adam@treyarch.com
- Critique: Realms of Despair Andrew Ritchie
- Critique: Realms of Despair adam@treyarch.com
- Critique: Realms of Despair adam@treyarch.com
- Critique: Realms of Despair Marc Bowden
- Software combinations Ian C. Smith
- Software combinations David Bennett
- Software combinations Erik Jarvi
- Software combinations Ian C. Smith
- Software combinations Scatter
- Software combinations J C Lawrence
- Hobby Muds and Money Maarten van Leunen
- Hobby Muds and Money Mordengaard
- Mud Clients Mud Imp
- update on selling Godhoods Matthew Mihaly
- update on selling Godhoods Brian Green
- update on selling Godhoods Richard Woolcock
- update on selling Godhoods Matthew Mihaly
- update on selling Godhoods Jeremy Hovance
- Ten commandments for the next MMORPG Raph Koster
- Ten commandments for the next MMORPG Dan Shiovitz
- Ten commandments for the next MMORPG Brian Green
- Ten commandments for the next MMORPG Matthew Mihaly
- Ten commandments for the next MMORPG AR Schleicher
- Ten commandments for the next MMORPG Mud Imp
- Ten Commandments for the next MMORPG The Inquisition Administrator
- Ten commandments for the next MMORPG David Wruck
- MudDev FAQ 2 Marian Griffith
- MudDev FAQ 2 Wes Connell
- The great myth of broadband Brian Green
- The great myth of broadband Madrona Tree
- The great myth of broadband Par Winzell
- The great myth of broadband John Bertoglio
- Effective use of the third dimension Richard Ross
- Effective use of the third dimension adam@treyarch.com
- Effective use of the third dimension Richard Tew
- Ten commandments for players of the next MMORPG Ananda Dawnsinger
- Free Speech Jeff Freeman
- Free Speech Ananda Dawnsinger
- Free Speech Par Winzell
- Free Speech Jeff Freeman
- Free Speech Jon A. Lambert
- Free Speech Schubert, Damion
- Free Speech Matthew Mihaly
- Free Speech Jessica Mulligan
- Free Speech Darren Henderson
- Free Speech kitkat@marcus.pants.nu
- Free Speech Gary Whitten
- Free Speech J C Lawrence
- Free Speech Geoffrey A. MacDougall
- Free Speech Jeremy Hovance
- RPGPlanet article: The Evils of Character Progression Raph Koster
- More storytelling - And also game secrets Chris Lloyd
- Marketing text-based games (was: Ten Commandments for the next MMORPG) Andrew Ritchie
- java performance questions (fwd) J C Lawrence
- MUDs as art (was A footnote to Procedural Storytelling) Ola Fosheim Grøstad
- MUDs as art (was A footnote to Procedural Storytelling) Lee Sheldon
- MUDs as art (was A footnote to Procedural Storytelling) Caliban Tiresias Darklock
- Any hungry Java GUI programmers out there? Par Winzell
- Any hungry Java GUI programmers out there? Par Winzell
- Supporting multiple output formats Nolan Darilek
- The 10 basic rules of a good PvP system Raph Koster
- Player storytellers? Travis Nixon
- Thoughts about smarter Sims Jon A. Lambert
- Thoughts about smarter Sims J C Lawrence
- Thoughts about smarter Sims Jon A. Lambert
- Thoughts about smarter Sims Raph Koster
- Thoughts about smarter Sims Jon A. Lambert
- Thoughts about smarter Sims Paul Schwanz - Enterprise Services
- Thoughts about smarter Sims Jon A. Lambert
- Thoughts about smarter Sims Mordengaard
- Thoughts about smarter Sims Jon A. Lambert
- Thoughts about smarter Sims Justin Rogers
- Thoughts about smarter Sims Jon A. Lambert
- Advancement considered harmful (long) Brian Green
- Advancement considered harmful (long) Zak Jarvis
- Advancement considered harmful (long) J C Lawrence
- Advancement considered harmful (long) Zak Jarvis
- Advancement considered harmful (long) Raph Koster
- Advancement considered harmful (long) Zak Jarvis
- Advancement considered harmful (long) Charles Hughes
- Advancement considered harmful (long) Zak Jarvis
- Advancement considered harmful (long) Dave Rickey
- Advancement considered harmful (long) J C Lawrence
- Advancement considered harmful (long) Travis Nixon
- Advancement considered harmful (long) Paul Schwanz - Enterprise Services
- Advancement considered harmful (long) Miroslav Silovic
- Advancement considered harmful (long) Batir
- What I want, what players want Andrew Ritchie
- What I want, what players want Chris Jacobson
- What I want, what players want Jeff Freeman
- What I want, what players want Nicolai Hansen
- What I want, what players want Darren Henderson
- What I want, what players want adam@treyarch.com
- Domain Names and Trademarks Jon Morrow
- Domain Names and Trademarks J C Lawrence
- Domain Names and Trademarks Sellers, Michael
- Narratology WAS: Self-Sufficient Worlds Zak Jarvis
- Narratology WAS: Self-Sufficient Worlds J C Lawrence
- Narratology WAS: Self-Sufficient Worlds Zak Jarvis
- Narratology WAS: Self-Sufficient Worlds Christopher Allen
- narratology WAS Self-Sufficient Worlds Angela Ferraiolo
- FW: Advancement considered harmful (long) John Buehler
- Narratology and its application to VR, multi-player games, and the like J C Lawrence
- FW: Advancement considered harmful (long) John Buehler
- coordinate systems Richard Tew
- coordinate systems Jon Leonard
- coordinate systems Kerem 'Waster_' HADIMLI