City: Санкт-Петербург Новосибирск Казань Language: Русский English

Algorithmic game theory
Saint-Petersburg / autumn 2019, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Курс состоит из нескольких тем, относящихся к теории игр и алгоритмической сложности решения игр. Предварительного знания основных определений и фактов в теории игр не требуется: они будут, хотя бы кратко, рассказаны.

В начале будут рассказаны классические результаты о решении конечных игр и приведены примеры PSPACE-полных игр. Далее будет обсуждено (не-)существование выигрышных стратегий для бесконечных игр и дано доказательство существования особо простых стратегий (позиционные стратегии, стратегии с конечной памятью) для игр из нескольких интересных классов: игры чётности, циклические игры, простые стохастические игры. Существование таких стратегий имеет важные следствия для алгоритмической сложности решения таких игр, помещая эту задачу в пересечение классов NP и coNP. Основной темой курса является изложение недавно придуманных квазиполиномиальных алгоритмов для решения игр чётности. Для циклических игр будут рассказаны вероятностные субэкспоненциальные алгоритмы (лучше пока не получается).

Для понимания курса желательно знакомство с основными понятиями теории сложности вычислений: машины Тьюринга, основные сложностные классы, понятие сводимости. Текст содержит лишь короткие напоминания по этим вопросам. Для более подробного ознакомления с теорией сложности рекомендуются стандартные учебники, например, Сипсера или Ароры и Барака. Желательно также знакомство с базовыми алгоритмами (топологическая сортировка, построение кратчайших путей и т.п.).

Date and time Class|Name Venue|short Materials
09 November
17:15–18:45
Лекция, lecture ПОМИ РАН No
09 November
19:00–20:30
Лекция, lecture ПОМИ РАН No
10 November
11:15–12:45
Лекция, lecture ПОМИ РАН No
10 November
13:00–14:30
Лекция, lecture ПОМИ РАН No
10 November
15:30–17:00
Лекция, lecture ПОМИ РАН No
16 November
17:15–18:45
Лекция, lecture ПОМИ РАН No
16 November
19:00–20:30
Лекция, lecture ПОМИ РАН No
17 November
11:15–12:45
Лекция, lecture ПОМИ РАН No
17 November
13:00–14:30
Лекция, lecture ПОМИ РАН No
17 November
15:30–17:00
Лекция, lecture ПОМИ РАН No