Даниил Мусатов
Алгоритмическая теория игр и дизайн механизмов

»
О курсе

Алгоритмическая теория игр – это активно развивающаяся область, сочетающая в себе красивую теорию и многочисленные приложения.

Реальные экономические агенты зачастую далеки от рациональных и по меньшей мере являются вычислительно ограниченными. Это значит, что равновесие в теоретико-игровой модели может быть надёжным предсказанием реального исхода, только если участники игры (или хотя бы внешний наблюдатель) смогут его вычислить. По словам Камаля Джейна, «Если ваш компьютер не может найти равновесие, почему выдумаете, что рынок сможет?»

Первые лекции посвящены задаче вычисления различных равновесий. В то время как основная часть курса знакомит с теорией разработки механизмов. Задача теории механизмов обратна теории игр: нужно не предсказать исход по правилам игры, а, наоборот, по требуемому исходу составить правила игры. Мы изучим как классические подходы к этой теории, так и продвинутые подобласти, связанные, в том числе, и с ограничениями на вычислительную мощность.


»
Команда курса
Даниил Мусатов
Лектор
Ишкуватов Руслан
Семинарист

»
Программа курса
Алгоритмы поиска равновесия Нэша для игр двух лиц
Биматричные игры. Алгоритмы поиска равновесия Нэша для двух игроков: метод
«стакана» для игр 2×𝑁, метод перебора носителей, метод размеченных полиэдров,
метод Лемке-Хоусона.
Поиск равновесия в игре многих лиц
Поиск равновесия в игре многих лиц.
Понятие о вычислительной сложности задачи.
Итеративные алгоритмы поиска, сходящиеся к коррелированному равновесию.
Цена анархии
Сравнение оптимума и равновесия в играх. Понятия цены анархии и цены ста-
бильности. Пример: задачи маршрутизации трафика.
Задача о справедливом дележе
Задача о справедливом дележе. Критерии справедливости дележа: пропорцио-
нальность, отсутствие зависти и др. Конечные протоколы пропорционального де-
лежа и дележа без зависти. Протоколы с движущимися ножами. Задача о рассе-
лении по комнатам арендуемой квартиры (rental harmony).
Введение в теорию механизмов
Введение в теорию механизмов. Имплементация в доминирующих стратегиях и
по Байесу. Принцип выявления.
Механизм VCG
Механизмы с использованием денег. Имплементация в доминирующих стратегиях.
Аукцион Викри (второй цены). Механизм Викри–Кларка–Гровса. Приложения к
различным видам аукционов, задаче о двусторонней торговле, выполнению обще-
ственного проекта, маршрутизации потоков в сетях.
Имплементация по Байесу–Нэшу
Имплементация по Байесу–Нэшу. Механизм Эрроу–Дапремона–Жерара-Варе. Аук-цион первой цены.
Теорема об эквивалентности доходов в теории аукционов
Теорема об эквивалентности доходов в теории аукционов. Критерий существова-
ния индивидуально рационального механизма со сбалансированным бюджетом.
Теорема Майерсона–Саттертуэйта о двусторонней торговле.
Оптимальные аукционы
Аукционы с резервной ценой. Оптимальные аукционы.
Комбинаторные аукционы
Комбинаторные аукционы. Аукционы по продаже спектра.
Вычислительно эффективные механизмы для решения задач аппроксимации
Распределённые механизмы
Онлайн-механизмы
Разработка механизмов репутации, устойчивых к манипуляциям