Personalized Hitting Time for Informative Trust Mechanisms Despite Sybils
Pages 1124 - 1132
Abstract
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.
References
[1]
A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509--512, Oct. 1999.
[2]
M. Bianchini, M. Gori, and F. Scarselli. Inside pagerank. ACM Transactions on Internet Technology, 5(1):92--128, 2005.
[3]
A. Cheng and E. Friedman. Sybilproof reputation mechanisms. In Proceedings of the 2005 ACM SIGCOMM Workshop on Economics of Peer-to-Peer Systems, pages 128--132. ACM, 2005.
[4]
A. Cheng and E. Friedman. Manipulability of PageRank under sybil strategies. In First Workshop on the Economics of Networked Systems, 2006.
[5]
A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-Law Distributions in Empirical Data. SIAM Review, 51(4):661--703, Nov. 2009.
[6]
J. W. Demmel, M. T. Heath, and H. A. van der Vorst. Parallel numerical linear algebra. Acta Numerica, 2:111--197, 1993.
[7]
D. Fogaras, B. Rácz, K. Csalogány, and T. Sarlós. Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3):333--358, 2005.
[8]
Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating Web Spam with TrustRank. In Proceedings of the 30th International Conference on Very Large Databases, pages 576--587, Mar. 2004.
[9]
J. Hopcroft and D. Sheldon. Manipulation-resistant reputations using hitting time. In Algorithms and Models for the Web-Graph, pages 68--81, 2007.
[10]
S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The Eigentrust algorithm for reputation management in P2P networks. In Proceedings of the 12th International Conference on World Wide Web, pages 640--651, 2003.
[11]
J. Kunegis. The koblenz network collection (KONECT), 2015. Accessed on August 30, 2015, http://konect.uni-koblenz.de/.
[12]
R. Landa, D. Griffin, R. G. Clegg, E. Mykoniati, and M. Rio. A sybilproof indirect reciprocity mechanism for peer-to-peer networks. In INFOCOM 2009, pages 343--351, 2009.
[13]
J. Leskovec. Stanford network analysis project, 2015. Accessed on August 30, 2015, http://snap.stanford.edu/index.html.
[14]
L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[15]
J. S. Rosenschein and G. Zlotkin. Designing conventions for automated negotiation. AI Magazine, 15(3):29, 1994.
[16]
S. Seuken and D. C. Parkes. Sybil-proof accounting mechanisms with transitive trust. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Paris, France, 2014.
[17]
S. Seuken, J. Tang, and D. C. Parkes. Accounting mechanisms for distributed work systems. In Proceedings of the 24th Conference on Artificial Intelligence (AAAI), Atlanta, GA, 2010.
[18]
J. Tang, S. Seuken, and D. C. Parkes. Hybrid transitive trust mechanisms. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pages 233--240, 2010.
[19]
M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name bids in combinatorial auctions: new fraud in internet auctions. Games and Economic Behavior, 46(1):174--188, 2004.
[20]
H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. Security and Privacy, pages 3--17, 2008.
[21]
H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. Sybilguard: Defending against sybil attacks via social networks. ACM SIGCOMM Computer Communication Review, 36(4):267--278, 2006.
[22]
H. Yu, Z. Shen, C. Leung, C. Miao, and V. R. Lesser. A survey of multi-agent trust management systems. IEEE Access, pages 35--50, 2013.
Index Terms
- Personalized Hitting Time for Informative Trust Mechanisms Despite Sybils
Recommendations
Hybrid transitive trust mechanisms
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1Establishing trust amongst agents is of central importance to the development of well-functioning multi-agent systems. For example, the anonymity of transactions on the Internet can lead to inefficiencies; e.g., a seller on eBay failing to ship a good ...
Sybil-proof accounting mechanisms with transitive trust
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systemsFor the design of distributed work systems like P2P file-sharing networks it is essential to provide incentives for agents to work for each other rather than free ride. Several mechanisms have been proposed to achieve this goal, including currency ...
Collusion-resistant, incentive-compatible feedback payments
EC '07: Proceedings of the 8th ACM conference on Electronic commerceOnline reputation mechanisms need honest feedback to function effectively. Self-interested agents report the truth only when explicit rewards offset the potential gains obtained from lying. Feedback payment schemes (monetary rewardsfor submitted ...
Comments
Information & Contributors
Information
Published In
May 2016
1580 pages
ISBN:9781450342391
- General Chairs:
- Catholijn M. Jonker,
- Stacy Marsella,
- Program Chairs:
- John Thangarajah,
- Karl Tuyls
Sponsors
- IFAAMAS
In-Cooperation
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 09 May 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AAMAS '16
Sponsor:
AAMAS '16: International Conference on Agents and Multiagent Systems
May 9 - 13, 2016
Singapore, Singapore
Acceptance Rates
AAMAS '16 Paper Acceptance Rate 137 of 550 submissions, 25%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 131Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in