Algorithmic Game Theory (IN2239) SS21

THIS COURSE IS NOT OFFERED IN SS22, BUT THERE WILL BE A RETAKE EXAM IN SS22.

Lecture and Tutorials in SS2021

Important notice: All lectures and tutorials are fully online via Zoom.

Organization

  • Lecture: Tuesdays 14.00 - 16.00 (registration via TUMonline) via Zoom
  • Tutorials:  Mondays and Tuesdays (registration via TUMonline) via Zoom
  • SWS: 2+2
  • Credits: 5
  • Classification: "Algorithmen" (ALG)
  • Module description: IN2239
  • Language: English
  • Office hours: by arrangement
  • Exam: July, 27, 17.00 - 19.00
  • Exam format: Online at Moodle as graded online exercise (elektronische Übungsleistung)
  • Exam registration: TUMonline

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.

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)

Exercises

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. Points earned here can help improve the final grade, please see below for details.
  • H(omework)-exercises: Should be solved by yourself. Solution hints will be published online afterwards and will be complemented by explanatory videos. It is possible to hand in solutions for correction. We encourage you to join the virtual exercises classes to work on these problems with your fellow students and a tutor.
  • A(dvanced)-exercises: Similar to H-exercises, but usually these exercises introduce new concepts and work with advanced methods. Students are highly encouraged to work on these exercises, but are not expected to solve every step on their own.
  • 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 may be well beyond 40. Using the thresholds given 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 exam of the summer term 2020, grades of later exams are not affected.

The following grading scale is used to determine the G-grade:

  • [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,infinity) points: 1,0

Slides and exercise sheets

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

Exam (Elektronische Übungsleistung = graded online exercise)

The exam will be performed as a graded online exercise on Moodle. About two weeks before the exam, there will be a test run, where you can try out the format (interface, uploading answers, etc.).

All content from lecture and tutorials is relevant for the exam.

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

On G-exercises

The purpose of G-exercises is to provide additional insight into game-theoretic situations by experiencing them from the perspective of an actual decision maker. Bonus points are used to set up incentives according to the games' payoffs. You will quickly realize that there are no "correct" solutions (though there are sometimes particularly good/poor solutions). In some G-exercises, pairs of players may be randomly matched with each other to play a two-player game. It is therefore possible that two students who submit the same strategy receive different scores because their respective opponents submitted different strategies. This is in the nature of things and you need not worry about this too much. To a large extent, the G-grade is determined by the quizzes. G-exercises can be a lot of fun and we hope you enjoy playing the games.

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)
  • You might also consult this document by Itzhak Gilboa or this document by Walter Bossert (the latter 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 mathematical notions and proof techniques.