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