CS35915 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 decisionmaking 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 decisionmaking.
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  

Coursework: Problem Set 1  10%  5 hours 
This assessment is eligible for selfcertification (extension). 

Coursework: Problem Set 2  10%  5 hours 
This assessment is eligible for selfcertification (extension). 

Exam  80%  20 hours 
Students are asked to solve exercises that are similar in style to the exercises on the problem sheets. 
Assessment group R
Weighting  Study time  

Exam  100% 
Feedback on assessment
Feedback on problem sets in seminars.
Courses
This module is Optional for:
 Year 3 of UCSAG504 MEng Computer Science (with intercalated year)

UCSAG500 Undergraduate Computer Science
 Year 3 of G500 Computer Science
 Year 3 of G500 Computer Science

UCSAG502 Undergraduate Computer Science (with Intercalated Year)
 Year 3 of G502 Computer Science with Intercalated Year
 Year 3 of G502 Computer Science with Intercalated Year

UCSAG503 Undergraduate Computer Science MEng
 Year 3 of G500 Computer Science
 Year 3 of G503 Computer Science MEng
 Year 3 of G503 Computer Science MEng

UCSAG4G1 Undergraduate Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of UCSAG4G3 Undergraduate Discrete Mathematics
 Year 3 of UCSAG4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
 Year 3 of UCSAG4G2 Undergraduate Discrete Mathematics with Intercalated Year