This course is taught in English. This course is regularly offered every summer semester.

This course was offered in the summer terms from 2020 to 2023.

Link to StudIP course page

Link to TUNE course page

Description

Algorithmic game theory is a topic at the intersection of economics and computation. It deals with analyzing the behavior and interactions of strategic agents, who often try to maximize their incentives. The environment in which those agents interact is referred to as a game. We wish to understand if the agents can reach an "equilibrium", or steady state of the game, in which agents have no incentive to deviate from their chosen strategies. The algorithmic part is to design efficient methods to find equilibria in games, and to make recommendations to the agents so that they can quickly reach a state of personal satisfaction.

We will also study mechanism design. In mechanism design, we wish to design markets and auctions and give strategic options to agents, so that they have an incentive to act rationally. We also wish to design the markets and auctions so that they are efficient, in the sense that all goods are cleared and agents do not overpay for the goods which they acquire.

ECTS-Points: 6

Topics

In this course you will learn

• basic equilibrium concepts (Nash equilibria, correlated equilibria, ...)
• strategic actions (best-response dynamics, no-regret dynamics, ...)
• auction design (revenue-maximizing auctions, Vickrey auctions)
• stable matching theory (preference aggregations, kidney exchanges, ...)
• price of anarchy and selfish routing (Braess' paradox, congestion games, ...)

Setup

Weekly lectures and weekly exercise session.

Recommended literature:

• T. Roughgarden: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
• N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.