Recent Developments in Collective Decision Making in Combinatorial Domains

Collective decision making is the process of mapping the individual views of several individual agents into a joint decision. The need for collective decision making mechanisms is abundant, not just in the realm of politics, but also for a wide range of scientific and technological applications. These include, for instance, logistics, grid computing, and recommender systems. 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. 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. For instance, if we are asked to elect a committee consisting of k representatives, choosing from a pool of n candidates, then we are in fact faced with a social choice problem with (ⁿ_k) alternatives. Asking each voter for their full preferences over these (ⁿ_k) alternatives may not be feasible in practice. Similarly, if we have to choose between accepting or rejecting each of n different propositions, then we are dealing with a social choice problem with 2ⁿ possible outcomes.

In this talk I will report on a number of recent developments in the area of collective decision making in combinatorial domains. This includes the study of languages for the compact representation of preferences [2,4], the design of voting rules for multi-issue elections [1], and the analysis of the computational complexity of decision problems arising in judgment aggregation [3].