SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Algorithmic Game Theory - NDMI098
Title in English: Algoritmická teorie her
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Martin Balko, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics, Optimalization
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
An introduction to algorithmic game theory, a relatively new field whose objective is to study formal models of strategic environments and to design effective algorithms for them. This introductory course covers basic concepts and methods that are illustrated with several practical applications. To successfully pass the course, it is recommended to know basics from complexity theory.
Course completion requirements -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)

The credit for the exercise is given after obtaining a sufficient amount of points for solving the home problems. The nature of the conditions does not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

Literature -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007.

Tim Roughgarden, Lecture Notes on Algorithmic Game Theory :

Requirements to the exam -
Last update: RNDr. Martin Balko, Ph.D. (04.10.2018)

There will be oral exam with time for preparation of the answers. The material required for the exam will be the same as taught in the lecture. The exam may include easier or moderately difficult problems from these topics.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)

Formal models in game theory

Auctions, Myerson's Lemma

Price of anarchy

Nash equilibrium, Nash's Existence Theorem

Finding equilibria, complexity class PPAD

Correlated equilibiria and other variants

Minimax Theorem

Charles University | Information system of Charles University |