Lecturer	Edith Elkind
Degrees	Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science Hilary Term — MSc in Advanced Computer Science MSc in Mathematics and Foundations of Computer Science
Term	Hilary Term 2024  (20 lectures)

Overview

The purpose of this module is to explore collective decision making from an algorithmic point of view. We study settings where groups of agents need to make a joint decision by aggregating preferences of individual group members. Examples include (1) voting, i.e., selecting one or more candidates to represent the group, or one or more projects to be implemented, (2) coalition formation, where agents need to split into teams and have preferences over teams they can be part of, (3) fair allocation, i.e, distributing a set of items (or a single divisible item) among the agents in a fair and efficient way. We will consider both normative properties (such as axioms and fairness requirements) and algorithmic aspects of the proposed solutions (polynomial-time algorithms and NP-hardness results).

Synopsis

Part I: voting 

1 Voting Rules
An overview of single-winner, multiwinner and rank aggregation rules; basic axioms

2 Characterisations and Impossibility Results
Arrow's theorem (non-existence of a perfect rank aggregation rule), Gibbard-Satterthwaite theorem (non-existence of a non-manipulable voting rule), May's theorem (a characterisation of majority voting)

3 Complexity of Voting
Easy and hard single-winner rules, hardness in multiwinner (Chamberlin-Courant) and rank aggregation (Kemeny) settings. Complexity of manipulation.

4 Circumventing Hardness and Impossibility:
Single-peaked preferences Definition of single-peaked preferences, structure of majority preferences (and implications for Kemeny), median voting rule, dynamic programming algorithm for Chamberlin-Courant.

5 Algorithmics of Restricted Domains:

Single-crossing and group-separable preferences, preferences single-peaked on trees. Existence of Condorcet winners. Recognition algorithms for single-peaked ad single-crossing preferences.

6 Rationalisations of Voting Rules
Kemeny and Borda rules as maximum likelihood estimators. Distance rationalisation of voting rules.

7 Randomised Social Choice
Gibbard's theorem, maximal lotteries

8 Approval-based Multiwinner Voting.
Voting rules (including PAV, Phragmen and Method of Equal Shares) and representation axioms

9 Participatory Budgeting
Voting rules for budgeted setting, axioms, preference elicitation

Part II: Cooperative Games

10 Basics of Cooperative Games
Definition of a transferable utility cooperative game, payoffs, outcomes. Example games (weighted voting games, induced subgraph game, spanning tree games)

11 Stability in Cooperative Games
Notion of the core. Characterisations of the core in convex games and simple games

12 Shapley Value
Definition of Shapley value. Axiomatic characterisation. Computing Shapley value in induced subgraph games

13 Complexity in Cooperative Games
Complexity of the core in induced subgraph games, complexity of Shapley value in weighted voting games. Psudopolynomial algorithms for weighted voting games.

14 Stable Matching
Gale-Shapley algorithm and its extensions. Man-optimality and woman-pessimality.

Part III: Fair Allocation

15 Cake Cutting
Cake-cutting model. Proportionality, envy-freeness and equitability. Robertson-Webb model and query complexity. Moving knife and Even-Paz protocols for finding a proportional aallocation.

16 Cake Cutting Continued.
Envy-free allocation for 3 agents (Selfridge-Conway). Additional constraints: connectivity, truhfulness, welfare.

17 Fair Allocation of Indivisible Items
Proportionality, envy-freeness and maximin fare share concepts for indivisible items. Relaxations (EF1, EFX). Algorithms achieving EF1 (round robin, maximum Nash welfare).

18 Fair Allocation with Unit Demand.
Fairness in randomized settings. Serial dictatorship, top trading cycle, PS mechanism.

19 Rent Division.
Envy free rent division via Sperner's Lemma.

20 Hot Topics

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

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.