FI:IA168 Algorithmic game theory - Course Information

IA168 Algorithmic game theory

Extent and Intensity

2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Tomáš Brázdil, Ph.D. (lecturer)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 16:00–17:50 B410

Prerequisites

basic linear algebra, basic probability theory (mostly discrete probability), elementary complexity theory, some calculus

Course Enrolment Limitations

The course is offered to students of any study field.

Course objectives

In recent years, huge amount of research has been done at the borderline between game theory and computer science, largely motivated by the emergence of the Internet. The aim of the course is to provide students with basic knowledge of fundamental game theoretic notions and results relevant to applications in computer science. The course will cover classical topics, such as general equilibrium theory and mechanism design, together with modern applications to network routing, scheduling, online auctions etc. We will mostly concentrate on computational aspects of game theory such as complexity of computing equilibria and connections with machine learning.

Syllabus

• Basic definitions: Games in normal form, dominant strategies, Nash equilibria in pure and mixed strategies, existence of Nash equilibria, basic examples
• Computing Nash equilibria: Lemke-Howson algorithm, support enumeration, sampling methods, PPAD-completeness of Nash equilibria,
• Quantifying the inefficiency of equilibria and related games: Congestion and potential games, price of anarchy and price of stability, routing games, network formation games, load balancing games
• Learning in games: Regret minimization algorithms, correlated equilibria and connection to learning in games, regret minimization in routing games
• Auctions and mechanism design: First price auctions, Vickrey auctions, truthfulness, Vickrey-Clark-Groves mechanism, Bayesian games, Bayesian Nash equilibria, formal framework for mechanism design, revelation principle, auctions on Google
• Games with multiple moves: Games in extensive form, games on graphs, Markov decision processes, stochastic games

Literature

• Algorithmic game theory. Edited by Noam Nisan. Cambridge: Cambridge University Press, 2007, xxi, 754. ISBN 9780521872829. info
• FILAR, Jerzy A. and Koos VRIEZE. Competitive Markov decision processes : with 57 illustrations. New York: Springer, 1997, xii, 393. ISBN 0387948058. info

Teaching methods

Standard lecture

Assessment methods

Oral exam

Language of instruction

English

Further Comments

Study Materials
The course is taught annually.

• Enrolment Statistics (Autumn 2014, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2014/IA168