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


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


11

(4.2) и (4.3):

Я(х, у*) Н(х\ у*)< Н(х\ у) при любых xGx и у.(4.4)

Множество всех ситуаций равновесия игры Г обозначается через (Г). Очевидно,(Г) = »1(Г) П 2 (Г).

Применительно к матричным играм говорят о седловых точках матрицы выигрышей. □

4.3.Неравенство (4.4) выражает следующее свойство функции Я в точке (х*,у*): при любом изменении значения переменной х значение функции Я может только уменьшиться, а при изменении значения переменной у - только увеличиться. Если представить себе поверхность, описываемую функцией Я в координатах х и j, то ситуациям равновесия будут соответствовать седлообразные точки поверхности (рис. 1.1).

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

Во-вторых, в геометрии седлообразность точки носит аналитический характер и связана с обращением в нуль соответствующих производных. В теории игр аналитичность экстремумов не обязательна. Кроме того, нередко седловая точка оказывается на границе области задания функции. Например для функции Н(х,у) = х +j;, заданной на квадрате 0<х,у< 1, точка [1, 0] является седловой (рис. 12). В связи с этим поучительно вспомнить пример из п. 2.4. введения.

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

Теорема. Если в антагонистической игре Г = (х, у,Я > взять

(х\у*\ {х\у)ЩТ\(4.5) тОу во-первых,

Н{х\у*)=Н{х\у\(4.6) а, во-вторых,

{х\у)ЩТ) и (xJ*)G(Г).(4.7)

Доказательство. Из определения седловой точки в (4.4) следует, что при любых X G X и 7 G у имею! место неравенства

Я(х, у*)< Я(х*, у*) <Н{х\у\(4.8)

Я(х, ° ) < Я(х j; ) < Я(х >;).(4.9)

Положим в (4.8) слева х = х, справа = j, а в (4.9) слева х = х* и справа у у*. Тогда будет

Я(x7*)<Яfx7*)<

< Я(х*, у"") < Н(х,у) <Я(х j;*),(4.10)

откуда следует (4.6).

З.Н.Н. Воробьев33



Далее, из (4.8) и (4.10) следует, что при любом л: G х выполняется

Я(х, ;;*) < Н{х\ у*) = Я(х уП, а из (4.10) и (4.9) - что при любом уу выполняется

Н(х\у*)=Н{х,у)<Н(х\у). Оба эти неравенства дают

Н{х, у*) < Я(х, у*) < Я(х, у\

T.t,(x\ у*)ЩТ).

Соотношение {х*,у) Е (Г) получается симметричными рассуждениями. □

4.5.Первое из установленных в этой теореме свойств множества всех ситуаций равновесия антагонистической игры, выражаемое равенством (4.6), иногда называется равноценностью ситуаций равновесия. Общее значение функции выигрыша на множестве (Г) всех ситуаций равновесия (седловых точек) игры Г есть как бы обусловленный объективно правилами игры Г выигрыш игрока 1 (проигрыш игрока 2) в ней. Поэтому оно называется значением игры и обозначается через v р или у ( Г ).

Значение v г игры Г можно интерпретировать как разумную, "справедливую" плату, которую естественно взимать с игрока 1 в пользу игрока 2 за участие игрока 1 в игре Г против игрока 2.

Подчеркнем, что свойство равноценности ситуаций равновесия не поддается обращению: из {х*,у*) Е €{Т) и Н(х,у) = Н{х*,у*) вовсе не следует, что и {х,у) Е (Г), Например, в 2Х2-игре с матрицей выигрышей

1 2

О 1 .

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

4.6.Второе же установленное в теореме п. 4.4. свойство седловых точек дает основание для следующих рассуждений.

Очевидно, Й(Г) СхХу. Обозначим соответственно через §(Г) и «(Г) проекции (Г) на X и на у, т.е. положим

§(Г) = {х: хЕх и при некотором зЕубудет (х, j/) Е (Г)},

#rr)={j: jEy ипринекотором х Ex будет (х, j) Eg(r)}.

Определение. Стратегия игрока 1 из §(Г) и стратегии игрока 2 из (Г) называются оптимальными стратегиями соответствующих игроков в игре Г. □

Ясно, чтоg(r) С §(Г) Хс(Г). Предположим,что (jc*,j) Е §(Г) X X с(Г). Тогда по определению найдутся такие >*Еуил:Ех, что (jc*, J*) Е €{Т) и (Л J°) (Г). Но тогда по теореме п. 4.4 будет (jc*, j) Е ?g(r), и мы получаем (Г) D §(Г) X с(Г). Следовательно, в (Г) = §(Г) Х<(Г). Такая возможность представления множества ё(Г) называется его прямоугольностью.

Заметим, что всякое прямоугольное подмножество декартова произведения разлагается в декартово произведение подмножеств сомножителей 34



единственным способом. Поэтому если в двух играх Г и Г множества седловых точек совпадают, то совпадают и множества оптимальных стратегий каждого из игроков: 8(Г) = §(Г) Ис(Г) =Г(Г).

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

В качестве примера приведем 3 X 3-игру Г с матрице i вьшгрышей 1 2 Г О 100 о .1 3 и

Седловыми точками являются здесь все четыре угловых ситуации. То, что прямоугольное множество (Г) выглядит здесь несвязным, не имеет значения; порядок строк и столбцов матрицы может быть произвольно изменен (см. п. 1.9).

§ 5. ИНВАРИАНТНОСТЬ СЕДЛОВЫХ ТОЧЕК

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

Точная формулировка этой эквивалентности заключается в следующих теоремах.

5.2.Теорема. Если

Г = <х,у,Я> и Г = <х,у,Я>(5.1)

- две аффинно эквивалентных игры, причем

Н = кН + а,(5.2)

к>0,

то S(r)= §(Г), ЛГ) = да и v. =kvY а.

Доказательство. Приемлемость ситуации {х*, у*) для игрока 1 в игре Г означает, что она удовлетворяет соотношению (4.3). Но тогда должно быть и кН{х,у*) + а кН(х*,у*) + а для любого xG х, т.е. в силу (5.2) Н(х,у*) <Н(х*,у*) для любого хЕх. Таким образом, (х\у*) е 1 (Г ), так что gi (Г) С (Г ).Из симметрии аффинной эквивалентности следует, что должно выполняться и противоположное включение; следовательно,! (Г) = (Г).

Аналогично пол)ается, что2(Г) = 2 (Г). Следовательно,

(Г) = 1 (Г) П 2(Г) = 1 (Г) П.(Г) = (Г).(5.3)

3*35

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