The former, pretty much - if I want to know who I trust, I start with all the buckets empty, then start adding water to my bucket, and everyone gets a "trust rank" showing how much I trust them in order.
This is very similar in flavor to advogato's current trust metric. The main API difference is that it creates ordinal rankings. To weed stuff out based on it you'd presumably have to set a threshold. Advogato currently has multiple manually tweaked thresholds based on minimum distance, so a single simple one would be a big improvement.
Your system has some nice game-resistance properties. It can neither help nor hurt a peer's own status to cert other peers. However, the system can be gamed a little bit by trading certs with peers, so as to utilize water which would otherwise be wasted by being a dead end.
Exactly as you say, you just decide how many people to trust and you get that many people or so back from the metric. The "or so" is because some people may rank equally.
There are some big differences with Advogato. For one thing, it's deterministic; Advogato gives different rankings given isomorphic graphs, because Ford-Fulkerson doesn't treat isomorphic graphs the same. But the most important difference is that it works on incomplete graphs. And of course it's considerably simpler than Advogato.
TBH it seems as if Raph must have considered and rejected this metric before inventing the Advogato metric, but I'd be curious to know why; it's not in his draft PhD thesis.
The game-resistance property you name was a key design decision. I think dead ends will be very rare in practice, but I'll be interested to find out.
Don't be so sure that the technique occured to Raph before. It certainly hadn't occured to me. Trust metrics are a largely unexplored area, in which even the basic concepts are very far from obvious, despite sounding simple once they're explained.
Another problem with dead ends is that a node may be discouraged from certing a dead end because that would waste water once the node is filled up. This could be fixed by making water at a dead end back up rather than spill out. That might be a worthwile improvement.
You might be right about backing up. I had initially thought that it would make an incomplete graph implementation harder, but thinking about it it's just as easy - since you can and must do dead end discovery either way, you just mandate that water divides evenly between arcs that lead to non-dead-end nodes. I still think dead ends will be rare though.
Here is another weakness in your system, which is also present to some extent in max-flow. Say that I cert A and A certs B. If I get inflow of one unit per time, then A will get filled one tick after I do and B will get filled one tick after that. However, if I cert both A and B then both of them will get filled two ticks after I do, which is quite a bit worse for A. This problem is worse in longer chains
( ... )
I'm not sure the weakness you cite is really a weakness. Putting more people on your trusted list weakens the value of the trust you give them - that's pretty much a design decision.
Your alternative metric is one I've considered, and it's an interesting one - ridiculously efficient as you say. I think it might display some weird behaviour though: if the person at the top of my list is already trusted, then the person at the top of their list gets my second trust token before the second person on my list, which seems unnatural.
However, you could use this ranked cycling rule to make the "droplet" technique deterministic. Your metric then becomes a special case with droplet size 1, and it's worth considering what other droplet sizes will do.
Note that you still have to do dead end detection.
Have you considered trying out such a system on a real life group of friends and acquaintances? It might help to show whether the results look 'natural' or reflect what the people handing out trust want or expect.
I can't answer for the social consequences, though...
I certainly have. The metric is easy to implement, but the code to fetch Friends lists from LJ is just complex enough that it would take time away from other things I'm supposed to be doing...
It's an interesting idea, and not one I had thought about. Without having analyzed it carefully, it would seem that it has similar attack resistance properties as the current flow-based algorithm, and some advantages of its own, especially that it's deterministic.
I'm a little unsure whether the "incomplete knowledge" thing is a real win. A good heuristic to use for the network flow algorithm is to always pick the shortest augmenting path. I think you can do this with partial graph info as well, but it may well be that your result is crisper in the number of nodes that need be known.
This model has some network flow flavor and some eigenvalue flavor. As such, I'm intrigued by the possibility that it might be useful as a "bridge" between the two.
I'll have to think about this some more. Thanks for an interesting idea!
Comments 19
(The comment has been removed)
Reply
Your system has some nice game-resistance properties. It can neither help nor hurt a peer's own status to cert other peers. However, the system can be gamed a little bit by trading certs with peers, so as to utilize water which would otherwise be wasted by being a dead end.
Reply
Exactly as you say, you just decide how many people to trust and you get that many people or so back from the metric. The "or so" is because some people may rank equally.
There are some big differences with Advogato. For one thing, it's deterministic; Advogato gives different rankings given isomorphic graphs, because Ford-Fulkerson doesn't treat isomorphic graphs the same. But the most important difference is that it works on incomplete graphs. And of course it's considerably simpler than Advogato.
TBH it seems as if Raph must have considered and rejected this metric before inventing the Advogato metric, but I'd be curious to know why; it's not in his draft PhD thesis.
The game-resistance property you name was a key design decision. I think dead ends will be very rare in practice, but I'll be interested to find out.
Reply
Another problem with dead ends is that a node may be discouraged from certing a dead end because that would waste water once the node is filled up. This could be fixed by making water at a dead end back up rather than spill out. That might be a worthwile improvement.
Reply
Reply
Reply
Your alternative metric is one I've considered, and it's an interesting one - ridiculously efficient as you say. I think it might display some weird behaviour though: if the person at the top of my list is already trusted, then the person at the top of their list gets my second trust token before the second person on my list, which seems unnatural.
However, you could use this ranked cycling rule to make the "droplet" technique deterministic. Your metric then becomes a special case with droplet size 1, and it's worth considering what other droplet sizes will do.
Note that you still have to do dead end detection.
Thanks for writing this!
Reply
I can't answer for the social consequences, though...
Reply
Reply
(The comment has been removed)
Reply
I'm a little unsure whether the "incomplete knowledge" thing is a real win. A good heuristic to use for the network flow algorithm is to always pick the shortest augmenting path. I think you can do this with partial graph info as well, but it may well be that your result is crisper in the number of nodes that need be known.
This model has some network flow flavor and some eigenvalue flavor. As such, I'm intrigued by the possibility that it might be useful as a "bridge" between the two.
I'll have to think about this some more. Thanks for an interesting idea!
Reply
Leave a comment