This is an archived website. The group moved to RWTH Aachen University.

Algorithmic Game Theory 1+2 (Winter 2019/20)


Topical


Organizational


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:


Part 2:


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:


Many textbooks cover background and context in game theory, e.g.,