5. Соотношения превосходства

Как мы видели в разделе 3 главы I, иногда на основании простого рассмотрения матрицы прямоугольной игры можно сказать, что некоторые чистые стратегии могут войти в оптимальные смешанные стратегии лишь с нулевой вероятностью.

Так, например, если

    (34)

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

Цены обеих игр должны быть одинаковы; должен иметь в обеих играх одинаковые оптимальные стратегии. Если есть оптимальная стратегия для во второй игре, то оптимальная стратегия для в первой игре будет .

Поскольку каждый элемент первого столбца матрицы (35) меньше соответствующего элемента третьего столбца, и поскольку хочет свести платеж к минимуму, то мы можем вычеркнуть третий столбец матрицы (35) и получить матрицу

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

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

Заметим, что

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

Поскольку цена последней игры равна 6 и поскольку есть оптимальная стратегия для каждого игрока, мы заключаем, что игра, имеющая матрицу (37), также имеет цену, равную есть оптимальная стратегия для и есть оптимальная стратегия для .

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

решая игру с матрицей

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

Если и есть векторы (или строки, или столбцы матрицы) и если , то мы говорим, что а превосходит b; если , мы говорим, что а строго превосходит b. Оба эти соотношения транзитивны: если а превосходит b и b превосходит с, то а превосходит с, и такое же соотношение имеет место для строгого превосходства. Мы замечаем также, что соотношение превосходства рефлексивно, так что всякая величина превосходит сама себя, а соотношение строгого превосходства нерефлексивно, так что никакая величина строго не превосходит сама себя. Однако, применяя эти понятия, всегда нужно иметь в виду, что когда два вектора различны, из этого не следует, что один из них обязательно превосходит другой: например, это видно на векторах и .

Введем также понятие расширения смешанной стратегии на месте. Если есть элемент множества то расширением элемента на месте называется вектор . Так, расширением элемента на 2-м месте является вектор ; расширением на 1-м месте является вектор ; расширением на 4-м месте — вектор . Очевидно, если есть какой-либо элемент множества , то всякое расширение элемента на i-м месте является элементом множества .

Теорема 2.16. Пусть Г — прямоугольная игра с матрицей А. Предположим, что i-ю строку матрицы А для некоторого i превосходит некоторая выпуклая линейная комбинация других строк матрицы А;

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

Доказательство. Пусть

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

Пусть v — цена игры , — оптимальная стратегия игрока — оптимальная стратегия игрока в . Тогда по теореме 2.9

Для доказательства первой части теоремы теперь достаточно показать, что v есть также цена игры , y — оптимальная стратегия игрока и — оптимальная стратегия игрока в .

Из теоремы 2.9 следует, что для этого нужно доказать справедливость следующих неравенств:

Поскольку неравенство есть очевидное следствие неравенства (40), то достаточно доказать неравенство (39а). Следовательно, пользуясь неравенством (39), достаточно показать, что

Но из неравенств (38) и (39) мы получаем непосредственно

что доказывает первую часть теоремы.

Для доказательства второй части теоремы достаточно отметить, что если ни в одном из соотношений (38) нет равенства, то

Следовательно, из теоремы 2.12 вытекает, что у всякой оптимальной стратегии игрока в m-я компонента будет равна нулю.

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

Теорема 2.17. Пусть Г — прямоугольная игра с матрицей А. Предположим, что столбец матрицы А для некоторого превосходит некоторую выпуклую линейную комбинацию других столбцов матрицы А;

пусть — матрица, получающаяся из А после исключения столбца, и пусть — прямоугольная игра с матрицей Тогда цена игры Г такая же, как цена игры Г; всякая оптимальная стратегия игрока в есть также оптимальная стратегия игрока в ; если z — любая оптимальная стратегия игрока в и у — расширение стратегии z на месте, то у есть оптимальная стратегия игрока. в Г. Далее, если столбец матрицы А строго превосходит выпуклую линейную комбинацию других столбцов матрицы, то любое решение игры можно получить этим способом из решения игры Г.

Приведем несколько более сложный пример применения этих теорем.

Пример 2.18. Дана следующая платежная матрица прямоугольной игры:

Так как третья строка матрицы превосходит первую, то, вычеркивая первую строку, мы получаем:

В новой матрице первый столбец превосходит третий; вычеркивая первый столбец, мы получаем:

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

Поэтому мы исключаем первый столбец и получаем:

В свою очередь в этой матрице выпуклая линейная комбинация второй и третьей строк превосходит первую строку, так как

Таким образом, наша матрица приведена к матрице

Цена игры с этой матрицей равна у, а оптимальная стратегия для первого игрока (и для второго игрока) будет равна . Следовательно, поскольку мы получили матрицу 2x2 из первоначальной матрицы 4x4 путем вычеркивания первых двух строк и первых двух столбцов, мы заключаем, что оптимальная стратегия для первого игрока (и для второго игрока) в первоначальной игре будет .

Замечание 2.19. Из теорем 2.16 и 2.17 можно заметить, что когда мы вычеркиваем строку (или столбец), которая строго превосходит что-либо, мы получаем матрицу, которая приводит к точно такой же системе решений, которая получилась бы при решении первоначальной игры.

Однако это не имеет места, когда соотношение превосходства не является строгим; в этом случае мы можем «потерять» некоторые из решений первоначальной матрицы,

В качестве примера рассмотрим игру с платежной матрицей

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

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