This is the website for the course on computational social choice to be taught at the 20th European Summer School in Logic, Language and Information (ESSLLI-2008) in Hamburg in August 2008.
This course will give a gentle introduction to computational social choice, a new interdisciplinary field of study bringing together ideas from computer science, artificial intelligence, logic, political science and economic theory. Being a foundational course, no specific background is required to follow the lectures.
Social choice theory studies mechanisms for collective decision making. Examples are the comparison of different voting systems or the design of protocols for fairly dividing a number of goods between several agents. While the field has been spectacularly successful, yielding a host of deep mathematical results as well as Nobel prizes to some of its main proponents, it has largely neglected computational concerns. For instance, if we are interested in fairly allocating 100 indivisible goods to ten agents, then even just writing down a complete description of the problem requires asking each agent for their preferences over the 2100 alternative bundles of goods they might receive. This will hardly be possible if done in a naïve manner. But there are also examples where the computational perspective can resolve problems rather than create new ones. For instance, a seminal result in social choice theory says that there can be no voting system that would be non-manipulable in the sense of not sometimes giving incentives to voters to misrepresent their true preferences. However, if we can show this form of manipulation to be computationally intractable, then we may consider the issue less of a worry. Computational social choice addresses these and similar problems.
Logic & Computation play a central role in computational social choice. First, classical social theory already makes heavy use of logic: problems are typically specified using axioms and famous impossibility results, such as Arrow's Theorem, point at inconsistencies of certain combinations of such axioms. Second, a key ingredient of any social choice problem are the preferences of the individual agents, and logic has proven extremely useful for modelling preferences, in particular when the alternatives to be decided upon have a combinatorial structure. Third, complexity theory has been used extensively to provide a deeper analysis of social choice mechanisms.
The course will cover topics in preference modelling, voting theory, and fair division, and it will highlight recent contributions integrating social choice theory on the one hand and Logic & Computation on the other.
The survey papers listed below address many of the topics to be discussed during the course: