Daniil V. Musatov - Extensions of the 'hitchhiker' game-theoretic network formation model

Graphs of various online social networks share several common features. Most important of them are small average (and maximal) distance between two nodes, Pareto degree distribution and high clustering coefficient. Currently, there are no network models that demonstrate all three features. For instance, small world models have high clustering coefficient but unrealistic degree distribuition, and models of preferential attachment have Pareto degree distribution, but clustering coefficient is approximately 10 times lower than in real networks. In 2010, a conceptually new game-theoretic model was presented by Borgs, Chayes, Ding and Lucier. In this model, every agent may organize an arbitrary number of events ('gatherings'). Event organization is costly, and a link is formed if two agents participate together in sufficiently large number of events. Notably, a link may be created if two people are jointly invited to some gatherings organized by others. In this case they do not bear costs and are 'hitchhikers', thus explaining the name of the model. An advantage of this model is the fact that many real networks may emerge as a Nash equilibrium. A disadvantage is the immense multiplicity of equilibria: a plenty of other networks may also emerge. Moreover, if any non-empty equilibrium exists then the complete network is an equilibrium. We propose several extensions of the model that reduce the number of equilibria. Specifically, we propose differentiated costs of organizing events and differentiated gains from connections. We consider several particular examples and find equilibria in them. Though these equilibria are still not fully realistic, we believe that this line of research is potentially fruitful.