Algorithms & Randomness Center (ARC)
Nicole Immorlica - Microsoft Research New England
Monday, November 2, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
The Emergent Structure of Simple Behaviors in Complex Networks
Many games of social significance are played in a networked context. In these settings, agents often exhibit simple behaviors, shaped by local preferences and social norms. The interplay of these behaviors and the underlying network give rise to emergent structures with global impact. In this talk, we explore the impact of networked behavior on social capital, segregation, and learning.
First we study the emergence of social capital in dynamic, anonymous social networks, such as online communities. We find that, despite the lack of punitive strategies, (partial) cooperation is sustainable at an intuitive and simple equilibrium as cooperation allows an individual to interact with an increasing number of other cooperators, resulting in the formation of valuable social capital.
Next we examine the emergence of segregation in geographical networks. In 1969, Schelling introduced a model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority and suggested that this local behavior can cause global segregation effects. Our rigorous analysis shows that, in contrast to prior interpretations, the outcome exhibits local but not global segregation.
Finally, we study learning outcomes in social networks. Individuals with independent opinions asynchronously update their declared opinion to match the majority report of their neighbors. We show that the population will converge to the majority opinion with high probability if the underlying network is large, sparse, and expansive, properties reflected by realistic social networks.
Based on joint works with Christie Brandt, Michal Feldman, Gautam Kamath, Robert Kleinberg, Brendan Lucier, Brian Rogers and Matt Weinberg.