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


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


24

Анализ игры такого вида сходен с проведенным в предыдущем параграфе анализом 2Х «-игр.

Произвольная смешанная стратегия игрока 2 имеет здесь вид F = (??, 1 - 77), и их множество можно описать сегментом [О, 1] •

Если игрок 1 выбирает свою /-ю чистую стратегию, а игрок 2 - смешанную стратегию Y, то выигрыш игрока 1 будет, очевидно, равен Af. = ацГ1-У (1 - г?). Зависимость этого выигрыша от ?7 графически описывается прямой линией. Графиком

шах Af. Y = max (ац г? + ai2 (1 - ??)) /i

будет верхняя огибающая всех прямых, соответствующих чистым стратегиям игрока 1 (рис. 1.22). Абсциссой нижней точки этой ломаной будет значение т?*, соответствующее оптимальной стратегии игрока 2, а ординатой - значение игры .

20.2. Графоаналитический способ, подобный описанному, можно применить к решению игр, в которых один из игроков имеет три чистые стратегии. Однако получающиеся при этом построения оказываются весьма громоздкими. Для их проведения необходимо пользоваться методами начертательной геометрии.

Если каждый из игроков имеет более трех чистых стратегий, то графоаналитическое решение игры практически невозможно.

§ 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ 3 X 3-ИГР

21.1.3 X 3-игры встречаются во многих вопросах. Поэтому умение их решать, притом без обращения к общим методикам (например, к симплекс-методу линейного программирования, о возможности использования которого см. в § 26) и, тем более, к вычислительной технике, представляется важным. Разумеется, такой подробный анализ, которому бьши в § 18 подвергуты 2 X 2-игры, здесь оказьшается практически неосуществимым ввиду обилия и разнообразия могущих встретиться случаев. Поэтому мы ограничимся описанием способа решения такой игры, не доводя его до расчетных формул, к которым он приводит в каждой из своих реализаций.

Итак, пусть нам дана игра с 3 X 3-матрицей выигрышей А. В основу ее решения мы положим следующие соображения.

21.2.Прежде всего, как это уже неоднократно отмечалось, для значения всякой матричной игры Г должно быть

v. = max min Х4./,(21.1)

X f

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

В нашем случае Xявляется вектором вида (j, 2. 3) где

1,2.3 0,(21.2)

1 +3 =1-(21.3)

Обозначим множество всех таких векторов через X (см. п. 8.2). Тогда равенство



(21.1) можно переписать в виде X4.l

Х4.2 Х4.3)

= max minUi,2 +222 +332 Ji" G X

113 гзз +333

(21.5) (21.6) (21.7)

Рассмотрим теперь равенства Х4.1 =Х4.2, Х4.2 =Х4.з, Х4.3 =Х4.1.

Каждое из них в условиях (21.3) является либо тождеством, либо уравнением прямой, разбивающей плоскость (21.3) на две полуплоскости, в каждой из которых одна из сравниваемых линейных форм принимает большие значения, чем другая. Осуществив все такие разбиения плоскости (21.3) и произведя сравнения значений форм на соответствующих полуплоскостях, мы можем описать области плоскости, на которых меньшее значение оказывается у данной формы (т.е. у первой, второй или третьей) или одновременно у нескольких данных форм. Обозначим область, в которой минимальные значения будут у формы xA.j% через Жf.

Это значит, что мы полагаем

min XA.j = f= 1, 2, 3

XA.i для Xg X4.2 для XG2. Х4.3 для XG 3.

Вообще говоря, среди множествЖ, могут быть совпадаюище, а также

пустые.

Если система уравнений (21.3), (21.5), (21.6) (уравнение (21.7), очевидно, является следствием двух предьщущих) имеет единственное решение, то области , и Ж имеют вид згглов (рис. 1.23). Если же эта система имеет бесконечное множество решений, то области принимают вид полос и полуплоскостей (рис. 1.24).

Применяя введенные обозначения, мы можем переписать (21.1), или, что то же самое, (21.4), в виде

v - max min XA.j = XGX /=1,2,3

= max{ max X4.i, max X4.2, XGjflXхжх

max E n X

ХЛ.3}.

(21.8)

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

Рис. 1.23

Рис. 1.24



Но максимум линейной формы на любом выпуклом многограннике, и в том числе на отрезке, треугольнике или выпуклом четырехугольнике, должен достигаться на его вершине (это утверждение известно из линейного программирования и широко применяется там; фактически оно равносильно опирающейся на лемму о переходе к смешанным стратегиям из п. 9.4 лемме из п. 10.2). Поэтому для нахождения максимума в (21.8) достаточно найти вершины многоугольников п X, вычислить в них значения соответствующей формы XA.j и сравнить эти значения между собой.

Вершины же каждого многоугольника Ж j п X суть либо вершины X, принадлежащие у, либо вершина«у (если она есть), принадлежащая X, либо же точки пересечения сторонку со сторонами X. Все эти точки могут быть без труда перечислены.

Вершинами треугольника X являются точки 1 = (1, О, 0), 2 = (О, 1, 0), J = (0,0,1). Принадлежность той или иной точки X из их числа данному множеству Ж проверяется без труда путем установления того, что XA.j - наименьшее число среди X4.i, ХА.2 и Х4.3 (и во всяком случае, не большее, чем остальные).

Далее, если одно из множеств Жj имеет вершину, то мы имеем дело со случаем, изображенным на рис. 1.23. При этом все множества Жj должны иметь общую и притом единственную вершину. Принадлежность ее множеству X устанавливается проверкой соблюдения для ее координат уравнений (21.2) и (21.3).

Наконец, уравнение стороны Жj имеет вид

=Х4.у,(21.9)

а уравнение стороны X

/ = 0.(21.10)

Комбинируя все уравнения вида (21.9) с уравнениями (21.10) и учитывая условия (21.2) и (21.3), мы можем найти все точки и этого типа.

Как видно из рис. 1.23 и 1.24, наибольшее число точек, в которых придется фактически вычислять и сравнивать значения линейных форм, равно семи. Общее число комбинаторно различных вариантов оказьшается здесь весьма большим. Мы не будем их перечислять.

21.4.После того как значение игры найдено, нахождение оптимальных стратегий игрока 2 не представляет большого труда. Именно, для этого нужно найти те значения вектора У = (rj, , rjg ), которые удовлетворяют обычным соотношениям:

Tji,rJ2,r?3 О,(21.11)

г1г+П,+щ=1• *(21.12)

(множество всех таких векторов составляет треугольник, который мы обозначим через Y) и для которых

max Л/. Г = г;(21.13)

г-1,2,3

С этой целью достаточно найти областии5з плоскости (21.12), на кото-

рых из трех форм А(,У наибольшее значение принимает соответственно форма А J. У-, Л2- или A.y, и определить пересечение каждой из этих областей с треугольником.

Точки этого пересечения и составляют множество оптимальных стратегий игрока 2.

21.5.Разумеется, при фактическом нахождении значения игры и оптимальных стратегий игроков в ней по описанному выше способу может возникать большое число возможностей сократить и упростить рассуждения и вычисления. Перечислять здесь эти возможности едва ли целесообразно.

21.6.Пример. Пусть

Уравнение (21.5) в данном случае имеет вид

или 2 =3. 74

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