Celebrity games

We introduce Celebrity games, a new model of network creation games. In this model players have weights (W being the sum of all the player's weights) and there is a critical distance β as well as a link cost α. The cost incurred by a player depends on the cost of establishing links to other players and on the sum of the weights of those players that remain farther than the critical distance. Intuitively, the aim of any player is to be relatively close (at a distance less than β) from the rest of players, mainly of those having high weights. The main features of celebrity games are that: computing the best response of a player is NP-hard if β>1 and polynomial time solvable otherwise; they always have a pure Nash equilibrium; the family of celebrity games having a connected Nash equilibrium is characterized (the so called star celebrity games) and bounds on the diameter of the resulting equilibrium graphs are given; a special case of star celebrity games shares its set of Nash equilibrium profiles with the MaxBD games with uniform bounded distance β introduced in Bilò et al. [6]. Moreover, we analyze the Price of Anarchy (PoA) and of Stability (PoS) of celebrity games and give several bounds. These are that: for non-star celebrity games PoA=PoS=max{1,W/α}; for star celebrity games PoS=1 and PoA=O(min{n/β,Wα}) but if the Nash Equilibrium is a tree then the PoA is O(1); finally, when β=1 the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for β=2.