Algorithmic Game Theory 1+2 (Winter 2023/24)
Topical
- Logbook, with details about schedule and material.
- Part 1 ended with lecture 14 on Dec 7 and sheet 6. Part 2 started with lecture 15 on Dec 12 and sheet 7.
Organizational
- Lecturers: Prof. Dr. Martin Hoefer
- Exercises: Marco Schmalhofer, Lisa Wilhelmi
- LSF entries: Part 1, Part 2, Part 1+2
- Lectures:
Tue, 10:15 - 11:45h in Magnus-Hörsaal, Robert-Mayer-Str. 11-15
Thu, 10:15 - 11:45h in H16, Hörsaalgebäude - Exercises: Fri, 10:15 - 11:45h in SR 307, Robert-Mayer-Str. 11-15
Material
Slides and Notes
| Chapter | Updates | Lectures | |
|---|---|---|---|
| Organizational | Slides | 15.10.2023 | 1 |
| Part 1: | |||
| Strategic Games and Nash Equilibrium | Slides | 15.10.2023 | 1-3 |
| Pure Nash Equilibria | Slides | 25.10.2023 | 4-6 |
| Learning and Correlated Equilibria | Slides | 14.11.2023 | 7-9 |
| Prices of Anarchy and Stability | Slides | 27.11.2023 | 10-12 |
| Fair Division: Cake-Cutting | Notes | 22.02.2024 | 13-14 |
| Part 2: | |||
| Designing Incentive-Compatible Mechanisms | Slides | 14.12.2023 | 15-18 |
| Secretaries and Prophets | Slides | 16.01.2024 | 19-21 |
| Social Choice | Slides | 07.01.2024 | 22-25 |
| Fair Division: Indivisible Goods | Notes | 11.02.2024 | 26-27 |
Lecture Notes
German lecture notes from a previous version of this course are available here.Videos
Lectures are recorded by studiumdigitale and are published on this page (HRZ login).
Exercise Sheets
Weekly exercise sheets will be published here.
Your solutions must be submitted as a single PDF file via SAP.
You should have received a personalized URL via e-mail to upload your solution. If you have not received a personalized URL, please write an e-mail to Marco or Lisa.
Bonus points: one step if at least 2/3 of the overall points scored. To receive the bonus, at least one solution must be presented during an exercise session.
Part 1:
- Assignment 1. Issued: 24.10.2023. Due: 30.10.2023, 23:55. (TeX Code for Matrices.)
- Assignment 2. Issued: 31.10.2023. Due: 06.11.2023, 23:55. (TeX Code for Graph.)
- Assignment 3. Issued: 07.11.2023. Due: 13.11.2023, 23:55.
- Assignment 4 (Updated on 17 Nov 15:30). Issued: 14.11.2023. Due: 20.11.2023, 23:55.
- Assignment 5 (Updated on 24 Nov 16:20). Issued: 21.11.2023. Due: 27.11.2023, 23:55. (TeX Code for Matrix and Graphs.)
- Assignment 6. Issued: 28.11.2023. Due: 04.12.2023, 23:55.
Part 2:
- Assignment 7. Issued: 19.12.2023. Due: 08.01.2024, 23:55.
- Assignment 8. Issued: 09.01.2024. Due: 15.01.2024, 23:55.
- Assignment 9. Issued: 16.01.2024. Due: 22.01.2024, 23:55.
- Assignment 10. Issued: 23.01.2024. Due: 29.01.2024, 23:55.
- Assignment 11. Issued: 30.01.2024. Due: 05.02.2024, 23:55.
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
Directly related to the course material:
- [EK] Easley, Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Access here. - [NRTV] Nisan, Roughgarden Tardos, Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Non-printable PDF here. - [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. Access with Goethe University license here.
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...