Модели матричных игр и их решение в чистых стратегиях

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

Пусть игрок А располагает 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 ден. ед.