LIRa Special Session on Social Choince in October 25

Social choice theory, a scientific discipline developed largely in mathematical economics and political science, addresses questions regarding the design and analysis of methods for collective decision making. Examples for such methods include voting procedures and protocols for fairly dividing a set of goods amongst the members of a group. The emerging field of computational social choice studies these questions from a computational perspective, making use of a variety of tools and techniques, including logic. In this talk I will highlight a number of recent research directions pursued by members of the COMSOC Group at the ILLC that make use of logic in different ways: the compact representation of preferences over combinatorial domains, the aggregation of judgments regarding logically interconnected propositions, the formal specification of social choice mechanisms, and the use of automated reasoning tools to verify and even discover theorems in social choice theory.

We study a model where a group of self-interested agents negotiate over a set of resources. The agents believe that at the end of the negotiation phase a certain randomisation will take place: either the bundles of resources the agents have accumulated will get reassigned to other agents, or the valuation functions the agents use to assess the values of these bundles will get reassigned, or both. The uncertainty as to which combination of valuation function and bundle an agent will end up with will influence her negotiation strategy. For certain types of uncertainty of this kind and for certain assumptions on the attitude towards risk of the agents involved, it is possible to show that negotiation is guaranteed to converge to an allocation with certain desirable properties, such as maximising egalitarian or utilitarian social welfare. This model of distributed negotiation under uncertainty thus provides a new perspective on theories of social welfare. (This is joint work with Ulle Endriss.)

In the framework of binary aggregation several individuals each make a yes/no choice regarding a number of issues and these choices then need to be aggregated into a collective choice. Depending on the application at hand, different combinations of yes/no may be considered rational. We can describe such rationality assumptions in terms of a propositional formula. The question then arises whether or not a given aggregation procedure will lift the rationality assumptions from the individual to the collective level, i.e., whether the collective choice will be rational whenever all individual choices are. To address this question, for each of a number of simple fragments of the language of propositional logic, we provide an axiomatic characterisation of the class of aggregation procedures that will lift all rationality assumptions expressible in that fragment.
Most classical domains of aggregation can be modelled as binary aggregation problems, but when a more fine-grained analysis is required then rationality assumptions have to be expressed in more complex logical languages. This leads to the question of how to properly define the aggregation of logical structures other than propositional models. The last part of the talk will be dedicated to sketch ideas for future work in this direction. (Joint work with Ulle Endriss)