Теория игр. Оуэн (1971) (1186151), страница 35
Текст из файла (страница 35)
Доказательство. Во-первых, множество )т внутренне устойчиво. Действительно, доминирование может иметь местотолько гзг УПI. Б. Модель рынка ио Зд»еворту по такому множеству В, что В П М Ф'О и В П Ь/Ф 8. Но если х, Уев У и х; > Уг пРи некотоРом г' АМ, то х; < У; пРи всех / еи Ь/. Следовательно, х не может доминировать у, Пусть теперь хы У. Тогда найдется некоторая пара (г,/)„где (еи М, а /ги гЧ, такая, что х;+ х; <2гр(а/2, Ь/2).
Выберем вектор (гг, гг) так, что гг > х; и гг > хь Ясно, что дележ у е= У, соответ- ствующий вектору (г„гг), доминирует х по коалиции (г,/). Итак, У и внешне устойчиво. Конечно, предыдущие рассмотрения показывают, что НМ-реше- ния не обнаруживают тенденции к «сжатию» при возрастании л. Но ядро зту тенденцию имеет. Мы рассмотрим два случая: моно- полию (игра [1, и)) и чистую конкуренцию (игра [т, л), где как т, так и л велики). Ч1П.5.3. Теор ем а. В игре [1,л) дележ х, для которого х", = гр(0, Ь) ири всех /'в= гЧ, принадлежит ядру.
Кроме того, ка- ково бы ни было е > О, найдется такое л(е), что если п г п(е), то никакой дележ у, для которого уг ~ х, — е, не принадлежит ядру.. Д о к а з а т е л ь с т в о. Доминирование возможно только по коа- лиции, включающей 1. Если хг — наибольшее допустимое, то ясно, что х ~ С (о). Рассмотрим теперь выражение о(/) — о(/~,Ц) — гр(0, Ь), где / с=Лг. Если мы заменим о его значением (8.5.6) и воспользуемся теоремой Тейлора, мы увидим, что для любого е > 0 при доста- точно большом и(е) 1 о(/) — о (/',(/)) — г[г(0, Ь)! <е/п для всех п ~ л(е).
Предположим теперь, что у — дележ в игре [1, л), дли котоРого Уг аг: х, — е. Должно найтись такое /ен/Ч, что у; ~ гр(0, Ь)+ е/и (так как ~уг = х, + лгр(0, Ь)). Поэтому ясно„ что у, ~ о(/) — гь(0, Ь) — е/и<о (/",(/)) г~г пг и у ейС(о), Теорема ЧП1. Б.З описывает случай монополии. Случай чистой конкуренции характеризуется следующей теоремой. ЧП1.5.4. Теорема.
Пусть т' и л' таковы, что гр[, „... „,) =шахгр~ —,, — ", ). (8.5.10) Тогда для игры [т, п), где т = йт', а п = йл', дележ Гл Ч///. Игры и лня 182 всегда принадлежит ядру. Более того, для любого е ) 0 найдется такое /г(е), что при й =" й(е) никакой дележ, в котором одна иэ компонент меньше — — е,не принадлежит ядру игры [йт', йп') о (/) и+и Мы опускаем доказательство этой теоремы, так как оно совершенно аналогично доказательству теоремы Ч111. 5.3.
Равенство (8.5.!О) выражает тот факт, что соотношение размеров множеств М и /э/ оптимально (например, в случае, когда наличный капитал точно соответствует количеству предлагаемого труда). Если же М и /Ч находятся в ином отношении, то возникает неприятное несоответствие (безработица или недостаток рабочей силы) и в случае достаточно большого числа участников игра вообще не имеет ядра. Но если (8.5.10) выполняется, то всегда существует ядро, стягивающееся к единственному дележу х, и наша игра может благополучно развиваться в обстановке всеобщего счастья. Задачи 1. а) В игре и лиц ядро являетси подмножеством любого НМ-решения. б) Если ядро имеет непустое пересечение со всеми гранями х, - о((э)) , симплекса дележей, то ядро является едннственвым НМ-решеннем игры аз), н обратно. в) Положительная доля (подмножество полной размерности) множества игр п лнц (в (О, 1)-редуцированной форме) имеет единственное НМ-решение (теорема Ч! П.
4.7). 2, Для игры о определим полудележ как вектор х = (хь ..., х ), для которого хг ле о((з)) н ~~~~ х ~ о(йг) Тогда, если Ч есть НМ-решение игры о зэзя и х — полудележ, ве принадлежащий У, то существует такой у щ \', что у) х. 3. Для игры о определим Ьэ соотношением Ьг - гпах [о (5 ()(0) — о (5)1. 3 ю и ', (э'1 ') Это утверждение неверно, как показывает следующий пример, построенный в 1967 г, студенткой ЛГУ Т. Е.
Кулаковской (см. [Ч1!!. 13'[). Рассмотрим игру четырех лиц с характеристической функцией о, заданной следующим образом: ! о(5) =з/э, если [5[=3, о((1, 2, 3,4))=1, о(5) = О в остальных случаях. Ядро этой игры является выпуклой оболочкой точек ('/з '/з '/э О) ('/з '/з О /з). ('/з О /з '/з) (О '/з. /з '/э) и, таким образом, пересекаетсн со всеми гнперплоскостями хс О, э 1,2,3,4. Легко видеть, что ядро не будет НМ-решением. Справедливость обратного утнерждения была впервые установлена О. Н. Бондаревой [Ч!11. 12').
— Прим. ред. Задачи 183 Показать, что если найдется С, для которого х~ > Ьь то дележ х не может принадлежать ядру н не может принадлежать ни одному иэ НМ-решений, 4. Показать, что можсю получить главное простое решение симметричной игры, следующим образом обобщив рассмотренное в примере У!1!. 4.5 построение симметричного НМ-решевия У для простой игры трех лнц. Пусть о — простаи игра и лиц с постоинной суммой в (0,1)-редуцированной форме. Предположим, что существует вектор а = (ас, ..., а ), для которого ац ~ 0 и ~~ ас 1 для любой минимальной выигрывающей коалиции 5.
с ««3 Для такой коалиции определим вектор хз соотношениими: хз=оп если Сщ5, хг =0 в противном случае. Тогда хз — дележ и множество У = (хз) 5 — ииннмальная выигрывающая коалиция) является НМ-решением для игры о, называемым главным простым решением. 5. Рассмотрим простую игру и лиц в (О, 1)-редуцированной форме, в которой выигрывающие коалиции состоят нз а) игрока ! и еще хотя бы одного игрока, б) из множества (2..., и). а) Найти главное прас~ос решение этой игры. б) Пусть Ув для 5 (1,Д, где 1~1, состоит из всех дележей, для которых х, + хс = 1, и пусть Уз для 5 = (2, ..., л) состоит нз всех дележей, для которых х, = О. В обоих случаях Уз является НМ-решением. в) Пусть для 5 = (2, ..., и) н 0 = с ~ 1 множество Уг(с) состоит из всех дележей, для которых х, = с.
Тогда Ух(с) будет НМ-решением при 0 ~ с ( (и — 2)/(л — !), но ие при с) (и — 2)/(и — Ц . г) Для 5 = (1, 1) единственным НМ-решением, дискриминирующим членов множества У~,З, является множество Уз, определенное выше в б). 6. Композиция простых игр. Пусть пыла, ..., о„— простые игры в (0,1)-редуцированной ферме, имеющие ты»,, т игроков соответственно, и пусть ш — простая игра л лнц в (0,1).редуцированной форме. Пусть Ус, У,, ..., У„, Ю' предстаалвют собой НМ-решения игр оь а„.... а„, ы соответственно.
Образуем простую игру т лиц и (где т = тс+ тз+...+т„) следующим образом. Поставим в соответствие каждому из т игроков упоридочениую пару (с',1), где 1 ~ с ~ и и ! ~ с' ~ ть Коалицию же 5 будем считать выигрывающей в том и только в тои случае, когда она содержит подмножество 5' вида 5 = Ц 5/Х(/), /юг где Т вЂ” выягрывающая коалиция в ш, а каждая Зс — выигрывающая иоалиции в и» (Эвристически это можно представить себе, как «распадение» игры иа л «комитетов» мс х (/).) Каждой паре хс см У; и усы Ф' сопоставим т-вектор г с компонентамн хссу/. Показать, что множество всех таких г ивляетси НМ-решением «со/ ставной» простой игры и.
7. Рассмотрим простую игру о со счетным числом игроков, в которой коалиция является выигрывающей в том и только в том случае, когда ее дополнение конечно. Если о — игра в (О, !)-редуцированной форме, то Е(а) состоит из всех последовательностей (хи хи ...) неотРсщательных чисел, дла котоРых чз„хс=). Йгра э не имеет НМ-решений.
(Показатсч что ни одни дележ ие может принадлежать НМ-решению.) Гл. )г/П. Игра и лиц 8, Пусть о — простая игра четырех лиц в (О, 1) -редуцированной форме с вынгрывающими коалициями (1,2,4), (1,3,4), (2,3,4) и (1,2,3,4). Пусть С— любое замкнутое подмножество интервала [0,1), а Х вЂ” множество всех векторов л=(0, (1 — и)/2.
(1-и)/2, и), где и еэ С. Тогда у игры о существует такое НМ-решение (г, что /г= 1', н прн этом оба множества. Х и 4г~,l замкнуты и не пересекаются. а) Положим р(и, С) ш!п (и — о(. Пусть К- множество всех дележей в нд эс С ((! — и — р (и, С) )/2, л, р, и) для всех игп[0, Ц. Показать, что К замкнуто и К () ХцьЯ, б) Рассмотрим множество Н, состоящее из всех дележей из К, которые доминируются каким-либо дележом иэ Х.
Тогда У ' г'() (К ', И) и есть искомое НМ-решение. 9. Доказать теорему Ч!П. 5.4. Глава 1Х ДРУГИЕ ПОНЯТИЯ РЕШЕНИЯ В ИГРАХ !в ЛИЦ 1Х. 1, ВЕКТОР ШЕПЛИ То обстоятельство, что ни одна общая теорема существовании 'решения в играх л лиц пока не доказана, заставило математиков искать другие понятия решения. Одним из таких понятий является вектор значений игры, введенный Шепли (значение по Шепли).
Шепли подходит к своему понятию значения аксноматически. Сначала мы дадим два определения. 1Х.1.1. Определение. Носителел игры о называется такая коалиция Т, что о(5) = п(5 П Т) для любой коалиции 5. Содержательно определение 1Х. 1.1 утверждает, что любой игрок, не принадлежащий носителю, является «болваном», т. е. не может ничего внести ни в какую коалицию. 1Х.1.2. Определение. Пусть о — игра л лиц, а и — любая перестановка множества У.
Тогда через ло мы обозначаем такую игру и, что для любой коалиции 5 =(!ь (м ..., (,) и ((и (с1), л (!2), ..., и (1,))) = о (5). По существу игра ло отличается от игры о лишь тем, что в последней игроки поменялись ролями в соответствии с перестановкой и. С помощью этих двух определений можно изложить аксиома- тику Шепли. Заметим только, что так как игры в сущности отождествляются с вещественными функциями, можно говорить о сумме двух или большего числа игр, а также о произведении игры на число.
1Х.1.3. Аксиом ы (Ш еп л и). Под вектором значений игры о мы будем понимать л-вектор <р(о1 удовлетворяющий следующим аксиомам: 8!. Если 5 — любой носитель о,то .с) чч(п) = п(5). $2. Для любой перестановки и и ! ~ М р. „,(по) = р,(о).
Гл. /Х. Другие понятия решения е играх л лия 1ЗВ 33. Если и и о — две любые игры, то ф«[и+ о[=ф«[и1+ф,[о1. Таковы аксиомы Шепли. 11римечательно, что этих аксиом ока. зывается достаточно для определения единственным образом зна. чения ф для всех игр. 1Х.1.4. Теорема. Существует единственная функция ф, определенная для всех игр и удовлетворяющая аксиомам 5! — 53. Доказательство теоремы 1Х. 1.4 дается следующей цепочкой .лемм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
