Computational Social Choice and Complexity Theory

Logic and Computation Courses

Introductory Course

Computational Social Choice and Complexity Theory,
Ronald de Haan (University of Amsterdam, The Netherlands)

This course will provide a rigorous introduction to the use of computational complexity methods in the research field of computational social choice. We will study the role of complexity theory in social choice by exploring several topics. We will cover various computational problems and issues in the setting of voting. We will also examine the framework of judgment aggregation where a group of agents form a collective opinion on logically interconnected issues. Finally, we will discuss the topic of finding stable matchings between individuals that have preferences over possible matching partners, and the algorithmic barriers that come up in this setting. During the course, we will introduce the framework of parameterized complexity theory, and discuss its role in the various social choice settings that we consider. We will start with basic results, and we will work up to current research in the field.