VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Algorithmic Game Theory
Last Updated: 2026-02-05 15:24:47
Abstract
Game theory provides a good model for the behavior and interaction of the selfish users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory: Introduction to game theory, Auction-like mechanisms, Cost of a central control optimum and a selfish equilibrium, Algorithms and complexity of computing equilibria.
Content
The internet forms a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good, such as bandwidths, packet routes, computational loads, or download rates. Game theory provides a particularly well-suited model for the behaviour and interaction of such selfish users and programs, who only pursue their own interests. Dating back to the 1930s, and having received a Nobel prize as recently as last year, classical game theory typically does not consider algorithms. For these reasons, computer scientists have recently gained an increasing interest in algorithms for game-theoretic models. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth. Tentative outline: - An introduction to classical game theoretic concepts. - Auction-like mechanisms and algorithms that "direct" the actions of selfish agents into a certain desired equilibrium situation. - The cost difference between an optimum under central control and an equilibrium under selfish agents, known as the "price of anarchy". - Algorithms for computing equilibria of games, and the computational complexity of this task. - Time permitting, we may also consider the convergence process to an equilibrium.
Resources
Literature
"Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press; "Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004 (this book was used in the course two years ago and is available in the computer science library; its first few chapters cover some of the material of the first few weeks).
General Information
- Language
- English
- Levels
- BSC , DS , MSC , WBZ
- Frequency
- Yearly recurring
Examination
- Type
- end-of-semester examination
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Algorithmic Game Theory |
|
3 h weekly |
| exercise | Algorithmic Game Theory |
|
2 h weekly |