Decision making under uncertainty: Theoretical and empirical results on social choice, manipulation, and bribery

This dissertation focuses on voting as a means of preference aggregation. Specifically, empirically testing various properties of voting rules and theoretically analyzing how much information it takes to make tampering with an election computationally hard.;Groups of individuals have always struggled to come to consistent and fair group decisions and entire fields of study have emerged in economics, psychology, political science, and computer science to deal with the myriad problems that arise in these settings. In my research I have sought to gain a deeper understanding of the practical and theoretical issues that surround voting rules. This dissertation lies within the field of computational social choice, a subfield of artificial intelligence. This cross disciplinary area has broader impacts within the fields of economics, computer science, and political science.;My theoretical work focuses on the computational complexity of the bribery and manipulation problems. The bribery problem asks if an outside agent can affect the results of a voting scenario given some budget constraints, while the manipulation problem asks if one or more voting agents can strategically misrepresent their votes to induce a more preferred outcome. These questions seem to hinge on the amount of information an agent has. In this work I investigate the situations where the agents have access to perfect information, uncertain information, and structured preference information. I find that, depending on the structure and type of information, the complexity of the bribery and manipulation problems 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 assumptions in the social choice and voting theory literature. A dearth of accurate data has led many studies of the properties of voting rules to take place in the theoretical domain. With the new dataset I have been able to test many theoretical voting paradoxes with orders of magnitude more data than previously available. This work shows that many of the irregularities or paradoxes associated with voting occur very rarely in practice.;KEYWORDS: Artificial Intelligence, Computational Social Choice, Voting Theory, Bribery, CP-nets.