2. Пояснительный пример
Доказанные нами теоремы достаточны для того, чтобы дать общий метод подхода к задаче отыскания решений для разделимых игр: а) мы чертим кривые U и W (соответственно в m-мерном и
-мерном пространствах) и определяем их выпуклые оболочки, каковыми по теореме
11.4 являются соответственно U и W; б) мы находим
для любой точки и
и
для любой точки
(это равнозначно отысканию точек в некоторых замкнутых выпуклых множествах, где данные линейные формы принимают свои минимальные и максимальные значения); в) используя результаты пункта б), мы находим фиксированные точки пространств U и W; г) мы представляем фиксированные точки как выпуклые линейные комбинации точек множеств U и W соответственно и с помощью теоремы 11.1 находим функции распределения, которым соответствуют фиксированные точки. Эти функции распределения будут оптимальными стратегиями. Поясним этот метод на примере.
Пример 11.8. Платежная функция М разделимой игры определяется следующим равенством (для любой точки
замкнутого единичного квадрата):
Здесь мы примем:
так что М представлена следующим образом:
Очевидно, пространство U лежит в плоскости
а пространство
— в плоскости
. Начертим для простоты двумерное изображение этих пространств.
Кривая U выражается следующими параметрическими уравнениями:
Пространство
есть выпуклая оболочка кривой
, представляющая часть плоскости
ограниченную прямолинейными отрезками АВ, АС и BD и дугой косинусоиды CQD, как изображено на рис. 42 (на том же рисунке показано пространство W, которое тождественно пространству U).
Рис. 42.
Найдем координаты точки Скоторые понадобятся нам впоследствии. Обозначим точку С через
. Наклон m прямой АС такой же, как наклон кривой
в точке
. Следовательно,
отсюда мы получаем:
где
— угол во втором квадранте. Решая это уравнение, мы находим с точностью до двух десятичных знаков:
Таким образом, координаты точки С суть
. Если
— любая стратегия игрока
и G — любая стратегия
то математическое ожидание
равно
Вспомним, что точка
принадлежит пространству U тогда и только тогда, когда для некоторой функции F
и точка
принадлежит пространству W тогда и только тогда, когда для некоторой функции G
Мы видим, что если
выбирает точку
из U, а выбирает точку
из W, то математическое ожидание
для
определяется формулой
Наша задача состоит в том, чтобы найти две точки и и w, принадлежащие соответственно пространствам U и W и обладающие тем свойством, что
то есть такие, что
Множество
для всякой точки
есть подмножество правой границы BDQ пространства U. В самом деле, допустим, что
содержит точку
не находящуюся на BDQ. Пусть
— горизонтальная проекция точки а на BDQ, где d есть расстояние (положительное) от а до а'. Тогда из (20) мы видим, что
а это показывает, что
не имеет места при
то есть а не принадлежит к
. Аналогично, для всякой точки
образ множества
есть подмножество левой границы ACQ пространства
.
Теперь мы найдем
для произвольной точки
дуги QD косинусоиды, образующей часть границы пространства U. Точка b пространства W принадлежит к
тогда и только тогда, когда
В силу (20) это означает, что нам нужно найти точку
на левой границе пространства W, для которой выражение
минимально. Эта задача, очевидно, равнозначна следующей: дано семейство прямых линий
нужно найти прямые этого семейства, пересекающие пространство W, для которых к имеет минимальное значение, и затем найти точки, в которых эти прямые пересекают пространство W. Наклон каждой прямой этого семейства равен
Поскольку
есть точка на дуге косинусоиды QD, то
отрицателен и, следовательно, наклон положителен. Отсюда следует, что минимальное значение к можно получить, если провести прямую
как можно левее, но так, чтобы она пересекала пространство W. Это значит, что прямая должна проходить через точку
, а поскольку ее наклон положителен, А будет единственной точкой в пространстве W, лежащей на этой прямой. Итак, если а лежит на дуге
.
Аналогично, если
— любая точка на прямолинейном отрезке DR, то
состоит из точек пространства W, для которых имеет место минимум выражения
Следовательно, и в этом случае задача сводится к отысканию прямых семейства
пересекающих пространство W, для которых значение к минимально. А поскольку
отрицательно и наклон этих прямых равен
мы находим, рассуждая так же, как и раньше, что
.
Теперь мы берем
на прямолинейном отрезке RB и находим W (а). Вспомнив, что
есть наклон прямой АС, мы рассмотрим три случая:
Случай 1
Случай 2
Случай 3
Случай 1. В этом случае мы опять находим, что
используя по существу метод, применявшийся выше.
Единственное различие состоит в том, что теперь прямые (21) имеют отрицательный наклон; но поскольку абсолютная величина этого наклона больше наклона m прямой АС, то отсюда следует, как и раньше, что если прямая проводится как можно левее, но так, чтобы она пересекала пространство W, то у нее будет лишь одна общая точка с пространством W — точка А.
Случай 2. В этом случае прямые (21) имеют все такой же наклон, как прямая
. Следовательно,
минимально, когда (21) совпадает с
. Очевидно, в этом случае
состоит из всех точек прямолинейного отрезка
.
Случай 3. В этом случае прямые (21) имеют отрицательный наклон, который по абсолютной величине меньше, чем наклон прямой
. Поэтому точка
в пространстве W, для которой к минимально, должна быть точкой касания кривой CQ с самой нижней прямой семейства (21), еще пересекающей пространство W. Эта точка касания единственная, если
выбрано так, что имеет место случай 3. Следовательно, в этом случае
состоит из одной точки кривой CD, которая, очевидно, определяется выбором точки а. Итак, мы показали, как находить образ
всех точек а, лежащих на правой границе QDB пространства
.
Путем точно такого же анализа можно найти образ
любой точки; лежащей на левой границе ACQ пространства W. Приведем без доказательства следующие результаты этого анализа.
Пусть
— точка левой границы ACQ пространства W. Если
, то
есть точка
пространства U. Если
, то мы имеем следующие условия:
1) Если наклон
прямых
меньше, чем наклон —
прямой DB, то
— единственная точка, лежащая на кривой QD границы пространства
.
2) Если наклон прямых (21) больше, чем —
, то
есть точка В пространства
3) Если
, то
есть весь прямолинейный отрезок
.
Мы можем теперь использовать эти выводы для того, чтобы определить, какие точки суть фиксированные.
Прежде всего мы замечаем, что А не есть фиксированная точка, так как
и
есть точка кривой CQ. Следовательно, по теореме 11.7 никакая точка а пространства U, для которой
не может быть фиксированной точкой.
Далее мы замечаем, что ни одна точка кривой CQ не есть фиксированная, ибо для любой такой точки b
состоит из одной точки а на кривой QD, a
для любой точки а на кривой QD есть точка
Следовательно, по теореме 11.7 никакая точка а пространства U, для которой
есть точка кривой
не может быть фиксированной точкой. Это значит, что никакая точка
отрезка DB, для которой
не может быть фиксированной точкой пространства
Из этого мы заключаем, что единственные фиксированные точки пространства
суть те точки, которые предусматриваются случаем 2, то есть те точки а, для которых
Аналогичным образом мы заключаем, что фиксированные точки пространства W суть только те точки
для которых
Мы хотим теперь вычислить координаты точек пространства U (окажется, что есть лишь одна такая точка), для которых справедливо (23). Очевидно, поскольку наклон прямой
равен
наклон прямой АС также равен
поэтому из симметрии пространства U относительно прямой
мы заключаем, что наклон прямой DB равен
.
Итак, уравнение прямой DB таково:
Следовательно,
таким образом, мы имеем:
откуда
Следовательно, единственная фиксированная точка пространства U есть точка
Аналогично, единственная фиксированная точка пространства W есть точка
Цена игры (для как мы видим, равна
В заключение найдем функции распределения F и G, которые соответствуют фиксированным точкам
и
Точка
может быть представлена выпуклой линейной комбинацией точки
и точки
, если положить
откуда мы получаем:
Функция распределения
соответствует точке
, а функция распределения
соответствует точке
. Следовательно, по теореме 11.1 функция
где
и t определяются формулами (18), (19) и (25), соответствует точке
и поэтому она является оптимальной стратегией для
(Можно даже показать, что функция распределения G (26) единственная оптимальная стратегия для
, но мы опустим это доказательство.) Подставляя в (25) значения
и m, мы находим с точностью до двух десятичных знаков
Следовательно, цена игры равна примерно 1,05, а приближенное значение наилучшей стратегии для
есть
Аналогичным путем с помощью фиксированной точки и мы можем найти оптимальную (единственную) стратегию для