Методы приближённого решения матричных игр (стр. 2 из 4)
Цели игроков остаются прежними: игрок 1 желает получить максимальный выигрыш, а игрок 2 стремится свести свой проигрыш к минимуму. Поэтому для смешанного расширения игры, аналогичным образом определяются верхнее и нижнее значение цены игры, только теперь игроки выбирают свои смешанные стратегии. Обозначим их:
В этом случае остаётся справедливой лемма 1, т. е. 
.
Определение. Ситуация (x*, y*) в игре образует ситуацию равновесия, если для всех xÎX, yÎY выполняется равенство:
K(x, y*)≤K(x*,y*)≤K(x*,y).
Чтобы ситуация равновесия в смешанном расширении игры существовала необходимо и достаточно равенство верхней и нижней цен игры, т. е.
, где n - цена игры.Для случая смешанного расширения игры также справедлива лемма о масштабе.
Лемма о масштабе 2.
Пусть ГА и ГА/ - две матричные игры А/=aА+ В, , a=const, В – матрица с одинаковыми элементами b, т. е. bij=b для всех i, j.
Тогда Z( 
)=Z(ГА/) и nА/= anА+b (где nА/ - значение цены игры ГА/, nА - значение цены игры ГА). [17]
Теорема. В смешанном расширении матричной игры всегда существует ситуация равновесия. [17]
§2. Итеративный метод Брауна-Робинсона (метод фиктивного разыгрывания)
Часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры и приближённые оптимальные стратегии игроков.
Ориентировочное значение цены игры может дать уже простой анализ матрицы выигрышей и определение нижней и верхней цен игры. Если они близки, то поисками точного решения заниматься не обязательно, так как достаточно выбрать чистые минимаксные стратегии. Если же они не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых рассмотрим метод итераций.
Пусть разыгрывается матричная игра ГА с матрицей А={aij} размера (m´n). Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей. Одно разыгрывание игры будем называть партией, число которых неограниченно.
В 1-ой партии оба игрока выбирают совершенно произвольные чистые стратегии. Пусть игрок 1 выбрал i-ю стратегию, а игрок 2 – j-ю стратегию. Во второй партии игрок 1 отвечает на ход игрока 2 той своей стратегией, которая даёт ему максимальный выигрыш. В свою очередь, игрок 2, отвечает на этот ход игрока 1 своей стратегией, которая обращает его проигрыш в минимум. Далее третья партия.
С ростом числа шагов процесса смешанные стратегии, которые приписываются игрокам, приближаются к их оптимальным стратегиям. Этот процесс приближённого нахождения оптимальных стратегий игроков называется итеративным , а его шаги – итерациями.
Итак, предположим, что за первые kразыгрываний игрок 1 использовал i-ю чистую стратегию
ikраз (i=1,…,m), а игрок 2 j-ю чистую стратегию 
раз (j=1,…,n). Тогда их смешанными стратегиями будут векторы 
.Игрок 1 следит за действиями игрока 2 и с каждым своим ходом желает получить как можно больший выигрыш. Поэтому в ответ на применение игроком 2 своей смешанной стратегии yk, он будет использовать чистую стратегию ik+1 , которая обеспечит ему лучший результат при разыгрывании (k+1)-ой партии. Игрок 2 поступает аналогично. В худшем случае каждый из них может получить:
где
- наибольшее значение проигрыша игрока 2 и 
- наименьшее значение выигрыша игрока 1.Рассмотрим отношения, которые определяют средние значения проигрыша игрока 2 и выигрыша игрока 1:
Пусть ν - цена матричной игры ГА. Её значение будет больше выигрыша игрока 1, но меньше проигрыша игрока 2, т. е.
. (1)Таким образом, получен итеративный процесс, позволяющий находить приближённое решение матричной игры, при этом степень близости приближения к истинному значению игры определяется длиной интервала
.Сходимость алгоритма гарантируется следующей теоремой.
Теорема. 
.
Схема доказательства.
Лемма. Для всякой матрицы А и "e>0 существует такое k0, что
.
При предельном переходе в неравенстве (1) при k®¥имеем:
. (2)
Отсюда получаем оценку разности пределов:
.
Из леммы следует, что
.
На основании неравенства (1) имеем: 
.
Следовательно, в силу ограниченности пределов
.
Получаем оценку для разности пределов:
для "e>0.
Можем заключить, что 
. Осталось показать равенство пределов n. Это следует из неравенства (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 | ||||||
| 12 | 1 2 | 0 3 | 4 5 | 2 2 | 2 2 | 4 8 | 1 2 | 2 4 | 45/2 | 1 2/2 | 5/2 7/2 |
В третьей партии игрок 2 выбирает свою 2-ю стратегию, так как из всех суммарных проигрышей наименьшим является 2.