4. Способы вычисления и проверки решений

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

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

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

Тогда имеют место следующие равносильные условия:

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

2) если F и G — любые функции распределения, то

3) если z и w - любые точки интервала [0, 1], то

Доказательство. Равносильность условий (1) и (2) следует прямо из теоремы 10.4 и из определения седловой точки. Чтобы убедиться в том, что из условия (2) вытекает условие (3), мы берем и применяем теорему 9.20. Чтобы убедиться в том, что из условия (3) вытекает условие (2), предположим, что для всех z и w в [0, 1] мы имеем:

Заменив z на х в первой части этого неравенства, мы получим (на основании теоремы 9.15) для любой функции распределения

Аналогичным образом мы можем получить вторую часть неравенства (2) из второй части неравенства (3), что завершает доказательство.

Теорема 10.6. Пусть М — непрерывная платежная функция непрерывной игры, цена которой равна v. Функция распределения есть оптимальная стратегия для первого игрока тогда и только тогда, когда для всякого у из [0, 1]

Функция распределения есть оптимальная стратегия для второго игрока тогда и только тогда, когда для всякого х из [0, 1]

Доказательство. Если — оптимальная стратегия первого игрока, то на основании теоремы 10.5 мы заключаем, что для всех у

Предположим теперь, что есть функция распределения, которая удовлетворяет неравенству (26) для всех у. Пусть G — оптимальная стратегия для второго игрока. На основании теорем 9.16 и 9.15 из неравенства (26) мы заключаем, что

Поскольку G оптимальна, мы видим на основании теоремы 10.5, что для любой функции распределения F

в частности,

Из (27) и (28) мы имеем:

и, следовательно, из (26) для всех y

Поскольку G оптимальна, мы заключаем из теоремы 10.5, что для всех х

и, следовательно, в соответствии с равенством (29) приходим к выводу, что

Из (30) и (31) на основании теоремы 10.5 мы заключаем, что есть оптимальная стратегия для первого игрока, что и требовалось доказать.

Доказательство второй части теоремы аналогично. Теорема 10.7. Пусть М — непрерывная платежная функция непрерывной игры, v — действительное число и суть функции распределения такие, что для всех и из [0, 1]

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

Доказательство. Из условия мы заключаем, как и в доказательстве теоремы 10.5, что для всех функций распределения F и G

отсюда

так что . Теперь на основании теоремы 10.6 вытекает, что суть оптимальные стратегии.

Только что доказанные теоремы дают нам способы проверки решения игры. Мы поясним это на примерах.

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

Мы хотим показать, что решение игры определяется так:

По теореме 10.7 нам необходимо лишь показать, что 1

И

На основании теорем 9.11 и 9.20 вместо этого мы можем доказать равносильные неравенства

Умножая обе части неравенства (32) на положительную величину

получаем равносильное неравенство

которое в свою очередь равносильно неравенству

а последнее, очевидно, выполняется для всех из [0, 1].

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

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

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

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

и

то

Доказательство. По теореме 10.6 мы имеем для всех х

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

Допустим теперь, что

Тогда для всех х

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

Мы пришли к противоречию. Следовательно,

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

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

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

и

Тогда, если х есть любая точка интервала [0, 1], в которой производная слева функции отлична от нуля (то есть положительна и конечна или бесконечна), то

аналогично, если у есть любая точка интервала [0, 1], в которой производная слева функции отлична от нуля, то

В частности, если ступенчатая функция, так что

то

А если — ступенчатая функция, так что

то

Доказательство. По теореме 10.6, для всех х из [0, 1] мы имеем:

Далее, по определению цены игры, мы имеем:

Отсюда, если производная слева функции отлична от нуля при мы заключаем (на основании теорем 9.27 и 10.9), что

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

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

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

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

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

Мы хотим найти оптимальные стратегии обоих игроков в виде

Допуская, что имеется решение вида (34), мы получим:

следовательно, по теореме 10.6 для всех у из [0, 1]

Поскольку , из (35) мы получим, в частности,

или

Применяя способы, описанные в главе VII, мы можем доказать что функция не имеет седловой точки в единичном квадрате, поэтому игра не может иметь решений вида (34), где или .

Итак, из неравенства (36) мы заключаем, что

Аналогично, подставляя в (35) b вместо y, мы получаем:

откуда

Из этого равенства на основании (35) мы заключаем, что для всех у из [0, 1]

или

откуда

Из неравенства (38) вытекает, что либо , либо Аналогично либо , либо . Далее, b не может быть равно с, поскольку М не имеет седловой точки. Не ограничивая общности, мы можем считать, что

Из (38) и (39) получаем:

откуда

Аналогично,

Итак, функции имеют следующий вид:

и мы получаем:

Положив

мы видим (на основании теоремы 10.10), что

Поскольку дифференцируема в открытом интервале (0, 1) и поскольку находится в этом интервале, мы заключаем из равенства (42), что производная

при должна быть равна нулю. Так как

мы получаем отсюда:

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

Итак, из (39), (40) и (43) мы заключаем, что если для нашей игры существуют оптимальные стратегии, имеющие форму (34), то мы должны иметь:

Как в примере 10.8, мы убеждаемся, что (44) действительно есть решение.

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

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

Мы хотим показать, что решение игры будет:

Поскольку дифференцируема в интервале [0, 1], мы видим на основании теоремы 9.19, что для всех из [0, 1]

Аналогично, для всех х в [0, 1]

Из равенств (45) и (46) на основании теоремы 10.7 мы заключаем, что данные стратегии действительно оптимальны и

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

Теорема 10.13. Пусть М — платежная функция непрерывной игры, имеющей решение, и положим, что для всех х и у из интервала [0, 1]

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

Доказательство. Пусть v — цена игры, и пусть оптимальная стратегия первого игрока, a — оптимальная стратегия второго. Тогда на основании теоремы 10.5 мы видим, что для всех функций распределения F и G

Применив к неравенству (47) условие

мы получим:

отсюда

Изменив обозначения переменных интегрирования в (48), мы получаем:

Из (49) на основании теоремы 10.7 заключаем, что

откуда у = 0. Далее, из (49) и теоремы 10.7 вытекает, что — оптимальные стратегии как для первого, так и для второго игрока.

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

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

Надо найти оптимальные стратегии для обоих игроков в виде:

Поскольку есть функция распределения, мы должны иметь:

и, следовательно, Итак, опуская индекс, мы можем напйсать:

и аналогично

Мы замечаем, что

так что на основании теоремы 10.13

и любая оптимальная стратегия для первого игрока есть также оптимальная стратегия для второго игрока, то есть мы можем положить:

Поскольку точка не есть седловая точка функции , в (51) не может быть Следовательно, поскольку функция имеет положительную производную (в частности, положительную производную слева) во всякой точке х из открытого интервала (0, 1), мы заключаем (на основании теоремы 10.10), что для всякого х из (0, 1)

то есть

Поскольку при у = 0 имеет скачок величины а и непрерывна всюду, кроме этой точки, мы легко находим:

Итак, мы имеем:

для всех х из открытого интервала (0, 1), а отсюда мы заключаем, что

Таким образом, мы получаем:

Теперь легко проверить, как в примере 10.12, что (52) действительно есть решение данной игры.

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

Пример 10.15. Платежная функция непрерывной игры М такова:

Мы хотим найти непрерывную оптимальную стратегию для первого игрока, удовлетворяющую следующим условиям:

дважды дифференцируема при

здесь а — фиксированное число.

Поскольку , то на основании теоремы 10.13 мы видим, что

и что оптимальная стратегия также для второго игрока.

Из (55) и теоремы 10.10 мы заключаем, что для

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

Поскольку по условию дифференцируема, мы полагаем:

далее, используя теорему 9.19, мы получаем из равенства (56) для любого равенство

которое легко приводится к виду

Дифференцируя (57) по х и применяя правило дифференцирования под знаком интеграла, получаем:

ИЛИ

Дифференцируя (58) опять по х, получаем:

и отсюда

Следовательно, для мы должны иметь:

Решая это дифференциальное уравнение, мы получаем:

где — некоторая константа, и отсюда

где — также константа.

Итак, мы имеем:

Поскщку равенство (56) справедливо для всех , то ввиду непрерывности функции мы заключаем, что оно справедливо также для .

Итак,

Но из первого равенства (61) мы имеем:

и, следовательно, из (62) получаем:

или, ввиду второго равенства (61),

или

Но поскольку функция М не имеет седловой точки, мы видим, что и, следовательно,

Проводя интегрирование, находим:

и, следовательно, либо , либо . Но поскольку при функция М имела бы седловую точку, мы заключаем, что

Поскольку непрерывна, то на основании равенств (61) мы должны иметь:

так что

Поскольку есть функция распределения, мы должны иметь:

так что

Решая совместно уравнения (64) и (65), мы находим:

Итак, если имеется какая-либо оптимальная стратегия, удовлетворяющая условиям (53), (54) и (55), то решение игры определяется следующими равенствами:

Проверим теперь, что равенства (67) действительно дают решение, то есть покажем, что если F и G суть любые функции распределения, то

и

Легко убедиться, что (69) справедливо; легко также показать, что (68) справедливо для всех функций распределения, непрерывных в интервале (0, 1]. Но из того, что разрывна при , мы видим, что величины не существуют, если F и G имеют разрывы в полуоткрытом интервале (0, 1].

Следовательно, в силу определения интеграла Стилтьеса неравенства (68) не имеют смысла, если F и G имеют разрывы в (0, 1], поэтому мы можем лишь сказать, что неравенству (68) удовлетворяют все функции распределения F и G, непрерывные в (0, 1]. Однако мы можем устранить это затруднение, обобщив наше определение интеграла Стилтьеса, а именно, введя понятие интеграла Лебега — Стилтьеса, который связан с интегралом Стилтьеса (иногда называемым интегралом Римана — Стилтьеса) примерно так же, как интеграл Лебега связан с интегралом Римана. Если мы положим:

где интегралы понимаются в смысле Лебега — Стилтьеса, то неравенство (68) имеет смысл и справедливо для всех функций F и G, даже для разрывных.

В этой книге мы не будем вводить интегралы Лебега — Стилтьеса, потому что для изложения надлежащей теории этих интегралов необходимо основательное знакомство с другими разделами математики. Но и не вводя это понятие, мы можем сказать, что данные функции распределения представляют оптимальные стратегии для обоих игроков в том смысле, что для всякого х и у из [0, 1] мы имеем:

Замечание 10.16. В примере 10.15 нам удалось найти решение непрерывной игры с разрывной платежной функцией. Таким образом, оказывается, что теорему 10.4 можно обобщить так, чтобы охватить некоторые разрывные функции.

В математической литературе можно найти подобные примеры, но мы не собираемся их приводить. Следует лишь отметить, что можно интуитивно прийти к обобщению теоремы 10.4. Пусть имеется игра Г, платежная функция М которой не непрерывна; существуют функции и Ф, взаимно однозначно отображающие интервал [0, 1] на себя, и функция

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

Итак, пусть имеется игра, у которой разрывная платежная функция М определена следующим образом:

Определив 0 условиями

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

Поскольку ЛГ непрерывна, мы заключаем, что игра, у которой платежная функция есть М, также имеет решение.

Однако нужно заметить, что игра с разрывной платежной функцией может вообще не иметь никакой цены. Пример игры,которая по интуитивным соображениям действительно не должна иметь цены, был приведен в главе VII (пример 7.3).

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

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

а в качестве константы а может быть принято любое решение уравнения

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

а в качестве константы b может быть принято любое решение уравнения

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

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

Далее, если — оптимальная стратегия первого игрока, то по теореме 10.9

или

Итак, если есть оптимальная стратегия первого игрока, то а должно удовлетворять равенству (70). С другой стороны, если мы предположим, что а — какое-либо число, удовлетворяющее равенству (70), то для всех у

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

Замечание 10.13. Из теоремы 10.17 вытекает очевидное следствие, что если М — непрерывная платежная функция непрерывной игры и если существует оптимальная стратегия для первого игрока и оптимальная стратегия для второго игрока, то М имеет седловую точку.

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

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

Тогда цена игры v определяется формулой

где в качестве констант можно взять любые решения уравнения

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

то

а в качестве констант можно взять любые решения уравнения

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

Теорема 10.20. Любая выпуклая линейная комбинация оптимальных стратегий есть оптимальная стратегия.

Теорема 10.21. Если

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

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

Впервые доказательство теоремы 10.4 было дано в работе Виля [109]. Доказательства обобщений этой теоремы даны в работах Вальда [115] и Карлина [56].