§ 18. 2 X 2-ИГРЫ

л- Г11 й121.

L «2 1 «22 J

Пусть X — произвольная смешанная стратегия игрока 1 (в частности, эта стратегия может быть и чистой). Если ? — вероятность выбора игроком 1

своей первой чистой стратегии в условиях X, то вероятность выбора им вто&рой стратегии есть 1 — ?. Поэтому стратегию X можно представить в виде (?, 1 — ?). Аналогично, если Y — произвольная смешанная стратегия игро&ка 2, то она имеет вид (77, 1 — rj). Таким образом, стратегия X однозначно определяется числом а стратегия Y — числом rj. Чистым стратегиям соот&ветствуют, очевидно, значения параметров 0 и 1. Мы будем в соответствии со сказанным обозначать ситуацию (X, Y) парой чисел (?, т?).

Геометрически всякую ситуацию (?0> ^о) в смешанных стратегиях та&кой игры можно понимать как точку на единичном квадрате (рис. 1.9). Ситуациям в чистых стратегиях соответствуют вершины этого квадрата.

2. Ситуация (X, Y) является седловой точкой в игре Г^, если она приемлема для каждого из игроков. Поэтому для описания всех седловых точек в игре мы опишем множества ситуаций, приемлемых для отдельных игроков, и изобразим их на единичном квадрате всех ситуаций. Пересече&ние двух этих множеств и будет составлять множество всех седловых точек игры.
3. Займемся описанием ситуаций, приемлемых для игрока 1 в 2 X 2-игре ТА.

Приемлемость ситуации (X, Y) для игрока 1 в 2 X 2-игре Г^ означает (например, в силу леммы о переходе к смешанным стратегиям), что

AXJT SXAYT,              (18.2)

A2Yt ^XAYt.              (18.3)

Положим X = (?, 1 — ?) и рассмотрим отдельно три случая.

а) ? = 1.

для игрока 1 оказывается неравенство (18.3). Это можно записать как

A1.Yt^A2.Yt.              (18.4)

б)              % = 0. Здесь 1 — % > 0, так что в тождественное равенство обращает&ся (18.3), и условием приемлемости ситуации (X, У) оказывается (18.2) или, что то же самое,

AuYt^A2Jt.              (18.5)

в)              0< $ < 1. В этом случае как ? > 0, так и 1 - ? > 0. Поэтому по тео&реме п. 17.3 о дополняющей нежесткости оба неравенства (18.2) и (18.3) обращаются в равенства, и условием приемлемости становится

AXJT = A2JT.              (18.6)

18.3. Опишем варианты приемлемости ситуаций в более явном виде. Заметим для этого, что в любой ситуации (X, У) = (?, rj) в смешанных стра&тегиях 2 X 24ігрьі Г^ мы имеем

ац а12 0-2 1 Я22 .

= +?(1 -Т?)Л12 +(1 -f)W2 1 + 0 -0(1              2 =

= Й(«11 -«12 -«21 +«22) + ?(«12 -Л22) + ^7(«21 ~ «2 2 ) + «2 2 • (18.7)

Поэтому соотношения (18.4), (18.5) и (18.6) можно соответственно записать как

г}С >«!,              (18.8)

г?С ^а, ,              (18.9)

т?С =ах,              (18.10) где

С = ац -а12 -а21 +а22 и «1=022-012-              (18.11)

Таким образом, приемлемые для игрока 1 ситуации в игре могут быть одного из трех типов:

(1,7?), где              77С ;>(*!,

(0,7?), где Г]С ^С*!,

(?,77), где г\С = аа ?Є(0,1).

4. Если С = 0, но а! 0, то (18.10) не имеет места, так что выполня&ется либо (18.8), либо (18.9), и притом со знаком строгого неравенства. Поэтому множество всех vдает приемлемые ситуации либо с ? = 1, либо с ? = 0, смотря по тому, какое из чисел окажется больше, — а22 или аХ2.

Если же С = 0 и <*! = 0, то все соотношения (18.8) - (18.10) выполня&ются тождественно, и приемлемыми для игрока 1 будут вообще все си&туации.

Перечисленные случаи изображены на рис.

5. Обратимся к случаю, когда С Ф 0. Тогда из (18.10) следует 77 = = а|/С. Это значение 77 мы далее будем обозначать через 77*. С учетом(18.11)

64

XAY1 = «,1 -?) должно быть

rf =              g22 -ai2              .              (18.12)

«11 -«12 -«2 1 +«22

Тогда перечисленные в п. 17.3 типы приемлемых для игрока 1 ситуаций приобретают следующий вид:

(1,?7), где V^V*, если ОО,              если С< 0;

(0,??), где VSV*, если 00,77^17*, если С< 0;

(?,тГ), где ? Є [0,1 ]. *              (1813)

Если отвлечься от того, что число 77 является вероятностью и поэтому должно принадлежать сегменту [0, I ], то во всех вариантах случая С Ф 0 множества (18.13) составляют трехзвенные зигзаги, а множества при&емлемых для игрока 1 ситуаций суть пересечения этих зигзагов с единич&ным квадратом ситуаций. Возможные случаи изображены на рис. 1.11.

Далее назовем трехзвенный зигзаг левым, если при подходе к его средне&му звену оно будет расположено слева по направлению движения (рис. 1.11 а — д), и правым — в противном случае (рис. 1.11 е - к).

18.6. Описание ситуаций в игре Г4, приемлемых для игрока 2, делает&ся симметрично проведенному в пп. 18.3—18.5 описанию приемлемых си&туаций для игрока 1.

Приемлемость ситуации (X, У) в игре ТА для игрока 2 означает, что

XA.i^XAY7, ХА.2^ХАУг.              (18.14)

Положив У = (77, 1 — 77), мы приходим к рассмотрению трех случаев:

а)              77 = 1. В этом случае приемлемость ситуации (X, У) равносильна неравенству

ХА.^ХА.2.              (18.15)

б)              77 = 0. Приемлемость ситуации (.X, У) для игрока 2 означает, что

ХАЛ^ХА.2.              (18.16)

в)              0 < 77 < 1. Приемлемость ситуации (.X, У) для игрока 2 означает, что

ХА.і =Х4.2.              (18.17)

Согласно (18.7) соотношения (18.15), (18.16) и (18.17) могут быть соответственно переписаны в виде

где число С определяется, как и в (18.11), а а2 =«22 -«21-

Случай С - 0 разбирается так же, как и при рассмотрении ситуаций, приемлемых для игрока 1. В случае С Ф 0 положим ? * = а2/С, т.е.

Г =               *22               .              (18.18)

«11 -«12 "«21 +«22

Приемлемые для игрока 2 ситуации составляют пересечение единичного 5.Н.Н. Воробьев              65

квадрата с зигзагом, состоящим из трех звеньев:

(?, 1), где              если С>0,              если С< 0;

(5,0), где              если ОО,              если С<0;

(Г,г/), где г? Є [0,1] (рис. 1.12).

Обратим внимание на то, что в каждой игре зигзаги, на которых рас&положены приемлемые стратегии игроков, оказьюаются одной и той же ориентации, т.е. являются либо оба правыми, либо оба левыми.

Нам остается воспроизвести рассуждения п. 18.2.

18.7. Заметим, что при СФ 0 и rf Є(0,1) пересечением зигзагов яв&ляется единственная точка с координатами (5*, 17*), которая и будет един&ственной седловой точкой в игре.

мы имеем С = 4 Ф0, (Xj = 3, rj* =

= 3/4, а2 -2 и ?* =1/2. Поэтому зигзаги приемлемых ситуаций имеют

Рис. 1.14

вид, изображенный на рис. 1.13; соответствующая ситуация равновесия — точка их пересечения — единственная.

18.8. В качестве второго примера рассмотрим случай игры ГА с А = 2 0 1

^ ^ . Здесь С = 2Ф0, OLi =1, 7?* = 1/2, а2 = 0, =0. Поэтому

множество всех ситуаций равновесия в этом случае имеет вид отрезка,

(рис. 1.14). 1 2

Здесь С = 0, гірием-

0 1

лемыми для игрока 1 являются все ситуации вида (1,т?), а приемлемыми для игрока 2 — все ситуации вида (1,5)- В игре имеется единственная ситуация равновесия в чистых стратегиях: (1, 1) (рис. 1.15).

18.10. Проведенный анализ дает основания к несколько иному, упрощенному алго&рифму перечисления ситуаций равновесия в 2 X 2-игре, основанному на иной класси&фикации случаев.

Из сказанного выше следует, что таких основных и без труда распознаваемых случаев — два.

1. В игре ГА нет седловых точек в чистых стратегиях. В этом случае игра имеет единственную седловую точку в смешанных стратегиях (X* Y*)= (?*, т?*), где, как и выше, ?* = а2/Си7]*=о:1/С Заметим, что этот факт отражает примечательное свойст&во 2 X 2-игр: если в такой игре один из игроков имеет чистую оптимальную стратегию, то другой игрок тоже имеет чистую оптимальную стратегию.

Чтобы не запоминать выражений для С, а, и а2, удобно выводить соответствующие формулы каждый раз заново, пользуясь формулами (18.16) и (18.6), которые явля&ются одной из форм выражения дополняющей нежесгкости и в специальном запомина&нии не нуждаются.

2. В игре ГА есть седловые точки в чистых стратегиях. Пусть для определенности одна из них состоит из первых чистых стратегий игроков. Тогда vA=яп, и по опре&делению седловой точки должно быть а21 < аХ1 ^ д12. Смотря по тому, реализуются в этом соотношении строгие неравенства или точные равенства, нам могут предста&виться четыре варианта рассуждений.

а)              а21 < ап К д12.'Здесь для первой чистой стратегии игрока 2, которая по усло&вию оптимальна, мы имеем а21 -A2.YT < аХ1 -vA. Значит, по теореме п. 17.3 о дополняющей нежесткости вторая чистая стратегия игрока 1 не может входить в спектр какой-либо его оптимальной стратегии. Следовательно, первая его чистая стратегия является его единственной оптимальной стратегией.

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

б)              a2i -аи К а12. По тем же причинам, что и в случае а), здесь у игрока 1 имеется единственная оптимальная стратегия (именно, его первая чистая стратегия). Чтобы

смешанная стратегия У - (rj, 1 - 77) игрока 2 была оптимальной, необходимо и доста&точно соблюдение неравенства

Л2т УТ=а2лгі±а22 (1 - г)) vA = лп,"

откуда и находятся соответствующие значения 17.

в)              а2Х < аХ1 -аХ2. Симметрично предыдущему здесь единственная оптимальная (первая чистая) стратегия имеется у игрока 2, а условием оптимальности смешанной стратегии Х- (?, 1 - ?) игрока 1 будет

ХА.2 = + (1 - ?) «22              =

г)              а2Х -ахх -а12. Этот случай распадается в свою очередь на три подслучая.

гі) а22 < При этом, очевидно, СФ 0, у игрока 1 единственная оптимальная стратегия, а оптимальными стратегиями игрока 2 будут все его стратегии.

г2) а27 > Здесь также С Ф 0; единственная оптимальная стратегия здесь будет у игрока 2, а оптимальными стратегиями игрока 1 будут все его стратегии.

г3) а22 =t>p. Здесь С = а1 -а2 =0. Все ситуации оказываются равновесными, а все стратегии игроков - оптимальными.

18.11. Приведем пример, иллюстрирующий нахождение оптимальных стратегий игроков в случае 1) из предыдущего пункта.

Рассмотрим игру Г^ с матрицей выигрышей А =

этой матрицы равен 2, а минимакс равен 3. Поэтому седловых точек в чистых стра&тегиях в этой игре нет, и мы действительно имеем дело со случаем 1). Обозначим искомую оптимальную стратегию игрока 1 через (?* 1 -?*). Тогда выражающее дополняющую нежесткость равенство (18.6) принимает вид ?*-3 + (1 - ?*) *2 = = ?*¦ 1 + (1 - ?*) -5, откуда ?* = 3/5 и 1 — ? * = 2/5. Значение vA этой игры равно 13/5.

Аналогично соответствующее равенство для оптимальной стратегии 1 — 77*) игрока 2 имеет вид

Зтг*+1 ¦ (1 -V*) =2г?*+5 ¦ (1 -г?*),              (18.19)

откуда 77* = 4/5 и 1 - г\*= 1/5.

Заметим, впрочем, что, зная значение vA игры, равенства (18.19) можно и не выписывать. В данном случае должно быть А\. У* Ф vA, как, впрочем, и А^- У*= vA. Первое из этих равенств имеет вид 3?7* + 1 ¦ (1 — 77*) = 13/5, откуда и следует тре&буемое.

Максимин элементов