An Algorithmic Approach To Analyzing Social Phenomena

Other Titles



Online information and interaction is becoming more and more prominent in our lives. This development is made possible by the growth of large-scale userbased applications on the Web (including sites such as Wikipedia and Facebook). As the number of people using these applications increases, the number of social interactions increases and we start to witness social phenomena which originally appeared in the offline world, as well as new ones. Our main goal in this thesis is to obtain a better understanding of some of these phenomena both in the online and the offline world. We will concentrate on phenomena from two main domains. First, motivated by the increasing interest in polarization and the implications that social interactions in the online world has on it, we study how people form their opinion. We present and analyze two models of opinion formation and a more general model of culture dynamics describing the process by which people form opinions on a set of issues simultaneously. Second, we consider how to allocate credit to incentivize effort. We explore this question in the realm of scientific communities by studying a simple game theoretic model illustrating the process by which researchers choose a research project. Our results are not restricted to the academic domain alone, as crowd sourcing sites like Wikipedia are already implementing number of credit-allocation conventions familiar from the scientific community. We also take a special interest in studying the effects long range reasoning has on individuals' choices in other academic domains. We will take the algorithmic approach in which we first try to construct a model of the phenomena in question. For the most part of this thesis we choose to model individuals as strategic agents maximizing some utility function. Then we analyze the model using tools from various fields such as game theory, computer science and statistical physics. Finally, we use our analysis to derive lessons for designing new systems.

Journal / Series

Volume & Issue



Date Issued




Algorithmic game theory; social networks


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Kleinberg, Jon M

Committee Co-Chair

Committee Member

Macy, Michael Walton
Halpern, Joseph Yehuda

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record