Computational Social Choice

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 week has no tutorial
  • except on official holidays
     
• Topics:
  • Introduction
  • Voting systems
  • Structured preferences
  • Participatory
  • Judgement aggregation
  • Tournament solutions
  • Hedonic games
  • Multiagent resource allocation
     
• 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]
   
• Literatur: 
  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.