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:07:01
Abstract
Game theory provides a good model for the behavior and interaction of theselfish users and programs in large-scale distributed computer systemswithout central control. The course discusses algorithmic aspects of gametheory: Introduction to game theory, Auction-like mechanisms, Cost of acentral control optimum and a selfish equilibrium, Algorithms and complexityof 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
"A Course in Game Theory", M. Osbourne and A. Rubinstein, the MIT Press, 1994, a quite compact and formal text. "An Introduction to Game Theory", M. Osbourne, Oxford University Press, 2004, contains more extensive discussions and examples, less mathematical. "Game Theory for Applied Economists", R. Gibbons, Princeton University Press, 1992. "Combinatorial Auctions", P. Cramton, Y. Shoham, and R. Steinberg (eds.), The MIT Press, 2006. "Selfish Routing and the Price of Anarchy", T. Roughgarden, The MIT Press, 2005.
General Information
- Language
- English
- Levels
- BSC , DS , MSC
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 15 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Algorithmic Game Theory |
|
2 h weekly |
| exercise | Algorithmic Game Theory |
|
2 h weekly |