Теоретико-игровые методы принятия решений (Еремеев А. П.) (545581), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

где 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

Требуется найти решение – пару оптимальных смешанных стратегий (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^* при увеличении числа итераций.

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

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

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

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

Рассмотрим следующую задачу. Проводится конкурс на реализацию двух проектов, в котором участвует два претендента – конструкторское бюро 1 (КБ1), имеющее 4 отдела, и конструкторское бюро 2 (КБ2), имеющее 3 отдела. Финансирование первого проекта – 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.15

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

Таблица 3.16

Таблица 3.17

Решив данную игру, например, методом Лагранжа, получим: 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 = 5a / 4, V_КБ2 = 3a / 4.

Характеристики

Список файлов книги