Mechanisms of Social Interactions: Inference, Experimental Design and Optimization

Abstract

Mechanisms of social interactions describe the way through which local interactions between individuals give rise to complex collective phenomena. By combining the perspectives of statistics, game theory and optimization, this thesis investigates the question of learning, leveraging and engineering mechanisms of social interactions: - when the mechanism is modeled by a random diffusion in a network of individuals, I provide new algorithms to (1) learn an unknown network from few observations of past diffusions, and (2) approximately optimally select a set of individuals that maximizes the spread of the diffusion. Next, I provide evidence that gun violence spreads like a contagion in a network of criminals in Chicago, and that random diffusion models are helpful in predicting and understanding the occurrence of gun violence. - when the individuals are modeled as strategic agents, I construct an auction mechanism for the problem of experimental design, that selects an approximately maximally informative set of individuals respecting a given budget constraint while truthfully eliciting their cost for taking part in the experiment. - looking more broadly at the optimization problems encountered when working with mechanisms of social interactions, I investigate the impact of errors when evaluating the objective functions on the quality of optimization. For maximizing submodular functions---a discrete analogue of concave functions---I show that no efficient algorithm exists when the noise exceeds a certain threshold. For minimizing a convex function in the presence of random noise, I provide an algorithm with improved numerical stability compared to previously known methods.