AlgorithmicTheories of Games

Course guarantor:

Tomáš Valla

Lecturer:

Dušan Knop, Tomáš Valla

Tutor:

Jan Pokorný, Tomáš Valla

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/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Master specialization Computer Security, in Czech, 2020 (elective course)
• Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
• Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
• Master specialization Management Informatics, in Czech, 2020 (elective course)
• Master specialization Software Engineering, in Czech, 2020 (elective course)
• Master specialization System Programming, in Czech, version from 2020 (elective course)
• Master specialization Web Engineering, in Czech, 2020 (elective course)
• Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
• Master specialization Computer Science, in Czech, 2020 (elective course)
• Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
• Study plan for Ukrainian refugees (elective course)
• Master specialization System Programming, in Czech, version from 2023 (elective course)
• Master specialization Computer Science, in Czech, 2023 (elective course)