Теория игр за 15 минут

Многие из вас, я уверен, слышали о теории игр в какой-то момент своей жизни. Если вы хотите выглядеть умным и произвести впечатление на свою девушку — просто упомяните «игру с нулевой суммой» или «эволюционную стратегию», и ваши шансы отвести её домой сегодня вечером только что подскочили на 50%. Или вы можете использовать теорию игр, чтобы принимать решения в инвестировании своих денег (чтобы их полностью потерять и разориться) или, например решая, на какой девушке жениться (что также очень вероятно вас разорит). Как видите, это очень полезная теория.

Чтобы казаться умным - достаточно выучить эти пару выражений, но чтобы на самом деле что-то понимать - придется разобраться. Оказывается, это не так уж сложно и довольно интересно. Давайте посмотрим.

---

Первое упоминание, которое можно связать с теорией игр, находится в трудах Чарльза Вальдегрейва, математика 18 века. Он разработал стратегию для карточной игры вдвоем под названием «Le Her». Судя по названию, он тоже пытался впечатлить какую-то женщину. Правила игры были утеряны в истории, но основа была заложена.

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

Большинство терминов теории взято непосредственно из игр. Участников называют игроками, а каждое действие — ходом.

Реальный мир очень сложен, поэтому теория игр имеет дело с моделями (знаю вы начали представлять себе красоток в бикини — но я имею в виду упрощенные структуры, представляющие процессы реального мира).

Рациональность

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

Кейнсианский конкурс красоты

Более практичным примером является Кейнсианский конкурс красоты, предложенный очень известным экономистом Джоном Мейнардом Кейнсом, который также известен созданием МВФ и Всемирного банка и тем, что имел русскую жену. Так что, очевидно, он был неглупым человеком. Он сравнил фондовый рынок (еще одно выражение, упоминание которого увеличивает ваши шансы на горячую ночь)  с конкурсом красоты, но не таким где просто выбрать самую красивую девушку. Нет, это было бы слишком просто. Вместо этого нужно угадать девушку, которую все остальные считают самой красивой.

Таким образом, в этом «экономическом» конкурсе красоты речь идет не о поиске акций с наилучшей ценностью. Вместо этого речь идет о том, чтобы угадать, какую акцию все остальные считают самой привлекательной. Это игра второго уровня мышления: вы пытаетесь перехитрить толпу, которая пытается перехитрить толпу. Это как играть в шахматы с зеркалами — каждый ход отражает несколько слоев стратегии. Инвесторы наблюдают друг за другом с хитрой улыбкой, думая: «Я знаю, что ты знаешь, что я знаю...».

Точка зрения Кейнса подчеркивает иронию рынков: часто успех в инвестировании не связан с оценкой фундаментальных ценностей. Вместо этого он связан с прогнозированием коллективной психологии. 

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

Есть более простая версия того же мысленного эксперимента, предложенная Ричардом Таллером: игра «Угадай 2/3 от среднего». Участникам игры предлагается выбрать число от 0 до 100. Цель состоит в том, чтобы угадать, какой будет 2/3 от среднего всех предположений участников. Если все в игре абсолютно рациональны и знают, что все остальные тоже абсолютно рациональны, логика такова:

Самое высокое возможное среднее значение — 100,

так что 2/3 от этого составляет 66,67.

Но если все остальные тоже это рассчитают — новое среднее значение, которое следует учитывать, будет 66,67, и 2/3 от этого примерно 44,44.

Этот итеративный процесс продолжается, теоретически спускаясь до нуля, так как это единственное равновесие в игре полностью рациональных игроков.

Газета Financial Times провела этот эксперимент в действительности, и среднее значение оказалось 19. Вот вам и рациональность. Так что на самом деле игроки обладают «ограниченной рациональностью». Не будем рисковать быть сожжеными на костре за спекуляции чем ограниченна эта рациональность, но позвольте мне указать на существование пузырей — верха рациональной иррациональности.

Игры с одновременными ходами

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

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

Задача: Каждая компания должна решить, установить высокую или низкую цену.

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

Возможные сценарии:

• Обе выбирают высокие цены: Если обе компании A и B устанавливают высокие цены, они получают высокую прибыль с каждой продажи, но общий спрос может быть ниже.

• Обе выбирают низкие цены: Если обе устанавливают низкие цены, спрос на их продукты может увеличиться, но прибыль уменьшается.

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

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

Равновесие Нэша

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

Рассмотрим пример: представьте, что Алиса и Боб каждые выходные смотрят фильмы вместе. Алисе нравятся комедии, в то время как Бобу - боевики. Однако оба они согласны смотреть документальные фильмы, хотя они им не так сильно нравятся.

Вот как разворачивается их вечер:

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

Если оба выберут один жанр - они смотрят этот жанр.

Если Алиса выбирает комедию, а Боб - боевик, они ничего не смотрят и идут мыть посуду (оба проигрывают). 

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

Дилемма заключённого

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

Вот суть:

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

Допрос: полиция разделяет Алису и Боба, предлагая каждому одно и то же: если один даст показания против другого и другой останется молчать, сдавший будет освобожден, а не сотрудничающий получит тяжелый приговор (например, 10 лет). Если оба останутся молчать, они оба будут осуждены по менее тяжкому обвинению и получат умеренный приговор (например, по 2 года каждый). Если оба предадут друг друга, они оба получат значительный приговор (например, по 5 лет каждый).

Дилемма: дилемма возникает, потому что у каждого заключенного есть два варианта, ни один из которых он не может с уверенностью выбрать, не зная решения другого. Оптимальный исход для обоих - оставаться молчаливыми, что приведет к общему сроку в тюрьме в 4 года. Однако страх того, что другой может сдать и оставить их нести тяжелый приговор, часто приводит каждого к сдаче подельника, в результате чего общий срок в тюрьме составляет 10 лет. В теории игр говорят, что стратегия "сдачи" доминирует над другими.

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

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

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

Классический пример - паника в банках. Существует два равновесия: одно, где все доверяют банку и оставляют свои деньги там (нет паники), и другое, где все сомневаются в банке и пытаются снять свои деньги, создавая состояние, называемое “самоисполняющимся пророчеством”, приводящее к краху банка. Условие отсутствия паники стабильно до тех пор, пока есть доверие к банку, но если люди видят длинную очередь перед банком для снятия денег, они тоже будут пытаться забрать средства. Наблюдая за действиями других участников игроки координируют свои действия.

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

Игры со смешанной стратегией

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

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

Повторяющиеся игры против одноразовых игр

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

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

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

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

Эволюционная теория игр

Как вы помните из начала, классическая теория игр рассматривает всех участников как рациональных. Но были люди, которые видели, что это явно не так. Джон Мейнард Смит и Джордж Прайс (видимо после очередной встречи со британскими учеными), высказали противоположное мнение. Они сказали, что во много поведение людей и животных социально и генетически запрограммированы. Их игра Ястребы против Голубей до сих пор является основным принципом эволюционной биологии. Эта игра подчеркивает важность эволюционной стабильности.

В этой игре Ястребы всегда будут драться за доступные ресурсы, а Голуби будут демонстрировать готовность к борьбе, но на самом деле уступят. Допустим, потенциальная эволюционная ценность (для выживания особи) ресурса составляет 100 очков:

Если Голубь сталкивается с Ястребом - Голубь всегда улетит, так что результат всегда:

Ястреб: 100, Голубь: 0

Если Голубь сталкивается с другим Голубем - один из них улетит, с 50% вероятностью. В среднем каждый из них получит 50% награды (т.е. награду в 50% случаев), так что результат:

Голубь 1: 50, Голубь 2: 50

Если Ястреб сталкивается с Ястребом - они будут драться, и один выиграет, другой проиграет. Кроме того, оба могут быть ранены в драке и получить штраф на выживание (что по сути является стоимостью конфликта). В среднем они выиграют в 50% случаев, так что средний результат:

Ястреб 1: (100 - штраф)/2, Ястреб 2: (100 - штраф)/2

Что если стоимость конфликта меньше, чем награда? Тогда для рационального игрока единственно рациональная стратегия - стратегия Ястреба, и будет много драк. Давайте посмотрим на пример, где штраф составляет 40, а награда - 100:

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

Но если стоимость конфликта выше, чем награда - ситуация меняется. Допустим, штраф составляет 120:

Ой.. Теперь все зависит от того, сколько Ястребов в популяции. Если их слишком много - будет много боев с смертельным исходом, так что быть Ястребом не весело, и быть Голубем - лучшая стратегия. Давайте назовем шанс встретить Ястреба p, тогда шанс встретить Голубя равен (1- p). Тогда эволюционная пригодность Голубя:

dove_fittness = (p * 0) +        # награда против Ястреба
                (1 - p)*(100/2)  # награда против Голубя

или

dove_fittness = 50 - 50p

И для Ястреба:

hawk_fittness = p*((100 - 120)/2) + # награда против Ястреба
                (1 - p)*100         # награда против Голубя

или

hawk_fittness = 100 - 110p

Таким образом, быть Ястребом имеет смысл только если: hawk_fittness > dove_fittness, или:

100 - 110p > 50 - 50p

или

p < 5/6

Следовательно, если в популяции меньше 5/6 Ястребов - лучше быть Ястребом. Так что оптимальная пропорция Ястребов будет близка к 5/6, а Голубей - к 1/6, что приведет к эволюционному равновесию. Животные не рациональны в обычном смысле, но это равновесие равносильно равновесию Нэша, как если бы они были рациональны.

Ничто не длится вечно, как мы знаем от древних мудрецов из Guns N' Roses, так что изменения в окружающей среде будут постоянно сдвигать стоимость конфликта, и пропорция Ястребов и Голубей будет меняться.

Игры с последовательными ходами

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

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

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

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

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

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

Возвращаясь к нашему предыдущему примеру с Бобом и Алисой:

Алиса начинает, выбирая между "Смотреть комедию" (ее лучший выбор), "Смотреть боевик" (ее менее предпочтительны выбор) или "Ничего не делать" (наименее предпочтительный).

Если Алиса выбирает фильм, тогда Боб решает "Присоединиться" или "Ничего не делать".

Награды распределяются следующим образом:

• Если они смотрят фильм вместе, они получают награды (Алиса получает 100 за комедию и 50 за боевик; Боб получает 100 за боевик и 50 за комедию).

• Если оба выберут "Ничего не делать", награда для каждого будет 0.

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

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

Игры с асимметричной информацией

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

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

Типы асимметричной информации:

Скрытные действия: Также известные как "moral hazard", где действия одного игрока не видны другими. Например, работодатель не может идеально контролировать усилия и работу сотрудника, и тот начинает симулировать работу.

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

Примеры:

• Рынок страхования: Страховые компании часто сталкиваются с асимметричной информацией, так как они могут не знать истинного состояния здоровья или профиля риска своих клиентов.

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

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

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

Рынок "лимонов"

Асимметричная информация может привести к сбою рынка и последующем регулировании, как это видно на классическом примере "рынка лимонов" Джорджа Акерлофа. Продавцы подержанных автомобилей знают, является ли их автомобиль персиком (хорошим) или лимоном (плохим), но покупатели, к сожалению, не обладают экстрасенсорными способностями. Они оценивают все машины как гибриды полулимона, полуперсика, предлагая цену, которая где-то посередине. Продавцы персиков не в восторге от этих низких предложений и вынуждены вывести свои автомобили с рынка, оставляя его заваленным лимонами. Результат? Фруктовый салат, который никто не хочет покупать.

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

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

Групповые решения

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

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

Всем хорошего дня. Если у вас есть вопросы или уточнения - пишите в разделе комментариев.