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


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


55

Сопоставляя написанные формулы с определением v и v2 из п. 17.4, мы получаем

(17:5:а) vmaxmin 2 (Ti» т2) lxv

(17:5:b) vminmax 2 (Ti» 2) Цт2-

~y Tl T2= 1

Эти формулы допускают простую словесную интерпретацию. При вычислении мы заботимся только о защите игрока 1 от раскрытия противником его стратегии, что выражается в использовании (вместо Tt); игрок 2 может при этом действовать по-старому и использовать т2 (вместо г]). При вычислении v2 роли игроков меняются. Это понятно и с точки зрения здравого смысла: vi относится к игре ГА (см. пп. 17.4 и 14.2); там игрок 2 выбирает после игрока 1 и полностью информирован о выборе 1; следовательно, он не нуждается в защите от раскрытия его собственной стратегии игроком 1. Для числа v2, относящегося к Г2, роли игроков меняются.

Значение не увеличится, если в приведенной выше формуле ограничить переменную в операции max. Ограничим значение вектора

векторами 6Ti (т2 = 1, . . Pi) (см. п. 16.1.3 и конец п. 17.2). Поскольку

2 (Tlf т2)б , = 35Г(т;, т2),

Ti=l

наше выражение заменяется на

max min Ж (т, т2) = vle т т2

Таким образом, мы показали, что

vi v

Аналогично (см. замечание в начале доказательства последней леммы), ограничивая г] векторами т=8 2, мы получаем

v2=:v2.

Вместе с vfgVg (см. п. 17.4) это дает нам

(17:3) vi v;v2v2,

что и требовалось.

17.6. Доказательство основной теоремы

17.6. Мы установили, что полная определённость в частном смысле (vi = v2) влечет полную определенность в общем смысле (v = v2). То, что полная определенность в общем может иметь место и тогда, когда полная определенность в частном не имеет места, т. е. что = v2 и в то же



время v4 Ф v2, видно из примеров «орлянки» и игры «камень, мешок и ножницы» 1). Поэтому мы можем утверждать, что переход от полной определенности в частном смысле к полной определенности в общем смысле действительно является шагом вперед. Однако на данный момент мы не знаем, относится ли это ко всем играм; может оказаться, что существуют такие игры Г двух лиц с нулевой суммой, которые не вполне определены даже в общем: мы еще не исключили возможности неравенства

v;<v;.

Если эта возможность реализуется, то все сказанное в п. 14.7.1 будет снова применимо и даже более широко: раскрытие стратегии противника будет составлять определенное преимущество

A = v2-v;>0,

и трудно себе представить, как может быть построена теория такой игры без дополнительной гипотезы о том, «кто чью стратегию раскроет».

Решающим фактором поэтому является возможность доказательства ого, что это никогда не произойдет. Для всех игр Г

т. е.

(17:6) max min К (g, г)) = min max К (g, г]),

£ Tl Tl l)

или, что то же самое (снова подставляя £, г), К вместо х, у, ф

в (13:В) из п. 13.4.3), седловая точка функции К (£, г\) существует. Это - общая теорема, которая имеет место для всех функций

К (, л) вида

3l 32

(17:2) К (£, т) = 2 2 Ж (т4, т2) £Tlr]t2.

Ti=l Т2=1

Выбор коэффициентов Ж (xi9 т2) здесь абсолютно неограничен; они образуют, как это было описано в п. 14.1.3, некоторую совершенно произ-

-у ->

вольную матрицу. Переменные \ и г) представляют собой фактически последовательности вещественных чисел . . ., £рх и r\i, . . ., т)р2, областями изменения которых являются множества и £р2 (см. сноску 1

на стр. 174). Функции К (£, т)) вида (17:2) называются билинейными формами.

3 амечание. Эта теорема впервые была сформулирована и доказана в статье одного] из авторов теории игр: J. von Neumann, Zur Theorie de Gesellschaftsspiele, Math. Annalen, 100 (1928), 295-320. Несколько более общая форма этой минимаксной проблемы возникает в математической экономике в связи с уравнениями производства: J. von Neumann, Tiber ein okonomisches Gleichungssystem und eine Ver-allgemeinerung des Browerschen Fixpunktsatzes, Ergebnisse eines Math. Kolloquinms, 8*(1937), 73-83. Следует заметить, что две совершенно различные задачи, изучаемые совершенно различными методами, приводят к одной и той же математической задаче необычного, «минимаксного» вида. По-видимому, здесь имеют место и более глубокие формальные связи, как и в других направлениях, о которых упоминается во второй статье. Это обстоятельство должно быть разъяснено.

J) В обеих играх vi = - l,v2 = 1 (см. пп. 14.7.2 и 14.7.3), а рассуждения в п. 17.1 можно рассматривать как доказательство того, что vi = v2 = 0.



Доказательство нашей теоремы, приведенное в первой статье, довольно запутанным, образом использует аппарат топологии и теории функций. Доказательство во второй статье полностью топологическое и связано с теоремой, являющейся важным методом этой дисциплины, так называемой «теоремой о неподвижной точке» Л. Е. И. Бра-уера. Этот аспект был в дальнейшем прояснен, а доказательство упрощено С. К а к у-т а н и: A Generalization of Brouwer s Fixed Point Theorem Duke Math. Journal, 8 (1941), 457-459. Все эти доказательства определенно не являются элементарными. Первое элементарное доказательство было дано Ж. Биллем вместе с Е. Боре-л е м и его сотрудниками: Traite du Calcul des Probabilites et de ses Applications, IV, 2, Application aux Jeux de Hasard, Paris, 1938; J. V i 11 e, Sur la Theorie Generale des Jeux au Intervient IHabilete des Joueurs, 105-ИЗ. Доказательство, которое мы здесь приводим, является дальнейшей элементаризацией доказательства Ж. Билля и представляется особенно простым. Основным здесь является, конечно, связь с теорией выпуклых множеств, изложенной в § 16, и в особенности с результатами из п. 16.4.3.

Доказательство получается просто при помощи результатов п. 16.4.3. Приведем его.

Применим (16:19:а) и (16:19:Ь) из п. 16.4.3, заменяя i, у, п, т и

-У -У -У -У

a(i, 7) на ti, т2, Pi, р2 и Ж (хи т2), а векторы w и я -на £ и ц.

Если выполняемся (16:19:Ь), то существует такой вектор i, что 3i

2 fa, T2)Stl0 ДЛЯ T2=lf р2,

т. е.

min 2 3F(Ti, т2)?Т10.

Т2 Ti=l

Следовательно, формула (17:5:а) из п. 17.5.2 дает нам

Если выполняется (16:19:а), то существует вектор г)£#р2» для которого

2 Ж fa, т2) Т)Т20 для Ti = l, р1?

т2=1

т. е.

max 2 (Ti» т2) Цх2 = 0. Следовательно, формула (17:5:Ь) из ц. 17.5.2 дает

Мы видим теперь, что имеет место либо 0» либо v2 0, т. е.

(17:7) Невозможно < 0 < v2.

Возьмем теперь произвольное число w и заменим функцию Ж (хи т2) на Ж (хи т2) - w г).

> > 3l 32 ->

При этом К (£, т)) заменяется на К (£, n)-w 2 2 1xx2- Так как I и п

ti=l т2=1

3i З2

принадлежат соответственно и 5р2, должно быть 2 £ti = 2 Лтг = 1*

П=1 Т2=1

г) Это значит, что игра Г заменяется новой игрой, правила которой в точности совпадают с правилами игры Г, за исключением того, что в конце партии игрок 1 получает меньше, а игрок 2 больше на фиксированную величину w.

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