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

Также универсальным, но менее трудоемким по сравнению с методом линейного программирования в плане затрат вычислительных ресурсов является приближенный метод Брауна-Робинсона. Данный итерационный метод предназначен для решения любой игры G(mn), не требуя никаких ограничений на элементы матрицы игры.

Метод базируется на многократном разыгрывании игры и подсчете верхней и нижней оценок цены игры с занесением результатов в таблицу специального вида (табл. 3.11):

Таблица 3.12

Каждая строка таблицы соответствует однократному розыгрышу игры (партии игры).

Поясним записи в соответствующих позициях:

• k— номер партии (итерации);

• iиj— номера стратегий, выбранных соответственно игрокамиA иBв данной партии;

• B_1, …, B_n— накопленный заkпартий выигрыш игрокаAпри выборе им стратегииA_i в данной партии и ответе игрокомBсоответственно стратегиямиB_1, …, B_n;

• A_1, …, A_m— накопленный заkпартий выигрыш игрокаAпри выборе игрокомBстратегииB_j в данной партии и ответе игрокомAсоответственно стратегиямиA_1, …, A_m;

• V—нижняя оценка цены игры (минимальный накопленный выигрыш, поделенный наk);

• — верхняя оценка цены игры (максимальный накопленный выигрыш, поделенный наk);

• .

В [6] доказано, что при k:V^* V, ,,

где V– цена игры,N_i иN_j – число применений соответственно стратегийА_i иB_j за kпартий,p_i иq_j – значения вероятностей в оптимальных стратегияхS_A = (p_i), i = 1, …,m, S_B = (q_j), j = 1,…,n, игроковAиB соответственно.

Проиллюстрируем метод на примере игры G(33), представленной табл. 3.12.

Таблица 3.13

Bj Ai	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

Требуется найти решение – пару оптимальных смешанных стратегий (S_A, S_B),S_A = (p₁,p₂,p₃), S_B = (q₁,q₂,q₃), и цену игрыV.

Будем искать пару смешанных стратегий S_A = (p₁,p₂,p₃), p₁+p₂+p₃= 1, S_B = (q₁,q₂,q₃), q₁+q₂+q₃= 1 и цену игрыV.

Построим табл. 3.13 для первых десяти итераций.

Таблица 3.14

Поясним процесс заполнения табл. 3.13.

Пусть начинает (k = 1) игрокAи выбирает на первом шаге стратегиюА₁. Его выигрыш в зависимости от выбора игрокаBможет равняться 9 (при выборе стратегииB₁), 0 (при выбореB₂) или 11 (при выбореB₃). Поскольку теперь выбор за игрокомB(а он заинтересован в минимизации выигрыша игрокаA), то выделим (жирным шрифтом) минимальный выигрыш 0, соответствующий стратегииB₂. Следовательно игрокуBвыгоднее всего ответить стратегиейB₂, что, в свою очередь, может привести к выигрышу игрокаAпри его ответе в следующей партии, равному 2 (при выборе стратегииA₁), 9 (A₂) или 0 (A₃). Так как игрокAзаинтересован в максимизации выигрыша, то выделим максимальный выигрыш 9 (дляA₂). Соответствующие значенияV,иV^* равны 0; 9 и 4,5.

Во второй партии (k = 2) игрокуA, следовательно, выгодно выбрать стратегию A₂, которая позволит ему накопить выигрыш, равный соответственно 11 (дляB₁), 9 (дляB₂) или 11 (дляB₃) и т.д. Заметим, что дляk = 4 в столбцахА₁ иА₃ получаются одинаковые накопленные выигрыши (22), поэтому игрокA в пятой партии может выбрать как стратегиюА₁, так иА₃.

К сожалению (что видно и по табл. 3.12), сходимость данного метода довольно слабая, но существуют методы ее ускорения. Критерием останова можно выбрать достаточную стабильность величины V^* при увеличении числа итераций.

Для рассматриваемого примера в итоге получим:

и, что соответствует точному решению, полученному, например, методом Лагранжа.

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