Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 9

(2.3.9) ии У Такая стратегия у называется минимаксной стратегией игрока Н. Таким образом, мы получаем два числа о1 н оп. Эти числа называются значениями игры для игроков 1 и 11 соответственно. 11. 4. ТЕОРЕМА О МИЕИМАКСЕ Легко доказать, что для любой функции Р(х, у), определенной на произвольном декартовом произведении Х Х у, имеет место неравенство шах ппп Р (х, у) ~ ппп шах Р (х, у). (2.4,1) лиХ и~т и~т. Х Отсюда следует, что о~ ~ оп. ог = оп. Эта важнейшая в теории игр теорема была доказана многими способами. Мы приведем здесь доказательство, принадлежащее фои Нейману и Моргенштерну. Начнем с двух лемм. 1!.4.2.

Л е м м а (теорема об опорной гиперплоскости). Пусть  — замкнутое выпуклое множество в п-мерном евклидовом пространстве, а х = (х„..., х„) — некоторая точка, не принадлежащая В. Тогда существуют такие числа рь ..., р„, р„+ь что л Х Ргхг = Рл+1 г ! (2.4.2) ~~~~ р,у,> р„+, для всех у ен В. (2.4.3) г 1 Это неравенство аналогично (2.3.0). Действительно, вполне естественно, что в этом случае, как и выше, нижний выигрыш игрока ! не может превышать верхнего проигрыша игрока 11. Однако ранее мы видели, что равекство выполняется только в исключительных случаях.

В данном же случае справедлива следующая теорема. П.4.1. Теор ем а (теорема о минимаксе). 4! П. 4. Теорема о мииимаисе (Геометрически это означает, что через точку х можно провести гиперплоскость так, что В будет лежать целиком «выше» этой гиперплоскости.) До к а з а тел ьс т в о. Пусть г — такая точка из В, расстояние которой от х минимально. (Такая точка существует, так как В замкнуто.) Положим !Ос=гс — хс, с= 1, ..., л> р„+! = ~ г,х, — ~~.', хсп с ! ! Очевидно, равенство (2.4.2) выполняется.

Нужно доказать, что имеет место (2.4.3). Мы имеем и е е ~ге — ~ч',гх с ! с ! с ! и, следовательно, и е и и '.Ррсг! — Р„+, — — Х г', — 2 ~ г.х, + ,'~„хс - ~ч'„(г, — хс)' > О. Поэтому Х Рсгс > Ре+!. Допустим, что существует уев В, для которого и е..с Рсрс = Ре+! с ! Так как В выпукло, отрезок, соединяющий у с г, должен целиком содержаться в В, т. е. ис, = гу+ (! — г)ген В для всех О ~г ~ !. Квадрат расстояния от х до пс, имеет вид р'(х, пс,) ~~р~ (х, — гу, — (1 — г) гс)с. с 1 Поэтому л — = 2 ~~ (гс — у,) (х, — гу, — (1 — г) г,) = дре дг еаза с-! = 2 ~ (гс — х,) ус — 2 )~~~ (гс — х,) гс + 2 )~~ г (г, — у,)' 2 ~ р,у, — 2 ~)' р,г, + 2г,)~~ (гс — ус)з, При г О (т.

е. при пс, г) имеем дае ! — 2 ~~)' рсус — 2 ~ р,гс. Гд, О Антагонистические игом Здесь первое слагаемое по предположению не превосходит 2р +! а второе больше 2р,+ь Поэтому Отсюда следует, что для т, достаточно близких к нулю, р(х, гв,)<р(х, г). Но это противоречит выбору г; следовательно, для всех уев В! условие (2.4.3) должно выполняться. И.4.3.

Л е м м а (георема об альтернативах для матриц). Пусть А =(ам) есть (т Х п)-матрица. Тогда справедливо либо утвер- ждение (!), либо утверждение (1!): (!) точка 0 (в пг-мерном пространстве) содержится в выпуклой оболочке т + и точек а! =(ап, ..., а,), а„=(аьи ..., а „) е,=.(1, О, ..., О), ег = (О, 1, О, ..., 0), е = (О, О, ..., 1); (й) существуют числа х!, ..., х, удовлетворяющие условиям хг>0, ~хе=-1, ~~~Растят>0, 1=1, ..., и. ! ! ! ! Доказательство. Предположим, что утверждение (!) неверно.

На основании леммы П.4.2 существуют такие числа р„... ..., р,„+ь что ;~',О р,— р.„ ! 1 (отсюда следует, конечно, что р~+! —— 0) и ,э; р,у,>о для всех у в указанном выпуклом множестве. В частности, это выполняется, если у является любым из и! + и векторов аь е;.

Поэтому ~ апр, > 0 для всех 1, ! ! рг>0 для всех г. П. 4. Теорема о миломохее 43 'Так как рс > О, получаем ~ рс> О, и можно положить хс =— Следовательно, ,,'~~ а!/хс > О, х, > О„Х х, = 1. с-! с ! ~ э/ас/+ з„+с= О, / ! з/~О, се+ л ~ з/=1. ! /=1,..., т, /=1, ..., т+и, Если бы все числа зь ..., эл были равны нулю, то О оказывался бы выпуклой линейной комбинацией т единичных векторов еь ..., е, что, очевидно, невозможно, так как они линейно незаззисимы.

Следовательно, по крайней мере одно из чисел з!, ..., з л положительно и ~, з/>О. Тогда можно положить / ! 8/ у/ =— Х'/ / ! и мы получаем Х у/=1, / ! у, ~ О, / ! ~~~~ е/ для всех с. Значит, о(у)::-О и оп Б О. Предположим теперь, что х/(х) >О, так что от> О. верно утверждение (й). Тогда На основании двух этих лемм можно доказать теорему. Доказательство теорем ы о м пни ма к се. Пусть А — матричная игра. По лемме !!. 4.3 имеет место либо утверждение (!), либо (!!). Если верно (!), то О является выпуклой линейной комбинацией ,т+ и векторов.

Поэтому существуют такие з!, ..., з +„, что Гл. В. Антагонистические иг[[и Следовательно, неравенство о[-= О < оп не может иметь места. Предположим теперь, что мы изменили игру А, заменив ее на игру В = (Ьп), где Ь[! = ам+ й. Ясно, что для любых х, у хВут хАдт+ й Поэтому о[(В) = о[(А)+ й, он(В) = оп(А)+ й. Так как неравенство о! (В) < О < он (В) не может иметь места, то неравенство о! (А) < — й < оп (А) также не выполняется. Но Ь произвольно.

Значит, неравенство о! < оц невозможно. Так как о[~ оп, то о! он1 что и требовалось доказать. Таким образом, мы видим, что при использовании смешанных стратегий нижний выигрыш игрока 1 в точности равен верхнему проигрышу игрока П. Общая величина о этих двух чисел называется значением игры, Ыы видим, что стратегия х, удовлетворяющая условию Х х,а„ и о, !' = 1, ..., и, (2.4.4) ! ! является оптимальной для игрока 1 в том смысле, что не суще- ствует стратегии, которая дала бы ему больший ожидаемый вы- игрыш, чем о, против каждой стратегии игрока 11.

Обратно, если д удовлетворяет условию „~~ а,[у! ~ о, [=1, ..., и, (2.4.5) / ! то у является оптимальной стратегией для игрока П в том же смысле. Далее, очевидно, что хАут= о, так как если бы правая часть этого равенства была меньше левой, то это противоречило бы (2,4.5), а если бы она была больше ле- вой, это противоречило бы (2.4.4). Следовательно, оптимальные стратегии х и д являются также оптимальными одна против дру- П.

4. Теорема о минимакее той, а также против любой иной оптимальной стратегии. Будем называть любую пару оптимальных стратегий (х, у) решением игры. В дальнейшем окажется полезной следующая теорема (несколько более сильная форма теоремы о минимаксе). П,4.4. Теорема. В игре с (гп Х и)-матрицей А либо игрок П имеет оптимальную стратегию у, в которой у„> О, либо игрок 1 имеет оптимальную стратегию х, для которой ~~'.~ а,лх, > о. Р х = ~ч'.~ Хите е-! для некоторых неотрицательных Х„..., ).р. Легко проверить, что такой конус действительно является выпуклым. П.4.6. Лемма (Фаркаш).

Пусть г =(г!, ..., г„", й=1, ... ..., р+ 1,— такие п-векторы, что любь!е (д!, ..., 4„), удовлетворяющие условию ~ о.ге! ) О, й - 1, ..., р, ! ! (2.4.6) будут также удовлетворять условию ~~'.! д.ге+! = О, у„! !У Тогда гг+' принадлежит выпуклому конусу С, порожденному вектОРаЛСи Г', ..., ги. (2.4.7) Доказательство.

Допустим, что гР+' ф С. По лемме П,4.2 существуют такие числа дь ..., д„+!, что л ! л+! Х д гР+! = д и л Хогвг>а„+! для всех ее=С. ! ! Для доказательства теоремы П.4.4 приведем сначала одно определение. П45. Определение. Пусть г"=(г, ..., г„"),й=!... р,— система р и-векторов. Тогда под выпуклым конусом, порожденным векторами г', ..., гР, понимается множество всех таких векторов х, что Гл. 1!. Антагонистические игр!и Далее, Оен С; следовательно, дн+! (О.

Допустим, кроме того, что и сумма ~~~~ дгэготрицательна для любого вен С. Для всякого поло! жительного числа а имеем олен С Тогда, взяв а достаточно боль- шим, можно было бы сделать форму ~~'.~ о!аз!=а ~г д;з! меньше, чем д +!. Отсюда следует, что н Х у т,'+!<О, г! но ~! о!э! И 0 для всех а ен С ! и, в частности, для т = т', ..., Гг, а это противоречит предположению леммы. Докажем теперь теорему 11А.4. Предположим сначала, что о(А) =О. Рассмотрим лт+ и т-ве«торов е, =(1, О„..., О), е, = (О, 1, ..., 0), е = (О, О, ..., 1), а, =(ан, ато ..., а,), а„, =(аь„,, а„„„..., а,„„,), Тогда — а„либо принадлежит выпуклому конусу С, порожденному остальными и+ и — 1 точками, либо не принадлежит ему.