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


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


26

Аналогично, учитывая (22.5), мы можем (22.7) переписать как

Ai.YXAY = XAYSX*AYX*A.jnpH J G у.(22.9)

Наконец, объединение (22.8) и (22.9) дает нам (X*, Г) её (Г). Оптимальная стратегия Xявляется искомой. □

22.4. Следствие. Пусть чистая стратегия Iq игрока 1 в игре Гд доминируется некоторой его стратегией X, отличной от io,A - матрица, получаемая из А отбрасыванием ее стороки Iq, и XG (А), Тогда стра-

тегия Ху получаемая из X вставлением нуля на место Iq-u компоненты, принадлежит % {А), Кроме того, -а-

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

Доказательство. Из теоремы п. 22.3 следует, что в игре Гд у игрока 1 существует отптимальная стратегия Х, спектр которой не содержит стратегии io. Для нее

min XA.j = va.(22.10)

Эту стратегию можно рассматривать также как смешанную стратегию игрока 1 в игре Га (ср. п. 22.1), и для нее, как и для любой его стратегии, должно быть

minXA.jv .(22.11)

Вместе с (22,10) это дает нам Sva- Но согласно п. 16.11 должно быть ии, так что в действительности Va=Va, и в соотношении (22.11) оказывается равенство. Значит,

min XA.f = min XA.j = ijf = ,

откуда xe8 (А).П

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

23.1.Перейдем к рассмотрению второй из сформулированных в п. 22.1 задач.

Определение. В матричной игре с матрицей выигрышей А стратегия X игрока 1 строго доминирует его стратегию Х" (а стратегия сгро го доминируется стратегией X), если для любого /Gy XA.j >X"A,f.

Стратегия игрока 2 строго доминирует его стратегию Y[ если для любого / exAi.Y<Ai,Y[

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

Анализ строгого доминирования стратегий игроков оказывается проще проведенного в предьщущем параграфе анализа их (нестрогого) доминирования.

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



Теорема. Если в игре стратегия Х" одного из игроков строго доминируется его стратегией Х\ то стратегия Х" не может быть оптимальной.

Доказательство. Будем снова говорить о стратегиях игрока 1. Предусмотренное условиями теоремы строгое доминирование стратегий означает, что Х" >1.у <XA,j при любом/ G у, откуда (ср. п. 3.2)

min X " A.j < min XAj <Va ,

и стратегия X" не может быть оптимальной. □

23.3.Теорема. Если чистая стратегия io игрока строго доминируется в игре Га (чистой или смешанной) стратегией X, то для любой оптимальной стратегии X*=(i,...,) этого игрока должно быть = 0.

Доказательство. Пусть X и /о - стратегии игрока 1. Из условия доминирования при любом / должно быть aij <XA.j: Возьмем какую-нибудь оптимальную стратегию Y * игрока 2 и перейдем в написанном неравенстве к смешанным стратегиям:

Ai,Y*<XAY*.(23.1)

Из оптимальности F* следует, что ХА F*i; , что вместе с (23.1) дает Af.Y < Va у и нам остается сослаться на теорему п. 17.2 о дополняющей нежесткости. □

23.4.Следствие. Пусть чистая стратегия i игрока 1 в игре строго доминируется некоторой его стратегией, а А -матрица, получаемая из А отбрасыванием ее строки Af.. Тогда 8 (А)-8 (А ).

Доказательство. По последней теореме каждая стратегия из § (А) не содержит в своем спектре стратегии /. Поэтому ее можно рассматривать как стратегию в игре Г. По теореме о независимости от посторонних альтернатив (п. 5.5) она должна принадлежать § (Л). Значит, 8 (А) С 8 (А). Обратное же вютючение бьшо доказано в п. 22.4 даже при более слабом предположении нестрогого доминирования. □

§ 24. ВПОЛНЕ СМЕШАННЫЕ СТРАТЕГИИ

24.1.Как отмечалось, знание спектра оптимальной стратегии существенно облегчает ее нахождение. Далее мы рассмотрим один класс игр, в которых это соображение проявляется наиболее наглядно.

Определение. Стратегия игрока называетя вполне смешанной, если ее спектр состоит из множества всех стратегий игрока.

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

Игра называется вполне смешанной, если каждая ситуация равновесия (седловая точка) в ней является вполне смешанной. □

Хотя в данной главе изучаются лишь антагонистические игры, но данное определение умышленно сформулировано так, чтобы быть применимым к любым бескоалиционным играм,

24.2.Теория вполне смешанных матричных игр в значительной мере исчерпывается следующей теоремой.

Теорема. Пусть в пХп-матричной игре Га матрица выигрышей А является невырожденной.



Тогда, если игрок 2 имеет в вполне смешанную оптимальную стратегию, то игрок 1 имеет в ней единственную оптимальную стратегию X, для которой *)

J„A-

J„A-4l

при этом

(24.1)

(24.2)

Если же в Та вполне смешанную оптимальную стратегию имеет игрок 1, то игрок 2 обладает в ней единственной оптимальной стратегией У, для которой

причем также выполняется (24.2).

Доказательство. В условиях первой части теоремы для оптимальной стратегии X игрока 1 ввиду сушествования вполне смешанной оптимальной стратегии игрока 2 согласно теореме о дополняющей нежесткости должно быть XA.f =Va для всех / = 1,.. .Запишем эту систему равенств в ввде ХА = va Jny откуда ввиду невырожденности матрицы А

XVaJuA.(24.4)

Почленное умножение этого равенства слева надает нам

XJI = VaJ„A-41.(24.5)

Так как X - стратегия, левая часть здесь равна единице. Поскольку тем самым левая часть отлична от нуля, должно быть /„Л" ФО,и из (24.5) мы получаем (24.2).

Подстановка найденного выражения для Va в (24.4) дает нам (24.1).

Вторая часть теоремы доказывается симметрично. □

24.3. В качестве примера рассмотрим игру с диагональной матрицей выигрышей ... О

назьшаемую диагональной игрой.

Диагональную игру можно интерпретировать как следующую игру поиска. Игрок 2 прячет в одном из п мест предмет, причем в /-м месте прячется предмет ценности . №рок 1 производит поиск этого предмета также в одном из мест. Найдя предмет, игрок 1 тем самым вьшгрьшает его ценность, а не найдя - не получает ничего.

24.4. Матрица вьшгрьппей А диагональной игры Г, очевидно, является невырожденной. Для нее

а: О ... О

А- =

(24.6)

*) Здесь, как и всюду (см. п. 8.3), Jn есть Аьмерный вектор, каждая компонента которого равна единице. 80

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