Computational Game Theory (BE4M36MAS) Winter 2022/2023

The course provides an introduction to concepts, models and algorithms for autonomous agents and multi-agent systems. Game theory is the key formalism used in multi-agent systems that describes and defines optimal behavior of an agent while explicitly reasoning about plans and goals of other agents. In the course, we will explains key multiagent models and algorithms, both for cooperative and non-cooperative settings. Upon successful completion of the course, students will be able to understand main multi-agent concepts, be able to map real-world multi-agent problems to multiagent formal models and apply algorithmic techniques to solve them.

General Information

Lectures:
- Tuesday 9:15-10:45, 20.9.2022–10.1.2023, KN:E-301
- Lecturers: Branislav Bošanský, Tomáš Kroupa, Michal Jakob
Tutorials:
- Tuesday 11:00-12:30, 14:30-16:00, 20.9.2022 – 10.1.2023, KN:E-307
- Tutors: Ondřej Kubíček,Tomáš Votroubek
Main contacts:
- Regarding lectures/tutorials/course: branislav.bosansky@agents.fel.cvut.cz
- Regarding homework assignments: tomas.votroubek@fel.cvut.cz
Use recommended books for studying! Consider slides to be an outline of the topics we cover, they do not contain all the details.

Links

Grading

Both the course assessment 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).

Assessment

Minimum of 25 pts is required from the labs

Game theory: max grading: 14 pts.
Coalitional game theory: max grading: 12 pts.
Midterm Test: max grading 24 pts.

The penalty for submitting the homework assignment after the deadline, but no later than 24 hours after the deadline, is 20% of the points.

The penalty for submitting the homework assignment later than 24 hours after the deadline is 100% of the points.

Exam

Minimum of 25 pts is required from the exam (out of maximum 50 pts).

The exam is written. In selected cases, a brief oral part to clarify answers follows.
The form of exam/requirements can change depending on the current COVID restrictions.
Exam topics correspond to the topics covered by lecture slides
Course assessment is required prior to attending an exam

Dates:

10.1.2023 9:15 – 12:00 E307 + E310
17.1.2023 9:15 – 12:00 E307
31.1.2023 9:15 – 12:00 E307

Exam from the last years: example

Lectures

(subject to change)

For accessing the videos, please, log-in using your Google FEL account.

Date	Topic	Lecturer	Resources	Old Resources
20 Sept	Introduction to the course	Bošanský	lecture_1_2022.pdf	video_2020 lecture_1_2021.pdf
27 Sept	Normal-Form Games	Bošanský	lecture_2_2022.pdf	video_2020 lecture_2_2021.pdf
04 Oct	Solving Normal-form Games	Bošanský	lecture_3_2022.pdf	video_2020 lecture_3_2021.pdf
11 Oct	Games in Extensive Form	Bošanský	lecture_4_2022.pdf	video_2020 lecture_4_2021.pdf
18 Oct	Solving Extensive-Form Games	Bošanský	lecture_5_2022.pdf	video_2020 lecture_5_2021.pdf
25 Oct	Other Game Representations	Bošanský	lecture_6_2022.pdf	video_2020 lecture_6_2020.pdf
1 Nov	Bayesian games. Introduction to Auctions.	Jakob	Bayesian Games 2022
08 Nov	Auctions 1	Jakob	Auctions 1 2022	video_2020 slides
15 Nov	Auctions 2	Jakob	Auctions 2 2022	video_2020 slides
22 Nov	Coalitional Games. The Core	Kroupa	cg01_lectures.pdf	video_2020
29 Nov	The Shapley value	Kroupa	cg02_lectures.pdf	video_2020
6 Dec	The Nucleolus	Kroupa	cg03_lectures.pdf	video_2020
13 Dec	Voting and Social Choice	Kroupa	cg04_lectures.pdf
10 Jan	First Exam Date

Tutorials

Date	Topic	Lecturer	Resources
20 Sept	Introduction to the course	Bošanský & Kubíček	slides exercises
27 Sept	Normal-Form Games	Kubíček	exercises
04 Oct	Solving Normal-form Games	Kubíček	exercises
11 Oct	Games in Extensive Form	Kubíček	exercises
18 Oct	Solving Extensive-Form Games	Kubíček	exercises
25 Oct	Other Game Representations	Kubíček
1 Nov	Midterm Test	Kubíček
08 Nov	Auctions 1	Votroubek	exercises
15 Nov	Auctions 2	Votroubek	exercises
22 Nov	Coalitional Games. The Core	Votroubek	Exercises for the last 4 tutorials
29 Nov	The Shapley value	Kroupa
6 Dec	The Nucleolus	Votroubek
13 Dec	Voting and Social Choice	Votroubek
10 Jan	First Exam Date

Reading Resources

[Shoham] Shoham, Y. and Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2008, ISBN 9780521899437.
- available on-line
[Weiss] Weiss, G. (eds): Multiagent Systems, second edition, MIT Press, 2013
- relevant chapters available on-request from Michal Jakob
[AIMA] Russel, S. a Norvig, P.: Artificial Intelligence: A Modern Approach (2nd edition), Prentice Hall, 2003
- relevant chapters available by e-mail request from Michal Jakob
[Wooldridge] Wooldridge, M.: An Introduction to MultiAgent Systems, John Wiley & Sons Ltd, 2002, ISBN 0-471-49691-X.
- relevant chapters available by e-mail request from Michal Jakob

Tutorial Resources

For running IntelliJ Idea on local machines use command /opt/idea-IC-173.4548.28/bin/idea.sh.

Table of Contents