Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs
verfasst von : David Avis, Kazuo Iwama, Daichi Paku
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
J. Hopcroft and D. Sheldon originally introduced the PageRank game to investigate the self-interested behavior of web authors who want to boost their PageRank by using game theoretical approaches. The PageRank game is a multiplayer game where players are the nodes in a directed web graph and they place their outlinks to maximize their PageRank value. They give best response strategies for each player and characterize properties of
α
-insensitive Nash equilibria. In this paper we consider PageRank games for undirected web graphs, where players are free to delete any of their bidirectional links if they wish. We study the problem of determining whether the given graph represents a Nash equilibrium or not. We give an
O
(
n
2
) time algorithm for a tree, and a parametric
O
(2
k
n
4
) time algorithm for general graphs, where
k
is the maximum vertex degree in any biconnected component of the graph.