ГЛАВА XI. РАЗДЕЛИМЫЕ ИГРЫ

1. Метод отображения

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

Так, функция М, определенная уравнением

разделима; здесь мы можем взять:

Очевидно, данная разделимая функция может быть представлена в форме (1) многими способами. Например, для указанной выше функции мы можем также взять:

Если функция М разделима, то по определению мы имеем тождественно по и

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

мы можем написать:

где функции и непрерывны.

Многочлен от двух переменных есть, очевидно, частный случай разделимой функции. Так, многочлен

может быть представлен в форме (2), если взять:

Разделимой (или полиномиальной) игрой мы называем непрерывную игру, у которой платежная функция разделима. Таким образом, в разделимой игре платежная функция удовлетворяет уравнению (1), где и суть непрерывные функции на замкнутом единичном интервале.

Если М — платежная функция разделимой игры и если применяет смешанную стратегию F, а применяет смешанную стратегию G, то математическое ожидание выигрыша для (на основании уравнения (1) и некоторых простых свойств интеграла Стилтьеса) определяется так:

Таким образом, зависит от F и G лишь постольку, поскольку F и G влияют на значение компонент двух векторов

и

Легко видеть, что

и

могут представлять один и тот же вектор, если даже не тождественны; но если два вектора тождественны, то независимо от того, тождественны или нет, выполняемся

для всякой функции распределения G, и не имеет значения, применяет ли стратегию или стратегию Поэтому, когда два данных вектора одинаковы, мы будем называть стратегии эквивалентными (конечно, относительно данной игры). Таким образом, если имеется непрерывная игра, платежная функция которой удовлетворяет уравнению (1), то, как мы видим, для выбор смешанной стратегии сводится к выбору точки из некоторого подмножества U -мерного евклидова пространства. Это множество U, которое мы будем иногда называть пространством U, состоит из всех точек таких, что для некоторой функции распределения F

Когда и и F удовлетворяет равенствам (4), мы говорим, что и и F соответствуют друг другу (данная точка в пространстве U будет, вообще говоря, соответствовать различным функциям распределения).

Аналогично, для выбор смешанной стратегии сводится к выбору точки из множества, которое мы назовем пространством W, то есть из множества всех точек -мерного евклидова пространства таких, что для некоторой функции распределения

Следует заметить, что множества U и W относятся к данному частному представлению платежной функции М. Как мы видели раньше, одна и та же функция М может удовлетворять как равенству

так и равенству

При представлении функции М пространство U есть подмножество трехмерного евклидова пространства, а при втором — двумерного.

Но мы часто будем опускать ссылку на эту зависимость множеств U и W от способа представления функции М, так как при разборе данной игры мы обычно полагаем, что представление задано раз и навсегда.

До сих пор мы считали функцию математического ожидания выигрыша Е определенной только для функций распределения (в качестве аргументов). Однако для некоторых дальнейших рассуждений уместно говорить также о математическом ожидании выигрыша игрока , когда выбирает точку и из пространства U, а выбирает точку из пространства W. Поэтому мы расширяем область определения функции Е следующим образом: если гг — любая точка пространства U, a w — любая точка пространства W и если — любая функция распределения, соответствующая точке гг, a G — любая функция распределения, соответствующая точке w, то мы полагаем:

Из этой формулировки ясно, что при этом определена корректно, то есть, если гг соответствует и , a w соответствует и G, и G', то

и мы можем также написать:

Из (3) мы видим, что если - любая точка пространства U, a — любая точка пространства W, то

Итак, Е есть билинейная форма от координат и .

Для наших целей желательно теперь установить некоторые геометрические свойства пространств U и W и описать соотношение между каждым из этих пространств и множеством всех функций распределения. Эти положения будут сформулированы в нескольких дальнейших теоремах.

В главе II мы определили понятие выпуклой линейной комбинации конечного числа точек евклидова -мерного пространства. По аналогии с этим понятием мы говорим, что функция F есть выпуклая линейная комбинация функций с весами , если и если для всякого из [0, 1]

Когда F есть такая выпуклая линейная комбинация функций мы будем писать просто так:

Теорема 11.1. Пусть — функции распределения, — соответствующие точки пространства U разделимой игры и — любой элемент множества . Тогда точка

есть точка пространства U и соответствует функции распределения

Аналогичное предложение справедливо для пространства

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

Пусть . Поскольку соответствует , мы имеем:

Пусть . Поскольку

мы видим, что

Из (5) и (6) мы заключаем, что для

и, следовательно, на основании соответствующих теорем об интегралах Стилтьеса, для

Поскольку по теореме 8.3 F есть функция распределения, мы заключаем, что соответствует функции распределения F, и, следовательно, по определению, и принадлежит пространству U.

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

Мы можем классифицировать точки пространства U по типам соответствующих им функций распределения. Особенно важное подмножество пространства U — это подмножество, содержащее те точки, которые соответствуют одноступенчатым функциям. Мы обозначим это подмножество через , а аналогичное подмножество пространства W через . Весьма полезна следующая, легко доказываемая

Теорема 11.2. Пусть платежная функция М разделимой игры представлена равенством

где — непрерывные функции соответственно от и . Тогда множество U (по отношению к данному представлению) состоит из всех точек таких, для некоторого t из [0, 1]

Аналогично, множество состоит из всех точек таких, что для некоторого из [0, 1]

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

Доказательство второй части теоремы аналогично.

Следствие 11.3. Множества U и W для любой разделимой игры суть ограниченные, замкнутые, связные множества.

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

Теорема 11.4. Пространство U для любой разделимой игры есть выпуклая оболочка множества , а пространство W — выпуклая оболочка множества W (следовательно, пространство U — и аналогично пространство W — есть замкнутое ограниченное выпуклое множество).

Доказательство. Пусть U — выпуклая оболочка множества U. Мы хотим показать, что U совпадает с пространством U, то есть . Поскольку , мы видим непосредственно из теоремы 11.1, что . Поэтому остается лишь показать, что .

Допустим, что имеется точка , принадлежащая U, но не принадлежащая U.

Поскольку, согласно следствию 11.3, ограничено и замкнуто, мы видим, что U также замкнуто и ограничено; кроме того, U — выпуклое. Поскольку не находится в U, то из теоремы 2.3 мы заключаем, что существуют постоянные и , где такие, что

и для любой точки множества U

Из (8) и (9) мы видим, что для всякой точки множества

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

Поскольку (10) справедливо для всякой точки из U, оно справедливо, в частности, для всякой точки из U. Отсюда на основании теоремы 11.2 мы заключаем, что для всех

Пусть теперь F — функция распределения, которой соответствует точка пространства 13, то есть такая, что

Из (11) мы заключаем, что

и, следовательно, поскольку все величины постоянны,

или

или, наконец, на основании (12)

или

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

Поскольку и поскольку мы видели, что множество U ограниченное, замкнутое и выпуклое, мы заключаем, что множество U также ограниченное, замкнутое и выпуклое. Это завершает доказательство. Доказательство для пространства W аналогично.

Теорема 11.5. Пусть М — платежная функция разделимой игры, и пусть

Тогда всякая смешанная стратегия (обоих игроков) эквивалентна ступенчатой функции с числом ступеней не больше ; в частности, каждый игрок имеет оптимальную стратегию, которая является ступенчатой функцией с числом ступеней не больше n.

Доказательство. Пусть F — любая функция распределения, и пусть — точка пространства U, соответствующая функции F (доказательство будет аналогичным, если мы берем функцию распределения G для и рассматриваем точку пространства W, которая соответствует функции G). Поскольку пространство U по теореме 11.4 есть выпуклая оболочка связного множества U и поскольку пространство U есть подмножество евклидова -мерного пространства, мы видим на основании теоремы 2.1, что имеются точки из U и элемент из такие, что

Поскольку то имеются ступенчатые функции такие, что (для ) соответствует функции . Тогда по теореме 11.1 мы видим, что функция , определенная равенством

соответствует точке и. Очевидно, I есть ступенчатая функция, имеющая самое большее n ступеней, и I и F эквивалентны, поскольку обе функции соответствуют одной и той же точке пространства U.

В частности, любая оптимальная стратегия F (по теореме 10.4 такая существует) эквивалентна ступенчатой функции , имеющей самое большее ступеней, и такая функция , конечно, сама оптимальна.

Охарактеризуем теперь те точки пространств U и W, которые соответствуют оптимальным стратегиям. Для этого уместно определить отображение точек пространства U в множество точек пространства W и отображение точек пространства W в множество точек пространства U. Если и — любая точка пространства U, то образом точки и мы будем называть множество точек w пространства W таких, что

Будем обозначать образ точки и через . Аналогично, если до — любая точка пространства W, то образом точки w мы будем называть множество всех точек и пространства таких, что

Образ точки до обозначим через .

Если точка и пространства U и точка до пространства W таковы, что то мы называем точку и фиксированной точкой пространства U, а точку до — фиксированной точкой пространства .

Теорема 11.6. Если F — любая функция распределения и если — соответствующая ей точка пространства пространствах , то F есть оптимальная стратегия для тогда и только тогда, когда точка и фиксированная. (Аналогично, функция распределения G есть оптимальная стратегия для тогда и только тогда, когда соответствующая точка до пространства W есть фиксированная точка.)

Доказательство. Пусть — функция распределения, и пусть — соответствующая ей точка пространства U. Если говорится, что и есть фиксированная точка пространства U, то это значит, что для некоторой точки до пространства W мы имеем и , то есть

Если обозначить через функцию распределения, которой соответствует точка до, то из определения функции следует, что равенства (13) равносильны равенствам

которые, согласно теореме 10.5, означают, что есть оптимальная стратегия для .

Теорема 11.7. Если — любая фиксированная точка пространства U и — любая фиксированная точка пространства W, то и и .

Доказательство. Поскольку есть фиксированная точка пространства , то существует точка до пространства W такая, что и , то есть такая, что

и

Аналогично, поскольку до есть фиксированная точка пространства W, то имеется точка и пространства U такая, что

и

Тогда мы имеем:

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

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