Computational Social Choice (COMSOC)

COMSOC represents a burgeoning research domain situated at the confluence of artificial intelligence, theoretical computer science, and theoretical economic theory. It focuses primarily on automating the process of optimal collective decision-making through algorithmic methodologies. This course will focus on the following questions: (1) How do different decision-making rules function? (2) What are the key considerations and criteria in designing these decision-making rules? (3) What are the significant combinatorial problems associated with these rules, and are there efficient algorithms to solve them?

Time and Date

• Lecture: every Tuesday (12:00-14:00, Room 003, Building E1 3)
• Tutorial: every Friday (14:00-16:00, Room 003, Building E1 3)
• The first lecture will be on 15.10.2024
• The first week has no tutorial
• except on official holidays

Exams

Endterm: Tuesday, Febraruy 11th 2025,  13:00--15:00   HS 001, HS 003 in building E1 3.

Re-Exam: Tuesday, March 11th 2025,  10:00--12:00   HS 003 in building E1 3.

Topics

• Introduction
• Voting systems
• Structured preferences
• Participatory
• Judgement aggregation
• Tournament solutions
• Hedonic games
• Multiagent resource allocation

Problem Sets

• Problem sets are distributed every Wednesday afternoon.
• You may work in groups of up to three people. Only one submission is required per group. Ensure that all group members' names and student IDs are listed on the first page of the submission.
• Submissions can be made electronically in PDF or Word format, or as handwritten work.
• For handwritten submissions, you may use the paper provided with the problem set or any blank sheets of your own.
• Solutions can be submitted via the system, sent to my email, handed to me in person during the lecture, or delivered to my office.

Prerequisite

The course requires basic knowledge in computational complexity (P, NP, NP-hardness) and parameterized complexity. Accessible references for a quick overview of these concepts are [1,2].

Literature

The course will not adhere to a specific textbook. The following literature will serve as valuable reference material.

1. Tovey, C. A. (2002): Tutorial on Computational Complexity. Interfaces 32: 30–61.
2. Downey, R. (2012): A Parameterized Complexity Tutorial. in LATA.
3. Cygan, M., et al. (2015): Parameterized Algorithms. Springer.
4. Brandt, F., et al. (2016): Handbook of Computational Social Choice. Cambridge University Press.
5. Elkind, E., et al. (2022): Preference Restrictions in Computational Social Choice: A Survey.
6. Elkind, E., et al. (2017): Properties of Multiwinner Voting Rules. Soc. Choice Welf. 48(3): 599–632. 
7. Yang, Y. (2019): On the Tree Representations of Dichotomous Preferences. in IJCAI: 644-650.
8. Lackner, M., Skowron, P. (2023): Multi-Winner Voting with Approval. Springer-Verlag.
9. Aziz, H., et al. (2019): Fractional Hedonic Games. ACM Trans. Economics and Comput. 7(2): 6:1-6:29.