Seminar Social Choice Theory (WS 2012/13)

Basic Information

Lecture time:	Wednesdays 14-16 (First meeting 17.10.12)
Lecture room:	023, Campus E 1.4
Lecturers:	Christine Rizkallah and Rob van Stee
Audience:	The seminar counts as computer science seminar (2 SWS, 7 CP). Talks should be given in English.
Credits:	You earn the usual 7 credit points for a seminar if you (i) give a 45 minute presentation of the paper given to you, and (ii) write short summaries (about one page) about four topics other than your own. Summaries should be handed in within one day after the topic is presented. They are meant to summarize the topic and not the presentation. If you present a paper you will summarize 4 book chapters and if you present a book chapter you will summarize 3 papers and a book chapter. The presentation needs to be discussed with us at least one week before your scheduled talk in the seminar: please make an appointment by mail. This means in particular that you should have your presentation READY one week in advance, so that you can give a practice talk and we may discuss it. If you want credit for the course, please register by sending a short mail.
Initial Material:	In this seminar we will discuss similar topics to the ones discussed in the following courses: Computational Social Choice and Social Choice Theory for Logicians

Description

Social choice theory is the study of mechanisms for collective decision making where preferences of individuals are aggregated to produce a social welfare function. This seminar will focus on classical results in the field of social choice theory. We will cover some impossibility theorems such as Arrow's impossibility theorem, Sen's impossibility theorem. We will also go through axiomatc characterizations of voting methods such as May's characterization of the majority rule and Young's characterization of scoring rules. Moreover, we will cover some voting paradoxes such as Condorcet's paradox, Anscombe's paradox, and the No-Show paradox. We will also discuss strategic manipulation where a voter can sometimes improve the outcome of an election for herself by misrepresenting her preferences the Gibbard-Satterthwaite theorem is a key result in this field.

Topics

The Axiomatic Method in Social Choice Theory (Part 1) (Section 2, pages 4-9) (Treated as Chapter)
The Axiomatic Method in Social Choice Theory (Part 2) (Section 2, pages 10-15) (Treated as Chapter)
Optimal Voting Rules (Treated as Chapter)
Social Choice in Combinatorial Domains (Section 4) (Treated as Chapter)
Judgement Aggregation (Section 5) (Treated as Chapter)
The Computational Difficulty of Manipulating an Election (Treated as Paper)
When are Elections with Few Candidates Hard to Manipulate? (Treated as Paper) (optional)

Cake Cutting Is Really Not a Piece of Cake (Treated as Paper)
Divorcing Made Easy (Treated as Paper)
On Maxsum Fair Cake Divisions (Treated as Paper)

House Allocation Problem and Stable Matchings (Subsections 10.3 and 10.4) (Treated as Chapter)
Truthful Assignment without Money (Treated as Paper)
Mechanism Design without Money via Stable Matching (Treated as Paper)

Automated Search for Impossibility Theorems (Treated as Paper)
Social Choice Theory in HOL (Treated as Paper) (optional)

Summary Groups

We strongly recommend you to use this template for your summaries.

G1. Frederik Wiehr, Alexander Scheer, and Tigran Mkrtchyan.
G2. Felix Kosmalla, Amrullokhuja Olimov, and Jonas Oberhauser.
G3. Tetiana Zinchenko, and Sanjar Karaev.
G4. Mark Simkin, Maximilian Harz, and Dominik Feld.

Schedule

Date	Speaker	Topic	Slides	Summaries	Practice Talk
Oct 17	Rob van Stee	Giving Scientific Talks	slides
Oct 31	Frederik Wiehr	The Axiomatic Method in Social Choice Theory (Part 1)	slides	G1, G2, G3, G4	Rob
Nov 7	Felix Kosmalla	The Axiomatic Method in Social Choice Theory (Part 2)	slides	G3, G4	Rob and Christine
Nov 14	Alexander Scheer	Optimal Voting Rules	slides	G3	Rob
Nov 21	Amrullokhuja Olimov	Social Choice in Combinatorial Domains	slides	G3	Christine
Nov 28	Tigran Mkrtchyan	Judgement Aggregation	slides	G4	Christine
Dec 5	Tetiana Zinchenko	The Computational Difficulty of Manipulating an Election	slides	G1	Christine
Dec 19	Mark Simkin	On Maxsum Fair Cake Divisions	slides	G2	Christine
Jan 16	Jonas Oberhauser	House Allocation Problem and Stable Matchings		G4	Christine
Jan 23	Maximilian Harz	Truthful Assignment without Money		G1, G2	Rob
Jan 30	Dominik Feld	Mechanism Design without Money via Stable Matching		G1, G2	Rob

More Courses of the Algorithms and Complexity Group