What is Computational Social Choice?

Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, promoting an exchange of ideas in both directions. On the one hand, it is concerned with the application of techniques developed in computer science, such as complexity analysis or algorithm design, to the study of social choice mechanisms, such as voting procedures or fair division algorithms. On the other hand, computational social choice is concerned with importing concepts from social choice theory into computing. For instance, social welfare orderings originally developed to analyze the quality of resource allocations in human society are equally well applicable to problems in multiagent systems or network design.

Social choice theory is concerned with the design and analysis of methods for collective decision making. Much classical work in the field has concentrated on establishing abstract results regarding the existence (or otherwise) of procedures meeting certain requirements, but such work has not usually taken computational issues into account. For instance, while it may not be possible to design a voting protocol that makes it impossible for a voter to cheat in one way or another, it may well be the case that cheating successfully turns out to be a computationally intractable problem, which may therefore be deemed an acceptable risk.

Examples for topics studied in computational social choice include the complexity-theoretic analysis of voting protocols (both with a view to developing computationally feasible mechanisms, and to exploit computational intractability as a means against strategic manipulation); the formal specification and verification of social procedures such as fair division algorithms (social software); and the application of techniques developed in artificial intelligence and logic to the compact representation of preferences in combinatorial domains (such as negotiation over indivisible resources or voting for assemblies).

These are examples for a wider trend towards interdisciplinary research involving all of decision theory, game theory, social choice, and welfare economics on the one hand, and computer science, artificial intelligence, multiagent systems, operations research, and computational logic on the other. In particular, the mutually beneficial impact of research in game theory and computer science is already widely recognized and has lead to significant advances in areas such as combinatorial auctions, mechanism design, negotiation in multiagent systems, and applications in electronic commerce. What has been missing so far is a forum that specifically addresses issues in social choice theory. By organizing the COMSOC workshop series we hope to be able to fill this gap.