Теория игр. Оуэн (1971) (1186151), страница 36
Текст из файла (страница 36)
!Х.1.5. Лемма. Пусть для любой коалиции 5 игра и«в апре. делается следующим образом: (О, если 5~йТ, 11, если 5с=Т. -Тогда, если з — число игроков в 5, то ( 1/з, если 1ен 5, 1 О, если 1Ф5. Доказательство. Ясно, что 5 — носитель н«в, так же как и любое множество 7', содержащее множество 5. Тогда по аксиоме 81, если 5с Т, то ~ли~ ф«[гве«1. т Но это означает (так как возможно также равенство 5 = Т1, что ф«[«вг[ = О для 1ф5. Далее, если я — любая перестановка, которая переводит 5 в себя, то ясно, что яи«в = и«в. Следовательно, в силу 82 для любых 1, 1 ~ 5 будет ф«[гвв1 = ф«[гав[.
Так как этих величин всего з, а сумма их равна 1, то ф«[вв1= 1/з, если 1ен 5. 1Х.1.6. Следствие. Если с) О, то ( с/з, если рен 5, ф«[ з1 !Х.1.7. Лемма. Если о — любая игра, то для 5~!У существует 2" — 1 таких вещественньчх чисел св, что о = ~~'.~ сзюз, все где «вв определена в лемме 1Х. 1.5. ГХ. Д Вектор Шекли 181 Доказательство. Положим сз= ~ ( — 1)' о(Т) тсз (9.!.1) Х с. з((7) = Х Ь= Х [ Х (-1)'-'. (Т)) = зсу зси з и~1 з (-1)' о (Т). т и]зси ~,в т Рассмотрим теперь величину в скобках в этом последнем выражении. Для каждого значения з между 1 н и имеется С, ] таких множеств 5 с э элементами„что Тс= 5 с: У. Следовательно, выражение в скобках можно заменить на Но это — в точности бнномиальное разложение (1 — !)" '.
Следо- вательно, для всех Г < и оно равно О, а для Г = и она равно 1. Поэтому для всех У ~ йГ Х сказ((7) = о ((7). зси Теперь мы можем перейти к доказательству теоремы 1Х. 1.4. Действительно, лемма 1Х. 1.7 показывает, что любая игра может быть представлена в виде линейной комбинации игр тиз. По лемме 1Х.1.5 для таких игр функция ~р определяется единственным образом. Далее, некоторые из коэффициентов сз отрицательны; однако нз аксиомы 33 легко видеть, что если и, о и и — о являются играми, то 4и — о] = я~[и] — ~р[о]. Тогда по аксиоме 33 функция у для всех игр о определяется единственным образом.
Для функции чт мы можем также дать явное выражение. Мы знаем, что О .К~ Сз1из Яск и, следовательно, 1р,[о] =,'~Е се~р,[вз] = ~~'„~ сз (1/з). (здесь à — число элементов в Т). Мы покажем, что эти числа сз удовлетворяют условиям леммы. Действительно, если У вЂ” любая коалиция, то Гж Сяг другие понятия решения в играх и яия Но сз определены приведенной выше формулой (9.1.1); подставляя ее в это выражение, получаем срс[о[ии ~~'.с (1/з)1 ~~'.~ ( — 1)' о(Т)~, эссс 1т э ссэ йс[о)= Х ~ Х (-!)' '(1/з)о(Т) . !.
т йсс! с и (9.1.2) Положим (9.1,3) щ [о) = я!с ус (Т) [о (Т) — о (Т ', Я)). т и сит Далее, если с ен Т, то имеется ровно С„':сс таких коалиций Я с з элементами, что Т г:.$. Следовательно, мы имеем Ус(Т) = ,')', (-1)*-'С'„с!э = ,')'( — 1)*-'С*„с, ~ х'-' а = г с е с о ! п = 1 Х(-1)'-'С*;сх'-' !х= О е с ! и ! = ~ х' ' )' ( - 1)' С„':сх' с(х = ~ х' с(1 — х)" ~с!х. о е с Но это — хорошо известный определенный интеграл; имеем, таким образом, у, (Т) = (! — !)! (л — !)!!п! и, следовательно, р,[о)= ,')~ " '"„(" "'[ (Т)- (Т,[!))). (9.1.4) т с у сшт Формула (9.!.4) дает вектор Шепли в явном виде. Легко проверить, что это выражение удовлетворяет аксиомам 3! — 33.
Кроме того, легко видеть, что сумма коэффициентов ус(Т) равна 1. Действительно, числитель равен числу перестановок из йс элементов, Легко, видеть, что если с ф Т' и Т = Т'О(!), то ус(Т') = — ус(Т). Действительно, все члены в правой части (9.!.3) будут в обоих случаях одни и те же, за исключением тога, что й= !'+ 1, и, сле.довательно, будут отличаться лишь знаком. Значит, мы будем иметь 1Х. Л Вектор Шелли в которых элементу ! предшествуют в точности элементы из Т, а знаменатель равен общему числу перестановок.
Ввиду супераддитивности выражение в квадратных скобках всегда не меньше о(И). Следовательно, В[о] а о((1)), (9.1.5) так что ф[о] всегда является дележом, Если отвлечься от аксиоматического определения, то вектору Шепли, выраженному формулой (9.1.4), можно дать следующее содержательное истолкование. Предположим, что игроки (элементы множества й!) решили встретиться в определенном месте в определенное время.
Естественно, что из-за случайных флуктуаций все они будут прибывать в различные моменты времени; однако предполагается, что все порядки прибытия игроков (т. е. их перестановки) имеют одну и ту же вероятность, а именно 1!и!. Предположим, что если игрок 1, прибывая, застает на месте членов коалиции Т',(!) (н только их), то он получает величину о(Т) — о(Т' (!)); иначе говоря, его выигрышем является предельная величина, которую он вносит в коалицию. Тогда компонента вектора Шепли ф;[о] представляет собой математическое ожидание выигрыша игрока 1' в условиях этой рандомизационной схемы.
В случае когда игра о проста, формула для вектора Шепли также становится особенно простой. Действительно, о(Т)— — о(Т",Я) всегда будет либо О, либо 1, причем это выражение равно 1, если Т вЂ” выигрывающая коалиция, а коалиция Т'~(!) не является выигрывающей. Следовательно, мы должны иметь ф, [о] = ~~'.~ (! — 1)! (а — !)!/п1, г где суммирование распространяется на все такие выигрывающие коалиции Т, что коалиция Т',(!) не является выигрывающей.
1Х. 1.8. П р и м е р. Рассмотрим корпорацию из четырех акционеров, обладающих соответственно 10, 20, 30 и 40 акциями. Предполагается, что любое решение может быть утверждено акционерами, имеющими простое большинство акций. Эта ситуация может рассматриваться как простая игра четырех лиц, в которой выигрывающими являются коалиции: (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4) н (1, 2, 3, 4). Мы хотим найти вектор Шепли для этой игры.
Для того чтобы найти фп заметим, что единственная выигрынающая коалиция Т, такая, что коалиция Т~,(!) не является выигрывающей, есть коалиция (1, 2, 3). Следовательно, так как 1= 3, ф1= 2! 1Ч4! ='!м Гл. 1Х, другие понятия решения в играх п лиц Аналогично находим, что коалиции (2, 4), (1, 2, 3) и (2, 3, 4) являются выигрывающими, но каждая из них перестает быть выигрывающей, если из нее устраняется игрок 2. Поэтому В = '/ + '/ + '/ г = '/г. Точно таким же образом находим, что рг = '/4, а ерг = г/и Следовательно, вектор Шеплн есть вектор ('/иь '/,, '/г,е/м).Этотвектор ие совпадает с «вектором голосования», которыи равен (%о, ~/г г/~о, г/г), Заметим, что компоненты вектора Шепли для игроков 2 и 3 равны, хотя игрок 3 имеет гораздо больше акций.
Это неудивительно, так как у игрока 3 не больше возможностей для образования выигрывающей коалиции, чем у игрока 2; в игру, рассматриваемую как характеристическая функция, эти два игрока входят симметрично. Точно так же ясно, что «сила» игрока 4 больше, чем доля его акций, а «сила» игрока 1 меньше его доли акций. !Х.1.9. Пример.
Рассмотрим игру, аналогичную предыдущей, за исключением того, что игроки имеют соответственно 10, 30, 30 и 40 акций. Можно показать, что любые два игрока из множества игроков 2, 3, 4 образуют выигрывающую коалицию, а игрок 1 не может ничего внести ни в какую коалицию. Таким образом, вектор Шепли равен (О, Чг, '/г, Чг): акции игрока 1 бесполезны, а избыточные акции игрока 4 не дают ему преимущества по сравнению с игроками 2 и 3. 1Х.
2. УСТОИЧИВЫЕ МНОЖЕСТВА Одна из трудностей, связанных с понятиями, которые мы до сих тюр изучали, состоит в том, что, вообще говоря, эти понятия, повидимому, не объясняют того, что происходит в любой партии игры. НМ-решения определяют «нормы поведения»; вектор Шепли дает своего рода математическое ожидание. Устойчивое множество получается рассмотрением переговоров, которые фактически могут иметь место в продолжении партии игры. Таким образом, мы будем рассматривать возможные угрозы и контругрозы, выдвигаемые' несколькими игроками. !Х.2.1.
Определение. Коалиционной структурой в игре и лиц называется разбиение 8Г' =(ть т„..., т„,) множества У. Содержательно, коалиционная структура представляет собой разбиение множества т1/ на взаимно непересекающиеся коалиции.- Предположнм, что такая структура достигнута. Мы предполагаем, что каждая из образованных коалиций Тд получит величину г91 IХ. 2. Устойчивые миоесестви о(Ть), которую нужно разделить между членами этой коалиции Но как будет делиться эта величина? 1Х.2.2. О яр ед елен не, Конфигурацией называется пара (х; й) =(х„..., х„; Т„..., Т„), где У вЂ” коалиционная структура, а х представляет собой н-век- тор, удовлетворяющий условиям :Е х,= о(Ти) гь (9.2.
1) для й = 1, ..., пт. Мы хотим теперь выяснить, какая конфигурация будет достигнута. Очевидным требованием будет требование индивидуальной рациональности, т. е, мы должны потребовать, чтобы для всех/енй/ хт ~ о((1)). (9. 22) Дальнейшее возможное требование может состоять в том„чтобы никакая коалиция Т„не могла образоваться, если хоть одна из ее подкоалиций может получить больше, чем дает ей дележ х.
Следо- вательво, .лл х, о(Я) для Яс Тья У . сиз (9.2.3) Ясно, конечно, что условие (9.2.3) сильнее условия (9.2.2). 'С другой стороны, необходимость условия (9.2.3) не столь ясна, как необходимость условия (9.2.2). Не вдаваясь здесь в доводы за и против условия (9.2.3), мы просто будем говорить, что конфигурация„удовлетворяющая условию (9.2.3), будет называться коалиционно рациональной а удовлетворяющая только условию (92.2) — индивидуально рациональной. Прежде всего мы исследуем коалиционно рациональные конфигурации. Предположим теперь, что достигнута некоторая коалиционно рациональная конфигурация.
Когда она будет устойчива? Ясно, что если коалицнопно рациональная конфигурация есть дележ, принадлежащий ядру игры, то она будет устойчива в том смысле, что никакая коалиция не будет иметь ни возможности, ни склонности изменить эту конфигурацию, Так как, однако, ядро часто оказывается пустым, отсюда следует, что мы не можем требовать, чтобы коалиционно рациональная конфигурация принадлежала ядру. Рассмотрим, например, симметричную игру трех лиц, изученную ранее. Если образуется коалиция (1, 2), то весьма вероятен дележ ('/м '/м 0) Тем не менее любой из двух игроков этой коалиции мог бы потребовать от другого больше, угрожая присоединиться к игроку 3, если его требование не будет удовлетворено. 192 Гл.
ЕХ. Другие понятия решения в играх и лия Так, игрок 1 мог бы приг4позить образовать коалицию (1, 3), предлагая, например, дележ ( /ь О, '/е). Игрок 2, однако, может возразить на эту угрозу, указав, что в таком случае он попытается образовать коалицию (2, 3), предлагая игроку 3 вепичину '/е и получая, таким образом, дележ (О, '/м ~/«). Таким образом, игрок 2 может выдвинуть контругрозу, которая «защищает» его долю г/ь Для того чтобы сформулировать эту идею математически, мы начнем с определения понятия партнеров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
