Algorithmic Game Theory


Range: 2+0+4


Credits: 4

Programme type: Doctoral

Study form: Fulltime

Course language: English

Time table at FEE


This course extends the knowledge in multiagent systems and game theory by focusing on the algorithmic and computational problems - the computational complexity and current algorithms for finding and approximating different solution concepts, the impact of different representations of games, and the applications of learning techniques in game theory. The course is suitable for students that have already completed the course on Multiagent Systems (A4M36MAS) and either wish to strengthen their knowledge in game theory, or they are working on related problems from artificial intelligence such as machine learning, decision theory, planning.


Course syllabus:

1. Introduction to Game Theory
2. Fundamental Theorems (von Neumann, Nash, Kuhn)
3. Succinct Representations of Games
4. Finding Nash Equilibria
5. Approximating Nash Equilibria
6. Finding Correlated Equilibria
7. Finding Stackelberg Equilibria
8. Repeated Games
9. Learning and Dynamics in Games
10. Learning in Extensive-Form Games
11. Games of Incomplete Information, Auctions
12. Algorithmic Mechanism Design
13. Mechanisms Without Money
14. Stochastic Games

The structure of the lecutres covers the important algorithmic topics in game theory. Besides attending the lectures, the students are assumed to work on their homework assignments that strenghten the understanding of the topic (4h per week).

Seminar syllabus:


Shoham and Leyton-Brown. "Multiagent Systems", Cambridge University Press, 2009
Nisan, Roughgarden, Tardos and Vazirani. "Algorithmic Game Theory", Cambridge University Press, 2007
Maschler, Solan and Zamir. "Game Theory", Cambridge University Press, 2013