====== 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 ===== 
  * Lectures: 
    * Tuesday 9:15-10:45, 21.9.2021--4.1.2022, KN:A-215
    * Lecturers: [[http://cs.felk.cvut.cz/en/people/bosanbra|Branislav Bošanský]], [[http://cs.felk.cvut.cz/en/people/jakobmic|Michal Jakob]], [[http://cs.fel.cvut.cz/en/people/kroupto1|Tomáš Kroupa]]
  * Tutorials: 
    * Tuesday 11:00-12:30, 14:30-16:00, 16:15-17:45, 21.9.2021 -- 4.1.2022, KN:E-307
    * Tutors:[[http://cs.felk.cvut.cz/en/people/seitzdom |Dominik Andreas Seitz]],[[http://cs.felk.cvut.cz/en/people/sustrmic|Michal Šustr]],[[http://cs.fel.cvut.cz/en/people/votroto1|Tomáš Votroubek]],[[http://cs.fel.cvut.cz/en/people/aradhadi|Aditya Aradhye]]
  * **Main contacts:**
    * Regarding lectures/course: branislav.bosansky@agents.fel.cvut.cz
    * Regarding tutorials: dominik.seitz@aic.fel.cvut.cz (main contact, EN only), michal.sustr@aic.fel.cvut.cz (backup contact)
  * **Use [[https://cw.fel.cvut.cz/b191/courses/be4m36mas/start#reading_resources|recommended books]] for studying! Slides do not contain all the details.**

===== Links =====
  * [[https://cw.felk.cvut.cz/forum/forum-1749.html|Forum]]
  * [[http://cw.felk.cvut.cz/upload/|Upload System]] 
  * [[https://bit.ly/3dpuxm7|On line quizzes]]

===== 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

**Update January 2022, Form of the exam**
  * The exam is written, you have 150 minutes for the exam
  * The exam will be graded and the points will be put into the BRUTE system -- we will have online calls with those who wish to consult their results of the exam, discuss correct answers, etc. upon request
  * To minimize the probability of COVID transmission, please:
    * use FFP2 face mask and keep it on all the time
    * disinfect your hands upon entering the building
    * keep your distance from other colleagues
    * if possible, get yourself tested before the exam -- if you have a positive test or if you are not feeling well, please, do not come to the exam and sign-up to the next exam date. If needed, we will open additional exam dates. 

**Dates**:
  * 12.1. 13:30 -- 16:30 (KN:E-107)
  * 26.1. 9:00 -- 12:00 (KN:E-107)
  * 2.2. 9:00 -- 12:00 (KN:E-107)

Exam from the last years: {{ :courses:cgt:main.pdf |example}}

===== Lectures =====
(subject to permutation)

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

^ Date     ^ Topic ^ Lecturer ^ Resources ^ Old Resources ^ 
|21 Sept |Introduction to the course |Bošanský| {{ :courses:cgt:lecture_1_2021.pdf |}} | [[https://drive.google.com/file/d/1PJ_xwPzzr-gRGDzgFphSKjpK9UlzUorT/view?usp=sharing|video]] {{ :courses:be4m36mas:mas2018-l01.pdf |}} {{:courses:be4m36mas:mas2016-l01-introduction.pdf|1}} {{:courses:be4m36mas:mas2016-l02-architectures.pdf|2}} |     
|28 Sept | --- no lecture --- |  | | [[https://drive.google.com/file/d/1DDoPqFq1J001hXL2tOPwBZZqpAYt4tSh/view?usp=sharing|video]] {{ :courses:be4m36mas:mas2020-l02.pdf |}} {{ :courses:be4m36mas:mas2019-l02-bdi_architecture.pdf |Agent Architectures + BDI}}|
|05 Oct  | Normal-Form Games |Bošanský | {{ :courses:cgt:cgt_l02_nfgs_2021.pdf |lecture_2_2021.pdf}} | [[https://drive.google.com/file/d/1YPRUijNNiRmGPxkRQESpYPphJAZ2nUlV/view?usp=sharing|video]] {{ :courses:be4m36mas:mas_l03_gt_intro_2020.pdf |}} {{ :courses:be4m36mas:gt_intro_2019.pdf |}} {{:courses:be4m36mas:mas2016-l03-gt-intro.pdf|3}} |
|12 Oct | Solving Normal-form Games | Bošanský | {{ :courses:cgt:cgt_l03_solvingnfgs_2021.pdf |lecture_3_2021.pdf}} | [[https://drive.google.com/file/d/1XZULeToww4v1VkptowQG0gqEMss2T2Bf/view?usp=sharing|video]] {{ :courses:be4m36mas:mas_l04_nfgs_2020.pdf |}} {{ :courses:be4m36mas:nfg_2019.pdf |}} {{:courses:be4m36mas:nfg2.pdf|nfg}} {{:courses:be4m36mas:4.pdf|4}} |
|19 Oct | Games in Extensive Form  |Bošanský | {{ :courses:cgt:cgt_l04_efgs_2021.pdf |lecture_4_2021.pdf}}| [[https://drive.google.com/file/d/1CbJYC2GAG1yewdLuKA7esckGehvIPG3K/view?usp=sharing|video]] {{ :courses:be4m36mas:mas_l05_efgs_2020.pdf |}} {{ :courses:be4m36mas:efg_2019.pdf |}} {{ :courses:be4m36mas:efg_2018.pdf|efg_2018}} {{:courses:be4m36mas:5.pdf|5}} {{:courses:be4m36mas:efg_2017.pdf|efg_2017}} |
|26 Oct | Solving Extensive-Form Games | Bošanský | {{ :courses:cgt:cgt_l05_solvingefgs_2021.pdf |lecture_5_2021.pdf}} | [[https://drive.google.com/file/d/1a_DjGb6r_f3zUMJRBGdQfz1CKz5ZOIMa/view?usp=sharing|video]] {{ :courses:be4m36mas:mas_l06_solving_efgs_2020.pdf |}} {{ :courses:be4m36mas:solving_efg_2019.pdf |}} {{ :courses:be4m36mas:solving_efg_2018.pdf |}} {{:courses:be4m36mas:solving_efg_2017.pdf|solving_efg_2017}} {{:courses:be4m36mas:6.pdf|6}} |
|2 Nov | Other Game Representations  |Bošanský | --- canceled --- (see the materials from 2020)| [[https://drive.google.com/file/d/1Goeiw5fNEdA-gFftHa7X73e-WgV_Wds-/view?usp=sharing|video]] {{ :courses:be4m36mas:mas_l07_beyond_efgs_2020.pdf |}} {{ :courses:be4m36mas:beyond_2019.pdf |}}{{ :courses:be4m36mas:beyond_2018.pdf |}} {{:courses:be4m36mas:beyond_2017.pdf|beyond_2017}} {{:courses:be4m36mas:7.pdf|7}} |
|09 Nov | Multiagent Resource Allocation | Jakob  | {{ :courses:cgt:cgt2021-l7-multiagent_resource_allocation.pdf |slides}}| {{ :courses:be4m36mas:mas2020-l8-multiagent_resource_allocation-fixed.pdf |slides}}[[https://drive.google.com/file/d/1fHSkME2jTtZMMbvUJXWQZU3Kid4FJW9i/view?usp=sharing|video]]| 
|16 Nov  | Auctions 1 | Jakob |{{ :courses:cgt:mas2021-auctions-1.pdf |slides}} | [[https://drive.google.com/file/d/1mmHDDa-e6DsDjRu3JoekTLLv17OyE7uA/view?usp=sharing|video]] {{ :courses:be4m36mas:mas2020-l9-auctions-1.pdf | Auctions 1}}  {{ :courses:be4m36mas:auctions_2019.pdf |}}{{ :courses:be4m36mas:mas2018-l12-auctions.pdf |}} {{:courses:be4m36mas:12.pdf|12}} |
|23 Nov  | Auctions 2 | Jakob | {{ :courses:cgt:mas2021-cgt_auctions_2.pdf | slides }}| [[https://drive.google.com/file/d/1_Xul4CGZGCKhTWuNoFf5ur5YW64f9fj6/view?usp=sharing|video]] {{ :courses:be4m36mas:mas2020-l10-auctions_2.pdf | Auctions 2}}  |
|30 Nov  | Coalitional Games. The Core | Kroupa | {{ :courses:cgt:cg01_lectures.pdf |}} {{ :courses:cgt:coal.jl.zip |Pluto Julia notebook}} | [[https://drive.google.com/file/d/17H3XQ16syz9tTIjDKhYHIwSH9aOM8t0o/view?usp=sharing|video]]   |
|7 Dec | The Shapley value| Kroupa | {{ :courses:cgt:cg02_lectures.pdf |}} | [[https://drive.google.com/file/d/1UL7GSy3ajYG2wRgaaJAlsZWibmVN-xwp/view?usp=sharing|video]] |  
|14 Dec | The Nucleolus | Kroupa   | {{ :courses:cgt:cg03_lectures.pdf |}} | [[https://drive.google.com/file/d/1NCS0STKRlBbcQWces6jFAYuGKMtaczLF/view?usp=sharing|video]]  |  
|4 Jan | Voting and Social Choice | Kroupa   | {{ :courses:cgt:cg04_lectures.pdf |}} |  |

===== Tutorials =====

^ Date     ^ Topic ^ Lecturer ^ Resources ^ Old resources ^
|21 Sept | Introduction | Kroupa    | {{ :courses:cgt:cgt_c01_intro_2021.pdf |}} |  |
|28 Sept | --- no lab ---                      |     | |  |
|05 Oct | Normal-Form Games | Seitz  | {{:courses:cgt:cgt_c02_nfg_2021.pdf}} | |
|12 Oct | Solving Normal-Form Games                            | Seitz |{{:courses:cgt:cgt_c03_solvingnfg_2021.pdf}} | {{:courses:cgt:cgt_c03_lps.py}}[[https://drive.google.com/file/d/1nzVAabEpmI4Dmh314NbCdO8cRlx06wO_/view?usp=sharing|video]] {{courses:be4m36mas:mas_nfg_2020.pdf}} {{courses:be4m36mas:s_cv_nfg_2019.pdf}}{{ :courses:be4m36mas:cv_nfg_2018.pdf |}} {{:courses:be4m36mas:nfg_cermak_2017.pdf|}} {{:courses:be4m36mas:nfg.pdf|}} |
|19 Oct  | Extensive-Form Games                         | Šustr | {{:courses:cgt:cgt_c04_efg_formulation_2021.pdf}} | [[https://drive.google.com/file/d/1G2iB000tJfbhAhcCuuSWHk6UMhOX6s2M/view?usp=sharing|video]] {{courses:be4m36mas:cv_efg_2020.pdf}} {{courses:be4m36mas:cv_efg_2019.pdf}} {{ :courses:be4m36mas:cv_efg_2018.pdf |}} {{:courses:be4m36mas:cv_nfg_2017.pdf|}} {{:courses:be4m36mas:efg_intro.pdf|}} |
|26 Oct  | Solving Extensive-Form Games                         | Šustr | {{:courses:cgt:cgt_c05_solving_efg_2021.pdf}} | [[https://drive.google.com/file/d/1H9gY1teaqbAaNE9pUNs8csJi2s2X8CP6/view?usp=sharing|video]] {{courses:be4m36mas:cv_solving_efg_2019_2.pdf}} {{:courses:be4m36mas:cv_nfg_efg.pdf|cv_nfg_efg_2017}} {{:courses:be4m36mas:efg_solving.pdf|}} |
|2 Nov | Solving Extensive-Form Games 2                | Šustr | | [[https://drive.google.com/file/d/1VOwH5uY-QIP1w8r3tLwA-tpwYQzvofsW/view?usp=sharing|video]]  {{courses:be4m36mas: cv_solving2_efg_2019.pdf}}{{:courses:be4m36mas:cv_solving_efg.pdf|cv_solving_efg_2017}} {{:courses:be4m36mas:efg_solving.pdf|}} |
|9 Nov  | Midterm Test   |  | | [[https://drive.google.com/file/d/1Vxe4L_JtdqQHRTdwu2sb_Ptk0wrtIBLm/view?usp=sharing|video]] {{ :courses:be4m36mas:simple_poker.pdf |Simple Poker LPs}} [[https://drive.google.com/file/d/1Ej45s-_KRNstSCFhMIkRao8lC2Gyd0WP/view?usp=sharing|Video - consultation for the second assignment]] |
|16 Nov | Auctions 1  | Votroubek | {{:courses:cgt:auctions.simple.2021.pdf|Single-Item Auctions}} | [[https://drive.google.com/file/d/13vAflubipWZNEmn1SbFu2fpyo2qg4Ex1/view?usp=sharing|video]] {{:courses:be4m36mas:MAS2020_Auctions1_Lab (1).pdf|}} {{:courses:be4m36mas:mas_auctions_lab_2019.pdf|}} |
|23 Nov | Auctions 2  | Votroubek | {{:courses:cgt:auctions.combinatorial.2021.pdf|Combinatorial Auctions}} | [[https://drive.google.com/file/d/1IwBz2daqa1I7_F_w2Z4a35kpQSB_-mdx/view?usp=sharing|video]] {{:courses:be4m36mas:mas2020_auctions2_lab.pdf}} {{:courses:be4m36mas:cv_resource.pdf|}} {{:courses:be4m36mas:auctions_tree.ps|}} {{:courses:be4m36mas:cv_auctions_2017.pdf|}} {{:courses:be4m36mas:cv_auctions.pdf|}}|
|30 Nov | Coalitional Games. The Core  | Aradhye | | {{ :courses:cgt:cg_exercises.pdf |}}[[https://drive.google.com/file/d/1M9sR8pNIViLh3_090IZRWvQenYKX5fks/view?usp=sharing|video]] | 
|7 Dec | The Shapley Value  | Aradhye | | [[https://drive.google.com/file/d/1m-ILe6rlEOQQR7ZGOffhPMlFEBXpzYa6/view?usp=sharing|video]]  |
|14 Dec | The Nucleolus  | Aradhye | | [[https://drive.google.com/file/d/13v5YOFkKudM99ogPE6QS07WkOl4-Sl6I/view?usp=sharing|video]]  [[https://gitlab.fel.cvut.cz/votroto1/nucleolus|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.     
      * available [[http://www.masfoundations.org/download.html|on-line]]
  * [Weiss] [[http://mitpress.mit.edu/books/multiagent-systems-1|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''.