Schedule of Lectures

December 4th -8th, 2017

The schedule below is provided to share a rough layout of topics.

Please find the new schedule here (a downloadable PDF file) or on this Google Sheet.

Problem Sets.

Problem Set 1

Day 1:

Time Topic Materials
Lectur 1 [EE] Introduction to concepts in Computational Social Choice. Examples of voting rules (scoring rules, Kemeny, Dodgson, Copeland, Schulze, STV, etc). Axioms for voting rules. Basic impossibility results. The Condorcet paradox. available soon
Lecture 2: [EE] Maximum likelihood approach to voting. Jury theorems. Kemeny rule as the maximum likelihood estimator for Mallows noise model. Distance rationalizability approach to voting. available soon
Tutorial 1: [NM] Proof of Arrow’s theorem and a sketch for the Gibbard- Satterthwaite Theorem. available soon

Day 2:

Time Topic Materials
Lecture 3 [EE] Strategic Issues I. Manipulation and voting equilibria. Single-agent and coalitional manipulation; weighted vs unweighted elections. Introduction to the use of computational hardness as a barrier to strategic behaviour. The possible winner problem and its complexity. Equilibria of Plurality voting and equilibrium refinements. available soon
Lecture 4: [EE] Strategic Issues II. Election control and bribery. Forms of control: voter/candidate addition/deletion, partition. Constructive vs destructive control. An introduction to bribery models and an overview of their computational complexity. available soon
Tutorial 2: [NM] NP-hardness of manipulating Borda in the unweighted setting with two manipulators. available soon

Day 3:

Time Topic Materials
Lectur 5 [EE] Domain Restrictions I. Single-peaked profiles, single-crossing profiles. Transitivity of majority preferences and the median voter theorem. 1-Euclidean preferences. available soon
Lecture 6: [EE] Domain Restrictions II. Recognition algorithms for restricted domains; minor-based characterisations and connections to the consecutive 1s problem. Analogues of the single-peaked and single-crossing domain for approval preferences. Algorithmic results via structured linear programs. available soon
Tutorial 3: [EE] Profiles single-peaked on trees and circles. Exercises in showing relationships between specialized profiles in the context of approval ballots. Elicitation algorithms. available soon

Day 4:

Time Topic Materials
Lecture 7 [EE] Multiwinner voting rules for ranked ballots. Chamberlin-Courant and Monroe rules. Committee scoring rules. NP-hardness, and tractability on specialized domains. available soon
Lecture 8 [EE] Multiwinner voting rules for approval ballots. Justified representation axiom and its variants. Characterization of the PAV rule. Connections to apportionment. available soon
Tutorial 4 [NM] Minimax voting rule and the closest string problem. Parameterized algorithms and lower bounds. available soon

Day 5:

Time Topic Materials
Lecture 9 [EE] Hedonic games. An introduction to various stability concepts in the context of hedonic games. Complexity bounds. available soon
Lecture 10 [EE] Matching problems. Gale-Shapley algorithm for finding a stable matching and its extensions. available soon
Tutorial 5 [NM] Fair division algorithms. Problem solving session. available soon

a) 5 assignments will be given.
b) Every class will be transcribed by one of the students.