Florian Brandl, Christian Geist, Johannes Hofbauer, and Prof. Dr. Felix Brandt
Seminar WS 2015/2016
Computational Social Choice
Content
Social choice theory is the field that studies the aggregation of individual preferences towards a collective choice. This seminar is based on a brand-new book on computational social choice, which will appear later this year and which will be available for download after the overview meeting. The book is divided into four parts that correspond to three major focus areas of computational social choice, plus a part for additional topics.
Part 1: Voting. This part will consist of roughly half the book, and will cover work on computational aspects of voting, including an introduction to different families of voting rules and the computational complexity of computing the winners; the computational complexity of manipulation in elections, and related strategic behavior; the alternative computational approaches that were studied for the analysis of voting rules, such as communication complexity; and voting with rich combinatorial preferences.
Part 2: Fair division. Computational fair division is a subfield of computational social choice that deals with allocating goods to individuals with heterogeneous preferences in a socially desirable way. We will make the distinction between divisible and indivisible goods. The corresponding chapters will focus on issues related to complexity and optimization.
Part 3: Coalition formation. A third subfield of computational social choice deals with different interpretations of the process of coalition formation when players have preferences over different coalitions. This includes matching (to form coalitions of size two), hedonic games (where coalitions are created based on the preferences of individuals), and weighted voting games (where coalitions emerge to achieve some goal, such as passing a bill in parliament).
Part 4: Additional topics. This part will include topics that have been studied by the computational social choice community, but did not find a home in previous parts: judgement aggregation, ranking systems, and knockout tournaments.
For a brief and general introduction to computational social choice see, e.g., here.
Registration (*please read carefully*)
Seats are split up between students from computer science and students from other programs. All interested students have to attend the overview meeting and send an application by email briefly describing their background (including study program, current semester, previous relevant courses) and motivation (up to 250 words) as well as 2-5 book chapters they are interested in. Deadline for applications: July 8, 2015 (11:59pm). Students from computer science additionally have to use the matching system for indication of interest. Notifications will be sent out on July 10 (mathematics) and July 27 (computer science) and include assignment of book chapters and supervisors. Registration in TUMonline will be taken care of by the lecturers; no further action is required.
Time and venue
Overview (Vorbesprechung):
- Monday, July 6, 14.00 - 15.00, room 01.10.011
First meeting:
- Tuesday, October 20, 14.00 - 16.00, room 01.10.033
Talks:
- Tuesday, November 10, 14.00 - 17.00, room 01.10.033
- Talk 1
Speaker: Thiemo
Session chair: Christian B.
Chapter 2: Introduction to the Theory of Voting (Zwicker)
- Talk 1
- Talk 2
Speaker: Christian Gr.
Session chair: Gregor Sc.
Chapter 3: Tournament Solutions (Brandt, Brill, and Harrenstein)
- Tuesday, November 17, 14.00 - 17.00, room 01.10.033
- Talk 3
Speaker: Quentin
Session chair: David
Chapter 4: Weighted Tournament Solutions (Fischer, Hudry, and Niedermeier) - Talk 4
Speaker: Gabriel Sebastian
Session chair: Maximilian
Chapter 12: Fair Allocation of Indivisible Goods (Bouveret, Chevaleyre, and Maudet)
- Talk 3
- Tuesday, November 24, 14.00 - 17.00, room 01.10.033
- Talk 5
Speaker: Matthias
Session chair: Thiemo
Chapter 13: Cake Cutting Algorithms (Procaccia) - Talk 6
Speaker: Gregor Se.
Session chair: Christian Gr.
Chapter 14: Matching under Preferences (Klaus, Manlove, and Rossi)
- Talk 5
- Tuesday, December 1, 14.00 - 17.00, room 01.10.033
- Talk 7
Speaker: Christian B.
Session chair: Quentin
Chapter 15: Hedonic Games (Aziz and Savani) - Talk 8
Speaker: Gregor Sc.
Session chair: Gabriel Sebastian
Chapter 16: Weighted Voting Games (Chalkiadakis and Wooldridge)
- Talk 7
- Tuesday, December 8, 14.00 - 17.00, room 01.10.033
- Talk 9
Speaker: David
Session chair: Matthias
Chapter 17: Judgement Aggregation (Endriss) - Talk 10
Speaker: Maximilian
Session chair: Gregor Se.
Chapter 19: Knockout Tournaments (Vassilevska-Williams)
- Talk 9
Other resources
Practicalities
-
The seminar will be held in English (i.e., all presentations will have to be in English, too)
Module-Codes
-
IN2107 (Master-Seminar in the Master program Informatik)
-
IN0014 (Seminar in the Bachelor programs Informatik, Wirtschaftsinformatik)
-
For all other programs: Please check first whether this seminar fits in your curriculum. For example, mathematics students should find it listed as a mathematics seminar, too.