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

Общая постановка задачи о нахождении решения игры m´n. Пусть дана игра m´n с m стратегиями А₁, А₂,..., А_m игрока А и n стратегиями В₁, В₂,..., В_n игрока В и задана платежная матрица .

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

где p₁ +... +p_m = 1, q₁ + ... + q_n = 1 (некоторые из чисел р_i и q_j могут быть равными нулю.

Наша оптимальная стратегия S_A^* должна обеспечивать нам выигрыш, не меньший n, при любом поведении противника, и выигрыш, равный n, при его оптимальном поведении (стратегия S_B^*). Аналогично стратегия S_B^* должна обеспечивать противнику проигрыш, не больший n, при любом нашем поведении, и равный v, при нашем оптимальном Поведении (стратегия S_A^*).

Величина цены игры n в данном случае нам неизвестна; будем считать, что она равна некоторому положительному числу. Полагая так, мы не нарушаем общности рассуждений; для того чтобы было v>0, достаточно, чтобы все элементы матрицы были неотрицательными. Этого всегда можно добиться, прибавляя к элементам достаточно большую положительную величину L; при этом цена игры увеличится на L, а решение не изменится.

Пусть мы выбрали свою оптимальную стратегию S_A^*. Тогда наш передний выигрыш при стратегии В_j противника будет равен:

a_j= p₁ a_1j + p₂ a_2j + …+ p_m a_mj.

Наша оптимальная стратегия S_A^* обладает тем свойством, что при любом поведении противника обеспечивает выигрыш, не меньший чем v; следовательно, любое из чисел а_j не может быть меньше v. Получаем ряд условий:

(5.2)

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

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

(5.3)

где x₁, x₂,…, x_m — неотрицательные числа. Так как р₁, р₂, + ... +р_m =1, то величины x₁, x₂,… x_m удовлетворяют условию:

(5.4)

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

Таким образом, задача нахождения решения игры сводится к следующей математической задаче: определить неотрицательные величины x₁, x₂,…, x_m, удовлетворяющие условиям (5.3) так, чтобы, их сумма

была минимальной.

Обычно при решении задач, связанных с нахождением экстремальных значений (максимумов и минимумов), функцию дифференцируют и приравнивают производные нулю. Но такой прием в данном случае бесполезен, так как функция Ф, которую нужно обратить в минимум, линейна, и ее производные по всем аргументам равны единице, т.е. нигде не обращаются в нуль. Следовательно, максимум функции достигается где-то на границе области изменения аргументов, которая определяется требованием неотрицательности аргументов и условиями (5.3). Прием нахождения экстремальных значений при помощи дифференцирования непригоден и в тех случаях, когда для решения игры определяется максимум нижней (или минимум верхней) границы выигрыша, как мы, например, делали при решении игр 2´n. Действительно, нижняя граница составлена из участков прямых линий, и максимум достигается не в точке, где производная равна нулю (такой точки вообще нет), а на границе интервала или в точке пересечения прямолинейных участков.

Для решения подобных задач применяется специальный аппарат линейного программирования.

Задача линейного программирования ставится следующим образом.

Дана система линейных уравнений:

(5.5)

Требуется найти неотрицательные значения величин x₁, x₂,…, x_m, удовлетворяющие условиям (5.5) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин x₁, x₂,…, x_m, (линейную форму):

Поставленная выше задача теории игр является частным случаем задачи линейного программирования при с₁= с₂=…= с_m=1.

Спервого взгляда может показаться, что условия (5.3) не эквивалентны условиям (5.5), так как вместо знаков равенства они содержат знаки неравенства. Однако от знаков неравенства легко избавиться, вводя новые фиктивные неотрицательные переменные z₁, z₂,…, z_n и записывая условия (5.3) в виде:

(5.5)

Линейная форма Ф, которую нужно обратить в минимум, равна:

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

Пример 1. Требуется найти решение игры 3´3, с матрицей:

Чтобы сделать все а_ij неотрицательными, прибавим ко всем элементам матрицы L = 5. Получим матрицу:

При этом цена игры увеличится на 5, а решение не изменится. Определим оптимальную стратегию S_A^*. Условия (5.3) имеют вид:

(5.7)

где

Чтобы избавиться от знаков неравенства, введем фиктивные переменные z₁, z₂,…, z_n; условия (5.7) запишутся в виде:

(5.8)

Линейная форма Ф имеет вид:

и должна быть сделана как можно меньше.

Если все три стратегии В являются "полезными", то все три фиктивные переменные x₁, x₂, x₃ обратятся в нуль (т.е. выигрыш, равный цене игры n, будет достигаться при каждой стратегии В_j). Но мы пока не имеем оснований утверждать, что все три стратегии являются "полезными". Чтобы проверить это, попытаемся выразить форму Ф через фиктивные переменные z₁, z₂, z₃ и посмотрим, добьемся ли мы, полагая их равными нулю, минимума формы Для этого разрешим уравнения (5.8) относительно переменных x₁, x₂, x₃ (т.е. выразим x₁, x₂, x₃ через фиктивные переменные z₁, z₂, z₃):

(5.9)

Складывая x₁, x₂, x₃, получим:

(5.10)

В выражении (5.10) коэффициенты при всех z положительны, значит, любое увеличение z₁, z₂, z₃ сверх нуля может привести только к увеличению формы Ф, а мы хотим, чтобы она была минимальна. Следовательно, значениями z₁, z₂, z₃ обращающими форму (5.10) в минимум, являются:

z₁=z₂=z₃=0.

Подставляя их в формулу (5.10), находим минимальное значение формы Ф:

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

n=5.

Подставляя нулевые значения z_1, z₂, z₃ в формулы (5.9), находим:

или, умножая их на n,

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

т.е. мы должны в одной четверти всех случаев писать цифру 1, в половине случаев 2 и в остальной четверти случаев 3.

Зная цену игры n = 5, можно уже известными способами найти оптимальную стратегию противника:

Для этого воспользуемся нашими любыми двумя "полезными" стратегиями (например, А₂ и А₃) и напишем уравнения:

откуда Оптимальная стратегия противника будет такой же, как наша:

Теперь вернемся к первоначальной (не преобразованной) игре.

Для этого нужно только от цены игры n = 5 отнять величину L = 5, прибавленную к элементам матрицы. Получим цену исходной игры: n₀ = 0. Следовательно, оптимальные стратегии обеих сторон обеспечивают средний выигрыш, равный нулю; игра в одинаковой мере выгодна или невыгодна для обеих сторон.