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

Принцип минимакса (осторожности)

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет т альтернатив (А, Л₂, А_т), а игрок II — п стратегий (В₉ В₂,В_п). Такая игра называется игрой размерностью т’Хп. Пусть каждая сторона выбрала определен;

но ную стратегию: игрок I — Л, (/ = 1, 2,т), игрок II — Bj (j = = 1,2,…, п). Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой.

Пусть a_tj — выигрыш игрока I в ситуации, когда игрок выбрал стратегию Л" а игрок II выбрал стратегию Bj. Выигрыш игрока II в данной ситуации обозначим через by.

Рассматриваем игру с нулевой суммой, следовательно, ^aij⁼ ~^bij Д^ля любых i и j и для проведения анализа достаточно знать выигрыш только одного из игроков.

Если игра состоит только из личных ходов, то выбор стратегии (Ар Bj) однозначно определяет исход игры, например выигрыш игрока L Если игра содержит также случайные ходы, то выигрыш при паре стратегий (Л/, Bj) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш — это среднее значение (математическое ожидание). Предположим, что значения йу известны для каждой пары стратегий (Л" Bj). Составим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы — стратегиям игрока И. Такая таблица называется платежной матрицей. Каждый элемент (ау > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II при применении соответствующих стратегий (Л,-, Bj). Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш.

Будем считать, что все а_1} > 0. Этого всегда можно добиться прибавлением достаточно большого положительного числа ко всем строкам и столбцам матрицы. Такое изменение матрицы не повлияет на результат.

Таким образом, платежная матрица имеет следующий вид (табл. 3.8).

Таблица 3.8

I/II.	B	B2				B"	a,.
л.	au	^12.		«1/.		an	ai.
^2.	a2	a22		a2j		a2n	a2
Ai	a	ai2		ao		M in	a,.
Ат	am	am2		amj		&mn
P,.	P.	P2.		Pi		Р".

Задача состоит в определении:

• 1) наилучшей (оптимальной) стратегии игрока I из стратегий Л_ЬЛ₂, А_т;
• 2) наилучшей (оптимальной) стратегии игрока II из стратегий В₂,В_п.

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

Характерные оценки. Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию Д, то игрок II может выбрать такую стратегию Bj, при которой выигрыш игрока I будет равен наименьшему из чисел а _1;:

где aj — минимальное значение из всех чисел первой строки.

Тогда, но аналогии справедливо записать выражение для любой стратегии Д.

Выбирая стратегию Д, игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем а,. Поэтому игрок I должен выбрать ту стратегию, для которой это число а, — максимально.

где с^— максимальное значение из всех чисел столбца а_; (/ =.

= 1, т).

Подставив вместо а, выражение (3.3), получим.

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

Игрок II заинтересован в том, чтобы уменьшить свой проигрыш, т. е. обратить выигрыш игрока I в минимум. Для выбора оптимальной стратегии он должен найти максимальное значение выигрыша в каждом столбце и среди этих значений выбрать наименьшее. Обозначим через р, максимальное значение в каждом столбце:

Наименьшее значение Р₇ обозначим через.

С учетом выражения (3.5) получим.

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

Справедливо неравенство, а < р.

Таким образом, придерживаясь максиминной стратегии Л,-, игрок I желает получить выигрыш не менее, а независимо от действий игрока II, а игрок II, придерживаясь минимаксной стратегии В_п гарантирует себе проигрыш не больше р.

Принцип, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр называется принципом минимакса — принципом гарантированного результата. Этот принцип был впервые сформулирован Дж. фон Нейманом в 1928 г.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т. е. а = р. Такие игры называются играми с седловой точкой, в этом случае у = а = Р называется чистой ценой игры, а стратегии игроков А* и В*, позволяющие достичь этого значения, — оптимальными. Пара (Л*, BJ) называется седловой точкой матрицы, так как элемент а*- = у одновременно является минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии А* и В* и чистая цена являются решением игры в чистых стратегиях, т. е. без привлечения механизма случайного выбора.

При постановке задач необходимо иметь в виду некоторые преобразования, которые помогают упростить сложную задачу путем изменения — уменьшения размерности платежной матрицы посредством выделения и исключения доминирующих и дублирующих стратегий. Стратегия игрока Л, доминирует над стратегией Л/, если при любом поведении противника даст не меньший выигрыш, а если такой же, то дублирует Л/,. В таком случае все элементы строки i больше (доминируют) всех элементов строки k или равны (дублируют) им.

Пример 3.3. С учетом вариантов конъюнктуры В, В₂, В₃, В₄, В-_у сложившейся на рынке, и поведения покупателей в микрорайоне города коммерческое предприятие разработало шесть технологий продажи товаров А, А₂, А₃, Л₄, А₅, Л₆. Найти оптимальное решение. Возможные варианты среднедневного товарооборота в млн руб. приведены ниже:

	В	в2	Вз	в,	Вз
А	0,4.	0,9.	0,5.	0,5.	0,6.
а2	0,6.	0,5.	0,7.	0,8.	0,9.
Аз	0,6.	0,3.	0,8.	0,6.	0,7.
А	0,3.	0,8.	0,5.	0,4.	0,3.
Аз	0,1.	0,3.	0,5.	0,4.	0,3.
Ав	0,4.	0,8.	0,5.	0,4.	0,5.

Упростим матрицу. Стратегия А₍доминирует над стратегией Л_{!, а стратегия А₄ доминирует над стратегией Л₅, следовательно, исключаем 5-ю и 6-ю строки матрицы.

	В	в2	Вз	в,	Вз
^1.	0,4.	0,9.	0,5.	0,5.	0,6.
^2.	0,6.	0,5.	0,7.	0,8.	0,9.
^3.	0,6.	0,3.	0,8.	0,6.	0,7.
А	0,3.	0,8.	0,5.	0,4.	0,3.

С позиций проигрышей игрока В стратегии В₃, В₄ и В₅ доминируют над стратегией B_h поэтому эти столбцы исключаем.

	в,.	В2
А,	0,4.	0,9.
А-2	0,6.	0,5.
А3	0,6.	0,3.
а4	0,3.	0,8.

С позиций игрока А стратегия /1, доминирует над стратегией А₄, а стратегия А₂ доминирует над стратегией Л₃, поэтому исключим 3-ю и 4-ю строки и в результате получаем сокращенную матрицу.

Дальнейшее облегчение расчетов дает другое эквивалентное преобразование матрицы, при котором jre изменяются оптимальные смешанные стратегии игроков Р и Q.

Теорема. Если (Р, Q, у) есть решение^игры с матрицей А, то решение игры с матрицей кЛ + h есть (Р, Q, ку + Ь), где к > 0, b — любое действительное число.

На этом основании для рассматриваемой матрицы при &=10и6 = -3 получим следующую матрицу:

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

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

l/II.		B2	B3		a,.
^2
A3					®.
P,.		©.

Таким образом, нижней цене игры (а = 4) соответствует стратегия Л₃ игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 при любом поведении игрока II. Верхней цене игры (Р = 6) соответствует стратегия игрока II В₂. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен 5 (я₃₃).

Пример 3.5. Пусть задана платежная матрица. Найти нижнюю и верхнюю цены игры.

i/и.	B	B2	«3.	a,.
At
^2.
A3
Pj

Следовательно, а = р= у = 3, а седловая точка указывает решение на пару альтернатив (Л₃, В_А).