Computational Game Theory

Relations:

It is not possible to register for the course B4M36MAS if the student is concurrently registered for or has already completed the course BE4M36MAS (mutually exclusive courses).

It is not possible to register for the course B4M36MAS if the student is concurrently registered for or has previously completed the course BE4M36MAS (mutually exclusive courses).

The requirement for course B4M36MAS can be fulfilled by substitution with the course BE4M36MAS.

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Computer Science

Synopsis:

This course is designed to introduce students to the fundamental concepts and applications of game theory, a powerful tool used to model strategic interactions among individuals, organizations, or countries. Throughout the course, we will delve into various aspects of game theory and explore its wide-ranging applications in diverse fields, including machine learning and AI.

Requirements:

- programming in Python

- optimization, in particular linear programming basics

- linear algebra

- probability and statistics

- discrete mathematics

Syllabus of lectures:

1. Introduction. Normal-form games.

2. Nash equilibria for normal-form games.

3. Tractable classes of games. Learning in games.

4. Extensive-form games.

5. Solving imperfect information EFGs.

6. Alternatives to NE.

7. Bayesian games

8. Auctions 1.

9. Auctions 2.

10. Coalitional games. The core.

11. The Shapley value.

12. Weighted voting games.

13. Games in computer science and ML.

14. Summary.

Syllabus of tutorials:

1. Introduction. Normal-form games.

2. Nash equilibria for normal-form games.

3. Tractable classes of games. Learning in games.

4. Extensive-form games.

5. Solving imperfect information EFGs.

6. Alternatives to NE.

7. Bayesian games

8. Auctions 1.

9. Auctions 2.

10. Coalitional games. The core.

11. The Shapley value.

12. Weighted voting games.

13. Games in computer science and ML.

14. Summary.

Study Objective:

By the end of the course, you will be equipped with the knowledge and skills to analyze complex strategic situations, evaluate fairness of allocation mechanisms, and appreciate the exciting applications of game theory in AI.

Study materials:

Shoham, Y. and Leyton-Brown, K.: Multiagent Systems. Cambridge University Press, 2008.

Maschler, M., Zamir, S., and Solan, E. Game Theory. Cambridge University Press, 2020.

Kochenderfer M.J., Wheeler T.A., Wray K.H. Algorithms for decision making. MIT press, 2022.

https://cw.fel.cvut.cz/b231/_media/courses/cgt/cgt_exercises.pdf

Note:

Further information:

https://cw.fel.cvut.cz/wiki/courses/cgt

No time-table has been prepared for this course

The course is a part of the following study plans:

• Open Informatics - Artificial Intelligence (compulsory course of the specialization)