Algorithmic Game Theory 1+2 (Winter 2019/20)
Topical
- Logbook, with details about schedule and material.
- Part 1 ended on Nov 28. Part 2 started on Dec 5.
Organizational
- Prof. Dr. Martin Hoefer, Dr. Daniel Schmand
- LSF entries: Part 1, Part 2, Part 1+2
- Lectures: Tue/Thu, 10:15 - 11:45h in H9, Hörsaalgebäude
- Exercises: Fri, 12:15 - 13:45h in SR 11, Robert-Mayer-Str. 11-15
Material
Slides and Notes
| Chapter | Updates | Lectures | |
|---|---|---|---|
| Organizational | Slides | 14.10.2019 | |
| Part 1: | |||
| Strategic Games and Nash Equilibrium | Slides | 17.10.2019 | 15.10. - 22.10. |
| Pure Nash Equilibria | Slides | 15.11.2019 | 24.10. - 05.11. |
| Weighted Congestion Games | Notes | 15.11.2019 | 31.10. |
| Learning and Correlated Equilibria | Slides | 14.11.2019 | 07.11. - 14.11. |
| Prices of Anarchy and Stability | Slides | 29.11.2019 | 19.11. - 26.11. |
| Temporal Congestion Games | Notes | 29.11.2019 | 26.11. - 28.11. |
| Part 2: | |||
| Designing Incentive-Compatible Mechanisms | Slides | 17.12.2019 | 05.12. - 17.12. |
| Social Choice | Slides | 22.01.2020 | 14.01. - 23.01. |
| Secretaries and Prophets | Slides | 06.02.2020 | 28.01. - 06.02. |
| Credit Networks | Notes | 16.02.2020 | 11.02. |
| Additional Material: Credit Networks Slides | Slides | 16.02.2020 | 11.02. |
Lecture Notes
In German - most recent update on 29 Nov 2019.Videos
Available here (restricted access)
Exercise Sheets
Part 1:
- Sheet 1, published 22.10.2019. Due: 29.10.2019, 10:15.
- Sheet 2, Example File 1, Example File 2, published 28.10.2019. Due: 05.11.2019, 10:15.
- Sheet 3, published 05.11.2019. Due: 12.11.2019, 10:15.
- Sheet 4, published 12.11.2019. Due: 19.11.2019, 10:15.
- Sheet 5, published 19.11.2019. Due: 26.11.2019, 10:15.
- Sheet 6, published 26.11.2019. Due: 03.12.2019, 10:15.
- Sheet 7, published 29.11.2019. Due: 10.12.2019, 10:15.
Part 2:
- Sheet 8, published 17.12.2019. Due: 14.01.2020, 10:15.
- Sheet 9, published 19.12.2019. Due: 21.01.2020, 10:15.
- Sheet 10, published 21.01.2020. Due: 28.01.2020, 10:15.
- Sheet 11, published 27.01.2020. Due: 04.02.2020, 10:15. Sample input/output files can be found here.
- Sheet 12, published 03.02.2020. Due: 11.02.2020, 10:15.
Content
The course provides an introduction to theoretical and algorithmic foundations of computer systems that involve strategic and economic interaction of rational agents. These systems arise frequently in modern computer networks -- service providers strive to route packets as quickly or cheap as possible, in cloud computing the resources (such as computing time or memory) are shared, rented or sold, advertisers want to place their ads as prominently as possible and pay as little as possible, etc. The business model of many companies relies on trade and marketing in computational markets on the Internet.
In algorithmic game theory we design and analyze algorithms for systems with interaction of many rational agents. These algorithms search for optimal strategies for single users, or they try to optimize performance for the system while addressing strategic behavior of users. The goals are a characterization of incentives, as well as provable bounds on running time and solution quality for optimization algorithms. In the course, we will introduce basic ideas from game theory and combine them with techniques from approximation algorithms, distributed computing, and complexity theory.
Literature
Direct relation to the course material:
- [EK] Easley, Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Zugriff hier. - [NRTV] Nisan, Roughgarden Tardos, Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Non-printable PDF hier. - [R] Roughgarden. Twenty Lectures in Algorithmic Game Theory. Cambridge University Press, 2016.
- [RBLR] Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. Spektrum Verlag, 2012.
Zugriff mit Lizenz hier.
Many textbooks cover background and context in game theory, e.g.,
- [M] Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
- [O] Owen. Game Theory. Academic Press, 2001.
- [OR] Osborne, Runbinstein. A Course in Game Theory. MIT Press, 1995.
- etc...