Теория игр. Оуэн (1971) (1186151), страница 8
Текст из файла (страница 8)
мя альтернативами (обозначенными соответственно а и Ь, е я Н, е и )) в ка. ждой позиции. Глава 11 АНТАГОНИСТИЧЕСКИЕ ИГРЫ И..1. ИГРЫ С НУЛЕВОИ ОУММОИ И.1.1. Определение. Игра Г называется игрой с нулевой суммой, если в каждой окончательной позиции функция выигрыша (Рь ..., р ) удовлетворяет условию 1 Рс =О. (2.1.1) Вообще говоря, игра с нулевой суммой представляет собой замкнутую систему: все то, что кто-нибудь выиграл, должно быть кем-то проиграно. Большинство салонных игр является нграмн такого типа. Игры двух лиц с нулевой суммой называются антагонистическими, или строго конкурентными.
На основании условия (2.1.1) и-я компонента вектора выигрышей определяется остальными п — ! компонентами. В случае антагонистической игры можно просто задавать первую компоненту вектора выигрышей; вторая компонента обязательно равна первой с противоположным знаком, В этом случае назовем первую компоненту просто выигрышем, и это означает, что второй игрок отдает эту сумму первому.
Далее мы увидим, что антагонистическая игра отличается от остальных игр тем, что в ней нет никаких оснований для каких бы то ни было переговоров между игроками: в самом деле, если один выигрывает, то другой проигрывает. Смысл этого свойства виден из следующей теоремы. П.1.2.
Теорема. Пусть (аьах) и (тьтх) — две ситуации равновесия антагонистической игры. Тогда (!) (аь тх) и (ть вг) также являются ситуациями равновесия и (й) л (аь ае) = и (ть тт) = и (аь тт) = л (ть ат). (2.1.2) Доказательство. Ситуация (аьах) равновесна. Следовательно, л(аь а,) ~ л(т„а,). , С другой стороны, ситуация (тьте) также равновесна. Поэтому л(т!> 02) л,(т!> тг) Гл.
!!. Антагонистические игры Таким образом, тс (аы ои) ~' тс(тп ат) =— и (ть тт). Но, аналогично, п(то т,) = п(аь тг):- гт(ао от), и эти две системы неравенств доказывают равенство (2.!.2). Далее, для любого о| ж (оь ат) ~ и (оп а,) = ж (то о,) и для любого ои п(т~ от) ~ ж(т1 ти) = п(т~ от). Следовательно, (ть ои) является ситуацией равновесия; аналогично, равновесна и ситуация (аь ти). Эта теорема не имеет места для других игр: так, в игре, описанной в примере 1.4.2, (сть б1) и (ав би) являются ситуациями равновесия, но выигрыши в нпх различны и, кроме того, ни (аь ри) ни (ам ()1) ситуациями равновесия не будут, 11.
2. НОРМАЛЬНАЯ ФОРМА Как мы видели, нормальная форма конечной антагонистической игры сводится к некоторой матрице А с числом строк, равным числу стратегий игрока 1, и с числом столбцов, равным числу стратегий игрока П. Выигрыш — если игрок 1 выбирает Ью стратегию, а игрок П выбирает !'-ю стратегию — представляет собой элемент ап в Ьй строке и 1-м столбце этой матрицы.
Как вйяснится далее, ситуация (пара стратегий) будет равновесной тогда и только тогда, когда соответствующий ей элемент ам является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз в другом).
П.2.1. Пример. Матрица игры имеет седловую точку во второй строке и втором столбце. П.2.2. П р и м е р. Матрица игры не имеет седловых точек. 37 7!.8. Смешанные стратегии Предположим, что два игрока действительно участвуют в матричной игре. Выбирая стратегии, игрок 1 тем самым выбирает строку с, а игрок И выбирает столбец !.
Выигрышем будет элемент ам. Так как таковой будет сумма, которую ! получает от П, ясно, что игрок 1 будет стараться максимизировать ап, в то время как игрок И будет стараться его минимизировать. К сожалению, ни один из них не знает наверняка, какой будет стратегия противника, а это обычно имеет большое значение при решении вопроса о том, какую стратегию использовать, Например, при игре в орлянку (см. пример 1.3.2) можно представить себе, что игрок 1 рассуждает следующим образом; «Обычно игроки выбирают герб и потому И ожидает, что я выберу герб и выберет герб сам, так что я должен был бы выбрать решетку.
Но, возможно, и игрок И рассуждает таким же образом. Он ожидает, что я выберу решетку, так что мне лучше бы выбрать герб. Но, возможно, так же рассуждает и игрок И, так что...». В этом случае игрок 1 никогда не сможет принять решение, при котором он чувствовал бы себя уверенно, и исход игры оказывается неопределенным. Предположим теперь, что мы находимся в условиях игры из примера П.2.1. В этой игре игрок 1, наверное, решил бы применить либо первую, либо вторую стратегию, и можно было бы ожидать, что он рассуждает так: «Я должен был бы использовать либо первую, либо вторую стратегию, но если игрок И поймет это, он применит вторую стратегию, так что мне лучше использовать вторую стратегию».
Даже если игрок П отгадает стратегию игрока 1, то игроку 1 все равно лучше придерживаться ее! Таким образом, между этими двумя играми имеется огромная разница. В одной секретность важна, а в друтой она не имеет никакого значения. Причина этого состоит, конечно, в том, что вторая игра имеет седловую точку. 11. 3. СМЕШАННЫЕ СТРАТЕГИИ Проведенный выше анализ показывает, как играть в матричную игру с седловой точкой, но ие вносит никакой ясности в вопрос о том, каков наилучший выбор игрока в подавляющем большинстве игр, ие имеющих седловых точек.
Предположим теперь, что мы играем в игру без седловой точки, например в игру (' ') Мы не можем сказать, что произойдет. Однако допустим, что наш противник не только ведет себя непредсказуемо, но и всеведущ: он будет правильно угадывать любое наше решение. В этом зв Гл. I1. Антагонистические игра случае, если мы поставим себя на место игрока 1, то будем использовать первую стратегию, при которой мы не можем выиграть меньше двух единиц, в то время как при второй стратегии мы вынграем только одну единицу.
Этот гарантированный выигрыш по меньшей мере двух единиц есть наш «нижний выигрыш», который мы обозначим через о', = шах (ш1п а,. ). Если бы мы поставили себя на место игрока П, то выбрали бы (при тех же условиях) вторую стратегию, которая дала бы нам «верхний проигрыш» трех единиц. Обозначим этот верхний проигрыш через о,', пп'п (гпах а Ц ' Таким образом, для матричных игр мы имеем понятия нижнего выигрыша и верхнего проигрыша. Было бы нелепо ожидать, что нижний выигрыш игрока 1 превышает верхний проигрыш игрока П. И действительно, легко доказать, что (2.3.0) ( т о~ = оп. Доказательство этого неравенства элементарно и может быть предоставлено читателю.
Если в нем имеет место равенство,то мьв получаем седловую точку; если равенство не имеет места, то мы получаем игру без седловых точек. Для такой игры не определено, что же в действительности произойдет; можно лишь утверждать следующее: игрок 1 не должен вьшграть меньше, чем о,"„ игрок П не должен проиграть больше, чем о,'г Если в игре без седловых точек мы раскроем противнику нашу стратегию, то лучшее, на что мы можем рассчитывать, есть или «нижний выигрыш» о,', или «верхний проигрыш» о,', в зависимости от того, поставили ли мы себя на место игрока 1 или на место игрока П. Если же мы надеемся добиться лучшего, то не следует допускать того, чтобы противник знал нашу стратегию.
Это трудно осуществить, если мы вьгбираем свою стратегию на основании некоторых разумных соображений, так как ничто не мешает противнику воспроизвести наши рассуждения, Не собираемся ли мы этим сказать, что мы должны выбирать свою стратегию неразумно? Но какую пользу тогда представляет собой весь. наш анализ? Ответ состоит в том, что стратегия должна выбираться случайно — значит, не на основании каких-то разумных соображений,— но сама схема рандомизации должна выбираться разумно. В этом и состоит идея использования смешанных стратегий. //. 8. Смешанные стратегии зз П.3.1, Определение. Смешанная стратегия игрока есть вероятностное распределение на множестве его чистых стратегий.
В случае когда игрок имеет только конечное число т чистых ,стратегий, смешанная стратегия представляет собой и-вектор л = (х!,..., х ), удовлетворяющий условиям х!~0, (2.3.1) (2.3.2) Обозначим множество всех смешанных стратегий игрока 1 через Х, а множество всех смешанных стратегий игрока П че- рез У.
Предположим, что игроки 1 и П участвуют в матричной игре А. Если игрок ! выбирает смешанную стратегию х, а игрок П выби- рает у, то ожидаемый выигрыш будет равен А(х, у) =,'~', ~~.", х,а,/у/, ! !! 1 з/ли в матричных обозначениях: А(х, у) =хАут. (2.3 А) Как и прежде, игрок 1 должен опасаться, что игрок П раскроет его выбор стратегии. Если бы это случилось,то игрок П несомненно выбрал бы у так, чтобы минимизировать А(х, у); иначе говоря, ожидаемый нижний выигрыш игрока 1 в предположсиии, что он использует стратегию х, будет равен п(х) = ппп хАут (2.3.5) еы ! Далее, хАут можно рассматривать как взвешенное среднее ожидаемых выигрышей для игрока 1, когда он использует х против чистых стратегий игрока П.
Таким образом, этот минимум будет достигаться на некоторой чистой стратегии 1: о (х) = пп( п хА./ / (здесь А./ есть /-й столбец матрицы А). Поэтому игрок 1 должен выбрать х так, чтобы максимизировать о(х), т. е. так, чтобы получить о! = шах ппп хА./. (2.3.7) ешт / (Следовало бы доказать, что максимум существует; однако, так как Х компактно, а функция о(х) непрерывна, это очевидно.) Такая стратегия х называется максиминной стратегией игрока 1. Гл, П. Аитигоиистичеслие игам 40 Аналогично, если игрок 1! выбирает стратегию у, он будет иметь ожидаемый верхний проигрыш о(у)=шах Аьут (2.3.8) с (где Аь есть 1-я строка матрицы А) и должен выбирать у так, чтобы иметь оп = пп(п шах Аьут.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
