zbMATH — the first resource for mathematics

Max celebrity games. (English) Zbl 1398.91106
Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 13th international workshop, WAW 2016, Montreal, QC, Canada, December 14–15, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-49786-0/pbk; 978-3-319-49787-7/ebook). Lecture Notes in Computer Science 10088, 88-99 (2016).
Summary: We introduce max celebrity games a new variant of celebrity games defined in our work [Theor. Comput. Sci. 648, 56–71 (2016; Zbl 1410.91115)]. In both models players have weights and there is a critical distance \(\beta \) as well as a link cost \(\alpha \). In the max celebrity model the cost of a player depends on the cost of establishing links to other players and on the maximum of the weights of those nodes that are farther away than \(\beta \) (instead of the sum of weights as in celebrity games). The main results for \(\beta >1\) are that: computing a best response for a player is NP-hard; the optimal social cost of a celebrity game depends on the relation between \(\alpha \) and \(w_{max}\); ne always exist and ne graphs are either connected or a set of \(r\geq 1\) connected components where at most one of them is not an isolated node; for the class of connected ne graphs we obtain a general upper bound of \(2 \beta +2\) for the diameter. We also analyze the price of anarchy (PoA) of connected ne graphs and we show that there exist games \(\varGamma \) such that \(\text{PoA} (\varGamma )=\varTheta (n/\beta )\); modifying the cost of a player we guarantee that all ne graphs are connected, but the diameter might be \(n-1\). Finally, when \(\beta =1\), computing a best response for a player is polynomial time solvable and the \(\text{PoA} = O(w_{\max}/w_{\min})\).
For the entire collection see [Zbl 1350.68010].

91A43 Games involving graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
91D30 Social networks; opinion dynamics
Full Text: DOI