 CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2021/2022

# AlgorithmicTheories of Games

Code Completion Credits Range
NI-ATH Z,ZK 4 2P+2C
Lecturer:
Tomáš Valla (guarantor), Dušan Knop
Tutor:
Jan Matyáš Křišťan, Šimon Schierreich
Supervisor:
Department of Theoretical Computer Science
Synopsis:

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.

Requirements:

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:

Goals:

* 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

Note:
Further information:
https://courses.fit.cvut.cz/MI-ATH/
Time-table for winter semester 2021/2022:
Time-table is not available yet
Time-table for summer semester 2021/2022:
 06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00 roomTH:A-1242Knop D.Valla T.09:15–10:45(lecture parallel1)Thákurova 7 (FSv-budova A)roomTH:A-1242Křišťan J.Schierreich Š.11:00–12:30(lecture parallel1parallel nr.101)Thákurova 7 (FSv-budova A)
The course is a part of the following study plans:
Data valid to 2022-08-12
For updated information see http://bilakniha.cvut.cz/en/predmet6158006.html