10.1007/978-3-642-33996-7_7
Cord-Landwehr, Andreas
Andreas
Cord-Landwehr
Huellmann (married name: Eikel), Martina
Martina
Huellmann (married name: Eikel)
Kling, Peter
Peter
Kling
Setzer, Alexander
Alexander
Setzer
Basic Network Creation Games with Communication Interests
2012
2017-10-17T12:42:54Z
2019-04-11T13:44:55Z
conference
https://ris.uni-paderborn.de/record/628
https://ris.uni-paderborn.de/record/628.json
300591 bytes
application/pdf
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 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 Theta(n).Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.