Navigation auf uzh.ch
Navigation auf uzh.ch
Informative and scalable trust mechanisms that are robust to manipulation by strategic agents are a critical component of multi-agent systems. While the global hitting time mechanism (GHT) introduced by Hopcroft and Sheldon [9] is more robust to manipulation than PageRank, strategic agents can still benefit significantly under GHT by performing sybil attacks. In this paper, we introduce the personalized hitting time mechanism (PHT), which we show to be significantly more robust to sybil attacks than GHT.
|
|
|
Figure 1: The effect of strategic behavior by a single agent in a network with 500 non-sybil agents. The graphs shows the old rank (without manipulation) vs. new rank (with sybil manipulation), given that the strategic agent has access to 50 sybils. |
Specifically, if an agent has already cut all of its outlinks under PHT (which only leads to a negligible benefit), then adding sybils leads to no additional benefit. We provide an experimental analysis which demonstrates that, in the presence of strategic agents that create sybils, PHT dominates GHT (as well as PageRank and personalized PageRank) in terms of informativeness. We find the large dominance of PHT over GHT particularly surprising given the small difference between the two mechanisms. Finally, we provide a Monte Carlo algorithm to compute approximate PHT scores at scale, and we show that PHT retains its robustness to manipulation when used with approximate scores.
Webmaster
