SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Algorithmic Game Theory - NDMI098
Title: 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 [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: doc. 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. Martin Balko, Ph.D. (07.10.2019)

The credit for the tutorial is given after obtaining at least one quater of all available points. The points are given for solving problems that are assigned during semester. 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 : http://theory.stanford.edu/~tim/f13/f13.html

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

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. The exam can be done online.

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 | http://www.cuni.cz/UKEN-329.html