CS359 Computational Social Choice
CS359-15 Computational Social Choice
Introductory description
Computational Social Choice (COMSOC) addresses problems at the interface of social choice theory and computer science. Social choice theory is the formal study of collective decision-making processes, an important example of which are voting rules. We discuss concepts from social choice theory and investigate axiomatic and computational aspects.
Module aims
In this module, we study collective decision making from a mathematical and algorithmic perspective. We formally model situations in which the preferences of agents (or voters) need to be aggregated into a collective choice.
Key questions include:
- What does it mean to make rational choices?
- 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.
Outline syllabus
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
Specific topics include: choice theory, Arrow's impossibility result, restricted domains of preferences, approval voting, scoring rules (plurality, Borda, etc.), Kemeny's rule, tournament solutions, strategic voting, multiwinner elections, apportionment methods, and proportional representation.
Learning outcomes
By the end of the module, students should 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
- analyse axiomatic and computational properties of preference aggregation problems
Indicative reading list
See Talis Aspire link
View reading list on Talis Aspire
Interdisciplinary
Computational Social Choice is a research field at the intersection of computer science and economics (as part of the area often referred to as "Economics and Computation"). It is also related to mathematics, philosophy, and (theoretical) political science.
Subject specific skills
Understanding of fundamental tradeoffs when making collective decisions;
modelling preference aggregation methods and assessing their properties;
developing efficient algorithms for preference aggregation problems;
analysing axiomatic properties of voting rules.
Transferable skills
Critical and strategic thinking;
problem solving;
fair and representative collective decision-making.
Study time
| Type | Required |
|---|---|
| Lectures | 30 sessions of 1 hour (20%) |
| Seminars | 9 sessions of 1 hour (6%) |
| Private study | 81 hours (54%) |
| Assessment | 30 hours (20%) |
| Total | 150 hours |
Private study description
Inclusive of private study, coursework, problem sheets, background reading and revision.
Costs
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Assessment group D
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| Coursework: Problem Set 1 | 10% | 5 hours | Yes (extension) |
|
This assessment is eligible for self-certification (extension). |
|||
| Coursework: Problem Set 2 | 10% | 5 hours | Yes (extension) |
|
This assessment is eligible for self-certification (extension). |
|||
| Exam | 80% | 20 hours | No |
|
Students are asked to solve exercises that are similar in style to the exercises on the problem sheets. |
|||
Assessment group R
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| Exam | 100% | No |
Feedback on assessment
Feedback on problem sets in seminars.
Courses
This module is Optional for:
- Year 3 of UCSA-G4G1 Undergraduate Discrete Mathematics
- Year 3 of UCSA-G4G3 Undergraduate Discrete Mathematics
- Year 4 of UCSA-G4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
- Year 4 of UCSA-G4G2 Undergraduate Discrete Mathematics with Intercalated Year
This module is Option list A for:
- Year 4 of UCSA-G504 MEng Computer Science (with intercalated year)
- Year 3 of UCSA-G500 Undergraduate Computer Science
- Year 4 of UCSA-G502 Undergraduate Computer Science (with Intercalated Year)
-
UCSA-G503 Undergraduate Computer Science MEng
- Year 3 of G500 Computer Science
- Year 3 of G503 Computer Science MEng