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 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)

• 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)

• 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)

• 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)

Other resources

• Feedback guidelines (1) (2) [in addition to what is presented during the first meeting]

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.

Contact

Florian Brandl
Christian Geist
Johannes Hofbauer