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

Чтобы получить 6з, мы должны исключить из Ез П С1 те элементы, которые доминируются элементами Кь Но единственная коалиция, которая может реализовать дележи из Кз, есть коалиция (2, 3); из вида Кз следует, что из Ез П Сг мы должны исключить те элементы, для которых хз < 1 и хз < 1.

Таким образом, 6з задается условиями Задачи 2!3 менты гтг будут принадлежать К» которое, следовательно, задается как объединение следующих множеств: 0(хз(1, ! ~хз(5, (!0.3.7) 1 ~ хз ~ 5, 0 ~ х, ~ 5, (10.3.8) хз -ь 5, хз ~ 3. (10.3.9) Условия (10.3.2) — (10,3,9) определяют три множества Кг, Кз, Кз. Множество !т = Кг () Кз () Кз есть единственное устойчивое множество (решение) в нашей игре (см. рис. Х. 3.1). (0,0,8) (0,0,6) (6,0,0) (0,6,0) (8,0,0) (0, о,гб) (0,8,0) (10,0,0) (0,10,0) Р и с, х. 3.1.

Задгямтз 1, Сумма любого числа мер также ввлветсв мерой. Показать, что если Р(яь ..., ры) — полинам от мер рь то Р можно представить в виде и1 лз ль Р сгчг +акта + ... +сечь, где сг — константы, ч; — меры, а аг — поло. жнтельные целые числа, Гя. Х. Модификации понятия игра 214 2. Для 8 ~ [О, Ц положим о(3) !»з(8))»(5), где к — мера Лебега, а р(8)- ~ яда. Найти функцию Шепли Ч»(о] этой игры. 8 3.

Завершить доказательство теоремы Х.3,4 (т. е. показать, что построенное в этом доказательстве множество )7 есть единственное решение). Для этого показать по индукции, что все К, К», ..., К, должны быть подмножествани некоторого устойчивого множества. 4. Игра и лиц без побочных платежей может н не иметь решения, Рассмотреть для этого простую игру о семи лиц, где Н вЂ” выпуклая оболочка пяти точек с (2, О, 2, О, 2, О, !), р» = (1, 1, 2, О, О, О, 0), рз (О О.!.1*2 0 0) рз (2 0 0 0 1 1 0) 0 = (О, О, О, О, О, О, 0), а минимальными выигрывающими коалициямн являются (1,3,5), (1, 2, 7), (3, 4,7), (5,0,7). Любая выигрывающая коалиция может навязать любой дележ, а ос- тальные коалиции являются эффективными только для таких дележей, в кото- рых члены этих коалиций получают О. Тогда игра о не имеет устойчивых мно- жеств (решений).

а) Ядро о есть просто (с). б) Если й» вЂ” отрезок (р»,с), то множество дележей, не доминнруемых точ- кой с, есть й» () (.з() йз, Если У устойчиво, то оно должно содержать по край- ней мере по одной точке»!» Ф с из яаждого».», в) Точки д» должны удовлетворять условию 4» дз д. Следовательно, У т т т содержит только по одной точке из каждого 1,ь отличной от с. Значит, У не- устойчиво и о ие имеет решений. ПРИЛОЖЕНИЕ И. 1. ВЫПУИЛОСтЬ Во всей этой книге широко использовалось понятие выпуклости. Ниже мы приведем некоторые свойства выпуклых функций; другие свойства их были указаны в основном тексте, а именно в гл.

11 и 11,г. П.1.1. Определение. Вещественная функция !(х), определенная в вещественном линейном пространстве, называется выпуклой, если для любых значений х, у независимой переменной и любого такого г, что О ~ г ~ 1, ) (гх + (1 — г) у) ~ г) (х) + (1 — г) ! (у). (1.1) Функция ! называется строго выпуклой, если при х Ф у н О ( г < 1 неравенство (1.1) будет строгим неравенством. П.1.2. Определение. Функция г называется вогнутой (строго вогнутой), если функция — 1 выпукла (строго выпукла), Следующая теорема указывает на очевидные свойства выпуклых функций, Доказательство этой теоремы не приводится.

П. 1.3. Т е о р е м а. Пусть )' и д — выпуклые функции, а с К О. Тогда функции ! + д, с! и шах (1, д) также выпуклы. Аналогично, если ) и й вогнуты, то вогнутыми являются функции 1+ д, с) и ппп (1, у). Легко показать, что линейная функция одновременно вогнута и выпукла. Обратно, если функция одновременно вогнута и выпукла, то она линейна. П.1.4. Определение. Множество Я с )', где $' — вещественное линейное пространство, называется выпуклым, если из х, у~8 н О ~. :г ~ 1 следует, что гх + (1 — г) у ен Я. (1.2) Таким образом, множество 5 выпукло, если отрезок, соединяющий две точки из Я, целиком принадлежит Я.

Для сравнения отметим, что функция выпукла, если хорда, соединяющая две точки графика этой функции, целиком лежит над графиком. Таким образом, множество точек, находящихся над графиком выпуклой функции, является выпуклым (этот факт часто берется в качестве 2!6 Приложение определения выпуклой функции). Эта связь между выпуклыми множествами и выпуклыми функциями отражается в следующей теореме которая в некотором смысле аналогична теореме П. !.3. Доказательство этой теоремы тривиально.

П.1 5. Теорем а. Пусть для а с=А множества 5„выпуклы (А — некоторое множество индексов), Тогда П 5„также выпукло. аул Очень часто нам дано невыпуклое множество К, а мы хотим использовать некоторую теорему, применимую только для выпуклых множеств. В таком случае нам необходимо связать с К некоторое выпуклое множество Н(К). П.1.6. Определение. Пусть К вЂ” произвольное множество. Тогда его выпуклои оболочкой Н(К) называется пересечение всех выпуклых множеств, содержащих К. По теореме П. !.5 выпуклая оболочка любого множества выпукла; ясно также, что если множество выпукло, то оно совпадает со своей выпуклой оболочкой. Существует, однако, другое определение выпуклой оболочки, а именно через выпуклые линейные комбинации. П.

1.7. О п р е д е л е н и е. Пусть х', хт, ..., хт суть р точек в некотором вещественном линейном пространстве. Тогда говорят, что точка у есть выпуклая линейная комбинация точек х', хз, ..., хр, если существуют вещественные числа сь ... с„, удовлетворяющие условиям (!) с! =-О, 1=-1, ..., р, (Й) ~ с! —— 1, (ш) у = ~~'.~с х'. Связь между выпуклыми линейными комбинациями и выпуклой оболочкой указана в следующей теореме. П.1.8.

Теорема. Для любого множества К выпуклая оболочка Н(К) совпадает с множеством 5 всех точек у„являюсцихся выпуклыми линейными комбинациями элементов из К, Доказательство. Легко видеть, что Кс: 5. Далее, 5 выпукло; действительно, предположим, что р у= ~~'., сгт', х', ..., хее-:К у=! и Р+ е у'= .~з~ с!х~, хр'', ..., хо+о~К, 1-р+! 2)7 П. и Выпуклость так что у, у'ен5, причем (с1,..., ср) и (ср+„..., с„+,) удовлетворяют условиям (!) и (В) определения П.

1.7. Тогда если О:-г~1, то р рл-р у"=ту+(1 — г)у'= ~(гс;) х1+ ~~.", (1 — г)сгхл. ! ! р+1 и числа (гс1, ..., гср, (1 — г)с„+ь ..., (1 — г)ср+ч) удовлетворяют условиям П.1.7 (!), (В). Следовательно, у" ен 5, так что 5 выпукло. Отсюда следует, что Н(К)с: 5. р Обратно, пусть у = ~ сгх', где х! ~ К, а с; удовлетворяют ! 1 тем же условиям, что и выше. Индукцией по р докажем, что у ен Н(К). Действительно, у = х' для р = 1, так что у я К с Н(К). Предположим теперь, что это утверждение верно для р — 1. Не умаляя общности, мы можем предположить, что с, ) О, так что р-! г = ~л~~ с;> О.

Тогда имеем 1 ! у = гу'+ (1 — г) хР, где р-1 у' = ~~~ (с;/г) х~. 1-! Ясно, что у'~5, так что по предположению индукции у'~ Н(К). Но х!' с Н(К). Ввиду выпуклости отсюда следует, что у я Н(К). Значит, 5 с: Н(К). Это включение доказывает теорему. Понятие выпуклой оболочки позволяет нам каждому множеству поставить в соответствие некоторое выпуклое множество. С другой стороны, иногда важно иметь представление выпуклого множества в виде выпуклой оболочки некоторого своего подмножества. П.1.9. Определение, Пусть 5 — выпуклое множество, а хан 5.

Мы будем называть х крайней точкой 5, если не существует двух таких точек х', хл из 5, что х' Ф х" и х =- (х' + хр)!2. Следующая важная теорема была использована в основном тексте этой книги. П. 1.1О. Т е о р е м а. Компактное выпуклое подмножество 5 и-мерного евклидова пространства является выпуклой оболочкой своих крайних точек, Кроме того, любая точка у~5 может быть представлено как вь!пуклая линейная комбинация не более и + ! крайней точки из 5. в!в Приложение Дока з а тел ь ство.

Ясно, что из второй части теоремы следует первая. Поэтому мы докажем только вторую часть, Доказательство ее мы проведем индукцией по и. Действительно, для и = 1 единственными компактными выпуклыми множествами является пустое множество 8, одноточечные множества и интервалы !а, Ь) Для пустого множества 1В' и одноточечных множеств теорема тривиальна; для интервалов (а, Ь1 ясно, что а и Ь являются крайними точками и любая точка у е4а, Ь) есть выпуклая линейная комбинация а и Ь. Предположим теперь, что теорема верна для и — 1.