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

Algorithmic Game Theory 1+2 (Winter 2022/23)


Topical

Organizational


Material

Slides and Notes

Chapter Updates Lectures
Organizational Slides 18.10.2022 1
Part 1:
Strategic Games and Nash Equilibrium Slides 18.10.2022 1-3
Pure Nash Equilibria Slides 16.11.2022 4-8
Learning and Correlated Equilibria Slides 23.11.2022 8-10
Prices of Anarchy and Stability Slides 24.11.2022 11-13
Part 2:
Designing Incentive-Compatible Mechanisms Slides 09.12.2022 14-17
Social Choice Slides 10.01.2023 18-21
Fair Division: Cake-Cutting Notes 26.01.2023 22-23
Fair Division: Indivisible Goods Notes 02.02.2023 24-25
Hedonic Games Notes 07.02.2023 26

Lecture Notes

German lecture notes from a previous version of this course are available here.

Videos

Lectures will be recorded by studiumdigitale and made available here (access via HRZ login).


Exercise Sheets

Weekly exercise sheets will be published here. Your solutions must be submitted as a single PDF file via SAP.
You need to sign up first: Please send an Email to Conrad Schecker with your full name, your matriculation number and your HRZ mail address.

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

Directly related to the course material:


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