Теория игр

2022-06-01 20:11

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

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

История

Оптимальные решения или стратегии в математическом моделировании предлагались ещё в XVIII в. Задачи производства и ценообразования в условиях олигополии, которые стали позже хрестоматийными примерами теории игр, рассматривались в XIX в. А. Курно и Ж. Бертраном. В начале XX в. Эмануил Ласкер, Эрнст Цермело и Эмиль Борель выдвигают идею математической теории конфликта интересов.

Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior).

Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Форбса Нэша, лауреата премии по экономике памяти Альфреда Нобеля и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума». Некоторые американские телевизионные шоу, например, «Friend or Foe?», «Alias» или «NUMB3RS», периодически ссылаются на теорию в своих эпизодах.

Джон Нэш в 1949 году пишет диссертацию по теории игр, через 45 лет он получает Нобелевскую премию по экономике. Нэш после окончания Политехнического института Карнеги с двумя дипломами — бакалавра и магистра — поступил в Принстонский университет, где посещал лекции Джона фон Неймана. В своих трудах Нэш разработал принципы «управленческой динамики». Первые концепции теории игр анализировали антагонистические игры, когда есть проигравшие и выигравшие за их счёт игроки. Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу», или «некооперативное равновесие», в ситуации стороны используют оптимальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение. Эти работы Нэша сделали серьёзный вклад в развитие теории игр, были пересмотрены математические инструменты экономического моделирования. Нэш показывает, что классический подход к конкуренции А. Смита, когда каждый сам за себя, не всегда оптимален. Более выгодны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.

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

В 1960—1970 гг. интерес к теории игр угасает, несмотря на значительные математические результаты, полученные к тому времени. С середины 1980-х гг. начинается активное практическое использование теории игр, особенно в экономике и менеджменте. За последние 20 — 30 лет значение теории игр и интерес к ней значительно растёт, некоторые направления современной экономической теории невозможно изложить без применения теории игр.

Исторически первыми в сферу интересов математиков попали игры с полной информацией, в которых относительно просто анализировать стратегию всех участников. Затем внимание исследователей привлекли «игры с неполной информацией». Проанализировав покер и остальные игры этого класса, математики попробовали применить математический аппарат к играм «глобального масштаба» — войнам, экономике и даже к обычным разводам.

Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако математический аппарат теории игр затратен[4]. Его применяют для оправданных задач: политика, экономика монополий и распределения рыночной власти и т. п. Ряд известных учёных стали Нобелевскими лауреатами по экономике за вклад в развитие теории игр, которая описывает социально-экономические процессы. Дж. Нэш, благодаря своим исследованиям в теории игр, стал одним из ведущих специалистов в области ведения «холодной войны», что подтверждает масштабность задач, которыми занимается теория игр.

Лауреатами премии по экономике памяти Альфреда Нобеля за достижения в области теории игр и экономической теории стали: Роберт Ауман, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Уильям Викри, Джеймс Миррлис, Томас Шеллинг, Джордж Акерлоф, Майкл Спенс, Джозеф Стиглиц, Леонид Гурвиц, Эрик Мэскин, Роджер Майерсон, Ллойд Шепли, Элвин Рот, Жан Тироль, Пол Милгром, Роберт Уилстон.

Представление игр

См. также: Список игр теории игр

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

наличие нескольких участников;
неопределённость поведения участников, связанная с наличием у каждого из них нескольких вариантов действий;
различие (несовпадение) интересов участников;
взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников;
наличие правил поведения, известных всем участникам.

Развёрнутая форма

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

На рисунке — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего, первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.

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

Нормальная форма

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

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

Характеристическая функция

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

Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N — количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой) представляется парой (N, v), где N — множество всех игроков, а v : 2N -> R — характеристическая функция.

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

Применение теории игр

Теория игр как один из подходов в прикладной математике применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения.

Описание и моделирование

Первоначально теория игр использовалась для описания и моделирования поведения человеческих популяций. Некоторые исследователи считают, что с помощью определения равновесия в соответствующих играх они могут предсказать поведение человеческих популяций в ситуации реальной конфронтации. Такой подход к теории игр в последнее время подвергается критике по нескольким причинам. Во-первых, предположения, используемые при моделировании, зачастую нарушаются в реальной жизни. Исследователи могут предполагать, что игроки выбирают поведения, максимизирующие их суммарную выгоду (модель экономического человека), однако на практике человеческое поведение часто не соответствует этой предпосылке. Существует множество объяснений этого феномена — нерациональность, моделирование обсуждения, и даже различные мотивы игроков (включая альтруизм). Авторы теоретико-игровых моделей возражают на это, говоря, что их предположения аналогичны подобным предположениям в физике. Поэтому даже если их предположения не всегда выполняются, теория игр может использоваться как разумная идеальная модель, по аналогии с такими же моделями в физике. Однако на теорию игр обрушился новый вал критики, когда в результате экспериментов было выявлено, что люди не следуют равновесным стратегиям на практике. Например, в играх «Сороконожка», «Диктатор» участники часто не используют профиль стратегий, составляющий равновесие по Нэшу. Продолжаются споры о значении подобных экспериментов. Согласно другой точке зрения, равновесие по Нэшу не является предсказанием ожидаемого поведения, оно лишь объясняет, почему популяции, уже находящиеся в равновесии по Нэшу, остаются в этом состоянии. Однако вопрос о том, как эти популяции приходят к равновесию Нэша, остаётся открытым. Некоторые исследователи в поисках ответа на этот вопрос переключились на изучение эволюционной теории игр. Модели эволюционной теории игр предполагают ограниченную рациональность или нерациональность игроков. Несмотря на название, эволюционная теория игр занимается не столько вопросами естественного отбора биологических видов. Этот раздел теории игр изучает модели биологической и культурной эволюции, а также модели процесса обучения.

Нормативный анализ (выявление наилучшего поведения)

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

Типы игр

Кооперативные и некооперативные

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

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

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

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

Симметричные и несимметричные

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

В примере справа игра на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так — ведь выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.

С нулевой суммой и с ненулевой суммой

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

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

Ещё игрой с отличной от нуля суммой может являться торговля, где каждый участник извлекает выгоду. Широко известным примером, где она уменьшается, является война.

Параллельные и последовательные

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

Различия в представлении параллельных и последовательных игр рассматривались выше. Первые обычно представляют в нормальной форме, а вторые — в экстенсивной.

С совершенной или полной информацией

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

Игры с бесконечным числом шагов

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

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

Дискретные и непрерывные игры

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

Метаигры

Это игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов.

Комбинаторная теория игр

Изучение последовательных игр с совершенной информацией и сравнительно сложными наборами возможных стратегий выделяют в отдельную область, называемую комбинаторной теорией игр (или теорией комбинаторных игр). Эта теория оперирует такими инструментами, как функция Шпрага — Гранди. В значительной степени эту область сформировали Джон Конвей, Элвин Берлекэмп и Ричард Гай в книгах «On Numbers and Games» и «Winning Ways for your Mathematical Plays».

Список игр теории игр

Список игр теории игр — теория игр изучает стратегии между лицами в ситуациях, называемых играми. Классам этих игр даны имена. Здесь приведен список наиболее часто изучаемых игр

Объяснение свойств

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

Число игроков: каждое лицо, делающее выбор в игре или получающее выгоду от этого выбора, является игроком.
Стратегий на игрока: в игре каждый игрок выбирает из множества возможных действий, которые известны как чистые стратегии. Если это число одинаково для всех игроков, оно указано в таблице.
Число чистых стратегий равновесия Нэша: равновесие Нэша — это множество стратегий, которые соответствуют смешанным лучшим ответам другим стратегиям. Другими словами, если каждый игрок играет свою часть равновесия Нэша, никто из игроков не имеет стимулов односторонне сменить свою стратегию. Если принять, что играют единственную стратегию без случайного выбора (чистые стратегии), игра может иметь любое число равновесий Нэша.
Последовательная игра: игра является последовательной, если один игрок делает свой ход после хода другого игрока. В противном случае игра является синхронной.
Полная информация: игра имеет полную информацию, если игра является последовательной и каждый игрок знает стратегии, выбранные игроками до этого хода.
Постоянная сумма: игра имеет постоянную сумму, если сумма плат каждого игрока та же самая для всех стратегий. В этих играх один игрок выигрывает только если другой теряет. Игры с постоянной суммой можно свести к играм с нулевой суммой путём вычитания постоянной величины из всех плат, оставляя относительные величины неизменными.

Список игр

Битва полов, Игры Блотто, Задача о делении торта, Стоножка, «Ястребы и голуби», Координационная игра, Олигополия Курно, Тупик,Диктатор, Дилемма обеда, Долларовый аукцион, Задача бара «Эль Фароль», Игра без значения, Угадать 2/3 среднего, Покер Куна, Орлянка,Задача о сделках, Игра в войну и мир, Игра «Пять пиратов», Дилемма заключённого, Общественные блага, Камень, ножницы, бумага, Игра отбора, Игра сигнализации, Охота на оленя, Дилемма путешественника, Дилемма доверия, Дилемма добровольца, Война на истощение, Ультиматум, Принцесса и Чудовище.

Игра с совершенной информацией

Игра с совершенной информацией (англ. game of perfect information) — игра, в которой игроки в ходе игры не сталкиваются ни со стратегической неопределённостью (когда бы игрок не знал ходы соперника в прошлом или одновременно с собственными ходами), ни с внешней неопределенностью (когда бы игрок не знал какие будут внешние обстоятельства). Таким образом, в игре с совершенной информацией каждый игрок в каждой точке, в которой наступает его очередь ходить, знает всю историю игры вплоть до этой точки, в том числе результаты любых действий, предпринятых «природой», или предыдущие действия других игроков, включая чистые стратегии и фактические результаты любых смешанных стратегий, которые они могут использовать в игре.

Определение

Согласно Авинашу Дикситу, игра c полной информацией — это игра, в которой все правила игры (стратегии игроков и выигрыши каждого из них как функции стратегий всех игроков) полностью известны всем игрокам, и более того, являются общим знанием. Игра с совершенной информацией — это игра, в которой игроки в ходе игры не сталкиваются ни со стратегической неопределённостью (когда бы игрок не знал ходы соперника в прошлом или одновременно с собственными ходами), ни с внешней неопределенностью (когда бы игрок не знал какие будут внешние обстоятельства). Таким образом, в игре с совершенной информацией каждый игрок в каждой точке, в которой наступает его очередь ходить, знает всю историю игры вплоть до этой точки, в том числе результаты любых действий, предпринятых «природой», или предыдущие действия других игроков, включая чистые стратегии и фактические результаты любых смешанных стратегий, которые они могут использовать в игре.

В своём учебнике А. Мас-Коллел, М. Уинстонruen и Д. Грин определяют игру c полной информацией как игру, в которой игроки обладают всей информацией друг о друге, информацией о выигрышах, которые они получат при различных исходах игры; а игру с совершенной информацией как игру, в которой каждое информационное множество содержит один узел решения.

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

Игра с полной информацией

Игра с полной информацией (англ. game of complete information — букв. — «игра с полной информацией») — теоретико-игровой термин, обозначающий игру, в которой игрокам известны функция полезности, правила игры, а также ходы других игроков. Примеры игр c полной информацией — шахматы и нарды; с неполной информацией — аукцион и покер.

Определение

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

Свойства

Если ни в каких аспектах игры (правилах, возможности или очерёдности ходов, определении момента завершения игры или результата) не участвует элемент случайности, такая игра будет ещё и детерминированной.

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

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

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

Дизайн механизмов

Определение

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

Дизайн механизмов (англ. mechanism design) — область исследования в экономической теории и теории игр, которая представляет собой подход создания механизмов и стимулов для достижения желаемых целей, где игроки действуют рационально, а действия экономических субъектов приводят к решению, оптимальному для функции социального выбора. Этот подход впервые был предложен Леонидом Гурвичем в 1960 году.

История создания

Леонид Гурвич в 1959—1960 годах впервые сформулировал основные положения экономических механизмов в своей статье «Оптимальность и информационная эффективность в процессах распределения ресурсов», в 1973 году сформулировал свойство правдивости, затем принцип выявления, а в 2006 году им совместно с Стэнли Райтером[en] была опубликована книга о дизайне механизмов «Дизайн экономических механизмов». Эрик Маскин разрабатывал в своих статьях за 1980—1984 года так называемую «теорию реализации»: как сделать такой протокол, чтобы он обладал нужными свойствами. А Роджер Майерсон в своих статьях за 1979—1985 года применил этот подход к аукционам. Шведская королевская академия наук наградила премией по экономике памяти Альфреда Нобеля за 2007 год Леонида Гурвича, Эрика Маскина и Роджера Майерсона за «создание основ теории оптимальных механизмов распределения ресурсов».

Функция Шпрага — Гранди

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

В случае дискретных игр иногда называется нимбером.

Теорема Шпрага-Гранди — это общий вывод из результатов, которые были независимо сформулированы и доказаны Р. Шпрагом (1935) и П. М. Гранди (1939). Она состоит в том, что для любой беспристрастной игры, где выигрывает сделавший последний ход, для каждой позиции однозначно определено значение функции Шпрага-Гранди, которое и определяет выигрышную стратегию либо её отсутствие.

Теория Игр и функция Шпрага-Гранди

https://habr.com/ru/post/124856/

Задача

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

Решение

Задача решается с конца. Рассмотрим варианты деления площади для всех случаев от 1 до 10 клеток, и найдем для них значения функции Шпрага-Гранди. Заметим, что для данной игры, в результате деления площади каждый раз на две новые площади, значение функции Шпрага-Гранди находится с помощью Ним-суммы.

Значение Шпрага-Гранди для n = 10 получается равным 0. Следовательно, игрок, делающий ход первым, проигрывает. При любом его ходе второй игрок переходит в позиции 4 + 4 или n = 1/2/7, значение Шпрага-Гранди для которых также равно 0.

Ответ

Выигрывает тот, кто ходит вторым.

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

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

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

До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Примеры использования понятия

Социология

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

В таблице слева приведена структура действия в терминах теории игр, составленная для двух действующих субъектов (акторов). Каждый актор имеет два варианта действия, обозначенных цифрами 1 и 2. Коэффициенты вознаграждения получаемые ими при выборе определённых вариантов действия указаны в соответствующих ячейках таблицы. Предположим, что в данный момент оба актора используют действие 2, а их вознаграждения соответственно равны нулю. Выбрав действие 1, актор A ухудшит собственную ситуацию на одну позицию (A: -1, B: +2). Аналогично актор B самостоятельно выбрав вариант 1, в то время когда актор A продолжает использовать действие 2, только ухудшит свою ситуацию (A: +2, B: -1). Таким образом, несмотря на то, что оба актора понимают, что оптимальным для них была бы ситуация, когда оба они используют действие 1 (вознаграждение — A: +1, B: +1), ни у одного из них нет мотива к изменению ситуации, а равновесие становится результатом отсутствия таких мотивов. Если система уже находится в оптимальном состоянии (когда оба актора выбрали действие 1), то у обоих из них всегда будет искушение начать использовать действие 2, которое принесёт им вознаграждение за счёт другого игрока. Этот пример иллюстрирует возможность существования двух социальных состояний: устойчивого, но неоптимального (оба актора используют вариант 2); а также второго оптимального, но неустойчивого (оба актора используют вариант 1).

Политология

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

Экономика

В отрасли имеются две фирмы № 1 и № 2. Каждая из фирм может установить два уровня цен: «высокие» и «низкие». Если обе фирмы выберут высокие цены, то каждая будет иметь прибыль по 3 млн. Если обе выберут низкие, то каждая получит по 2 млн. Однако, если одна выберет высокие, а другая низкие, то вторая получит 4 млн, а первая только 1 млн. Наиболее выигрышный в сумме вариант — одновременный выбор высоких цен (сумма = 6 млн). Однако это состояние (при отсутствии картельного сговора) нестабильно из-за возможности относительного выигрыша, которая открывается перед фирмой, отступившей от этой стратегии. Поэтому обе компании с наибольшей вероятностью выберут низкие цены. Хотя этот вариант и не даёт максимального суммарного выигрыша (сумма = 4 млн), он исключает относительный выигрыш конкурента, который тот мог бы получить за счёт отступления от взаимно-оптимальной стратегии. Такая ситуация и называется «равновесием по Нэшу».

Взаимное гарантированное уничтожение

Взаимное гарантированное уничтожение — военная доктрина времён холодной войны, согласно которой применение двумя противоборствующими сторонами оружия массового поражения приведёт к полному уничтожению обеих сторон, что делает бессмысленными любые попытки применения доктрины первого удара. В западном мире доктрина известна под термином Mutually Assured Destruction (англ. MAD, буквально «безумный»), введённым учёным Джоном фон Нейманом.

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

Теоретические основы

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

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

История

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

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

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

Этика

Известный футурист Герман Кан в своей книге «On Thermonuclear War» (1960) описал гипотетическую «машину Судного дня» (так называемую кобальтовую бомбу), которая иллюстрировала абсурдность возможности буквального применения военными доктрины взаимного гарантированного уничтожения. Кан при этом опасался, что американские военные воспримут эту идею всерьез и построят подобное устройство для ядерного шантажа СССР. Стоит отметить, что подобная система всё же была разработана в СССР (система «Периметр»), и служила в первую очередь для сдерживания вероятного противника.

Станислав Лем писал в «Фантастике и футурологии» (1970):

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

Проблемы доктрины

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

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

Среди главных проблем доктрины назывались:

Требование гарантирования ответного удара

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

Требование идеального обнаружения предупреждения

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

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

Требование рациональности сторон

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

Требование неспособности к обороне

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

Факторы, нарушающие доктрину

Противоракетная оборона

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

Противоракетная оборона не может быть абсолютной: всегда существует вероятность, что какое-то количество боеголовок пройдут оборону.
Чем меньше ракет будет запущено противником, тем больше эффективность противоракетной обороны.
Таким образом, в случае конфронтации — сторона, имеющая противоракетную оборону имеет стимул нанести удар первой и вывести из строя максимальное число ракет неприятеля до их запуска.
Сторона, не имеющая противоракетной обороны, но знающая о существовании таковой у неприятеля, должна учитывать её в своих расчетах.
Сторона, не имеющая противоракетной обороны, понимает, что противник (см. пункт 3) имеет стимул нанести первым удар.
Соответственно, сторона не имеющая противоракетной обороны, ТАКЖЕ имеет стимул нанести удар первой, чтобы опередить возможный превентивный удар противника.

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

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

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

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

Разделяющиеся боевые блоки индивидуального наведения

Баллистические ракеты с разделяющимися головными частями индивидуального наведения (далее — РГЧ ИН) воспринимались многими экспертами как потенциальная угроза для мировой стабильности и фактор, увеличивающий риск эскалации международных конфликтов. Проблема заключалась в том, что МБР, оснащенные РГЧ ИН значительно усиливали возможный удар без увеличения числа ракет как таковых; ввиду этого, ядерный арсенал становился значительно более концентрированным (вместо ввода в строй большого числа моноблочных ракет появилась более дешевая возможность ввода в строй небольшого числа ракет с РГЧ ИН) и более чувствительным к превентивному неприятельскому удару.

Эта ситуация описывалась двумя моделями:

Если обе стороны имеют по 100 моноблочных ракет, то агрессор, чтобы поразить ядерный арсенал оппонента (и нейтрализовать его ответный удар) должен нацелить каждую свою МБР на каждую ракету оппонента. При этом, по каждой МБР оппонента может быть нанесен всего один ядерный удар, что не гарантирует уничтожения всех атакованных МБР. Ракетный же арсенал агрессора будет полностью истощен этой единственной атакой.
Если обе стороны имеют по 100 ракет с разделяющимися головными частями индивидуального наведения (по 10 на каждой), то агрессор, чтобы поразить ядерный арсенал оппонента (и нейтрализовать его ответный удар) может направить всего половину своих ракет — 50 единиц, с 10 боеголовками каждая — против ядерного арсенала оппонента. За счет применения РГЧ ИН, агрессор может всего 50 ракетами атаковать 100 ракет оппонента, причем по каждой ракете оппонента будет нанесено по 5 ядерных ударов — что существенно повышает шансы на полное уничтожение ядерного арсенала оппонента. При этом агрессор сохраняет половину своего ракетного арсенала в резерве.

Таким образом, с одной стороны — массовое развертывание ракет с РГЧ ИН создает возможность для частичной либо полной нейтрализации ядерного арсенала оппонента превентивным ударом, тем самым подрывая основы доктрины гарантированного взаимного уничтожения.

С другой стороны — массовое развертывание ракет с РГЧ ИН обеспечивает возможность нанесения ответного ядерного удара даже небольшим числом ракет, и тем самым усиливают доктрину гарантированного взаимного уничтожения.

Таким образом, РГЧ ИН являются ещё одним элементом, вводящим доктрину в логический парадокс.

Подводные ракетоносцы

Подводные лодки, оснащенные баллистическими ракетами, были ещё одним фактором, нарушающим работу доктрины гарантированного взаимного уничтожения.

С одной стороны, ПЛАРБ являлись оптимальным средством нанесения ответного удара, так как наиболее эффективно обеспечивали рассредоточение и выживание стратегического ядерного арсенала при нападении противника.
С другой стороны, ПЛАРБ также являлись оптимальным средством нанесения первого удара, ввиду их способности занять скрытно позицию в непосредственной близости от территории неприятеля.
Кроме того, ПЛАРБ представляли угрозу неидентифицированных запусков; запуск ракет с ПЛАРБ не позволял по месту запуска установить принадлежность субмарины.

Приложение доктрины

Доктрина гарантированного взаимного уничтожения не была принята официально ни в США, ни в СССР. Хотя обе сверхдержавы декларировали готовность применить её в случае агрессии со стороны оппонента, на практике, в военных доктринах и США и СССР гарантированное взаимное уничтожение рассматривалось лишь как крайний случай; в основном, как средство удерживать противника от ядерных ударов против гражданского населения, а не как средство предотвращения агрессии вообще. Понимая ограничения и слабые места доктрины, обе стороны принимали более комплексный подход, в котором ответ на агрессию зависел от масштабов и конкретных методов агрессии. Например, в случае не-ядерной агрессии одной из сторон против другой, обороняющийся поначалу ответил бы конвенционными средствами и (в зависимости от ситуации) тактическими ядерными ударами против военных целей на поле боя, избегая сразу начинать эскалацию. Это обеспечивало сохранение возможности деэскалации конфликта и защиту гражданского населения.

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

Источник: m.vk.com

Теория игр

Комментарии: