December 4th -8th, 2017
The schedule below is provided to share a rough layout of topics.
|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|
|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|
|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|
|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|
|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.