Reputation games for undirected graphs

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(n2) time algorithm for a tree, and a parametric O(2kn4) 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(n3) 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 α-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.