9. РЕШЕНИЕ ИГР mxn

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

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

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

Действительно, рассмотрим игру стратегиями игрока Лил стратегиями игрока В. Задана матрица игры

Требуется найти решение игры, т. е. две оптимальные смешанные стратегии игроков А и В:

где

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

Найдем сначала оптимальную стратегию Эта стратегия должна обеспечить нам выигрыш, не меньший v, при любом поведении противника, и выигрыш, равный v, при его оптимальном поведении (т. е. при стратегии

Цена игры v нам пока неизвестна. Не нарушая общности, можно предположить ее равной некоторому положительному числу Действительно, для того чтобы выполнялось условие достаточно, чтобы все элементы матрицы были неотрицательными. Этого всегда можно добиться, прибавляя ко всем элементам матрицы одну и ту же достаточно большую положительную величину М; при этом цена игры увеличится на М, а решение не изменится. Итак, будем считать

Предположим, что мы (А) применяем свою оптимальную стратегию а противник (В) свою чистую стратегию Тогда наш средний выигрыш будет равен:

Наша оптимальная стратегия обладает тем свойством, что при любом поведении противника обеспечивает нам выигрыш, не меньший, чем цена игры v; значит, любое из чисел не может быть меньше v.

Получаем ряд условий:

Разделим неравенства (9.1) на положительную величину v и введем обозначения:

Тогда условия (9.1) запишутся в виде:

где — неотрицательные переменные. В силу (9.2) и того, что переменные удовлетворяют условию

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

Определить неотрицательные значения переменных так, чтобы они удовлетворяли линейным ограничениям (9,3) и при этом их линейная функция

обращалась в минимум.

Перед нами — типичная задача линейного программирования.

Таким образом, решая задачу линейного программирования, мы можем найти оптимальную стратегию игрока А.

Найдем теперь оптимальную стратегию игрока В. Все будет аналогично решению игры для игрока А, с той разницей, что игрок В стремится не максимизировать, а минимизировать выигрыш, а значит, не минимизировать, а максимизировать величину Вместо условий (9.3) должны будут соблюдаться условия:

где — неотрицательные переменные, равные

Требуется так выбрать переменные чтобы они удовлетворяли условиям (9.6) и обращали в максимум линейную функцию

Вместо того чтобы максимизировать функцию (9.7), можно, как мы знаем, минимизировать функцию

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

Попутно заметим, что из сведения задачи решения игры к задаче линейного программирования вытекают соображения по поводу существования решения игры

Действительно, пусть задача о нахождении оптимальной стратегии игрока А сведена к задаче линейного программирования с условиями-неравенствами (9.3) и минимизируемой функцией (9.5). Всегда ли существует ее решение? Мы знаем (см. гл. 2), что решение задачи линейного программирования может и не существовать; оно отсутствует, если:

1) условия (равенства или неравенства) вообще не имеют допустимых неотрицательных решений;

2) допустимые решения существуют, но среди них нет оптимального, так как минимизируемая функция не ограничена снизу.

Посмотрим, как обстоит дело в нашем случае. Нетрудно убедиться, что допустимое решение ЗЛП в нашем случае всегда существует. Действительно, сделаем элементы матрицы строго положительными (для этого достаточно прибавить к каждому из них достаточно большое число М) и обозначим наименьший элемент матрицы через

Положим теперь Нетрудно видеть, что эта система значений переменных представляет собой допустимое решение ЗЛП — все они неотрицательны, и их совокупность удовлетворяет условиям (9.3).

Теперь убедимся, что линейная функция (9.5) не может быть не ограничена снизу. Действительно, все неотрицательны, а коэффициенты при них в выражении (9.5) положительны, значит, функция L в формуле (9.5) тоже неотрицательна, значит, она ограничена снизу (нулем) и решение задачи линейного программирования (а следовательно, и игры ) существует.

Пример 1. Найти методом линейного программирования решение игры «три пальца» из примера 2 § 4

Решение. Матрица игры имеет вид:

Прибавляя ко всем элементам матрицы одно и то же число сделаем их неотрицательными:

При этом цена игры увеличится на 5, а решение не изменится. Обозначим новую цену игры Найдем оптимальную смешанную стратегию игрока А. Условия (9.3) примут вид:

Минимизируемая линейная функция

Перейдем от условий-неравенств (9.11) к условиям-равенствам:

Заполним симплекс-таблицу (табл. 9.1). Так как свободные члены отрицательны, то, полагая мы не получим опорного решения.

Таблица 3.1

Таблица 9.2

Таблица 9.3

Таблица 9.4

Применяя аппарат симплекс-метода (см гл. 2, § 7), находим опорное решение (табл 9.2, 9.3, 9.4) Табл 9.4 дает опорное решение ОЗЛП:

Надо проверить, является ли оно оптимальным, т. е. обращает ли в минимум выражение (9.12) Пользуясь табл. 9.4, выразим L через новые свободные переменные

и запишем свободный член и коэффициенты при в верхней строке табл. 9.5.

Таблица 9.5

Из того, что коэффициент при положителен, видно, что увеличение уменьшает L, т. е. минимум еще не достигнут. Производим замену (табл. 9.5, 9.6).

Таблица 9.6

Из табл. 9.6 видно, что функция t принимает минимальное значение при

Отсюда т. е. цена игры с матрицей

Следовательно, цена исходной игры с матрицей (9.9):

Это значение выигрыша достигается при

т. е. для вероятностей стратегий

Таким образом, найдено решение игры — оптимальная стратегия игрока А

и цена игры

Оптимальная стратегия игрока В может быть найдена точно таким же способом, если составить условия, аналогичные (9.7), но не по столбцам, а по строкам, заменив в них знаки > на <, а величину L обращать не в минимум, а в максимум Однако в данном случае в этом надобности нет: из симметрии строк и столбцов матрицы ясно, что оптимальная стратегия игрока В должна быть такой же, как и оптимальная стратегия игрока А:

Таким образом, в игре «три пальца» оптимальная стратегия каждого из игроков состоит в том, чтобы с вероятностью 1/4 показывать один палец, с вероятностью 1/2 — два пальца и с вероятностью 1/4 — три пальца При этом средний выигрыш каждого игрока будет равен нулю

В этом примере все три стратегии каждого игрока были активными. Такая игра, в которой все стратегии активны, называется полностью усредненной. В следующем примере мы рассмотрим пример не полностью усредненной игры.

Пример 2. Игра «вооружение — помехи».

Сторона А располагает тремя видами вооружения а сторона В — тремя видами помех Вероятность решения боевой задачи стороной А при различных видах вооружения и помех задана матрицей:

Сторона А стремится решить боевую задачу, сторона В — воспрепятствовать этому Найти оптимальные стратегии сторон.

Решение. Избавляясь от дробей, перепишем матрицу в виде: и обозначим цену новой игры с такой матрицей Запишем условия (9.3):

откуда (переходя к условиям-равенствам)

Требуется найти неотрицательные значения удовлетворяющие условиям (9.13) и обращающие в минимум линейную функцию:

Решаем задачу симплекс-методом (опуская подробности, приведем сразу оптимальное решение, табл 9.7).

Таблица 9.7

Из табл 9.7 видно, что минимум L достигнут и равен Это значение достигается при

Отсюда находим вероятности с которыми игрок А должен применять свои стратегии

и цену игры:

В данном случае

Таким образом, оптимальная стратегия игрока Л найдена:

т. е., мы должны пользоваться с вероятностью 1/7 первым видом вооружения, с вероятностью 6/7 — вторым, а третий вид вооружения не применять вовсе. При этом вероятность выполнения боевой задачи будет максимальна:

Теперь найдем оптимальную стратегию противника. В общем случае для этого надо поступать так, как сказано выше: решать задачу для противника так как мы ее решали для себя, с заменой столбцов матрицы на строки, знаков > на < и минимума на максимум Однако в данном случае в этом надобности нет: нам помогает то обстоятельство, что нам уже известны активные стратегии игрока А, и их только две: Игра, таким образом, обратилась в игру 2X3, которую можно решить элементарно. Опуская подробности, приведем только решение:

т. е. оптимальная стратегия противника состоит в том, чтобы с вероятностью 3/7 пользоваться помехами с вероятностью 4/7 — помехами а третий вид помех не применять вовсе

В заключение заметим, что продемонстрированный в данном параграфе общий метод решения игр — сведение к задаче линейного программирования — не всегда оказывается самым простым. Часто игру — особенно с небольшими тип — удается решить проще, если заранее угадать, какие стратегии являются активными. Например, если матрица игры — квадратная то можно попробовать — не является ли игра полностью усредненной? В этом случае все стратегии обеих сторон являются активными, а неравенства (9.3) обращаются в равенства. Если, решив эту систему уравнений, мы получим положительные значения , то, складывая их, найдем величину

откуда цена игры:

а вероятности в оптимальной стратегии 5 найдутся как