DSS
Decision Sciences & Systems
Technical University of Munich
 

Prof. Dr. Felix BrandtM.Sc. Johannes Hofbauer and Dipl.-Math. Hans Georg Seedig

Lecture and Tutorials in SS2014

Algorithmic Game Theory (IN2239)

Organization

The course will be offered in condensed form, i.e., there are two lectures and two tutorials per week until the end of May. All lectures and tutorials will take place in roomid=3.5.06@8102" data-mce-href="https://portal.mytum.de/campus/roomfinder/roomfinder_viewmap?mapid=182&roomid=3.5.06@8102">Seminarraum 3 (3.5.06) in Garching-Hochbrück.

The course will start with a lecture.

  • Lecture: Mondays 16.15 - 17.45 and Thursdays 16.15 - 17.45 (starting on April  7th, 2014)
  • Tutorial: Mondays 14.15 - 15.45 and Thursdays 14.15 - 15.45 (starting on April 10th, 2014)
  • SWS: 2+2
  • Credits: 5
  • Classification: "Formale Methoden und ihre Anwendungen" (FMA)
  • Module decription: IN2239
  • Language: English
  • Office hours: by arrangement
  • Exam: May 28th, 2014, 18.00 - 20.00 in Interimshörsaal 1
  • Exam registration: via TUMonline between May 5th and May 27th, 2014 (if you are not registered yet, write an email to This email address is being protected from spambots. You need JavaScript enabled to view it.)
 
IMPORTANT NOTICE: This is a theory course. It is expected that participants are familiar with formal mathematics and standard proof techniques. Additionally, basic knowledge about NP-completeness is useful (e.g., Module IN0011).

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

Exercises

There will be one exercise sheet after every lecture containing G-, H- and T-exercises.
 
  • G(ame)-exercises: Students' answers have to be submitted midnight before the next tutorial. Results will be presented in the respective tutorial. Points earned here can improve the final grade according to the following method:
    • Students who passed the exam will be ranked according to their accumulated scores from G exercises.
    • All students in the upper half of this ranking will get a 0.3 bonus on their final grade (e.g., the grade 2.7 would then be turned into 2.4.)
  • 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. Students are not expected to prepare them beforehand.

Slides and exercise sheets

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

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
 

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.

Literature

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)

Contact

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

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