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


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


38

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

Все сказанное дает нам право говорить о двойном интеграле (9.3). Оба повторных интеграла (9.1) и (9.2) оказьшаются равными этому двойному интегралу (это составляет содержание известной теоремы Фубини). Общее значение всех этих трех интегралов естественно обозначать через Н{Х, У).

9.6.Определение. Если Г = (х, у, Я) - антагонистическая игра,

то ее смешанным расширением назьшается антагонистическая игра Г = = < X, Y, Я), где X и Y - множества смешанных стратегий игроков в игре Г, а значения Н{Х, Y) определяются как общее значение интегралов (9.1), (9.2) и (9.3). □

9.7.На множествах X и Y стратегий игроков в смешанном расширении

Г = < X, У, Я) антагонистической игры Г = < х, у. Я) можно согласно сказанному в п. 6.1 ввести естественную метрику, положив для Xi, Хг G X

p,(Xb2) = sup \H{XuY)-H{X2.Y)\

идля Ух, Г2

Р2(У1,Г2)= sup \H{X,Y,)-H{X,Y2)l

Оказьшается что если исходная играТ = < х, у, Я> компактна, то ее

смешанное расширение Г = < X, ¥,Я> также компактно.

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

Кроме того, оказывается***), что если функция Я( j) непрерывна, а последовательность Хь Хг, ..., Х„, ... смешанных стратегий игрока 1 сходится к некоторой предельной стратегии Xq, то при любом> G Y

lim Я(Х„,)=Я(Хо,).(9.4)

Аналогичный предельный переход имеет место для сходящихся смешанных стратегий игрока 2.

9.8.Заметим, наконец, что множество всех смешанных стратегий игрока 1 в произвольной антагонистической игре является, как и в матричной

*) в действительности достаточно существенно более слабого предположения о сепарабельности пространств х и у. (Напомним, что топологаческое пространство назьшается сепарабельным, если оно содержит счетное всюду плотное подмножество. То, что всякое вполне ограниченное, а тем более компактное пространство сепарабель-но, вытекает непосредственно из определений.)

**) Доказательство см. в монографии А. Валвда "Статистические решающие функции" (русск. пер. в кн. "Позищюнные игры" М., "Мир", 1967, с. 367). В основе этого доказательства лежат рассуждения, известные для случая х = у = R как первая теорема Хелли (см., например, учебник Б.В. Гнеденко "Курс теории вероятностей", М,, Гос-техиздат 1961, с. 234).

***) В основе этого доказательства лежат рассуждения, известные для случаях = у = = R как вторая теорема Хелли (см. тот же учебник Б.В. Гнеденко, с. 236).



игре, выпуклым, т.е. любым двум смешанным стратегиямХиХ" игрока 1 и числу \ G [О, 1] можно поставить в соответствие его смешанную стратегию Хх = хх + (1 - Х)Х", для которой при любом борелевском множестве х С х чистых стратегий игрока 1 имеет место

Х;,(х) = ХХ(х) + (1-Х)Х"(х).

Из определения интеграла Лебега - Стилтьеса (см. п. 9.3) немедленно следует, что при любой чистой стратегии > игрока 2 вьшолняется

Я(Хх, у) = ХЯ(Х>) + (1 - Х)Я(Х у).

Аналогичны двойственные рассуждения о выпуклости множества смешанных стратегий игрока 2.

§ 10. ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКОВ В КОМПАКТНЫХ ИГРАХ

10.1. Теперь мы можем доказать теорему, анонсированную в конце п.9.1.

Теорема ("о сновная теорема" теории компактных игр). В компактной игре игроки имеют смешанные оптимальные стратегии.

Доказательство. Пусть Г = < х, у, Я > - компактная игра. Она является вполне ограниченной, и потому, на основании сказанного в п. 8.1, при любом 6 > О в ней имеются ситуации 6-равновесия в смешанных стратегиях. В частности, отсюда следует, что игра Г имеет значение .

Возьмем сходящуюся к нулю убьшающую последовательность 6i > ег > >... >б„>... >0и найдем по каждому w = 1, 2, ... б„-седловую точку (Х„,Г„).

Согласно части 1 теоремы из § 3 (формула (3.1))

шГЯ(Х„,У) + 2€„1;г, у

так что при любой чистой стратегии у игрока 2

Я(Х„,>;) + 2е„1;г.00.1)

Ввиду указанной в п. 9.7 компактности множества X смешанных стратегий, из последовательности

Х„Х„...(10.2)

можно выбрать подпоследовательность, сходящуюся к некоторой стратегии (функции распределения) Xq, Не нарушая общности, можно считать, что (10.2) уже является выбранной подпоследовательностью. Перейдем теперь в (10.1) к пределу:

lim Я(Х„,>)+ lim 2б„>Уг.

Согласно формуле (9.3) первый из этах пределов естьЯ(Хо, у), а второй, очевидно, равен нулю. Таким образом, при любом G Y оказьюается Я(Хо, у) Vy. Следовательно, по теореме п. 5.5 Хо есть оптимальная стратегия игрока 1 в рассматриваемой игре.

Симметричные рассуждения приводят к доказательству существования оптамальной стратегии у игрока 2. □

8*115



10.2.Сделаем к сказанному комментарий, аналогичный сделанному в п. 8.3.

Нахождение оптимальной стратегии в компактной игре Г распадается на 3 этапа:

1)построение в множествах стратешй игроков в игре Г е-сетейиз (8.1) для "исчезающей" последовательности значений е„ i О и составление соответствующих матричньгх игр из (8.2);

2)решение матричных игр Г, состоящее в нахождении седловых точек (Xg, Y) в них;

3)вьщеление сходящихся подпоследовательностей из последовательностей Х(е I 0) и Y(e i 0) и нахождение их пределов.

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

10.3.Заметим в связи со сказанным, что множество всех (смешанных) оптимапьных стратегий каждого из игроков в компактной антагонистической игре является вьшуклым (см. п. 16.1 гл. 1) и замкнутым в смысле естественной топологии.

Действительно, если Х* и Х2 - две оптимальные ctparernn в игре Г = = < X, у, Я >, то для них имеют место неравенства вида (5.9) :

Я(Х;,;;)1;г,(10.3)

Я(Х;,;;)ч;г(10.4)

при любой стратегии j G Y. Возьмем произвольно X G [О, 1 ] и положим Xx = Xi +(1 - Х)Х2. Тогда из (10.3) и (10.4) будет следовать

Н{Х,у) = Ш(Х:,у) + (1 -\)H{Xly)v

при любом> G у, а это и означает оптимальность стратегии Хх-

Замкнутость множества всех оптимальных стратегий вытекает из непрерывности функции Я в естественной топологии (см. формулу (9.4). □

§ 11. ВНЕШНЯЯ ТОПОЛОГИЯ. НЕПРЕРЫВНЫЕ КОМПАКТНЫЕ ИГРЫ

11.1. Помимо описанной в § 6 внутренней (естественной) топологии, порождаемой на пространствах стратегий игроков функцией вьшгрыша, на этих множествах может быть (через метрику или как-либо иначе) априори определена еще и некоторая исходная, внешняя по отношению к игре топологая. Множество ситуаций оказьшается в этом случае декартовым произведешем топологических пространств и тем самым - тоже топологическим пространством. Наличие у функции вьшгрыша тех или иных топологических свойств (например, непрерьшности) может предопределять некоторые полезные особенности внутренней топологии. Это обстоятельство представляется важным потому, что свойства внешней топологии обнаруживаются более непосредственным образом, чем свойства топологии внутренней (ср. примеры из п. 6.3).

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