Сведение конечной матричной игры к задаче линейного программирования

Рассмотрим матричную игру тхп с платежной матрицей U = Щ-/||.

Пусть у игроков А и В имеются в распоряжении соответственно тип чистых стратегий: {А₁;А₂; и {В_ХВ₂ И пусть.

р = (р] р₂ р_т) q = (9il •••'Уп) ~ произвольные смешанные стратегии игроков А и B_f а и — платеж, получаемый игроком Л от игрока # в конце игры. По аналогии с двумерным случаем задача эквивалентна задаче линейного программирования на максимум величины v на допустимом множестве К, задаваемом системой неравенств.

Добавив ограничения неотрицательности и нормировки на р, получим задачу.

Переменными в задаче являются v, р^ р₂,.р_т.

Целевая функция f (v, p_vp₂,…, p_m) = v.

Если v > 0, то размерность задачи линейного программирования можно уменьшить на единицу, введя новые переменные

Оптимумом в задаче является нижняя цена игры

Если условие v > 0 не выполнено, то всегда можно перейти к игре с положительными значениями выигрышей, прибавив к матрице игры некоторую положительную константу так, чтобы это условие выполнялось. При этом на ту же константу увеличится и цена игры. Это, однако, не повлияет на решение игры (выбор стратегий). Нетрудно убедиться, что и более общее линейное преобразование платежной матрицы й_1; = au_Vj + b, где а > 0; b — произвольные постоянные, не изменяет решения игры, а цена игры изменяется по тому же правилу — V = aV + Ъ'.

Что касается вектора вероятностей i = (q_l', q₂',, то для него можно выписать аналогичную задачу линейного программирования.

Задачи (2.3) и (2.5) можно решать, например, с помощью программы Excel, используя надстройку «Поиск решений».

Пример 2.12. Решить игру, заданную матрицей.

Решение.

Составляем задачу линейного программирования:

Решая эту задачу линейного программирования симплекс-методом либо с помощью компьютерных программ, например Excel, можно получить:

. Из симметричности матрицы игры вытекает, что оптимальная стратегия второго игрока равна . Цена игры: v = 0.

Возвращаясь к задаче линейного программирования (2.4), построим двойственную к ней задачу:

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

q;

Путем ввода новых переменных у = — получим систему (2.6).

^J v

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

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

В следующем параграфе мы увидим, как применяется это правило.

Пример 2.13. Решить антагонистическую матричную игру:

Нетрудно увидеть, что а У с и h>d. Поэтому игра эквивалентна следующей:

Далее, y>t. Напомним, что матрица выигрышей первого игрока одновременно является и матрицей проигрышей второго игрока. Поэтому второй игрок выбирает столбец с меньшими проигрышами. Исключив строго доминируемые стратегии, получим эквивалентную матрицу.

Для строго доминируемых стратегий игроков положим равными нулю их вероятности:

Если второй игрок выбирает чистую стратегию х, а первый — смешанную стратегию ра + (- р) Ь, то математическое ожидание выигрыша первого игрока равно U_x—p + l {-р) — прямая х (рис. 2.6).

Рис. 2.6.

Если второй игрок выбирает чистую стратегию у, а первый — смешанную стратегию ра + (1- р) Ь, то математическое ожидание выигрыша первого игрока равно U_y =4-р + 1-(1-р) — прямая у на рис. 2.6.

Если второй игрок выбирает чистую стратегию z, а первый — смешанную стратегию ра + ( 1 — р)Ь, то математическое ожидание выигрыша первого игрока равно U_z = 9 • р + (-4) • (1 — р) — прямая z на рис. 2.6.

Пусть теперь первый игрок выбирает смешанную стратегию pa + (1 — р)Ь, а второй — смешанную стратегию (q_x; q_yq_z). Зафиксируем какое-нибудь значение р, например р = 0,2, и проведем вертикальную прямую через эту точку. Тогда ординаты точек А, В и С пересечения вертикальной прямой с тремя прямыми показывают выигрыши первого игрока при применении им смешанной стратегии и чистых стратегиях х, у и 2 второго игрока. Если же и второй игрок будет применять смешанные стратегии, то все возможные значения выигрышей первого игрока будут укладываться на отрезке АС (от наименьшего значения выигрыша в точке С до наибольшего значения в точке А). В точке С при заданном значении р достигается наименьший выигрыш первого игрока Решая эту задачу при каждом значении р, получим ломаную линию /(р) (минимальная огибающая — жирная линия на графике). Далее выбираем точку максимума (М) на жирной ломаной . Ордината точки М — это и есть цена игры. Абсцисса точки М показывает осторожную стратегию первого игрока.

Наибольшее значение жирная ломаная достигает при , Значит, Следовательно, для первого игрока оптимальной является стратегия . Ордината точки М определяет цену игры v = 3.

Из рисунка следует также, что стратегия z не участвует в формировании точки М. Это означает, что q_z =0. Стратегии х и у участвуют в формировании точки М. Второму игроку следует выбирать значения вероятностей q_x и q_y такими, при которых ему будет безразлично, выберет первый игрок ход а или Ь, т. е.

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

Ответ: оптимальные стратегии игроков: цена игры.

v = 3.

Пример 2.14. Решить матричную игру

Решение

Пусть первый игрок выбирает смешанную стратегию ра + (-р)Ь.

При выборе вторым игроком чистой стратегии х математическое ожидание выигрыша первого игрока равно Uf (р) = 4-р + 0-(1-р) = 4р.

При выборе вторым игроком чистой стратегии у математическое ожидание выигрыша первого игрока равно Uf (р) = 1 • р + 5 • (1 — р).

При выборе вторым игроком чистой стратегии z математическое ожидание выигрыша первого игрока равно Uf (р) = 2 • р + 2 • (1 — р) = 2.

Изобразим графики этих функций на рис. 2.7.

Рис. 2.7.

Максиминная стратегия первого игрока соответствует точке максимума на минимальной ломаной (жирной линии). В данном случае максимум достигается на множестве точек отрезка MN. Следовательно, оптимальной стратегией первого игрока является ра + (-р)Ь, где. Цена игры равна 2.

Найдем теперь оптимальные стратегии второго игрока. Если

то чистые стратегии х и у неактивны (не участвуют в формировании точек интервала MN) и, следовательно, q_x =q_y =0. И поэтому q_z= 1, что соответствует чистой стратегии г.

Если , что соответствует точке М, то стратегия у неактивна и q_y = 0.

Тогда любые комбинации стратегий х и z будут эквивалентны. Решением будет стратегия qx + (1 — q)z, где q G [0; 1].

Аналогично при (что соответствует точке N) стратегия х неактивна и q_x = 0. Тогда любые комбинации стратегий у и 2 будут эквивалентны. Решением будет стратегия qy + (-q)z, где

Ответ', решением игры являются следующие совокупности стратегий игроков:

цена игры равна 2.

Пример 2.15. Решить матричную игру Решение

Изобразим, как и ранее, на графике средние выигрыши первого игрока при выборе им смешанной стратегии ра + { - р) Ь и выборе вторым игроком чистых стратегий (рис. 2.8).

Рис. 2.8.

Максиминная стратегия первого игрока дает значение и цену игры v=2.

(точка М). При этом второму игроку совершенно безразлично, какую стратегию он будет выбирать. Получим систему.

Ответ: решением игры является совокупность стратегий игроков Пример 2.16. Решить матричную игру.

Решение

Изобразим на графике средние выигрыши первого игрока при выборе им смешанной стратегии рп + (1 —р)т и выборе вторым игроком чистых стратегий.

Поскольку в матрицу входит параметр, то проследим за изменением решения в зависимости от параметра а.

1. Случай а > 4. Тогда максимум минимальной ломаной достигается 2.

в точке р = — (рис. 2.9).

Рис. 2.9.

Третье ограничение (z) неэффективно. Следовательно,.

2. Случай а е (1; 4). Тогда эффективными в точке М становятся стратегии у и z (рис. 2.10).

Рис. 2.10.

Имеем

Первое ограничение (х) неэффективно. Следовательно,.

3. Случай -2 < а < 1. Тогда третья стратегия второго игрока становится доминирующей (рис. 2.11).

Рис. 2.11.

Максимальный гарантированный выигрыш достигается в точке р_а =1. Тогда р = (1; 0); q = (0; 0; 1); v — а.

4. Случай а<-2. Тогда третья стратегия второго игрока доминирующая (рис. 2.12).

Рис. 2.12.

Максимальный гарантированный выигрыш достигается в точке р_а = 0.

Тогда р = (0; 1); q = (0; 0; 1); v = -2.

5. Случай а = 4. Тогда v = 2. Этот случай рассмотрен в предыдущем примере:

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

6. Случай а = 1. Тогдар = 1, т. е. р = (1; 0), v = 1. Кроме того, поскольку первое ограничение неэффективно, то q_x = 0. Далее, потребуем, чтобы р = 1 было наилучшим ответом первого игрока на стратегию q = (0; q 1 — q). Для этого необходимо выполнение неравенства Получим

7. Случай