Nicholas Mattei is a recipient of The Graduate School’s Myrle E. and Verle D. Nietzel Visiting Distinguished Faculty Award, honoring outstanding dissertations. Dr. Francesca Rossi of the University of Padova, Italy, is the Visiting Distinguished Faculty and will serve as the Graduate School’s outside examiner during the dissertation defense.

Dissertation Title: Decision Making Under Uncertainty: Theoretical and Empirical Results on Social Choice, Manipulation, and Bribery.

Abstract Title: Groups of individuals have always struggled to come to consistent and fair group decisions. Entire fields of study have emerged in economics, psychology, political science, and computer science to deal with the myriad intricacies that emerge when groups attempt to decide. In my PhD work I have sought to gain a deeper understanding of the practical and theoretical shortcomings of existing voting rules and procedures. This dissertation lies within the field of computational social choice, which is a subfield of artificial intelligence. Computational social choice attempts to apply ideas from computer science to the well established field of social choice. This information exchange goes both ways and this cross disciplinary area has broader impacts with the fields of economics, computer science, and political science. My theoretical work focuses the computational complexity of the bribery problem. The bribery problem asks if an outside agent can affect the results of a voting scenario. The key to this question seems to lay in the amount of information the outside agent has access to. In this work I investigate the situation when the outside actor has access to perfect information, uncertain information, and structured information, with respect to the voting agents? preferences. I find that, depending on the structure and type of information, the complexity of the bribery problem can range from computationally easy to computationally intractable. Equally critical to the theoretical aspects of voting are empirical tests of existing assumptions. I have identified a large, sincere source of data with which to test many of the underlying assumptions of social choice. For years a dearth of accurate data has led to many studies of the properties of voting rules to take place in the theoretical domains. With the new dataset, identified as part of my dissertation research, I have been able to test many theoretical voting paradoxes with orders of magnitude more data than is currently available. This work shows that many of the irregularities or paradoxes associated with voting occur very rarely in practice.