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

Предположим, что У имеет такой вид и что коалиция (Е, Е) строго эффективна для х. Тогда имеем ов'((Е, Е)) ~ и((Е, Е))>х,+хи Но так как дележ х реализуем разбиением У, имеем также хс + хе + хи+ х, = 1) У )) = о'г ((Е, Е)) + о'" ((й, Е)) и, следовательно, хи+ х, > о" ((й, Е)) ) и ((Ег, Е)), Таким образом, коалиция (Й, Е) не является эффективной для х. Переходим теперь к доказательству теоремы Х. 3.4.

Игра четы- рех лиц имеет 15 разбиений Уь Уя, ..., Ум, перенумеруем их в по- рядке убывания норм; ))Уе)1>))Уе+,)) для Е = 1, ..., 14. Обозначим через Е; множество всех таких дележей х, что ~~'.) х,= !5 ))Уе)); это даст нам множествоЕ = ЦЕ,. Затем для Е = 1, ..., 1Ь 1 введем срезанные ядра о,=), я( Х,м,~м~ я, - ° м цп,) дым и-1 и положим Са = Е. Легко видеть, что Се с: Се ь Пусть т — такое наименьшее целое Е, что Се П Е;+~ — — Еа. Если С, ПЕ,+~ чьИ при Е = 1,..., 14, то положим т = 15.

Заметим, что т > О, так как Са () Е = Е1 Ф Ео. Наконец, определим множество Ег= й(Е ПС, ). Е-1 Х. 8. Игры, заданные в форме функции разбиения 209 Х.3.8. Лемма, Пусть Š— такое подмножество Я, цто каждый дележ хек Я',Е доминируется некоторым дележом уев К. Тогда каждьгй хек Е'; )с доминируется некоторым у ен К. Доказательство. Если хяЕ'~Я, то хенЕг для некоторого 1, и существует некоторое М е= Уь где 1' =.

ппп (гп, 1 — 1), которое строго эффективно для х. Выберем Мое=-У, так, чтобы з было минимально, т. е. Ма~У, строго эффективно для х, но если М енУь где 1' ~ з — 1, то М не строго эффективно для х. Выберем так г ~ Ее, чтобы Мо было эффективно для г и чтобы для всех 1~М выполнялось неравенство г; хо Тогда ген Е, П С,, с: Я.

Если г ~ Е, то г) х по М, и г есть искомый у. Если же гф Р, то некоторый ус=-Е доминирует г, и по лемме Х.3.6 у) х. Следовательно, в любом случае х доминируется некоторым у е= )с'. Х.3.9. Лемма. Если Š— решение, то Ес: Я. Доказательство. Пусть хе= Е'; Я. Как и в лемме Х.38, существует такой г~ Я, что г) х, и если у) г, то мы должны иметь у) х.

Тогда, если ген Е, то мы не можем иметь х енес; если же гцй гс', то существует такой у е= й, что у) г, Но тогда у)х и, следовательно, х Ф гс. Х.3.10. Доказательство теорем ы Х.3.4. Ввиду предыдущих лемм достаточно доказать, что Я содержит единственное решение. Мы докажем зто утверждение, построив для 1 = 1, ..., и подмножества йг~с: Е; П С, 1 и показав, что ЦЯ~ — — гс является / ! решением. Прежде всего предположим, что К содержит все элементы множества Еы П С и максимальные по отношению ). Так как )и есть'отношение частичного упорядочения н множество Е П П С, компактно, из леммы Цорна следует, что для любого хе-= е=-Е П С ь не являющегося максимальным по отношению )и, существует такой у, максимальный по этому отношению, что у)мх.

Но это означает, что М эффективно для у и строго эффективно для х. Следовательно, М с= У„, поскольку х ~ С,„, и, значит, у реализуем для М. Далее, не существует такого генЕ П С, ь что г)у. Действительно, предположим, что г) у по 5. Это означает, что 5 строго эффективно для у и что г, а следовательно, и у реализуемы для 5. Но 5 Ф М, и поэтому в силу леммы Х.3.7 М не может быть эффективно для у. Следовательно, у максимален в Е„,П С г по отношению ), и, значит, у~ Я,„= К .

Итак, мы видим, что любой хе=Е П С,' Е доминируется некоторым у~Я . Кроме того, ввиду максимальности по отношению ), никакой х ен Е не доминирует никакого у е= Е . Гя. Х. Модификации понятия игра! 210 Продолжим построение множеств К ь К .я... К! следующим образом. Предположим, что множества К, К .!, ..., К/+я мы уже построили. Пусть Я/~, = Ц Кп Тогда пусть О; — подмно/+! жество Е; П С; „состоящее из дележей, которые не доминируются никаким элементом из /т/+!.

Пусть К/ — подмножество Оь состоящее из максимальных (в О;) по отношению ) элементов. Снова заметим, что О; компактно, и поэтому каждый хе= О/, К/ домииируется некоторым уев К; и, следовательно, каждый хин Е/Й П С/ !' К/ доминируется некоторым ден /(/= Ц К!. / Примем теперь в качестве предположения индукции, что никакой элемент из /!!/+! не доминирует никакого другого элемента из Я/+! и что если хин Ц(Е!ПС!-!)' й/+! /+! ()) хе=/с/+„ (И) хе=/с/+„ (гй) х еК/, (!!/) хе= К/, у ен Р/+!', дев К/, У~ Р/эб д ив : К/. В случае (!) по предположению индукции мы не можем иметь х)у. В случае (И) мы не можем иметь х) у„так как дан О; и хан/г/+!.

В случае (!И) мы не можем иметь х)у, так как эт!ь означало бы, что некоторое М АУ/ строго эффективно для у; но де=-Сь так что это невозможно. Наконец, в случае (1ч) мы не можем иметь х) у, потому что как х, так и у максимальны в О/ п/ь отношению ). Таким образом, если х и у принадлежат /с/, то мьа не можем иметь х) д. С другой стороны, пусть хе=Ц(Е!() С! !) ~ /г/. Тогда либо ! (!) хен Д(Е!ЙС! !); /т/+„ /+! либо (!!) Е/() С/ ! .

К/. В случае (!) по предположению индукции существует такой у !-: ен/!!/+т, что у) х. В случае (И) мы видели, что существует такой то существует такое у ~ Я/+т, что у ) х. Предположим, что как х, так и д принадлежат /(/. Так как /г/ = /г/+! () Кп имеется четыре возможности: Х. 8, ИгРы, заданные в форме функции разбиения 2!! уев Кь что у) х. Итак, в любом случае существует такой уен Еь что у)х. Продолжая таким образом, мы придем к множеству Е = яо которое удовлетворяет условиям леммы Х.

3.8 и, очевидно, внутренне устойчиво. Следовательно, гг будет решением. Теперь мы должны показать, что Š— единственное решение. Доказательство этого факта нетрудно провести, и оно предлагается в качестве задачи (задача Х. 3). Доказательство теоремы Х.3.4 использует лемму Цорна, но в такой незначительнои степени, что практически является конструктивным. Ниже мы приведем пример того, как это доказательство можно использовать для нахождения решения. В силу того, что множество всех дележей есть объединение большого числа симплексов,мы будем рассматривать только игры трех лиц. Далее.

в то время как игры четырех лиц имеют 15 разбиений, игры трех лиц имеют только 5 разбиений. Следовательно, игра трех лиц гораздо проще. Можно показать, что теорема Х.3.4 верна также и для игр трех лиц. Х.ЗЛ1. П'ример. рассмотрим игру трех линн гдеУ1=((1, 2),(3)), .'У',=и1, 3), (2Ц, Уз=((Ц, (2„3)), У,=Ц1,2,3И, Уз=(И, (2), (3)), а ов' Н1, 2)) = 5, оР'((3)) = 5, о'"*((1, 3)) = 5, оР*((2)) = 3, оРг((2, 3)) = 6, огг ((1)) = О, ов' ((1,2, 3)) = 4, ов'((1)) =О для ю'= 1„2,3. Отсюда получаем !!У1!! = 10, !!Уз!! = 8, !!Уз!! = 6, !!Уз!! = 4, !!Уз!!= =О и и((1,2)) = и((1, 3)) = 5, и((2,3)) = 6, и((1)) = О.

Легко видеть, что Ез П Сз Ф Я, а Ее П Сз = кг, так что ог = 3. Построим Е следующим образом. Заметим прежде всего, что Ез — симплекс неотрицательных векторов, сумма компонент которых равна 6; множество Ез П Сз будет состоять из тех элементов Ез, которые удовлетворяют неравенствам х,+хе~5, х,+хе~5, мли, что эквивалентно, ха~1, хе~1 Далее, доминирование в Ез может иметь место только по коалиции (2,3). Следовательно, Кз состоит из тех элементов Ез П Сь которые максимальны по отношению ) по коалиции (2, 3). Теперь, если хз < ! и хз < 1, то у ) х, где у = (4, 1, 1) .

С другой стороны, если либо хз = 1, либо хз = 1, то х не может доминироваться Г.и Х. Модификации оокятия игры 212 в Ез П Сз, Следовательно, К, есть объединение двух сегментов ха=1, ОЫхзЯ! (10.3.2) О~х =1. (10.3.3) хз=1, Х~ + Хз + Хз = 8г хз ~ 3. хи~ 1 или хз~ 1. Далее, нам нужны элементы в 6з, максимальные по отношению ).

Так как (1,3) — реализующая коалиция, то любой такой х, что лг + х, < 5, х, < 3, будет доминироваться некоторым у е- =6з. Тогда легко показать, что Кз есть объединение трех множеств 0 == хз ~ 1, 1 г хз ~ 3, 1~Хи~3, 0~ха~3 (10.3.4) (10.3.5) (10.3,5) хз — — 3. Рассмотрим теперь множество Ег П Со — — Еь Оно состоит из всех неотрицательных векторов, сумма компонент которых равна 10.

Чтобы получить 6ь нам необходимо из Е1 исключить все дележи, которые доминируются элементами из йз = Кз () Кз. Но дележи, которые доминируются элементами из Кз, задаются неравенствами хз < 1, ха < 1, а дележи, доминируемые элементами из Кз — неравенствами хг + хз < 5, хз(3. Таким образом, бз задается усло- виями хи~1 или хз~1, хз ~ 5 или хз — 3. Далее, можно показать, что 6з содержит все дележи из Е, для которых хз = 5, Следовательно, если уз < 5, то у будет доминироваться некоторым х еи 6~ по коалиции (1,2). Все остальные эле- Рассмотрим теперь множество ЕзП Сь Множество Е, состоит из неотрицательных векторов, сумма компонент которых равна 8; Ез П Сз состоит из тех элементов Еь которые удовлетворяют также неравенству х, + хз ~ 5, или, что эквивалентно, хз ~ 3.