Чистые и смешанные стратегии и их свойства.

Наличие седловой точки в игре — это далеко не правило, скорее — исключение. Большинство игр не имеет седловой точки.

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

Если игра не имеет седловой точки, то для ее решения используются смешанные стратегии. Смешанной стратегией называется вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии. Обычно смешанную стратегию первого игрока обозначают как вектор U=(u₁, u₂, ...u_m), а второго — как вектор Z=(z₁, z₂,...z_n), где u_i0 (i=1...m), z_j0 (j=1...n), =1, =1. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности. Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведет себя противник в данной партии. Такая тактика часто применяется в карточных играх .

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

Применение игроком А оптимальной стратегии U* должно обеспечить ему при любых действиях игрока В выигрыш не меньше цены игры. Поэтому выполняются следующие соотношения:

, j=1,...n. (4.1)

Аналогично, для игрока В оптимальная стратегия Z* должна обеспечить при любых стратегиях игрока А проигрыш, не превышающий величину v, т. е. справедливо соотношение

, i=1,...m (4.2)

Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Если U* — оптимальная стратегия первого игрока, а Z* — оптимальная стратегия второго игрока, то число

v=

является ценой игры.

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

а).

4	3	-5	12
14	-4	5	8
3	5	8	9
5	12	4	5

Р е ш е н и е. Запишем платежную матрицу, найдем нижнюю и верхнюю границы цены игры:

			B1	B2		B3		B4		
		A1	4	3		-5		12		-5
		A2	14	-4		5		8		-4
		A3	3	5		8		9		3
		A4	5	12		4		5		4
			14	12		8		12

Видим, что =4 не равно =8, следовательно, седловой точки нет и, следовательно, данная игра имеет решение в смешанных стратегиях.

б).

10	7	4	8	9
-4	12	2	4	5
5	-6	1	3	4
4	5	-4	1	2

Р е ш е н и е. Из платежной матрицы видно, что когда первый игрок применяет стратегию А₁, а второй — В₃, игра имеет седловую точку, следовательно, решение игры записывается в чистых стратегиях (А₁; В₃) при цене игры V=4. Чистые стратегии определяются как вектора U(1, 0, 0, 0) и Z(0, 0, 1, 0).

	B1	B2	B3	B4	B5	
A1	10	7	4	8	9	4
A2	-4	12	2	4	5	-4
A3	5	-6	1	3	4	-6
A4	4	5	-4	1	2	-4
	10	12	4	8	9	4