UC Berkeley

This thesis studies problems in applied probability using combinatorial techniques. The first part of the thesis focuses on voting, and studies the average-case behavior of voting systems with respect to manipulation of their outcome by voters. Many results in the field of voting are negative; in particular, Gibbard and Satterthwaite showed that no reasonable voting system can be strategyproof (a.k.a. nonmanipulable). We prove a quantitative version of this result, showing that the probability of manipulation is nonnegligible, unless the voting system is close to being a dictatorship. We also study manipulation by a coalition of voters, and show that the transition from being powerless to having absolute power is smooth. These results suggest that manipulation is easy on average for reasonable voting systems, and thus computational complexity cannot hide manipulations completely.

The second part of the thesis focuses on statistical inference questions in growing random graph models. In particular, we study the influence of the seed in random trees grown according to preferential attachment and uniform attachment. While the seed has no effect from a weak local limit point of view in either model, different seeds lead to different distributions of limiting trees from a total variation point of view in both models. These results open up a host of new statistical inference questions regarding the temporal dynamics of growing networks.