Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 3. Определение всех решенийЛемма. 3.5. Пусть Г — прямоугольная игра, платежная матрица которой есть А, пусть
где r есть порядок матрицы В, X — вектор, полученный из X путем вычеркивания элементов, соответствующих вычеркнутым строкам при образовании матрицы В из матрицы A, a Y есть вектор, полученный из Y путем вычеркивания элементов, соответствующих вычеркнутым столбцам при образовании матрицы В из матрицы А. Доказательство. Положим
Чтобы убедиться в достаточности нашего условия, предположим, что имеется невырожденная матрица В, удовлетворяющая условиям (14), (15) и (16), и что при этом условия Поскольку задача определения решений игры не меняется существенно при перестановке строк или столбцов, мы можем, не нарушая общности, положить, что В находится в левом верхнем углу матрицы А, то есть что
Таким образом, если
Поэтому
и
Поскольку мы предположили, что
то есть такие, что
Из выражений (17), (18) и (19)
Следовательно, будем иметь:
Но поскольку
и, следовательно, на основании равенства (21)
совершенно аналогично можно получить
Из равенств (14) и (15) имеем:
и, следовательно,
так что, используя (19), получаем:
или
Из выражений (22), (23) и (24) имеем:
и, следовательно,
откуда вытекает, что
и, следовательно, что
Поскольку предполагалось, что U и W различные векторы, то
Тогда из выражений (26) и (27) следует, что В есть вырожденная матрица, что противоречит условию. Остается показать, что условие необходимо. Допустим, что Не нарушая общности, мы можем предположить, что строки матрицы А расположены таким образом, что
и
и кроме того, предположим, что столбцы матрицы А расположены таким образом, что
и
На основании теоремы 2.9 мы заключаем, что
и
Далее, не нарушая общности, мы можем также предположить, что строки и столбцы матрицы А расположены таким образом, что для некоторого
Пусть Положим
Предположив, что
мы будем различать два случая: Случай 1. Существует целое число
Случай 2. Такого целого числа В первом случае, обозначая через
Во втором случае считаем
Не нарушая общности, мы можем предположить, что столбцы матрицы А расположены в таком порядке, что для некоторого
Тогда легко видеть, что для Аналогично, если положить
где i — любой элемент множества Положим теперь
Допустим, что матрица В вырождена, так что либо строки, либо столбцы ее линейно зависимы. Разберем случай линейной зависимости строк (в случае линейной зависимости столбцов доказательство аналогично). Для
Поскольку строки матрицы В зависимы, то существуют такие постоянные
Кроме того, для
На основании равенства (36) имеем:
и, следовательно, из (31), учитывая, что получаем:
Итак, полагая
Используя (40) и (38), мы видим, что
а поскольку, по условию,
Положим теперь
Из условия (39) и из определения
Для любого действительного числа а определим вектор
Так как не все компоненты вектора С равны нулю, очевидно, что Из равенства (41) вытекает, что если
Далее, из условия (43) видно, что, выбрав а достаточно малым, мы можем получить
Обозначив через
Если
Отсюда, используя равенство (47), получаем:
Таким образом, из равенств (47) и (48) следует
и поэтому для
справедливое при всех а. Для всех
Введем обозначение
Но так как
то Для завершения доказательства остается проверить выполнение для В равенств (14), (15) и (16). Поскольку матрица В невырожденная,
Пусть
и, следовательно, поскольку
Из (51) следует, что
а отсюда в силу невырожденности В
Аналогично, с помощью равенства (36) мы заключаем, что
откуда
Следовательно,
Из равенства (52) мы получаем:
откуда
Это и есть равенство (14) нашей леммы. Равенства (15) и (16) вытекают непосредственно из равенств (52), (53) и (54). Доказательство закончено. Теорема 3.6. Пусть Г — прямоугольная игра с матрицей А. Предположим, что
и
где X есть вектор, полученный из X путем вычеркивания элементов, соответствующих вычеркнутым строкам при образовании В из A, a Y есть вектор, полученный из Y путем вычеркивания элементов, соответствующих вычеркнутым столбцам при образовании В из А. Доказательство. Для
Для
полагаем
то есть
Теперь легко проверйть с помощью теоремы 2.6, что
и далее, что
и
так что, очевидно,
и
Поскольку, согласно (59),
где X и Y суть векторы, полученные путем вычеркивания элементов, соответствующих вычеркнутым строкам и столбцам при образовании Из равенств (62) и (63) мы видим, что существование матрицы, удовлетворяющей условиям (64), есть также необходимое и достаточное условие того, что
Предположим, что В — матрица, полученная из
Это завершает доказательство теоремы. Теорема 3.7. Если Г — некоторая прямоугольная игра, то множества Доказательство. На основании теоремы 3.6 любой элемент множества Замечание 3.8. Теорема 3.6 дает нам следующий удобный метод нахождения всех решений прямоугольной игры: Пусть дана прямоугольная игра с платежной матрицей А, мы рассматриваем поочередно каждую квадратную подматрицу В матрицы А. Для подматрицы В порядка Если нет, мы отбрасываем эту подматрицу В и переходим к другой квадратной подматрице. Если X и Y оба принадлежат множеству В связи с этим отметим, что нам не следует рассматривать подматрицы первого порядка, так как они определяют решения по формулам теоремы 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 лишь одна дает дополнительное решение, а именно
для которой
отсюда
Итак,
в то время как
где Замечание 3.12. Следует отметить, что метод решения прямоугольных игр, изложенный в этой главе, хотя и весьма прозрачен (и, конечно, более эффективен, чем трудоемкий метод, указанный в главе II), все же приводит к громоздким вычислениям для игр с большими платежными матрицами, ибо число квадратных подматриц, имеющихся у матриц высокого порядка, само очень велико, и поэтому чрезвычайно утомительно вычислять присоединенную матрицу квадратной матрицы высокого порядка. Число арифметических операций, необходимых при этом способе, так быстро возрастает с повышением порядка матрицы, что представляется мало вероятным применение даже современных электронных вычислительных машин для решения игр порядка, скажем, 100 x 100 Замечание 3.13. Из выводов этой главы следует, что для многих прямоугольных игр имеется бесконечно много оптимальных стратегий как для одного, так и для двух игроков. Естественно, возникает вопрос, возможно ли сделать выбор, между различными оптимальными стратегиями. Это можно сделать различными способами, один из которых будет сейчас описан. Предположим, что когда первый игрок выбирает смешанную стратегию X, а второй — чистую стратегию j математическое ожидание выигрыша первого игрока равно
Мы говорим, что сметанная стратегия X превосходит смешанную стратегию X, если для каждой чистой стратегии j игрока
и существует по меньшей мере одна стратегия j игрока
Мы называем стратегию X наилучшей, если она оптимальна и никакая другая стратегия не превосходит ее. Аналогично определяются соотношения превосходства и наилучшие стратегии для Интуитивное обоснование этих определений заключается в том, что если X превосходит Доказательство этого мы оставляем в качестве упражнения. Пример 3.14. Рассмотрим игру с платежной матрицей
Поскольку каждый из элементов первого столбца является седловой точкой, то любая смешанная стратегия первого игрока оптимальна. Если
В частности,
Поскольку для всех
мы заключаем, что Для Библиографические замечания Материал этой главы был взят в основном из работы Шепли и Сноу [101]. С задачей, которой мы здесь занимаемся, тесно связана такая задача: найти условия, которым должны удовлетворять два множества X и Y для того, чтобы для некоторой прямоугольной игры имели место равенства Эта задача решена в работе Боненблуста, Карлина и Шепли [10] и в работе Гейла и Шермана [42]. Полную теорию можно найти в книгах Бохера [8] и Мак-Даффи [68].
|
1 |
Оглавление
|