Академия. Теория игр. Неделя 1.

Наконец решился принять участие в проекте Вторая академия, организованном  @ontofractal. 

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

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

Для меня выбранная тема практически неизвестна, но вызывает профессиональный (и не только) интерес. Планирую использовать полученные знания при работе со своими учащимися.

"ЧТО НАША ЖИЗНЬ? ИГРА!"

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

Основы этой теории были заложены только в середине прошлого века, но молодая наука очень быстро доказала свою эффективность и сейчас является основным инструментом анализа в экономике. Не случайно, что в 1994, 2005, 2007 и 2012 годах Нобелевская премия в области экономики была присуждена за разработки именно по теории игр.

Сегодня мы рассмотри первый из одиннадцати разделов курса:

ВВЕДЕНИЕ В ТЕОРИЮ ИГР

Итак, что же такое теория игр?

Это наука о стратегических решениях так называемых агентов, то есть участников игры.

Тогда возникает следующий вопрос: а что означает "стратегическое решение"?

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

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

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

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

Рассмотренные примеры демонстрируют два типа стратегических взаимодействий: 

1) одновременные ("камень-ножницы-бумага") - агенты принимают решение одновременно и независимо друг от друга;

2) последовательные (торг на рынке) - агенты принимают решения по очереди с учётом предыдущих шагов своих противников.

Для работы со стратегическими взаимодействиями мы будем придерживаться следующего алгоритма: 

1) переводим исходную реальную ситуацию на язык игры,

2) работаем с формальным описанием игры,

3) получаем стратегическое решение в рамках игры.

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

ПРИМЕРЫ СТРАТЕГИЧЕСКИХ ВЗАИМОДЕЙСТВИЙ

1. Поступление в ВУЗ. Абитуриент Петя получил на ЕГЭ не очень высокие баллы, но хочет поступить на бюджетное место в хорошее учебное заведение. Он может подать документы одновременно в пять ВУЗов. Если он подаст их в пять престижных институтов, то скорее всего он никуда не поступит (со своими баллами). Поэтому Петя принимает стратегическое решение: изучает результаты приёмных кампаний прошлых лет и выбирает учебные заведения, куда его возьмут с его баллами. Затем он подаёт документы в разные по степени престижности ВУЗы. Если ему повезёт - он попадёт в какой-нибудь топовый университет, если не повезёт - он всё равно поступает. То есть, по-любому, Петя в выигрыше.

2. Футбольный турнир. Реальная ситуация, имевшая место быть в 1994 году в Тринидад и Тобаго. Здесь проходил футбольный турнир, и в одной из групп оказались три сборные: Барбадоса, Гренады и Пуэрто-Рико. Правила турнира:

- в следующий этап выходит один победитель из группы,

- если у команд одинаковое количество очков, победитель определяется по результатам их личных встреч,

- если и здесь количество очков одинаково, то учитывается разница между забитыми и пропущенными мячами,

- если матч заканчивается ничьей, то назначается дополнительно время с правилом "золотого гола" - кто забивает первым, тот и победил,

- мяч, забитый в дополнительное время засчитывается за два мяча.

Турнирная таблица после первых двух матчей выглядела следующим образом:

Осталось сыграть сборным Гренады и Барбадоса. Пуэрто-Рико все матчи уже отыграла, у неё 3 очка и -1 в мячах. У Гренады тоже есть 3 очка и личная победа над Пуэрто-Рико. Значит, чтобы Пуэрто-Рико могла выйти в следующий круг, нужно чтобы Гренада проиграла Барбадосу с разницей мячей в -3. Но тогда у Барбадоса будет тоже 3 очка и разность мячей +2. То есть Пуэрто-Рико - уже пролетела. Каковы шансы Барбадоса?  Ему надо победить, набрав 3 очка с разницей мячей +2. А что надо Гренаде? Конечно же выиграть или в худшем случае проиграть, но с разницей мячей не более чем -1.

К концу основного времени счёт на табло 2:1 в пользу Барбадоса. Эта ситуация устраивает Гренаду, но не устраивает Барбадос - ему нужна победа с разницей мячей +2. Время уходит, счёт не меняется. Тогда игрок Барбадоса принимает гениальное стратегическое решение - он забивает гол в свои ворота, счёт становится 2:2 и дело идёт к дополнительным 30 минутам, когда шансов забить победный гол у команды будет значительно больше, чем в оставшееся основное время, а разница мячей будет +2 в пользу Барбадоса. 

Однако в Гренаде тоже не лаптем щи хлебают. Они понимают, что если они успевают до конца основного времени забить один мяч, то - выходят в следующий круг. Причём не важно в чьи ворота они его закатят, в свои (3:2) или в чужие (2:3). По разнице мячей они по-любому выходят из группы дальше. Это же понимают и в штабе Барбадоса. И дальше начинается не совсем обычный футбол: игроки Гренады пытаются забить мяч в любые ворота, а игроки Барбадоса защищают и свои ворота и ворота противника. Судьи ошалевают, болельщики веселятся.

КЛАССЫ ИГР

Как же формально описывать стратегические взаимодействия на языке теории игр?

1. Игры в нормальной форме. Данный вид формализации базируется на трёх "китах":

- множество всех игроков,

- множество всех возможных стратегий каждого игрока,

- множество всех возможных платежей каждого игрока

Для каждого из "китов" введём следующие обозначения:

В качестве примера игры в нормальной форме рассмотрим так называемую "Битву полов". Муж и жена одновременно и независимо друг от друга решают как им вместе провести выходной. Для мужа предпочтительнее пойти на футбол (платёж +1) вместе с женой (платёж +4), жене - пойти на балет (платёж +1) вместе с мужем (платёж +4). Формализуем условие.

Все конечные игры в нормальной форме можно представить в виде матрицы, содержащей все возможные стратегии им платежи игроков.

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

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

Например, студент (С) пришёл сдавать экзамен, но не может решить задачу. Он может попытаться списать решение (платеж +3), но тогда его могут удалить с экзамена (платёж -5). А может не списывать, но тогда он не решит задачу (платёж 0). Преподаватель (П), видя, что студент списывает может удалить его с экзамена (платёж 0) или не удалить, позволив списать, что противоречит принципам преподавателя (платёж -2). Но так же преподаватель может и пожалеть студента, глядя на его мучения, и подсказать решение (платёж 0) или не подсказать (платёж +2). Дерево игры в этом случае будет выглядеть так: 

Итак, классификацию игр можно графически представить себе следующим образом:

         

ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА

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