Decision Sciences & Systems
Technical University of Munich

Prof. Dr. Felix Brandt, M.Sc. Johannes Hofbauer, and M.Sc. (hons) Paul Stursberg

Lecture and Tutorials in SS2015

Algorithmic Game Theory (IN2239)


  • Lecture: Tuesdays 12.15 - 13.45, MI HS 2 (starting on April 14th, 2015)
  • Tutorials: (starting on April 20th or 21st, 2015, respectively; registration opens on April 14th, 2015, 20.00 via TUMonline)
    • Group 1: Mondays 10.15 - 11.45, 01.10.011
    • Group 2: Mondays 18.00 - 19.30, 01.10.011
    • Group 3: Tuesdays 10.15 - 11.45, 01.10.011
    • Group 4: Mondays 16.15 - 17.45, 03.13.010 (due to high demand)
  • SWS: 2+2
  • Credits: 5
  • Classification: "Formale Methoden und ihre Anwendungen" (FMA)
  • Module description: IN2239
  • Language: English
  • Office hours: Thursdays 15.00 - 16.00 or by arrangement
  • Exam: Wednesday, July 15th, 18.00 - 20.00, MW2001
  • Exam registration: May 18th - June 30th via TUMonline
  • Resit exam: Tuesday, October 6th, 14.30 - 16.30, InterimsHS 1
  • Resit exam registration: August 31st - September 14th via TUMonline
IMPORTANT NOTICE: This is a theory course. It is expected that participants are familiar with formal mathematics, concepts such as continuity or convexity, and standard proof techniques. Additionally, basic knowledge about NP-completeness and linear programming is useful.


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


There will be one exercise sheet after every lecture containing G-, H- and T-exercises. Additional Q-exercises will be available in Moodle.
  • G(ame)-exercises: Students' answers have to be submitted by midnight (i.e., 23.59) each Saturday before the next tutorial. Results will be presented in the subsequent tutorial. Points earned here can help improve the final grade, please see below for details.
  • H(omework)-exercises: Should be prepared before the tutorial and can be handed in on a voluntary basis. Will be discussed in detail in the tutorial. Solution hints will be published online afterwards.
  • T(utor)-exercises: Will be presented by the tutor in the tutorial. Solution hints will be published online afterwards. Students are not expected to prepare them beforehand.
  • Q(uiz)-exercises: Will be made available and can only be answered online in Moodle once every three to four weeks. Points earned here can help improve the final grade, please see below for details.
Grade Bonus:
  • At the end of the semester, the points acquired in all G- and Q-exercises will be summed up to form a final score, the theoretical maximum will lie somewhere around 45. Using the same thresholds as for the exam (see below), this score will be converted to a so-called G-grade.
  • Based on APSO Section 6 Subsection 5 (2), this G-grade can only be used to improve the grade of a passed exam, i.e., if you pass the exam and your G-grade is better than your exam grade, then your final grade will be computed according to the following formula:
     final_grade = 0.8 * exam_grade + 0.2 * G-grade
  • Note that the bonus only applies to the grades of passed exams.
  • Note that grades can only be improved by the bonus, never worsened.
  • Note that the bonus only applies to the first exam of the summer term 2015, the grades of later exams are not affected.

Slides and exercise sheets

Lecture slides, exercise sheets, and solution hints will only be available in Moodle.


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

The only resource you may use during the exam is one hand-written sheet of DIN A4 paper that you prepared yourself (you may write on both sides). In particular, electronic devices, books, photocopies, and printouts are disallowed. All content from lecture and tutorials is relevant for the exam. Please remember to bring your student id (or an equivalent photo id).

You will be notified by email when the grades are available in TUMonline.

A second exam will be offered at the end of the semester break.


This course is not based on a textbook. The literature listed below can be helpful to get a better understanding of some concepts, but the notation and terminology might deviate from the lecture.

Books (available online for free):

Other recommended books:

  • Hans Peters: Game Theory - A Multi-leveled Approach (Springer, 2008)
  • Michael Maschler, Eilon Solan, and Shmuel Zamir: Game Theory (Cambridge University Press, 2013)
  • 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)
Some of the mathematical background required is nicely covered in this document by Itzhak Gilboa. You might also consult this document by Walter Bossert (but it covers much more than we need in this course). Michael Sipser's book "An Introduction to the Theory of Computation" also contains a good introduction to basic mathmatical notions and proof techniques.


Johannes Hofbauer

Decision Sciences & Systems (DSS), Department of Informatics (I18), Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany
©2002-2017 DSS All Rights Reserved
Impressum, Privacy Policy, Copyright Information and Disclaimer