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

Fingerprint

PageRank
Nash Equilibrium
Websites
Game
Search engines
Web Graph
Reputation System
Restart
Web Search
Search Engine
Reputation
Manipulation
Maximise
Symmetry
Imply
Graph in graph theory
Vertex of a graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

On the α-sensitivity of nash equilibria in pagerank-based network reputation games. / Chen, Wei; Teng, Shang Hua; Wang, Yajun; Zhou, Yuan.

Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings. 2009. p. 63-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5598 LNCS).

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

Chen, W, Teng, SH, 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5598 LNCS, pp. 63-73, 3rd International Frontiers of Algorithmics Workshop, FAW 2009, Hefei, China, 6/20/09. https://doi.org/10.1007/978-3-642-02270-8_9
Chen W, Teng SH, Wang Y, Zhou Y. On the α-sensitivity of nash equilibria in pagerank-based network reputation games. In Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings. 2009. p. 63-73. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-02270-8_9
Chen, Wei ; Teng, Shang Hua ; Wang, Yajun ; Zhou, Yuan. / On the α-sensitivity of nash equilibria in pagerank-based network reputation games. Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings. 2009. pp. 63-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{bc645e09321d42af889c0715e888a756,
title = "On the α-sensitivity of nash equilibria in pagerank-based network reputation games",
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 α.",
author = "Wei Chen and Teng, {Shang Hua} and Yajun Wang and Yuan Zhou",
year = "2009",
month = "11",
day = "9",
doi = "10.1007/978-3-642-02270-8_9",
language = "English (US)",
isbn = "3642022693",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "63--73",
booktitle = "Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings",

}

TY - GEN

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

AU - Chen, Wei

AU - Teng, Shang Hua

AU - Wang, Yajun

AU - Zhou, Yuan

PY - 2009/11/9

Y1 - 2009/11/9

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

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

UR - http://www.scopus.com/inward/record.url?scp=70350697854&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350697854&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02270-8_9

DO - 10.1007/978-3-642-02270-8_9

M3 - Conference contribution

AN - SCOPUS:70350697854

SN - 3642022693

SN - 9783642022692

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 73

BT - Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings

ER -