Better than PageRank: Hitting Time as a Reputation Mechanism

Abstract

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.