Computational Game Theory (BE4M36MAS) 2023/2024

Welcome to the exciting world of game theory! This course is designed to introduce you 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 explainable AI.

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.

Prerequisities

The student of this course should have a working knowledge of

• programming in Python
• optimization (B0B33OPT), in particular linear programming basics (see the sections 1-3 in the lecture notes by Komei Fukuda)
• linear algebra (B0B01LAG)
• probability and statistics (B0B01PST)
• discrete mathematics (B4B01DMA)

Teachers

• Teaching Assistants for tutorials: Ondřej Kubíček,Tomáš Votroubek
• Main contacts:
• We will prioritize answering questions posted to discussion forum.
• Regarding lectures/course: tomas.kroupa@fel.cvut.cz, michal.jakob@fel.cvut.cz
• Regarding turorials/homework assignments: kubicon3@fel.cvut.cz, tomas.votroubek@fel.cvut.cz

Part Points
Homeworks assignments 30
Midterm test 30
Exam 40

The points for 4 homework assignments are distributed as follows:

• Assignment 1 - EFG: max 10 pts. Deadline: 14.11.2023
• Assignment 2 - SQF: max 10 pts. Deadline: 28.11.2023
• Assignment 3 - Auctions: max 5 pts. Deadline: 12.12.2023
• Assignment 4 - Flow game: max 5 pts. Deadline: 09.01.2024

Both the course assessment (zápočet) and exam are required to pass the course. The final grade (A,…,F) will be determined by the sum of points obtained from the assessment and exam (<50 = F, 50-59 pts = E, …, 90-100 pts = A).

Midterm test

The midterm test has two parts:

1. The quiz part of the test consists of five questions, each of which has five possible answers and only one is correct. You can obtain 2 points for each question.
2. The computational part contains two minor problems for 5 points each and one major task (10 points).

Assessment

Minimum of 30 pts is required from the sum of points for homework assignments and midterm test. The penalty for submitting the homework assignment after the deadline is 0.05 points per hour.

Exam

Minimum of 20 pts is required from the exam.

• The exam is written. In selected cases, a brief oral part follows to clarify answers.
• Course assessment is required prior to attending an exam.

Exam from the last years: example

Lectures

Date Topic Lecturer Slides
26/09 Introduction. Normal-form games. TK01
03/10 Nash equilibria for normal-form games. TK 02
10/10 Tractable classes of games. Learning in games. TK 03
17/10 Extensive-form games. OK 04
24/10 Solving imperfect information EFGs. OK 05
31/10 Alternatives to NE. TK 06
07/11 Bayesian games. MJ 07
14/11 Auctions 1. MJ 08
21/11 Auctions 2. MJ 09
28/11 Coalitional games. The core. TK 10
05/12 The Shapley value. TK 11
12/12 Weighted voting games. TK
19/12 Games in computer science and ML. TK
09/01 First exam term.

Tutorials

Materials
26/09 Basic notions. TK
03/10 Normal-form games. OK
10/10 Solving normal-form games. OK LP
17/10 Extensive-form games. OK
24/10 Solving imperfect information EFGs. OK LP
31/10 Alternatives to NE. OK
07/11 Midterm test.
14/11 Bayesian games. TV
21/11 Auctions 1 TV
28/11 Auctions 2. TV
05/12 Coalitional games. The core. TV
12/12 The Shapley value. TV
19/12 Weighted voting games. TV
09/01 First exam term.

The students are encouraged to read the relevant chapters in the following textbooks:

• Kochenderfer M.J., Wheeler T.A., Wray K.H. Algorithms for decision making. MIT press, 2022.online
• Shoham, Y. and Leyton-Brown, K.: Multiagent Systems. Cambridge University Press, 2008. online
• Maschler, M., Zamir, S., and Solan, E. Game Theory. Cambridge University Press, 2020.