This module is taught in English. This module is regularly offered every summer term.

This module was previously offered in the summer terms 2020, 2021, 2022 and 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.

Recommended prerequisites

We expect attendees to be proficient in the material from the following modules:

• Discrete algebraic structures
• Mathematics I
• Mathematics II

We further recommend basic knowledge of the following topics:

• Algorithms and data structures
• Graphs and networks
• Probability theory (probability spaces, expected value)
• Programming in Python, C++, C# or Java

Learning goals

In this module you will learn

• to model strategic interaction systems and market mechanisms of agents,
• to analyze their efficiency and equilibria (existentially and algorithmically),
• to understand various auction concepts,
• to create and analyze exchange markets based on preferences.

Topics

In this module we will cover the following topics:

• 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 (in presence) and weekly tutorial session (in presence).
• Each week an assignment is handed out, which should be solved individually outside the classroom  and then be submitted for grading. The assignment and its solutions are then discussed in the subsequent tutorial session. If sufficiently many points are awarded in the grading process (cumulative over all assignments of the term), then a bonus is given for the final exam at the end of the term.
• Final exam (written) for 90 minutes at the end of the term, whose outcome (together with a potential bonus from the assignment) determines the final grade for the module.

Overall module load: 6 ECTS credit points

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.