Теория игр. Оуэн (1971) (1186151), страница 33
Текст из файла (страница 33)
Любой дележ нз ядра устойчив в том смысле, что ни одна из коалиций не имеет ни желания, ни возможности изменить этот исход игры. Конечно, в общем случае ядро может содержать более одной точки. Это не является существенным препятствием и попросту означает, что устойчивых исходов несколько. Более серьезная Гл. УИД Игры и лиц 172 трудность, связанная с ядром, состоит в том, что оно вообще может отсутствовать (т. е. быть пустым). 'т'1П.4.3. Теорема. Если о — существенная игра с постоянной суммой, то С(о) = 8'. Дока з а тел ьс та о. Допустим, что хан С(о).
Для любого (ен /»/ Х , ~ (й/ ' (1)), Уын ' »и но по определению игры с постоянной суммой о (/»/' (»)) = о (/з) — о ((»)) н, так как х является дележом, должно быть х» ~ о((»)). Из суще. ственности игры о следует, что ~ х, ~;~~ о((»))<о(/»/), и, следовательно, х~ Е(о). Полученное противоречие доказывает, что С (о) пусто. Поскольку ядро часто оказывается пустым, приходится искать некую иную концепцию решения.
Таким новым объектом изучения будут служить НМ-решения. Мы приведем сперва некоторые эвристические соображения, оправдывающие эту концепцию. В 5 Ч111. 2 мы привели пример игры трех лиц, характеристическая функция которой весьма просто записывается в следующей форме: — 2, если 5 состоит из одного игрока, о(Е) = 2, если Я состоит из двух игроков, О, если 5 состоит из трех игроков. Мы можем оставить игру в этой форме или привести ее к (О, 1)-редуцированной форме. (Для этого достаточно положить т = »/з, сз» вЂ”вЂ” »хз = аз = »/з ) В (О,1) -редуцированной форме эта игра становится простой игрой, в которой коалиции, состоящие из двух или трех игроков, выигрывают, а коалиция, включающая только одного игрока, проигрывает.
Для этой игры в (О,!)-редуцированной форме мы рассматриваем три дележа: ам=('/и '/з, О), о»з=(»/з, О, »/з), .„-(О,' /,', /,)' 173 !1111. 4. Ядро. НМ-решения как «решение». В каком же смысле они составляют решение? Легко видеть, что ни один из этих трех дележей не доминирует никакого другого из них. (Именно доминирование и заставило нас отвергнуть три слегка видоизмененных дележа в последующем варианте игрь!.) Конечно, это еще не все; любое множество, состоящее из единственного дележа, этим свойством обладает. Наше же множество дележей имеет, помимо этого, и следующее свойство: любой дележ, кроме трех дележей ап, доминируется одним нз дележей агр Чтобы это проверить, рассмотрим какой-нибудь дележ х = (хь хм ха). Так как мы рассматриваем игру в (О, 1)-редуцированной форме, то хг ~ О и х! + ха+ х, =!.
Следовательно, не более двух компонент вектора х могут быть не меньше !1а. Если их действительно Две, то кажДаЯ из них Равна !1а, в то вРемЯ как тРетьЯ равна О. Но это означает, что х совпадает с одним из ачн Если же х — какой-либо иной дележ, то у него не более одной компоненты, не меньшей чем !1ю Значит, по кРайней меРе Две компоненты, скажем х; и хь где г' < 1, меньше г1а. Но в таком случае ясно, что аи)!г, 11х. Мы, таким образом, приходим к следующему определению для нашей «концепции решения». Ч111.4.4. О и р е де лен не. Множество У~ Е(и) называется НМ-решением для о, если (1) из х,у е= У следует, что х ». у не может иметь места; (й) если х ф У, то найдется такой уев У, что у) х.
Таким образом, НМ-решение удовлетворяет как условию внутренней устойчивости (ни один дележ из 1' не доминирует другого), так и условию внешней устойчивости (любой дележ, не входящий в У, доминируется каким-нибудь дележом нз У). Впервые НМ-решения были введены фон Нейманом и Моргенштерном; их часто также называют просто решениями игры. Мы не будем использовать этот термин, поскольку позднее были выработаны многие другие понятия решения. Одна нз основных трудностей, связанных с НМ-решениями, состоит в том, что из определения не следует ни их существования, ни их единственности.
До сих пор не было дано общего доказательства существования НМ-решений. С другой стороны, до последнего времени не было построено н игры п лиц, ими не обладающей '); в действительности большинство игр имеет огромное количество НМ-решений (хотя существуют и такие игры, у которых НМ-решение единственно). г) Недавно была построена игра !О лин, не нмеющаи НМ-решений; см. 1. н с а а цг. г., А каще мНЬ но ао!окоп. мА!ЧО Мещогапбвгп мМ-5518-Рм. йА!ЧО Согрогаг!оп, Ос1оЬег 1967.
174 Га 17111, Игра п лич т/1!!.4.5. Пример. Рассмотрим снова игру трех лиц с постоянной суммой в (О, 1)-редуцированной форме. Как уже указывалось выше, множество ! (( /г /ь О)г ( /ь Оэ /г)ю (О /м /т)) является НМ-решением. Но это не единственное НМ-решение. Пусть с — любое число из интервала (О, '/т); легко проверить, что множество )гк г = ((ха 1 — с — х „с) ~ 0 ~ х, ~ 1 — с) тоже является НМ-решением. В это множество входят дележи, при которых игрок 3 получает постоянную с, а игроки 1 и 2 делят остаток во всевозможных пропорциях.
Внутренняя устойчивость следует из того, что для любых двух дележей х и у из этого множества, если х, ) уь то хг < дв Но доминирование по коалиции, состоящей из единственного участника, невозможно. Чтобы доказать внешнюю устойчивость )гк„возьмем какой- либо дележ У вне Ук, Это означает, что либо Уг ) с, либо дг < с. Пусть дг ) с, скажем, уг = с+ е. Определим дележ х следующим образом: х, = д, + е/2, х, = уз+ з/2, х, = с.
Легко видеть, что х~ )гк, и что х) у по коалиции (1,2). Пусть теперь уг < с. Ясно, что либо у~ =' Ъ либо ут ( '/г (ибо в противном случае их сумма была бы больше 1). Пусть у~ -= '/ь Положим х=(1 — с,О,с). Так как 1 — с) '/, ~уь то х)у по коалиции (1, 3). Очевидно, что х ен Уг,, Если же дг ~ '/г, мы покажем аналогично, что х ) у, где г = (О, 1 — с, с). Итак, мы видели, что, кроме симметричного НМ-решения, наша игра имеет еще целое семейство решений, при которых игрок 3 получает фиксированное количество с из интервала (О, '/г). Этн НМ-решения называются дискриминируюи4ими; говорят, что игрок 3 при этом дискриминирован. В случае множества )гг е говорят, что игрок 3 полностью дискриминировак или исключен. По соображениям симметрии очевидно, что существуют также два семейства НМ-решений Ук, и Ук „в которых дискрнминируются игроки 1 и 2 соответственно. Предшествующий пример показывает, что у игры может быть чрезвычайно много НМ-решений.
Совершенно неясно, какое из этих решений следует выбрать. Когда же НМ-решение выбрано„ остается непонятным, какой из него выбрать дележ. Фон Нейман и Моргенштерн утверждают, что НМ-решения отражают нормы поведения, свойственные данной социальной структуре. Когда же общество выбрало норму поведения (НМ-решение), дележ определяется деловыми способностями игроков. Ч111.4.
Ядро. ЯМ-решения Как уже отмечалось выше, существование НМ-решений в общем случае до сих пор не было доказано, однако получены некоторые частные результаты. Некоторые из этих результатов касаются существования НМ-решений для конкретных классов игр, другие — существования решений определенного типа. И2, , 112) Ряс. ЧШ.4.1. Трн НМ-регпення игры трех лнн с постоянной суммой. Рассмотрим несколько таких теорем. 71П.46. Теорема. Пусть о — простая игра в (О,!)-редуцированной форме, и пусть 5 — минимальная выигрывающая коалиция (т.
е. такая коалиция, что о(5) = 1, но о(Т) - О для любой коалиции Т с: 5, Т Ф 5). Обозначим через )тв множество всех таких дележей х, что х; = О для всех (ф 5. Тогда )гн есть НМ-ретиение. Доказательство. Эта теорема доказывается так же, как и тот факт (прнмер ИП.4.5), что множества тк, являются НМ-решениями. Теорема ЧП1. 4.6 устанавливает, что любая простая игра имеет дискриминирующие НМ-решения, в которых минимальная выигрывающая коалиция исключает остальных игроков. В некоторых случаях днскриминированные участники могут получать небольшие !7Б Гл. ИП. Огрм л лич суммы (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
