Теория игр. Методы решения

Впервые математические аспекты и приложения теории были изложены в классической

книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение.

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

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

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

игроками, набором стратегий для каждого игрока и указания выигрышей, или

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

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

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

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

с постоянной суммой, то есть таких, где игроки не могут

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

В такой игре участники знают все ходы, сделанные до текущего

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

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

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

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

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

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

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

и то же время на сходных преступлениях. Есть основания полагать,

что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку:

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

что одна из них содержит деньги, другая — товар. Каждый

игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку.

равновесия, а дорогое равновесие лучше незащищенности.
Равновесие двух противников может

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

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

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