Collective Decision Making in Combinatorial Domains

This is the website of NWO Vidi project 639.022.706 on "Collective Decision Making in Combinatorial Domains", which is led by Ulle Endriss and ran from January 2008 until June 2013 at the Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam.

The project brings together ideas from computer science, artificial intelligence, multiagent systems, computational logic, and social choice theory to develop and analyse mechanisms for collective decision making when the set of possible agreements has a combinatorial structure. Exemplary applications include resource allocation problems with indivisible goods and the study of voting rules for committee elections.

Keywords: computational social choice, multiagent resource allocation, preference modelling, social software

Scientific Staff

Project Summary

Collective decision making is the process of mapping the individual preferences of several independent agents into a joint decision. The need for collective decision making mechanisms is abundant, not just in human society, but also in a number of scientific and technological application areas. These range from logistics, over grid computing, to e-democracy. The alternatives to be decided upon often have a combinatorial structure: an alternative is characterised by a tuple of variables, each ranging over a finite domain. For instance, if the objective is to divide a number of indivisible goods amongst several agents, then each agent must be able to reason about his or her preferences over sets of goods, of which there are exponentially many. Classical approaches to collective decision making, developed in social choice theory, do not take the computational limitations induced by the combinatorial nature of the problem into account. The overall aim of this project is to develop a comprehensive theory of how agreements between independent decision makers are formed when the domain of possible outcomes has a combinatorial structure. Specific topics to be addressed include the compact representation of preferences in combinatorial domains; the development of distributed approaches to computing fair and economically efficient allocations of resources for varying interpretations of the terms fairness and efficiency; and the logic-based modelling and complexity-theoretic analysis of collective decision making mechanisms. The project will employ the tools and techniques of computer science in a broad sense, including computational logic, artificial intelligence and multiagent systems, whilst also drawing heavily upon ideas from mathematical economics, in particular social choice theory.

Related Links

More information on this research area and on related events and activities is available here:


For further information on the project, please feel free to contact Ulle Endriss.