←предыдущая следующая→
1 2 3
процесса
Другой способ нахождения оптимальных стратегий игроков и седловой точки игры — решать матричную игру с помощью итерационных методов.
Рассмотрим простейший итерационный метод нахождения оптимальных стратегий в матричных играх - метод Брауна-Робинсона. Идея метода состоит в следующем: имитируется многократное повторение игры и набирается статистика, показывающая какие стратегии максимизируют выигрыш, и таким образом определяется оптимальная стратегия.
Для анализа антагонистической игры с матрицей
строится итерационный процесс, каждый шаг которого - розыгрыш игры. В первой игре у игроков ещё нет никакой информации, поэтому они выбирают свои стратегии произвольно. Положим для определённости, что в первой игре оба игрока всегда выбирают свои 1-е чистые стратегии:
k =1 ; ξ1 = (1,0,…,0); η1=(1,0,…,0).
Верхний индекс обозначает номер игры k. Предположим, состоялось k игр, в них игрок 1 использовал свою i-ю стратегию ξki раз, а игрок 2 использовал свою j-ю стратегию ηkj раз. Определим максимальный ожидаемый выигрыш игрока 1 и минимальный ожидаемый проигрыш игрока 2 с учётом результатов состоявшихся игр:
(15)
В (k + 1)-й игре игрок 1 должен использовать свою стратегию ik+1 , доставляющую максимальный ожидаемый выигрыш vmaxk, а игрок 2 – стратегию jk+1, обеспечивающую минимальный ожидаемый проигрыш vmink. Тогда векторы, координаты которых равны частотам, с которыми чистые стратегии обеспечивали максимальный выигрыш игроку 1 и минимальный проигрыш игроку 2
(16)
являются k-м приближением к оптимальным стратегиям игроков. При этом
является приближением к положению равновесия (седловой точке), так как седловая точка находится между vmaxk и vmink. Точность этого приближения можно оценить соотношением
Итерационный процесс сходится, т. е. после достаточного числа итераций можно получить решение с заданной точностью. Но у данного метода довольно малая скорость сходимости, т. е. для получения приемлемого решения необходимо выполнить большое число итераций.
Задачи
Принятие решений при совместных действиях. 1. задача
Магазин может завести в различных пропорциях товары типа (А, Б, В). Их реализация, а следовательно и прибыль (Сij) завися от вида товара и состояния спроса. Предполагая, что последний может характеризоваться тремя состояниями (1 2 3) и учитывая, что спрос зависит от моды и прогнозировать его невозможно, определить оптимальные пропорции в закупке товаров из условия гарантированной прибыли при следующих вариантах матриц.
1 2
вариант 1
При сведении этой задачи к задаче линейного программирования получаем результат
Седловая точка: 6,6
Оптимальная стратегия первого игрока:
x1 = 0,1
x2 = 0,1
x3 = 0,8
Оптимальная стратегия второго игрока:
y1 = 0,2
y2 = 0,6
y3 = 0,1
Это означает, оптимальные пропорции выпуска товаров являются:
10% доля товара А, 10% доля товара Б, 80% доля товара В.
При этом соотношении магазин получит доход не менее 6,6.
вариант 2
Седловая точка: 13,8
Оптимальная стратегия первого игрока:
x1 = 0
x2 = 0,8
x3 = 0,2
Оптимальная стратегия второго игрока:
y1 = 0,1
y2 = 0,9
y3 = 0
При данных матрицы 2 разумнее всего 80% продавать товара Б и 20% товара В, при этом товар А вообще не реализуется. Магазин получит доход не менее 13,8
Задача 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
Является ли игра с платежной матрицей
(60, 20)
(10, 50)
(20, 80)
(40, 70)
(40, 20)
(50, 30)
(80, 50)
(30, 60)
(90, 70)
Антагонистической?
Существуют ли в ней
1. ситуация равновесия в чистых стратегиях?
2. Вполне смешанная ситуация?
3. Ситуация оптимальная по Парето?
Чтобы назвать эту игру антагонистической нужно, чтобы выполнялось условие:
aij + bij = 0 или aij + bij = const , в данном случае игра не является антагонистической.
1. В игре не существует ситуация равновесия в чистых стратегиях.
2. В игре не существует вполне смешанной ситуации.
3. Расчет игровых ситуаций оптимальных по Паретто
Платежная матрица игрока 1
60 10 20
40 40 50
80 30 90
Платежная матрица игрока 2
20 50 80
70 20 30
50 60 70
Множество ситуаций, оптимальных по Парето, содержит 2 элемента: (1, 3) (3, 3)
←предыдущая следующая→
1 2 3