назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [ 39 ] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


39

Определение. Антагонистаческаяигра

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

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

11.2.Лемма. Непрерывная компактная антагонистическая игра Г = = {х,у,Н) является компактной и во внутренней топологии.

Доказательство. Пусть Xi, лгз,... - последовательность стратегий игрока 1, сходящаяся к его стратегии Xq во внешней топологии. Тогда в силу предположения о непрерьюности функции Н при любом> G у должно быть

lim Н(Хп,у) = Н(хо,у).(11.2)

В силу компактности х X у эта сходимость оказьюается равностепенно непрерьюной поу Gy, так что

lim sup \Н(Хп,у)-Н(хо,у)\=0,

,7 -> оо у

Т.е. р 1 (jc„, Xq) -> 0. Это значит, что последовательность стратегий Xi, ,... сходится к Xq и во внутренней метрике (топологии). □

11.3.Применение теорем п. 8.1 и 10.1 дает нам следующее утверждение. Теорема. Непрерывная компактная антагонистическая игра имеет

при любом € > О е-оптмалъные стратегии игроков, являющиеся смесями конечного числа чистых, а также смешанные оптимальные стратегии.

11.4.Практически теорему п. 11.3 приходится применять в следующем частном виде.

Теорема. Если в игре Г = (х, у, Я > множества стратегий игроков х и у являются выпуклыми многогранниками в конечномерных евклидовых пространствах, а функция выигрыша Н непрерывна на х X у, го в этой игре игроки имеют оптимальные смешанные стратегии, а также - при любом е > О - оптимальные стратегии, являющиеся смесями конечного числа чистых.

Частным случаем этой теоремы является тот, когда х и у - единичные кубы конечномерных евклидовых пространств.

Наконец, "самым частным" случаем, к которому приложимо сделанное заключение, составляют здесь игры на единичном квадрате (см. п. 1.2).

§ 12. ВЫПУКЛЫЕ ФУНКЦИИ ОДНОГО ПЕРЕМЕННОГО

12.1. Никаких общих методов для точного нахождения решений бесконечных антагонистических игр, и в том числе непрерьшньгх игр на единичном квадрате, пока не найдено. Известны только отдельные индивидуальные приемы, годные лишь для тех или иных сравнительно узких ютассов игр. Одан из таких классов составляют антагонистические игры с выпуклыми функциями выигрыша. Они представляют также известный при- > кладной интерес. Далее мы рассмотрим несколько примеров таких вьшуклых игр.



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

Определение. Вещественная функция (р, определенная на числовом промежутке Z, называется выпуклой, если для любых z, z" G z и любого \ G [О, I ]

v?(Xz+(l -X)z")gX<(z) + (l -X)v?(z").(12.1)

Если при z Ф z" и при ХФ0и\ф1ъ (12.1) имеет место строгое неравенство, то функция if назьгоается строго выпуклой.

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

Рис. 2.2

Рис. 2.3

Аналитически вьшуклость дважды дифференцируемой функции соответствует неотрицательности (а в случае строгой вьшуклости - положительности) ее второй производной.

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

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

piXz + (1 - X)z") g X<(z) + (1 - X)iz")

(т.е. если вьшолняется неравенство, противоположное (12.1)).

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

12.2. Лемма. Если - выпуклая функция на сегменте д, Z? ], z j,. .., z„ е [о, Z? ], и X,,. .. , \„ - вещественные числа, для которых п

,. . . , Х„ > О, S X. = 1, 1 = 1

<р( 2 x.z.) 2 Xj-v9(z.). /=11=1

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

12.3. Лемма. Выпуклая функция <р при увеличении аргумента не может переходить от возрастания к убыванию.

Доказательство. Предположим, что Zj < Zj <z, но

«(Zi) <v?(Z2),

(z)<(z).

(12.2)



Найдем такое Л е [О, 1 ], что z= Xz + (1 - X)z. Тогда на основании вьшуклости функции if будет

(z) = (Xz, +a-X)z,)<

SX(z,) + a - X) (Z3) max {(z,), (z) },

что противоречит (12.2). □

12.4.Следствия. I) Выпуклая функция состоит не более чем из двух монотонных частей; если их две, то убывание предшествует возрастанию.

2)Множество точек, на которых выпуклая функция принимает минимальные значения, замкнуто и связно {т.е. является сегментом, быть может, пустым).

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

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

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

Лемма. Если выпуклая функция \ \а,Ъ\ -Кограничена, то она непрерывна в любой точке Zq {a;b).

До казательство. Разрывность ограниченной функции в точке означает, что найдется такая сходящаяся к z последовательность Zj, z, . . ., что

lim (Zn) = t¥(z).

Будем для определенности считать, что <p(Zo) - t = 2b > О, и рассматривать последовательность Z1, Z 2,. . . , начиная с того места, когда ((z,j) <Г + б (рис. 2.3).

Пусть некоторое число h меньше, чем расстояние от z до д или Ь. Возьмем произвольно большое /Г > О, найдем такой номер w, что z„ - z < h/K, и возьмем точку

nf.=o +(0 -Zn){K-l){a,b). Очевидно,

К - 1 1 *

« " к "К К

так что из выпуклости функции следует К-11 .

откуда

К -I1 *

? + 2б < ~j-(r + 6)+ - {Znj.).

v?(z*)>/i:(r + 26) -(а:- 1)(г + б) = А:б + f+ 6,

т.е. с ростом К значения функции «(z* ) неограниченно возрастают. Это, однако,

противоречит предположению об ограниченности функции ip, □

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

lim v?(z) < v?(fl)(12.2)

и аналогично при z -Ь.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [ 39 ] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]