Computational Game Theory (BE4M36MAS) Winter 2021/2022

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

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:

  • TBA

Exam from the last years: TBA

Lectures

(subject to permutation)

Date Topic Lecturer Resources Old Resources
21 Sept Introduction to the course Bošanský lecture_1_2021.pdf video mas2018-l01.pdf 1 2
28 Sept — no lecture — video mas2020-l02.pdf Agent Architectures + BDI
05 Oct Normal-Form Games Bošanský lecture_2_2021.pdf video mas_l03_gt_intro_2020.pdf gt_intro_2019.pdf 3
12 Oct Solving Normal-form Games Bošanský lecture_3_2021.pdf video mas_l04_nfgs_2020.pdf nfg_2019.pdf nfg 4
19 Oct Games in Extensive Form Bošanský lecture_4_2021.pdf video mas_l05_efgs_2020.pdf efg_2019.pdf efg_2018 5 efg_2017
26 Oct Solving Extensive-Form Games Bošanský video mas_l06_solving_efgs_2020.pdf solving_efg_2019.pdf solving_efg_2018.pdf solving_efg_2017 6
2 Nov Other Game Representations Bošanský video mas_l07_beyond_efgs_2020.pdf beyond_2019.pdfbeyond_2018.pdf beyond_2017 7
09 Nov Multiagent Resource Allocation Jakob slidesvideo
16 Nov Auctions 1 Jakob video Auctions 1 auctions_2019.pdfmas2018-l12-auctions.pdf 12
23 Nov Auctions 2 Jakob video Auctions 2
30 Nov Coalitional Games. The Core Kroupa video cg01_lectures.pdf
7 Dec The Shapley value Kroupa video cg02_lectures.pdf
14 Dec The Nucleolus Kroupa video cg03_lectures.pdf
4 Jan Social Choice TBA

Tutorials

Date Topic Lecturer Resources Old resources
21 Sept Introduction Kroupa cgt_c01_intro_2021.pdf
28 Sept — no lab —
05 Oct Normal-Form Games Seitz cgt_c02_nfg_2021.pdf
12 Oct Solving Normal-Form Games Seitz cgt_c03_solvingnfg_2021.pdf cgt_c03_lps.pyvideo mas_nfg_2020.pdf s_cv_nfg_2019.pdfcv_nfg_2018.pdf nfg_cermak_2017.pdf nfg.pdf
19 Oct Extensive-Form Games Šustr cgt_c04_efg_formulation_2021.pdf video cv_efg_2020.pdf cv_efg_2019.pdf cv_efg_2018.pdf cv_nfg_2017.pdf efg_intro.pdf
26 Oct Solving Extensive-Form Games Šustr video cv_solving_efg_2019_2.pdf cv_nfg_efg_2017 efg_solving.pdf
2 Nov Solving Extensive-Form Games 2 Šustr video cv_solving2_efg_2019.pdfcv_solving_efg_2017 efg_solving.pdf
9 Nov Midterm Test video Simple Poker LPs Video - consultation for the second assignment
16 Nov Auctions 1 Votroubek video mas2020_auctions1_lab_1_.pdf mas_auctions_lab_2019.pdf
23 Nov Auctions 2 Votroubek video mas2020_auctions2_lab.pdf cv_resource.pdf auctions_tree.ps cv_auctions_2017.pdf cv_auctions.pdf
30 Nov Coalitional Games. The Core Aradhye video
7 Dec The Shapley Value Aradhye video
14 Dec The Nucleolus Aradhye video cg_exercises.pdf Python code for the nucleolus
4 Jan Social Choice, Voting Seitz Votroubek

Reading Resources

  • [Shoham] Shoham, Y. and Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2008, ISBN 9780521899437.
    • 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.

courses/cgt/start.txt · Last modified: 2021/10/19 08:55 by bosanbra