  J. Hopcroft and D. Sheldon originally introduced network reputation games to
investigate the self-interested behavior of web authors who want to maximize
their PageRank on a directed web graph by choosing their outlinks in a game
theoretic manner. They give best response strategies for each player and
characterize properties of web graphs which are Nash equilibria. In this paper
we consider three different models for PageRank games on undirected graphs such
as certain social networks. In undirected graphs players may delete links at
will, but typically cannot add links without the other player's permission. In
the deletion-model players are free to delete any of their bidirectional links
but may not add links. We study the problem of determining whether the given
graph represents a Nash equilibrium or not in this model. 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. In the request- delete-model players are free to delete
any bidirectional links and add any directed links, since these additions can
be done unilaterally and can be viewed as requests for bidirected links. For
this model we give an $O(n^3)$ time algorithm for verifying Nash equilibria in
trees. Finally, in the add-delete- model we allow a node to make arbitrary
deletions and the addition of a single bidirectional link if it would increase
the page rank of the other player also. In this model we give a parametric
algorithm for verifying Nash equilibria in general graphs and characterize so
called $\alpha$-insensitive Nash Equilibria. We also give a result showing a
large class of graphs where there is an edge addition that causes the PageRank
of both of its endpoints to increase, suggesting convergence towards complete
subgraphs.
