# Computational Social Choice and Complexity TheoryESSLLI—August 13–17, 2018

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

If you are interested in a PhD or PostDoc position in Computational Social Choice at the University of Amsterdam, talk to me!

## 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
• Online tool Democratix to compute the winner of elections.
• Example elections from the slides in PrefLib election format:
• 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:
• 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:

## 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.