##
* 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.