What is Computational Social Choice?

Algorithmic
Insights Classical results in social choice theory often concern the mathematical possibility (or impossibility) of designing mechanisms for collective decision making that meet certain desirable properties. These usually are normative properties, such as satisfying some notion of fairness or being immune to strategic manipulation. But those classical results typically do not take computational considerations into account. In COMSOC, on the other hand, algorithmic questions take centre stage: How hard, in the complexity-theoretic sense, is it to solve the problem at hand? Can we design an algorithm for it?

Information
Encoding Mechanisms for collective decision making, such as voting rules or protocols for the fair allocation of resources, may face serious challenges when dealing with large numbers of alternatives. Those numbers can get large when alternatives have a combinatorial structure, meaning that the overall decision to be taken really is made up of several smaller decisions. COMSOC makes the need for the compact representation of preferences explicit: How should we represent the preferences of individuals over a complex space of alternatives? What is the impact of the chosen format of representation on the mechanisms and algorithms we can design?

Strategic
Thinking Social choice theory is a close cousin of game theory, the study of mathematical models for the analysis of strategic interactions between rational agents. Indeed, a voter seeking to act in their own best interest must reason about the impact their own vote will have in view of the strategies adopted by everybody else. There thus is an intensive exchange of ideas between COMSOC and the field of algorithmic game theory. Can we avoid voters acting strategically? Does this depend on the information voters have access to? Does it depend on their computational abilities?

Formal
Reasoning Logic has long been used to formally specify the behaviour of both hardware and software systems, so as to allow for the automatic verification of certain desirable properties of such systems. Can we use logic in a similar fashion to also verify the adequate behaviour of “social procedures”, such as voting rules? Relatedly, logic is at the core of attempts to automate the derivation of proofs in several branches of mathematics. Can this methodology be applied to open problems in social choice theory as well?

Learning
Choices There are also intriguing open questions at the interface of social choice theory with machine learning. Also here, the exchange of ideas can go in both directions. Can we learn a good voting rule from data on collective decisions taken in specific situations? Vice versa, can we use the axiomatic method of social choice theory to improve machine learning algorithms that may affect groups of individuals and that are required to adhere to certain ethical standards?

Experimental
Findings The formal models we study in social choice theory are intended to to represent real-life processes. There thus is a need for collaboration between social choice theorists and behavioural scientists. What are realistic assumptions regarding the preferences found in a population? Are the decisions taken by a given mechansism perceived as fair by its users? Assumptions and hypotheses need to be tested in controlled environments to assess how realistic they are. Human feedback must be collected on aggregation mechanisms to determine their usability. Numerical simulations with real-life data also can offer important insights.