Основные понятия теории игр

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

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

1. Интересы участников совпадают, и они могут догово­риться о совместных действиях;

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

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

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

Если во множественной игре интересы игроков сов­падают, то они могут объединяться, создавая коалиции. Такие игры называются коалиционными.

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

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

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

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

основные понятия теории игр - student2.ru игре участвуют два игрока. Каждый из них может записать независимо от другого цифры 1, 2 и 3. Ес­ли разность между цифрами, записанными игроками, положи­тельна, то первый игрок выигрывает количество очков, равное разности между цифрами, и, наоборот, если разность отрица­тельна, то выигрывает второй игрок. Если разность равна ну­лю, то игра заканчивается вничью.

У первого игрока три стратегии (варианта действия): А1(записать 1), А2 (записать 2), А3 (записать 3).

У второго игрока также три стратегии: B1, B2, В3 (табл. 33.1).

Задача первого игрока — максимизировать свой выигрыш.

основные понятия теории игр - student2.ru Задача второго игрока — минимизировать свой проигрыш или минимизировать выигрыш первого игрока.

Игру можно представить в виде матрицы, в которой стро­ки — стратегии первого игрока, столбцы — стратегии второго игрока, а элементы матрицы — выигрыши первого игрока. Та­кую матрицу называют платежной.

основные понятия теории игр - student2.ru Для данного примера платежная матрица имеет вид,

В общем случае парную игру с нулевой суммой можно за­писать платежной матрицей

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

Найдем наилучшую стратегию первого игрока: минималь­ное число а, в каждой строке обозначим αi (i = основные понятия теории игр - student2.ru ),

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru Зная αi, т.е. минимальные выигрыши при различных стра­тегиях Аi, первый игрок выберет ту стратегию, для которой αi максимально. Обозначим это максимальное значение через α, см. справа.

основные понятия теории игр - student2.ru Величина α — гарантированный выигрыш, который может обеспечить себе первый игрок, — называется нижней ценой игры (максимином).

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

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

Для матричной игры справедливо неравенство основные понятия теории игр - student2.ru

основные понятия теории игр - student2.ru Если α = β, то такая игра называется игрой с седловой точ­кой, а пара оптимальных стратегий (Аiопт, Bjопт) — седловой точкой матрицы. В этом случае элемент αij = v называется ценой игры, является одновременно минимальным в i-й строке и j-м столбце. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Решение игры рассмотренного выше, см. справа.

Так как α = β = 0, матрица игры имеет седловую точку.

Оптимальная стратегия первого игрока — А3, второго — В3. Из табл. 31.1 видно, что отклонение первого игрока от оп­тимальной стратегии уменьшает его выигрыш, а отклонение второго игрока от В3 увеличивает его проигрыш.

Если платежная матрица не имеет седловой точки, т.е. α < β, то поиск решения игры приводит к применению слож­ной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. Такая сложная стратегия называется смешанной.

основные понятия теории игр - student2.ru В игре, матрица которой имеет размерность т х п, стра­тегии первого игрока задаются наборами вероятностей = (x1, x2,... ,xт), с которыми игрок применяет свои чистые стратегии. Эти наборы можно рассматривать как m-мерные векторы, для координат которых:

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru Аналогично для второго игрока наборы вероятностей опре­деляют n-мерные векторы основные понятия теории игр - student2.ru = (y1, y2, … , yп), для координат которых:

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

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

Применение оптимальной стратегии может получить выигрыш, равный цене игры: a≤ v≤ b.

основные понятия теории игр - student2.ru Применение первым игроком оптимальной стратегии xiопт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры. Поэтому выполняется соот­ношение справа:

основные понятия теории игр - student2.ru Аналогично второму игроку оптимальная стратегия yjоптдолжна обеспечить при любых стратегиях первого игрока про­игрыш, не превышающий цену игры, т.е. справедливо соотно­шение справа:

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

Откуда имеем α и β.

Все элементы А2 меньше A3, т.е. А3 заведомо невыгодна для первого игрока и А2 можно исключить. Все элементы А4меньше А3, исключаем А4.

основные понятия теории игр - student2.ru Для второго игрока: сравнивая В1 и B4, исключаем В1;сравнивая В2 и В4, исключаем В2; сравнивая B3 и В4, исклю­чаем В3. В результате преобразований получим матрицу справа:

31.1. Графическое решение игр вида (2 x n) и (m x 2)

основные понятия теории игр - student2.ru Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии. Рассмотрим игру (2 х п), см. табл. 31.2.

Предполагаем, что игра не имеет седловой точки.

основные понятия теории игр - student2.ru Обозначим: х1 — вероятность применения первым игроком 1-й стратегии, x2 — вероятность применения первым игроком 2-й стратегии, причем х2 = 1 — x1; y1 — вероятность примене­ния вторым игроком 1-й стратегии, у2 — вероятность приме­нения вторым игроком 2-й стратегии и т.д., уn — вероятность применения вторым игроком п-й стратегии.

Ожидаемый выигрыш первого игрока при применении вто­рым 1-й стратегии составит

основные понятия теории игр - student2.ru Аналогично найдем ожидаемые выигрыши первого игрока при применении вторым игроком 2, 3, ..., n-й стратегий. Полу­ченные данные поместим в табл. 31.3.

Из таблицы видно, что ожидаемый выигрыш первого иг­рока линейно зависит от x1. На оси X1 построим выражения ожидаемых выигрышей первого игрока.

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

основные понятия теории игр - student2.ru Аналогично находим оптимальную стратегию второго иг­рока. Она определяется как точка пересечения прямых, мини­мизирующих его максимальные ожидаемые проигрыши.

Пример 1. Рассмотрим представленную выше игру, заданную платежной матрицей

Найти оптимальные стратегии игроков и цену игры.

основные понятия теории игр - student2.ru Решение. Обозначим: x1 — вероятность применения пер­вым игроком 1-й стратегии, х2, х3, х4 — вероятность исполь­зования первым игроком 2, 3, 4-й стратегий соответственно, причем х1 + x2 + x3 + x4 = 1; y1 — вероятность применения вторым игроком 1-й стратегии, у2, у3, y4, y5 — вероятность использования вторым игроком 2, 3, 4, 5-й стратегий соответ­ственно, причем y123+y4 + y5 = 1.

основные понятия теории игр - student2.ru Платежная матрица была упрощена путем вычеркивания дублирующих, заведомо невыгодных стратегий. Поэтому x2 = x4 = y1 = y2 = y3 = 0 и матрица имеет вид

Найдем решение игры (табл. 31.4) графическим методом (рис. 31.1). На оси Х1 разместим точки х1 = 0 и х1 = 1, через которые проведем прямые, перпендикулярные оси Х1. Подстав­ляя х1 = 0 и x1 = 1 в выражение х1 +3, найдем значения, кото­рые отложим на соответствующих перпендикулярных прямых. Соединив эти точки, получим прямую.

Аналогично рассмотрим выражение –3x1 + 5.

основные понятия теории игр - student2.ru Оптимальная стратегия первого игрока определится из ра­венства выражений х1 + 3 и -3х1 + 5:

основные понятия теории игр - student2.ru

Цена игры v = x1 + 3 = 1/2 + 3 = 7/2.

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

основные понятия теории игр - student2.ru

Найдем оптимальную стратегию для второго игрока (табл. 31.5).

основные понятия теории игр - student2.ru Имеем

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

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

основные понятия теории игр - student2.ru

Пример 2. Найдем решение игры вида (2 х n), заданной пла­тежной матрицей (табл. 31.6)

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

Решение. Находим

α = mах (-1,2) = 2,

β = min (4, 3, 3, 6) = 3, 2≤ v≤ 3.

Тогда

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

Оптимальное решение:

первого игрока: основные понятия теории игр - student2.ru опт = (1/2, 1/2), при этом цена игры составляет v = 5/2.

Найдем оптимальное решение второго игрока (табл. 31.7).

основные понятия теории игр - student2.ru Из рис. 31.3 следует, что оптимальная стратегия первого игрока определяется из равенства выражений –x1 + 3 и х1 + 2, соответствующих 2-й и 3-й чистым стратегиям второго игрока (см. табл. 31.5), поэтому y1 = y4 = 0, а у3 = 1 – y2.

Имеем

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

откуда основные понятия теории игр - student2.ru

Оптимальное решение второго игрока (рис. 31.4):

основные понятия теории игр - student2.ru опт = (0,1 / 2,1 / 2,0), при этом цена игры v = 5/2.

Ответ.

основные понятия теории игр - student2.ru опт = (1/2, 1/2), основные понятия теории игр - student2.ru опт = (0,1 / 2,1 / 2,0), v = 5/2.

основные понятия теории игр - student2.ru Пример 3. Найдем решение игры вида (т х 2), заданной пла­тежной матрицей (табл. 31.8)

основные понятия теории игр - student2.ru Решение. Находим α = mах (2, 2, 2, -2) = 2, β = min (3, 6) = 3, 2 ≤ v ≤ 3. Пусть y1 и у2 (причем y2 = l —y1) — смешанные стратегии второго игрока; x1, x2, x3, x4 — смешанные страте­гии первого игрока.

Находим

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

Оптимальное решение второго игрока (рис. 31.5):

основные понятия теории игр - student2.ru опт = (2/3, 1/3), при этом цена игры v = 8/3.

основные понятия теории игр - student2.ru Прямые, пересекающиеся в минимаксной точке, соответ­ствуют 1-й и 3-й чистым стратегиям первого игрока. Это озна­чает, что х2= х4 = 0. Следовательно, х1 = 1 — x3. Найдем оптимальную стратегию 1-го игрока (табл. 31.9, рис. 31.6).

Имеем

основные понятия теории игр - student2.ru основные понятия теории игр - student2.ru

Оптимальное решение первого игрока:

основные понятия теории игр - student2.ru опт = (1/3, 0, 2/3, 0), при этом цена игры v = 8/3.

Ответ.

основные понятия теории игр - student2.ru опт = (1/3, 0, 2/3, 0), основные понятия теории игр - student2.ru опт = (2/3, 1/3), v = 8/3.

Наши рекомендации