Person:

Liu, Brandon

In online multi-agent systems, reputation systems are needed to distinguish between trustworthy agents and potentially malicious or unreliable agents. A good reputation system should be accurate, resistant to strategic manipulations, and computationally tractable. I experimentally analyze the accuracy and manipulation-resistance of a reputation mechanism called personalized hitting time, and present efficient algorithms for its calculation. I present an alternate definition to hitting time that is amenable to Monte Carlo estimation, and show that it is linearly equivalent to the standard definition for hitting time. I present exact and approximation algorithms for computing personalized hitting time, and I show that the approximation algorithms can obtain a highly accurate estimate of hitting time on large graphs more quickly than an exact algorithm can find an exact solution. An experimental comparison of the accuracy of six reputation systems — global and personalized PageRank, global and personalized hitting time, maximum flow, and shortest path — under strategic manipulation shows that personalized hitting time is the most accurate reputation mechanism in the presence of a moderate number of strategic agents.

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 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. 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.