Computational social choice is concerned with the design and analysis of mechanisms for collective decision making. This course provides a thorough introduction to both classical social choice theory, originating in Economics and Political Science, and modern computational social choice, emphasising its interface with Computer Science and AI. The intention is to enable students to conduct independent research in this exciting and fast-moving field. This is an advanced, research-oriented course in the Master of Logic that is also listed as an elective for the MSc AI and the MSc Computational Science. Students from other programmes, such as Computer Science, Mathematics, Economics, or Philosophy, are equally welcome (contact me if you are unsure about your qualifications).
Nature of the Course and Prerequisites: The focus of this course is on theory: we will mostly be concerned with developing formal models of collective decision making and with proving theorems about those models. Therefore, I will expect what sometimes is called mathematical maturity, meaning that you need to have prior experience with working out and writing up mathematical proofs.
Special Theme for 2024: The special theme for this edition of the course is representation and reasoning. In particular, we will see how to use tools from the field of automated reasoning (notably SAT solvers) to support the research process in social choice theory.
Literature: We will mostly rely on original research papers, which I will post on this website as we go along. Beyond these papers, the main reference for this course is the Handbook of Computational Social Choice, the electronic edition of which is freely available online.
Please note that the outline below is tentative only. We will use some of the tutorial slots in the official schedule to discuss your progress with the mini-projects, and possibly to cover some background material some of you might not yet be familiar with. But there won't be any regular tutorials (in the sense of exercise classes). It's also possible that we might use some of the tutorial slots for lectures and/or some of the lecture slots for other activities. In principle, you should be available during all officially scheduled course activities. Please also note that the scheduling of the presentations during the final week is not yet finalised.
| Date | Content | Homework |
|---|---|---|
| Tuesday 29 October 2024 |
This first lecture has been a bit of a sightseeing tour of computational social choice, with various examples for problems addressed, results obtained, and techniques employed in different subfields of this research area. |
Read the historical (not the technical) parts of Chapter 1 of the Handbook and prepare the presentation of your assigned voting rule. |
| Wednesday 30 October 2024 |
We started with student presentations of a large number of voting rules, illustrating the many different ideas people have had over the centuries for how to run an election. We then tried to put some order into this large space and specifically focussed on the family of positional scoring rules and the family of Condorcet extensions (which, somewhat surprisingly, do not overlap). Finally, we turned our attention to the axiomatic method and proved the seminal result of May, providing a characterisation of the simple majority rule in terms of three simple and convincing axioms. I recommend having a look May's original paper, which is a nice example for an early application of the axiomatic method and still highly accessible today.
|
Homework #1 |
| Friday 1 November 2024 |
Tutorial: SAT Solving via Python We will be going over a simple Jupyter Notebook (view, download) that illustrates how to access a SAT solver via Python. |
|
| Tuesday 5 November 2024 |
Impossibility Theorems |
|
| Wednesday 6 November 2024 |
Strategic Manipulation |
Homework #2 |
| Tuesday 12 November 2024 |
Automated Reasoning 1 |
|
| Wednesday 13 November 2024 |
Automated Reasoning 2 |
Homework #3 |
| Friday 15 November 2024 |
Discussion: Project Startup |
|
| Tuesday 19 November 2024 |
Automated Reasoning 3 |
|
| Wednesday 20 November 2024 |
Alternative Models |
|
| Friday 22 November 2024 |
Discussion: Project Ideas |
|
| Tuesday 26 November 2024 |
Explainability |
|
| Wednesday 27 November 2024 |
Logic for Social Choice |
|
| Wednesday 4 December 2024 |
Combinatorial Domains |
|
| Friday 6 December 2023 |
Discussion: Paper Writing and Reviewing |
|
| Tuesday 10 December 2024 |
Judgment Aggregation |
|
| Wednesday 11 December 2024 |
Discussion: Presenting |
During the second part of the course you will work on a small research project on a topic related to the special theme, write a short paper about it, and present your insights and results in a talk. The purpose of this exercise is to give you some exposure to what it is like to do research, including not only the lofty feeling associated with expanding the boundaries of human knowledge, but also all the hard bits, such as identifying a topic that is worth investigating, finding competent people to collaborate with, and sticking to the relentless deadlines and seemingly arbitrary constraints imposed on you by those higher up the food chain. Projects are to be worked on in groups of three people each. Your paper must be 4-5 pages long, excluding references, using the IJCAI LaTeX style (IJCAI is the International Joint Conference on Artificial Intelligence, the kind of conference where a lot of work on computational social choice gets published). I have a strong preference for your paper not having an appendix, but if you feel that you need to put some material in an appendix, get in touch to discuss this well before you finalise your paper. Finally, you must meet all of the deadlines below (what these involve exactly will get announced in due time):
Identifying a Topic. Finding a good topic for a project is difficult and you should set aside a significant amount of time for this task. You have a lot of freedom about what to work on, but your project must be related to the special theme of representation and reasoning. My advice is to start thinking about possible ideas early, but to not settle on a specific topic until we are a few weeks into course. The first project discussion session in particular is intended to help you generate ideas.
One possible approach is to look through the literature and see whether you can extend an existing paper in some way. For example, maybe you can come up with better proofs of the main results, maybe you can generalise or extend some of the results, maybe you can strengthen some of the results by restricting attention to interesting special cases, or maybe you can obtain new insights by varying the methods used in the original paper (e.g., by adding an algorithmic perspective to a paper that is largely axiomatic, or vice versa).
Good places to look for relevant papers are recent editions of AAMAS, IJCAI, and AAAI. For papers published in the AI literature, I recommend checking these conferences first, but note that in some cases you may find a longer and more mature version in a journal, such as JAIR or AIJ. In the economics literature, you will find good number of papers on social choice theory in the specialised journal Social Choice and Welfare and a few more in the much broader JET. At the interface with philosophy, a relevant journal is Economics and Philosophy. At the interface with theoretical computer science, have a look at EC (a conference) and TEAC (a journal). While this is not a hard rule, I recommend that you focus your search on papers that have been published fairly recently. This makes it more interesting and gives you a better chance managing to do something original. Please note that my own papers are off limits for this exercise (because I will have to grade your project and naturally will be somewhat biased when it comes to my own work).
Requesting approval of your project. Start talking to me about your tentative ideas early on. To formally request approval of your project, upload a one-page PDF on Canvas in which you answer the following three questions:
Drafts and reviewing. As an intermediate step, each group will produce a 2-page draft, consisting of most of Section 2 (often called "The Model" in social choice papers), a few sentences of motivation (from Section 1), and a tentative outline (in the form of a bullet list) of what they still hope top do. Each draft will be anonymously reviewed by several students from the other groups (see how to write a review).
Talks. In the final week of the course, we are going to organise a mini-workshop where each group will present their work (20 minutes talk + 10 minutes for questions). Every group member should contribute in some form. Every course participant will be expected to attend all talks.