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

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

 

5. Приложение

 

   Задача 1.

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

А=

.

     Пусть игру начнёт игрок 2. Он произвольно  выбирает одну из своих чистых стратегий. Предположим, что он выбрал свою 1-ю  стратегию, а игрок 1 отвечает своей 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.

 

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

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

 

     Из  таблицы видно, что в 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.

     Таким образом, получили приближённое решение  игры: x²⁰=(1/10, 1/2, 2/5), y²⁰=(2/5, 3/5, 0), n=1,57.  

Задача 2.

      Магазин  может завести в различных пропорциях товары типа (А, Б, В). Их реализация, а следовательно и прибыль (С_ij) завися от вида товара и состояния спроса. Предполагая, что последний может характеризоваться тремя состояниями (1 2 3) и учитывая, что спрос зависит от моды и прогнозировать его невозможно, определить оптимальные пропорции в закупке товаров из условия гарантированной прибыли при следующей  матрице.

Точность: 0,5

Седловая точка: 14,8

Оптимальная стратегия  первого игрока:

x1 = 0,3

x2 = 0

x3 = 0,7

Оптимальная стратегия второго игрока:

y1 = 0,1

y2 = 0

y3 = 0,9

      Методом Брауна установлено, что наилучший  вариант реализации продукции для магазина 30% товара А, 70% товара В. При этом гарантирован доход 14,8. 

Задача 3.

Пусть  ε = 1/5, а матрица игры – 

Отметим, решение  игры в смешанных стратегиях имеет вид

     Применяя  метод Брауна, найдем приближенное значение игры, а также ε-максиминную  и ε-минимаксную смешанные стратегии  игроков. Вычисления удобно производить  в форме таблицы. В каждой ее k-ой строке подчеркнуты наибольшие значения величин c_i(k) , i=1,2,3  и наименьшие значения величин d_j(k), j=1,2,3

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

Задача 4.

      Типичное  поведение различных методов  решения систем нелинейных уравнений  отражает следующий пример

Пусть ищется решение  системы

В окрестности точки x₀=0, y₀=-1.

      Результаты  применения к этой системе разных итерационных процессов, начинающихся с данной точки (x₀,y₀)и заканчивающихся как только выполнится неравенство

      Где k – номер итерации, представлены в таблице ниже. В ней приведены приближенные решения, полученные на k-й итерации с помощью девяти перечисленных там методов, значения k, при которых сработал критерий останова с ε=0,000001, а также векторы невязок, характеризующие некоторую меру близости указанного приближения к точному решению системы. При этом всюду шаг аппроксимации производных (начальный шаг в методах секущих и Брауна) брался равным ε в каждой компоненте.

 

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

*) – Аппроксимация производных на k-q итерации осуществлялась с шагом h_k=min{|p_k|, |q_k|}.

**) – С постоянной  матрицей  и переменным вектором d=F(x^(k)), т.е. с полюсами  

 

6. Библиография

 

1. Васин А.А., Морозов В.В. «Введение в теорию игр с приложениями к экономике»(учебное пособие). – М.:2003
2. Вержбицкий, В.М. «Основы численных методов:Учебник для вузов». – М.: Высш. шк., 2002.
3. Дюбин Г.Н., Суздаль В.Г. «Введение в прикладную теорию игр». – М.: Наука, 1981.
4. Э.Г. Давыдов. «Методы и модели теории антагонистических игр». Издательство МГУ, 1978г.
5. http://gos-asu.narod.ru
6. http://intuit.ru