Prof. Dr. Felix Brandt, M.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.)

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

### 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

#### Books (available online for free):

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

**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: agtin.tum.de