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


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


57

чтобы для любого игрока i и любой его чистой стратегии / выполнялось неравенство

Щ{Х* \\Xi)Hi{X).(8.2)

Доказательство. Необходимость очевидна, так как чистая стратегия является частным случаем смешанной и, таким образом, каждое из неравенств (8.2) есть частный случай соответствующего неравенства (8.1).

Для доказательства достаточности следует воспользоваться переходом к смешанным стратегиям, как это бьшо описано в п. 7.6. П

8.3. Ввиду того, что бескоалиционная игра является подыгрой своего смешанного расширения, к этой паре игр применима теорема о независимости от постороншх альтернатив. .Теорема. Если

Г =<Д{Х,},„{Я,}.,>

- смешанное расширение бескоалиционный игры

Г = </,{х,},е/. <>,е/>

<£,iT)-xnTi{r\(8.3)

?(Г) =хП £(Г),(8.4)

Доказательство аналогично доказательству теоремы п. 9.6 гл. 1 и вытекает непосредственно из теоремы п. 5.4 о независимости от посторонних альтернатив. □

§ 9. ТЕОРЕМА НЭША

9.1. Дж. Нэшем было доказано существование ситуации равновесия в смешанных стратегиях для любой конечной бескоалиционной игры. Теорема. В каждой бескоалиционной игре

Г = </,{х,}.,,{Я,}.>

существует хотя бы одна ситуация равновесия (в смешанных стратегиях).

Доказательство. Если игрок / имеет в игре Г чистых стратегий, то множество всех его смешанных стратегий, как уже неоднократно отмечалось, можно представлять как (ш/ - 1)-мерный симплекс. Поэтому всякую ситуацию

Х = (Хь...,Х„)(9.1)

в смешанных стратегиях можно рассматривать как точку в декартовом произведении X = Xi X . . . X Х„ симплексов смешанных стратегий. Это декартово произведение, очевидно, является вьшуклым и компактным подмножеством евклидова пространства размерности mj + ... + w„ -

Положим теперь для произвольной ситуации X и любой чистой стратегии х G X/ игрока /

ft\x) = i{X) = mx{0,Hi(X\\x)~Hi{X)) .(9.2)

Очевидно, все вводимые таким образом функции (/?. принимают только неотрицательные значения.



функция <р. показьшает увеличение выигрыша игрока i в ситуации X, происходящее за счет замены его стратегии Xi, входящей в эту ситуацию, некоторой чистой стратегией х/ . Уменьшения же вьшгрыша функция

не показьшает, ибо в этом случае ее значение будет равно нулю. Составим теперь для всевозможных / = 1, ..., « и / = 1, ..., ту числа вида

1 + 2 W

7 = 1

Все эти дроби, очевидно, неотрицательны, а каждая сумма вида 1 + 2 !(Х)

7 = 1

равна единице.

Следовательно, при фиксированных X и i дроби (9.3) можно понимать как вероятности соответствующих чистых стратегий х/ игрока /. Тем

самым каждый набор таких дробей для всех чистых стратегий х/ Е х/ можно понимать как смешанную стратегию игрока i.

Так как дроби (9.3) составляются для каждого игрока i G /, их совокупность определяет систему смешанных стратегий всех игроков, т.е. некоторую ситуацию в игре Г. Эта ситуация зависит от исходной ситуации X, являясь ее функцией. Будем обозначать ее поэтому через ф(Х). Очевидно, что функция ф осуществляет преобразование замкнутого вьшуклого и ограниченного множества всех ситуаций X в себя.

Кроме того, эта функция является непрерывной функцией ситуации. Действительно, каждая компонента ситуации, являющейся значением функции есть дробь вида (9.3). В числителе этой дроби первое слагаемое есть сама компонента исходной ситуации и поэтому зависит от нее непрерывно. Второе слагаемое, как видно из (9.2), есть комбинация из линейных функций Я/ (X)

и Hi(X II Xj-(), постоянной О и операции взятия максимума (то, что функция шах { О, х } является непрерывной, легко усмотреть из ее графика на рис. 3.2; ср. также лемму п. 10.5 гл. 1). Следовательно, !\Х) также является непрерывной функцией X

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

На основании сказанного мы находимся в условиях известной теоремы Брауэра о неподвижной точке*), согласно которой непрерьшное преобразование ф вьшуклого компактного подмножества конечномерного прост-

Рис. 3.2



ранства в себя должно иметь хотя бы одну неподвижную точку, т.е. такую точку , для которой i (X) = Х, Пусть Х - одна из таких неподвижных точек. Это значит, что для всех / и /

1 + Z /(Л-О)

/ = i

(9.4)

Вспомним теперь, что на основании леммы п. 7.7 для любого игрока /должна найтись такая его чистая стратегия л:?, что X.{x>Q и .(Х) = 0. Цля этой стратегии равенство (9.4) записывается как

1 + I /(Х)

i = \

откуда

Xl(x)Xf{x) Z 1{Х) = Х{хГ)(Ху j -1

Отбрасьшая равные слагаемые справа и слева и вспоминая, что второе слагаемое справа по самому выбору стратегии обращается в нуль, получаем

/ = 1

Но первый сомножитель слева, опять-таки по выбору стратегии х, от-личен от нуля. Следовательно, 2 <р{{К) = 0. А так как все числа ф!{Х) неотрицательны, каждое из них должно обращаться в нуль:

{Х) = 0. Следовательно, в нашем случае в равенстве (9.2) под знаком шксимума положительных чисел нет, г.е.

Так как это неравенство справедливо для любого игрока / и любой его

чистой стратегии л/\ теорема 8.2 дает нам, что ситуация Х является ситуацией равновесия. □

Другое доказательство теоремы Нэша см. в приложении 2.

9.2. Заметим, что принципиальнш важность теоремы Нэша ограничивается вопросом существования лпуапии равновесия. Непосредственно применять ее дпя нахождения i.:kix ситуаций не удается, так как сама

( м., например, Люстсрник Л.А., (оболов В.И. "Элементы функционального .нализа", М., Наука, 1965, с. 502 - 507.

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