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


[Старт] [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]


41

= Ну{х\у*)0,(14.2)

у = у*

§ 14. ВЫПУКЛЫЕ ИГРЫ НА ЕДИНИЧНОМ КВАДРАТЕ. ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА 1

14.1.Займемся описанием оптимальных стратегий игрока 1.

Далее через Я(х, у) обозначаются значения частной производной функции выигрыша Н по у. При у = О это выражение понимается как правая производная, а при 7 = 1 - как левая. Мы будем предполагать, что эта производная супдествует для всех значений хну.

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

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

H{x,y*)-VY.(14.1)

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

14.2.Лемма. Если у* - оптимальная стратегия игрока 2 в выпуклой игре с функцией выигрыша Я, дифференцируемой поу,и у*>0, то существует такая существенная стратегия х игрока 1, что

ЬН(х\у)

Ъу •

Доказательство. Предположим, что для каждой существенной стратегии Xq игрока 1 Ну(хо, у*) > 0. Это значит, что для всякой существенной стратегии лго функция Ну(хо, • ) в точке у* строго возрастает. Следовательно при значениях у, меньших чем у* и близких к у*, будет Н(хо.у)<Н(хо,уП.

Говоря точнее, по каждой существенной стратегии Xq найдутся такие б(хо)>0 и б(хо)>0, что

Н(х,у)<Н(х,у*)-е(Хо)

при всех X, для которых \ х - Хо\ < S(хо). Ввиду компактности множества всех существенных стратегий оно покрьюается конечным числом таких 6 (хо)-окрестностей. Пусть е - наименьшее из всех соответствующих чисел б(хо). Тогда будет

Я(х,;;) < Н(х,у* ) - 6.(14.3)

Пусть теперь X* - оптимальная стратегия игрока 1. Так как (14.3) по предположенному справедливо для всех существенных стратегий игрока 1, и в том числе для всех точек спектра X*, мы имеем, интегрируя,

Н(Х\у) <Н(Х\у* )-e = Vr-€,

а это противоречит оптимальности стратегии X*. □

14.3.Аналогично доказьшается следующее симметричное утверждение. Лемма. Если в условиях предыдущей леммы у* < I, то существует

такая существенная стратегия х" игрока 1, что Ну(х\у*)0,

14.4.Объединяя эта леммы, мы получаем следствие.



Следствие. Если в условиях предыдущих лемм 0<у* < 1, то найдутся такие существенные стратегии хи х" игрока!, что

Н;(х.у*)0,(14.4)

Ну(х",у*)0.(14.5)

14.5. Теорема. Пусть Г - выпуклая игра с функцией выигрыша Н, дифференцируемой по у при любом х, у* - чистая оптимальная стратегия игрока 2 в ней, avjp - ее значение. Тогда:

1)если у* = I, то среди оптимальных стратегий игрока 1 имеется чистая стратегия х\ для которой ЯДл:, 1) < 0;

2)если V* = О, то среди оптимальных стратегий игрока 1 имеется чистая стратегия х", для которой Ну{х\0) 0;

3)если О у* 1, го среди оптимальных стратегий игрока 1 найдется такая, которая является смесью двух существенных стратегий х и х". Для этих стратегий

Н;{х\у*)<0, Н;{х",у*)0.

При этом стратегии х и х" употребляются с вероятностями а и i - а, где а находится из уравнения

аЯ;(х,/*) + (1 -а)Н;(х",у*) = 0.(14.6)

Доказательство. Пусть сначала = 1. Тогда по лемме п. 14.2 найдется существенная стратегия х игрока 1, для которой выполняется (14.2). Следовательно, вблизи у* = I функция Я(х, у) убывает. Но выпуклая функция не может переходить от возрастания к убьюанию. Поэтому Н(х, у) убьюает на всем сегменте [О, 1], достигая при у = 1 своего минимума. Это значит, что

Н(х,у)<Н(х\у) при всех >G[0,1].(14.7)

С другой стороны, из существенности х следует неравенство

Н{х,х*)Я(х,у) при всех xG[0,1].(14.8)

Неравенства (14.7) и (14.8) означают, что (х, у*) есть седловая точка, и случай 1) разобран.

Случай 2) разбирается при помощи симметричных рассуждений.

Перейдем к случаю 3). Здесь мы на основании следствия п. 14.4 располагаем существенными стратегиями х и х\ которые удовлетворяют соответственно неравенствам (14.4) и (14.5).

Рассмотрим функцию

т=т;{х,у*)+{1 -)пу(х",у*).

Неравенства (14.4) и (14.5) означают, что /(0) 0, /(1) 0. Так как функция / непрерьшна (в данном случае она просто линейна), найдутся такие а* G [О, 1 ], что Да*) = 0.

Возьмем теперь смешанную стратегию игрока 1, состоящую в выборе стратегии х с вероятностью а* и стратегии х" с вероятностью 1 - а*, и обозначим ее через X*.



По лемме п. 12.9

Н(Х\у)а*Н(х\у)-ь(1 -а*)Н(х\у)

является выпуклой по у функцией. Ее производная по > в точке у = у* равна

я; (X *, J) = а*н; (х\ у)(1- а*)Н; (х\ у) = 0.

Следовательно, в точке у* функцияЯ(Х* у) имеет экстремум; ввиду вьшуклости фунюхии этот экстремум должен быть минимумом. Таким образом,

Н(Х\y*)SЩХ*,у) при всех j G [0,1 ].(14.9)

С другой стороны, в силу существенности стратегии х

ЩХ\у*)= Щх\ j;*) = иг = maxЩх,у* )Я(х, у*) при всех х G [0,1 ].

(14.10)

Соотношения (14.9) и (14.10) означают, что ситуация {Х*,у*) является равновесной, а стратегияX* - оптимальной. □

§ 15. СТРОГО ВЫПУКЛЫЕ ИГРЫ

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

15.2.Теорема. В строго выпуклой игре Г игрок 2 имеет единственную оптимальную стратегию, которая является чистой.

Доказательство. Пусть X* - оптимальная стратегия игрока 1 и lJy)=ЩX\y).

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

ф(у*) = тш ij(y)VY.

Но на основании леммы п. 12.10 функция \[/(у) является строго выпуклой, а по следствию 3) из п. 12.4 ее минимум единствен (обозначим его через у*). Поэтому спектр всякой оптимальной стратегии игрока 2 исчер-пьюается точкой >*. Это значит, что кроме у* игрок 2 никаких оптимальных стратегий не имеет. □

§ 16. ОБЩАЯ СХЕМА РЕШЕНИЯ ВЫПУКЛЫХ ИГР НА ЕДИНИЧНОМ КВАДРАТЕ. ПРИМЕРЫ

16.1. На основе сказанного в § § 13 и 14 решения вьшуклых игр естественно находить по схеме, состоящей из следующих пунктов. 1 °. Проверка фуньсции Щх, ) на вьшуклость.

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

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

[Старт] [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]