Seminar on Computational Social Choice
| Year | Semester | Date | Period | Language | In charge |
|---|---|---|---|---|---|
| 2016 | autumn | 08.09-15.12. | 1-2 | English | Matti Järvisalo |
Lectures
| Time | Room | Lecturer | Date |
|---|---|---|---|
| Thu 10-12 | C220 | Matti Järvisalo | 08.09.2016-08.09.2016 |
| Thu 10-12 | C220 | Matti Järvisalo | 03.11.2016-15.12.2016 |
General
The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the computational (algorithmic) aspects of collective decision making. The aim of this seminar is to give an overview of fundamental concepts and recent algorithmic advances in computational social choice research, based on the very recent Handbook of Computational Social Choice published in early 2016. Topics include (but are not restricted to) voting theory (such as the computational complexity of winner determination and manipulation in elections), fair allocation (such as algorithms for dividing divisible and indivisible goods), coalition formation (such as matching and hedonic games), and automated theorem discovery in computational social choice.
The seminar is intended for MSc students especially in the Algorithms, Data Analytics, and Machine Learning (ALKO) subprogramme, and also PhD students. A certain level of theoretical/mathematical maturity is expected from the participants.
Schedule (preliminary):
-
Introductory lecture and selection of seminar topics: September 8.
[introductory lecture slides] - Weekly seminar meetings during study period II (two presentations per week).
- Final deadline for seminar reports: December 18.
Completing the course
The course work consists of
- giving a 40 min presentation,
- writing a 10-15 page report, and
- acting as an opponent and giving feedback to another student
on a selected topic based on an individual chapter from the seminar textbook. You may also propose your own topic based on a recently published research article that falls within the topic of the seminar. In this case, please email the teacher with more details on the topic you are interested in.
Latex Template
The report should be formatted according to the general format (cover etc.) used on the Scientific Writing course, example layout
Using LaTeX is recommended. LaTeX-templates are available from http://www.cs.helsinki.fi/u/kurhila/tiki_k2007/coursedescription.html (See "Tools to work with").
Seminar Schedule
Updated Nov 17
| Date | Topic | Presenter | Opponent |
| Nov 3 |
Ch. 2-3 Ch. 5 |
Hyvärinen Berg |
Linkola Uusitalo |
| Nov 10 |
Ch. 6 |
Leinonen |
Sallinen |
| Nov 17 |
JAIR'16 Ch. 8 |
Niskanen Sallinen |
Karikoski Leinonen |
| Nov 24 |
Ch. 10 Ch. 17 |
Nikkari Uusitalo |
Niskanen - Berg |
| Dec 1 |
Ch. 13 Ch. 14 |
Karikoski Zosa |
- Zosa Lin |
| Dec 8 | - | No seminar | |
| Dec 15 |
Ch. 16 Ch. 15 |
Lin Linkola |
Hyvärinen Nikkari |
Literature and material
The individual topics for each student are chosen from chapters in the book Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (editors), Cambridge University Press, 2016.
Chapters of the handbook will be made available to the attending students; there is no need to purchase the handbook. Please contact the lecturer if you want to view the handbook in advance.
Table of contents
1. Introduction to computational social choice (during the introductory lecture in period I)
Part I. Voting:
2. Introduction to the theory of voting [topic reserved / Hyvärinen]
3. Tournament solutions [topic reserved / Hyvärinen]
4. Weighted tournament solutions
5. Dodgson's rule and Young's rule [topic reserved / Berg]
6. Barriers to manipulation in voting [topic reserved / Leinonen]
7. Control and bribery in voting [topic reserved / Hannikainen]
8. Rationalizations of voting rules [topic reserved / Sallinen]
9. Voting in combinatorial domains
10. Incomplete information and communication in voting [topic reserved / Nikkari]
Part II. Fair Allocation:
11. Introduction to the theory of fair allocation [topic reserved / Viinikka]
12. Fair allocation of indivisible goods [topic reserved / Mertanen]
13. Cake cutting algorithms [topic reserved / Karikoski]
Part III. Coalition Formation:
14. Matching under preferences [topic reserved / Zosa]
15. Hedonic games [topic reserved / Linkola]
16. Weighted voting games [topic reserved / Lin]
Part IV. Additional Topics:
17. Judgment aggregation [topic reserved / Uusitalo]
18. The axiomatic approach and the internet
19. Knockout tournaments
Topics outside the handbook:
[JAIR'16] Felix Brandt, Christian Geist: Finding Strategyproof Social Choice Functions via SAT Solving. Journal of Artificial Intelligence Research 55:565-602 (2016) pdf [topic reserved / Niskanen]