8.5 Приближенный метод решения матричных игр

Если точное решение матричной игры оказывается громоздким, можно ограничиться приближенным решением. В частности, когда нижняя чистая цена игры  мало отличается от верхней чистой цены , иногда пользуются чистыми максиминной и минимаксной стратегиями, принимая их за оптимальные. В противном случае целесообразно использовать метод итераций. В основе этого метода лежит предположение, что игра состоит из большого количества партий и игроки выбирают свои чистые стратегии в очередной партии, руководствуясь накапливающимся опытом уже сыгранных партий, обоснованно полагая, что партнер и дальше будет действовать так, как он действовал до этого момента. Если каждый игрок имеет единственную оптимальную смешанную стратегию, то при неограниченном увеличении числа партий приближенные смешанные стратегии стремятся к оптимальным стратегиям игроков, а средние выигрыши – к цене игры v. Используя ЭВМ, вычислительную процедуру можно значительно ускорить и получить решение игры с любой точностью даже при матрицах больших размерностей.

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

Пример. В матричной игре получить приближения цены игры и оптимальных смешанных стратегий, выполнив 20 итераций.

Таблица 8.5

	В1	В2	В3
А1	4	2	2
А2	2	5	0
А3	0	2	5

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

Пусть в первой партии игрок А избрал стратегию А1. Выигрыши его при различных стратегиях игрока В будут равны соответственно 4, 2 или 2. Запишем их в первую строку таблицы. (см. таблицу8.6). Игроку В в первой партии выгоднее использовать либо вторую, либо третью стратегию, так как в обоих случаях его проигрыш будет наименьшим и равняться двум. Условимся в случае равенства выигрышей (проигрышей) при нескольких стратегиях брать стратегию с меньшим индексом. Итак, игрок В выберет стратегию В2, при которой он проиграет либо 2, либо 5, либо 2 в з0ависимости от выбора игроком А своей чистой стратегии (см. табл.8.5). Внесём эти значения в первую строку таблицы решения и заполним строку до конца:

Таблица 8.6

Номер партии	Игрок А				Игрок В				Приближённые значения цены
	Стратегия	Накопленный выигрыш при различных стратегиях игрока В			Стратегия	Накопленный проигрыш при различных стратегиях игрока А
		В1	В2	В3		А1	А2	А3
1	А1	4	2	2	В2	2	5	2	2	5	7/2
2	А2	6	7	2	В3	4	5	7	1	7/2	9/4
3	А3	6	9	7	В1	8	7	7	2	8/3	7/3
4	А1	10	11	9	В3	10	7	12	9/4	3	21/8
5	А3	10	13	14	В1	14	9	12	2	14/5	12/5
6	А1	14	15	16	В1	18	11	12	7/3	9/3	8/3
7	А1	18	17	18	В2	20	16	14	17/7	20/7	37/14
8	А1	22	19	20	В2	22	21	16	19/8	11/4	41/16
9	А1	26	21	22	В2	24	26	18	7/3	26/9	47/18
10	А2	28	26	22	В3	26	26	23	11/5	13/5	12/5
11	А1	32	28	24	В3	28	26	28	24/11	28/11	26/11
12	А1	36	30	26	В3	30	26	33	13/6	33/12	59/24
13	А3	36	32	31	В3	32	26	28	31/13	38/13	69/26
14	А3	36	34	36	В2	34	31	40	17/7	20/7	37/14
15	А3	36	36	41	В1	38	33	40	12/5	40/15	38/15
16	А3	36	38	46	В1	42	35	40	9/4	21/8	39/16
17	А1	40	40	48	В1	46	37	40	40/17	46/17	43/17
18	А1	44	42	42	В2	48	42	42	7/3	8/3	5/2
19	А1	48	44	52	В2	50	47	44	44/19	50/19	47/19
20	А1	52	46	54	В2	52	52	46	23/10	13/5	49/20

Переходим ко второй партии. Предполагая, что игрок В и во второй партии может воспользоваться стратегией В2, игрок А выберет стратегию А2, при которой его выигрыш является наибольшим и равняется 5. При стратегии А2 игрок А может выиграть либо 2, либо 5, либо 0. Во вторую строку таблицы решения записываем выигрыши игрока А в двух партиях, т.е. 4+2=6, 2+5 = 7, 2+0=2. Игроку В в данной ситуации выгоднее всего применить стратегию В3, соответствующую наименьшему проигрышу, равному 2. Записываем во вторую строку его суммарные проигрыши в двух первых партиях: 2+2=4, 5+0=5, 2+5=7. В последние три столбца записываем:

В третьей партии игроку А выгоднее всего применить стратегию А3, а игроку В после этого лучше использовать стратегию В1 и т.д. После 20 итераций подсчитываем, сколько раз игроки использовали каждую из своих чистых стратегий. Получаем m(A1)=12, m(A2)= 2, m(A3)= 6, m(B1)=6, m(B2)=8, m(B3)=6. После этого определяем вероятности применения игроками своих чистых стратегий: , , , , .

Таким образом, приближёнными оптимальными смешанными стратегиями игроков будут: , , а приближённое значение цены игры