4. Свойства оптимальных стратегий

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

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

Аналогично, для того чтобы элемент Y множества был оптимальной стратегией для , необходимо и достаточно, чтобы для всякого элемента X множества имело место неравенство

Доказательство. Если X — оптимальная стратегия для то имеется элемент У множества такой, что есть седловая точка функции , и, следовательно, такой, что для всякого ,

что и требовалось доказать.

С другой стороны, предположим, что X — элемент множества такой, что для всякого

На основании теоремы 2.7 существует точка , такая, что для всех и всех

а поскольку по условию v есть цена игры, мы имеем

Из (26) и (28) мы заключаем, что

Заменяя У на У в неравенстве (29), и заменяя X на X* в первой части неравенства (27), получаем

Итак,

Из (27), (29) и (30) мы заключаем, что

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

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

вместо

где — элемент множества компонента которого равна 1, а все другие — нулю; аналогично мы будем писать

вместо

где — элемент множества компонента которого равна 1, а остальные — нулю. Если то

и

Заметим также, что

Теорема 2.9. Пусть Е — математическое ожидание выигрыша прямоугольной игры с матрицей порядка , пусть v — действительное число, и пусть — соответственно элементы множеств . Тогда, для игого чтобы v было ценой игры, а - оптимальными стратегиями соответственно для , необходимо и достаточно, чтобы для

Доказательство. Необходимость условия следует непосредственно из определения седловой точки — при замене X на i и Y на j.

С другой стороны, если условие выполняется, то для любого , являющегося элементом множества

Аналогично, для любого , являющегося элементом множества

Из неравенств (31) и (32), заменяя X на и Y на , мы получаем соответственно

и

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

Тогда из неравенств (31), (32) и (33) мы получаем

так что есть действительно седловая точка функции а v — цена игры.

Следующая теорема является следствием теоремы 2.8; доказательство ее мы оставляем читателю в качестве упражнения.

Теорема 2.10. Пусть Е — математическое ожидание выигрыша прямоугольной игры с матрицей порядка , цена которой есть v. Тогда, для того чтобы элемент X множества был оптимальной стратегией для необходимо и достаточно, чтобы для выполнялось

Аналогично, для того чтобы элемент Y множества был оптимальной стратегией для необходимо и достаточно, чтобы для выполнялось

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

Доказательство. На основании теоремы 2.10 для

где v — цена игры, следовательно,

Но если

то

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

или

Но это противоречит условию, что v есть цена игры. Отсюда мы заключаем, что

Аналогично доказывается, что

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

Теорема 2.12. Пусть Е — математическое ожидание выигрыша для прямоугольной игры с матрицей порядка имеющей цену v, и пусть - оптимальные стратегии соответственно для . Тогда для любого i, при котором

имеет место равенство

а для любого j такого, что

имеет место равенство

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

и

Тогда мы заключаем, что

Поскольку, для

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

мы заключаем, что

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

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

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

Теорема 2.13. Пусть Е — математическое ожидание выигрыша прямоугольной игры с матрицей порядка и пусть и — соответственно элементы множеств и Тогда имеют место следующие эквивалентные утверждения:

1) есть оптимальная стратегия для а есть оптимальная стратегия для .

2) Если X есть любой элемент множества а Y — любой элемент множества , то

3) Если i и j суть любые целые числа, такие, что и то

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

Пример 2.14. Требуется найти цену и оптимальные стратегии обоих игроков для прямоугольной игры, имеющей следующую матрицу:

На основании теоремы 2.9 достаточно найти числа удовлетворяющие следующим условиям:

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

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

Применяя любой из известных методов элементарной алгебры, мы находим, что эта система уравнений имеет следующее решение:

Поскольку , найденные таким образом, оказываются неотрицательными, мы нашли решение нашей первоначальной системы уравнений и неравенств. Итак, оптимальный способ для выбирать числа 1, 2, 3 с соответствующими вероятностями и ; а оптимальный способ игры для — выбирать числа 1, 2, 3 с соответствующими вероятностями и . Цена игры равна — Это значит, что игрок может играть таким образом, чтобы гарантировать себе, что проиграет не больше может играть таким образом, чтобы наверняка проиграл по меньшей мере

Следующий пример показывает, как можно обойти затруднения, возникающие в том случае, когда уравнения, соответствующие шести уравнениям предыдущего примера, оказываются несовместными или не имеют решений, лежащих в интервале [0, 1].

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

На основании теоремы 2.9 достаточно найти числа , и , удовлетворяющие следующим условиям:

Рассмотрим сначала случай, когда все шесть неравенств вменены равенствами:

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

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

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

Из строгого неравенства вытекает, на основании теоремы 2.12, что , а из строгого неравенства вытекает, что .

Итак, нам нужно решить следующую систему уравнений;

Эта система имеет решение

Мы подставляем значения

в первоначальную систему неравенств и находим, что она удовлетворяется.

Таким образом, цена игры равна 2, вектор — оптимальная стратегия для первого игрока, а вектор 2 3 — оптимальная стратегия для второго игрока.