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


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


25

Рис. 1.25

Рис. 1.26

Аналогично уравнение (21.6) записывается как т.е. 22 =1-

Наконец, из уравнения (21.7), которое оказьшается следствием двух предьщущих, следует, что j = 2 з.

Значит, областибудут выглядеть так, как это изображено на рис. 1.25

(здесь точка О имеет координаты (1/2, 1/4, 1/4)). Вычисление значений формы Х4. j в точках 1у 2и О дает нам

(1,0. 0) (1,0, 2)=1,

(0,1,0) (1,0, 2) = 0,

(1/2, 1/4, 1/4) (1,0, 2)-1,

а вычисление значения формы Х4.2 в точке 3-

(0, О, 1) (1,2, 0)=1.

Значит, именно векторы (1, О, 0) и (1/2, 1/4, 1/4) являются оптимальными стратегиями игрока 1. Следовательно, на основании сказанного в предьщущем параграфе множество всех оптимальных стратегий игрока 1 есть отрезок, соединяющий соответствующие точки i и 0. Значение игры равно 1.

Обратимся к нахождению оптимальных стратегий игрока 2. Приравнивание соответствующих линейных форм дает нам сначала

1. r = rj, ч-г?2 +2щ =2г?2 =2.y,

откуда I + 17з = 2г?2; далее

А2.У = 2щ =2щ =Аз,¥,

так что - rjj; наконец, изА.У-А» следует 1 +173 = 2?7,.

Значит, области , 1 и £3 имеют вид, изображенный на рис. 1.26. Здесь

6= (2/3,0, 1/3),(0,2/3, 1/3),W= (1/3, 1/2,0).

Вычисление в точках U, V и W значений формы Л j. У дает нам

(1, 1, 2) (2/3, О, 1 /3) = 4/3, (1, 1, 2) (О; 2/3, 1/3) = 4/3,

(1, 1, 2) (1/2, 1/2, 0) = 1,(I, 1, 2) (О, О, 1) = 2,

а вычисляя в точках 2 и 1 соответствеьшо значения форм А2-У и А-У, получаем (О, 2, 0) (О, 1,0)= 2,(2, О, 0) (1, О, 0) = 2.

Таким образом, единственной оптимальной стратегией игрока 2 оказывается точка W= (1/2, 1/2, 0).



§ 22. ДОМИНИЮВАНИЕ СТРАТЕГИЙ

22.1.Из сказанного выше видно, что с ростом формата матричной игры весьма резко возрастает сложность анализа игры и трудоемкость ее решения. Поэтому любые приемы, позволяющие сводить решение игры к решению другой игры, меньшего формата, представляются весьма полезными. Если выражаться более точно, то здесь, говоря о "сведении", мы имеем в виду две задачи. Во-первых, более легкую: построить по игре такую ее подыгру что (А) С (А), а, во-вторых, - более трудную: построить по игре такую ее подыгру s что (А) = (А). При этом в обоих случаях, в соответствии со сказанным в п. 8.5, мы отождествляем смешанные стратегии игроков в подыгре Гд со смешанными стратегиями этих игроков в игре , получаемыми из стратегий в игре путем надлежащего их пополнения нулевыми компонентами.

Одна из возможностей такой редукции игр основана на двух вариантах понятия доминирования стратегий.

Определение. Говорят, что в матричной игре 1 стратегия X* игрока 1 доминирует его стратегию х" (г стратегия X" доминируется стратегией х), если для любой чистой стратегии/ игрока 2 XA.jX "A,j.

Аналогично, стратегия Уигрока 2 доминирует его стратегию У", если для любой чистой стратегии / игрока 1 А(. У S г- У"-

В частности, чистая стратегия V игрока 1 доминирует его чистую стратегиюесли для любого/ aijafj, а чистая стратегия/и игрока 2 доминирует его чистую стратегию/ если для любого / д/у < д ». □

Обратим внимание на то, что отношение доминирования касается стратегий одного и того же игрока, а доминирования стратегий игрока 1 и игрока 2 находятся в отношении двойственности для антагонистических игр (ср. п. 5.4). Далее мы будем для определенности говорить, как правило, о доминировании стратегий игрока 1.

22.2.Игроки могут не употреблять в играх своих доминируемых стратегий. Точный смысл этого высказывания содержится в следующих утверждениях.

Теорема. Если в игре стратегия одного из игроков х доминирует его стратегию х\ и стратегия х" оптимальна, то стратегия х также оптимальна.

Доказательство В соответствии с соображениями двойственности пусть речь идет об игроке 1. В силу доминирования, указанного в условии, мы имеем

X"A.jS.XA.j прилюбом / = !,...,«,(22.1)

откуда

min X"A.j< mm Г A.J.(22.2)

Но в силу оптимальности Х" должно быть (теорема п. 15.1) min X*A,j=va-

Значит, по (22.2) и minX A.j, т.е. стратегия Хявляется оптимальной. □

22.3.В применении к чистым стратегиям неупотребление доминируемых стратегий может означать следующее.



Теорема. Если чистая стратегия Iq игрока доминируется его (чистой или смешанной) стратегией X (отличной от /о)> то существует оптимальная стратегия Х этого игрока, в которую Iq входит с нулевой вероятностью.

Доказательство. Как и выше, ограничимся рассмотрением стратегий игрока 1. Пусть Х= (Ь, • •, Составим вектор Х= .. ., ),

при г Фгоу

(22.3)

о при i -io. Очевидно, / 0 для всех /, и

1=11Ф1 -io~io о

так что вектор является смешанной стратегией игрока 1. При этом /о suppX.

Предусмотренное условиями теоремы доминирование означает XA.j ajj при любом /, что можно переписать как

i-11= 1

Отбрасывая теперь справа и слева общее слагаемое iatj и деля обе части получаемого неравенства на (положительное!) число 1 - 5/, имеем

2 \ац=Ъ atjatj при любом,/,(22.4)

11 о/=1

т.е. aij XA.j при любом/. Это и означает, что X* доминирует стратегию

/о- Далее, согласно лемме о переходе к смешанным стратегиям отсюда получается

Ai.YXAY при любом yGy.(22.5)

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

ледняя по существу является стратегией игрока 1 в (х\го)-подыгре Г = = игры . Возьмем (X*,Y) eS (А). Это значит, что

Af.Y-<X*ATYuX*A.j пщвсехг Ф1о и/Gy.(22.6)

Обозначим через X стратегию игрока 1 в игре Г, получаемую изХотбрасы-ванием ее нулевой io-й компонеты. Из (22.6) следует, что

XAY£X*AY£X*A.j привсех/ G у.(22.7)

Так как векторы X и X отличаются только лишней нулевой компонентой у X, соотношение (22.6) можно переписать как

Л,..У ХМГХ*Л.у привсех (Ф1о и/Gy.(22.8)

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