Logical Frameworks for Multiagent Aggregation
European Summer School in Logic Language and Information, Tübingen, 11-15 August 2014
Lecturer: Umberto Grandi
Lecture notes : download here the lecture notes.
Societies of agents, be they human or artificial, need rules to take collective decisions. The field of Social Choice Theory has come up in the last century with procedures and theoretical analyses of the problem of collective choice, developing tools that are recently receiving increasing attention from researchers in Artificial Intelligence, in particular for the modelling and the design of multiagent systems. Starting from rational individual expressions, such as preferences, judgments and beliefs, the problem of aggregation focuses on how to obtain a collective view from the individual views provided. The basic assumption behind these theories is that individuals can act and choose independently in a rational way: at hearing this word I expect logicians to wake up and pay close attention, given that the concept of rationality is one of the main drives behind logical modelling.
In this spirit, this course wants to provide a partial yet detailed answer to the following question: given that all individuals are rational, can we devise procedures that make rational collective choices from the individual choices collected? The answer to this question is negative in general, as the discovery of a number of paradoxical situations has shown. But this is good news for researchers, as it opens up for the study and the characterisation of domains in which safe (i.e., non-paradoxical) aggregation is possible. The possibility of obtaining rational collective choices from rational individuals, i.e., the problem of collective rationality, is thus the central question in the study of every aggregation framework.
The early developments of Social Choice Theory were inspired by logic in their use of the axiomatic method, but it is with the recent study of judgment aggregation that logic has come to play a more important role in theories of aggregation. These results have been developed across disciplines such as Economic Theory (most notably Social Choice Theory), Computer Science (in particular Artificial Intelligence) and Philosophy. Conferences that are close to the Logic, Language and Information community such as Theoretical Aspects of Rationality and Knowledge (TARK) and Logic and the Foundations of Game and Decision Theory (LOFT) have recently seen an increasing number of submissions in topics related to logical frameworks for aggregation.
In brief: In this course I will provide an introduction to the various frameworks developed for the study of aggregation of individual expressions, and explore in depth the main research questions arising in this field. Logic will be our travel companion: we will see that it is a natural tool to model individual views and rationality assumptions, and proves very useful in characterising domains in which aggregation can be performed in a safe way.
Prerequisites: No strict requirement, but this is an advanced course. A good mastery of mathematical proofs and formal modelling will be expected. Familiarity with basic notions in computational complexity (polynomial reductions, NP-completeness) and propositional logic (basic definitions, conjunctive normal form).
Program (tentative):
- Lecture 1: Condorcet paradox, May's Theorem, preference aggregation, judgment aggregation, binary aggregation, basic computational properties of aggregation frameworks.
- Lecture 2: Paradoxes of aggregation (Condorcet, discursive dilemma, Ostrogorski, multiple elections, divided government), characterisation of paradoxes for the majority rule.
- Lecture 3: Collective rationality and languages for integrity constraints.
- Lecture 4: Ultrafilter techniques and winning coalitions.
- Lecture 5: Aggregation procedures, applications (modal logic, annotations, argumentation)
A list of courses taught at past editions of ESSLLI on related topics:
- ESSLLI 2008 course on Introduction to Computational Social Choice by Ulle Endriss.
- ESSLLI 2012 course on Introduction to Judgment Aggregation by Davide Grossi and Gabriella Pigozzi (lecture notes, now a book)
- ESSLLI 2013 course on Logic and Social Choice Theory by Ulle Endriss.