Computational Social Choice and Complexity Theory
ESSLLI—August 13–17, 2018

Lecturer: Ronald de Haan (me@ronalddehaan.eu)

 

 

Day 1: Introduction, Voting, Complexity

• What is computational social choice?
• Voting theory, voting rules
• Computational complexity theory, NP-hardness
• Complexity of winner determination for voting rules

Material:

• Slides
• Video about voting paradoxes.
• Online tool Democratix to compute the winner of elections.
• Example elections from the slides in PrefLib election format:
  • Example 1
  • Example 2
  • Example 3
• Reading: Sections 1.1, 1.2, 2.2, 2.4 and 2.7 of [3], Chapter 1 of [2], Chapter 2 of [1].

Day 2: Parameterized Complexity, Strategic Behavior in Voting

• Parameterized complexity theory
• Strategic manipulation in voting
• The Gibbard-Satterthwaite Theorem
• Complexity of strategic manipulation
• Caveats for intractability results

Material:

• Slides
• Example elections from the slides in PrefLib election format:
  • Example 4
• Reading: Section 11.1 of [4], Sections 1, 2 and 5 of [6], Sections 2.8, 6.1, 6.2 and 6.4 of [3].

Day 3: Bribery in Voting, Domain Restrictions

• Bribery in voting
• Domain restrictions
• (Nearly) single-peaked preferences
• Black's Theorem

Material:

• Slides
• Example elections from the slides in PrefLib election format:
  • Example 5
  • Example 6
  • Example 7
  • Example 8
• Online tool Pnyx to hold different types of elections.
• Example election that you can vote in.
• Reading: Sections 2.9, 7.4 and 7.5 of [3].

Day 4: Judgment Aggregation

• Judgment Aggregation (JA)
• Simulating Voting in JA
• Complexity Issues in the Model of JA
• Using Logic Fragments

Material:

• Slides
• Reading: Chapter 17 of [3], Chapter 6 of [5].

Day 5: Stable Matching

• Stable Matching
• The Gale-Shapley Algorithm
• Strategizing
• Variants of Matching Problems

Material:

• Slides
• A story about strategizing and fairness in school matching in Amsterdam.
• Reading: Sections 14.1 and 14.2 of [3].

 

Literature

[1] Computational Complexity: A Modern Approach. Sanjeev Arora and Boaz Barak, 2009.
[2] Computers and Intractability: A Guide to the Theory of NP-completeness. Michael Garey and David Johnson, 1979.
[3] Handbook of Computational Social Choice. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel Procaccia (eds), 2016.
[4] Trends in Computational Social Choice. Ulle Endriss (ed), 2017.
[5] Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Jörg Rothe (ed), 2016.
[6] Studies in Computational Aspects of Voting. Nadja Betzler, Robert Bredereck, Jiehua Chen, and Rolf Niedermeier. In: The Multivariate Algorithmic Revolution and Beyond. Hans Bodlaender, Rod Downey, Fedor Fomin, and Dániel Marx (eds), 2012.
[7] P, NP, and NP-Completeness: The Basics of Computational Complexity. Oded Goldreich, 2010.