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

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

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

Таблица 3.11

k	i	B 1	…	Bn	j	A 1	…	Am	V		V*

 

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

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

· 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.12

Bj Ai	B1	B 2	B 3
A 1	7	2	9
A 2	2	9	0
A 3	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.13

k	i	B 1	B 2	B 3	j	A 1	A 2	A 3	V	` V	V*
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	15	27	11	4	22	18	22	2,75	5,5	4,13
5	1	22	29	20	3	31	18	33	4,0	6,6	5,3
6	3	31	29	31	2	33	27	33	4,84	5,5	5,17
7	1	38	31	40	2	35	36	33	4,43	5,14	4,79
8	2	40	40	40	2	37	45	33	5,0	5,61	5,30
9	2	42	49	40	3	46	45	44	4,45	5,11	4,78
10	1	49	51	49	1	53	47	53	4,90	5,30	5,1

 

Поясним процесс заполнения табл. 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^* при увеличении числа итераций.

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

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

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

Практический пример

Рассмотрим следующую задачу. Проводится конкурс на реализацию двух проектов, в котором участвует два претендента – конструкторское бюро 1 (КБ1), имеющее 4 отдела, и конструкторское бюро 2 (КБ2), имеющее 3 отдела. Финансирование первого проекта – a денежных единиц, второго – b. Практика проведения данного конкурса показывает, что, как правило, проект достаётся тому КБ, которое выделяет большее число отделов на его выполнение. Если каждое КБ выделяет одинаковое число отделов на выполнение проекта, то они имеют одинаковую вероятность на его получение. Требуется определить, сколько отделов следует выделить каждому КБ на выполнение первого и второго проектов с целью максимизации их финансирования.

Если в качестве стратегии КБ взять пару (a, b), где a и b – количество отделов, выделяемых соответственно под первый и второй проекты, то у КБ1 (игрока A) имеется 5 стратегий: A ₁=(4; 0), A ₂=(3; 1), A ₃=(2; 2), A ₄=(1; 3), A ₅=(0; 4), а у КБ2 (игрока B) – 4 стратегии: B ₁=(3; 0), B ₂=(2; 1), B ₃=(1; 2), B ₄=(0; 3).

Так как целью каждого из игроков является максимизация собственного выигрыша (возможного финансирования), то соответствующая парная игра G (5´4)не является антагонистической (выигрыш одного игрока не равен проигрышу другого).

Для того чтобы свести данную игру к антагонистической необходимо из выигрышей a_ij игрока A вычесть средний выигрыш – (a + b) / 2. В итоге получим антагонистическую игру G (5´4), представленную табл. 3.14.

Таблица 3.14

	В 1	В 2	В 3	В 4
А 1	а / 2	(a – b) / 2	(a – b) / 2	(a – b) / 2
А 2	b / 2	a / 2	(a – b) / 2	(a – b) / 2
А 3	(b – a) / 2	b / 2	a / 2	(a – b) / 2
А 4	(b – a) / 2	(b – a) / 2	b / 2	a / 2
А 5	(b – a) / 2	(b – a) / 2	(b – a) / 2	b / 2

 

Рассмотрим случай а = b, представленный табл. 3.15. Упростим игру, удалив доминируемые и дублируемые стратегии A ₁, A ₅, B ₂, B ₃, A ₃. Получим игру G (2´2), представленную табл. 3.16.

 

Таблица 3.15

Bj Ai	В1	В2	В3	В4
А1	a / 2	0	0	0
А2	a / 2	a / 2	0	0
А3	0	a / 2	a / 2	0
А4	0	0	a / 2	a / 2
А5	0	0	0	a / 2

 

Таблица 3.16

Bj Ai	В1	В4
А2	a / 2	0
А4	0	a / 2

 

Решив данную игру, например, методом Лагранжа, получим: p ₂= p ₄=0,5; q ₁= q ₄=0,5; V = a/ 4.

Тогда для исходной игры G (5´4)решением будет: S_A =(0,0; 0,5; 0,0; 0,5; 0,0), S_B =(0,5; 0,0; 0,0; 0,5), V _КБ1= a / 4 + a =5 a / 4, V _КБ2=3 a / 4.

Полученный результат означает, что КБ1 рекомендуется использовать равновероятно стратегии A ₂или A ₄, т.е. распределить отделы между проектами в соотношении 3 к 1 или 1 к 3 с ожидаемым финансированием 5 a / 4, а КБ2 – стратегии B ₁или B ₄, т.е. направить все усилия (отделы) на выполнение одного из проектов с ожидаемым финансированием 3 a / 4.