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

ГЛАВА XII. ИГРЫ С ВЫПУКЛЫМИ ПЛАТЕЖНЫМИ ФУНКЦИЯМИ

1. Выпуклые функции

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

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

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

Чтобы понять геометрический смысл понятия выпуклости, рассмотрим график на рис. 49.

Поскольку абсцисса точки равна ордината кривой в точке равна , то есть

Аналогично

и

Поскольку абсцисса точки Q равна , очевидно, Q делит отрезок в отношении ; кроме того, поскольку числа и оба положительны, Q лежит между .

На основании подобия треугольников мы заключаем, что В делит АС в отношении и, следовательно,

Рис. 49.

Итак, из неравенства, определяющего выпуклую функцию, вытекает, что

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

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

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

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

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

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

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

строго выпуклая по х для любого , так как

но она не выпуклая по у для любого х, так как

Функция

есть строго выпуклая функция по х для любого у и строго выпуклая функция по у для любого x.

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

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

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

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

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

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

Доказательство. Поскольку непрерывна, она принимает минимальное значение по меньшей мере в одной точке интервала. Но если принимает минимальное значение в двух различных точках а и b, то мы должны иметь в силу строгой выпуклости функции:

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

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

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

а константа с есть единственное решение уравнения

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

Из непрерывности функции М можно легко вывести, что есть непрерывная функция от . В самом деле, если М непрерывна, то для всякого имеется такое , что для мы имеем:

Тогда

Далее, из того, что строго выпукла по у для любого вытекает, что строго выпукла по . В самом деле, по теореме 9.15

Следовательно, Удовлетворяет условиям леммы 12.1, откуда мы заключаем, что принимает минимальное значение в одной и только одной точке с интервала [0, 1]. Итак,

и

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

Пусть G — любая оптимальная стратегия для второго игрока. Покажем, что , то есть для . Для этого, очевидно, достаточно показать, что для всякого положительного числа мы имеем:

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

Далее, на основании теоремы 9.22

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

Поскольку . мы заключаем отсюда, что

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

Но, очевидно,

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

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

Справедливость последнего предложения теоремы вытекает непосредственно из теоремы 10.17.

Совершенно такими же рассуждениями доказывается следующая теорема.

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

а константа с есть единственное решение уравнения

Пример 12.4. Пусть

Поскольку

то есть вогнутая функция от х для любого у. Следовательно, по теореме 12.3

Из рассмотрения графика различных фиксированных значений мы легко получаем, что если то

а если , то

Итак,

Кроме того,

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

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