AlgorithmicTheories of Games

The course is not on the list Without time-table
Code Completion Credits Range Language
NI-ATH Z,ZK 4 2P+2C Czech
Garant předmětu:
Department of Theoretical Computer Science

Traditional game theory is a branch of mathematics, which has broad applications in economy, biology, politics and computer science. This theory studies the behaviour of agents (players) of a certain competitive process by designinng a mathematical model and investigating the strategies. The traditional task of classical game theory is to find the equilibria, which are the states of the game where no player wants to deviate from his strategy.

Due to the recent development of computers, internet, social networks, online auctions, advertising, multiagent systems and other concepts the algorithmic point of view is gaining attention. In addition to existential questions we study the problems of efficient computation of various solution concepts.

In this course we introduce the basics of game theory of many players, solution concept (usually equilibria) and methods of their computation.


Some knowledge of graph theory, combinatorics and algebra.

Syllabus of lectures:

1) introduction to game theory 1

2) introduction to game theory 2

3) computing Nash equilibria and the class PPAD 1

4) computing Nash equilibria and the class PPAD 2

5) computing Nash equilibria and the class PPAD 3

6) election theory, impossibility theorems 1

7) election theory, impossibility theorems 2

8) election theory, impossibility theorems 3

9) gerry mandering

10) combinatorial auctions

11) mechanism design

12) equlibria effectivity

Syllabus of tutorials:

Tutorials for deeper understanding the theory presented in the course, analysing simpler games.

Study Objective:


* to introduce the classical game theory

* to introduce the algorithmic game theory

* survey several special fields in algorithmic game theory

Study materials:

Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory

Dresher: The mathematics of games of strategy

Cramton, Shoham, Steinberg: Combinatorial Auctions

Brandt, Conitzer, Endriss, Lang, Procaccia: Handbook of Computational Social Choice

Rothe: Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division

Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-06-16
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6158006.html