Модели матричных игр

6.2.1. Модели матричных игр и их решение в чистых стратегиях. Рассмотрим парную игру (игру двух лиц), в которой у каждого из двух игроков А и В конечное число чистых стратегий.

Пусть игрок А располагает m чистыми стратегиями , а игрок В – n чистыми стратегиями . Чтобы игра была полностью определенной, необходимо указать правило, сопоставляющее каждой паре чистых стратегий и число – выигрыш игрока А за счет игрока В или проигрыш игрока В. Если < 0, то игрок А платит игроку В сумму . Если игра состоит только из личных ходов (личный ход – игрок сознательно выбирает и реализует ту или иную стратегию), то выбор пары чистых стратегий (;) единственным образом определяет исход игры. Если же в игре используются и случайные ходы (выбор хода случаен), то исход игры обусловлен средним значением выигрыша (математическим ожиданием).

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

Если известны значения выигрыша для каждой пары (;) стратегий, то можно составить матрицу игры – платежную матрицу (таблица 6.1). Таблица 6.1

	…
	…
…	… … …
	…

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

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

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

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

(6.1)

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

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

(6.2)

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

Таблица 6.2

			…		…
			…		…
			…		…
…	…	…		…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
			…		…

Таким образом, игрок А обеспечивает выигрыш не менее α, а игрок В может не позволить игроку А выиграть больше, чем β.

Принцип осторожности диктует игрокам выбор максиминной и минимаксной стратегий.

Теорема 6.1. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры:

α ≤ β.

Действительно, так как а , то , т. е. , тогда для любых . Следовательно, .

Если в матричной игре нижняя и верхняя чистые цены игры совпадают (т. е. α = β), то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры v = α = β.

Пара чистых стратегий () игроков А и В, при которых α = β, называется седловой точкой матричной игры, а элемент матрицы, стоящий на пересечении -строки и -столбца, – седловым элементом платежной матрицы.

Седловой элемент является наименьшим в строке и наибольшим в столбце, т. е.: ≤ ≤ .

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

Пример 6.1. Найти максиминную и минимаксную стратегии в игре с матрицей

.

Решение. Составим платежную матрицу

	1 5 –2 4	–2
	0 1 2 3
	2 3 –1 0	–1
	2 5 2 4

и выпишем в последнем столбце минимальные по строкам элементы

Наибольшим из них является 0, т. е. , значит, максиминной чистой стратегией игрока А является .

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

Минимаксной для игрока В является стратегия или .

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

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

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

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

Если > , то фирма , предлагая товар более высокого качества, будет единолично получать доход от до истечения 3 месяцев. Доход фирмы (игрок ) за это время будет равен: 20(3 - +1) ден.ед.

Если = , т. е. продукция поступает одновременно от обеих фирм, то он реализуется с одинаковы спросом. Доход фирмы будет равен доходу фирмы и составит: 10(3 - + 1) ден.ед.

Тогда выигрыши игрока можно записать в виде следующей функции:

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

Таблица 6.3

Определим нижние и верхние чистые цены игры (табл. 6.3):

В данном случае имеем две седловые точки или , а седловой элемент равен 20.

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

6.2.2. Модели матричных игр со смешанными стратегиями игроков. Свойства смешанных стратегий. Рассмотрим матричную игру:

			…		…
			…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
			…		…

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

. (6.3)

Упорядоченное множество р = (, …, ), элементы которого удовлетворяют условиям (6.3), полностью определяют характер игры игрока А и называется его смешанной стратегией. Итак, смешанной стратегией игрока А является полный набор вероятностей применения его чистых стратегий. Множество смешанных стратегий определяется случайным выбором чистых стратегий. Любая его чистая стратегия А может рассматриваться как частный случай смешанной стратегии, i -я компонента которой равна 1, а остальные равны нулю: р = (0; …; 1; …; 0).

Упорядоченное множество q = (, …, ), элементы которого удовлетворяют соотношениям , называются смешанной стратегией игрока В.

Применение смешанных стратегий p и q игроками А и В означает, что игрок А использует стратегию с вероятностью , а игрок В – стратегию с вероятностью . Поскольку игроки выбирают свои стратегии случайно и независимо друг от друга, то вероятность выбора комбинации стратегий (, ) будет равна . При использовании смешанных стратегий игра приобретает случайный характер, поэтому случайными будут и выигрыши игрока А и проигрыши игрока В. Следовательно, можно вести речь лишь о средней величине (математическом ожидании) выигрыша (проигрыша). Эта величина является функцией смешанных стратегий p и q и определяется по формуле:

.

Функция f (p; q) называется платежной функцией игры с матрицей .

Смешанные стратегии , назовем оптимальными смешанными стратегиями игроков А и В, если они удовлетворяют неравенству:

f (, ) ≤ f (, ) ≤ f (, ) (6.4)

для любых стратегий и .

Значение f (, ) платежной функции при оптимальных стратегиях определяет цену игры v, т. е. v = f (, ).

В седловой точке платежная функция достигает максимума по смешанным стратегиям игрока и минимума по смешанным стратегиям игрока .

Рассмотрим игру с матрицей и предположим, что и – оптимальные смешанные стратегии игроков и v = f (, ) – цена игры. Проверку того, что набор (, , v) является решением, можно провести при помощи теоремы 6.2.

Теорема 6.2. Для того, чтобы смешанные стратегии = (, …, ) и = = (_, , …, ), были оптимальными для игроков А и В в игре с матрицей и ценой v, необходимо и достаточно выполнения неравенств:

Кроме того, смешенные стратегии удовлетворяют еще следующим теоремам.

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

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

Активные стратегии – это чистые стратегии игрока, входящие в оптимальную смешанную стратегию с вероятностями, отличными от нуля.

Из теоремы 6.2 вытекает принципиальное решение матричной игры: надо найти неотрицательное решение (, , …, , , , …, , v) системы линейных неравенств и линейных уравнений:

; .

Отметим, что число активных стратегий игроков не превышает наименьшего из чисел m и n.

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

Говорят, что стратегия доминирует над стратегией , если элементы k -й строки не меньше соответствующих элементов s -ой строки: , . Выигрыш игрока А в этом случае (при стратегии ) больше чем при стратегии , какой бы стратегией не воспользовался игрок В. Стратегию назовем доминирующей, а стратегию – доминируемой.

Аналогично и для столбцов:

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

Если , , или , , то стратегии и , и называются дублирующими.

Пример 6.3. Выполнить возможные упрощения платежной матрицы:

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

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

.