Computational Social Choice – ComSoc

Social choice theory is a branch of economics that already has a long history. More recently computer scientists have tackled similar problems with a more algorithmic approach. These algorithmic questions are important since most results in social choice theory are 'generic' in that they are independent from the object of the decision, the size of the group having to take the decision and the nature of the alternatives. But such considerations become crucial when the set of objects has a combinatorial nature. Such a structure forbids using any naïve approach to collect, store, manipulate, and aggregate preference information. The French community on Social Choice is internationally strong (let us simply observe here that the top journal in the area, Social Choice and Welfare, is managed by in France). Similarly there is an active community in Artificial Intelligence interested by algorithmic problems. Unfortunately, it turns out that these two strong communities rarely meet and, consequently, no cross-fertilization has happened. The aim of this proposal is to change this situation. Let us illustrate the importance of algorithmic questions in social choice by a simple example. Suppose that a group of individuals has to take a decision on a set of projects. This may amount to answering yes or no to approximately 20 questions. Such a setting would be well adapted to describe a legislative assembly having to examine a bill and discuss a number of amendments to this bill. In this problem, the size of the set of alternatives is then 2^{20}, i.e., more than 10^{6}. It is clearly impossible to directly question each member of the group on his/her preference for these 10^{6} alternatives. Even if this were possible, storing the sets of all collected preference orders would be a huge problem. Finally applying an algorithm, even moderately complex, to this extremely large amount of data would result in a practically intractable task. Hence, computational investigations cannot be avoided if one is interested in practical applications of social choice theory. They are not limited to the study of the algorithmic complexity of aggregation procedures. As shown above, they also have to deal with the question of the elicitation and representation of preferences. The project will have four working groups. The first group will work on the methods for the elicitation and representation of preferences. The main theme here is to take advantage of several 'independence' properties that would allow an efficient elicitation procedure and a compact representation of preferences. The second group will deal with questions of fairness and equity. Although these are rather old themes in economics, the questions linked to the algorithmic properties of the associated criteria have been left virtually untouched. yet, there are many important practical situations in which one might wish to apply fairness criteria to a set of alternatives that is quite large, e.g., when scheduling workforce in an hospital. The third group will deal with the algorithmic complexity of aggregation methods. Two main questions will be investigated: aggregation procedures on a combinatorial domain and complexity as a possible counter-measure to Gibbard-Satterthwaite type of results. The fourth group will investigate aggregation problems in presence of incomplete preferences and/or when there is incomplete information about preferences. These two settings are rather natural in situations involving a very large number of objects. Each of these four working groups will involve economists and computer scientists. We do hope that this pluri-disciplinary research program will contribute to the creation of strong research group in the area of computational social choice in France. Key words: Computational social choice, Voting, Complexity, Collective decision making, Equitable resource allocation