Главная > Математика > Введение в теорию игр
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4. Дальнейшие примеры

Пример 11.18. Платежная функция М разделимой игры удовлетворяет следующему равенству (для любой точки замкнутого единичного квадрата):

Возьмем

так что M представится следующим образом:

Итак, пространства U и W имеют два измерения. Для нахождения U мы чертим кривую, соответствующую параметрическим уравнениям

Эта кривая, очевидно, есть окружность радиуса 1 с центром в начале координат (поскольку мы чертим кривую для и поскольку , то часть окружности чертится дважды, но сейчас это для нас безразлично). Следовательно, U (выпуклая оболочка множества U есть эта окружность вместе с ее внутренней частью. Аналогично, поскольку , кривая W тождественна с U, a W тождественно с .

Очевидно, данное представление является каноническим, так как

этого примера уравнения (28) записываются так:

а уравнения (29) так:

Решения этой системы, очевидно, такие: и . Итак, первая критическая точка принадлежит множеству а вторая — мнджеству . Следовательно, по теореме 11.16, р — единственная фиксированная точка пространства U, a q — единственная фиксированная точка пространства .

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

Поскольку есть точка множества U, этой точке соответствует одноступенчатая функция ; итак, мы имеем:

Эти уравнения наряду с неравенством

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

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

Обобщая это рассуждение, мы находим, что наиболее общий вид функции распределения с двумя ступенями, соответствующей точке пространства U, такой:

где Итак, мы нашли бесконечное семейство оптимальных стратегий для .

Аналогично можно написать общее выражение для оптимальной стратегии игрока содержащей лишь две ступени:

где и

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

Решая совместно эти уравнения, получаем:

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

где определяются уравнениями (35), есть оптимальная стратегия для .

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

Так, функция распределения F такая, что

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

Из теоремы 11.12 следует, что цена этой игры для равна 0.

Пример 11.19. Платежная функция разделимой игры (для любой точки замкнутого единичного квадрата) удовлетворяет следующему равенству:

Мы примем здесь

так что можно представить следующим образом:

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

и следовательно, М представлена в канонической форме.

Вспомнив, что лежит в интервале [0, 1], мы видим, что кривая есть часть окружности

представленная на рис. 43 дугой ABC (угол равен 4 радианам), и что пространством U является заштрихованная область. Пространство W изображается заштрихованной областью на рис. 44.

Первую критическую точку мы находим, решая уравнения

Отсюда заключаем, что точка является внутренней точкой пространства U. Вторая критическая точка есть Это внутренняя точка пространства W. Из следствия 11.16 вытекает, что точки и суть единственные фиксированные точки соответственно пространств U и W.

Рис. 43.

Рис. 44

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

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

Положив

мы имеем:

Теперь легко убедиться в том, что пространство U состоит из точек, лежащих на или внутри окружности

а пространство W состоит из точек, лежащих на или внутри окружности

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

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

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

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

Пример 44.21 Платежная функция разделимой игры удовлетворяет (для любой точки замкнутого единичного квадрата) следующему равенству:

Положив

мы имеем:

и отсюда

И первая, и вторая критические точки суть . Мы легко можем убедиться в том, что пространства U и W изображаются заштрихованными областями соответственно на рис. 45 и на рис. 46. Далее, всякая точка отрезка АВ есть фиксированная точка пространства U, а всякая фиксированная точка отрезка АВ есть фиксированная точка пространства W.

Рис. 45.

Рис. 46.

В примере 11.20 мы видели, как можно использовать следствие 11 15 для разбора некоторых игр, в которых ни одно из пространств U или W не содержит в себе, своих критических точек. Следующий пример поясняет, как можно использовать это следствие для исследования игр, у которых одна критическая точка лежит в соответствующем ей пространстве, а другая не лежит.

Пример 11.22. Платежная функция М разделимой игры (для любой точки замкнутого единичного квадрата) удовлетворяет следующему равенству:

Положив

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

вместе с ее внутренней частью, а пространство W представляет окружность

вместе с ее внутренней частью. В этом случае критическая точка есть . Эта точка не находится в W, но лежит внутри пространства .

Поскольку вторая критическая точка не принадлежит пространству W, то на основании следствия 11.15 мы видим, что фиксированные точки пространства U находятся только в . При помощи рассуждения, аналогичного тем, которые мы применяли для этой цели в примере 11.20, мы докажем, что в U есть лишь одна фиксированная точка, скажем, . Но если бы в находилась фиксированная точка пространства W, то по теореме 11.14 первая критическая точка была бы фиксированной точкой пространства U. Это противоречит утверждению, что единственная фиксированная точка пространства U лежит в Следовательно, фиксированные точки пространства W должны лежать только в В(W); а поскольку W есть круг, мы заключаем (опять при помощи таких же рассуждений, как в примере 11.20), что в W имеется лишь одна фиксированная точка. Итак, мы видим, как и в примере 11.20, что игра имеет седловую точку.

<< Предыдущий параграф Следующий параграф >>
Оглавление