Курсы по теории игр. Объединенный критерий Байеса-Лапласа и минимакса

1. Понятия неопределенности и риска.
2. Функция полезности Неймана-Моргенштерна. Аксиомы рационального поведения, доказательство теоремы Неймана-Моргенштерна
3. Эмпирические проверки теории ожидаемой полезности (парадокс Алле и др.).

Тема: Статические игры с полной и неполной информацией >>

1. Определение игры в нормальной форме: Игроки, стратегии, платежи.
2. Примеры игр: Дилемма заключенного, координация, война полов, ястреб-голубка.
3. Решения некооперативных игр: доминирование сильное и слабое. Равновесие Нэша в чистых стратегиях.
4. Примеры: дуополия Курно, дуополия Бертрана, город Хотеллинга. Двусторонние торги. Эксперимент: координационные игры.

Тема: Равновесия в играх >>

1. Смешаные стратегии. Теорема о существовании равновесия и ее доказательство.
2. Рационализируемые стратегии.
3. Коррелированное равновесие.

Тема: Усиления равновесий в статических играх >>

1. Проблема множественности равновесий. Понятие об усилениях равновесий (equilibrium refinements).
2. Строгое, существенное, совершенное, собственное равновесия.
3. Риск-доминантные равновесия.

Тема: Динамические игры с полной информацией >>

1. Определение игры в развернутой форме. Дерево игры, информационные множества.
2. Принцип Беллмана, обратная индукция и равновесие совершенное по подыграм.
3. Поведенческие стратегии, теорема Куна.
4. Примеры: Дуополия Штакельберга, парадокс супермаркета. модель чередующихся предложений Рубинштейна.
5. Эксперимент: Игра-сороконожк

Тема: Повторяющиеся игры >>

1. Повторяющаяся дилемма заключенного. Дисконтирование.
2. Народная теорема. Примеры повторяющихся игр: обязательства и репутация.
3. Эксперимент: Повторяющаяся игра – ультиматум Зельтена.

Тема: Эволюционые игры >>

1. Эволюционно-устойчивое равновесие и его связь с другими усилениями.
2. Эволюция стратегий во времени: репликаторная динамика в непрерывном и дискретном случае.
3. Динамика мнимых ходов
4. Динамика наилучшего ответа.
5. Приложения эволюционных игр: рынки сбережений, формирование социальных норм.

Тема: Динамические игры с неполной информацией >>

1. Понятие о типах и равновесие по Байесу-Нэшу.
2. Последовательное равновесие.
3. Примеры: дуополия Курно и Бертрана с неполной информацией. Сигнальная игра на рынке труда.

Тема: Равновесия в динамических играх >>

1. Игры в развернутой и нормальной формах: интерпретация Кохберга-Мертенса. Примеры.
2. Самоподтверждающееся равновесие.

Тема: Знание и игры >>

1. Информация и знание.
2. Функция знания: аксиоматика и теория рационального вывода.
3. Общее знание.

Тема: Элементы теории контрактов >>

1. Воплощение решений (implementation) и задачи теории контрактов.
2. Принцип соответствия Майерсона.
3. Скрытая информация и скрытое действие. Участие и совместимость по стимулам.
4. Примеры: механизм Кларка-Гроувса.
5. Эксперимент: акуционы.

Тема: Экономическая теория регулирования >>

1. Основные парадигмы теории регулирования: Дюпюи, Рамсей, Коуз, Буате, Аверх-Джонсон.
2. Проблема асимметричной информации и извлечение ренты – подход Лаффона-Тироля.
3. «Захват» регулирующего органа (regulatory capture).
4. Примеры в условиях переходной экономики: регулирование естественных монополий.

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

Слово «игра» не должно вводить в заблуждение. Это понятие в теории игр трактуется шире, чем в повседневной жизни. Ситуация стратегического взаимодействия может быть описана в виде модели, которую и называют игрой. Таким образом, в теории игр игрой будет считаться не только игра в шахматы, но и голосование в Совете Безопасности ООН, и торг продавца с покупателем на рынке.

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

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

Сначала по реальной жизненной ситуации нужно построить формальную модель. Как правило, в модели нужно отразить три основные характеристики жизненной ситуации: кто взаимодействует друг с другом (такие агенты в теории игр называются игроками), какие решения могут принимать игроки и какие платежи они в результате этого взаимодействия получают. Формальная модель и называется игрой.

Как только мы построили игру, ее нужно каким-то образом решить. На этой стадии мы полностью абстрагируемся от реальности и изучаем исключительно формальную модель. Как устроено решение модели? Мы должны зафиксировать концепцию поведения игроков в игре, то есть принципы принимаемых ими решений. Как только мы зафиксировали эту концепцию, мы можем постараться с ее помощью решить игру, то есть предъявить исход, которым закончится игра.

С помощью разных теоретико-игровых концепций можно решать разные классы игр. Один из самых красивых теоретических результатов теории игр доказывает, что в некотором очень широком классе моделей можно гарантированно найти решение. Я имею в виду результат Джона Нэша, полученный им в 1950 году: в любой конечной игре в нормальной форме можно всегда найти по крайней мере одно равновесие в смешанных стратегиях. Хронологически это была первая универсальная теоретико-игровая концепция, которая позволяет гарантированно найти решение в очень широком классе моделей.

В отличие от представителей социальных наук, математиков-игровиков больше интересуют внутренние свойства игр и концепций их решения. Именно благодаря таким теоретическим результатам мы можем быть уверены в том, что, строя и решая ту или иную теоретико-игровую модель, мы в итоге получим решение с необходимыми свойствами.

Конечно, Джон Нэш не является единоличным автором теории игр. Теория игр как самостоятельная наука начала развиваться чуть раньше, в начале ХХ века. Первые попытки формально определить игры, стратегии игроков и концепции решения игр восходят к именам Эмиля Бореля и Джона фон Неймана. Однако именно Нэш предъявил концепцию равновесия, которая позволяет гарантированно найти решение в конечных играх. В честь автора теоремы о существовании равновесия в смешанных стратегиях в конечных играх это равновесие стали называть равновесием Нэша.

Врученная в 1994 году первая Нобелевская премия за результаты в области теории игр (Джону Нэшу, Райнхарду Зелтену и Джону Харсаньи) фактически утвердила статус теории игр как самостоятельного научного направления со своими задачами и методами их решений. Последовавшие за этим еще несколько Нобелевских премий вручались как за фундаментальные теоретико-игровые результаты, так и за приложения теории игр к той или иной стороне нашей жизни. В ведущих университетах мира на программах и по экономике, и по политическим наукам теория игр обязательно входит в стандартный набор курсов. Часто ее изучают и психологи, и математики.

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

Тем не менее всегда открываются новые интересные направления исследований и в самой теории игр. Так, благодаря развитию вычислительных технологий появились новые теоретико-игровые концепции, учитывающие возможности и ограничения вычислительных машин. Благодаря им появилась возможность решать новые задачи. Результат 2015 года о равновесии в одной из версий покера, полученный Боулингом, Берчем, Йохансоном и Таммелином, - замечательный пример использования современных теорий и технологий.

Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры.

Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр.

В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.

Информационные ресурсы

• Захаров А.В.
  Теория игр в общественных науках. М.: препринт НИУ ВШЭ, 2014
  Данилов В.И., Лекции по теории игр. М.: препринт РЭШ, 2002
• Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В.
  Теория игр, Санкт-Петербург (БВХ-Петербург) 2012 г.
• Мазалов В.
  Математическая теория игр и приложения, Санкт-Петербург, Лань, 2010 г.
• Меньшиков И. Лекции по теории игр и экономическому моделированию, М.: Контакт Плюс 2010 г.
• Губко М., Новиков Д.
  Теория игр в управлении организационными системами, М: Синтег, 2002 г.

Требования

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

Программа курса

1. Позиционные игры
Дерево игры. Выигрышные и проигрышные позиции. Существование выигрышной стратегии у одного из игроков. Игра «ним» и выигрышные стратегии в ней.

2. Статические игры
Статические игры: игроки, стратегии, платежи. Примеры игр: «дилемма заключённого», «семейный спор», «пенальти». Доминирующие и доминируемые стратегии. Решение игр по доминированию. Понятие равновесия Нэша. Несоответствие равновесия и оптимума. Смешанные стратегии. Смешанное равновесие Нэша. Равновесие в игре «пионеры и вожатый». Приложения равновесий Нэша в экономике. Модели олигополий Курно и Бертрана. Статические игры с неполной информацией. Равновесие Байеса-Нэша.

3. Динамические игры
Динамические игры с полной информацией. Равновесие Нэша, совершенное на подыграх, и его соотношение с обычным равновесием. Теорема Куна. Динамические игры с неполной информацией. Информационные множества. Условие совершенной памяти. Равновесие Байеса. Игры сигнализирования. Смешивающее и разделяющее равновесия. Повторяющиеся игры.

4. Кооперативные игры
Кооперативные игры с трансферабельной полезностью. Определение игры, доступные дележи, ядро и вектор Шепли. Игра «Аэропорт». Устойчивые паросочетания. Алгоритм Гейла-Шепли.

5. Приложения теории игр
Механизмы голосования. Требования к ним. Теорема Эрроу о невозможности построения неманипулируемой системы выборов. Концепция рекуррентной устойчивости. Модель Асемоглу-Егорова-Сонина внутренней устойчивости авторитарных систем. Элементы теории аукционов. Равновесные стратегии в аукционах первой и второй цены.

Результаты обучения

В результате изучения дисциплины студент должен:

• знать:
  • классификацию игр;
  • основы моделирования розыгрышей игр;
  • основные принципы решения игр;
• уметь:
  • применять имеющиеся знания для решения практических задач
  • применять новые технологии анализа экономических систем;
• иметь представление:
  • о формировании стратегий, платежах, цене игры;
  • об основах рационального поведения, правилах справедливого дележа;
  • о взаимосвязи дисциплины с другими смежными дисциплинами;

Формируемые компетенции

• способность к восприятию, обобщению, анализу информации, постановке цели и выбору путей её достижения (ОК-6)
• способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-11)
• способность использовать основные положения и методы гуманитарных и социально-экономических наук при решении профессиональных задач (ПК-12)

теории игр , были сделаны биологами, рассматривавшими теорию естественного отбора и поведения животных; поведение было, разумеется, эгоистическим. Классический труд Рональда Фишера содержит многие методы теории игр , а уже после математического оформления этой теории эстафету принял Джон Майнард Смит . Математически же теорию игр оформил Джон фон Нейман: сначала в статьях 1920-х годов , а затем в книге с Оскаром Моргенштерном , с которой, наверное, и нужно вести историю теории игр как развитого математического аппарата. Учебники по теории игр мы здесь пересказывать не будем, цель этой книги совершенно другая; мы просто изложим вкратце некоторые вещи из теории игр , без которых нам совсем уж не обойтись. А если читатель заинтересуется теорией игр всерьез, рекомендуем ему учебники [ , , , , ].

Дадим формальное определение игр, которые мы будем рассматривать. Кстати, шахматы или даже го не будут подпадать под это определение . Что и логично: мы тут математикой занимаемся, а не эффективными алгоритмами; а с математической точки зрения (да и с точки зрения теории сложности алгоритмов, асимптотической по своей природе) шахматы или го совершенно неинтересны: на конечной доске с конечной продолжительностью партии и с полной информацией выигрышную (или беспроигрышную, если выигрышной нет) стратегию можно "легко" подсчитать простым перебором вариантов.

Игры, которые будем рассматривать мы, тоже обычно подразумевают конечное (или в теории непрерывное, но в реальности все равно конечное, как множество возможных цен, которые игрок может объявить на аукционе) множество возможных стратегий. Но при этом информация принципиально будет неполной; об этом и вся теория. В нашем понимании стратегической игры все игроки будут действовать одновременно, и выигрыш каждого будет зависеть от того, какие стратегии изберут все остальные.

Определение 1.1 .Стратегическая игра - это тройка

где обозначения расшифровываются следующим образом:

Нас будут больше интересовать не действия, а стратегии. Стратегия - это то, как агент выбирает свое действие. В началах теории игр это одно и то же, но в теории экономических механизмов мы будем рассматривать стратегии, представляющие собой вероятностные распределения на действиях или функции, которые принимают во внимание еще и какую-либо дополнительную информацию.

Есть и еще одно важное замечание: в течение этой лекции мы предполагаем, что у участников есть предпочтения по поводу исходов игры и эти предпочтения можно выразить при помощи функций . Это далеко не всегда так, и в "Теоремы Эрроу и Гиббарда-Саттертуэйта" мы еще поговорим об интересных эффектах, возникающих, когда предпочтения так выразить нельзя. Но для базовой теории игр придется это предположение все-таки сделать.

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

Пример 1.1 . Первый пример возьмем совсем уж из детства - рассмотрим классическую игру "камень-ножницы-бумага" 2Хотя насчет детства еще можно поспорить: в США вот недавно появилась аж целая ассоциация, посвященная игре в " Rock , Paper , Scissors " под логичным названием USARPS. Призы неплохие - можете попробовать свои силы на сайте http://www.usarps.com/ . . Камень побеждает ножницы, ножницы побеждают бумагу, бумага - камень. У игры получается вот какая матрица (где означает победу того игрока, чьи стратегии выписаны слева, а - победу игрока, стратегии которого стоят в первой строке):

Конец примера 1.1 .

Пример 1.2 . В качестве второго примера рассмотрим классическую игру полковника Блотто [ , ]. Полковник Блотто должен распределить свои силы ( солдат) между несколькими участками поля боя ( участков). Его противник должен сделать то же самое (количество его солдат может отличаться). Выигрывает тот, кто победит на большем количестве участков боя.

Например, пусть участков боя в игре три, причем и Блотто, и его противник располагает тремя солдатами. Тогда множество стратегий у обоих участников сражения состоит из следующих элементов:

(3,0,0), (2,1,0), (2,0,1), (1,2,0), (1,1,1), (1,0,2), (0,3,0), (0,2,1), (0,1,2), (0,0,3).

В результате у этой игры получается вот какая матрица . Здесь стратегии Блотто изображены слева, противника - сверху; означает, что победил Блотто, - что противник, - случилась ничья.

Конец примера 1.2 .

Отметим, что в играх из примеров 1.1 и 1.2 прибыль одного участника строго равнялась убытку второго. Такие игры называются играми с нулевой суммой ; формально говоря, в таких играх для любого профиля действий участников верно, что .

В дальнейшем нас будут интересовать не только игры с конечными множествами стратегий, но и игры с непрерывными такими множествами. Возьмем классический пример - конкуренцию по Курно (Cournot competition) 3Этот пример действительно восходит к классику экономической теории Антуану Огюстену Курно .

Рис. 1.1.

Пример 1.3 . Рассмотрим рынок некоего продукта, на котором находятся ровно две фирмы: . Стратегия каждого из участников - количество продукта, которое он производит: .