Basic network creation games with communication interests

Network creation games model the creation and usage costs of networks formed by a set of selfish peers. Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links. In doing so, a peer can reduce its individual communication cost. Typically, these costs are modeled by the maximum or average distance in the network. We introduce a generalized version of the basic network creation game BNCG. In the BNCG by Alon et al., SPAA 2010, each peer may replace one of its incident links by a link to an arbitrary peer. This is done in a selfish way in order to minimize either the maximum or average distance to all other peers. That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers. However, participants of large networks are seldom interested in all peers. Rather, they want to communicate efficiently with a small subset only. Our model incorporates these communication interests explicitly. Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model. We focus on the MAX-version, i.e., each node tries to minimize the maximum distance to nodes it is interested in, and give an upper bound of ${\mathcal O}{\sqrt{n}}$ for the private costs in an equilibrium of n peers. Moreover, we give an equilibrium for a circular interest graph where a node has private cost $\Omega{\sqrt{n}}$, showing that our bound is tight. This example can be extended such that we get a tight bound of $\Theta{\sqrt{n}}$ for the price of anarchy. For the case of general networks we show the price of anarchy to be i¾źn. Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.