3. Определение всех решений

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

где r есть порядок матрицы В, X — вектор, полученный из X путем вычеркивания элементов, соответствующих вычеркнутым строкам при образовании матрицы В из матрицы A, a Y есть вектор, полученный из Y путем вычеркивания элементов, соответствующих вычеркнутым столбцам при образовании матрицы В из матрицы А.

Доказательство. Положим

Чтобы убедиться в достаточности нашего условия, предположим, что имеется невырожденная матрица В, удовлетворяющая условиям (14), (15) и (16), и что при этом условия и не выполняются одновременно, так что либо либо . Покажем, что предположение, будто приводит к противоречию; доказательство противоречивости предположения аналогично.

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

Таким образом, если , то . Но поскольку , то (для и, следовательно, тем более для ) Далее, из равенства (15) мы заключаем, что

Поэтому

и

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

то есть такие, что

Из выражений (17), (18) и (19)

Следовательно, будем иметь:

(21)

Но поскольку , то

и, следовательно, на основании равенства (21)

совершенно аналогично можно получить

    (23)

Из равенств (14) и (15) имеем:

и, следовательно,

так что, используя (19), получаем:

или

    (24)

Из выражений (22), (23) и (24) имеем:

и, следовательно,

откуда вытекает, что

и, следовательно, что

Поскольку предполагалось, что U и W различные векторы, то

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

Остается показать, что условие необходимо. Допустим, что и и построим невырожденную матрицу В, удовлетворяющую условиям (14), (15) и (16).

Не нарушая общности, мы можем предположить, что строки матрицы А расположены таким образом, что

и

и кроме того, предположим, что столбцы матрицы А расположены таким образом, что

и

На основании теоремы 2.9 мы заключаем, что

и

Далее, не нарушая общности, мы можем также предположить, что строки и столбцы матрицы А расположены таким образом, что для некоторого и некоторого

    (34)

Пусть есть вектор , где — любое целое число из множества . Определим рекуррентно некоторые множества целых чисел .

Положим

Предположив, что определено и равно

мы будем различать два случая:

Случай 1. Существует целое число в множестве такое, что вектор линейно независим от векторов то есть такой, что несуществует постоянных чисел , одновременно отличных от нуля и удовлетворяющих условию

Случай 2. Такого целого числа не существует.

В первом случае, обозначая через наименьшее целое число в множестве такое, что линейно независимо от , положим

Во втором случае считаем . Положим теперь

Не нарушая общности, мы можем предположить, что столбцы матрицы А расположены в таком порядке, что для некоторого

Тогда легко видеть, что для вектор D, линейно не зависит от векторов , кроме того, если то линейно зависит от .

Аналогично, если положить

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

Положим теперь

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

Для введем обозначение

Поскольку строки матрицы В зависимы, то существуют такие постоянные не все равные нулю, что

Кроме того, для мы должны иметь так как в противном случае мы могли бы разделить равенство (38) на и прийти к выводу, что линейно зависит от и, следовательно (так как — часть вектора ), линейно зависит от что противоречит построению. Поэтому из условий (28) и (29) заключаем, что

На основании равенства (36) имеем:

и, следовательно, из (31), учитывая, что получаем:

Итак, полагая имеем:

Используя (40) и (38), мы видим, что

а поскольку, по условию, , то

Положим теперь для и

Из условия (39) и из определения для имеем:

Для любого действительного числа а определим вектор

Так как не все компоненты вектора С равны нулю, очевидно, что тогда и только тогда, когда в общем случае тогда и только тогда, когда .

Из равенства (41) вытекает, что если , то

Далее, из условия (43) видно, что, выбрав а достаточно малым, мы можем получить для , следовательно, существует такое что

Обозначив через столбец матрицы А, мы видим на основании (43) и (38), что для ,

    (47)

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

Отсюда, используя равенство (47), получаем:

Таким образом, из равенств (47) и (48) следует

и поэтому для , получаем равенство

справедливое при всех а.

Для всех имеем Следовательно, мы можем найти такое что

Введем обозначение . Тогда из (46), (49) и (50) получим, что для выполняется , поэтому . В частности положив , мы получим:

Но так как

то , что противоречит условию. Отсюда заключаем, что матрица В невырожденная, что и требовалось доказать.

Для завершения доказательства остается проверить выполнение для В равенств (14), (15) и (16). Поскольку матрица В невырожденная, положим , тогда

Пусть . Вектор получается из путем вычеркивания элементов, соответствующих вычеркнутым строкам при образовании В из вектор Y получается аналогичным образом. Если верно равенство (34), то тем более справедливо, что

и, следовательно, поскольку , то

    (51)

Из (51) следует, что

а отсюда в силу невырожденности В

Аналогично, с помощью равенства (36) мы заключаем, что

откуда

Следовательно,

Из равенства (52) мы получаем:

откуда

Это и есть равенство (14) нашей леммы. Равенства (15) и (16) вытекают непосредственно из равенств (52), (53) и (54). Доказательство закончено.

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

и

где X есть вектор, полученный из X путем вычеркивания элементов, соответствующих вычеркнутым строкам при образовании В из A, a Y есть вектор, полученный из Y путем вычеркивания элементов, соответствующих вычеркнутым столбцам при образовании В из А.

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

Для мы определяем новую игру с матрицей прибавляя к каждому элементу матрицы А число . Например, при

полагаем

то есть

Теперь легко проверйть с помощью теоремы 2.6, что

и далее, что

и

так что, очевидно,

и

Поскольку, согласно (59), теорема справедлива для (см. выше). Из равенств (60) и (61) получаем . Поэтому, для того чтобы и , необходимо и достаточно, чтобы существовала квадратная подматрица В матрицы порядка , такая, что

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

Из равенств (62) и (63) мы видим, что существование матрицы, удовлетворяющей условиям (64), есть также необходимое и достаточное условие того, что

Предположим, что В — матрица, полученная из путем вычитания b из каждого элемента матрицы В очевидно, В есть квадратная подматрица матрицы А, которая может быть получена из А путем вычеркивания тех же строк я столбцов, которые вычеркиваются из при образовании . Тогда из формулы (59) и леммы 3.4 видно, что условия (64) равносильны следующим:

Это завершает доказательство теоремы.

Теорема 3.7. Если Г — некоторая прямоугольная игра, то множества и конечны, а и являются соответственно их выпуклыми оболочками; следовательно, и — многогранники с вершинами в точках, принадлежащих соответственно и .

Доказательство. На основании теоремы 3.6 любой элемент множества можно получить из квадратной подматрицы матрицы А игры Г, а данная квадратная подматрица не может образовать более одного элемента множества . Поскольку матрица А имеет лишь конечное число подматриц, то отсюда следует, что есть конечное множество. Доказательство конечности аналогично. Остальные предложения теоремы следуют из леммы 3.2.

Замечание 3.8. Теорема 3.6 дает нам следующий удобный метод нахождения всех решений прямоугольной игры:

Пусть дана прямоугольная игра с платежной матрицей А, мы рассматриваем поочередно каждую квадратную подматрицу В матрицы А. Для подматрицы В порядка из формул теоремы 3.6 мы определяем v, X и Y и решаем прежде всего, принадлежат ли множеству .

Если нет, мы отбрасываем эту подматрицу В и переходим к другой квадратной подматрице. Если X и Y оба принадлежат множеству то мы образуем векторы X и Y, прибавляя к X и У нулевые компоненты, соответствующие строкам и столбцам, вычеркнутым из А для образования В, и определяем с помощью теоремы 2.9, действительно ли . Если нет, мы также отбрасываем В и переходим к другой квадратной подматрице матрицы А. Если да, то есть решение, и, кроме того, на основании теоремы 3.6 . Так мы можем определить все элементы множеств и, следовательно, найти все элементы множеств образовав выпуклые линейные комбинации элементов множеств соответственно и

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

Поясним этот метод на нескольких примерах.

Пример 3.9. Рассмотрим игру Г с платежной матрицей

Поскольку матрица не имеет седловой точки, мы рассмотрим три подматрицы 2-го порядка:

Легко проверить, что

и

следовательно,

Таким образом,

и

Подставляя эти значения в формулы теоремы 3.6, мы находим теперь, что

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

Обращаясь к матрице С, мы находим по формулам теоремы 3.6:

где . Так как при образовании С из А строки не вычеркивались, то

а поскольку при образовании С из А был вычеркнут второй столбец, то

Далее, проверяя величины v, X и Y согласно теореме 2.9, мы находим, что

Итак, найденные X и Y действительно представляют решение.

Возвращаясь к D, мы находим из теоремы 3.6, что

и, следовательно,

Но при проверке величин X, Y и у согласно теореме 2.9 мы находим, что

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

Итак, игра имеет единственное решение:

Этот результат можно легко проверить графическим способом, изложенным в главе II.

Пример 3.10. Рассмотрим игру Г с платежной матрицей

Мы полагаем

Применяя формулы теоремы 3.6 к В, мы, находим, что

и, следовательно,

Из теоремы 2.6 мы видим, что эти величины действительно представляют решение первоначальной матрицы. Аналогично, используя матрицу С, мы получаем:

и, применяя теорему 2.6, опять убеждаемся в том, что это есть решение.

Наконец, используя матрицу D, получаем, что

то есть то же решение, что и найденное с помощью матрицы В.

Итак, в этой игре содержит лишь один элемент, а именно следовательно, содержит лишь один элемент. Но множество содержит два элемента, а именно и . Поэтому общий элемент множества можно написать в виде

или просто

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

Пример 3.11. Рассмотрим игру с платежной матрицей

Для этой матрицы

откуда получаем решение

Из девяти подматриц порядка 2x2 лишь одна дает дополнительное решение, а именно

для которой

отсюда

Итак, имеет единственную оптимальную стратегию

в то время как имеет множество оптимальных стратегий

где — произвольный элемент множества . Цена игры равна 1.

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

Число арифметических операций, необходимых при этом способе, так быстро возрастает с повышением порядка матрицы, что представляется мало вероятным применение даже современных электронных вычислительных машин для решения игр порядка, скажем, 100 x 100

Замечание 3.13. Из выводов этой главы следует, что для многих прямоугольных игр имеется бесконечно много оптимальных стратегий как для одного, так и для двух игроков. Естественно, возникает вопрос, возможно ли сделать выбор, между различными оптимальными стратегиями. Это можно сделать различными способами, один из которых будет сейчас описан.

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

Мы говорим, что сметанная стратегия X превосходит смешанную стратегию X, если для каждой чистой стратегии j игрока

и существует по меньшей мере одна стратегия j игрока такая, что

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

Интуитивное обоснование этих определений заключается в том, что если X превосходит , то, независимо от того, как решает поступить игрок заведомо поступит не хуже при использовании X, чем при использовании . Далее, если делает какие-то ошибки, для лучше применять X, чем . Итак, стратегия X позволяет лучше, чем , использовать возможные ошибки противника. Поэтому игрок может вполне выбрать стратегию из класса «наилучших». Легко показать, что во всякой прямоугольной игре существуют наилучшие стратегии.

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

Пример 3.14. Рассмотрим игру с платежной матрицей

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

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

В частности,

Поскольку для всех из

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

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

Библиографические замечания

Материал этой главы был взят в основном из работы Шепли и Сноу [101]. С задачей, которой мы здесь занимаемся, тесно связана такая задача: найти условия, которым должны удовлетворять два множества X и Y для того, чтобы для некоторой прямоугольной игры имели место равенства .

Эта задача решена в работе Боненблуста, Карлина и Шепли [10] и в работе Гейла и Шермана [42].

Полную теорию можно найти в книгах Бохера [8] и Мак-Даффи [68].