Матричные игры с нулевой суммой

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

Игроки	Стратегии игрока В
	В А		…		…
Стра-тегии игрока А			…		…
	…	…………………………….
			…		…
	…	…………………………….
			…		…

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

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

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

Число называется нижней чистой ценой игры (максимином). Она выражает выигрыш игрока А, при использовании максиминной стратегии независимо от действий игрока В.

Число β определяемое по формуле,

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

Стратегии ( ) первого игрока и стратегии второго игрока (возможные их ходы) принято называть чистыми стратегиями.

Пример. Пусть первый игрок имеет т, а второй – п чистых стра­тегий, тогда каждую пару чистых стратегий первого и второго игро­ков можно представить в виде единичных векторов:

, ,

-е место -е место

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

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

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

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

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

(Пример). Игра задана следующей платежной матрицей

	3	2	1	4	5	1
	4	3	2	5	6	2
	7	4	-3	4	-1	-3
	7	4	2	5	6

– максиминная стратегия, – минимаксная стратегия, следовательно, и . Особенность этого примера в том, что если оппонент придерживается стратегии , то игроку А невыгодно использовать какую-либо стратегию кроме . Но если игрок А использует стратегию , то оппоненту придется использовать . Причина состоит в том, что выигрыш одновременно является минимальным для максиминной стратегии и максимальным для минимаксной стратегия . Это игра с седловой точкой , стратегии сторон , , соответствующие этой точке, являются оптимальными чистыми стратегиями. Чистая цена игры равна .

Пример. Игра задана следующей платежной матрицей

	4	5	5	6	6	4
	7	9	3	-3	4	7
	5	3	3	1	4	5
	3	4	3	6	-6	3

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

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

	4	5	5	6	6	4	4
	7	9	3	-3	4	7	-3
	5	3	3	1	4	5	1
	3	4	3	6	-6	3	-6
	7	9	5	6	6	7

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

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

Смешанной стратегией p первого (А) игрока называется вектор

, где , ( ) и /

Аналогично q – смешанная стратегия игрока В:

( , где , ( ) и ).

Здесь и – вероятности, с которыми игроки А и В выбирают свои чистые стратегии и в ходе игры.

Чистая стратегия игрока А может рассматриваться как частный случай смешанной стратегии, i-я компонента которой равна 1, а остальные равны 0. Аналогично для игрока В.

Применяя смешанные стратегии игроки выбирают свои чистые стратегии слу­чайно и независимо друг от друга и, таким образом, случайной становится величина выигрыша (про­игрыша):

– плата – платежная функция игры с платежной матрицей .

Смешанные стратегии , называ­ются оптимальными, если для произвольных стратегий , выполняется условие

,

т.е. – является седловой точкой функции .

Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р, второму игро­ку – проигрыш, не больший, чем при использовании им лю­бой другой стратегии q.

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

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

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

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

Игрок А заинтересован в максимизации выигрыша. Поэтому в платежной матрице сравниваем элементы строк s и t, а именно: с элемен­тами для . Если ( ) то выигрыш игрока А при стратегии будет больше, чем при стратегии , какую бы чистую стратегию не применил игрок В. В этом случае стратегия доминирует над стратегией . Стратегию называют доминирующей, а стратегию – доминируемой.

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

Если в матричной игре имеем строки (столбцы) с одними и теми же элементами, то такие строки (столбцы), а соответственно и стратегии игроков А и В называются дублирующими.

В матричной игре доминируемые и дублирующие строки (столбцы) можно опускать, что не влияет на решение игры, но позволяет уменьшить размерность платежной матрицы. Таким образом, если стратегия доминирует над стратегией , то вероятность применения последней в оп­тимальной смешанной стратегии р* игрока А равна нулю, а поэтому t-ю строку из платежной матрицы можно исключить. Если l-я стратегия игрока В доминирует над r-й стратегией , то r-й столбец из платежной матрицы можно исключить.

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

Так, разделив элементы матрицы

на 100 (умножив на 0,01), а затем прибавив к элементам но­вой матрицы число 3, придем к матрице

.

Работать с этой матрицей проще, чем с исход­ной.

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