33. Матричные игры двух игроков. Решение матричных игр в чистых стратегиях

В общем случае матричная игра двух игроков может рассматриваться как абстрактная одношаговая антагонистическая игра, заданная с помощью матрицы размерностью N ´ M. В этом случае первый игрок имеет N стратегий: 1, 2, ¼, N, а второй – M стратегий: 1, 2, ¼, M. Каждой паре стратегий (I, J) соответственно первого и второго игроков ставится в соответствие числовой элемент матрицы Aij. В матричной игре каждый из игроков делает только по одному ходу: первый игрок выбирает свою I-ю стратегию I Î {1, 2, ¼, N}, а второй игрок – свою J-ю стратегию J Î {1, 2, ¼, M}. Если выбранный парой стратегий (I, J) элемент Aij положителен, то первый игрок получает выигрыш Aij за счет второго игрока, если элемент Aij отрицателен, то выигрывает второй игрок. В любом случае выигрыш одного игрока равен проигрышу другого. После определения выигрыша одного из игроков партия матричной игры заканчивается.

Стратегии I и J (I Î {1, 2, ¼, N}, J Î {1, 2, ¼, M}) соответственно первого и второго игроков часто называют чистыми стратегиями.

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

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

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

Исходя из этого определения, исследуем матрицу выигрышей A = первого игрока

.

Если первый игрок выберет стратегию I (I Î {1, 2, ¼, N}), то второй игрок будет стремиться к тому, чтобы выбором своей стратегии J (J Î {1, 2, ¼, M}) выигрыш первого игрока, а, следовательно, и свой проигрыш свести к минимуму:

, . (3.2)

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

. (3.3)

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

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

, (3.4)

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

. (3.5)

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

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

Если в матричной игра A нижняя и верхняя чистые цены игры совпадают, то говорят, что матричная игра A имеет седловую точку в чистых стратегиях и чистую цену игры

.

Седловой точкой в матричной игре A называется пара (I0, J0) чистых стратегий соответственно первого и второго игроков, при которых достигается равенство между верхней и нижней чистыми ценами игры

.

Элемент матрицы A, стоящий на пересечении строки и столбца называют седловой точкой матричной игры, а число – чистой ценой игры.

Понятие седловой точки несет определенный смысл. Рассмотрим его. Если в матричной игре A имеется седловая точка и один из игроков придерживается стратегии, соответствующей седловой точке, то у другого игрока нет лучшей стратегии, чем также придерживаться седловой точки. Действительно, если седловой точки придерживается первый игрок, а второй игрок хочет выбрать стратегию , то поскольку по определению b (выражение (3.5)) элемент , т. е. является минимальным в дополнительной строке, то второй игрок не может уменьшить свой проигрыш, но может его увеличить. Если седловой точки придерживается второй игрок, а первый хочет изменить стратегию на , то поскольку по определению a (выражение (3.3)) элемент и , то первый игрок не сможет увеличить свой выигрыш за счет замены стратегии на любую другую, но может уменьшить свой выигрыш, так как элемент является максимальным элементом дополнительного столбца. Таким образом, имеем

, (3.6)

Где I, J – соответственно произвольные чистые стратегии первого и второго игроков; – чистые стратегии первого и второго игроков, соответствующие седловой точке; – произвольный элемент столбца матрицы A; – седловой элемент матричной игры; – произвольный элемент строки матрицы A.

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

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

Стратегии , соответственно первого и второго игроков в матричной игре A, Называют оптимальными чистыми стратегиями.

Предложенные алгоритмы поиска седловых точек очень просты и, на первый взгляд, не всегда могут находить правильное решение или, наоборот, несколько разных решений. Предположим, что найденный элемент , являющийся минимальным элементом в строке и максимальным элементом столбца , не является равным величине цены игры, то есть существует элемент , который также является минимальным в K-й строке и максимальным в L-м столбце и , и , где V – цена игры. Рассмотрим матрицу A с элементами и :

.

Поскольку элемент является минимальным элементом в строке K, а элемент является максимальным элементом в столбце , то имеем

. (3.7)

Однако элемент является по условию максимальным элементом L-го столбца, а элемент – минимальным элементом строки , поэтому получаем

. (3.8)

Из соотношений (3.7), (3.8) следует, что и , следовательно . Таким образом, если рассмотренные алгоритмы в матричной игре A определяют несколько седловых элементов, то это означает, что матричная игра имеет несколько решений, но с одной ценой игры, поскольку численные значения всех седловых элементов одинаковы.

Если в матричной игре нет седловой точки в чистых стратегиях, то в этом случае и .

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

.

Доказательство. Из соотношений (3.2) и (3.4) имеем:

, , ;

, , .

Объединив эти соотношения, получим

, , .

Отсюда следует, что

, , .

Или

, , .

Поскольку последнее неравенство справедливо при любых I и J, то, следовательно, .

Пример 3.4. Установить наличие седловых точек в матричной игре

.

С помощью соотношений (3.3) и (3.5) определим нижнюю и верхнюю чистые цены игры:

;

.

Отсюда имеем, что

.

Таким образом, в данном случае имеем одну седловую точку, определяемую парой оптимальных чистых стратегий ( = 1, = 2), и седловой элемент = 3.

Заменим в матрице A элемент = 3 на элемент = –3 и определим a и b для новой матричной игры:

;

.

В этом случае a ¹ b и получить решение матричной игры в чистых стратегиях не удается. Можно только определить, что цена игры V находится между a и b: –2 £ V £ 2. Для поиска более точного решения матричной игры в подобных случаях необходимо применять методы, основанные не на чистых, а на смешанных стратегиях обоих игроков.

< Предыдущая		Следующая >