6. Графический метод решения

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

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

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

Рис. 2.

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

а если применяет чистую стратегию то ожидаемый платеж игроку равен

Проведем на интервале [0, 1] три прямые,

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

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

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

Перейдем теперь к примеру, когда имеет много оптимальных стратегий.

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

Обозначив стратегии, как в примере 2.20, и проведя соответствующие прямые, как в предыдущем примере, мы получим рис. 3.

Рис 3.

Из рис. 3 видно, что цена игры равна 4 и что любое удовлетворяющее условию будет оптимальным для Решая совместно уравнения и и находим соответственно, что , а . Итак, оптимальной стратегией для является любая пара , где . Оптимальная стратегия для в этой игре равна .

Замечание 2.23. В примере 2.22 мы нашли, что множество оптимальных смешанных стратегий игрока состоит из точек прямолинейного отрезка; очевидно, это всегда будет иметь место для игры (хотя, конечно, отрезок может стянуться в одну точку, как в примере 2.20).

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

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

Первое доказательство основной теоремы (теоремы 2.6) было дано фон Нейманом [88], это доказательство было основано на топологической теореме Брауэра о неподвижной точке; позднее Билль [109] дал элементарное доказательство. В книге фон Неймана и Моргенштерна [92] было дано простое доказательство, основанное на теории выпуклых множеств; доказательство, приведенное выше, по существу есть доказательство, фон Неймана и Моргенштерна. Другие доказательства этой теоремы или ее обобщения мокно найти у Боненблуста и Карлина [9], у Брауна и фон Неймана [19] и у Вейля [122].

Для дальнейших сведений по теории выпуклых множеств рекомендуется обратиться к работам Глезермана и Понтрягина [46] или Боннезена и Фенхеля [12].