On the α-sensitivity of nash equilibria in pagerank-based network reputation games

Wei Chen, Shang Hua Teng, Yajun Wang, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Web search engines use link-based reputation systems (e.g. PageRank) to measure the importance of web pages, giving rise to the strategic manipulations of hyperlinks by spammers and others to boost their web pages' reputation scores. Hopcroft and Sheldon [10] study this phenomenon by proposing a network formation game in which nodes strategically select their outgoing links in order to maximize their PageRank scores. They pose an open question in [10] asking whether all Nash equilibria in the PageRank game are insensitive to the restart probability α of the PageRank algorithm. They show that a positive answer to the question would imply that all Nash equilibria in the PageRank game must satisfy some strong algebraic symmetry, a property rarely satisfied by real web graphs. In this paper, we give a negative answer to this open question. We present a family of graphs that are Nash equilibria in the PageRank game only for certain choices of α.

Original languageEnglish (US)
Title of host publicationFrontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings
Pages63-73
Number of pages11
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event3rd International Frontiers of Algorithmics Workshop, FAW 2009 - Hefei, China
Duration: Jun 20 2009Jun 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5598 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Frontiers of Algorithmics Workshop, FAW 2009
CountryChina
CityHefei
Period6/20/096/23/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the α-sensitivity of nash equilibria in pagerank-based network reputation games'. Together they form a unique fingerprint.

  • Cite this

    Chen, W., Teng, S. H., Wang, Y., & Zhou, Y. (2009). On the α-sensitivity of nash equilibria in pagerank-based network reputation games. In Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings (pp. 63-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5598 LNCS). https://doi.org/10.1007/978-3-642-02270-8_9