Core course: Algorithmic game theory

This course will next be offered in the summer term 2021.

This course was offered in the summer term 2020.

Link to official 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 (online) 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.