Geum.ru
Темы диссертаций по экономике » Математические и инструментальные методы экономики

Реализация соответствий группового выбора равновесиями Нэша тема диссертации по экономике, полный текст автореферата



Автореферат



Ученая степень доктор физико-математических наук
Автор Данилов, Владимир Иванович.
Место защиты Москва
Год 1992
Шифр ВАК РФ 08.00.13

Автореферат диссертации по теме "Реализация соответствий группового выбора равновесиями Нэша"

ЦЕНТРАЛЬНЫЙ ЭК0Н0ММН0-МАТИ1А.ТИЧЕСК1Ш ИНСТИТУТ РАН

На правах рукописи

В.И.ДАНИЛОВ

ДОМАД-АВТОРЕФЕРАТ по материален диссертации па тему

Реализация соответствий группового выбора равнове<"1шш1 Нэта

Специальность 08.00.13 - Экономика и математические методы

Диссертация представляется к защите по совокупности работ на соискание ученой степени доктора физико-математических наук

Москва 1ЭЭ2 г.

Работа выпонена в Центральном экономико-математическом

институте РАН Официальные оппоненты:

доктор фп.-мат. наук Булевский В.А.

доктор фцз.-мат. наук Васильев В.А. доктор фаз.-мат. наук Шоломов Л.А.

Ведущая организация - Вычислительный центр РАН

Защита состоится ЬО) Л 1992 г. на заседал:

специализированного совета ДР 002.27.Ш в Центральном экономико-математическом институте РАН по адресу 117418, Москва, уд.Красикова .32

'диссертацией можно озпакомк ься в оибнотеке центрально; эконо..шсо-математического гаститута РАН

Автореферат разослан " " с ^ г.

Ученый секретарь специализированного совета

Скоков В.А.

Введение

Так уж получилось, что главными темами мои исследований в штедатической экономике (работы по агебраической геометрии я ютавляю в стороне) были равновес :е (в экономиках и играх и рутовой выбор. К первым относятся работы [1-7], среди которых ледуэт выделить с.татью [61, посвященную обобщению понятия копошяеского равновесия, и Г4], в которой развивается редложенное В.М. Потеровичем понятие уравновешенного со-тошшя, Начатый в работе [4] перекос результатов с выпуклой бстановгаг на связки конечных мнонеств вылися позднее в цегчй нкл работ, посвященных обобщение понятия выпуклого множества и бстрактному изучению выпуклых пространств.

Групповому выбору посвящены работы [8-24]. Некоторые олученные здесь результаты собраны в обзоре [1Q] и монографии 20], написанной совместно с Сотсковкм Л. И, Темой же настоящего оклада я выбрал несколько результатов (изложенных в [20-2-2] и 24], в которых переплетаются-и играют оба эти понятие - груп-овой выбор и равновесие.

Задачи группового выбора возникают во многих областях оциальных наук, и ш посвящено большое количество литературы, уть их в принятии колективных решений на основе индк-здуальных интересов. Решение форме,изуется понятием функции гл соответствия группового выбора (СГВ). В данном докладе яимание будет уделено вопросу о реализации заданного СГВ с змощью тоге или иного механизма группового выбора (далеп docto механизма).

Основная задача группового зыс^ра состоит ь следующем, /сть имеется некоторая груша лиц, называемых агентами . или гастншсами; множество этих агентов обозначается N. эедполагается, далее, что эта группа имеет дело с некоторым мкесгвом объектов (альтернатив) А, из которых она доша /делить один или несколько "наилучших". Наконец, считается, го каждый агент имеет некоторое предпочтение на указанной южестве А, как-то ранжирует альтернативы по их важности или эивлекательности. Нужно как-то сегрегировать кндивидуз >,ьные :едпочтения и на этой основе выбрать объект, "наилучший" с

точки зрения группы в целом.

Предпочтения участников понимаются как слабые порядки и обозначаются буквой Я, или й{, если мы хотим указать, что это предпочтение агента I. Набор предпочтений взех участников - это семейство (Д{), оно обозначается как В^ и 'называется профилем предпочтений группы N. Ь таком случае решение конкретной задачи группового выбора - это выделение некоторой альтернативы аеА, которая зависит оз профиля предпочтений Е^, так что а=/ЧЯл). Однако часто нужно решить не одну конкретную задачу, а целый класс задач, отличающихся различными профилями. Поэтому более правильно будет сказать, что задача теории группового выбора состоит в изучении правил группового выбора, т.е. многозначных функций (соответствий группового выбора, СГВ) вида

Р: {профили предпочтений} => А, При конкретном профиле СГВ указывает не одну альтернативу : -а, а некоторое подмножество =4 альт^р^атив, а том или ином смысле приемлемое для группы N.

Другой важьейший объект теории группового выбора и данного доклада - механизмы группового выбора. Главное в механизме это описание возможностей агентов влиять на результат. Формально для каждого участника специфицируется то множество действий, которое он может д ла^ч. Обозначай это множество элемеьд! его называются сообщениями или стратегиями. Кроме того, указывается, какой исход вызывает та или иная комбинация ь1='з1,1е№) индивидуальных сообщений, т.е. задается отображение

Все это вместе и называется механизмом (группового выбора).

Если теперь зафиксировать некоторое понятие решения У, мы толучаем многзство возможных равновесных исходов Я^),

которое зависит как от профиля Я , так я от механизма ж и концепции решения ?. Зафиксировав последние, мы получаем некоторое СГВ Про неги говорят, что оно реализуется

(имплементируется) механизмом я или концепции У.

Впервые проблему имплементации СГВ поставил Масгаш и 1877 г. в своей так и неопубликованной, но получившей широкую известное'!о статье [28]. Он обнаружил важное, хоз л очень

простое условие реализуемости СГВ - условие монотонности. Кроме того, он показал, что если монотонное СГВ удовлетворяет еще одному, не очень ограничительному условию отсутствия права вето, и если участников не менее -рех, го такое СГВ реализуется как равновесные по Нэшу.^сходн некоторого механизма. Однако проблема не была решена, до конца, и некоторое время существенного продвижения не было. Решение было найдено Муром и Ре)туло [27] и (независимо) автором [22]. Мур и Репуло ориентировались на общую обстановку; соответственно их условия Нэш-реалигуемасти имели примерно такой вид: нужно, чтобы для любого допустимого профшя предпочтений существовало нечто с определенными свойствами. Конечно, такие условия трудны для проверки. Условия, предложенные мною, имели более качественный характер и представляли некоторое усиление монотонкости. Л именно, я ввел понятие существенных элементов и основанное на них понятие существенно-монотонных СГВ. Тогда реализуемость СГВ оказывалась эквивалентной (снова при трех и более участниках) существенной монотонности СГВ. Условие существенной монотонности проверяется для многих классов CIB, что устанавливает их реализуемость. Случай двух участников тоже поностью разобран.

Случай коалиционных равновесий выглядел более сложным. В работе f 25] была доказана сильная имплементируешсть ядерногб соответствия. Положение изменилось .шь к 1990 г.,' когда в работе Детты и Сэна [29], а также в работе Д-нилова l Сотскова [21] были получены необходимые и достаточна условия сильной реализуемости. Ответ Датты и Сена был в стиле работы Мура к Репуло: нужно бы.' i, чтобы для каждого допустимого ' профиля предпочтений существовало нечто с нужными свойствами. Ясно, что такой критерий неудобен для применения. Его достоинством было то, что он относися к произвольной обстановке. Напротив, в [21] ответ был дан для универсальной обстановки и выглядел Золье удовлетворительно. Дл произвольного СГВ F мы строил, зекоторое вспомогательное соответствие ер: = А. Основная георема состояла в том, что СГВ F сильно реализуемо тогда и голько тогда, когда соответствие ер непустозначно. В ряде злучаев соответствие явно вычисляется, что позволяет троверять сильную реализуемость некоторых конкретных СГВ.

Например, это позволило дать поное описание тех ядерны соответствий, которые допускают сильную реализацию: для этог соответствующее блокирование дожно быть достаточно сильным.

Однако и это решение выглядело не впоне удовлетворительно, гак как вычисление соответствия ер было достаточно сложным и трудоемким. Поэтому в работе автора [24] был; предпринята попытка найти критерий качественного характера, кш это было сделано в-отношении Нэш-реализуемых соответствий. Дл: получения более качественного критерия сильной реализуемост! пришлось несколько видоизменить понятие профиля предпочтений. 1 именно, пришлось допустить более гибкое формировано предпочтений коалиций. После этого ответ стал более гладким: для строгой реализуемости СРВ необходимо и достаточна, чтоб! СГВ удовлетворяло трем условиям: монотонности, грубости I состоятельности. Первое условие монотонности объяснялось выше. Второе - грубость - означает, что группоьой выбор не меняете} при некоторых "несущественных" изменениях профиля; в нзкотороь смысле это условие аналогично упомянутой вше существенно! монотонности. Наконец, состоятельность означает существование некоторого естественного закона хюшозиции на множестве квазкпрофилей.

Доклад организован следу .да. образом. В главе 1 приводите* обзор работ автора по равноЕэсням. Во второй главе - обзо! работ автора по групповому выбору. В третьей главе обсуздаетс^: просвет реализации и вводятся необходимые понятия. Глава 4 относится к реализуемости равновесиям! Нэша. Глава 5 посвящена реализуемости сильными (коалицронно-Нэшевскими) равновесиями.

Глава 1. Обзор работ по равновесию.

Обобщённые цени. Первой работой автора на эту тему являете? статья [1] "Экономическое равновесие и обобщенные цены". Несмотря на некоторую наивность и сырость, она содержала "енную идею, которая в вызревала и оформлялась в дальнейших работах. Идея эта была в том, что цена - это не просто линейный функционал на пространстве товаров, но инструмент достижения равновесия, белее точно, инструмент формирования сщ М в принципе возможно существование других, более тонких инструментов. В данной работе внимание кснцентрировелось лишь

на том, что цена как линейный ф,гчкцаонал не всегда дает однозначный спрос, если полезности потребителей (или технологии производителей) имени? плоские участки. В качестве более тонкого инструмента ("обобщенные цены") предлагались пределы вероятностных смесей обцчшхх цен. Грубо говоря, обобщенные ценн -это бесконечно малые случайные колебания цены вокруг некоторого устойчивого уровня.

Заложенная в 'этой работе идея встечаегся почти во всех дальнейших работах автора на тему равновесия. Превде всего зтоит отметить так и не опубликованную работу о ррвновесии с эчерэдями (черэз десяток лет переоткрытую Алексеевым и Сталем). 1'ак как она не была опубликована, то нечего подробно о ней и эассказыгчть. А упоминается она в той связи, что в ней шструментом форфовашя спроса ьоребителя (тоже своего рода )бобщенная цена!) выступала днна очереди. Некоторые другие зыриации на тему "обобщенной цены" можно встретить в работе штора [2] "Невальрасэво равновесие и обобщенная лемма Гейла". 5 ней предлагается несколько вариантов реашацш: идеи (бобщепкой ценн каг регулятора спроса (или предлозкения), а акже развивается некоторый общий формализм ("обобщенная лемма "ейла"), позволяющий устанавливать существование равновесий для 'бобщенных цен.

Более частной реализации обобщенных цен как инфинитези-гальши отклонений обычных цен посвящена работа .[16] и, -в ольшей степени, [3] и [6]. В первой, гд^ речь идет о онкурентных равновесиях в коалиционных играх, обобщенные цени оявляются как бы эпизодически, где-/о на периферии. В раостах о обобщенному экономическому равкояесшо ([3, 6]) обобщенные ены занимают уже центральное место. И так как я считаю р-боту 3] одной из центральных в се зм творчестве, то стоит становиться на ней несколько подробнее.

Начинается она с замечания (или примера), что даке при ороших условиях равновесие может не существовать. Формально эло в разрывности бюдкетного соответствия, которое (^ моделя" истого обмена) происходит на границе симплекса цен, эгда экоторые цены обращаются в нуль. Иначе говоря, предельное оджетное множество зависит от конкретного способа стремления зны к пределу. И у нас с Сотсковым А.И. созрела мыоль

(подсказанная пр) предыдущими упомянутыми работами! считать "обобщенной" ценой именно этот процесс стремления цен к пределу. д!а идея может быть формализована разными способами; в работе [3] она реализуется и как меновая стоимость, и как иерархическая цена - (прекрасную реализацию нестандартными числами- предложил позлее В.Маракулин). После этого ш доказываем, что (в модели чистого обмена) при Х обычных стандараяых условиях обобщенное равновесие существует всегда. Здесь еще раз была показана верность принципа Д.Гильберта: всякая задача имеет решение, если: только понятию "решения" придать правильный смысл. То есть часто дело не в конструкции хитрог" доказательства, а в нахождении правильного, адекватного, естественного понятия и определения.

В работе [б] полученные результаты были обобщены на случай с производством. В отданной в печать статье автора "Экономики с перекрывающимися поколениями" идея обобтшшк цен также нашла свое применение. Во-первых, при определении цены, включающей в себя субсидии, и, во-вторых, при доказательстве существования равновесия, где я пользуюсь нестандартными ценами.

Обобщение выпуклости. Другая ветвь исследования в области равновесия выросла из статьи [16]. Поставленные в ней вопросы натокнули нас (меня и Сотокова Л.и.) на аналогии между леммой 'Зкарфа (используемой им при изучении ядра игр) и теоремой В.М.Потеровича о существовании уравновешенных состояний. Г :ар*юе их отличие в том, что если у Погеровича рассматривается выпуклое множество альтернатив, то у Скарфг речь йдет о конечном множестве. Б работе [4], которую я также считаю принципиальной, была найдена некоторая общая точка зрения на оба эти результата, и сформулировано более общее и правильное понятие уравновешенного состояния. Главное было в том, чтобы решением в конечном случае считать нэ исходную альтерн^дту, а непустое подмножество альтернатив ("связку"). При этом аналогом понятия уравновешенного состояния для конечного случая оказывас :ся примитивное множество Скарфа. Было получено несколько результатов о существовании уравновешенных состояний.

Однако более важной даже, чем конкретные резуль^л,', мне представляется вынесенная из этой работы идея, что множество

связок (хотя оно тоже конечное) в ком-то смысле обладает "выпуклой" структурой. Более точн<-, "выпуклой смесью" двух связок следует считать их объединение. Возникало естественное желание развить теорию обобщенных выпуклых множеств, которая наряду с обычными выпуклыми шоке .твами включала бы и такие непривычные образования, как связки. В работе [7] мы построили такую теорию. 1 именно, выпуклым пространством мы назвали л"збое множество I, снабженное оберацией "смешивания", или выпуклой комбинации:-для любых двух точек х и у их 1 и вещественного числа <*е[ОД] догого быть определена точка <с+сИуеХ. При этом операция смешивания долина удовлетворять четырем естествеодт аксиомам (из которых самая ваша" и нетривиальная - аксиома ассоциативности). Обычные выпуклые множзства выделяются тем, что для них выпонена еще одна аксиома - т.н. аксиома сотсрацения. Другой класс выпуклых пространств ("ординальных") доставляют полурешетки - упорядоченные множества с верхними гранями. При этой нетривиальная смесь точек хну- это их верхняя грань вир(х.у); в частности, она не зависит от весовых коэффициентов. Главный результат [7] состоит в том, что любое выпуклое пространство естественниц образом расслаивается над некоторым ординальным выпуклым пространством, причем все слои являются уже обычными выпуклым*' пространствами.

Перенос на выпуклые пространств топологических понятий шгволиг сформулировать и доказать некоторую теорему о неподвижной точке, частными случаями которой являются как теорема Брау. ра, так и теорема Биркгофа-Гарского. ЕсТл надежда; что подобные теоремы о неподвижных точках найдут сЕое применение в моделях равновесия, где пространства товаров имеют дискретную природу, таких как модели рынков интелектуальных товаров.

Глава 2. Обзор работ по групповому выбору

Агрегирование предпочтений. Как видимо и у многих, мои исследования по групповому выбору оттакивались от классического парадокса Эрроу. Он показал, что если правило агрегирования предпочтений удовлетворяет некоторым естестве.ним, условиям, то существует диктатор. Я заметил, что возможен более

rov шй и исчерпывающ^ ответ на вопрос о структуре правил агрегирования Эрроу. Все они устроены так: имеется линейная иерархия участников, и групповое предпочтение есть лексикография предпочтений этих участников. Конечно, старший по этой иерархии - это и есть диктатор Эрроу. Эти результаты, распространенные на бесконечное множество участников, приведены в работе til] "Структура бчнарных правил агрегирования предпочтений". Остальные работы автора такие были направлены на получение поных характеризаций правил агрегирования.

Аксиоматический подход Эрроу к проблеме агрегирования выжил причины появления диктаторства и возможные пути выхода из тупика. Эти причины: универсальность обстановки, ^ребованил рациональности группового выбора (слабые порядки), бинарность (независимость от посторонних альтернатив), и наличие белее двух альтернатив. Последнее требование особого изучения не требовало - ясно, что при двух альтернативах имеется много "хороших" правил, и их мозшо описать. Остальные же причины более глубокие и породили массу исследований, в том числе и автора. Опишем их кратко.

Довольно ясно, что отказ от универсальности обстановки, т.е. от применимости правил^ . ь любых ситуациях, расширяет возможности для конструирования хороших правил и усложняет задачу поного их описания. Классическим примером ограничения обстановки служит класс однопиковых предпочтений. В работе [8] я исследовал другой тип ограничения, *:огда участники связаш некоторым отношением "близости", и у близких учпстникоЕ предпочтения тоже дожны быть близки. Дело о том, что на множестве всех слабых порядков имеется естественное отношение толерантности (рефлексивное и симметричное). Были найден: необходимые и досте.точные условия на связь участников, при которых возможны не диктаторские правила.

Надо сказать, что агрегирование по Эрроу обладает замечательными категориями чертам.!, которые были исследованы г работе [9] "Агебраические аспекты группового выбора".

Друге1! Сольной класс предпочтений, для 'которого также имеются хорошие правила агрегирования - это класс т.н. дихотомических предпочтений, которые делят все альтернативы не

две группы - хороших и плохих. В работах [14,15]. мне удалось найти поное описание правил а^реги;звания дихотомических предпочтений; оказалось, что ответ связан с наличием во множестве участников структуры качественной меры. Последнее означает наличие слабого порядка па множестве всех коалиций участников, удовлетворяющего одному допонительному условию. Например, если на множестве участников задана обычная мера (например, вероятностная), то можно сравнивать коалиции по их массе. Оказалось, что существуют качественные меры, не возникающие из количественных. Тем не канее, еоли правило агрегирования допускает неограниченное решицирование, то оно соответствует обычной количественной мере.

Другая возможность обойти парадокс Эрроу состоит г отказе (или ослаблении) требования, чтобы групповое предпочтение было слабым порядком. Например, можно потребовать, чтобы оно было только транзитившш. Эта и некоторые другие комбинации были исследованы в обзорной работе автора [10] "Модели группового выбора", где были даны поные .описания возможных правил агрегирования.

Соответствия и механизмы. Однако наиболее радикальный выход состоит в отказе от требования би^арности, или независимости. При этом рамки трсгацдокного подхода сттновятся узкими, и лучше перейти к прямой задаче группового выбора. В с .том ^еле, групповое предпочтение нужно в основном для последующего выбора лучших альтернатив, и поэтому лучше сразу рассмотрев'.ь соответствия (или функции) группового выбора вида

F:(профили предпочтений}' === А,

где а - ' рассматриваемое множество альтернатив. При ^аком иодходе на первое место выходит проблема выявления предпочтений и связанная с ней проблема манипулирования. Как показали Гиббэрд и Саттерсвейт, неманкпулируемые функции груп. зого выбора являются диктаторскими; это аналог теоремы Эрроу. Однако прк ограничении обстановки снова появляются возмоа0">сти дг< построения не диктаторских неманипулируемых механизмов /ппо-вого выбора. Одному такому случаю, а именно - эвклидовой обстаноЁке, когда предпочтения участников определяются расстоянием до идеальной точки, посвящена работа [19}. В ней

дается поное описание неманипулируемых в эвклидовой обстановке механизмов, однако ответ слишком сложен, чтобы приводить его здесь. Другой случай - однопнковые предпочтения на дереве, разобран в книге [20]. Там тоже дано поное описание неманинулируемых механизмов, обобщающее исследования Мулена.

Еще одно направление исследований - построение механизмов группового выбора, которые при любом профиле предпочтений обладают сильными (коалициогшыми) равновесиями. Первые работы на эту тему принадлежат Пелегу. В статьях автора и Сотскова [17, 18, 23] содержится обобщение резуль~зтов Пелена. В частности, мы доказываем очень глубокую, на наш взгляд, теорему о том, что почти-адщгашкое блокирование стабильно. Более подробное изложение этих, а также многих других наших результатов можно найти в монографии [20], посвященной механизмам группового выбора.

Наконец, проблеме реализуемости соответствий группового выбора с помощью механизмов, .иосвящего основное содержание этого доклада. СЗ этом будет более подробно сказано ниже.

Глава 3. Механизмы и реализация

Всюду далее В - конечно^ множество индивидов, А - конечное множество альтернатив. Предпочтением называется слабый порядок на А, т.е. поное транзитивное бинарное отношение на А. Для предпочтения Л соотношение хЯу интерпретируется как утверждение, что альтернатива х не хуже альтернативы у. Для предпочтения Я и альтернативы а обозначим Ь{а,Н)={хеА, ах). Иначе говоря, это множество альтернатив, котсрые не лучше а.

Проф1ыем предпочтений-(или просто профилем) называется семейство предпочтений участников группы М, т.е. ЬеИ)

Если V - множестве всех слабых порядков на А, то профиль - это отображение из № в ЧГ, или элемент декартовой степени

Соответствием группового выбора (СГВ) называется непустое подмножество Р в ТпхАД Более наглядно нужно понимать СГВ как многозначное отображение из множества всех профилей Vя в множество альтернатив А. Тем самым СГВ Р для каждего профиля предпочтений указывает некоторое подмножество ЛЯ^ЫхеЛ, (Д в А. Некоторые примеры СГВ приведены в [20].

Вторым важнейшим понятием является понятие механизма (группового выбора!: Это нэбор абстрактных множеств S{, по одному для каждого участника letf, и отображение

Vies5' Л-

Элементы St называются стратегиями, или сообщениями участника I. Для набора сигналов sN={sl)eS1{ механизм ж указывает некоторый исход л(з}т)еА. Посылая те или иные сигналы, участники имеют возмояснэсть влиять на исход. Если мы зафиксируем еще некоторую концепцию решения ?, то для каздог. профиля предпочтений R} мы имеем множества исходов ^(я.й^), т.е. СГВ ^ = А. Соответствия вида для некоторого

механизма я называются реализуемыми, при концепции решения . Далее, в главах А и 5 мы более подробно остановимся на концепциях равновесия по Нзшу и на концепции сильного (коалиционно-Нэшевского) равновесия.

В дальнейшем, для реализацш! соответствий, нам понадобится одна достаточно общая конструкция механизмов, которле мы называем состпабншш. Опишем ее здесь. Предположил, что у нас имеется "основной" механизм /

a: IItS{ Ч J

со значениями в некотором множестве J", и, кроме того, . для каждого j&J задан вспомогательный механизм "доводки"

ру. ntf Ч А,

уже со значе;ляш в множестве альтернатив А. В этом случае можно образовать составной механизм a*Pj. Стратегиями участника I будут элементы множества Si=StxTl, где Для sveS}}

и iNer;i исход составного механизма образуется по правилу

Иначе говоря, по стратегиям з;} "основного", или "грубоп" механизма а определяется индекс j=o[an) того механизма "доводки" р , с помощью которого и осуществляется окончательный исход Pj(t^).

Интерес этой конструкции в том, что часто на первом ?-"апе з помощью некоторого естественного правила удается сформировать *е один исход, но лишь некоторое подмножество, куда этот исход

можт или дожен попасть. Окончательный выбор их этого подмножества приходятся делать с помощью допонительного механизма. Например, использовать диктаторский механизм или постоянный механизм. Однако для на'-мх целей более важен будет другой, более изощренный и интересный способ разбивания связок, который мы назовем вертушкой. Дадим формальное определение.

Предположим, что зафиксирована некоторое . непустое подмножество X <= А. Упорядочим участников lf={,2,...,я}. Сообщение каждого участника состоит из пары (x.v), где хеХ, a v - некоторое целое число. Пусть участники юслали сооо^ения lx{,v{). Тогда исход механизма определяется как xv, где vИ{1,...,п} и равно (v{ по модулю п. Говоря наглядно, сначала участники с помощью выбрасывания пальцев выбирают "короля" v (с номером, равным v^...-и^ по модулю п), который затем называет произвольный элемент х из множества X. Назовем построенный механизм вертушкой со значеишш в X.

Глаьа 4. Реализация равновесиями Нэша

Здесь устанавливаются два основных результата. Если число участников не меньше трех, то для реализуемости но 'Нэшу СГВ необходима и достаточна существенная монотонность. Если же участников двое, то для реализуемости по Нэшу необходимо и достаточно выпонение трех свойств: 1) существенной монотонности, 2) индивидуальной рациональности, и 3) свойства Мура-Репу :ло. Результаты --той главы опубликованы в [2С и 22].

з . Соответствие равновесных по Нэшу исходов

Пусть дан механисм л:SN Ч А и профиль предпочтений R}r Набор стратегий s*=(3*)eStf называется равновесием по Нэшу в игре Gin.Ey), если для любого участника 1еЛ~ и любой его стратегии sieSl выпоняется соотношение

zispRMs^B*^). иначе говоря, Ь(Я(зу),Я{) для всех участников leN.

Множество BCt-x равновесных ислодов а=я(з*) в игре Gin.R^) обозначим как NEix.R^). Так возникает соответствие равновесных исходов :^===>Л механизма п. Скажем, что >1ТТУ>, F Нэш-реализуется (гшглелеыжируется) механизмом'ж, если w/iw).

В следующем параграфе мы введем определение монотонных и

существенно монотонных ОГВ и проверим, что любое Нэш-реа-лизуемое СГВ обладает этими свойствами.

з 2. Монотонные и существенно монотонные СГВ

Определение 1. СГВ F называемся ионотоншт, если для любых профилей предпочтений и Я'ы и альтернативы aeF(R;j] из соотношений

L(a,R, ) с L(a,R'{) дл всех IdT (i)

следует, что aeF(R^).

Грубо говоря, монотонность означает, что альтернатива а выживает, если.ее позиция не ухудшается в смысле (1). -1тобы сформулировать усиление понятия'монотонности, нам понадобится одно вспомогательное понятие.

Определение 2. Пусть даны участник и подмножество ХсА. Альтернатива хеХ называется существенной для участника I в мноиестве I, если xeF{RH) для некоторого профиля предпочтений Яд. с условием L(x,R )сХ.

Множество всег. (-существенных'элементов в X обозначается как Ess{F\l,X), или просто Езз(Д), если ясно, какое СГВ F имеется ввиду.

Определение 3. СГВ F называется существенно люнотонным, если для любых профилей предпочтений R}J, и альтернативы aeF(R77) из выпонения соотношений

E33(F;t,L(a,Fl)) с L(a,R[) д..я всех е?/ (2)

следует, что aeF(Rp.

Видна аналогия с определением монотонности. Грубо говоря, суще твенная монотонность означает, что альтернатива а выживает : э только при улучшении, но и при несущественном ухудшении позиции альтернативы а. Очевидно, что существенная монотонность влечет монотонность, но не наоборот.

Тем не менее во многих случаях монотонность влечет существенную монотонность. Большинство этих случаев охватывает следующая

Лемма 1. Пусть СГВ F штототю xl Оля любого le А тожество Езз(1,Х-) m о пусто, либо совпадает, с X. Тогда F существенно монотонно.

Как мы уже упоминали, Маскин показал, что любое Нэш-реа-лизуемое СГВ монотонно. Усиливая этот результат, мы доказываем следующую георему.

Теорема 1. Дл любого иезхшизш я соответствъл НЕ (к) сильно монотонно.

з 3. Основной результат

Таким образом, существенная монотонность необходима для Нэшреализуемости. Здесь ш покажем, что она и достаточна,, если участников .не менее трех. Для этого мы явно построим ло СГВ Р реализующий механизм я=ж . Здесь будет использована общая конструкция составного механизма, изложенная в главе 0.

Конструкция яехакизш. Пусть дано (пока произвольное) СГБ Р. "Основная", или главная часть механизма устроена так. Стратегические множества тождественно совпадают с Р (или графиком Г, если угодно). Это яначит, что сообщение любого участника имеет вид (й^.з), где - некоторой! профиль предпочтений, а хеР(Дн). Окончательная доводка, т.е. исход пр(8я) происходит по разному в трех различных ситуациях.

Первая. Если все участники посылают одно и то те сообщение (Л^.з:), исход равен х.

Вторая. Предположим, ч;о все участники, кроме одного диссидента 1, посылают однс и то же сообщение (й^.х). В этой ситуации доводочный механизм - это диктатура участника I на ьшолестве Ь'зз(Р; 1,1(х.Л{)).

Третья. Во всех остальных случагд: доводочный механизм -ото вертушка со значениями в множестве льР = ип Р(ДН).

Лемма г. Всегда Р с ДЕся.Ду).

Равенство Р=й(зг ), как мы видели в предыдущем параграфе, може выпоняться только для существенно монотонных СГВ. Покажем, что для таких СГВ оно действительно верно.

Георема 2. Если СГВ Р существенно монотонно, и. участников не меньше трех, ::ю Р=Щ Кр).

Замечание. По поводу равновесий для механизма Маскина-Винда. Теоретически они существуют, но совершенно непонятно, как участники могли бы к ним прийти с помощью индивидуальных действий. Для этого они дожны "всего .иищь"

правильно угадать предпочтения всех остальных участников и кроме того назвать одну и ту же допустимую альтернативу. Во всег остальных случаях они попадают в несогласованное состояние, из которого почти наверняка не смогут выбраться. Механизм Маскина, формально реализуя соответствие F, на деле мало помогает (и даже мешает) участникам прийти к равновесию.

з А. Примеры существенно монотонных СГВ

Приведем несколько примеров существенно Минотошых, а значит реализуемых при \H\}s3 соответствий. Здесь ш ограничимся только краткими указаниями, отсылая за подробностями [20] ilhi [22].

Прхшер 1, Скажем вслед за Ма&сином, что участник I слабый, если из того, что .гемах^. для всех участников j^l, следует, что xeF{R]}). В этой случае для любого мнозкества Х^л имеем Es3(.F;l,X)~ -X. Зсии рее участники, слабне, скакем, что СГВ F без права взто. Из легли 1 видно, что монотонное СГВ без права вето существенно монотонно, п следовательно, Нэш-реализуемо. Именно этот последний факт и был установлен Маскином.

Пример 2. Предположим, что F - нейтральное СГВ. Тогда для любого множества I множество существеннгт элементов Езз(Г-Л.Х) либо пусто, либо совпадает с А; это зависит лишь от числа элементов в X. Снова из леммы 1 получаем, что монотонное и нейтральное СГВ существенно, монотонно. Ммплементируемость ""аких СГВ отмечалась т [26]. Вот более кошсретные примеры.

a) F тозндествееко равное Л, см. пршер 2. ' '

b) Соответствие Par Паретовских альтернатив.

c) Объединение нескольких диктаторских ФГВ. Вообще, можно i-лазать, что объединение, .сельно монотонных СГВ снова сильно монотонно.

Пример 3. Соответствие Маскина. Зафиксируем некоторую альтернативу а и для профиля предпочтений RN определим мне :ество Uaa(RN) как пересечение мнонестве Раг(Д^) Паретовских альтернатив с множеством {хеА, хЕ^а для всех id/}. Это СГД Mas монотонно, но оно не нейтрально и с правом вето. Тем не менее. оно также существенно монотонно.

Последний факт допускает обобщение в двух направлениях.-

Первое состоит в том, чтп ядерное соответствие любого блокированная (или любой функции эффективности) также существенно монотонно. Другое обобщение - что любое минимальное монотонное СГВ (определение см. в [26]) существенно монотонно. За доказательством этого факта мы отсылаем к [22]. В частности, при >3 минимальное монотонное СГВ имплементируемо; этот факт был анонсирован Муленом [2Р], однако у него имеется ошибка.

Завершим этот з одним замечанием, которое призваны избавить читателя от возможных; илюзий. Из последнего абзаца могло показаться, что конструкция механизм Маскина позволяет строить состоятельные механизмы, столь желательные для группового выбора. В самом деле, достаточно взять существенно монотонное и непустозначное СГВ. Но делеЧто как раз в том, что мы плохо, представляем, как явно строить .монотонные непустозначные СГВ.

5 5. Случай двух участников: необходимые условия

В случае двух участншсав, ?Ы 1,2), одной существенной монотонности мало для имгглеменгацчи. Например, как мы увидим, тождественно равное Л СГВ не реализуемо. Важную роль здесь начинает играть понятие блокирования, которое имеет смысл и при многкг участниках, ^го общее понятие, но мы приведем его только в нужном для целей этой главы объеме.

Определение 4. Густь дан механизм л:БяЧ>А. Скажем, что участник р-Олошрует множество КсА с помощью л (пишем 1вРц, если для любого существует такая

стратегия а^еЗ^что ж(а1,3{!_1) не принадлежит X.

Очевидно, что если участник /3-блокирует множество X, он ("-блокирует л'тбое меньшее множество, т.е. в^ монотонно. В общем случае блокирование в^ не имеет каких-либо интересных свойств. Однако з случае двух участников в^ обладает следующим свойством суО- авшивиаспги: если участник 1 не ^-блокирует множество X, а участник г не р-блокируе^ множестро У, то ХПУ ^ 0.

В самом деле, если участник 1 не /-блокирует X, ' то участник 2 обладает стратегией а2> гарантирующей попадание в X, л(.,82)ИХ. Аналогично существует в1е31, что л(з1,.). '. Но тогда я(а1,в2)еХПУ.

Определение 5. Пусть дано СГВ Р:^ => А. .сажем, что

/частник I ялокирует 'тожество Х<=А с помощью Г (пишем ЬВ^Х), если существует такое предпочтение Л{еТ, что для любого Я множество Г(К(1Нгг._{> не пересекается с X.

Блокирование Вртакже обладает свойством монотонности.

Определение 5. Блокированием будет называться любое отношение В^17х2/,1 удовлетворяюдее свойству монотоньости и такое, что никакой участник не блокирует все

Исходя из произвольного блокирована.' В, можно построить соответствие индивидуально рациональных исхобо& 1Д(В) по формуле:

ГПсЗ.Д^) = <а<гА, (ВЬ(а.й^)

где В означает отрицание В. Очевидно, что всегда В^В1П(В). С другой стороны, как легко попять, для любого механизмам выпоняется включение для любого гпофиль

предпочтений Я1}. Приведем бе

Для любого иехашэш л

Предыдущие результат^ верш для любого И, 'но напбопэе интересные следствия даг для N={1,2}.

Следствие. Пусть 11 = П,2} и СГВ Р Н&я-ресиизуели. Тогда блокирование В^субаддиживно и Р с Ш(В^).

В частности, соответствие не реализуемо, так как

блокирование р здесь не субаддитивно. Действительно, любой участник не блокирует никакое нгтустое X.

Однако реализуемые СГВ обладают более тонки.. свойством, чем субаддитивность блокирования Вр. Чтобы сформулировать его, введем еще пару определений.

Определение 7. Пусть и 1 - два подмножества альтернатив. Скажем, что аеА', ПХ2 есть ЫЯ-элемент (в честь Мурт и Репуло) для пары (Х^Х ), .эсли существует- такой профиль предпочтений =(Й1,Й;)),' что X =Б(а,й{) для 1=1,2,- и аеР(И^).

В эт^м определении можно увидеть нечто от понятия существенного элемента из у 2. Множество всех ГД-элементов обозначим через MRi.Fi Х1Дг). Х

Определение 8. СГВ ? имеет МП-свойство, если НЩР-. Х^,Хг) непусто для любой пары {1^,1 ), такой что 1=1,2.

Предложение 1. Пусть л - механизм с двумя участник/и.и.

То"0а соотЪествие равновесных исходов Ш(к) имеет МЯ-свойство.

Подведем итог предыдущим рассуждениям. Если СГВ Р Нэш-реалисуемо некоторым Механизмом, -то для него выпонены следующие три свойства:

'- ? существенно монотонно;

2. Е с т(Вр), т.е. ? индивидуально'рационально;

3. Р тлеет НЕ-свойство (усиление субаддстивности).

В следующем параграфе покажем, что условия 1-3 не только необходимы, но и достаточны для Нэш-реализуемости в случае двух участников.

Х^ 6. Случай двух участников: достаточные условия

ъйпсырь^сщш шшеиетирукгчего механизма. Для реализац: а СГЕ с условиями 1-3 предыдущего параграфа мы построим сейчас соответструщий механизм Заметим, что предыдущая

конструюща Маскина-Винда не годится хотя бы- потому, -что участников всего два и нельзя выделить из них одного диссидента. II хотя идея механизма та'ке, детали отличаются. Он снова, строится как составной. Основными сообщениями этого механизма будут подмножества Л. Точнее, участник- I называет некоторое подднокество Т_1, которое не блокирует № смысле блокирования Вр) ротивсполозшый участник -I: После того, как /частыкп послали сообщеыгя (Х_1 ,Х_2), формируется множество ), и окончательный исход образуется с 1 помощью вертуыкг со значением в втом множестве ). Заметим,

что множество 1!Р.{Е;Х_г,Х_)) непусто, если Е Х обладает '"-свойством.

Предложение Пусть СГВ Е обладает Ш-свойством, и 1=^ -соотбетствукщ'й механизм. Тогда:

. а; если Е иядивидуелъно рацйошльно (т.е. с.1ЩВ )), то

Ь) Если Е существенно монотонно, то Ш(р.)сЕ.

Доказательно см. 120, 22]. Подвдем итог:

Теорема 3. Пуа.о илеется Оба участника. СГВ Г Яэш-реамичуемо тогда и. только тогда, когда втонени условия 1-3 предыдущего параграфа. Х

В заключение заметим, что Нэш-реализуемое соответствие Е

может отличаться от соответствия индивидуально рациональных исходов 1И(Зр). Такой пример, а также некоторые допонительные содержательные обсуждения можно найти в [20]. Х

Глава 5. Реализация сильные. (коалиционными; р вновесиями

В этой главе будут приведены результаты о реа-язаичи СГВ с помощью концепции сильного (=коалицистцо-Нэшевского) равновесия. Сь-лала кратко излагаются результаты работы-Данилова и Сотскова [21]. Затем более подробно рассказывается о дальнейшие исследованиях пптора, содержащих^- в статье [24], еще не появившейся в печати. Основной результат здесь в том, что. для сильной реализуемости соответствий, определенных на квазипрофилях, необходимо и достаточно выпонение трех свойств:, монотонности, грубости и состоятельности.

з 1. Определение сильной реализуемости

Пусть имеется механизм Ч> .4 и профиль

предпочтений Я,7=(Д{){аг Напомним, что коалицией, шзша^тся произвольное подшюжестъо К^н. Набор стратегий з*=(з*, 1е7) называется сшъныл равновесием з игре йЧтг.Я^), если для любой непустой коалиция Я и любо" стратегии зк=(з{,1еК) этой коалиции найдется участник IИК, для которого исход ?е (зД. з* Д) ке лучше

* ' /Чл.

г схода л(зч), т.е.

л(а*)Д{я(зг,з*_к).

Иначе говоря, ситуация равновесна (в коалиционно-Нэшевском смысле), если никакая'коалиция не монет стрто улучшить исход для всех своих членов при условии, что остальные участники сохраняют. прежние стратегии. Для более компактной зашит условия сильной равновесности, удобно ввести следующее обозначение. Пусть даны профиль предпочтений Яя, альтернатива а к коалиция К. Тогда обозначим; лерез I,(а, объединение Ь(а,Я{) по всем 1аК, т.е.

Отдельно условися, что Ъ{а,К^)={а}. В этих обозначениях условие равновесности набора стратегий з* приобретает следующий

вид: для любой коалиции К выпонено включение:

Заметим, что это включение верно и для .густой коалиции, для которой сно тавтологично.

Как и для равновесий Наша, мы определяем соответствие сильно равновесных исходов БЕ {ж) механизма к с помощь э следующей формулы:

БЕ {я) = {(Д^.и^етГ^х/!, что существует такой для которого

л(*к;,а*_к:)с1(г-)дк:) для любой коалиции К}.

Заметим, что при 1=0 мы имеем, что а=-я(з*). Остальные условия 1ают, з'ы есть сильное равновесие в'игре С(;с,Дл).

Соответствия вида Ж(зг) называются сильно реплизуетми. Наша задача - охарактеризовать сильно реализуем!, з СГВ. Во втором параграфе мы приведем основные результе ы работы [21], а остальные параграфы г^святим некоторое естественной модификации предыдущей постановки, при которой ответы становятся более качественными.

з 2. Критерий сильной реализуемости

Пусть 'Л^а.) - пара, где Пи - профиль предпочтении, а аеЛ. Множество всех сильных равновесий а* в игре С(л,для которых о-ж(з*), обозначим Б*(И]!,аК Проекцию множества (Нп,а) ьа Бк обозначим как таким образом,' набор а*

из глинядлешт если его можно продожить до

Определение. Пусть да^л СГВ К Ситуацией называется ^брикение Ч>Р; шгаче говоря, ситуация - это семейство пар (Л*, а1.) из Р, параметризованное участниками Мы

гг Еор..л, что в-ситуации участник I посылает сообщение

Пусть дана ситуация для соответствия л). Соберем группы единомышленников участников, пославших одинаковые сообщения. Получается разбиение

1 Ш ' . Х

еяНн) = ЖЗХ.

Можно показать, что множьотво содержится в

пересечении множеств Ца^ ). Для дальнейшего удобно ввести

обозначение

Тогда ел($№) с для любо: ситуации

Интерес множеств объясняется счедующей причиной. .

Пусть дан элемент аеел(^). Тогда а является равьовесным исходом для любого профиля, в которых' а располагается "достаточно высоко". Более точно, имеет место 'следующее '.утверждение.

Предложение 1. Пусть дана ситуация ^ и алътернс-гива аеел(п). Предположим, что для любой непустой коалиции К выпонено включение 1(а,Р.к)^ ел(*к, Тогда (К1{,а)еЗЕ(п).

Подведем итог. Пусть СГВ Е сильно реализуемо. Тогде для любой ситуации Чсуществует множество е{^)<=А,

обладающее тремя свойствами:

1) е(^) непусто;

2) е(^) с А(4К);

3) если аее(^) и профиль так'-в, что . Ца,!^) ? е(*к> Для любой непустой коалиции К, го №1Га)еР.

Мы утверждали, что обратно, если для СГВ Г существует семейство е(^), где' ^ прс "егает I11, удовлетворяющее свойствам 1)-3), то Е сильнз реализуемо. При этом реализация осуществляется механизмом я , конструкцию которого мы сёйчас приведем.

Конструкция механизма Механизм ле снова строится как составной (см. главу 3). Основными стратегиями каждого участника являются элементы ?, т.е. пары Х (й^,а)еР. Если участники посылают' сообщения то возникает ситуация ^ и соответственно, непустое множество Окончательный исход

механизма ле определяется с помощью вертушки со значениями в вЦя).

Предложение 2. Ьсли сенейстрво г( Х) обладает свойствами 1)~3), то Р=Е(яе).

При этом свойство 2) отвечает за включение F с БЕ(ле), а . свойств., 3) - за противоположное включение ? = Ж(ле).

Подведем итог в следующей теореме.

Теореыа 1. Соответствие F сил i со реализуемо тогда и только тогОа, когда Оля любой ситуации. Ч F существует множество е(н) с А, обладающее свойствами 1)-3)'.

Полученный в теореме 1 ответ не Bojae удовлетворителен. В самом деле, он ничего не говорит о том, как узнать, существует ли такая система е(Х) или нет? Можно дать чуть более удовлетворительный ответ. Оказывается, что систему можно получить как предел (или пересечение) последовательности систем е^О). 0,1,2,..., которая строится,индуктивно.

Х Построение этой последовательности Х начинается с е0<Х'Х). Остальные } строятся до шдувдш. Если уже достроено, то для ситуации полагаем eA+1(tir) = 1аеекЦ.7)к что a,F?{Rh) для любого профиля

такого, что Ka.^J-a e(*к,N-K) Для любой непустой коалиции К}.-

Таким образом, получается серия необходимых условий коалиционной реализуемости: непус:означность систем е.(Х} для любого целого числа к^О. В совокупности omi достаточны для строгой реализуемости.

В качестве применения в работе [21] устанавливается сильная реализуемость ядерных соответствий для сильных блоирований.

з 3. Модификация задачи: квазипрофили

Ka*, yi.j отмечалось, приведенный выше критерий сильной реализуемости не впоне удовлетворителен. Здесь мы ' собираемся ,едлоюш более качественный критерий сильной реализуемости. Доотигается это за счет видоизм нения понятия профиля предпочтений. Обычно профиль предпочтений д состоит в спецификации предпочтений в'сех учел,тникор Ш. Посредством правила одиногласия можно сформировать тогда предпочтения коалиций и говорить о сильных (когтиционных) равновесиях. Однак. для изучения коалиционных вопросов оказыьается более удобным не связывать столь жестко предпочтения коалиций с предпочтениями ее членов. Иначе говоря, удобно считать, tiro профшь предпочтений состоит в спецификации предпочтений всех коалиций, р не только индивидов. Такой Ьбъект = (Hg-где

Kg. - некоторое бинарное отноиеняь на множестве альтернатив А, назовем коалиционным профилем. Вообще, символ # мы используем для обозначения переменной булевского типа, значен ами которой Служат коалиции Kcfl. Интерес коалиционных профилей в том, что для mix естественно ' определяется понятие . сильного (коалиционного) равновесия. А пенно, если иыеетсг механизм л.

Ч>А, то набор стратегий а* называется . сильным равновесием, если для любой коалиции К и любой коалиционной стратегии sT.eSK = xlИgSi 'выпоняется . '

n{s*)RKn(sK,s*_K).

Normo обозначите через мьожестго таких равновесных

исходов. Обобщая эту конструкцию, соответствием группового выбора мк будем, начиная с этого места, считать отображение F из множества всех коалиционных профилей в тожество- 2Л подмножеств А. Такое соответствие сильно реализуема, ееjlA оно тлеет иид Eq[л,-) для некоторого механизма ir.

На самом деле, равновесность исхода а зависит не столько от предпочтений коалиций RK, сколько от их нит .контуров

L[a,R^) = {хеА, aRgX}.

Это позволяет сделать последний шаг и перейти от коалиционных предпочтений к с ответствующим низшим множествам. Мы назовем квазипрофилем семейство - )ксда. подмножеств А. Снова можно говорить о соответствиях, ' сильно равновеенных исходах и Х имплементации. Именно в этой постановке мы и даем необхс.доые и достаточные условия сильной имплементации. Ответ гэстоит в том, что соответствие дожно быть монотонным, грубым и состоятельным.

Приведем точные определения.

Определение 1. Квазипрофилем называется семейств^ (%K)KzN подмножеств А, удовлетворяющее условию монотонности: если КсК', то IjcZ,.

Иначе говоря, квазипрофиль - это монотонное отображение из 2я в Множество всех квазипрофилей обозначим как Qpr. Как мы увидим, это множество обладает несколькими интересными* структурами.

Типичный квазипрофиль возникает, когда имеется коали-

ценный профиль предпочтений и альтернатива с; в атом случае можно ьоложить 1^=1('о,R^) Обратно, квазипрофиль можно ' представл ять себе в ввде коалиционного профиля Х дихотомических предпочтений,. в которых Хк играет * роль второго класса экпвалентных элементов.

Другой способ образования квазипрофилей доставляют к.эханизмы. Предположим, "что имеется мехавдзг л: x{ИiiS{ Ч>А и набор стратегия s^eS^. Тогда можно определить кшзипрофиль полагая дчя коалиции К

Понятие равновесия имеет Х естественный смысл тля любого квазипрофиля.

определение 2. Пусть-дан . :еха: изм л и квазипрофиль Набор стратегий назовем сильным равновесием в игре

С(яД#), асли Х#, т.е. если для любой коалищш К

nK(s*) с хк.

Множество соответствующих исходов а=л(э*) обозначим Яд(я,Х#Ч Таким образом, Ед(п Х#) состоит из альтернатив а вида я(з*), причем ). При переменном квазипрофиле ш

получаем соответствие равновесных исходов Ед{л): Орг ==>А.

Определение 3. Соответствием (группового выиора) называется ;.логознвчное отображение ? из множества Орг квазипрофилей .в А, (т.е. подмножество Рс(2рг*А), для которого

Мы будем предполагать, что ? не пусто; при атом для конкретного квазипроршя Х# множество значений /(Х^)-может быть ""'стым. Если все же негусто, квааипрофль называется

^-сосиошелыъш.', разумеется, в этом случае Х^ также непусто.

Соответствие вида Ец(п) называется сильно ш. глеьентируемым, Х или просто .имплементируемым. Наша задача -с аракт~ризоьат} такие соответствия. Мы начнем с выяснения некоторых необходимым условий. Простейшее из них - аналог монотонности Красина. Скажем, что соответствие Г монотонно, если Х# с х^ влечет с: Р('Х^). Из приведенного выше

определения совершенно очевидно, что соответствие Ец{п) монотонно.

з 4. Необходимые условия: грубость

резде чем переходить к определению грубости соответствия, нужно ввести одну простую, ьо полезную операцию с квазипрофилями, которую мы называем тривиализацией. пусть имеется квазипрофиль Х# и некоторая коалиция Octf. О-тривиамзацпей квазипрофиля будем называть новый .

квазипрофиль Я-ая компонента соторой pt-зна ^kUo'

Очевидно, что Х#<=х^0Д

Вернемся к условиям имплементации. Пусть дано Монотонное соответствие F. Сейчас мы введем одну операцию! навеянную понятием существенных sj. ментов. Бе тее точно, мы построил для каждого кгазипрофиля Xit новый квазипрофиль Х^, который назовем производным.

Определение 4. F-произвоОныи квазипрофилем называется Х кзазипрофкль й-ая коштонента которого равна

где, напомним, обозначает Я-тривиализацию квазипрофиля Х#.

В частности, с хк для любой коалиции к, т.е.

Отсюда в силу монотошости F мы имеем включение ДХр с i'(^)-

Определение 5. Соответствие F называется грубил, сели для любого квазипрофиля Х.^ шлеет место равенство

F{.X*) '= F(I#). . .

Георема 1. Для любого . меткизш л соответствие Eq(n) грубое.

Доказательство. Пусть произвольный квазипрофиль, мы дожны показать, что Ед{Д#). с Eq(n,X^), где F=hq{п). Пусть aeq(jr,Xtt), т.е. имеется набор стратений эд, для которого а=л(зя) и Нужно проверить, что Х^-Л^Сз^).

Зафиксируем коалицию Ос.Ц. Мч. дожны показать, что

т.е. что

Е:(л,х#ио) г, x(s0,a*_0).

Для этого достаточно показать, что для любого лабора стратегий-s0eSQ набор (з0,з^_0) будет сильным равновесием в игре С(д,Х^0). Но это очевидно, так как для любой коалиции if

j(sk'30-k'8ff-0-k) c n{fj[}k'aii-0-k] ^ z-

Первое включение верно по .определению, а второе - следствие равновесности s* в игре G(я,Х#).

так, шг доказали (*!, а значит и теорему.в аним образом, грубость соответствия - необходимое условие его имплементируемости.,

з 5. Необходимые условия: состоятельность

Здесь нужно ввести довольно нетривиальную п-арную операцию свертки, на мно!.;ествё квазипрофилей, .где п=|й| - число участнш DB. а Ю'ЭННО, пусть- даны квазипрофили о одной для каждого участшжа leu. . Разобьем участников нэ группы единомышленников К1, ...,кт в сооиетствии с их квазипрофиляш (так что кваз1шрофили всех членов KJ одинаковы и равны Х Х^). Сверткой' (X.;,.. будем называть квазипрофиль *^)^, к-ая компонента которой рьвна

( (45 к =

Получим теперь третье необходимое узловые имплементируемости, предполагая по-прежнеыу, что соответствие F определено ни квазипрофилях. Напомним, что квазипрофиль называется Е-сос,Дошелышл,. если.множество непусто.

Определение R. Соответствие F назгвем состоятельный, 'если для любого набора (X*), ew, Р-состоятельных квазипрофплей их свертка *lXi tarace является F-состоятельшш квазшрофилэм.

Теорема 2. Пусть ссоэтКеистбие F есть соответствие 3повлеки" исходов механизма к. Тогда F состошиелъгьо. Х Доказательство. Пусть даны Р'-ссотоятель'^е квазкпрофшш xi.ies. Образуем, коалицг "единомышленников" я',,...,йт. Так как квазипрофиль 'F-состоятелен', то суэствуе- набор стратегий а^,, равьjEeсный ъ игре Это означает, что

xэ V8^ для ХХл.

нп, более развернутг. что для любой коалиции к

=> для /=1.....т. (**)

Образуем теперь смешанный набор стратегий s* = (9^1,... Го^да для льбой коалиций Л' мы имеем включения

= л(*к1)(я-гг,)*э^-к) с ^киот-к-*)'

где последнее включение следует из (**). Так как это верно .для любого мы получаем включение

с = '"сФгг

То есть з* - сильное равновесие в игре С(л:, и квази-

профиль *(ХС является Р-состоятелышм. и

з 6. Достаточные условия1

Покажем, что эти три условия - монотонность, грубост., и состоятельности - достаточны для сильной имплементацип. Пусть Р -'множество всех г-ссстоятелышх-квазшрофилей. Напомним, что состоятельность Г означает существование свертки

*: л" -г-*

В частности, для любого семейства квазипрофилей определено непустое множество {которое является аналогом

приведр.-щого в з 1 множества ер(4д). Поэтом'/ можно, с зорудить сост?"5яой механизм к , главными стратегиями/которого являются эрленты множества 2\ а исходы в ситуации определяются с

помощью вертушки со'значена'тми в множестве Р{*9Я).

Посмотри?,I, какое соответствие имплементируется механизмом Х л"у, т.о. сравним соответствие Е с Ец{%р). Пусть Х# будет Р-состоятельный квазипрофиль, и Мы утверждаем, что а

является сильно равновесным исх;дом в игре с(л:Д#). Для этого все участники долины послать одно и то ке сообщение (8,1),Я), где б=Х# и_ тахД=а. Оказывается, что этот набор спбщений является сильным ' равновесием. Х Мн дожны убедиться в справедливости включений

для всех коалиций к. Оценим для этого множество р{5к,дд_к). Независимо от сообщений коалиции К -однг. из коалиций единомышленников будет содержать К-К, а .. значит, 0-компонента свертки (&к,вя_к) содержится в Хк. Поэтому

9к-к>> с (*<0кЛ-к>>0 с V что означает, что есть.сильное равновесие в игре с(яД#). Тем самым мы показали, что включение Р с выпоняется для

любого состоятельного сос Д'ветствия- Р.

11окажем теперь, что для монотонно:о грубого соответствия Р вшонено равенство Р Х= Eq(7tp). Пусть - -квазипрофиль, и аеЕд(я?Д^); докажем, что аеР'Х^). Альтернатива а является сильно равновесным, исходом в игре ССл^Д^); это означает существова: ие набора стратегий такого что

'.)аеКр^-Рнвд). и

2) Яр(Ьк,в,,_к) О ддя любой коалиции к. для дальнейшего ртм нужно переформулировать выражение я (б )_ Мокно псза^ь, что верна еле пущая общая

формула

= "в*>Г

В силу этой формулы условие 1) поено переписать как л# ^ = Из ЭгОГО 11 113 монотоности Р мы получаем

зключениеР(Х#) з Р{(*0^ф.

В силу грубости Р правам сторона равна ). Так как в силу 2) аеР(*Он), то ае?'(Х#).а

Подведем итог в следующей теореме.

хворема 3. Пусть Р - сосиоятельж з соответствие. Тогда Р с с Ец(р). Ёс/м, кроле того, Р лонотошше и грубое, mo'F=Eq(.яF).:

Следствие. Соответствие (определенное на кваэтрофилях) являете г сильно шииезтируелаш тогда и только тогда, когда о монотонно, грубо-и состоятельно.

з 7. Сильная реализация ядерного соответствия

Примени! предыдущий критерий к ядерному соответстьлю. Ядерное соответствие возникает, когда есть блокирование. Это понятие нам ук встречалось.в контекгтзе Нэш-реализации. Здесь мы дожны дать более об: .эе определение. Здесь блокированием будет называться отношение Б между множествами 2^ и. гл, которое удовлетворяет двум аксиомам:

В1. Есда ЕВХ, К'^К и Х'с1, то К'ВХ".

Б2. 08,3 и Ь'ВА (Б здесь и далее означает отрицание В).

Для заданного квази-гтофнля Х^ определим ядро С(В,Х#) как

fXw, если КВХД для каждоРкоалицттЯ, С(В,ХЧ) = Щ к :

10 в пропаном случае.

При вариации чвази-профиля ш получаем т.н. ядерное соответствие блокирования Л, которое обозначил как С(В): Qpr*===>/4. Из аксиомы В1 еидно, что соответствие С (В монотоннг.

ХЛемма. Ядерное соответствие С(В) грубое. Доказательство. Пусть - произвольный квази-профиль. Обозначим через производный квази-профиль, - те. Имеем

г 0, если ЯВХзик для некоторой коалиции S,

к i ХД в остальных случаях.

H дожны проверить, что

C(B,Y^)=C[B,X#).

Так как включение с очевидно, то мы дожны рг"смотреть лишь

случай, когда пножество С{В,Х^) непусто. Ко в этом случае ГЗХ^

для любой козлищи К (см. определение .ядра). Тем болел КВХкцк, для любого К' (r\. аксиому В1) и, следовательно, , Но

тогда равенство очевидно.п

После этого ворос об ыдиементации ядра сводится к вопросу о состоятельности ядерного соответствия. Чтобн ' дать ответ на этот вопрос, нам нужно еще одно понятие.

Определение 7. Блокироваш-.е В сильное, если выпонена аксиома

ВЗ. Если КВХ, К'ВХ' и Щ'=1,ло (КПК')В(ХПХ').Х')Х

Предложение. Яберное соответствие С(В) состоятельно тогиЛ и юяысо тогда,, когда блокирование Б аньное.

Доказательство. Предположил, что В сильное, и проверил состоятельность С(Р;. Пусть 11 = -. некоторое разби-

ение, jljj, ...,Х^ - соответствующие состоятельные квазипрофили. Мы дожны проверить, что Х,( = свертка(X*,...также есть состоятельный квази-профиль, т.е. что ядро С(ВХ#) непусто. Состоятельность квази-профиля означает, что никакая

коалиция К не блокирует Х^. Из аксиомы вз мы имеем тогда, 1то К не блокирует множество

хк = ^г^я-к3 )Цк* В самом деле, К есть пересечение (М-'ж, 3=1,...,т. Но ето как раз и означает, что,С(В,Х#) непусто. . Мы опустим .проверку обратного утверждения.в Подведем итог.в следующей теореме.

Теорема 4. Ядерное соответствие С(В) б локирования В сильно реалииуеиа тогда и только тогда, когда блокирование Б сильно.в

ЖГЕРТУРА

1. Данилов В.И. Экономическое равновесие -и обобщенные цени//Исследования по стохастической теории управления_ и математической экономике. М. ЦЭШ, 1981

2. Данилов В.И. Невальрасови 4авновесие и обсбп-чшая лемма Гейла//Математическая экономика и экс ?ремальяче Х задачи. ' М., 1984

3. Данилов В. И., Сотсков А.И. Чистый 'обмен при меновых стоимостях//Проблема равновесия и принятие экономических решений. М., ЦЭШ, 1985

4. Данилов В.к., Сотсков А.И. Уравновешенные состояния ц теоремы о ядре//Оптимизация,- т. 41, 1987

5; Данилов В.И. Меновая стоимость как эквивалент обмена //Математические модели экономических механизмов. М., ЦЭМИ, 1988

6. Danilov V.I. and Sotskov ' A.I. A generalized, eoonomio equillbriuin//Journal of raath. eoonornios, v. 19 n.4 (1990), 341-356

7. Danilov V.I. and Sotskov A.I. Abst"aot Convex Spaoes (сдана в печать)

8. Данилов В И. Согласование толерантных предпочти ний//Категория общеотгонной полезности: вопросы методо . логии и структуризации.' М. ЦЭШ, 1982

9. Данилов З.И. Агебраические аспекты группового выбора// Исследования по математической экономике и теор*ш управления. М., ЦЭМИ, 1982

10. Данилов В.И. Модели группового выбора//Техническая кибернетика, 1983

11. Данилов В.и! Структура бинарных правил агрегирования предпочтеннй//Экономика и матем. метода, т.20, 1984

12. Данилов В.И., Сотсков'A.M. Рациональный выбор и выпуклые предпочтения/Техническая кибернетика, 1985

13. Данилов В.И. Аксиома Виля в теории выбора//Техкическая кибернетика, 19851985

14. Данилов В.И. Агрегирование дихотомических предпо . чт .;ний//Проблема равновесия и пр1шятие экономически

решений. М., ЦЭШ, 1985

16. Danilov V.I. Aggregation of dichotomic prefei зпоеа //Mathema tical Social Soienoes, 13 1985 ,

16. Данилов В.И., Сотсков А.И. Конкурентные равновесия в коалиционных 'грахУ/Обществетитя полезность: зканош1ко-математический анализ. Ы., ЦЭММ, 1984

17. Данилов В.И., Сотсков А.И. Стабильны" блокирования- в, мехаю1зые'х груш.)вого выбора// Экономика и татем, методы, т.23, 1987

18. Данилов В.П., Союков А.И; Коалиционно-устойчивые механизмы группового выбора//Экочоы.нка и матеы. методы, т.24, 1980

19. Цанилов В. И. Доминантно-стратегические механизмы в эвклидовой 0бсгаи0вке//ма^ема'1ические модели ^'оношческих механизмов. Ы., ЦЭММ, 1988

20. Данилов В.Ж., Соvсков А.И. Механизмы группового выбора. Наука, 19Э1

21. Данилов В.Г., Потеков 4.И. Имплементация соответствий группового выбора коалиционными равновесиями//Рконоьшка и "матем. методы, т.27, вып.4, (1991) стр. 720-732

22. Danilov л7.1. Implement at ion via Hash equilib'ria//~'aonomet-rica, 1991, v. 59

23. Danilov V.I. and Sotskov- 'A.I. On strongly consistent social choioe functions (сдана В Journal of math, economics)

24. Danilov V.I. Or atrongly Tmplementatable oorrespondebces (сдана в Journal of math, eoonomi s)

к "ouli . 11.. Teleg B. Core of Effeotivity Functions and < Implementation Theory // J. Hatu. Eoon. "982. v. 10. Jb 1.

26. f'oulin H. The Б+rategy of Sooial ' Choice. Amsterdam, 19P3- Х '

27. Ho ore J., liepv.Ho R. Kash.. Implementation: A Pull Characterisation // Econometrion 19Q0. v. 58., 1083-1100

28. ~askiii El "Hash Equilibrium and ?<elfare Optimality", rnlnieo, U I.T., 1977.

29. Dutta Q., Sen A. Implementation under strong equilibrium: A\ Hath. Eoon., 1991, v. 20,

Похожие диссертации