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


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


49

Поэтому разумное, минимаксное поведение игрока 2 в простой игре должно состоять в наиболее редких укладках v-сечений в множестве \ стратегий игрока 1.

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

Определение. Пусть к - целое положительное число. Семейство подмножеств множества у называется покрытием кратности к множества у, если каждая стратегия j G у входит не менее чем в к множеств из числа У . Семейство Й7 подмножеств хпгзьтаетсяукладкой кратности к в множестве х, если каждая стратегия х G х входит не более чем в к множеств из £С .

Ясно, что всякое покрытие является вместе с тем покрытием любой меньшей кратности, а всякая укладка - укладкой любой большей кратности. Поэтому мы далее под кратностью покрытия будем понимать его наибольшую кратность, а под кратностью укладки - ее наименьшую кратность.

Покрытия кратности 1 называются просто покрытиями, а укладки кратности 1 - просто укладками.

Если X * С X и семейство х-сечений Zp, соответствующих стратегиям из х* составляет покрытие у кратности к, то будем говорить, что х* порождает покрытие у кратности к. Аналогично, если у* Су и семейство у-сечений, соответствуюпщх стратегиям Jy*, составляет укладку в х кратности , то будем говорить, что у* порождает укладку в х кратности к. □

§ 28. ОЦЕНКИ ЗНАЧЕНИЙ ПРОСТОЙ ИГРЫ

28.1.Через множества стратегий, порождающих кратные покрытия в у и кратные укладки в х, можно оценивать верхнее и нижнее значения простой игры Г = < X, у, Z >. Эти множества связаны также со спектрами оптимальных стратегий игроков.

28.2.Теорема. Если для простой игры Г = < х, у, z > ex существует г-элементное множество, порождающее покрытие у кратности к, то Vy kjr.

Доказательство. Пусть множество {Х\, . . . ,х} порождает покрытие у кратности к. Возьмем стратегию X* GX, для которой Х*(Х/) -= 1/г при каждом i = I,. . . ,г. Для любого у Еу мы тогда имеем

И(Х\у) = - Z Н(х,,у), г / = 1

(28.1)



Ввиду того, что мы имеем дело с покрытием у кратности к, стратегия у принадлежит не менее чем к множествам из числа ylx/. Поэтому хотя бы для к из соответствующих значений i должно быть Я(х/, у) = 1, а остальные слагаемые в сумме из (28.1) неотрицательны. Значит,

H(X*,y)klr.(28.2)

Отсюда сразу получается, что

и Р = sup inf Н(Х, у) к/г

X у

28.3.Двойственным к доказанной теореме можно считать следующее утверждение.

Теорема. Если в у существует s-элементное подмножество, порождающее укладку в X кратности к, гоТУр kjs.

Доказател ьство. Пусть множество{уi, • , у} порождает укладку в Xкратности к. Возьмем стратегию У*, для которой Y*{yj) = Ijs при любом / = 1,... , 5. Тогда для любого х G х мы имеем

Я(х, Г)=- Z H{x,yj),(28.3)

5 / = 1

Здесь мы имеем дело с уютадкой кратности к. Поэтому любая стратегиях может принадлежать не более чем к из множеств х у/, так что в сумме из (28.3) отличными от нуля могут быть не более к слагаемых. Поэтому

Я(х, Y*)<kls.(28.4)

Отсюда следует, что

Up = inf sup Я(х. Y) kis, □

у X

28.4.Объединение утверждений двух последних теорем дает нам следующее следствие.

Следствие. Если для игры Г одновременно в х существует п-эле-ментное подмножество х*, порождающее покрытие у кратности к, а в у -п-элементное подмножество у*, порождающее в х укладку кратности к, то игра Г имеет значение, равное к/п, а смешанные стратегии X* и Y*, для которых соответственно элементы из х* и у* выбираются с равными вероятностями 1/п, являются оптимальными.

Доказательство. То, что j;p = = TJp = к/п, непосредственно следует из теорем пп. 28.2 и 28.3. Далее, полагая в (28.2) г = п, мы получаем Я(Х*, у) >Д:/п при любому G у, а полагая в (27.5) s = n,H(x, Y*) к/п при любомX G X, откуда требуемое вытекает немедленно.

28.5.Анализ обширного класса примеров простых игр сводится к использованию следующей теоремы.

Теорема. Пусть для простой игры Г = < х, у, Я > = < х, у, z > в у существует счетное подмножество, порождающее укладку в х. Тогда Up = О, и всякая.стратегия игрока 1 является оптимальной.

Если, кроме того, в х существует счетное подмножество, порождающее покрытие у, то игрок 2 не имеет оптимальных стратегий (хотя и имеет е-оптимальные стратегии при любом е > 0).



Доказательство. Пусть счетное множество{у1,У2,- - -}порождает укладку в X. Возьмем произвольно YGYc supp Y = {yi, у2, ...) .Ясно, что для любого xGx должно быть

Y(yk), если xGxlyf,,.

(20 .bj

Н(х, Г) =

Ов противном случае.

Выберем такое А:*, что max= Y{y*), и возьмем х х \ Ук*

Тогда из (28.5) следует, что для любого xGx

Н(х, Y) Y(y.) = H(xj,,Y), и поэтому

5ирЯ(х, Y)=H(x,,Y),

При данной уютадке мы можем найти смешанную стратегию Y, для которой max Y(yj) будет сколь угодно малым положительным числом. Следовательно, по (28.5) должно быть

Vr = inf 8ирЯ(л:, Г) = 0. у X

Из неотрицательности значений функции выигрыша игры Г мы получаем, что j;p = Up = О . Далее, из

Up = sup inf Н(Х,у)=0

X у

следует, что inf ЩХ, у) = 0 при любой стратегии X, которая тем самым

оказьшается оптимальной.

Пусть теперь счетное множество {дгь Ха, . . .}порождает покрытие у. Возьмем произвольную смешанную стратегию У игрока 2. Очевидно, найдется такое Хп, что

У(уи„) = Я(х„,Г)>0.

Значит, sup Я(х, F)>0 = Up, т.е. стратегия Т не является оптимальной.

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

§ 29. ПРИМЕРЫ ПЮСТЫХ ИГР

29.1.Далее мы будем рассматривать простые игры на единичном квадрате или хотя бы изображать их в таком виде. Это позволит нам широко пользоваться геометрическими представлениями.

29.2.Пусть множество zp таково, что для некоторого Xq ех будет уХо = у (рис. 2.11). Тогда уже взятая в единственном числе стратегия Xq порождает покрытие у, и по теореме п. 28.2 должно быть up 1. Отсюда следует, что up = 1, а стратегия Хо игрока 1 оказьшается его чистой оптимальной стратегией. Игроку 2 при этом ничего не остается делать, как выбирать произвольную стратегию и потфять единицу. Таким образом, произвольная его стратегия является оптимальной.

29.3.Следующий пример как бы двойствен предьщущему. Пусть множество zp таково что некоторое G у не принадлежит ни одному >-сечению zp (рис. 2.12). Это

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