4.3. Решение матричных игр в чистых стратегиях.

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет т стратегий i = 1,2,...,т, второй имеет п стратегий j= 1,2,..., п. Каждой паре стратегий (i, j) поставлено в соответствие число a_ij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию , 2 – свою j-ю стратегию , после чего игрок 1 получает выигрыш a_ij за счёт игрока 2 (если a_ij< 0, то это значит, что игрок 1 платит второму сумму | a_ij|). На этом игра заканчивается.

Каждая стратегия игрока i= ; j = часто называется чистой стратегией.

Если рассмотреть матрицу

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_ij.

Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2

а_ij (i = ) ,

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i_о, при которой этот минимальный выигрыш будет максимальным, т.е. находится следующим образом

(1)

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

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

Аналогичные рассуждения можно провести для игрока 2, который при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскива­ется (2)

Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гаран­тировать игрок 1.

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

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

Седловая точка - это пара чистых стратегий (i₀, j₀) соответственно игроков 1 и 2, при которых достигается равенство .

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

Пример 1. Рассмотрим матричную игру следующего вида

Vj Ui	V1	V2	V3	V4	V5
U1	3	4	5	2	1
U2	1	8	4	3	4
U3	10	3	1	7	6
U4	4	5	3	4	8

Где U_i – стратегии игрока 1 и соответствующий выигрыш, а V_j – стратегии игрока 2 и соответствующий проигрыш (т.к. в парной игре выигрыш одного влечет за собой проигрыш другого).

Игроку 1 предпочтительнее выбрать стратегию с наибольшим выигрышем, поэтому он, очевидно, выберет стратегию U₃. Однако, у игрока 2 имеется выбор из пяти стратегий, поэтому он может воспользоваться стратегией V₃, и тогда выигрыш игрока 1 окажется минимальным (1). Аналогичные ситуации возможны и при использовании игроком 1 других стратегий. Вместе с тем, минимальные значения выигрыша для различных стратегий игрока 1 различны между собой. В этой связи для него имеет смысл выбрать такую стратегию U_i, для которой минимальный выигрыш будет наибольшим на множестве остальных стратегий.

Поэтому,

,

Пример 2.

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

Таблица 1

Показатели	Мягкая	Нормальная	Суровая
Расход, т	7	12	20
Цена, руб за 1 т	200	300	400

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

Определить оптимальную стратегию в закупке топлива: А₁ – 7т, А₂ – 12т и А₃ – 20т.

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

Обозначим состояние погоды зимой: мягкая зима – В₁, нормальная – В₂, суровая – В₃. Будем заполнять платежную матрицу.

Платежная матрица задачи

Состояние погоды Стратегии заготовки топлива		В1	В2	В3	min 	maxminα
		Мягкая	Нормальная	Суровая
А1	7т	1400	2900	6600	1400
А2	12т	2400	2400	5600	2400
А3	20т	4000	4000	4000	4000	4000
max 		4000	4000	6600
minmax 		4000	4000

Для стратегии заготовки топлива А₁ рассмотрим три случая.

Случай А₁В₁. Затраты составят: 200 * 7 = 1400 (руб.).

Случай А₁В₂. При нормальных погодных условиях расход угля составит 12т, т.е. зимой придется докупить 5т (к закупленным летом 7т по цене 200 руб.) уже по 300 руб. за тонну. Тогда затраты составят: (руб.).

Случай А₁В₃. При суровой зиме к закупленным 7т летом по 200 руб. за тонну придется докупить зимой 13т по цене 400 руб. за тонну. Затраты составят: (руб.). Для стратегии заготовки топлива при А₂ тоже необходимо рассмотреть три случая.

Случай А₂В₁. Закупить летом 12т по 200 руб. Затраты составят: (руб.).

Случай А₂В₂. Закупить летом 12т. по 200 руб. Для нормальной зимы 12т хватит. Затраты составят (руб.).

Случай А₂В₃. Закупить топливо летом 12т по 200 руб. Для суровой зимы придется докупить 8т по 400 руб. за тонну. Затраты составят: (руб.).

Для стратегии А₃ в заготовке угля расчеты аналогичны.

Случай А₃В₁. Закупить летом 20т по 200 руб. Для мягкой зимы угля хватит 7т. Остатки можно продать. Затраты составят: (руб).

Случай А₃В₂. Затраты равны 4000 руб.

Случай А₃В₃. Затраты составят тоже 4000 руб.

Платежная матрица составлена.

Нижняя цена игры .

Верхняя цена игры  = min (4000, 4000, 6600) = 4000.

Здесь  = , т.е. игра имеет седловую точку. Поэтому решением задачи является одна точка. Эта точка (А₃В₃). Следовательно, при заготовке топлива нужно принять решение закупить 20т топлива в расчете на суровую зиму. При этом затраты на заготовку топлива для одного помещения не превысят 4000 рублей.