Selfish network creation with non-uniform edge cost.

*(English)*Zbl 1403.91062
BilĂ˛, Vittorio (ed.) et al., Algorithmic game theory. 10th international symposium, SAGT 2017, L’Aquila, Italy, September 12–14, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-66699-0/pbk; 978-3-319-66700-3/ebook). Lecture Notes in Computer Science 10504, 160-172 (2017).

Summary: Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by A. Fabrikant et al. [in: Proceedings of the 22nd annual ACM symposium on principles of distributed computing, PODC ’03. New York, NY: Association for Computing Machinery (ACM). 347–351 (2003; Zbl 1322.91013)] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games.

We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant price of anarchy. To the best of our knowledge, this is the first proof of a constant price of anarchy for any network creation game.

For the entire collection see [Zbl 1371.91003].

We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant price of anarchy. To the best of our knowledge, this is the first proof of a constant price of anarchy for any network creation game.

For the entire collection see [Zbl 1371.91003].

##### MSC:

91A43 | Games involving graphs |

91D30 | Social networks; opinion dynamics |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |