Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Метод Брауна Системы массового обслуживания
Матрица рисков Седловая точка Платежная матрица Цена игры
Смешанные стратегии Матричная игра онлайн Чистые стратегии

Итерационный метод Брауна-Робинсона

Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.
В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.

Достоинства метода Брауна:

  1. Этот метод ориентирован на произвольную игру G(m×n).
  2. Не требует условия aij>0.
  3. Легко реализуем программными методами.

Недостатки метода Брауна: скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры.
Рассмотрим метод на примере игры G(3×3).

Ai \ Bj B1 B2 B3
A1 7 2 9
A2 2 9 0
A3 9 0 11
SA=(p1,p2,p3)

SB=(q1,q2,q3)

Строится следующая матрица:

k i B1 B2 B3 j A1 A2 A3 VminVmaxV*
1 3 9 0 11 2 2 9 0 0 9 4.5
2 2 11 9 11 2 4 18 0 4.5 9 6.75
3 2 13 18 11 3 13 18 11 3.67 6 4.84
4 2 13 18 11 3 22 18 22
5
где:
k – номер партии.
i – номер стратегии, выбираемой игроком A.
j – номер стратегии, выбираемой игроком В.
Bi– накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bi.
Аj – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аj.
Vmin – нижняя оценка игры = min (накопленный выигрыш)/k.
Vmax – верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что
V*=(Vmin+Vmix)/2, V* à V при k à ¥ и


Ni - сколько раз выбирается Аi стратегия.
Nj - сколько раз выбирается Bj стратегия.
Итерационный процесс метода Брауна-Робинсон не является, вообще говоря, монотонным. Кроме того, скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры. Однако он обладает одним неоспоримым преимуществом, которое заключается в исключительной простоте программирования метода.

Размерность платежной матрицы x

Пример.
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки B1 B2 B3 a = min(Ai)
A1 6 1 4 1
A2 2 4 2 2
A3 4 3 5 3
b = max(Bi) 6 4 5
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 3, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 4.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 3 <= y <= 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
k i B1 B2 B3 j A1 A2 A3 Vmin Vmax Vср
1 1 6 1 4 2 1 4 3 1 4 5/2
2 2 8 5 6 2 2 8 6 5/2 4 13/4
3 2 10 9 8 3 6 10 11 8/3 11/3 19/6
4 3 14 12 13 2 7 14 14 3 7/2 13/4
5 2 16 16 15 3 11 16 19 3 19/5 17/5
6 3 20 19 20 2 12 20 22 19/6 11/3 41/12
7 3 24 22 25 2 13 24 25 22/7 25/7 47/14
8 3 28 25 30 2 14 28 28 25/8 7/2 53/16
9 2 30 29 32 2 15 32 31 29/9 32/9 61/18
10 2 32 33 34 1 21 34 35 16/5 7/2 67/20
11 3 36 36 39 1 27 36 39 36/11 39/11 75/22
12 3 40 39 44 2 28 40 42 13/4 7/2 27/8
13 3 44 42 49 2 29 44 45 42/13 45/13 87/26
14 3 48 45 54 2 30 48 48 45/14 24/7 93/28
15 2 50 49 56 2 31 52 51 49/15 52/15 101/30
16 2 52 53 58 1 37 54 55 13/4 55/16 107/32
17 3 56 56 63 1 43 56 59 56/17 59/17 115/34
18 3 60 59 68 2 44 60 62 59/18 31/9 121/36
19 3 64 62 73 2 45 64 65 62/19 65/19 127/38
20 3 68 65 78 2 46 68 68 13/4 17/5 133/40
NA1 = 1
P(A1) = 1/20 = 1/20
NA2 = 7
P(A2) = 7/20 = 7/20
NA3 = 12
P(A3) = 12/20 = 3/5
NB1 = 4
P(B4) = 4/20 = 1/5
NB2 = 14
P(B4) = 14/20 = 7/10
NB3 = 2
P(B4) = 2/20 = 1/10
Цена игры, W = 133/40
p = (1/20, 7/20, 3/5)
q = (1/5, 7/10, 1/10)