ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 389400, 9787302245179
Tsinghua University Press
We propose a new class of gametheoretic models for network formation in which strategies are not directly related to edge choices, but instead correspond more generally to the exertion of social effort. This differs from existing models in both formulation and results: the observed social network is a byproduct of a more expressive strategic interaction, which can more naturally explain the emergence of complex social structures. Within this framework, we present a natural network formation game in which agent utilities are locally defined and that, despite its simplicity, nevertheless produces a rich class of equilibria that exhibit structural properties commonly observed in social networks − such as triadic closure − that have proved elusive in most existing models. Specifically, we consider a game in which players organize networking events (or gatherings) at a cost that grows with the number of attendees. A gathering's cost is assumed by the organizer but the benefit accrues equally to all attendees: a link is formed between any two players who see each other at more than a certain number r0 of gatherings per time period, whether at gatherings organized by themselves or by third parties. The graph of connections so obtained is the social network of the model. We analyze the Nash equilibria of this game for the case in which each player derives a benet a > 0 from all her neighbors in the social network and when the costs are linear, i.e., when the cost of a gathering with Ɩ invitees is b + cƖ, with b > 0 and c > 0. For γ = a/cr0 > 1 and b sufficiently small, all Nash equilibria have the complete graph as their social network; for γ < 1 the Nash equilibria correspond to a rich class of social networks, all of which have substantial clustering in the sense that the clustering coefficient is bounded below by the inverse of the average degree. Many observed social network structures occur as Nash equilibria of this model. In particular, for any degree sequence with finite mean, and not too many vertices of degree one or two, we can construct a Nash equilibrium producing a social network with the given degree sequence. We also briefly discuss generalizations of this model to more complex utility functions and processes by which the resulting social network is formed. Preview:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.