Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 5. Соотношения превосходстваКак мы видели в разделе 3 главы I, иногда на основании простого рассмотрения матрицы прямоугольной игры можно сказать, что некоторые чистые стратегии могут войти в оптимальные смешанные стратегии лишь с нулевой вероятностью. Так, например, если
—матрица прямоугольной игры, то, как подсказывают интуитивные соображения, ни при какой оптимальной стратегии игрока
Цены обеих игр должны быть одинаковы; Поскольку каждый элемент первого столбца матрицы (35) меньше соответствующего элемента третьего столбца, и поскольку
Таким образом, мы можем найти решение первоначальной игры, решая игру с матрицей (36). Цена игры,имеющей матрицу (36), равна 4, и поскольку Эти рассуждения можно несколько обобщить на тот случай, когда элементы одной строки не все меньше соответствующих элементов другой строки, но все меньше некоторых выпуклых линейных комбинаций соответствующих элементов других строк. Так, например, рассмотрим игру с платежной матрицей
Заметим, что
и, следовательно, для
Поскольку цена последней игры равна 6 и поскольку Аналогично, если каждый элемент некоторого столбца больше некоторой выпуклой линейной комбинации соответствующих элементов некоторых других столбцов, то этот столбец можно исключить. Так, мы можем решить игру с матрицей
решая игру с матрицей
Для того чтобы строго обосновать этот метод, удобно ввести некоторые определения. Если Введем также понятие расширения смешанной стратегии на Теорема 2.16. Пусть Г — прямоугольная игра с матрицей А. Предположим, что i-ю строку матрицы А для некоторого i превосходит некоторая выпуклая линейная комбинация других строк матрицы А; пусть Доказательство. Пусть
Можно предположить, не нарушая общности, что последнюю строку матрицы А превосходит выпуклая линейная комбинация других строк. Поэтому существует элемент
Пусть v — цена игры
Для доказательства первой части теоремы теперь достаточно показать, что v есть также цена игры Из теоремы 2.9 следует, что для этого нужно доказать справедливость следующих неравенств:
Поскольку неравенство
Но из неравенств (38) и (39) мы получаем непосредственно
что доказывает первую часть теоремы. Для доказательства второй части теоремы достаточно отметить, что если ни в одном из соотношений (38) нет равенства, то
Следовательно, из теоремы 2.12 вытекает, что у всякой оптимальной стратегии игрока Доказательство следующей теоремы аналогично, и мы его опустим. Теорема 2.17. Пусть Г — прямоугольная игра с матрицей А. Предположим, что пусть Приведем несколько более сложный пример применения этих теорем. Пример 2.18. Дана следующая платежная матрица прямоугольной игры:
Так как третья строка матрицы превосходит первую, то, вычеркивая первую строку, мы получаем:
В новой матрице первый столбец превосходит третий; вычеркивая первый столбец, мы получаем:
В этой матрице никакая строка (и никакой столбец) не превосходит другие строки (и столбцы); но первый столбец превосходит выпуклую линейную комбинацию второго и третьего столбцов, потому что
Поэтому мы исключаем первый столбец и получаем:
В свою очередь в этой матрице выпуклая линейная комбинация второй и третьей строк превосходит первую строку, так как
Таким образом, наша матрица приведена к матрице
Цена игры с этой матрицей равна у, а оптимальная стратегия для первого игрока (и для второго игрока) будет равна Замечание 2.19. Из теорем 2.16 и 2.17 можно заметить, что когда мы вычеркиваем строку (или столбец), которая строго превосходит что-либо, мы получаем матрицу, которая приводит к точно такой же системе решений, которая получилась бы при решении первоначальной игры. Однако это не имеет места, когда соотношение превосходства не является строгим; в этом случае мы можем «потерять» некоторые из решений первоначальной матрицы, В качестве примера рассмотрим игру с платежной матрицей
Легко убедиться, что любой элемент множества
для которой
|
1 |
Оглавление
|