News

Problem set 7 handed out

Written on 21.12.24 by Yongjie Yang

Dear all, Problem Set 7 has just been distributed.

Best regards

Written on 19.12.24 by Yongjie Yang

Dear All,

I hope you are doing well.

As many of you have started traveling, we will not have a tutorial this week. Our next lecture is scheduled for Tuesday, 7th January 2025, and the next tutorial will take place on Friday, 10th January 2025.

Within the next day or two, I will upload the… Read more

Dear All,

I hope you are doing well.

Within the next day or two, I will upload the following materials:

(1) Slides for this Tuesday’s lecture
(2) The solution to the previous problem set
(3) The next problem set

Please review these materials and check your solutions independently. If you have any questions, do not hesitate to email me.

Additionally, I’d like to highlight a correction regarding Lecture 7: On Page 36 of the slides, it states that the core computation for the enemy-oriented HD game is polynomial-time solvable (without a proof). This statement is incorrect. The problem is actually more complex than NP-hard. I will upload the corrected slides shortly.

Finally, I wish all of you a Merry Christmas and a Happy New Year!

Best regards,

Yongjie Yang

Written on 08.12.24 by Yongjie Yang

Dear Students,

If you have decided to drop the lecture, please remember to complete the deregistration process.

Best Regards,

Notes on Problem Set 5

Written on 08.12.24 by Yongjie Yang

Dear All,

Please take note of the following updates regarding Problem Set 5:

- In Problem 6, in addition to solving the current problem, you should also analyze the complexity of the same problem under the condition that $|P|\geq k$.

- In Problem 4, we assume that the costs of all projects… Read more

Dear All,

Please take note of the following updates regarding Problem Set 5:

- In Problem 6, in addition to solving the current problem, you should also analyze the complexity of the same problem under the condition that $|P|\geq k$.

- In Problem 4, we assume that the costs of all projects are positive integers.

- Deadline: The submission deadline is on Wednesday, December 11, 2024.

The updated problem set has been uploaded.

Best regards,

Problem set 6 distributed

Written on 05.12.24 by Yongjie Yang

Dear all,

Problem 6 has just been handed out. The deadline for submission is December 17, 2024.

Best regards,

Yongjie Yang

Problem Set 5 handed out

Written on 29.11.24 by Yongjie Yang

Dear all,

Problem 5 has just been handed out. The deadline for submission is December 10, 2024.

Best regards,

Yongjie Yang

Cancellation of Tomorrow's Lecture

Written on 18.11.24 by Yongjie Yang

Dear all,

Unfortunately, I need to cancel tomorrow's lecture as I have a heavy flu. I apologize for the inconvenience. Wishing you all a great week, and I’ll see you on Friday!

Best regards,

Yognjie Yang

solution to problem set 2 uploaded

Written on 17.11.24 by Yongjie Yang

Dear all, the solution to Problem Set 2 has uploaded.

Best,

Problem set 4 handed out

Written on 17.11.24 by Yongjie Yang

Dear all,

The fourth problem set has been distributed.

The submission deadline is **November 27, 2024**.

Best regards,

Yongjie Yang

problem set 3 and solution to problem set 1

Written on 08.11.24 by Yongjie Yang

Dear all, Problem Set 3 and the solutions to problem set 1 have been uploaded.

best,

problem set 2

Written on 31.10.24 by Yongjie Yang

Dear all,

The second problem set has been handed out. The submission deadline is November 12, 2024.

Best regards,

Problem Set 1

Written on 24.10.24 (last change on 24.10.24) by Yongjie Yang

Dear all,

The first problem set has been handed out. The submission deadline is November 5, 2024.

Best regards,

slides uploaded

Written on 15.10.24 by Yongjie Yang

Dear all, the slides for the first lecture have been uploaded.

The first lecture will take place on October 15 (Tuesday), HS 003

Written on 14.10.24 by Yongjie Yang

looking forward to seeing you

Show all

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.

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