double arrow

Лекция 8. Приближенное решение матричной игры в смешанных стратегиях (модифицированный метод Брауна)

2

Приближенное решение матричной игры в смешанных стратегиях (модифицированный метод Брауна)

0. Общая характеристика условий применимости метода Брауна: приближенное решение с меньшими трудозатратами.

1. Описание метода Брауна

2. Алгоритм модифицированного метода Брауна:

2.1. Обозначения

2.2. Алгоритм

2.3. Пример

Модифицированный метод Брауна

О П Р Е Д Е Л Е Н И Я

Кп.1. Идея метода Брауна

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

Первый игрок выбирает произвольно свою чистую стратегию i(1). Зная ее, 2-й игрок выбирает свою стратегию, стремясь минимизировать выигрыш 1-ого игрока. Здесь предполагается, что 2-й игрок лучше информирован о ходе игры, чем первый. Результат выбора – j(1). Первая итерация закончена.

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

Далее первый игрок выбирает ход i(3), в предположении, что второй игрок применяет стратегии j(1) и j(2) с вероятностями . Теперь второй игрок знает о выборе первым стратегий i(1), i(2), i(3) и выбирает свой ход j(3), полагая, что первый игрок применяет стратегии i(1), i(2), i(3) с вероятностями. Третья итерация закончена.

Доказано, что при этих условиях при числе итераций получаются оптимальные смешанные стратегии.

Кп/п2.1. Обозначения:

- элемент матрицы платежа (выигрыш 1-ого игрока при использовании 1-ой стороной стратегии i, а противником – стратегии j),

K – номер итерации в методе, (- тоже самое)

- номер стратегии, выбираемой 1-ой стороной на -ом шаге

- номер стратегии, выбираемой 2-ой стороной на -ом шаге

(тоже

- последовательности чистых стратегий, применяемых 1-ой и 2-ой сторонами соответственно за К шагов,

- возможный суммарный выигрыш 1-ой стороны за К шагов в ситуации, когда суммирование ведется с 1-ого по К-ый шаг при использовании 1-ой стороной последовательности чистых стратегий , а вторая сторона применяет всегда одну и ту же стратегию j,

(1)

- гарантированный выигрыш 1-ой (2)

стороны на -ой итерации использования ею на -ой итерации чистой стратегии ;

(3)

- средний за К шагов гарантированный выигрыш 1-ой стороны, при использовании ею чистых стратегий из с равной вероятностью

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

(4)

(5)

- максимальный возможный выигрыш 1-ой стороны на -ом шаге при использовании второй стороной стратегии ,

- максимальный средний за К шагов выигрыш 1-ой стороны при применении 2-ой стороной последовательности чистых стратегий G(K),

(6)

(7)

(8)

; - очень большое число

- заданная точность расчетов, - достаточно малая положительная величина;

,

- цена игры за К шагов,

,

Кп/п2.2. Алгоритм.

На 1-ой итерации выбираем произвольно i(1). При данном подсчитываем . Затем определяем . При данном вычисляем величины . Определяем . Подсчитываем и .

Конец первой итерации.

Эти данные заносим в таблицу.

K I(K) MJ(K)1 ….. MJ(K)n Ai(K) J(K) Д1 G(K) …. Дm G(K)
                         

и т.д.

Расчеты заканчиваются, если .

- номер итерации, где ……….

Кп.3. Пример

K i(k) MJ(k)1 MJ(k)2 AJ(k) j(k) Д1 G(k) Д2 G(k) BG(k)
5/2=2,5 6/2=3 2,5 0,5
6/3=2 8/3=2,66 2,5 2,66 0,16
10/4=2,5 10/4=2,5 2,5 2,5
не делаем т.к.              

Оптимальные смешанные стратегии:

2

Сейчас читают про: