Теория игр

Джон Нэш — математик, лауреат премии по экономике памяти Альфреда Нобеля

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

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

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

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

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

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

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

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

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

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

Основная статья: Развёрнутая форма игры

Игра «Ультиматум» в развёрнутой форме

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

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

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

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

	Игрок 2 стратегия 1	Игрок 2 стратегия 2
Игрок 1 стратегия 1	4, 3	–1, –1
Игрок 1 стратегия 2	0, 0	3, 4
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

Основная статья: Нормальная форма игры

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

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

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

Основная статья: Кооперативная игра (математика)

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

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

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

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

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

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

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

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

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

Типы игр

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

Основные статьи: Кооперативная игра (математика) и Некооперативная игра

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

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

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

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

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

	А	Б
А	1, 2	0, 0
Б	0, 0	1, 2
Несимметричная игра

Основная статья: Симметричная игра

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

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

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

	А	Б
А	−1, 1	3, −3
Б	0, 0	−2, 2
Игра с нулевой суммой

Основная статья: Игра с нулевой суммой

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

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

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

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

Основная статья: Последовательная игра

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

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

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

См. также: Игра с совершенной информацией и Игра с полной информацией

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

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

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

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

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

Основная статья: Дифференциальные игры

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

Метаигры

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

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

Основная статья: Комбинаторная теория игр

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

См. также

• Теория принятия решений
• Антагонистическая игра
• Дифференциальные игры
• Игра преследования
• Сетевые игры
• Компьютерные шахматы
• Кооперативные стохастические игры
• Марковский процесс принятия решений
• Линейная частичная информация
• Дилемма заключённого
• Математическая теория игр и её приложения
• Матчинг

Литература

• Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. — М.: Наука, 1970 (англ. Theory of Games and Economic Behaviour, 1944).
• Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр: Учеб. пособие для ун-тов. — М.: Высш. шк., Книжный дом «Университет», 1998. — 304 с. — ISBN 5-06-001005-8, 5-8013-0007-4.
• Васин А. А., Морозов В. В. Теория игр и модели математической экономики. — М.: МГУ, 2005. — 272 с. ISBN 5-317-01388-7.
• Мазалов В. В. Математическая теория игр и приложения. — Санкт-Петербург - Москва - Краснодар: Лань, 2010. — 446 с. — ISBN 978-5-8114-1025-5.
• Позиционные игры / ред. Воробьёв Н. Н., Врублевская И. Н.. — Москва: Наука, 1967. — 522 с.