====== Computational Game Theory 2024/2025 ====== [[https://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B241/public/html/predmety/47/01/p4701406.html|B4M36MAS]] [[https://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B241/public/html/predmety/48/70/p4870006.html|BE4M36MAS]] [[https://cw.felk.cvut.cz/brute/|BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1891.html|Discussion forum]] This course introduces the fundamental concepts and applications of game theory, a powerful framework for modeling //strategic interactions between rational agents.// We will explore key aspects of game theory, including strict competition, coordination, and cooperation, while examining its practical applications in areas like //auctions//, //security models,// and //voting//. ===== Prerequisities ===== Students taking this course should have a working knowledge of * Programming in Python * Optimization (B0B33OPT), specifically the basics of linear programming (refer to sections 1-3 of the [[https://people.inf.ethz.ch/fukudak/lect/opt2011/aopt11note1.pdf|lecture notes]]) * Linear algebra (B0B01LAG) * Probability and statistics (B0B01PST) * Discrete mathematics (B4B01DMA) ===== Teachers ===== * Lecturer: [[http://cs.fel.cvut.cz/en/people/kroupto1|Tomáš Kroupa]] * Teaching assistants: [[https://cs.fel.cvut.cz/en/people/kubicon3|Ondřej Kubíček]], [[http://cs.fel.cvut.cz/en/people/votroto1|Tomáš Votroubek]] ===== Contact Information ===== * [[https://cw.felk.cvut.cz/forum/forum-1891.html|Discussion Forum]]: For general questions, we recommend posting in the course discussion forum, where we will prioritize responses. * //Lecture/Course-related inquiries//: tomas.kroupa@fel.cvut.cz * //Tutorials/Homework-related inquiries//: kubicon3@fel.cvut.cz, tomas.votroubek@fel.cvut.cz ===== Grading policy ===== ^ Part ^ Points ^ | Homeworks assignments | 35 | | Midterm test | 25 | | Exam | 40 | The points for 5 homework assignments are distributed as follows: ^Assignment ^Deadline ^Points^ |Double Oracle |05.11.2025|10| |Extensive Form Games|19.11.2024|5| |Sequence Form LP |03.12.2024|10| |Auctions |17.12.2024|5| |Flow Games |07.01.2025|5| 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 is divided into two sections: - //Quiz section//. This section includes five multiple-choice questions. Each question has five answer options, but only one is correct. Each correct answer with the explanation is worth 2 points (10 points in total). - //Computational section//. This section consists of two to three problem-solving tasks (15 points in total). {{ :courses:cgt:midterm_cgt-2023a.pdf|Midterm test}} in 2023/2024 ==== Assessment ==== A **minimum of 30 points** is required from the combined total of homework assignments and the midterm test. For each hour that a homework assignment is submitted past the deadline, a penalty of 0.05 points will be deducted. ==== Exam ==== A **minimum of 20 points** is required to pass the exam. The exam is a written test lasting 2 hours. In certain cases, a brief oral examination may follow to clarify answers. There is no quiz component in the exam. Please note that course assessment must be completed before taking the exam, except for those attending the first exam session. Exam tests in 2023/2024: {{ :courses:cgt:cgt_23_24_zkousky_01.pdf |1}} {{ :courses:cgt:cgt_23_24_zkousky_02.pdf |2}} {{ :courses:cgt:cgt_23_24_zkousky_03.pdf |3}} ===== Lectures ===== ^ Date ^ Topic ^ Lecturer ^ Slides ^ Additional \\ materials ^ |24/09 | Normal-form games |TK|{{ :courses:cgt:cgt_nf.pdf |01}} | {{ :courses:cgt:cgt01.pdf |01}} | |01/10 | Nash equilibrium | TK | | | |08/10 | Two-player zero-sum games | TK | | | |15/10 | Extensive-form games | OK | | | |22/10 | Solving extensive-form games |OK | | | |05/11 | Alternatives to Nash equilibrium | TK | | | |12/11 | Tractable classes of games |TK | | | |19/11 | Games with incomplete information | TK | | | |26/11 | Analysis of auctions | TK | | | |03/12 | Design of auctions | TK | | | |10/12 | Coalitional games | TK | | | |17/12 | Shapley value | TK | | | |07/01 | Summary | TK | | | ===== Tutorials ===== {{ :courses:cgt:cgt_exercises.pdf |Current version of the exercises used in tutorials}} ^ Date ^ Topic ^ Lecturer ^ Additional \\ Materials ^ |24/09 | Basic notions | OK | | |01/10 | Normal-form games | OK | | |08/10 | Solving normal-form games | OK | {{ :courses:cgt:cgt_lab3.py | LP}}| |15/10 | Extensive-form games | OK | | |22/10 | Solving imperfect information EFGs |OK | {{ :courses:cgt:cgt_lab5.py |LP}} | |05/11 | Alternatives to NE | OK | | |12/11 | //Midterm test// | | | |19/11 | Bayesian games | TV | | |26/11 | Simple Auctions | TV | | |03/12 | Optimal Auctions and VCG | TV | | |10/12 | Coalitional games | TV | | |17/12 | Shapley value | TV | | |07/01 | Weighted voting games | TV | | ===== Recommended reading ===== Students are encouraged to explore the relevant chapters in the following textbooks: * Shoham, Y. and Leyton-Brown, K.: Multiagent Systems. Cambridge University Press, 2008. [[http://www.masfoundations.org/download.html|online]] * Maschler, M., Zamir, S., and Solan, E. Game Theory. Cambridge University Press, 2020.