Prof. Felix Brandt

Prof. Dr. Felix Brandt
Dr. Paul Harrenstein, Dipl.-Math. Hans Georg Seedig

Lecture and Tutorials in SS 2011

Algorithmic Game Theory (IN2239)

Please contact us if you want to take an oral exam in the winter semester. The tentative date for these exams is Friday, October 21st.

Organization

Lecture: Tuesdays, 14.15 - 15.45, Room 01.10.011
Tutorial: Mondays, 16.15 - 17.45, Room 01.10.011
SWS: 2+2
Credits: 5
Classification: "Formale Methoden und ihre Anwendungen" (FMA)
Module decription: IN2239
Language: English
Exam: July 26th 2011, 16.00 - 18.00, Room MW 2050
Exam registration deadline: June 30th 2011

Content

Algorithmic game theory is a young research area at the intersection of theoretical computer science, mathematics, and economics that deals with the optimal strategic behavior in interactive situations. In this course, particular attention will be paid to algorithmic aspects of game-theoretic solution concepts such as Nash equilibrium and the general design of economic mechanisms. The concrete design of specific mechanisms for resource allocation (auctions) and collective choice (voting rules) is covered by the courses Auction Theory and Market Design and Computational Social Choice, respectively.

Tentative list of topics:

Utility theory (preference relations, expected utility, von Neumann-Morgenstern preferences)
Normal-form games (prisoner's dilemma, Pareto-dominance, dominance)
Nash equilibrium (pure and mixed equilibria, axiomatization)
Computing equilibria (hardness, support enumeration, zero-sum games, minimax theorem, linear programming)
Alternative solution concepts (equilibrium refinements, Shapley's saddle)
Concise representations (graphical games, anonymous games)
Extensive-form games (subgame-perfect equilibria)
Mechanism design (Gibbard-Satterthwaite impossibility, Nash implementation, quasi-linear preferences, VCG mechanism)
Cooperative games (Shapley value, coalition formation)
Stable matchings (Gale-Shapley algorithm, hedonic games)

Exercises

Exercises are voluntary, but highly recommended. Each exercise sheet will contain tutorial exercises (T) and homework exercises (H). Bonus points for correct homework exercises will be taken into account when grading the final exam. Bonus points will be awarded as follows:

at least 40 per cent of (H) exercises solved: 1 point
at least 60 per cent of (H) exercises solved: 2 points
at least 80 per cent of (H) exercises solved: 3 points

Exercise sheets will be made available each Wednesday. They are due the following Monday at 4.15 pm (before the tutorial begins).

Exam

There will be a written exam at the end of the semester, which will be graded according to the following grading scale:

[0,5) points: 5,0
[5,11) points: 4,7
[11,17) points: 4,3
[17,19] points: 4,0
(19,22] points: 3,7
(22,24] points: 3,3
(24,26] points: 3,0
(26,28] points: 2,7
(28,30] points: 2,3
(30,32] points: 2,0
(32,34] points: 1,7
(34,36] points: 1,3
(36,40] points: 1,0

Literature

Available online:

Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani: Algorithmic Game Theory (Cambridge University Press, 2007)
Martin Osborne and Ariel Rubinstein: A Course in Game Theory (MIT Press, 1994)
Robert Aumann: Game Theory, in J. Eatwell, M. Milgate, and P. Newman: The New Palgrave, A Dictionary of Economics, Vol. 2 (MacMillan, 1987)
Yoav Shoham, Kevin Leyton-Brown: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge University Press, 2009)

Books:

Hans Peters: Game Theory - A Multi-leveled Approach (Springer, 2008)
Roger Myerson: Game Theory - Analysis of Conflict (Harvard University Press, 1991)
Drew Fudenberg and Jean Tirole: Game Theory (MIT Press, 1991)
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green: Microeconomic Theory (Oxford University Press, 1995)
D. Austen-Smith and J. Banks: Positive Political Theory II: Strategy & Structure (University of Michigan Press, 2005)

Contact

Hans Georg Seedig
Room 01.10.040
Phone: 289-17537
E-Mail: seedighin.tum.de