Celebrity games.

*(English)*Zbl 1410.91115Summary: 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 \(\beta\) as well as a link cost \(\alpha\). 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 \(\beta\)) 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 \(\beta > 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 \(\beta\) introduced in [D. Bilò et al., “Bounded-distance network creation games”, Lect. Notes Comput. Sci. 7695, 72–85 (2012; doi:10.1007/978-3-642-35311-6_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 \(\text{PoA} = \text{PoS} = \max \{1, W / \alpha \}\); for star celebrity games \(\text{PoS} = 1\) and \(\text{PoA} = O(\min \{n / \beta, W \alpha \})\) but if the Nash equilibrium is a tree then the PoA is \(O(1)\); finally, when \(\beta = 1\) the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for \(\beta = 2\).

##### MSC:

91A43 | Games involving graphs |

91D30 | Social networks; opinion dynamics |

05C57 | Games on graphs (graph-theoretic aspects) |

PDF
BibTeX
XML
Cite

\textit{C. Àlvarez} et al., Theor. Comput. Sci. 648, 56--71 (2016; Zbl 1410.91115)

Full Text:
DOI

##### References:

[1] | Albers, S.; Eilts, S.; Even-Dar, E.; Mansour, Y.; Roditty, L., On Nash equilibria for a network creation game, (Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, (2006)), 89-98 · Zbl 1192.91036 |

[2] | Alon, N.; Demaine, E. D.; Hajiaghayi, M.; Kanellopoulos, P.; Leighton, T., Basic network creation games, SIAM J. Discrete Math., 27, 2, 656-668, (2013) · Zbl 1273.90167 |

[3] | Alon, N.; Demaine, E. D.; Hajiaghayi, M.; Kanellopoulos, P.; Leighton, T., Correction: basic network creation games, SIAM J. Discrete Math., 28, 3, 1638-1640, (2014) · Zbl 1302.90163 |

[4] | Àlvarez, C.; Serna, M.; Fernàndez, A., Network formation for asymmetric players and bilateral contracting, Theory Comput. Syst., (2015), in press |

[5] | Bilò, D.; Gualà, L.; Leucci, S.; Proietti, G., The MAX-distance network creation game on general host graphs, Theoret. Comput. Sci., 573, 43-53, (2015) · Zbl 1318.68125 |

[6] | Bilò, D.; Gualà, L.; Proietti, G., Bounded-distance network creation games, (Proceedings of the 8th International Workshop on Internet and Network Economics, WINE, Lecture Notes in Computer Science, vol. 7695, (2012), Springer), 72-85 |

[7] | Bilò, D.; Gualà, L.; Proietti, G., Bounded-distance network creation games, ACM Trans. Econ. Comput., 3, 3, 16, (2015) |

[8] | Brandes, U.; Hoefer, M.; Nick, B., Network creation games with disconnected equilibria, (Proceedings of the 4th International Workshop on Internet and Network Economics, WINE, Lecture Notes in Computer Science, vol. 5385, (2008), Springer), 394-401 |

[9] | Corbo, J.; Parkes, D. C., The price of selfish behavior in bilateral network formation, (Proceedings of the 24th annual ACM Symposium on Principles of Distributed Computing, PODC, (2005)), 99-107 · Zbl 1314.91051 |

[10] | Cord-Landwehr, A.; Lenzner, P., Network creation games: think global - act local, (Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS, Lecture Notes in Computer Science, vol. 9235, (2015), Springer), 248-260 · Zbl 06482813 |

[11] | Demaine, E. D.; Hajiaghayi, M. T.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in cooperative network creation games, ACM SIGecom Exch., 8, 2, (2009) · Zbl 1236.68082 |

[12] | Demaine, E. D.; Hajiaghayi, M. T.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in network creation games, ACM Trans. Algorithms, 8, 2, 13, (2012) · Zbl 1295.68041 |

[13] | Ehsani, Shayan; Fadaee, Saber Shokat; Fazli, Mohammadamin; Mehrabian, Abbas; Sadeghabad, Sina Sadeghian; Safari, Mohammadali; Saghafian, Morteza, A bounded budget network creation game, ACM Trans. Algorithms, 11, 4, 34, (2015) |

[14] | Fabrikant, A.; Luthra, A.; Maneva, E. N.; Papadimitriou, C. H.; Shenker, S., On a network creation game, (Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing, PODC, (2003)), 347-351 · Zbl 1322.91013 |

[15] | Lenzner, P., On dynamics in basic network creation games, (Proceedings of the 4th International Symposium on Algorithmic Game Theory, SAGT, Lecture Notes in Computer Science, vol. 6982, (2011), Springer), 254-265 · Zbl 1233.91071 |

[16] | Leonardi, S.; Sankowski, P., Network formation games with local coalitions, (Proceedings of the 26th ACM Symposium on Principles of Distributed Computing, PODC, (2007)), 299-305 · Zbl 1283.68057 |

[17] | Meirom, E. A.; Mannor, S.; Orda, A., Network formation games with heterogeneous players and the Internet structure, (Proceedings of the 15th ACM Conference on Economics and Computation, EC, (2014)), 735-752 |

[18] | Nikoletseas, S. E.; Panagopoulou, P. N.; Raptopoulos, C.; Spirakis, P. G., On the structure of equilibria in basic network formation, Theoret. Comput. Sci., 590, C, 96-105, (2015) · Zbl 1330.91049 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.