Algorithmic Foundations of Collective Decision Making: 2025-2026
Degrees | Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science |
Term | Hilary Term 2026 (24 lectures) |
Overview
In this course, we study collective decision making from a mathematical and algorithmic perspective, focussing primarily on voting. We formally model situations in which the preferences of agents (or voters) need to be aggregated into a collective choice.
Key questions include:
- Which formal properties should an aggregation function satisfy?
- Which of these properties can be satisfied simultaneously?
- How difficult is it to compute collective choices?
- How can we achieve the ideal of proportional representation?
We will address all these questions formally, by means of mathematical definitions and theorems. A key role will be played by the axiomatic method.
Learning outcomes
Upon completing this course, a student will be able to: - understand fundamental tradeoffs in the context of collective decision making; - model preferences and aggregation methods; - develop (efficient) algorithms for collective decision making; and - analyse axiomatic and computational properties of preference aggregation problems.Synopsis
- Arrow's impossibility theorem
- Strategic voting
- Restricted domains of preferences (single-peaked preferences, etc.)
- Scoring rules (plurality, Borda, etc.),
- Condorcet methods
- Kemeny's rule
- Multiwinner elections
- Apportionment methods
- Proportional representation
Reading list
There is no single textbook that covers all topics. Lecture slides will be published before each lecture. The reading list below provides supplementary materials for those who want to explore topics in greater depth, but is not required.
Introductory texts:
- M. Allingham: Choice Theory - A very short introduction. Oxford University Press, 2002 (Chapters 1, 2, and 6)
- F. Brandt, V. Conitzer, and U. Endriss. Computational Social Choice. In Multiagent Systems (G. Weiss, ed.), MIT Press, 2013 (Sections 1, 2, and 3)
- W. Gaertner: A Primer in Social Choice Theory, Oxford University Press, 2009 (Chapters 1, 2, 3, 5, and 6)
Advanced books:
- F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (eds.): Handbook of Computational Social Choice. Cambridge University Press, 2016 (Chapters 1, 2, 3, 4, and 6)
- H. Moulin: Axioms of Cooperative Decision Making. Cambridge University Press, 1988 (Chapters 9, 10, and 11)
- J. Laslier: Tournament Solutions and Majority Voting. Springer-Verlag, 1997 (Chapters 1, 2, 3, 5, 6, 7, and 10)
- A. Taylor: Social Choice and the Mathematics of Manipulation, Cambridge University Press, 2005 (Chapters 1, 2, and 3)
- U. Endriss (ed.): Trends in Computational Social Choice, AI Access, 2017 (Chapters 2, 3, and 10)
- M. Lackner and P. Skowron: Multi-Winner Voting with Approval Preferences, Springer, 2023 (Chapters 1, 2, 3, and 4)
Taking our courses
This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses
Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.