Better than PageRank: Hitting Time as a Reputation Mechanism
Author
Metadata
Show full item recordCitation
Liu, Brandon. 2014. Better than PageRank: Hitting Time as a Reputation Mechanism. Bachelor's thesis, Harvard College.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.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:12705170
Collections
- FAS Theses and Dissertations [6136]
Contact administrator regarding this item (to report mistakes or request changes)