Решение матричных игр методом Брауна

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

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

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

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

       . (1)

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

     

.

     Сходимость  алгоритма гарантируется следующей  теоремой.

Теорема.    .

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

     Пусть задано число ε>0. Требуется найти значение игры с точностью до величины ε , а также ε –максиминную и ε –минимаксную смешанные стратегии игроков.

     Метод Брауна состоит в многократном фиктивном  разыгрывании матричной игры, при  котором игроки по определенным правилам выбирают свои чистые стратегии. Пусть за k повторений игры первый игрок r_i раз выбрал стратегию i∊ I=1,…,m, а второй l_j раз выбрал стратегию j, j=1,…,n. Векторы частот выбора чистых стратегий

Являются смешанными стратегиями игроков.

2. Описание  алгоритма

Определим итерационный процесс Брауна.

Шаг 1. Игроки выбирают произвольно стратегии i₁ и j_1.

     Пусть за k повторений игры первый игрок выбрал стратегии i₁,…,i_k, а второй – стратегии j₁,…,j_k. При этом p(k) и q(k) – соответствующие векторы частот.

Шаг k+1. Игроки выбирают стратегии i_k+1 и j_k+1 из условий

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

     Покажем, что v₁(k) и v₂(k) – оценки для значения v матричной игры:

Действительно

     Для доказательства сходимости последовательностей {v₁(k)}, {v₂(k)} к значению игры v нам потребуется обобщенный итерационный процесс.

     Пусть c(0) – два вектора, удовлетворяющие условию Возьмем

     Пусть определены стратегии  и векторы c(0), c(1),…, c(k),  d(0), d(1),…, d(k). Возьмем

     И положим для всех i=1,…,m, j=1,…,n

     Таким образом, вектор c(k+1) есть сумма вектора c(0) и столбцов матрицы A с номерами j₁,…, j_k. Нетрудно видеть, что

     При нулевых векторах c(0) и d(0) построенный итерационный процесс совпадает с процессом Брауна. Поскольку множества и могут соержать более одного элемента последовательности {c(k)}, {d(k)} определяются в ходе итерационного процесса не однозначно.

Определим, как  и ранее, последовательности величин

     Далее будет доказана их сходимость к значению игры v для любых векторов c(0), d(0).

Из неравенств

Следует, что

Отсюда

(5.8)

Покажем, что

(5.9)

Будем использовать обозначение

   С помощью  него условие  можно записать в виде

3. Теоретическое обоснование

Определение Будем говорить, что i-ая строка (j-ый столбец)матрицы A существенна (существенен) на отрезке шагов [s, s+t], если для некоторого шага t’   i_t’=i (j_t’=j).

Лемма1  Пусть все строки и столбцыматрицы A существенны на отрезке шагов Тогда

Доказательство. Покажем сначала, что в условиях леммы справедливы неравенства

     Докажем (5.11) Пусть для l-ой строки выполнено равенство . Из условия луммы вытекает, что найдется такой номер шага t’ что Тогда

     Поскольку все последние разности не превосходят  at. Неравенство (5.12) доказывается аналогично. Покажем также, что справедливо неравенство

Пусть v^T – значение игры с матрицей A^T, транспонированной к A. Тогда

Отсюда

     Домножая  это неравенство на s+t выводим (5.13). Неравенство (5.10) получается сложением неравенств (5.11)-(5.13). Лемма доказана.

Лемма2.  Для произвольной матрицы A и произвольного ε>0 найдется такой номер шага k₀, что для любых последовательностей c(k), d(k), k=0,1,… итерационного процесса

Доказательство. Утверждение леммы верно для 1⨯1 матриц A, поскольку тогда c(k)=d(k) для всех k³1. Примем, что лемма верна для всех подматриц матрицы A и докажем, что она верна и для A. Выберем k₁ таким образом, чтобы для любых последовательностей c¹(k), d¹(k), k=0,1,… итерационного процесса, соответствующего подматрице A¹= (a_ij)_i∊I,j∊J, полученной из A вычеркиванием строки или столбца, было выполнено неравенство

     Докажем, что если для матрицы A некоторая строка (столбец) несущественна (несущественен) на отрезке [s,s+k₁], то справдедливо неравенство

     Предположим, например, что подматрица A¹ получается вычеркиванием из A несущественной l-й строки. Положим I={1,…,m}\{l},

     Поскольку l-я строка матрицы несущественна, и в итерационном процессе можно взять   Итерациооный процесс для матрицы A¹ можно продолжать и при k>k₁.

На основании  выбора k₁   

и неравенство (5.14) доказано.

     Мы  теперь можем показать, что для  любых последовательностей c(k), d(k), k=0,1,… итерационного процесса   при

     Рассмотрим  целое k>k₁ и представим его в виде k=(q+t)k₁ , где 0£q<1, а t>0 – целое (qk₁ – остаток от деления k на k₁).

Случай 1. Найдется такое целое положительное число h£t , что все строки и столбцы матрицы A на отрезке [(q+h-1)k₁,(q+h)k₁] существенны. Беря наибольшее из таких h имеем:

     Это неравенство получено повторным применением неравенства (5.14), поскольку на каждом из отрезков

Некоторая строка или столбец матрицы A несущественны.

Из леммы1 на основании выбора h имеем

Из (5.15) и (5.16) получаем

Случай 2. В каждом отрезке [(q+h-1)k₁,(q+h)k₁], h=1,…,t, некоторая строка или столбец несущественны. Следовательно, как и при выводе (5.15),

     В обоих случаях, используя неравенство  tk₁£k, получим Лемма доказана.

     Из  леммы2 вытекает неравенство (5.9) и сходимость последовательностей v₁(k),v₂(k), k=0,1,… к значению цены иигры v.

     Вернемся  к методу Брауна. Сформулируем правило  остановки. Пусть задано число ε>0. Будем останавливаться на шаге k₀, когда впервые выполнено неравенство

     Из (5.7) и (5.17) следует, что величины v₁(k₀),v₂(k₀) приближают значение v матричной игры с точностью до ε. Покажем, что p(k₀) – ε-максиминная стратегия первого игрока. Действительно,

Аналогично, q(k₀) – ε-минимаксная стратегия второго игрока.

Теорема. В методе Брауна а любые предельные точки p⁰, q⁰ последовательностей {p(k)}, {q(k)} являются оптимальными смешанными стратегиями игроков.

Доказательство. Сходимость последовательностей {v₁(k)} и {v₂(k)} к значению игры v вытекает из леммы2. Пусть p⁰ – любая предельная точка последовательности {p(k)}. Покажем, что p⁰ – оптимальная смешанная стратегия первого игрока. Действительно, поскольку последовательность {p(k)} принадлежит компакту P, без потери общности (выделяя соответствующую подпоследовательность) можно считать, что она сходится к p⁰.  Тогда

где ε_k→0+ . Переходя в этих неравенствах к пределу при k→∞, получим неравенство что означает оптимальность стратегии p⁰. Аналогично доказывается оптимальность для второго игрока любой предельной точки q⁰ последовательности {q(k)}  . Теорема доказана.

   Однако  оценка скорости сходимости процесса Брауна малоэффективна при больших  размерах матрицы A . Практически наблюдаемая скорость сходимости процесса существенно выше. 
 

 

4. Вывод

 

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