с другой стороны, из полунепрерывности сверху функции Н{Х*, •) в точках у = 0 и у=1 следует, что последнее неравенство остается в силе и при = О и у = \. Это означает, что ситуация {Х*,у*) является седловой точкой в исходной игре Г.

б)7*= 0. В этом случае игрок 1 также имеет чистую оптимальную стратегию. Обозначая ее через х*, мы имеем

H{x,Q)H{x\G)<H{x\y) длявсех x,j;G [0,1].

Осуществим переход к функции выигрыша Я.Заметим для этого, что ввиду равностепенной непрерывности функций Я (х, •) по всякому 6 > О найдется такое б, что при О < < 6 будет

Н{х,у) --еН{х\Уе)Н{х\у) +€ для всех х,уЕ [0,1], откуда, согласно (20.1),

Я(х, Je)Н{х\Уе) Н{х\у) +€ длявсех xG [О, 1], JG (О, 1).

Как и в случае а), полунепрерывность сверху дает здесь возможность распространить написанное неравенство на значения j = О и j = 1.

Таким образом, в этом случае игра Г имеет при любом € > О ситуацию €-равновесия (2 е-седловую точку) в чистых стратегиях.

в)К тому же выводу, что и в случае б), мы приходим при j* = 1. □

§ 21* ВЫПУКЛЫЕ ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ

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

Определение. Вещественная функция определенная на выпуклом подмножестве Z конечномерного евклидова пространства, назьшается выпуклой, если при любых Zj , G Z и Л G [ О, 1 ]

V? (XZj + (1 - \) z) 4 \ (Z, ) + (1 - X) (Zj). □

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

Естественным образом определяются на любом выпуклом множестве z и вогнутые функции.

21.2.На случай произвольного вьшуклого подмножества конечномерного евклидова пространства дословно переносятся формулировки и доказательства лемм пп. 12.2 и 12.3 и - с несущественными изменениями - доказательство леммы п. 12.5.

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

Из непрерывности выпуклой функции и аналогов леммы п. 12.2 следует аналог леммы п. 12.6.

Лемма. Если функция выпукла на гс RP, а Z - произвольная вероятностная мера на z, то

(JzdZiz)) f(z) dZ(z).(21.1)

Аналоги утверждений п.п 12.7-12.11 также остаются в силе.

Из следствия п. 12.7 следует, что всякий локальный минимум выпуклой функции (/? является ее наименьшим значением.

21.3. Лемма. Если zc л z-*R - выпуклая функция, то множество (/? = (z: yp(z) а} является выпуклым.

Доказательство. Пусть z,, z и хе [О, 1]. Тогда по вьшуклости функции if должно быть

(XZ, + (1 - Л) 2,)< (Z,) + а-Х) (zJ Ха+ Ц-Х)а =л,

т.е. \Zj + (1 - X)Z2 ед. □

§ 22*. ВЫПУКЛЫЕ ИГРЫ С ВЕКТОРНЫМИ СТРАТЕГИЯМИ. ЧИСТЫЕ ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА 2

22.1.0пределение. Непрерывная игра

Г = <х,у,Я>,(22.1)

в которой X и у являются компактными подмножествами конечномерных евклидовых пространств, а множество у выпукло, называется выпуклой игрой, если функции Я (д:, •) выпуклы при любом значении xGx.

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

22.2.Теорема. В выпуклой игре Г = <х, у. Я) игрок 2 имеет чистую оптимальную стратегию.

Доказательство. Так как рассматриваемая выпуклая игра компактна, согласно теореме п. 10.1 она имеет значение Up, а игроки 1 и 2 - оптимальные (вообще говоря, смешанные) стратегии X* и Y*, Тогда

Н(х, Y*)S Н{Х\ Г*) = для любого xG х.(22.2)

Составим, как и при доказательстве теоремы п. 13.2, чистую стратегию

y*-!ydY*{y).(22.3)

Применяя к выпуклой функции Н{х, •) и мере У* неравенство (21.1), мы получаем при любом xGx

Н(х,у*)=Н(х, fydY*iy))< У

< fH(x,y)dY*(y)-H(x, У*),(22.4)

что вместе с (22.2) даетЯ(л:,у*) i?r прилюбом xGx.

Согласно теореме п. 5.5 это означает оптимальность стратегии у* игрока 2. □

Буквально так же, как и в теореме п. 13.2, устанавливается, что множество всех чистых оптимальных стратегий оказывается в рассматриваемом случае вьшуклым и замкнутым.

22.3.Как и в § 13, из доказанной теоремы получаем следствие. Следствие. В выпуклой игре Г из (22.1) имеет место равенство

i; = min max Н(х, у) = max Н(х, у*),(22.5)

где у* - оптимальная стратегия игрока 2 в Г. 136

Все чистые оптимальные стратегии игрока 2 в Г суть решения уравнения и =тахЯ(л:,). □(22.6)

22.4. Для простоты дальнейших рассмотрений мы ограничимся случаем, когда оптимальная стратегия у* игрока 2 в выпуклой игре Г является единственной. Это будет, например, в том случае, когда функция вьшгрыша Я строго вьшукла (ср. § 15).

Охарактеризуем положение оптимальной стратегии у* игрока 2 в и-мер-ном множестве всех его стратегий у.

Точка у* является либо внутренней в множестве у, либо принадлежит границе у и тогда содержится в пересечении у с некоторой опорной к у гиперплоскостью. В случае, когда имеется несколько таких пересечений, будет выбирать то из них, которое имеет наименьшую размерность. Ясно, что если эта размерность равна нулю, то у* будет крайней точкой у, а если она положительна, то у* будет внутренней точкой соответствующего пересечения. Обозначим это пересечение через у*, допуская при этом и крайние случаи: у*-у* и у* = у. Для наглядности заметим, что если у есть вьшуклый многогранник, то у* есть наименьшая по размерности (или, что то же самое, по включению) грань у, содержащая j*.

Пусть размерность у* равна г. Тогда по теореме Каратеодори (см. п. 11.5) найдутся такие г+ 1 крайних точек Уо,У\у . * -, Уг множества у, что7* является их выпуклой комбинацией:

y*=j:\*yi, М>о (/ = 1,...,г), i;xj=i. (22.7)

Для дальнейшего нам будет полезно дополнить этот набор стратегий еще п - г точкамиУг+ij ... ,Упу которые вместе с имеющимися составляют вершины некоторого «-мерного симплекса (т.е. являются точками общего положения). Поэтому вблизи у* каждая точка jGy может быть представлена в виде

y=X\yi,(/=1,...,/2),ГХ,.= 1, (22.8)

/=11=1

т.е. в виде фукктиУ =у(К, Xi, ..., Х„) от барицентрических координат Хо, Xl, ..., Х,х, причем при у=у* последние п - г координат должны обращаться в нуль.

§ 23* ВЫПУКЛЫЕ ИГРЫ С ВЕКТОРНЫМИ СТРАТЕГИЯМИ. ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА 1

23.1. Усложнение, которое наблюдается в описании и нахождении оптимальных стратегий игрока 1 при переходе от вьшуклых игр на единичном квадрате к векторным вьшуклым играм, выходит за пределы обычных усложнений, возникающих при переходе от оптимизационных задач одной переменной к оптимизационным задачам нескольких переменных: не поддается распространению на векторный случай теорема п. 14.5. Ее роль будет играть следующее утверждение.