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

Рассмотрим приближенный метод решения матричных игр - метод Брауна-Робинсон (метод итераций). Идея его заключается в следующем. Разыгрывается эксперимент, в котором игроки А и В поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков стремится увеличить свой выигрыш, предполагая, Что будущее будет походить на прошлое; при этом считается, что ни один из них не знает своей оптимальной стратегии.

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

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

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

Объясним этот метод на примере игры 3X3, платежная матрица которой приведена ниже. Игра начинается с произвольно выбранной стратегии игрока А, - например стратегии А1 (выбранные стратегии обозначаются звездочкой). Платежные элементы этой строки переписываются под платежной матрицей. Игрок В, предполагая, что будущее будет походить на прошлое, выберет стратегию В1, при которой его проигрыш минимален. Соответствующий этой стратегии проигрыш обозначен звездочкой. Платежные элементы стратегии В1 переписываются справа от платежной матрицы. Игрок А, также предполагая, что будущее будет походить на прошлое, выбирает стратегию А2 (наибольшее число обозначено звездочкой). Платежные элементы, соответствующие стратегии А2, Прибавляются поочередно к элементам предыдущей строки, записанной под матрицей. Далее выбирается наименьший элемент суммарной строки. Ему соответствует стратегия В2. Тогда к столбцу, записанному справа от платежной матрицы, поочередно прибавляются платежные элементы стратегии В2. Этот процесс продолжается до тех пор, пока разрыв между нижней и верхней оценками игры станет небольшим. Если при выборе стратегий на некотором шаге есть несколько альтернатив, то выбирается любая из равноценных стратегий.

В рассматриваемом примере сделано 20 шагов. За эти двадцать шагов игрок А применил свою первую стратегию (количество звездочек в суммарных выигрышах, соответствующей первой стратегии) 7 раз; вторую - 8 раз; третью - 5 раз. Игрок В применил стратегию В1 восемь раз; вторую - 8 раз; третью - 4 раза. Следовательно, приближенные оценки оптимальных стратегий, полученные за 20 итераций, равны:

.

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

Bi Ai	B1	B2	B3		1	2	3	4	5	6	7	8	9	10
A1	1	2	3	*	1	3	5	8*	9*	10	12	14	17*	20*
A2	3	1	1		3*	4*	5	6	9	12*	13*	14	15	16
A3	1	3	1		1	4	7*	8	9	10	13	16*	17	18
					11	12	13	14	15	16	17	18	19	20
1	1*	2	3		21*	22	24*	25	27	29	31	32	33	36*
2	4	3*	4		19	22*	23	26*	27*	28	29	32	35*	36
3	7	4*	5		19	20	23	24	27	30*	33*	34*	35	36
4	8	7	6*
5	9*	9	9
6	10*	11	12
7	13	12*	13
8	16	13*	14
9	17	16	15*
10	18	13	18*
11	19*	20	21
12	20*	22	24
13	23	23*	25
14	24*	25	28
15	27	26*	29
16	30	27*	30
17	31	30*	31
18	32*	33	32
19	33*	36	33
20	36	37	34*

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

.

В рассматриваемом примере

.

Точная цена игры V = 1,8.

Разрыв между и отражает неточность оценок относительно оптимальных смешанных стратегий. В примере составляет 2,8% от цены игры V=1,8.

Увеличивая число итераций k, можно найти еще более точные оценки оптимальных смешанных стратегий.

Преимуществом итерационного метода решения матричных игр является то, что объем вычислений с увеличением размерности игры MXN растет существенно медленнее, чем в методах линейного программирования (в частности, в симплекс - методе).

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