Computational Foundations of Social Choice

Motivation

This seminar will address key issues in computational social choice, a novel interdisciplinary field of study at the interface of social choice theory and computer science. Computational social choice is concerned with the application of computational techniques to the study of social choice mechanisms, such as voting rules and fair division protocols, and with the integration of social choice paradigms into computing. Current research themes in computational social choice include:

The classical literature in social choice theory sometimes speaks informally of one choice rule being "more difficult to compute" than another. This strand of research seeks to pinpoint the computational complexity of various voting rules, to gain a deeper understanding of why some rules are more difficult to compute than others, and to devise efficient algorithms for computing specific voting rules.

Gibbard and Satterthwaite's Theorem tells us that the strategic manipulability of voting systems is unavoidable in principle. However, such manipulation can sometimes be rendered computationally infeasible, and thus deemed an acceptable risk. Methods include worst-case and typical-case analysis, approximability, and heuristic approaches in various formal settings. Manipulation has also been studied in contexts such as controlling the agenda, bribing voters, or using multiple identities.

Besides voting, another central problem domain in social choice theory is fair division. This leads to the study of issues such as the computational requirements of classic cake-cutting algorithms, as well as the complexity of finding suitable allocations of indivisible goods.

Social choice in combinatorial domains is concerned with studying collective decision making mechanisms when the set of alternatives has an underlying combinatorial structure. Research in this area includes work on multiple referenda and committee elections, as well as a host of work on representing and reasoning about preferences in combinatorial domains.

Voting settings are often modeled as cooperative games which represent the voting power of coalitions (e.g., weighted threshold games). Computational research in this area includes work on the compact representation of such games and the complexity of game-theoretic solution concepts such as the core or the Shapley value.

Besides computational complexity theory, theoretical computer science also provides tools to analyze the communication requirements of voting rules and other mechanisms for collective decision making. These issues have been studied in view of efficiency concerns and to scrutinize the existence of privacy-preserving voting protocols.

Much of social choice theory attempts to characterize social choice mechanisms that satisfy various important properties. Such characterizations often have important computational implications (e.g., every mechanism satisfying these properties can be computed efficiently or requires little communication).

This seminar will bring together researchers working on diverse aspects of computational social choice, who come to this area from very different backgrounds: theoretical computer science, artificial intelligence, political science, economics, operations research, and mathematics. This diversity is reflected in the heterogeneous composition of the organizing panel, which includes three computer scientists, an economist, and a mathematician. We expect a mutual fertilization of these disciplines and the emergence of various, possibly multidisciplinary, collaborations.