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 analyse the quality of resource allocations in human society are equally well applicable to problems in multiagent systems or network design.

Computational social choice brings together ideas from computer science, artificial intelligence, logic, political science and economic theory, amongst others. Below we briefly introduce some representative problems that have been studied in the field.

Social Choice and Theoretical Computer Science

Social choice theory is concerned with the design and analysis of methods for collective decision making. Examples include in particular voting protocols, but also procedures for fairly dividing a number of goods between several agents. 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, classical results in voting theory show that, under some weak and very natural conditions, it is impossible to design a voting protocol that voters cannot manipulate by reporting insincere preferences when casting their ballots. A voting system that induces such insincere voting behaviour cannot be expected to reliably return the socially most preferable candidate as a winner. In recent years, computer scientists have started to analyse this kind of problem from a computational point of view. The basic idea is that, should it be the case that manipulating successfully is a computationally intractable problem, manipulability may be less of a worry.

Social Choice and Logic

Another example for the application of tools typically used in computer science to problems stemming from economics and social choice is the use of logic for the formal specification and verification, or more generally analysis, of social procedures. In the same way as computer scientists have long been using logic to formally specify the behaviour of computer systems, so as to allow for the automatic verification of certain desirable properties of such systems, suitable logics may be used to specify social procedures such as voting protocols or fair division algorithms. This line of research is also known as "social software".

Social Choice and Artificial Intelligence

Known methods for collective decision making and classical results from social choice theory may not always be applicable when the number of alternatives from which to choose is large. This may, for instance, be the case when these alternatives have a combinatorial structure, as in negotiation over indivisible goods (where the number of bundles an agent may obtain is exponential in the number of goods) or committee elections (where the number of possible committees is exponential in the number of seats to be filled). For such combinatorial problems, the mere representation of the preferences of individuals over different alternatives becomes a non-trivial problem. A third example for work in computational social choice is then the application of techniques developed in artificial intelligence and logic for the compact representation of preferences to this kind of problem.

Reference

Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), LNCS 4362, Springer-Verlag, 2007.

F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.