Описание и программирование матричных игр

= (0,17;0,05;0,11;0,15;0,09;0,11;0,1;0,07;0,03;0,12);

=(0,22;0,03;0,09;0,17;0,12;0,13;0,07;0,05;0,04;0,08).

=134,126

 

4. Метод Брауна-Робинсона решения матричных игр

 

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

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

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

В 1-ой партии оба игрока выбирают совершенно произвольные чистые стратегии. Пусть игрок 1 выбрал i-ю стратегию, а игрок 2 – j-ю стратегию. Во второй партии игрок 1 отвечает на ход игрока 2 той своей стратегией, которая даёт ему максимальный  выигрыш. В свою очередь, игрок 2, отвечает на этот ход игрока 1 своей стратегией, которая обращает его проигрыш в минимум. Далее третья партия.

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

Итак, предположим, что  за первые разыгрываний игрок 1 использовал i-ю чистую стратегию раз , а игрок 2 j-ю чистую стратегию раз . Тогда их смешанными стратегиями будут векторы , .

Игрок 1 следит за действиями игрока 2 и с каждым своим ходом  желает получить как можно больший  выигрыш. Поэтому в ответ на применение игроком 2 своей смешанной стратегии  , он будет использовать чистую стратегию , которая обеспечит ему лучший результат при разыгрывании (k+1)-ой партии. Игрок 2 поступает аналогично. В худшем случае каждый из них может получить:

где - наибольшее  значение проигрыша игрока 2 и - наименьшее значение выигрыша игрока 1.

Рассмотрим отношения, которые определяют средние значения проигрыша игрока 2 и выигрыша игрока 1:

Пусть н - цена  матричной  игры .  Её  значение будет больше выигрыша игрока 1, но меньше проигрыша игрока 2, т. е.

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

Пример. Найти приближённое решение игры с матрицей

А=

.

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

 

но-мер пар тии	стратегия второго игрока	выигрыш игрока 1 при его  стратегиях			стратегия первого игрока	проигрыш игрока 2 при его стратегиях			u	w	n
		1	2	3		1	2	3
1	1	0	4	2	2	4	1	2	4	1	5/2

В столбце u находится наибольший средний выигрыш 4 игрока 1, полученный им в первой партии; в столбце w стоит наименьший средний проигрыш 1, полученный игроком 2 в первой партии; в столбце n находится среднее арифметическое n=(u+w)/2=5/2, т. е. приближенное значение цены игры, полученное в результате проигрывания одной партии.

Так как игрок 1 выбрал 2-ю стратегию, то игрок 2 может проиграть:

• 4, если применит свою 1-ю стратегию;
• 1, если применит свою 2-ю стратегию;
• 2, если применит свою 3-ю стратегию.

Поскольку он желает проиграть  как можно меньше, то в ответ  применит свою 2-ю стратегию.

Тогда первый игрок получит  выигрыш равный 3, 1, 0 соответственно при своих 1-й, 2-й, 3-й стратегиях, а  его  суммарный выигрыш за две  партии составит:

• 0+3=3 при его 1-й стратегии;
• 4+1=5 при его 2-й стратегии;
• 2+0=2 при его 3-й стратегии.

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

При 1-й стратегии игрока 1 игрок 2 проигрывает 4, 1, 2 соответственно 1-й, 2-й, 3-й его стратегиям, а суммарный проигрыш за обе партии составит:

• 4+4=8 при его 1-й стратегии;
• 1+1=2 при его 2-й стратегии;
• 2+2=4 при его 3-й стратегии.

Все полученные данные занесём  в таблицу. В столбец u ставится наибольший суммарный выигрыш игрока 1 за две партии, деленный на число партий, т. е. 5/2; в столбец w ставится наименьший суммарный проигрыш игрока 2, деленный на число партий, т. е. 2/2; в столбец n ставится среднее арифметическое этих значений, т. е. 7/2.

 

но-мер пар тии	стратегия второго игрока	выигрыш игрока 1 при его  стратегиях			стратегия первого игрока	проигрыш игрока 2 при его стратегиях			u	w	n
		1	2	3		1	2	3
1 2	1 2	0 3	4 5	2 2	2 2	4 8	1 2	2 4	4 5/2	1 2/2	5/2 7/2

В третьей партии игрок 2 выбирает свою 2-ю стратегию, так  как из всех суммарных проигрышей наименьшим является 2.

 Таким образом,  продолжая этот процесс далее,  составим таблицу разыгрываний  игры за 20 итераций (партий).

 

но-мер пар тии	Страте- гия второго игрока	выигрыш игрока 1 при его  стратегиях			Страте- гия первого игрока	проигрыш игрока 2 при его стратегиях			u	w	n
		1	2	3		1	2	3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	1 2 2 2 3 3 1 3 3 3 3 3 2 2 2 2 2 2 2 3	0 3 6 9 10 11 11 12 13 14 15 16 19 22 25 28 31 34 37 38	4 5 6 7 9 11 15 17 19 21 23 25 26 27 27 29 30 31 32 34	2 2 2 2 5 8 10 13 16 19 22 25 25 25 25 25 25 25 25 28	2 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1	4 8 8 8 8 8 12 16 20 24 28 32 36 40 44 48 48 48 48 48	1 2 5 8 11 14 15 16 17 18 19 20 21 22 23 24 27 30 33 36	2 4 5 6 7 8 10 12 14 16 18 20 22 24 26 28 29 30 31 32	4 5/2 6/3 9/4 10/5 11/6 15/7 17/8 19/9 21/10 23/11 25/12 26/13 27/14 27/15 29/16 31/17 34/18 37/19 38/20	1 2/2 5/3 6/4 7/5 8/6 10/7 12/8 14/9 16/10 18/11 20/12 21/13 22/14 23/15 24/16 27/17 30/18 31/19 32/20	5/2 7/2 11/6 15/8 17/10 19/12 25/14 27/16 33/18 37/20 41/22 45/24 47/26 49/28 50/30 53/32 58/34 64/36 68/38 70/40

Из таблицы видно, что  в 20-ти проигранных партиях стратегии 1, 2, 3 для второго игрока встречаются  соответственно 2, 10, 8 раз, следовательно, их относительные частоты  равны 2/20, 10/20, 8/20. Стратегии 1, 2, 3 для игрока 1  встречаются соответственно 8, 12, 0 раз, следовательно, их относительные частоты равны 8/20, 12/20, 0, а приближённое значение цены игры равно 70/40.

Таким образом, получили приближённое решение игры: , , n=1,57.

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

1. Этот метод даёт возможность найти ориентировочное значение цены игры и приближённо вычислить оптимальные стратегии игроков.
2. Сложность и объём вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков (m  и n).

5. Монотонный итеративный алгоритм решения матричных игр

 

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

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

Рассмотрим смешанное  расширение =(X,Y,K) матричной игры ГА с матрицей А размера (m´n). Процесс разыгрывания игры состоит из нескольких шагов. Пусть каждый из игроков имеет конечное число стратегий.

Введём следующие обозначения:

аi – i-я строка матрицы  выигрышей;

xN=(x1N,x2N,…,xmN) ÎX – m-мерный вектор,  приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);

cN=( ) –n-мерный вектор, определяющий средний накопленный выигрыш на N-шаге. 

Зададим начальные условия. Пусть на 0-шаге с0= , x0=(0,…, 1,…, 0), где 1 занимает i0-ю позицию.

Определим итеративный  процесс  следующим образом: по известным  векторам xN-1, cN-1   находим векторы   xN и cN , которые вычисляются по следующим  формулам:

где параметр 0£eN£1, а векторы     вводятся далее.

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

. (4)

Запомним множество  индексов J^N-1=( ), (k<n), на которых   будет достигается этот минимум, т. е.

.

Далее рассмотрим подыгру  ГN игры   ГА с матрицей выигрышей АN={ }, i=1,…,m, jN-1ÎJN-1. Матрица выигрышей состоит из столбцов данной матрицы, номера которых определяются множеством индексов JN-1. В этой подыгре ГN находим одну из оптимальных смешанных стратегий игрока 1:  .

После нахождения , находим вектор по правилу:

.

И рассмотрим игру (2´n), в которой у игрока 1 две чистые стратегии, а у игрока 2 – n чистых стратегий. Эта игра задаётся матрицей , решая которую, находим вероятность использования игроком 1 своей стратегии. Это даёт нам коэффициент eN.

Далее вычисляем xN, сN и  переходим к следующему шагу. Процесс  продолжаем до тех пор, пока не выполнится равенство eN=0, потому что по теореме о минимаксе , а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.

 

Пример. Решить  игру с матрицей А= .

Итерация 0. 1. Пусть игрок 1 выбрал свою 1-ю стратегию, т. е. А0 = [0, 1, 2]. Тогда за начальные условия примем следующие: x0 = (1, 0, 0) – приближение оптимальной стратегии игрока 1; c0=a1=(0, 1, 2) – возможный выигрыш игрока 1.

Найдём множество индексов , на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: , значит множество индексов J0={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т. е. .

На этом шаге определим, пользуясь начальными значениями, компоненты векторов . Для этого рассмотрим подыгру . Для этой подыгры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.

Обозначим её через :  =(0, 1, 0). Зная  , можем вычислить =0а1+1а2+0а3=а2=(4, 2, 1).

Найдём e1. Для этого рассмотрим подыгру (2´3) с матрицей .  Решая матрицу графическим способом, получаем, что e1=1/2.

Проведённые вычисления позволяют найти значения векторов x1, c1: