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


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


58

по себе она не является конструктивной: теорема Брауэра не содержит никаких указаний на способ фактического нахождения неподвижной точки; ICM самым и теорема Нзша, которая опирается на теорему Брауэра самым существенным образом, не дает путей к нахождению ситуаций равновесия. Вместе с гем, все методы приближенного нахождения неподвижных точек в непрерывных отображениях компактов (особенно выпуклых) в себя могут быть использованы для приближенного решения конечных бе с ко ал и ци о н ны х игр.

if 10. ДОПОЛНЯЮЩАЯ НЕЖТХТКОСТЬ

юл. Ряд свойств приеж1емых ситуаций и седчовых точек в антагонистических играх переносится на приемлемые ситуащш и на ситуации равновесия в произво.чьных OecKoajrauHOHHbix играх. К их числу относится следую-пхий аналог теоремы о дополняющей нежесткости" (см. пп. 17.2,17.3 гл. 1).

Теорема. Если смешанная стратегия Xf игрока i входит в приемлемую djLH негп ситуацию X и для некоторой его чистой стратегии имеет место строгое неравенство Я;{Х л*) <Я/(Х), го Xjix) = 0.

Доказательство этой теоремы по существу не отличается о i доказательства аналогачной теоремы п. 17.2 гл. 1.

Именно, предположим, что Л,(л ) > 0. Тогда

Hi{X\\x)X{x;)<H(X)X{x).(10.1)

Вместе с тем для всех чистых стратегий игрока /, отличных от х, должно быть по определению ситуации равновесия Hf(X \\ Л/) Я/(Л) и тем самым HiiX II )Х{хПй ЯД V )X{Xi).(10.2)

Суммируя по всем Xf G Xf и прибавляя (10.1), мы, как и при рассуждениях, встретившихся нам в ходе доказательства леммы п. 7.7, получаем Я, (Л) < И,(Х ), чего не может быть. □

10.2. Доказанную теорему можно сформулировать и в несколько измененной ("контрапозитарной") форме: если равновесная стратегия Xj игрока / входит в ситуацию равновесия X и чистая стратегия х принадлежит спектру смешанной стратегии Х\-, то

fT{X\\x;) = H,{\),(10.3)

§ И.СИММЕТРИЧНЬН: СИТУАЦИИ РАВНОВЕСИЯ

11.1. В теореме п. 5.2. бьша зафиксирована инвариантность множеств приемлемых ситуаций, а также множеств ситуаций равновесия при автоморфизмах игры.

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

Определение. Ситуация Y в смешанных стратегиях в бескоалиционной игре V называется симметричной, если для любого автоморфизма тг игры Г имеет место пХ = X. □

Содержательно симметричные ситуации равновесия являются оптимальными не только в смысле общей дгш всех ситуаций равновесия устойчивости, но и в смысле справедливости; в таких ситуациях игроки, равноправно



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

11.2.Л е м м а. Множество всех симметричных ситуаций (в смешанных стратегиях) в конечной бескоалиционной игре Г из (1.1) является непустым, выпуклым и замкнутым.

Доказательство. Непустота множества всех симметричных ситуаций в игре Г Следует из того, что ему принадлежит ситуация X = = (Xl, ..., Xfj), для которой

Xi{xi)=llmj при /Е/ и XjGxj.

Действительно, в этом случае при любом автоморфизме п тгХДтгх/) = = l/nijf, а, как бьшо замечено в конце п. 2.4, т/ = т{.

Далее, при симметричных ситуациях XV й X G [О, 1] мы имеем

7г(ХХ/+(1 -Х)Х;)(7гх,) =

= Х(7ГХ/(7ГХ,-)) + (1 -Х)(7ГХ;)(7ГХ,) =

= ХХ;(х,) + (1 -Х)ХГ(х,) = (ХХ/+(1 -Х)ХГ)(х,),

т.е. множество всех симметричных ситуаций оказывается вьшуклым.

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

11.3.Т е о р е м а. Конечная бескоалиционная игра имеет симметричные ситуации равновесия.

Доказательство. Возьмем отображение ф из доказательства теоремы Нэша (см. п. 9.1) и покажем, что оно преобразует множество всех симметричных ситуаций в себя.

Пусть X - симметричная ситуация, а тг - произвольный автоморфизм игры. Из (9.2) следует, что

;ЧтгХ) = тах{О.Я,.(тгХ ях/)-ЯДтгХ)} =

= тгх{0,HiiX \\ xi)-HiiX)} = V)-" Поэтому

=x„,(7rx;:)+;W)(i+ .2 k"W =

= Xi{xi)+f{X)il+ 2 fiX))- -{px.){xi),

xlS X.



т.е. если ситуация X симметричная, то такой же оказывается и ситуация фХ.

Таким образом, мы имеем дело с непрерывным отображением компакта симметричных ситуаций в себя. По теореме Брауэра это отображение имеет неподвижную точку, которая, как это было выяснено в ходе теоремы Нэша, является ситуацией равновесия. □

Заметим, кстати, что эта теорема также была доказана Дж.Нэшем.

§ 12.БИМАТРИЧНЫЕ ИГРЫ

12.1. Задача нахождения ситуаций равновесия бескоалиционной игры Г формата (т,... ,т„) фактически состоит в решении системы Wi + . .. ... + m„ неравенств вида (8.2) с . .. т„ ограничениями неотрицательности и п ограничениями нормирования. Математически это сложно и громоздко. Лишь для отдельных сравнительно простых классов бескоалиционных игр ход решения этой задачи поддается элементарному описанию.

Одним из таких классов являются конечные бескоалиционные игры двух лиц. Пусть в такой игре игрок 1 имеет т чистых стратегий, а игрок 2 - п стратегий, и в каждой ситуации (/,/) игрок 1 получает выигрыш Uij , а игрок 2 - выигрыш bfj , Тогда значения обеих функций выигрыша игроков естественно расположить в виде пары матриц

Поэтому такие игры называются биматричными. Биматричная игра с матрицами выигрышей А и В обозначается через Г (А, В.) или через Г.

12.2. Смешанные стратегии в биматричных играх, как и в матричных играх, естественно понимать как векторы, составляющие фундаментальный симплекс. Если X nY - соответственно векторы, описывающие смешанные стратегии игроков 1 и 2, то, как легко видеть,

H,{X,Y)=XAY, H2{X,Y) = XBY.

Определение ситуации равновесия для случая биматричной игры приобретает следующую формулировку. Ситуация (X, Y) в биматричной игре с матрицами выигрышей А и В является равновесной, если

Ai. Y й XAY, /=1,...,т.

(12.1) (12.2)

Очевидно, при В - - А биматричная игра превращается в матричную, а соотношения (12.1) и (12.2) - соответственно в

XB.f £ XBY,1, ...,/7.

Ai.Y- й XAY\ /=1,...,

-XA.f

(12.3)

Последнее неравенство равносильно XAY XA.j , что вместе с (12,3) дает нам известное определение седловой точки в матричной игре

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