Hiders' Game

A number of recent models in the literature studied various versions of the adversarial social network analysis problem. Generally speaking, this problem involves some members of a network---e.g. leaders of a covert network, political activists, or simply privacy-concerned members of the public---attempting to evade social network analysis tools, such as centrality measures, by rewiring the network. While to date most works focused on analysing possible actions of the evader, in this paper, we propose the first study of the adversarial social network analysis problem as a  network formation game. In particular, our model concern scenarios, in which a group of newcomers attempt to connect to and possibly rewire the social network with a aim to become directly tied with important players with high centrality but while keeping a their own centrality small. Our model extends the existing network formation literature, including the well-known model of Jackson and Wolinsky, by considering additional strategies and utility formulations more suitable to the adversarial social network analysis. In more detail, in our network formation game, we allow a player not only to connect to another node, but also to connect any two of her existing neighbour. Furthermore, unlike many network formation games, where utilities reward high degree, our focus is on minimising own degree while maximising connectedness to high-degree nodes which is a proxy for influence in the network. Analysing the structure of the networks in equilibria, we algorithmically demonstrate that the pairwise Nash stable networks (\PANS) have a lattice structure. We also exactly characterise the \PANS{} in practically important cases. Furthermore, we exactly bound the social efficiency of \PANS{}, namely the price of anarchy and stability, and directly connect efficiency to the strength of \PANS.