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


[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


37

(13:А*) Всегда

max min ф (х, у) rg min max ф (х, у).

х у ух

(13:В*) Мы имеем

max min ф (х, у) = min max ф (х, у)

х у ух

тогда и только тогда, когда существует седловая точка х0, Уо функции ф.

13.5. Доказательства основных фактов

13.5.1. Во-первых, определим для каждой функции ф (х, у) два множества: Av и В®, min ф (х, у) является функцией от х. Пусть А®

будет множеством всех тех х0, при которых эта функция достигает своего максимального значения. Аналогично max ф (х, у) является функцией

от у. Пусть В® будет множеством всех тех у0, при которых эта функция достигает своего минимального значения. Теперь мы докажем (13:А*) и (13:В*).

Доказательство (13:А*). Выберем х0 из А* и у0 из Бф. Тогда max min ф (х, у) - min ф (х0, у) ф (х0, у о) max ф (х, у0) = min max ф (х, у),

х у у х ух

т. е. max min ф (x, i/) g min max ф (x, г/), что и требовалось.

х у у X

Доказательство необходимости существования седловой точки в (13:В*). Предположим, что

max min ф (х, у) = min max ф (х, у).

х у ух

Выберем х0 в 4Ф и у0 в 5Ф; тогда мы имеем

max ф (х, у о) = min max ф (х, у) = max min ф (х, у) = min ф (х0, у).

х ух х у у

Следовательно, для любого х

Ф (х, у о) max ф (х, у0) = min <р (х0, у) Ф (х0, у0),

т. е. ф (х0, Уо) ф (х, уо), так что ф (х, у0) принимает свое максимальное значение при х = х0. Точно так же для любого у*

Ф (х0, у) min ф (х0, у) = max ф (х, у0) ф (х0, у0),

т. е. ф (яо, у о) Ф (#о, У)\ поэтому ф (х0, у) достигает минимума при у = у0.

Следовательно, пара х0, у0 составляет седловую точку.

Доказательство достаточности существования седловой точки в (13:В*). Пусть х0, Уо - седловая точка. Тогда

max min ф (х, у) min ф (х0, у) = ф (х0, у о),

х у у

min max ф (х, у) max ф (х, у0) = у(х0, Уо)-

ух x



Следовательно,

max min ср (х, у) ср~(#0, у0) min max у(х, у).

х у ~ " ух"

С учетом (13:А*) это дает

max min ср (х, у)=ц> (х0, у0) = min max ср (х, у)

х у ух

и, следовательно, нужное равенство.

13.5.2. Рассуждения п. 13.5.1 приводят к некоторым дальнейшим результатам, которые имеет смысл отметить. Мы предположим теперь существование седловой точки, т. е. справедливость равенства (13:В*).

Для каждой седловой точки х0, у0

(13:С*) ср (#0, уо) =max min ср (х, у) = min max ср у).

х у ух

Доказательство. Это совпадает с последним равенством в доказательстве достаточности (13:В*) в п. 13.5.1.

(13:D*) #0, уо образуют седловую точку тогда и только тогда, когда х0 принадлежит <р, а у0 принадлежит В® 1).

Доказательство достаточности. Пусть х0 принадлежит А®, а уо принадлежит В®. Тогда доказательство необходимости (13:В*) в п. 13.5.1 показывает, что пара х0, у о является седловой точкой.

Доказательство необходимости. Пусть х0, у0 - седловая точка. Воспользуемся (13:С*). Для каждого х должно быть

min ф (#, у) max min ф (х, у) = <р (ж0, у о) = min ф (х0, у)9

уху у

т. е. min ф (х0, у) min ф (хг, у); поэтому min ф (х, у) достигает своего

У У у

максимального значения при х = х0. Следовательно, х0 принадлежит А®. Аналогично для каждого у

max ф (х, у) min max ф (х, у) = ф (х0, у0) = max ф (х, у0),

х у X X

т. е. max ф (х, у0) max ф (х, у)\ поэтому max ф (х, у) достигает

XX X

своего минимального значения при у = у0. Следовательно, у0 принадлежит В®. Это завершает доказательство.

Теоремы (13:С*), (13:D*) указывают, между прочим, на недостатки аналогии, описанной в конце п. 13.4.2, т. е. они показывают, что наше понятие седловой точки уже, чем обиходное представление о седле, или перевале. Действительно, (13:С*) указывает, что все седла, в предположении их существования, имеют одну и ту же высоту. A (13:D*) утверждает, что, если мы изобразим множества А®, В® как два интервала чисел 2), то все седла образуют область, которая имеет форму прямоугольного плато 3).

г) Только при наших предположениях, сформулированных в начале этого пункта. В противном случае седловых точек нет вообще.

2) Если х, у - целые положительные числа, то это, конечно, можно осуществить при помощи двух соответствующих преобразований их областей.

3) Общие математические понятия, упомянутые в сноске 1 на стр. 121, свободны от этих недостатков. Они точно соответствуют обиходному представлению о перевале.



13.5.3. Мы закончим этот раздел доказательством существования седловой точки для одного частного вида х, у и ф (х, у). Далее станет видно, что общность этого частного случая не является незначительной. Пусть дана функция if (х, и) двух аргументов х, и. Рассмотрим все функции / (х) аргумента х, которые принимают значения в области изменения и. Сохраним теперь аргумент х, а вместо аргумента и используем саму функцию /*). Выражение if (х, f (х)) определяется для любых х и /; следовательно, мы можем трактовать if (х, f (х)) как функцию аргументов х, f и взять ее вместо ф (х, у).

Мы хотим доказать, что для этих х, f и if (х, f (х)) (вместо хну и ф (х, у)) существует седловая точка, т. е. что

(13:Е) maxminif(#, f (х)) == min max if (я, f(x)).

! х f fx

Доказательство. Выберем для каждого х значение щ так, чтобы было if (х, щ) = min if) (х, и). Это и0 зависит от х; следовательно,

мы можем определить функцию /0 равенством щ = /0 (#), Тем самым if (х, /о (х)) = min if (х, и). Следовательно,

max if (х, /о (х)) = max min if (i, и).

x х и

Тем более

(13:F) min max if (x, f (x)) :g max min if (#, u).

fx X и

Далее, min if (x, f (x)) есть то же самое, что и min if (х, и), так как /

входит в это выражение только через свое значение при данном х, т. е. / (х), для которого мы можем написать и. Таким образом, min if (х, f (х)) =

= min if (я, и) и потому

(13:G) max min if (x, f (x)) = max min if (x, u).

X f X и

Соотношения (13:F) и (13:G) вместе устанавливают справедливость знака в (13:Е). Знак :g в (13:Е) имеет место благодаря (13:А*). Следовательно, в (13:Е) мы имеем знак равенства, т. е. доказательство завершено.

§ 14. ВПОЛНЕ ОПРЕДЕЛЕННЫЕ ИГРЫ

14.1. Формулировка проблемы

14.1.1. Теперь мы приступаем к рассмотрению игры двух лиц с нулевой суммой. Начнем с использования нормальной формы.

В соответствии с этим игра состоит из двух ходов: игрок 1 выбирает число т4 = 1, . . Pi, а игрок 2 выбирает т2 = 1, . . ., р2 (каждый выбор производится при полном незнании выбора другого игрока), после чего игроки 1 и 2 получают соответственно выигрыши Ж± (тА, т2) и Ж2 (Tl, т2) 2).

х) Читателю предлагается отдать себе отчет в том, что, хотя / является функцией, она вполне может быть аргументом другой функции. 2) См. (11:D) в п. 11.2.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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]