A computational perspective on collective decision making

Abstract

In this talk I will provide two examples of the research that is being conducted in artificial intelligence, and particularly in the research agenda of computational social choice, on the implementation and analysis of classical problems from social choice theory. In particular, I will focus on the problem of taking collective decisions on combinatorial sets of alternatives, such as multiple referenda or committee elections, which have a long history of documented paradoxical outcomes. The solutions initially proposed in political science and in computer science have a too high computational complexity of implementation, i.e., the time necessary to obtain the result may be excessively long. I will therefore propose simpler solutions based on the selection of the most representative voter in an electorate, presenting considerations of computational complexity as well as algorithmic approximation results. Towards the end of the talk I will also touch on the use of simulations in the related problem of iterated manipulation in elections, showing how an experimental approach can provide useful tools to select those voting procedures that are more appropriate depending on the collective decision problem at hand.