WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     || 2 |
-- [ Страница 1 ] --

Р О С С И Й С К А Я А К А Д Е М И Я Н А У К ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА С.Н. Петраков Механизмы планирования в активных системах: неманипулируемость и множества диктаторства П Р

Е П Р И Н Т Москва 2001 УДК.65.012.

Петраков С.Н.

Механизмы планирования в активных системах:

неманипулируемость и множества диктаторства - М., 2001 (Институт проблем управления им. Трапезникова В.А. РАН Исследуется манипулируемость механизмов планирования в активных системах с сообщением информации.

Рецензент:

Текст препринта воспроизводится в том виде, в котором представлен авторами.

Утверждено к печати Редакционным советом Института Содержание Содержание …………………………………………………………….. 3 Введение ………………………………………………………………... 4 Глава I. Механизмы функционирования активных систем с сообщением информации §1. Описание модели активной системы с сообщением информации 9 §2. Неманипулируемость механизмов планирования..….…………... §3. Реализуемость соответствий группового выбора.……………….. §4. Достоверная реализуемость соответствий группового выбора … §5. Топологические методы в теории коллективного выбора.……… §6. Постановка задачи исследования манипулируемости механизмов планирования...…………………………………………... Глава II. Условия неманипулируемости прямых механизмов планирования, сформулированные в терминах множеств диктаторства §1. Множества диктаторства и неманипулируемость прямых механизмов ……………………………………………………………...

§2. Коалиционная неманипулируемость прямых механизмов ……... §3. Неманипулируемость и реализуемость механизмов активной экспертизы и распределения ресурса ………………………………… §4. Неманипулируемость прямых механизмов планирования с векторными планами …………………………………...……………... Глава III. Существование эквивалентных прямых механизмов §1. Прямые и непрямые механизмы планирования …………………. §2. Существование равновесия Нэша ………………………………... §3. Существование эквивалентного прямого механизма …………… §4. Существование эквивалентного прямого механизма для дифференцируемых процедур планирования и линейных процедур планирования …………………………………………………………... § 5. Влияние множества возможных сообщений на существование эквивалентного прямого механизма ………………………………….. Заключение ……………………………………………………………... Литература ……………………………………………………………… Приложение …………………………………………………………….. Введение В социально-экономических системах (активных системах), функционирующих в условиях изменяющейся внутренней и внешней среды наряду с социально-экономическими факторами, действие которых учитывается управляющим органом (Центром), существуют факторы, предсказать возникновение и воздействие которых достаточно сложно для управляющего органа в силу ограниченности возможностей цента по сбору и переработке информации. Обычно, остальные участники активной системы (активные элекменты) осведомлены о неизвестных центру параметрах гораздо лучше центра.

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

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

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

Объектом настоящего исследования являются механизмы функционирования активных систем с сообщением информации.

Предметом исследования является неманипулируемость механизмов планирования1 в активных системах с сообщением информации.

1) Механизмы, в которых в качестве принимаемого ЛПР решения выступает набор скалярных величин, регламентирующих действия В случае, если сообщение достоверной информации является равновесием Нэша, механизм планирования называется неманипулируемым.

Целью работы является получение условий неманипулируемости механизмов планирования в активных системах с нетрансферабельной полезностью и однопиковыми и сепарабельными функциями полезности активных элементов.

Реализация указанной цели подразумевает решение следующих задач:

- получение условий неманипулируемости прямых механизмов;

- получение общих условий существования эквивалентных прямых механизмов;

- получение конструктивных условий существований эквивалентных прямых механизмов для широкого класса практически значимых частных случаев механизмов планирования;

- исследование влияния множества допустимых сообщений на существование эквивалентного прямого механизма.

В работе развивается метод анализа множеств диктаторства2), который основывается на применении аппарата теории активных систем, системного анализа и исследования операций.

Ниже описан предложенный автором метод анализа множеств диктаторства в механизмах планирования. На основе предложенного метода получены: достаточные условия неманипулируемости прямых механизмов в терминах множеств диктаторства;

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

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

2) Множество возможных предпочтений в механизмах планирования можно разбить на подмножества, в каждом из которых определенной группе АЭ будут назначаться оптимальные планы. Такие множества называются множествами диктаторства.

механизмов планирования общего вида;

достаточные условия неманипулируемости механизмов планирования с векторными планами;

достаточные условия существования эквивалентных прямых механизмов;

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

в рамках выбранного метода исследовано влияние множества возможных сообщений на существование эквивалентного прямого механизма.

Результаты работы позволяют значительно расширить множество прямых механизмов планирования, для которых доказана их неманипулируемость. Также расширен класс непрямых механизмов, для которых доказано существование эквивалентных прямых механизмов.

Конструктивные условия существования эквивалентных прямых механизмов позволяют строить эффективные (с точки зрения критерия управления) неманипулируемые механизмы планирования, для активных систем, в которых существуют удовлетворительные (с той же точки зрения) непрямые механизмы планирования.

Во введении обосновывается актуальность проблемы, формулируется цель и задачи работы, приводится краткое изложение основного содержания работы.

Изложение материала имеет следующую структуру. Первая глава посвящена общей постановке задачи и обзору результатов исследований активных систем с сообщением информации, полученных в отечественных и зарубежных работах. В §1 дается общая постановка задачи: определяются состав, информированность и порядок функционирования системы с сообщением информации, а также описываются предпочтения элементов системы, определяются механизм функционирования системы с сообщением информации и модели поведения элементов системы. В §§ 2-3 приводится обзор существующих на настоящий момент работ, посвященных неманипулируемости механизмов планирования и реализуемости соответствий группового выбора. В §4 приводится обзор результатов работ, посвященных условиям существования эквивалентных прямых механизмов для непрямых механизмов планирования. В §5 конкретизируется постановка задачи настоящего исследования.

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

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

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

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

литературу, доказательства оригинальных результатов вынесено в приложение.

Неманипулируемость Неманипулируемость CW – функции выбора механизмов вида [53] (раздел 1. c : (Rm )n Rm настоящей работы) [7] (раздел 1.2) Неманипулируемость Неманипулируемость Неманипулируемость прямого механизма прямого механизма прямого механизма, активной экспертизы распределения ресурса удовлетворяющего [87,89] (раздел 1.4) [87,89] (раздел 1.4) А.1.2.1, 1.2.2. [111,112] (раздел 1.2) Достаточные условия Достаточные условия Необходимые условия неманипулируемости коалиционной коалиционной прямого механизма неманипулируемости неманипулируемости (Т.2.1.1, раздел 2.1) (Л.2.2.1, раздел 2.2) (Л.2.2.2.,2.2.3 раздел 2.2) Существование Неманипулируемость равновесия Нэша механизмов (Т.3.2.1, раздел 3.2) планирования вида c : (Rm )n Rm Достаточные условия существования эквивалентного прямого механизма (Т.3.3.1, раздел 3.3) Достаточные условия Достаточные условия Достаточные условия существования существования существования эквивалентного прямого эквивалентного прямого эквивалентного прямого механизма для линейных дифференцируемого дифференцируемого процедур планирования двухэлементного многоэлементного (Т.3.4.1, раздел 3.4) механизма механизма планирования (Т.3.4.2, планирования (Т.3.4.3, раздел 3.4) раздел 3.4) Рис. 0.1. Структура теоретических результатов настоящей работы Глава 1. Механизмы функционирования активных систем с сообщением информации §1. Описание модели активной системы с сообщением информации Будем рассматривать организационные (активные) системы (АС) с двухуровневой структурой. Такая организация состоит из управляющего органа — центра и конечного числа подчиненных ему активных элементов (АЭ). Множество АЭ обозначим I = {1,..., n}. Задачей центра является выбор некоторого множества альтернатив X из заранее определенного множества возможных альтернатив A. Предпочтения элементов и центра [104,119,122] на множестве A задаются бинарными отношениями, определяющими в общем случае нестрогий порядок над A. Элемент i I характеризуется отношением предпочтения Ri.

Множество возможных предпочтений i - го элемента обозначим i.

Строгую компоненту отношения Ri будем обозначать Pi. Вектор отношений предпочтения всех элементов R = (R1,..., Rn ) называется профилем предпочтений. Множество всех возможных профилей предпочтений обозначим через, =. Предпочтения центра i iI также будем задавать бинарным отношением и обозначать RP (R1,...., Rn ), отношение предпочтения центра является нестрогим порядком над A, который зависит от профиля предпочтения активных элементов (изучение конкретного вида этой зависимости, а также задач агрегирования предпочтений [3,22,108] выходит за рамки настоящей работы).

Будем предполагать, что для каждого профиля предпочтений АЭ R задана альтернатива z(R) A, которая является наихудшей из допустимых для центра альтернатив. Определим верхний срез H (z(R), RP (R)) отношения RP (R) по альтернативе z(R) следующим образом H (z(R), RP (R)) = {a A aRP (R)z(R)}. Множество допустимых для центра альтернатив определим как соответствие F(R) = H (z(R), RP (R)) и будем называть это соответствие соответствием группового выбора (СГВ).

Сделаем следующее предположение об информированности:

центру неизвестен профиль предпочтения активных элементов, активные элементы имеют информацию о предпочтениях других элементов [28,29,43,44,49,113,121].

Примем следующий порядок функционирования системы.

Поскольку профиль предпочтений неизвестен центру, он запрашивает от элементов информацию, и те посылают в центр сообщения si.

Множество возможных сообщений i - го участника обозначим Si.

Совокупность сообщений участников назовем вектором сообщений и обозначим s = (s1,..., sn ). Множество всех возможных векторов сообщений обозначим через S, S =. Получив сообщения, центр по S i iI процедуре принятия решения g : S A выбирает единственную альтернативу g(s) A, которая считается решением. Совокупность множества возможных сообщений S и заданной на нем процедуры называется механизмом принятия решений, G = (S, g).

Моделью поведения активного элемента служит понятие равновесия [89,96,104,106,115]. В настоящей работе используются два типа равновесия: равновесие Нэша и равновесие в доминантных стратегиях.

Допустим, задан профиль предпочтений элементов R и механизм (S, g). Вектор сообщений s называется равновесием Нэша при данном R, если для любого активного элемента i I и любого его сообщения si Si выполняется g(s)Rig(si, s-i), где s-i называется обстановкой для i - го активного элемента и обозначает вектор размерности n -1 с компонентами вектора s за исключением i - ой компоненты: s-i = (s1,..., si-1, si+1,..., sn ). Таким образом, в равновесии Нэша s ни один из игроков не выигрывает, отклоняясь из равновесия в одиночку и посылая сообщение si, отличное от равновесного si.

Сообщение элемента si называется доминантной стратегией для элемента i I при данном Ri, если si Si и s-i S-i выполняется g(si, s-i )Rig(si, s-i ).

То есть, сообщение si является для i - го элемента при данном Ri оптимальным независимо от того, что сообщают остальные активные элементы.

Вектор сообщений s называется равновесием в доминантных стратегиях при данном профиле предпочтений R, если i I, si Si, s-i S-i выполнено g(si, s-i )Rig(si, s-i ). Другими словами, у каждого элемента есть сообщение si, оптимальное при любых сообщениях остальных элементов s-i, и в равновесии s каждый элемент посылает именно это сообщение.

Пусть задан механизм G = (S, g) и множество возможных профилей предпочтений. Для R множество равновесных векторов N сообщений обозначается через EG (R) при использовании определения D равновесия Нэша и EG (R) при использовании определения равновесия в доминантных стратегиях. Когда ясно, какое из определений равновесия используется, либо утверждение верно для обоих определений, индекс равновесия указываться не будет: EG(R).

Легко показать, что для любого механизма G = (S, g) при любом D N профиле предпочтений R выполняется EG (R) EG (R).

В качестве иллюстрации введенных определений рассмотрим следующий пример.

Пример 1.1.1. Пусть n городам (активным элементам) необходимо пробурить артезианскую скважину в некоторой области - множестве возможных альтернатив A. Для простоты положим, что это - единичный квадрат A = [0, 1][0, 1] R2. Координаты скважины обозначим x = (x1, x2 ). Будем считать, что для каждого города i I есть оптимальная с экономических позиций точка ri = (ri1, ri2 ) [0, 1] множества A, стоимость доставки воды из которой минимальна, например, центр этого города. Положим эту стоимость равной нулю.

Далее предположим, что затраты на транспортировку пропорциональны квадрату расстояния от скважины до абсолютно оптимальной точки.

Предпочтения элементов могут быть заданы функцией полезности, поскольку она порождает транзитивное бинарное отношение. Если предположить, что каждый город стремится минимизировать собственные затраты, получим, что предпочтения каждого города выражены некоторой функцией полезности (x, ri ) = -[(x1 - ri1)2 + (x2 - ri2 )2].

i В качестве центра в этом примере выступает комиссия по экологической безопасности, которая стремится минимизировать ущерб, наносимый природе при транспортировке воды. Если считать, что этот ущерб пропорционален затратам на транспортировку, то целевая функция центра может быть представлена в виде (r1,..., rn, x) = (x, ri ). Чтобы i iI минимизировать суммарные затраты всех городов на транспортировку воды, необходимо разместить скважину следующим образом x = ri.

n iI Центр, не зная истинных положений оптимальных точек элементов, готов допустить отклонение значения целевой функции от максимального значения на 50 %, то есть СГВ будет выглядеть следующим образом F(r1,..., rn) = [0,1]2 i (x, ri ) 0,5, ri.

x 1 r i i n iI iI iI В этом примере функции полезности (x, r) представляют i отношения предпочтения Ri, поскольку все функции полезности параметризованы параметром r можно считать предпочтения заданными, когда задано значение r.

Поскольку скважина строится сообща, у администраций городов просят сообщить положения идеальных точек. Администрация каждого города направляет в комиссию по строительству скважины оценку положения идеальной точки si = (s1, si ), где si [0, 1][0, 1]. Координаты i скважины находятся по этим оценкам следующим образом x = g(s1,..., sn ) = si.

n iI Здесь в качестве сообщений выступают оценки положений идеальных точек si, а множеством возможных векторов сообщений будет S = si.

[0, 1]2. Процедурой принятия решения будет g(s1,..., sn ) = n iI iI Пара (S, g) составляет механизм принятия решений.

Допустим n = 2 и идеальная точка первого города r1 = (0.8, 0.4), а второго r2 = (0.9, 0.2). Если города сообщат достоверную информацию, то скважина будет построена в точке x = (0.85, 0.3). Затраты городов i будут равны = 0.0125 и = 0.0125. Если первый город сообщит 1 оценку s1 = (0.7, 0.6), а второй город по-прежнему будет сообщать достоверную информацию, скважина будет пробурена в точке x = (0.8, 0.4) и затраты городов на транспортировку воды будут равны соответственно 0 и 0.05. Если комиссия поставит условия, что скважина будет пробурена только после того, как оценки стабилизируются, то получим многошаговый процесс, во время которого каждый город будет изменять свое сообщение, пытаясь максимизировать свою функцию полезности.

Если администрации городов не обмениваются информацией, оценки стабилизируются только тогда, когда изменять своё сообщение каждому городу при неизменном сообщении другого города будет невыгодно. В нашем примере такими сообщениями будут s1 = (0,6;

0,8) и s2 = (1;

0). Затраты городов при этом будут равны соответственно (0, 0.05). Очевидно, меняя своё сообщение, второй город не может приблизить место бурения к своей оптимальной точке. Скважина будет пробурена точно в точке, оптимальной для первого города.

Таким образом, ситуация, когда сообщение первого города s1, а второго s2 будет при заданных r1 и r2 равновесием Нэша (но не будет равновесием в доминантных стратегиях).

Как видим, если комиссия не имеет информации о местоположении идеальных точек городов, место бурения, определенное при помощи механизма принятия решения (S, g), не будет равным x = (0.85, 0.3), т.е. не будет оптимальным с точки зрения минимизации экологической опасности проекта. Однако, суммарные затраты городов на транспортировку воды от места бурения, определенного при помощи механизма (S, g), будут составлять 0,05, а от точки, оптимальной для центра – 0,025. Так как центр готов допустить отклонение значения целевой функции от максимального значения на 50%, построенный механизм можно считать удовлетворительным.1) Рассмотренный пример в общих чертах качественно отражает введенные определения и проблемы, возникающие при исследовании механизмов функционирования систем с сообщением информации.

Таким образом, при изучении системы с сообщением информации необходимо выделить элементы системы, определить их предпочтения, информированность и порядок функционирования системы, а также модели поведения АЭ. На основании предпочтений центра строится СГВ, отражающее представления центра об эффективности функционирования системы. В настоящей работе будем 1) Знак “” здесь и далее обозначает окончание примера предполагать, что элементы системы, предпочтения, информированность и порядок функционирования системы определены и фиксированы.

Допустимое для центра СГВ определяется из соображений оптимальности его для центра. Выбору оптимальных для центра альтернатив посвящено большое количество работ по исследованию операций [77,95,102,103,121]. Поскольку в круг наших интересов будет входить в основном анализ механизмов функционирования, мы будем полагать, что допустимое для центра СГВ определено.

Как видно из примера 1.1.1, каждый из АЭ стремится максимизировать собственную полезность, вследствие чего может сообщать недостоверную информацию. В тоже время, сообщение недостоверной информации может быть нежелательным для центра.

Таким образом, одной из задач центра может быть построение неманипулируемого механизма функционирования АС, в котором АЭ выгодно сообщать достоверную информацию.

С другой точки зрения, манипулируемый механизм, построенный в примере 1.1.1, может считаться центром удовлетворительным (так как обеспечивает не более 50% потерь). Таким образом, в задачи центра также может входить построение удовлетворительных с его точки зрения механизмов функционирования АС, то есть механизма функционирования, реализующего заданное СГВ (см. раздел 1.2).

Качественно, из литературы известно, что при достаточно богатых множествах возможных предпочтений АЭ механизмы с сообщением информации оказываются диктаторскими (в теоремах о невозможности [3,7,22,32] существует единственный АЭ – диктатор). В настоящей работе мы рассматриваем более “узкий” класс предпочтений (сепарабельные, обобщенно однопиковые), что приводит к появлению групп диктаторов, различных для разных подмножеств множества возможных предпочтений.

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

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

работы, посвященные исследованию механизмов функционирования систем с сообщением информации, полезность элементов которых трансферабельна, как общего вида [23,30,31,32,33,34,35,37] так и механизмов частного вида [4,7,36,37,38,54,69,70,120];

работы, посвященные исследованию неманипулируемости прямых механизмов функционирования систем с сообщением информации, в которых в явном виде выделены условия неманипулируемости механизмов функционирования [7,9,10,22]. Эти работы и будут представлять для нас основной интерес.

В настоящем параграфе будем рассматривать механизмы, в которых каждый элемент с номером i I сообщает центру только своё отношение предпочтения Ri i. Тогда пространство возможных сообщений S будет совпадать с, а процедура планирования h будет отображением из в A. Такие механизмы называются прямыми.

Обычно прямые механизмы обозначаются H = (, h).

Прямые механизмы, в которых сообщение достоверной информации является равновесием в доминантных стратегиях D R EH (R), называются неманипулируемыми. Формальное определение неманипулируемого механизма следующее. Пусть H = (, h) – прямой механизм. Механизм H неманипулируем, если и только если D R, R EH (R), либо (что одно и тоже) i I, Ri i, Ri i, R-i -i выполняется h(Ri, R-i)Rih(Ri, R-i ).

Интересен тот факт, что определение неманипулируемого механизма можно строить, используя определение равновесия по Нэшу N EH (R), что устанавливается следующей теоремой.

Теорема 1. 2.1 [22]. В прямом механизме H = (, h) для любого R, N D R EH (R) тогда и только тогда, когда R, R EH (R).

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

Одной из основных проблем в теории коллективного выбора является существование набора так называемых результатов о невозможности существования функций коллективного выбора, удовлетворяющих тем или иным условиям (impossibility results), и, в частности, теорема Эрроу [2,3].

Рассмотрим активную систему с n АЭ. Множество возможных альтернатив A состоит не менее чем из трех альтернатив, A 3.

Предпочтения каждого i - го АЭ представляются упорядочением (полным, транзитивным, ассиметричным бинарным отношением) Pi множества A. Обозначим ( A) - класс всех допустимых упорядочений множества A, а S(A) - класс всех упорядочений, которые допустимы в качестве коллективного выбора.

Функцию коллективного агрегирования (ФКА) определим как отображение из :(( A))n S(A). Таким образом функция коллективного агрегирования каждому набору предпочтений активных элементов из множества ((A))n ставит в соответствие коллективное упорядочение из множества S(A).

Говорят, что ФКА :((A))n S(A) оптимальна Парето (ПО) [2,3], если для любых двух альтернатив a1, a2 A и любого профиля P = (P,..., Pn) такого, что i I a1Pia2 выполняется a1(P)a2.

Говорят, что ФКА :((A))n S(A) удовлетворяет условию независимости от посторонних альтернатив по Арроу (НПАА) [2,3], если для любых двух альтернатив a1, a2 и любых двух профилей предпочтения P, P таких, что a1Pia2 тогда и только тогда, когда a1Pia выполняется a1(P)a2 тогда и только тогда, когда a1(P )a2.

Говорят, что ФКА :((A))n S(A) удовлетворяет условию универсальности множества возможных предпочтений (УМВП), если (A) является множеством всех упорядочений над A.

Говорят, что ФКА :((A))n S(A) является диктаторской, если существует АЭ i I такой, что для любого P ((A))n выполняется (P) = Pi.

Верна следующая Теорема 1.2.2 [2,3]. Любая ФКА удовлетворяющая ПО, НПАА, УМВП является диктаторской.

Механизм коллективного выбора g :((A))n A назовем диктаторским, если существует АЭ i I такой, что для любого профиля предпочтений P = (P,..., Pn)((A))n и для любой альтернативы из множества значений механизма a g([(A)]n), если a g(P), то g(P)Pia.

Как и для функций коллективного агрегирования справедлив следующий результат о невозможности.

Теорема 1.2.3 [26,65]. Если множество значений механизма g :((A))n A состоит не менее чем из трех альтернатив, g[((A))n]> 3, механизм g неманипулируем и удовлетворяет УМВП, то он является диктаторским.

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

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

Наиболее глубоко исследована неманипулируемость механизмов планирования [80,82,84,85,86,106,112] и их частных случаев – механизмов экспертизы и/или голосования [7,32,33,53,66]. В таких механизмах множество возможных альтернатив представляет собой подмножество конечномерного Евклидова пространства. При этом, предпочтения АЭ задаются функциями полезности, i I, которые ставят в соответствие i каждой альтернативе действительное число, характеризующее полезность данной альтернативы для элемента. Предпочтения, выраженные функцией полезности можно считать частным случаем предпочтений, заданных бинарными отношениями в силу того, что любая функция полезности порождает бинарное отношение [109].

Работы зарубежных авторов посвящены в основном изучению неманипулируемости механизмов функционирования систем с сообщением информации, которые являются моделями систем голосования [7,32,33,53,66], экспертиз и т.п. В таких механизмах компоненты вектора Евклидова пространства, которым является альтернатива, в явном виде присутствуют в функциях полезности всех АЭ. Такие системы с сообщением информации называются экономиками с общественными товарами (Economies with common (public) goods) [32,33,54]. Круг вопросов, возникающих при исследовании механизмов функционирования таких систем, не ограничивается только неманипулируемостью и включает в себя проблемы устойчивости равновесий, соответствия теории активных систем с теорией информации и др. [105,114], обсуждение которых выходит за рамки настоящей работы.

Наиболее простыми механизмами функционирования АС являются механизмы голосования, исследуемые в работе [53]. Множество возможных альтернатив в таких механизмах является подмножеством множества действительных чисел.

Пусть множество возможных альтернатив A = [0, 1] R1.

Обозначим через B, множество непустых, замкнутых подынтервалов [0, 1].

Функция полезности называется однопиковой, если u : A R существует точка r A, называемая точкой пика функции полезности u, такая, что u(x) строго возрастает при x < r и строго убывает при x > r, то есть x A, таких, что x r и для любых, таких, что 0 < < выполняется u(x) < u( x + (1- )r) < u(r).

Множество всех однопиковых функций полезности обозначим через SP. Поскольку функция полезности задает на A некоторое отношение предпочтения, в дальнейшем под профилем предпочтений будем понимать совокупность функций полезности всех элементов.

Введем следующие ограничения на класс допустимых механизмов функционирования. Пусть задано множество активных элементов I = {1,..., n}, однопиковой функцией выбора (в обзоре мы будем в основном придерживаться оригинальных названий и обозначений, введенных авторами в соответствующих работах, в наших определениях функция выбора соответствует механизму функционирования) назовем отображение S : SPn B A, ставящее в соответствие каждому профилю предпочтений u = (u1,..., un) SPn и любому подынтервалу B B альтернативу S(u, B) из B. В настоящем разделе будем предполагать, что выполнены следующие условия:

i) анонимность: S симметрична по отношению к переменным u1,..., un ;

ii) эффективность: для всех u, B и для всех y B таких, что x = S(u, B) и i I, ui(x) ui(y), выполняется i I, ui (x) = ui (y) ;

iii) непрерывность по отношению к подынтервалам:

S(u, B) непрерывна по отношению к B B.

Однопиковая функция выбора S, определенная для множества элементов I, обладает свойством независимости от посторонних альтернатив по Нэшу (NIIA) [53], если для всех u SPn и для всех B, B Bn выполняется:

если B B и S(u, B) B то S(u, B ) = S(u, B).

Если для всех u, u SPn и для всех B B выполняется:

для всех i I и всех x, y B таких, что ui(x) ui( y) ui(x) ui( y) верно S(u, B) = S(u, B), то однопиковая функция выбора обладает свойством независимости от посторонних альтернатив по Эрроу (AIIA) [3,53].

Свяжем с каждым профилем предпочтений = (,..., ) SPn 1 n профиль пиков ( r - профиль) r = (r1,..., rn), где ri - пик ui. Далее мы будем рассматривать только такие функции выбора, которые зависят только от профиля r.

Пусть a1,..., a2n-1 – (2n -1) альтернативы из A (не обязательно различные). Их медианой называется единственная альтернатива a = med (a1,..., a2n-1), такая, что {i I 1 i 2n -1, a ai} n и {i I 1 i 2n -1, ai a} n.

Пусть задано множество активных элементов I ={1,..., n} и (n -1) фиксированные альтернативы (не обязательно различные),..., A. Определим для произвольных u, B функцию выбора 1 n- обобщенного победителя по Кондорсе (CW - функцию) S(u, B) = projBmed (r1,..., rn,,..., ) = 1 n- B B B = med (r1B,..., rn, a1,..., ), n- B где (r1,..., rn) – r - профиль u и piB ( ) обозначает проекцию ri, i соответственно на B. Здесь, под проекцией некоторого элемента на i множество понимается ближайший к этому элементу элемент множества.

Множество всех CW - функций { S} R обозначим через CW.

n- Определенная таким образом функция выбора удовлетворяет анонимности, эффективности и непрерывности по отношению к подынтервалам.

Известны следующие свойства CW - функций.

Теорема 1.2.4 [53]. S CW :

i) S неманипулируема;

ii) S определяется (n -1) альтернативами = S(uk, A), k 1 k n -1, где uk - профиль, такой, что ri = 1, i =1, k и ri = 0, i = k +1, n.

iii) S - бескомпромиссные, то есть u SPn, x = S(u, A), если i I такой, что x < ri ( ri < x ), то ui SP : x ri (ri x) выполняется x = S(ui, u-i).

Теорема 1.2.5 [53]. Для любой однопиковой функции выбора S в рамках рассматриваемой модели следующие утверждения эквивалентны:

i) S неманипулируема и удовлетворяет NIIA;

ii) S бескомпромиссна и NIIA;

iii) существует = (,..., ) An такой, что S = S.

1 n Класс CW - функций характеризуется следующими свойствами.

Теорема 1.2.6 [53]. Однопиковая функция выбора удовлетворяет NIIA и AIIA тогда и только тогда, когда она является CW - функцией.

Как оказалось, класс допустимых функций полезности, на которых функции из CW неманипулируемы, можно расширить.

Через FP обозначим класс одноплатовых функций, v FP, если существует пара fp = (r-, r+), называемая плато функции v, такая, что строго возрастает при x < p-;

0 r- r+ 1 и v (x)постоянна на x [ p-, p+];

строго убывает при x > p+.

В то время, как предпочтения элементов допускают несколько максимальных элементов, будем исследовать однозначные функции выбора, которые отображают профиль плато ( fp - профиль) в единственную альтернативу ( fp). Выбор на интервале будет определяться выражением S(, B) = projB ( fp).

Обобщенная CW - функция для одноплатовых функций n(n -1) полезности определяется +1 параметрами. Эти параметры для I = {1,..., n} выбираются следующим образом: = ( ), где 0, n и + n ;

при этом 0 1 и = 1 при 1 n,, = 0 при 1 n. Предположим так же, что для выполнено следующее свойство монотонности:

, когда + n -1 и n -1;

+1,, когда + n -1 и n -1.

, + Для заданного множества активных элементов и набора ( ), удовлетворяющего введенным выше условиям, поставим каждому профилю из FPn две конечные цепочки в [0, 1] :

сигнатура u - строго возрастающая последовательность 0 = q0 < q1 <... < qt <... < qT < qT +1 =1, составленная из альтернатив 0, 1, ri-, ri+, i I, где fpi = (ri-, ri+) - плато ui. Таким образом T 2n с равенством только тогда, когда все ri-, ri+ различны и не равны 0, 1.

- спектр профиля - это не возрастающая последовательность =... = =, 0 t T 0 0 t t T T где T то же, что и в определении сигнатуры и = {1 i n qt+1 pi-} t = {1 i n pi+ qt}.

t Наконец - обобщенную CW функцию S определим на FPn как S(, B) = projB ( fp), где fp есть fp - профиль.

( fp) = med (q1,...,,..., ) 0 T Параметры интерпретируются так же, как и для однопиковых функций полезности:

( fp) =, если элементов имеют предпочтения fpi = (1, 1), элементов - fp = (0, 0), n - ( + ) элементов - fp = (0, 1).

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

Лемма 1.2.1 [53]. Зафиксируем r+, fp2,..., fpn и для всех x таких, что 0 x r1+ обозначим (x)= ( fp1(x), fp2,..., fpn), где fp1(x) = (x, r1+).

Тогда могут возникнуть лишь два следующих случая:

случай i) r1+ (0) и (x) = (0) для всех x : 0 x r1+ ;

случай ii) (0) (r1+) r1+ и (x) = (0), если 0 x (0), (x) = x, если (0) x (r1+), (x) = (r1+), если (r1+) x r1+.

+ Если меняется y = p1 при постоянных r1-, fp2,..., fpn, то возможны лишь следующие случаи случай i ) (1) r1- и (y) = (1) для всех y : r1- y 1;

случай ii') r1- (r1-) (1) и (x) = (0), если r1- y (r1-), (x) = x, если ( p1 ) y (1), (x) = (r1+ ), если (1) y 1.

Следствие 1 из Л.1.2.1 [53]. Для всех наборов, удовлетворяющих ограничениям (1.6.1), (1.6.2), отображение непрерывно по fp, не убывает и липшицево по каждой из переменных pi+, pi-, i =1,..., n. Кроме этого бескомпромиссно в следующем смысле. Возьмем произвольный ~ fp - профиль и положим ( fp) = z. Для всех i и всех плато fpi в ~ каждом из следующих случаев имеем ( fp)= ( fpi, fp-i) :

~ i) { z < ri- и z ri } ii) {pi+ < z и ~i+ z} p ~ iii) {pi- < z < pi+ и ~i- z pi+} p ~ iv) {z = pi = pi для некоторого {+, -}.

Характеристические свойства обобщенных CW функций на множестве одноплатовых функций полезности определяет следующая Теорема 1.2.7 [53]. Пусть задано множество I ={1,..., n}. Функция выбора на множестве одноплатовых профилей FPn удовлетворяет NIIA и AIIA тогда и только тогда, когда она является обобщенной CW функцией.

Следствие 1 из Т.1.2.7 [53]. Обобщенная CW - функция коалиционно неманипулируема.

Следующая теорема 1.2.8. показывает, что невозможно расширить определение класса обобщенных CW - функций на класс квазивогнутых функций полезности QC, то есть таких, что x, y, [0, 1] выполняется ( x + (1- )y) inf { (x), (y)}. Другими словами, существует альтернатива r, не обязательно единственная, такая, что u не убывает на [0, r] и не возрастает на [r, 1].

Теорема 1.2.9. [53] Для всех целых n не существует функций выбора на QCn, удовлетворяющих NIIA и AIIA одновременно.

Итак, мы рассмотрели неманипулируемые механизмы в случае, когда функции полезности элементов являются однопиковыми либо одноплатовыми при множестве возможных альтернатив, состоящем из отрезка [0, 1] действительной оси. Далее мы рассмотрим обобщения этих результатов на случай, когда множество возможных альтернатив представляет собой m - мерное пространство векторов. В частности, следующая модель является обобщением предыдущей и допускает, что альтернатива является вектором в Rm [7].

Пусть множество альтернатив является m -мерным евклидовым пространством Rm. Предпочтения на Rm задаются полными, рефлексивными, транзитивными бинарными отношениями.

Антисимметричная часть отношения предпочтения G обозначается и ~ симметричная часть – G. Отношение предпочтения называется звездным (аналог однопиковой функции полезности над m -мерным евклидовым пространством Rm ), если существует точка r Rm, называемая идеальной точкой отношения предпочтения, такая, что для всякой точки r Rm : r r и для всех 0 < < 1 выполняется r[ r + (1- )r]r.

Такая точка единственна. I(G) обозначает идеальную точку отношения предпочтения G.

Отношение предпочтения G называется сепарабельным, если для j каждого j {0, 1,..., m} и x, x, k j, xk, ~k выполняется x j j (x1,..., x, x, x,..., xm )G(x1,..., x, x, x,..., xm) j-1 j j+1 j-1 j+ j (~1,..., ~j-1, x, ~j+1,..., ~m )G(~1,..., ~j-1, x, ~j+1,..., ~m ).

x x x x x x x x j Обозначим множество всех звездных сепарабельных отношений предпочтения на Rm через Sm. Отношение предпочтения называется квадратичным, если оно может быть представлено функцией полезности вида n - (xi - pi)(x - p ), a j j ij i, j= где aij - симметричная положительно определенная матрица.

Квадратичное отношение предпочтения является звездным, с точкой пика r = (r1,..., rn). Квадратичное отношение предпочтения является сепарабельным тогда и только тогда, когда aij = 0 для всех i j. В этом случае функция полезности принимает вид n - (xi - ri )2.

a ii i= Обозначим множество всех сепарабельных квадратичных предпочтений над Rm через Qm. Очевидно, множество Qm m параметризуется парой параметров (, r) R++ Rm.

Профиль предпочтений АЭ будем обозначать < Gi >. Для любого D Sm функция выбора будет отображением C : Dn Rm.

Функция выбора C : Dn Rm называется единогласной (respects unanimity) если для любого профиля предпочтений такого, что i, I(Gi) = r выполняется C(< Gi >) = r.

Пусть функция выбора C задана на множестве профилей предпочтений Qn и является отображением C : Qn R. Если можно определить функцию c : Rn R (поскольку разным профилям предпочтений может соответствовать одна точка пика) так, что c(< ri >) = C(< Gi >), где для всех i и Gi Q, ri = I(Gi), то такую функцию назовем механизмом голосования, соответствующим C.

Механизм голосования c : Rn R называется бескомпромисным n если r R, x = c(r), если i I такой, что x < ri ( ri < x ), то ri R1 : x ri (ri x) выполняется x = S(ri, r-i ).

Результаты работы [7] по неманипулируемости механизмов голосования вида c : (Rm )n Rm базируются на свойствах механизмов c : Rn R1, поэтому рассмотрим некоторые их свойства.

Лемма 1.2.2 [7]. Пусть СГВ C : Qn R1 соответствует механизм голосования c : Rn R1. Если механизм голосования c является бескомпромиссным, то СГВ C неманипулируема.

Лемма 1.2.3 [7]. Предположим, что СГВ C : Qn R1 неманипулируемо и допускает единогласие. Тогда соответствующий C механизм голосования бескомпромиссный.

Пусть задан механизм голосования c. Точка r R1 называется фантомным голосом, если существует профиль идеальных точек < pi > такой, что c(< pi >) = p и p pi для всех i. Обозначим через P множество фантомных голосов. Если множество P конечно, то p будет так же обозначать мощность P. Будем считать, что множество элементов I = {1,..., n}, а множество фантомных голосов P = {n +1,..., n + r}.

Определим соответствие голосования e : Rn I P e(< ri >) = {k I : c(< ri >) = rk} {n + j P : c(< ri >) = rn+ j}.

Таким образом, e ставит в соответствие каждому профилю множество элементов и фантомных голосов, идеальные точки которых выбираются при этом профиле. Говорят, что график e замкнут, если для каждого k I P, множество профилей предпочтений, соответствующих этому k - {< ri > Rn : k e(< ri >)} замкнуто.

Лемма 1.2.4 [7]. Механизм голосования бескомпромиссен тогда и только тогда, когда (i) число фантомных голосов не больше 2n и (ii) график e замкнут.

Лемма 1.2.5 [7]. Механизм голосования c бескомпромиссен тогда и только тогда, когда для каждого подмножества S I существуют константы CS, удовлетворяющие - CS для всех S и C <, CI > - и для всех S, T I, S T CS CT такие, что c(< pi>) = maxS I{miniS{ri} CS}.

Для многомерного случая верны следующие теоремы.

Теорема 1.2.10 [7]. Функция выбора C : (Qm )n Rm неманипулируема и единогласна тогда и только тогда, когда существуют механизмы голосования c1,..., cm : Rn R, которые неманипулируемы и допускают единогласие и такие, что C(< Gi >) = (c1(< I1(Gi ) >),..., cm (< Im (Gi ) >)), где I (Gi) обозначает j - ю координату идеальной точки i - го j активного элемента.

Теорема 1.2.11 [7]. Функция выбора C : (Sm )n Rm неманипулируема и единогласна тогда и только тогда, когда существуют механизмы голосования c1,..., cm : Rn R, которые неманипулируемы и допускают единогласие и такие, что C(< Gi >) = (c(< I1(Gi ) >),..., cm (< Im (Gi ) >)), j для всех < Gi >(Sm)n.

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

Обозначим через Qm множество всех квадратичных предпочтений. Для каждого > 0 обозначим Q ={(A, p)Qm : aij < aii, если i j}, где (A, p) соответствует функции полезности - (x - r)T A(x - r).

Теорема 1.2.12 [7]. Пусть > 0 и предположим, что C : Q n Rm, m неманипулируема и единогласна. Тогда C диктаторская.

Таким образом, мы рассмотрели механизмы планирования для случая, когда выбираемая альтернатива является вектором Евклидова пространства и привели достаточные условия (Т.1.2.10-1.2.12) для неманипулируемости таких механизмов.

Теорема 1.2.11 дает результат о невозможности построения неманипулируемого механизма для предпочтений для более широкого класса предпочтений, чем сепарабельные предпочтения.

В отечественных работах авторы сосредоточили внимание на способах организации деятельности отдельных элементов системы. В [10,11,83-92] исследуются механизмы функционирования систем, в которых альтернатива представляет собой вектор Евклидова пространства, причем в функции полезности каждого активного элемента явно участвует только одна компонента этого вектора, обычно содержательно интерпретируемая как план, назначаемый данному элементу. Такие системы в зарубежных работах получили название экономик с частными товарами (Economies with private goods) [4,35,37,53,55,110].

Следует отметить, что механизмы экспертизы, обсуждавшиеся выше, являются частными случаями механизмов планирования.

Действительно, в механизмах экспертизы можно считать, что всем АЭ назначаются одинаковые планы.

Рассмотрим систему, состоящую из центра и n активных элементов. Интересы элементов и центра выражаются их целевыми функциями fi (xi, yi, ri ), i = 1, n и (x, y) где ri i - параметр, параметризующий класс допустимых целевых функций i - го элемента, x = (x1,..., xn ) - вектор планов, назначаемых элементам, а y = (y1,..., yn) - вектор действий, выбираемых элементами. Порядок функционирования системы следующий:

1. Этап сбора информации. Элементы сообщают центру оценки (s1,..., sn) параметров (r1,..., rn) ;

2. Этап планирования. На основе полученных оценок центр, используя процедуру планирования : S X, где S =, X = Xi - i iI iI множество допустимых планов, назначает планы xi = (s) i элементам, i = 1, n.

3. Этап выбора состояния. Получив плановые задания, элементы выбирают свои состояния yi Ai - множества допустимых состояний.

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

yi Pi(xi, ri) = Argmax fi (xi, yi, ri).

yiAi Как и ранее, при сообщении оценок на этапе 2, будет иметь место эффект манипулирования информацией. Задачей центра является выбор такой процедуры планирования, чтобы в точке равновесия значение его целевой функции было максимально. Введем эффективность механизма = (, ) K() = min min ( (s*), r), r s*E N (r) где (x, r) = (x, y(x, r)).

При заданных значениях параметра ri i и плане xi X i элемент выбирает действие yi (xi, ri) Pi(xi, ri) = Argmax fi(xi, yi, ri).

yiAi Таким образом, можно говорить о функции предпочтения (полезности) элемента (xi, ri ) = fi (xi, yi (xi, ri ), ri ).

i Зададим для каждого элемента множества X (s-i) Xi и i рассмотрим следующую процедуру планирования:

(x, s) max (1.2.1) xX (xi, si) = max (z, si ). (1.2.2) i i zXi (s-i ) Условие (1.2.2) обеспечивает назначение элементу плана, максимизирующего его функцию полезности и называется условием совершенного согласования (УСС). Как оказалось, условие совершенного согласования эквивалентно условию независимой субъективной монотонности для транзитивных бинарных отношений предпочтения.

Условие (1.2.1) в неявном виде задает процедуру планирования максимизирующую целевую функцию центра. Механизм, удовлетворяющий (1.2.1), (1.2.2) называется механизмом открытого управления (ОУ).

Теорема 1.2.13 [82]. Необходимым и достаточным условием сообщения достоверной информации как доминантной стратегии при любых r является существование множеств X (s-i), для которых выполнено i условие совершенного согласования.

Рассмотрим механизм с сильными штрафами за отклонение от плана [80, 82]. Для такого механизма выполнено ri i, i I, Ai(ri), fi (, ) = (, ri ). Пусть множество i i i i i допустимых планов представимо в виде:

Xi(s-i ) = Ai(si) Di(s-i). (1.2.3) Условие (1.2.3) является утверждением того факта, что план, назначаемый элементу при данном s-i, выполним, то есть принадлежит Ai(si). Для механизмов с сильными штрафами верна следующая Теорема 1.2.14 [82]. Для того, чтобы механизм с сильными штрафами обеспечивал сообщение достоверной информации как доминантной стратегии при любых r, необходимо и достаточно, чтобы:

1) i I существовали множества Di(s-i), удовлетворяющие (1.7.3);

2) выполнялось условие совершенного согласования (1.7.2), где множества допустимых планов имеют вид (1.7.3).

Рассмотрим механизм, в котором часть компонент плана является общей для всех элементов, то есть план имеет вид (, x). В системах с большим числом элементов влияние оценки отдельного элемента на общее управление мало. Если при сообщении своей оценки si каждый активный элемент не учитывает ее влияния на (s), то считается выполненной гипотеза слабого влияния. При выполнении гипотезы слабого влияния справедлива следующая Теорема 1.2.15 [82]. Если выполнена гипотеза слабого влияния и компоненты x(s) плана удовлетворяют условию совершенного согласования, то сообщение достоверной информации является доминантной стратегией.

В работе [107,112] получены более конструктивные условия неманипулируемости механизмов планирования.

Будем считать, что функции полезности элементов однопиковые.

Вектор точек пиков обозначим через r = (r1,..., rn) [111].

Через SP обозначим класс действительных функций q(x), определенных на R1 и удовлетворяющих следующим свойствам:

1. q(x) - полунепрерывна сверху;

2. Существуют точки r-, r+ R1 (возможно r- = r+ = r, r- = - или r+ = + ), такие, что q(x) не убывает при x r-, постоянна при x [r-, r+] и не возрастает при x r+.

3. q( p±) < +.

Функции, принадлежащие классу SP назовем квазиоднопиковыми. Для функций полезности из класса SP, множество P = [r-, r+] назовем идеальным множеством.

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

Теорема 1.2.16. [111,112] Пусть множество АЭ системы I, функции полезности АЭ однопиковые и для прямого механизма h : Rn Rn выполнены следующие условия:

A.1.2.1. Для любого r Rn ( r Rn ), для любого i I 1. Если hi(r) < ri, то ~ hi(r), hi (~, r-i) = hi(r) ;

ri ri 2. Если hi (r) > ri, то ~ hi(r), hi (~, r-i) = hi(r).

ri ri A.1.2.2. Для любого r Rn ( p Rn ), для любого i I 1. Если hi(r) < ri, то ~ < hi(r), hi (~, r-i) hi (r) ;

ri ri 2. Если hi ( p) > pi, то ~ > hi(r), hi (~, r-i) hi (r).

ri ri Тогда механизм h(r) неманипулируем.

Таким образом, для достаточно широкого класса механизмов голосования в активных системах, предпочтения активных элементов которых заданы однопиковыми функциями полезности, теорема 1.2.3 и лемма 1.2.5 позволяют утверждать, что любой неманипулируемый механизм принадлежит классу CW функций. Аналогично теорема 1.2.10.

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

Попытка расширить множество возможных предпочтений ограничения, наложенные на функции полезности приводят к тому, что все возможные неманипулируемые механизмы голосования являются диктаторскими, то есть зависящими от предпочтений единственного АЭ.

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

В следующем параграфе мы рассмотрим основные результаты исследований механизмов функционирования АС с применением формализма бинарных отношений.

§ 3. Реализуемость соответствий группового выбора Теория реализуемости представляет собой раздел теории управления социально-экономическими системами с сообщением информации. Наиболее полный обзор существующих результатов теории реализуемости можно найти в [3,50,51,58,67,68,101]. В теории реализуемости исследуется реализуемость соответствий группового выбора, свойства реализующих механизмов [47,49,50,67], модели поведения АЭ в детерминированном случае, и в случае наличия вероятностной неопределенности [27,39,42,43,44,57,61,74] и их влияние на реализуемость СГВ.

В настоящем параграфе мы приедем известные условия реализуемости соответствий группового выбора и различные виды реализующих механизмов [22,26,50,52,64], а также некоторые детерминированные модели поведения и опишем их влияние на реализуемость [42,43,48,59,65].

Говорят, что механизм G (полностью) реализует СГВ f [22], если для всех R :

1) EG(R) не пусто;

2) g(EG (R)) (=) f (R).

Другими словами, при всех R равновесие существует и в любом из возможных при данном R равновесии s(R) EG(R) принимаемое решение g(s(R)) лежит в f (R).

Говорят, что прямой механизм H = (, h) реализует СГВ f : A достоверно, если R выполнены:

D 1) R EH (R) ;

2) h(R) f (R).

Достоверная реализуемость означает, что сообщение достоверной информации в механизме H является доминантной стратегией, и при сообщении достоверной информации выбирается допустимая для центра альтернатива.

Рассмотрим некоторые свойства соответствий группового выбора, необходимые для исследования реализуемости СГВ.

Рассмотрим бинарное отношение RA над множеством A и некоторую альтернативу a A. Нижним срезом L(a, RA ) отношения RA по a называется множество X A, определяемое следующим образом:

X = {b A : aRAb}. Верхним срезом H (a, RA) отношения RA по a называется множество X A, определяемое следующим образом:

X = {b A : bRAa}.

Говорят, что СГВ f : A удовлетворяет условию монотонности Маскина (ММ) если {R, R }, a f (R) таких, что a f (R) и i I, L(a, Ri ) L(a, Ri ) выполняется a f (R ).

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

е. i I, L(a, Ri ) L(a, Ri ), то альтернатива a будет выбираться и при новом профиле предпочтений a f (R ).

Для однозначных соответствий группового выбора (ОСГВ), то есть таких, что R f (R) = 1, определяется следующее свойство ОСГВ f : A удовлетворяет независимой слабой монотонности (НСМ) тогда и только тогда, когда i I, R f (R) H ( f (Ri, R-i ), Ri ).

R Содержательно, НСМ означает, что при сообщении достоверной информации, для всех элементов назначается наилучшая альтернатива, что является аналогом УСС, рассмотренного в разделе 1.2.

Говорят, что СГВ удовлетворяет свойству отсутствия права вето (ОПВ), если a A, i I, R : i j, b A, aRjb выполнено a f (R). То есть, если есть альтернатива a наилучшая с точки зрения всех активных элементов кроме некоторого j, то a f (R).

СГВ f : R A называется диктаторской, если i I такой, что R, a A, a f (R) тогда и только тогда, когда b A, aRib. Это означает, что среди элементов I найдется элемент j такой, что альтернатива a выбирается по СГВ тогда и только тогда, когда для j - го элемента нет никакой другой альтернативы, строго лучшей её.

СГВ f : A называется Парето - оптимальной, если R, {a, b} A если i I, aPib, то b f (R). Парето - оптимальность означает, что если какая - то альтернатива b для всех элементов строго хуже альтернативы a, то альтернатива b не может быть выбрана по этой СГВ.

Еще одним важным свойством СГВ является существенная монотонность [21,107].

Альтернатива a X A называется существенной для активного элемента i I во множестве X если существует профиль предпочтений R такой, что a f (R) и L(a, Ri ) X.

Множество всех существенных для элемента i I во множестве X A обозначим Ess (i, X ).

СГВ f : A называется существенно монотонным если R, R и a f (R) таких, что i I выполняется Ess (i, L(x, Ri)) L(x, Ri ) a f (R ).

Приведем далее результаты, дающие необходимые и достаточные условия реализуемости СГВ при использовании понятий равновесия Нэша и равновесия в доминантных стратегиях. Теоремы 1.3.1-1.3. представляют условия реализуемости при использовании определения равновесия в доминантных стратегиях, теоремы 1.3.5-1.3.9 являются условиями реализуемости при использовании определения равновесия Нэша.

Теорема 1.3.1 [22]. Для того, чтобы ОСГВ f : A было достоверно реализуемо в доминантных стратегиях, необходимо и достаточно, чтобы оно удовлетворяло НСМ.

Теорема 1.3.2 [22]. СГВ f : A достоверно реализуема в доминантных стратегиях тогда и только тогда, когда существует ОСГВ f, удовлетворяющая НСМ, такая, что для всех R, f (R) f (R).

Теорема 1.3.3 [22]. Пусть содержит только строгие порядки, СГВ f : A достоверно реализуема в доминантных стратегиях тогда и только тогда, когда f является ОСГВ и удовлетворяет НСМ.

Теорема 1.3.4 [22,26,65]. Предположим, что включает все возможные строгие предпочтения над A. Тогда не существует ОСГВ f, множество значений которой содержит не менее трех различных альтернатив, которая достоверно реализуема в доминантных стратегиях.

Вместе с теоремой 1.3.2, последний результат утверждает, что ни одно достаточно сложное СГВ не может быть реализовано в доминантных стратегиях, если на множество возможных профилей предпочтений не наложены дополнительные ограничения.

Гораздо более обширен класс СГВ, реализуемых по Нэшу.

Необходимое условие реализуемости СГВ по Нэшу устанавливает следующая Теорема 1.3.5 [22]. Если СГВ f : A реализуема по Нэшу, то она удовлетворяет монотонности Маскина.

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

Следующий механизм, реализующий СГВ, удовлетворяющую условиям ММ и ОПВ, был получен Е.Маскиным (E.Maskin). Пусть I - множество активных элементов, профили предпочтений которых принимают значения из множества. Задано СГВ f : A. Каждый активный элемент сообщает в центр профиль предпочтений всех элементов из, альтернативу из A и натуральное число. Таким образом для каждого элемента Si = A N и множество возможных сообщений S =. Назовем множеством согласованных сообщений множество S i iI Sa = {s S j I, R, a f (R) : i j, si = (a, R, 0)}.

Множество несогласованных сообщений определим как дополнение к множеству Sa :

Sd = {s S s Sa}.

Таким образом определенные множества Sa и Sd являются разбиением S.

Процедура принятия решения g : S A определяется двумя правилами.

Правило 1.3.1. Если s Sa, то по определению существуют j I, R, a f (R) такие, что i j, si = (a, R, 0). Пусть j - ый активный элемент сообщает альтернативу aj. В этом случае выбираемая альтернатива a, при a jPja;

g(s) = a, при aRaj.

j j Правило 1.3.2. Если s Sd, то g(s) = ak(s), где k(s) = max{i I zi z, j I}.

j Введенный таким образом механизм назовем механизмом Маскина. Первое правило определяет действие механизма в случае, когда все активные элементы, кроме быть может одного, сообщают одинаковые профили предпочтений R, одинаковые альтернативы a f (R) и не желают принять участие в лотерее, то есть i j, zi = 0. В этом случае считается, что все кроме j - го элемента сообщают достоверный профиль предпочтений R, соответствующий действительному профилю предпочтений всех элементов, и большинство голосует за альтернативу a. При этом из согласованных сообщений остальных АЭ делается однозначное предположение R о предпочтениях j -го элемента и j выбирается альтернатива, наихудшая для j -го АЭ. Второе правило определяет так называемую целочисленную игру. Если сообщения элементов не согласованны, то любой элемент выбором соответствующего натурального числа может добиться выбора наилучшей для себя альтернативы. Имеет место следующая Теорема 1.3.6 [22]. Если I 3 и f : A монотонная по Маскину СГВ, удовлетворяющая ОПВ, то механизм Маскина реализует эту СГВ по Нэшу.

Как видно из определения, в механизме Мавскина каждый активный элемент сообщает профиль предпочтений всех элементов, точное знание которого не всегда возможно. Множество возможных сообщений было значительно сужено в работах Сайжо (Saijo) [64] и МакКельви (McCelvey) [50]. Перейдем к описанию введенного ими механизма.

Определим механизм МакКельви следующим образом.

Обозначим множество элементов через I = {1,..., n}. Будем считать, что элементы нумеруются по mod n, то есть номер k Z соответствует элементу с номером k (mod n). Каждый элемент i I = {1,..., n} посылает в центр сообщение следующей структуры:

si = (ai, Ai, Bi, ni ), где ai A, и R такое, что либо Ai = L(a, Ri ) и Bi = L(a, Ri+1), либо Ai = L(a, Ri ) и Bi =. Таким образом A A Si = A 2 2 N и S =.

S i iI Для любых s S и j I, обстановка s- j называется f - согласованной, если a A и R такие, что 1) a f (R) ;

2) ai = a, i I \{ j};

3) i j, Ai = L(a, Ri) и Bi = L(a, Ri+1).

Процедура принятия решения механизма МакКельви определяется следующими правилами.

Правило 1.3.3. Пусть число элементов I 3, тогда для любого s S если j I такой, что a a и обстановка s- j является f - j j- согласованной, то, a Bj-1;

a j j g(s) = a, aj Bj.

-1 - j Правило 1.3.4. В противном случае, g(s) = ak(s), где k(s) = ni (mod n).

iI Как оказалось, для любой СГВ с количеством активных элементов больше трех верна следующая Лемма 1.3.1 [50]. Пусть I 3, тогда для любой СГВ f : A и определенного для неё механизма МакКельви верно N R, f (R) g(EG (R)).

Таким образом, любая СГВ, удовлетворяющая условиям леммы 1.3.1, может оказаться нереализуемой лишь в том случае, когда имеются дополнительные равновесия s такие, что g(s) f (R).

Теорема 1.3.7 [50]. Пусть I 3 и пусть f : A монотонное по Маскину СГВ, удовлетворяющее ОПВ, тогда механизм МакКельви реализует по Нэшу СГВ f.

Дальнейшее уменьшение множества возможных сообщений произведено только для СГВ специального вида. Допустим, что существует альтернатива aH A, называемая "истребление" (holocaust), такая, что, aH f () и R a A \{aH}, a L(aH, Ri ) и aH L(a, Ri) при всех i I.

Множество возможных сообщений механизма с истреблением определяется следующим образом:

Si = {(ai, Ai, ni ) ai A, ni N, Џ R : Ai = L(ai, Ri+1)}, S =.

S i iI Таким образом, предполагается, что элементы сообщают альтернативу a A, целое число и профиль предпочтения своего соседа.

Пусть I 3, для всех s S определим процедуру принятия решения g : S A механизма с истреблением тремя правилами:

Правило 1.3.5. Если a A такое, что i I, ai = a, то (i) Если R, такое, что a f (R) и i I, Ai = L(ai, Ri+1), то g(s) = a.

(ii) в противном случае, g(s) = aH.

Правило 1.3.6. Если a A и j I такой, что i I \{ j}, ai = a aj, то aj, a j Aj-1 \{aH } или a = aH ;

g(s) = a.

Правило 1.3.7. Если не выполнены условия предыдущих правил, g(s) = ak(s).

Теорема 1.3.8 [50]. Пусть I 3, A содержит истребление и f : A произвольное монотонное по Маскину СГВ, удовлетворяющее ОПВ, тогда механизм с истреблением реализует f (R) по Нэшу.

Другой важной задачей является поиск необходимых и достаточных условий реализуемости по Нэшу. В случае, когда множество возможных отношений всех элементов универсально, то есть содержит все возможные отношения на A, удается найти необходимое и достаточное условие реализуемости СГВ [21,101].

Теорема 1.3.9 [21]. Если множество возможных профилей предпочтения универсально, и I 3, тогда для того, чтобы СГВ f : A было реализуемо по Нэшу, необходимо и достаточно, чтобы f (R) была существенно монотонна.

Приведенные теоремы позволяют сделать вывод о реализуемости СГВ при использовании определений равновесия Нэша и равновесия в доминантных стратегиях.

Как оказалось, класс реализуемых механизмами Маскина и МакКельви СГВ является достаточно бедным, поэтому в ряде работ были сделаны попытки расширить этот класс. Сделать это оказалось возможным несколькими путями: первый путь состоит в усилении определения равновесия Нэша таким образом, чтобы исключить лишние равновесия и оставить только те, на которых механизм дает результаты из СГВ (недоминируемое равновесие Нэша (Undominated Nash Equilibrium) [42,59] и недоминируемые стратегии (undominated strategies) [48], хотя последние являются альтернативным определением равновесия, а не усилением);

второй путь заключается в том, чтобы расширить класс используемых для реализации механизмов (совершенная пошаговая реализуемость (Subgame Perfect Implementation))[1,55]. Обсуждение результатов работ [1,48,55] выходит за рамки настоящей работы.

Приведем результаты работ [42,59] по реализуемости ФКВ при использовании определения недоминируемого равновесие Нэша.

Рассмотрим механизм G = (S, g). Профиль сообщений s S называется недоминируемым равновесием Нэша [42,59] механизма G при профиле предпочтений R, если i I и для всех si Si g(s)Rig(si, s-i) и для всех i I и всех si Si, существует такой профиль s-i S-i, что g(si, s-i )Pig(si, s-i ), где через Pi обозначается строгая компонента отношения Ri.

Как видно, первая часть определения является определением равновесия Нэша, а вторая часть отбрасывает слабо доминируемые сообщения. Сообщение s S является слабо доминируемым, если найдется активный элемент i I и сообщение si Si такое, что при всех обстановках s-i S-i для i -го активного элемента g(si, s-i)Rig(si, s-i).

Верна следующая Теорема 1.3.10 [42,59]. Пусть не содержит профиля, в котором некоторый активный элемент безразличен между всеми альтернативами из A, то есть R, i I, {a, b} A : aPib. Если I 3 и СГВ f : A удовлетворяет ОПВ, то f реализуема при использовании определения недоминируемого равновесия Нэша.

Таким образом, результаты теории реализуемости позволяют гарантировать реализуемость некоторых функций коллективного выбора, однако в механизмах, реализующих ФКВ, удовлетворяющие условиям теорем 1.3.7 - 1.3.9, либо достаточно сложно множество возможных сообщений АЭ: правила 1-4 вынуждают каждый АЭ сообщать не только свои предпочтения, но и предпочтения остальных АЭ, либо ограничения налагаются на предпочтения АЭ, что не позволяется напрямую применить результаты теории реализуемости для исследования манипулируемости механизмов планирования.

§4. Достоверная реализуемость соответствий группового выбора В параграфах 2, 3 были рассмотрены две задачи, возникающие при исследовании механизмов функционирования систем с сообщением информации: построение неманипулируемого механизма и построение реализующего заданное СГВ механизма. При этом центр может быть заинтересован в том, чтобы прямой механизм H = (, h) реализовывал заданное СГВ F : A, и чтобы при этом сообщение достоверной информации было равновесием.

Таким образом, в интересы центра может входить построение механизма функционирования АС, реализующего заданную СГВ F достоверно. При этом, хотя теоремы 1.3.1, 1.3.2 дают необходимые и достаточные условия достоверной реализуемости, условие НСМ является недостаточно конструктивным и проверка его трудоемка [113] (см. раздел 2.3).

Другим способом построения механизма, достоверно реализующего заданную СГВ, является построение эквивалентного прямого механизма. Рассмотрим следующую процедуру: допустим, что задан механизм G = (S, g). При этом G может не быть прямым. Для каждого профиля предпочтений R механизм G порождает множество равновесных сообщений EG (R). Определим функцию отбора равновесия определив некоторое равновесное сообщение s(R) EG(R) для каждого R. Определим H как механизм, в котором пространство возможных сообщений совпадает с, а сама процедура принятия решения h(R) = g(s(R)).

Однако, в определенном таким образом прямом механизме H элементы в равновесии не обязательно сообщают достоверную информацию, поэтому, во избежание путаницы, процедуру h для прямых ~ ~ механизмов будем записывать как h(R) где R. Эта запись отражает тот факт, что, хотя в прямом механизме пространство сообщений S и совпадает со множеством возможных профилей предпочтений, сообщение и истинный профиль предпочтения следует различать.

Механизм H, построенный по приведенной выше схеме называется соответствующим G прямым механизмом. Если оказывается, что в соответствующем прямом механизме сообщение достоверной информации является равновесием в доминантных D стратегиях, т. е. R, R EH (R), то соответствующий G прямой механизм H называется эквивалентным G прямым механизмом [22].

Таким образом, одним из способов построения достоверно реализующего заданное СГВ механизма является поиск реализующего это СГВ механизма G и построение эквивалентного ему прямого механизма H. Возникает необходимость определить условия на механизм G, являющиеся достаточными для существования эквивалентного прямого механизма.

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

Теорема 1.4.1 [22]. Пусть G = (S, g) - механизм, в котором для каждого профиля предпочтений существует равновесие в доминантных стратегиях s*(R). Тогда для механизма G существует эквивалентный прямой механизм H = (, h), где h = g(s(R)).

Для систем с одним активным элементом доказана следующая Теорема 1.4.2 [89]. В активной системе с одним элементом для любого механизма функционирования существует эквивалентный прямой механизм.

Эта теорема, фактически, отражает тот факт, что в системе с одним элементом определения равновесия по Нэшу и равновесия в доминантных стратегиях совпадают.

Далее мы переходим к изучению конкретных механизмов функционирования АС, для которых в теории активных систем доказана оптимальность принципа ОУ, в соответствии центр выбирает оптимальный план среди наилучших для всех АЭ планов.

Рассмотрим задачу активной экспертизы [80,89] (механизм активной экспертизы (МАЭ)). Под задачей активной экспертизы понимается задача оценки некоторой величины группой экспертов. Для простоты рассмотрим оценивание скалярной величины группой экспертов. Пусть ri, i = 1, n - истинное мнение i - го эксперта, ri [d, D] и пусть эксперты упорядочены по возрастанию их мнений r1 r2... rn.

Известна процедура принятия экспертного решения x = (s). В качестве функции полезности i - го эксперта возьмем обобщенно однопиковые функции полезности (каждый эксперт стремится минимизировать отклонение итоговой оценки от его истинного мнения). В такой постановке задача активной экспертизы аналогична механизмам функционирования в системах с общим товаром (см. раздел 1.2).

Пусть существует базовая процедура (s), которую будем считать оптимальной при условии, что все элементы сообщают достоверную информацию. Требуется построить некоторую процедуру (s), наиболее близкую к оптимальной в некоторой метрике:

max (s(r)) - (r) min, r[d, D]n где s - равновесие Нэша.

На процедуру (s) накладываются следующие требования:

искомая процедура должна быть непрерывна, монотонна по сообщениям экспертов и a [d, D], (a,..., a) = a. Равновесие в таком механизме имеет следующую структуру:

Лемма 1.4.1 [80,89]. Для каждого вектора точек пика одно из положений равновесия имеет следующую структуру d, если x > ri, si = D, если x < ri.

si [d, D], если xi = ri.

Если все ri различны, то только одна из оценок может находиться не на границе отрезка [d, D]. Обозначим:

k АЭ – сообщаяют d, s(k) = (n - k) АЭ – сообщаяют D. k = 0, n.

Введем Wk = (s(k)), W0 = D, Wn = d.

Теорема 1.4.3 [80,89]. Решение в равновесии имеет вид:

x = max min (rk, Wk -1). (1.4.1) k Теорема 1.4.4 [80,89]. Для любой процедуры активной экспертизы существует эквивалентная процедура ОУ вида (1.4.1).

Следует отметить, что для механизма вида 1.4. неманипулируемость была доказана в работах [80,89] для случая, когда точки пика АЭ упорядочены. В связи с этим, в разделе 2.3 мы приводим доказательство результата неманипулируемости этого механизма для общего случая.

Рассмотрим механизм распределения ресурса (МРР) [80,89].

Пусть центр обладает R единицами ресурса, потребителями которого являются элементы. Ценность ресурса для i - го элемента определяется функцией полезности (xi, ri ), ri [d, D]. Задачей центра является i распределение ресурса с целью максимизации суммарной полезности:

(xi, ri ) max, x iI i iI xi = R.

Функции полезности элементов являются однопиковыми, с точками пиков ri. Элементы сообщают оценки si [di, Di ], i = 1, n и получают ресурс в количестве xi = (s). Будем считать, что (s) - i i непрерывная и монотонная функция si.

Пусть механизм удовлетворяет следующим условиям:

А.1.4.1. Весь ресурс распределяется полностью.

А.1.4.2. Каждый активный элемент, изменяя только свою заявку, имеет возможность получить любое количество ресурса, меньшее того, которое он уже получил.

А.1.4.3. Если количество ресурса у центра увеличивается, то элементы получают не меньшее количество ресурса.

Распределение ресурса в равновесии определяет следующий результат.

Лемма 1.4.2 [80,89]. Пусть (s) - монотонна по si, тогда равновесие i имеет следующую структуру:

xi > ri si = d;

si = d xi ri x < ri si = D;

si = D xi ri i d < si < Di xi = ri.

i Алгоритм 1.4.1 [80,89]. Сначала предполагается, что все элементы заинтересованы в максимизации xi. В этом случае xi = g(D), где D = (D,..., D). Если xi ri, то i - ый элемент не может увеличить количество получаемого ресурса. Если на j -ом шаге ( j = 1, 2,... ) не пусто следующее множество: Qj = {i I : xi > ri}, то все элементы i Qj начнут уменьшать свои заявки и получат в силу гипотезы 2 требуемое количество ресурса. Это приведет к переходу от Qj к новому множеству «приоритетных потребителей» Qj+1, соответствующему ( j +1) шагу и т.

д. Такая процедура сойдется к тому, что элементы будут либо получать xi = ri, (i Q ), либо сообщать s = D ( j Q ) и получать xj < rj.

j Теорема 1.4.5 [80,89]. Для любого механизма распределения ресурса существует эквивалентный механизм ОУ.

Рассмотрим обобщения задачи существования эквивалентного прямого механизма. Обозначим через gi(s) произвольную процедуру планирования, si Si, s S =. Планы, назначаемые элементам S i iI ~ x = (x1,..., xn ) X = g(S). Будем считать, что функции полезности элементов однопиковые. Вектор точек пиков обозначим через r = (r1,..., rn) [110].

Обозначим Gi ={ j I : s S, g(s) не убывает по si}, Hi = { j I : s S, g(s) не возрастает по si}.

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

А.1.4.4. (А.1.4.4’) i I, Si = [di, Di ] R1, - < di < Di < +.

А1.4.5. s S, i I gi(s) - строго возрастающая функция по si.

А.1.4.5’. s S, i I gi(s) - неубывающая функция по si.

А.1.4.6. (А.1.4.6’) i I, Gi Hi = I.

~ А.1.4.7. (А.1.4.7’) i I, r Rn и r R1 если gi(s(~, r-i )) gi(s(r)), то ri j Gi g (s(~, r-i)) g (s(r)), ri j j j Hi g (s(~i, p-i)) g (s( p)).

p j j А.1.4.8. i I, SP.

i ~ А.1.4.9. p X.

~ А.1.4.10’. P X =.

А.1.4.11’. Для любого i I, для любых s-i S-i, s1, si2 Si, s1 > si i i если g(s1, s-i ) < ri(ri+ ), g(si2, s-i) < pi( pi-), то АЭ сообщит s1 ;

i i если g(s1, s-i ) > ri (ri+), g(si2, s-i) > ri(ri-), то АЭ сообщит s1 ;

i i Структуру равновесия определяет следующая Лемма 1.4.3 [111]. Если выполнено А.1.4.4,1.4.5,1.4.8 (А1.4.4’, A.1.4.5',A.1.4.8',A.1.4.10'), то для любого r Rn ( r Rn ), для любого i I 1(1 ). Если gi(s(r)) < ri(ri-), то si(r) = Di ;

2( 2 ). Если gi(s( p)) > pi ( pi+ ), то si (r) = di ;

3( 3 ). Если s(r) (di, Di), то gi(s(r)) = ri([ri-, ri+ ]).

Следующие леммы определяет свойство соответствующего g(s) прямого механизма h(~), аналогичное бескомпромиссности в [5,40] и § r главы I.

Лемма 1.4.5 [111]. Если выполнено А.1.4.4,1.4.5,1.4.8 (А1.4.4’, A.1.4.5',A.1.4.8',A.1.4.10'), то для любого r Rn ( r Rn ), для любого i I 1. Если hi (r) < ri, то ~ hi (r), hi(~, r-i) = hi(r) ;

ri ri 2. Если hi ( p) > pi, то ~ hi (r), hi(~, r-i) = hi(r).

ri ri Лемма 1.4.6 [111]. Если выполнено А.1.4.4,1.4.5,1.4.8 (А1.4.4’, A.1.4.5',A.1.4.8',A.1.4.10'), то для любого p Rn ( r Rn ), для любого i I 1. Если hi ( p) < pi, то ~ < hi (r), hi(~, r-i) hi(r) ;

ri ri 2. Если hi (r) > ri, то ~ > hi(r), hi(~, r-i) hi(r).

ri ri Следующая теорема дает достаточные условия существования эквивалентного прямого механизма.

Теорема 1.4.6 [111]. Если выполнено А.1.4.4-1.4.10 (А.1.4.4’-A.1.4.11’), то для любого механизма существует эквивалентный прямой механизм.

Эта теорема обобщает теоремы 1.4.5 - 1.4.6, но не удобна для практических целей, поскольку проверка её условий требует вычисления равновесных сообщений и равновесного распределения планов при каждом профиле предпочтений активных элементов.

В настоящем параграфе мы рассмотрели один из способов построения механизма достоверно реализующего заданное СГВ. При этом, для механизмов частного вида (механизмы активной экспертизы и распределения ресурса) были получены конструктивные условия (накладываемые на непрямые механизмы) достаточные для существования эквивалентных прямых механизмов (Т.1.4.2, 1.4.3). Для механизмов планирования общего вида построить удобные и конструктивные, с точки зрения проверки, условия существования эквивалентного прямого механизма не удалось и на текущий момент подтверждение существования эквивалентного прямого механизма (согласно условиям А.1.4.4-A.1.4.9) требует вычисления равновесия Нэша для каждого возможного профиля предпочтения (Т.1.4.5).

В следующем параграфе мы рассмотрим результаты применения топологических методов для исследования задач коллективного выбора.

§5. Топологические методы в теории коллективного выбора Исторически, наиболее ранние методы исследования проблем теории коллективного выбора формулировались в предположении дискретности (конечности) множества возможных альтернатив A, и предпочтения АЭ при этом представлялись бинарными отношениями.

Такая формулировка накладывает определенные ограничения на методы исследования проблем коллективного выбора, связанные с дискретными методами, описанными в §§ 3-4 настоящей работы. В частности формализм бинарных отношений предпочтения неудобен при исследовании механизмов голосования, описанных в § 2 настоящей главы, а механизмы, используемые в дискретных теориях, являются достаточно громоздкими.

Однако, наиболее часто, в задачах теории коллективного выбора множество возможных альтернатив непрерывно, что дает возможность использовать "топологические методы" исследования задач теории коллективного выбора. Применение топологических методов позволяет исследовать не только стандартные проблемы теории коллективного выбора [13,15-19], но и неманипулируемость правил коллективного выбора [14,60], а так же исследовать механизмы коллективного выбора с бесконечным числом АЭ.

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

Применение топологических методов анализа проблем коллективного выбора показывает, что существование ФКА, удовлетворяющей НПАА и ПО эквивалентно существованию непрерывного симметричного отображения из произведения единичных сфер на единичную сферу и связано с теоремой Брауэра о неподвижной точке. Теорема о невозможности в топологической формулировке выглядит следующим образом.

Обозначим - пространство непрерывно дифференцируемых функций полезности над евклидовым пространством возможных альтернатив. По аналогии с механизмами голосования § 2 главы 1, ФКА : n назовем анонимной, если для любого профиля P n и для любой перестановки множества I выполняется (P1, P2,..., Pn ) = (P 1, P 2,..., P n). Единогласной назовем ФКА : n, такую, что для любого профиля предпочтений P n, такого, что для любых АЭ i, j I Pi = Pj выполняется (P) = Pk для любого k I.

Теорема 1.5.1 [5,63,17]. Не существует ФКА : n, удовлетворяющей условиям непрерывности (в смысле равномерной метрики), анонимности и единогласности.

Таким образом, при достаточно общих предположениях не удается построить отличного от диктаторского механизма коллективного выбора и/или функции коллективного агрегирования, и для того, чтобы существовал недиктаторский механизм коллективного выбора, необходимо изменить условия, налагаемые на механизм коллективного выбора. Как показывалось в § 3 при усложнении множества возможных сообщений АЭ удается найти механизмы, в которых активные элементы сообщают достоверную информацию, однако в таких механизмах потребуется изменение определения неманипулируемости в связи с тем, что сообщением АЭ уже не будет информация только о своих предпочтениях.

Другая возможность построения неманипулируемых механизмов коллективного выбора заключается в изменении множества допустимых предпочтений. В частности, в § 2 рассмотрены неманипулируемые механизмы голосования.

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

Пусть n - количество активных элементов, множество возможных альтернатив A = Rm+, предпочтения АЭ заданы m однопиковыми функциями полезности вида (x) = - - rj)2, где a (x i j j j= aj > 0, j =1, m, i I, r A - точка пика функции полезности.

Множество возможных сообщений каждого АЭ S, определяется либо как S = Rm+, либо S = Rm.

Функцию f : Rn R назовем локально постоянной либо диктаторской (ЛПД) [14], если она непрерывна, и для почти всех r Rm существует окрестность U (r) такая, что для всех r U(r) либо f (r) = const, либо существует АЭ d, такой, что f (r) = rd.

Функцию f : (Rm )n Rm назовем сепарабельной если 1 n 1 n f (r11,..., rm,..., r1n,..., rm) =(f1(r11,..., r1n),..., fm(rm,..., rm )).

Функция f : (Rm )n Rm называется покоординатно ЛПД если она сепарабельна и для каждого k =1, m, функция fm удовлетворяет ЛПД.

Основной результат работы [14] представляется следующей Теорема 1.5.2 [14]. Механизм g : Sn A неманипулируем тогда и только тогда, когда он удовлетворяет ЛПД.

Таким образом теорема 1.5.2 утверждает, что любой неманипулируемый механизм состоит из множеств, в которых определенные АЭ являются диктаторами, то есть механизм g назначает наилучший для них результат. При этом, из теоремы 1.5.1 следует, что любой неманипулируемый механизм вида g : Sn A непрерывен. Таким образом, результаты работы [14] являются топологической интерпретацией результатов работ [14, 53], обсуждавшихся в § 2.

Топологический подход также позволяет рассмотреть вопрос об устойчивости неманипулируемых механизмов вида g : Sn A. Будем m считать, что множество возможных альтернатив A является кубом I в Rm, множество возможных сообщений каждого АЭ так же является m кубом I в Rm. Таким образом, все неманипулируемые механизмы вида mn m mn m g : I I принадлежат множеству C0(I, I ) непрерывных mn m mn m отображений из I в I. На множестве C0(I, I ) введем расстояние между элементами f и g следующим образом d( f, g) = sup f (x) - g(x). Справедлива следующая mn xI Теорема 1.5.3 [14]. Множество манипулируемых механизмов на ограниченном множестве возможных альтернатив является всюду mn m плотным множеством в пространстве C0(I, I ).

Таким образом, малые изменения неманипулируемого механизма могут оказаться манипулируемыми.

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

Теорема 1.5.4 [20]. Существует непрерывная ФКА для бесконечного числа АЭ, которая удовлетворяет свойству Парето, единогласности и не является диктаторской, и определяется как предел диктаторских ФКА.

При этом, ФКА, определенная в работе [20], может не быть анонимной, однако удовлетворяет условиям непрерывности, единогласности и условию Парето, кроме этого, ФКА, определяемая теоремой 1.5.4, удовлетворяет усиленной версии независимости от посторонних альтернатив [20]. Возможны и другие подходы к решению проблемы бесконечного числа АЭ, в частности поиск ФКА, удовлетворяющих НПАА и не являющихся диктаторскими [25,45].

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

§6. Постановка задачи исследования манипулируемости механизмов планирования В предыдущих параграфах приведены известные условия неманипулируемости для механизмов планирования и условия реализуемости СГВ. Также мы рассмотрели механизмы планирования частного вида, для которых было доказано существование эквивалентного прямого механизма. Для механизмов планирования общего вида были проанализированы достаточные условия существования эквивалентных прямых механизмов, однако эти условия недостаточно конструктивны, так как требуют поиска равновесия для каждого возможного профиля предпочтений.

Таким образом, возникает необходимость построения конструктивных достаточных условий неманипулируемости механизмов планирования. Далее определим классы активных систем и механизмов планирования (прямых и непрямых), исследуемых в настоящей работе.

Обозначим I={1,…, n}—множество всех АЭ, xi R1 — план i-го АЭ. Планы АЭ назначаются по сообщениям АЭ si Si, i I : xi = gi (s).

Функция полезности i -го активного элемента - (x) называется i сепарабельной, если она зависит только от плана, назначаемого i -му элементу, то есть (x) = (xi ). Функция полезности (xi ) является i i i обобщенно однопиковой, если существует точка r R1 такая, что (r) > (xi) при любых xi ri и (xi) не убывает по x до точки r и не i i i возрастает после неё. Точка r называется точкой пика или идеальной точкой. Класс всех обобщенно однопиковых функций обозначается GSP и, очевидно, содержит класс однопиковых функций SP.

Всюду ниже, если не оговорено особо, предполагается, что полезность АЭ не трансферабельна, а АЭ имеют обобщенно однопиковые, сепарабельные функции полезности.

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

Набор функций полезности всех элементов (,..., ) обозначим 1 n через. Вектор точек пиков всех элементов (r1,..., rn ) Rn обозначим через r. Вектор точек пиков для профиля предпочтений GSPn будем записывать как r = peak ( ).

В прямых механизмах элементы сообщают оценку положения своих точек пиков из R1, таким образом, в прямых механизмах множество возможных сообщений каждого элемента есть R1. Пусть ~ элементы посылают в центр сообщения ri R1. План i-го элемента ~) ~ определяется процедурой планирования hi(r, где r = (~,..., ~ Rn.

r1 rn) Обозначим вектор планов через x = (x1,..., xn ) Rn. Механизм планирования будет определяться множеством возможных сообщений Rn и процедурой планирования h : Rn Rn.

В непрямых механизмах планирования множества возможных сообщений каждого АЭ i I представляют собой отрезки действительной оси. Без ограничения общности будем считать, что Si = [0,1]. Таким образом, процедура планирования в непрямом механизме представляет собой отображение g : S Rn.

Как отмечалось ранее, будем рассматривать такие механизмы, в которых каждый АЭ сообщает только свою точку пика ri R1, и, следовательно, множество возможных сообщений всех АЭ – все Rn, при этом процедура планирования будет отображением h : Rn Rn. Под достоверной информацией будем понимать реальное положение точек пиков элементов. Прямой механизм планирования называется неманипулируемым, если для любых идеальных точек АЭ сообщение достоверной информации является равновесием в доминантных стратегиях, то есть GSPn, r = peak( ) и iI, ri R1, r-i Rn- выполнено (hi(ri, r-i)) (hi(ri, r-i)).

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

Пусть механизм g : S не является прямым и для каждого Rn профиля предпочтений SPn мы знаем одно из положений равновесия ) которое зависит только от положения точек пиков s( элементов r Rn. Такие равновесия будем записывать следующим образом: s(r).

Для непрямого механизма g : S построим соответствующий Rn ему прямой механизм следующим образом. Элементы сообщают ~ информацию ri R1, i I о своих точках пика, центр по ним находит вектор равновесных заявок (r) для механизма g : S и назначает s Rn планы x = g(. Получим новый механизм h(r) = g(. Если s(r)) s(r)) соответствующий прямой механизм h(r) неманипулируем, то для непрямого механизма g : S существует эквивалентный прямой Rn механизм h(r) = g(.

s(r)) Таким образом, второй задачей настоящего исследования является поиск условий на исходный непрямой механизм G = (S, g), являющихся достаточными для того, чтобы положение равновесия зависело только от точек пика АЭ, и соответствующий прямой механизм был неманипулируем.

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

Как было показано в обзоре, приведенном в §§ 1-5 настоящей главы, существует множество подходов к исследованию неманипулируемости. В то же время, достаточно перспективным, с точки зрения получения условий неманипулируемости механизмов планирования, выглядит подход, предложенный в [7,94-96], который развивается в настоящей работе.

Таким образом, изучение условий неманипулируемости механизмов планирования можно свести к следующим задачам:

- получение условий неманипулируемости прямых механизмов;

- получение условий существования эквивалентных прямых механизмов;

- исследование влияния множества допустимых сообщений на существование эквивалентного прямого механизма.

Решение этих задач приводится соответственно в главах II и III.

Глава II. Условия неманипулируемости прямых механизмов планирования, сформулированные в терминах множеств диктаторства В предыдущей главе мы рассмотрели постановку задачи поиска неманипулируемого механизма планирования и основные проблемы, возникающие при исследовании неманипулируемости. При анализе манипулируемости механизмов планирования будем исследовать их множества диктаторства, определяемые ниже.

В первом параграфе приведены основные определения, необходимые для исследования множеств диктаторства прямых механизмов планирования и достаточные условия неманипулируемости прямых механизмов планирования в терминах множеств диктаторства. Во втором параграфе приведены необходимые и достаточные условия коалиционной неманипулируемости прямых механизмов планирования. В § 3 исследуется неманипулируемость механизмов с векторными планами.

В четвертом параграфе приводятся свойства механизмов активной экспертизы и распределения ресурса, описанных в главе I, с точки зрения метода исследования множеств диктаторства.

§1. Множества диктаторства и неманипулируемость прямых механизмов Рассмотрим прямой механизм h : Rn Rn. Пусть для некоторого ~ ~) сообщения r Rn выбирается вектор планов x = h(r. Так как полезность каждого АЭ определяется однопиковой функцией полезности, то каждый АЭ может находиться в одном и только одном из трех ~ возможных состояний: (а) либо hi(~) > ri и тогда АЭ будет получать план, r ~ строго больший желаемого, (б) либо hi (~) = ri и АЭ будет назначаться r ~ оптимальный для него план, (в) либо hi(~) < ri и план будет r недостаточным. Для каждого активного элемента i I введем индекс состояния, принимающий значения из набора {a, c, m}=, где a соответствует состоянию (а), с—состоянию (б), а m—(в), и обозначим его через (символы индекса являются первыми буквами фр. слов i manque—нехватка, contentement—удовлетворенность, abondance— n избыток). Вектор индексов состояния всех АЭ обозначим через.

n n n Введем соответствия M: 2I, C: 2I, A: 2I, значениями n которых для каждого вектора состояний будет подмножество АЭ из I, таких, что индексы состояний этих элементов равны, соответственно, m, n c и a: M( )={jI: =m}, C( )={jI: =c}, A( )={jI: =a},.

j j j Очевидно, для каждого подмножества C( ), A( ), M ( ) в совокупности являются разбиением множества всех элементов I.

Определение 2.1.1. Разбиением B пространства Rn назовем совокупность множеств D Rn, таких, что ~ если i ~ если i D ={~ Rn hi (~) < ri M ( ), hi(~) = ri C( ) r r r ~, если i и hi (~) > ri A( )}, n.

r ~ Сокращенно неравенства hi(~) < ri, при iM( ) будем записывать r ~ ~ ~ hM ( )(~) > rM ( ), а неравенства hi(~) > ri, при iA( ) как hA( )(~) > rA( ).

r r r Как видно из определения, для каждого множества D разбиения B задано множество элементов C( ), называемых диктаторами, которые получают оптимальные планы, остальные элементы при этом получают некоторые неоптимальные для себя планы. Разбиение B назовем разбиением на множества диктаторства, а сами множества D - множествами диктаторства.

Далее будем предполагать, что в каждом из множеств D разбиения B планы, назначаемые всем активным элементам зависят только от сообщений диктаторов C( ) в этом множестве и не зависит от ~ сообщений остальных элементов, если вектор сообщений r находится в этом множестве. То есть, существует функция x (~ ( )), определенная на rC ~ ~ для всех rC ( ) ProjC( ) D, такая, что для всех r D выполняется h(~) = x (~ )) и выполнено предположение r rC( n А.2.1.1. Для всех существует функция x : ProjC ( )D Rn, такая, что ~ D выполнено h(~) = x (~ )).

r r rC( Содержательно предположение А.2.1.1 означает, что планы, назначаемые для всех векторов сообщений из одного и того же множества диктаторства, не зависят от сообщений АЭ, не являющихся диктаторами.

Предположение А.2.1.1 будем считать выполненным, если не оговорено особо, в ходе всего последующего изложения.

Введенные определения иллюстрируются следующим примером.

Пример 2.1.1. Для механизма g1(s) = s1 + 2 s2, g2 (s) = s1 + s2, si [0, 1], i = 1, 2, (r1, r2 ) R2 рассмотрим соответствующий прямой механизм. Он задается следующими соотношениями:

x(c, c)(r1, r2) = (r1, r2), при (r1, r2 ) D(c, c) = {(r1, r2) : 2 r2 -1 r1 2 r2, r1 -1 r2 r1};

x(c, m) (r1) = (r1, r1), при (r1, r2 ) D(c, m) = { (r1, r2) : r1 [0, 1], r2 < r1 2 };

x(c, a) (r1) = (r1, r1 -1), при (r1, r2 ) D(c, a) = { r1 [2, 3], r2 > (r1 +1) 2 };

x(m, c) (r2 ) = (1- 2r2, r2 ), при (r1, r2 ) D(m, c) = { r2 [1, 2], r1 > 1+ r2 };

x(a, c) (r1) = (2 r2, r2 ), при (r1, r2 ) D(a, c) = { r2 [0, 1], r1 < r2 };

x(m, m) = (3, 2), при (r1, r2 ) D(m, m) = { r1 > 3, r2 > 2 };

x(m, a) = (1, 1), при (r1, r2) D(m, a) = {r1 > 2, r2 < 1} {r1 (1, 2], r2 < 2 r1} ;

x(a, m) = (2, 1), при (r1, r2 ) D(a, m) = {r1 < 1, r2 > 1} {r1 [1, 2), r2 > 2 r1 -1} ;

x(a, a) = (0, 0), при (r1, r2 ) D(a, a) = { r1 < 0, r2 < 0 }.

1 Легко проверить, что D = R2 и, D 1 D 2 =, то есть B есть разбиение R2. Множества разбиения изображены на рис. 2.1.

Определение 2.1.2. Определим совокупность множеств D 0 ={rRn: rM( )> x M ( ) (rC( ) ), rC( ) = Proj C( ) D, rA( )< x A( ) (rC ( ) ) }, n.

Из определения 2.1.2 очевидно, что для любого n выполнено включение D D 0. Так же очевидно, что если для любого ~ вектора сообщений r D 0 выполняется h(~) = x (~C( ) ), то для r r любого вектора истинных точек пика r D 0 сообщение достоверной информации является наилучшим сообщением из D 0 для всех АЭ.

Пример 2.1.2. Для примера 2.1.1 множества совокупности B0 имеют вид:

D(0, a) = {r R2: r1 < 0, r2 < 0} ;

a D(0 = {r R2: r1 [0, 1], x2 < x1};

c, a) D(0 ) = {r R2: r1 > 1, r2 < 1} ;

m, a D(0 = {r R2: r2 [1, 2], r1 > 1- 2r2};

m, c) D(0 = {r R2: r1 > 3, r2 > 2} ;

m, m) D(0 = {r R2: r1 [2, 3], r2 > 1+ r2};

c, m) D(0, m) = {r R2: r1 < 2, r2 > 1} ;

a D(0, c) = {r R2: r2 [0, 1], r1 < 2r2} ;

a D(0 = D(c, c) по определению.

c, c) ножества D(0, a), D(0, D(0m, a), D(0, D(0 изображены на рис.

a c, a) m, c) m, m) 2.2.

r D(c, m) D(m, m) D(a, m) D(m, c) D(c, c) D(a, c) D( m, a) r 1 2 D(c, a) D(c, a) Рис. 2.1. Множества B - разбиения для примера 2.1. Свойства множеств из B0 иллюстрируются следующей леммой.

Лемма 2.1.1. Рассмотрим произвольный r D 0, тогда:

a) iM( ) { (~,r-i) D 0} {~ > xi (rC( )) }, (2.1.1) ri ri r D( m, m) D(c, m) D(a, m) D(0m, c) D(a, c) D( m, a) D(0 r 1 2 c, a) D( c, a) Рис. 2.2. Множества совокупности B0 для примера 2.1. 2) б) iR( ) {(~,r-i) D 0} {~ < xi (rC( ))}. (2.1.2) ri ri Под записью B=B0 будем подразумевать, что n, D = D 0.

Теорема 2.1.1. Пусть I - множество активных элементов, функции полезности которых обобщенно однопиковые. Пусть механизм h : Rn Rn удолетворяет А.2.1.1 и B=B0, тогда он неманипулируем.

Очевидно, условия теоремы 2.1.1 не выполнены в примере 2.1.1.

Механизм примера 2.1.1 оказывается манипулируемым. Возьмем, например, такой профиль предпочтений, что функции полезности (x1) = - x1, (x2 ) = - x2 -1 2 имеют точки пика равные 1 соответственно (0, 1 2). Сообщая достоверную информацию, элементы получают планы (1, 1 2) и полезности (1, 0) соответственно. Если же первый активный элемент сообщит недостоверную информацию: 1 2, а второй сохранит своё сообщение 1 2, то будут назначены планы (1 2, 1 2) и полезности элементов в этом случае будут (0, 0).

2) Символ “ ” после формального утверждения означает, что его доказательство приведено в приложении Таким образом, в настоящем разделе сформулированы достаточные условия неманипулируемости прямых механизмов планирования, накладывающие ограничения на структуру множеств диктаторства (Т.2.1.1). Кроме этого, исследование манипулируемости механизмов планирования в АС с двумя АЭ (примеры 2.1.1, 2.1.2) дает наглядную геометрическую интерпретацию условий неманипулируемости в терминах множеств диктаторства.

§2. Коалиционная неманипулируемость прямых механизмов В §1 настоящей главы были построены достаточные условия неманипулируемости прямых механизмов планирования. В настоящем параграфе мы введем понятие коалиционной неманипулируемости и получим необходимые и достаточные условия коалиционной неманипулируемости для механизмов, удовлетворяющих предположению А.2.1.1.

Введем несколько отношений между векторами в Rn, которые будут необходимы нам в дальнейшем. Будем писать, что x < > y, x, y Rn если xC ( ) = yC ( ), xA( ) < yA( ), xM ( ) > yM ( ). Используя это обозначение, определение множеств D, D 0 можно записать следующим образом:

D = {~ Rn ~ < > h(~)}, n.

r r r ~ D 0 = {~ Rn ~ ) ProjC( ) D, r < > x (~ ( ))}, n r rC( rC Кроме отношения < > определим отношение < >. Будем записывать x < > y, если xC ( ) = yC ( ), xA( ) yA( ), xM ( ) yM ( ).

Для каждого подмножества активных элементов J I и для каждого вектора состояний n определим множества D(, J ) и вектора состояний c(, J ) следующим образом:

~ ~ D0(, J ) = {~ Rn ~ ( ) ProjC ( ) D, rJ = xJ (~ ) ), r- J < > x-J (~ ))}, r rC rC( rC( c(, J ) n : cJ (, J ) = и i I \ J ci(, J ) ='c'.

J В дальнейшем будем исследовать прямые механизмы, удовлетворяющие следующему условию A.2.2.1. n, J I D0(, J ) Dc(, J ).

Условие А.2.2.1 содержательно означает, что при переходе из множества диктаторства D, n с меньшим числом диктаторов в множество Dc(, J ) с большим количеством диктаторов, АЭ не являвшиеся диктаторами в D получат планы, не лучшие прежних.

Будем говорить, что прямой механизм h : Rn Rn коалиционно J манипулируем, если r Rn, J I, ~J R такие, что j J r (hj (~J, r-J )) (hj (rJ, r-J )) и i J (hi(~J, r-J )) > (hi(rJ, r-J )).

r r j j i i Содержательно, это означает, что при некотором профиле предпочтений найдется коалиция элементов, каждый элемент которой не проигрывает от сообщения недостоверной информации и найдется элемент, который строго выигрывает.

Следует отметить, что такое определение коалиционной неманипулируемости расходится с общепринятым [22,108] Определение 2.2.1. Коалиционно неманипулируемым назовем J механизм h : Rn Rn такой, что r Rn, J I, ~J R r {i J (hi(~J, r-J )) (hi(rJ, r-J ))} или {j J :

r i i (hj(~J, r-J )) < (hj (rJ, r- J ))}.

r j j Коалиционная неманипулируемость означает, что для любого профиля предпочтений и для любой коалиции ни какая коалиция АЭ не может получить выигрыш от создания коалиции либо полезность одиного из АЭ рассматриваемой коалиции строго убывает при образовании коалиции.

Верны следующие утверждения Лемма 2.2.1. Пусть механизм h : Rn Rn удовлетворяет предположениям А.2.1.1, А.2.2.1 и для него D = D0, тогда этот механизм коалиционно неманипулируем.

Лемма 2.2.2. Пусть механизм h : Rn Rn удовлетворяет А.2.1. и коалиционно неманипулируем, тогда D = D0.

Лемма 2.2.3. Пусть механизм h : Rn Rn удовлетворяет А.2.1. и коалиционно неманипулируем, тогда выполнено А.2.2.1.

Следствием Л.2.2.1-Л.2.2.3 является следующая теорема.

Теорема 2.2.1. Для того, чтобы прямой механизм h : Rn Rn удовлетворяющий А.2.1.1, был коалиционно неманипулируем необходимо и достаточно, чтобы выполнялись условия А.2.2.1 и D = D0.

Теорема 2.2.1 дает необходимые и достаточные условия для коалиционной неманипулируемости прямых механизмов в смысле определения 2.2.1.

В следующем параграфе мы рассмотрим обобщения результатов § 1 настоящей главы на механизмы планирования с векторными планами, что является обобщением результатов работ [7,14] о неманипулируемости механизмов голосования.

§3. Неманипулируемость прямых механизмов планирования с векторными планами В §§ 1-2 настоящей главы мы получили достаточные условия неманипулируемости и необходимые и достаточные условия коалиционной неманипулируемости в терминах множеств диктаторства.

Эти результаты включают результаты работ [7,14,53] для механизмов планирования со скалярными планами как частные случаи. В настоящем параграфе мы обобщим результаты этих работ на механизмы планирования с векторными планами.

Рассмотрим активную систему с сообщением информации.

Обозначим множество активных элементов через I. Пусть активным элементам назначаются векторные планы xi RJi, где Ji - множество компонент планов для i -го активного элемента. Обозначим через J множество всех компонент планов всех активных элементов J = Ji.

iI Будем считать, что функции полезности (xi ) активных i элементов являются однопиковыми, т.е. такими, что для каждого активного элемента i I существует единственная точка ri RJi такая, что для любой точки xi RJi такой, что xi ri выполняется i i i (xi) < ( xi + (1- )ri) < (ri), (0,1). Также будем считать функции полезности активных элементов сепарабельными, т.е. такими, что для каждого активного элемента i I, для любой компоненты его i i Ji \{i} ~ плана j Ji и для любых компонент плана xij, xji R1 и x- j, x- j R i i i i i i i i ~ ji ji ~ таких, что (xij, x- j ) (x, x- j ) выполняется (xij, x- j ) (x, x- j ).

В такой активной системе введем прямой механизм планирования h : RJ RJ. По аналогии с индексом состояния АЭ (§ 1 Главы II), определим индекс состояния для каждой компоненты плана каждого j активного элемента j J и каждого вектора точек пика r RJ следующим образом = a если xj > hj(r), = m если xj < hj(r) и j j = c если xj = hj (r). Обозначим через J вектор состояний всех j компонент планов всех активных элементов. Индекс состояния i -го i активного элемента i I обозначим через =.

Ji Механизм планирования e : RJi RJi, i I назовем элементарным для i -го АЭ, если для всех компонент плана j Ji и для всех состояний c существуют числа x j j R{ j} такие, что для j i любого ri RJi такого, что rj < > x j j выполняется ej (r) = x j j и для j i i любого ri RJi такого, что xa < a > rj и rj < > x j j. Элементарный j j механизм планирования для АЭ с двумерным планом из R2 приведен на a a m m рис. 2.3.1, в нем x1 = x2 = 0 и x1 = x2 = 1. Очевидно для любого элементарного механизма выполнено B = B0.

r D(m, m) D(c, m) D(c, m) D(a, c) D(c, c) D(m, c) r D(m, a) D(a, a) D(c, a) Рис. 2.3. Лемма 2.3.1. Пусть функция полезности активного элемента i I однопиковая и сепарабельная, тогда любой элементарный механизм e : RJi RJi неманипулируем.

Далее будем считать выполненным следующее условие.

А.2.3.1. Для любого вектора состояний множество ProjC( ) D является односвязным и существует функция x : ProjC ( ) D RJ такая, что для любого активного элемента i I величина xJi \C ( Ji ) = xJi \C( Ji ) (rC ( )\C( Ji ) ). Для любого r D выполняется ~ h(r) = x (rC ( )) и для любого J, i I, J Ji и ~ Dc(, J ) r ~ ~ найдется r D такой, что xc(, J )(~ (c(, J ))) = x (rC ( )).

rC Теорема 2.3.1. Пусть функции полезности активных элементов однопиковые и сепарабельные, прямой механизм h : RJ RJ ограничен и удовлетворяет условию А.2.3.1, тогда механизм h(r), r RJ является неманипулируемым.

Данная теорема является обобщением результатов работ для механизмов коллективного выбора с векторными альтернативами [7,14,53] и позволяет исследовать неманипулируемость механизмов планирования с векторными планами в терминах множеств диктаторства.

В следующем параграфе мы рассмотрим механизм активной экспертизы (МАЭ) и механизм распределения ресурса (МРР), и исследуем их свойства с точки зрения теории реализуемости и множеств диктаторства.

Так же будут рассмотрено соотношение результатов работ [110,111] и результатов § 1 настоящей главы.

§4. Неманипулируемость и реализуемость механизмов активной экспертизы и распределения ресурса В настоящем параграфе мы рассмотрим МАЭ, МРР а также их обобщения рассматривавшиеся в параграфе 4 главы 1, и установим связь между результатами работ [80,89,111,112] и утверждениями параграфа 2.1. Также приведем результаты работы [113], демонстрирующие возможности применения условий реализуемости (параграф 3 главы 1) в общем виде для исследования реализуемости и неманипулируемости.

Докажем, что прямые механизмы распределения ресурса, определяемые алгоритмом 1.4.1, удовлетворяют условиям А.2.1.1 и D = D0. Также проверим выполнение свойств ММ, НСМ, ПО и ОПВ (см.

раздел 1.3) для таких механизмов.

Если выполнены условия А.1.4.1-А.1.4.3, то алгоритм, аналогичный алгоритму 1.4.1, примет следующий вид.

На нулевом шаге полагаем si0 = D для всех i = 1, n и получаем распределение ресурса xi0 = (D,..., D). Множество Q на нулевом шаге i полагаем пустым Q0 =.

j На шаге j множество Q определяем следующим образом j j- Q = {i I : (x )i ri}.

j Для АЭ из множества Q по А.1.4.2 определяем Q j такие, что j Q (, sIj\-1 j ) = rQ j.

j j Q Q Q В конце j - го шага получим j j j s = (, sIj\-1 j ) и x = (s ).

j Q Q Если на некотором шаге k окажется, что Qk = Qk -1, то алгоритм останавливается и полагаем s = sk, x* = xk, Qk = Q.

Результаты этого алгоритма обладают следующими свойствами, приводимыми здесь без доказательства (см. [113]).

Свойство 2.3.1. Если i Q, то ri xi (r) выполняется xi(r) = xi (ri, r-i ) ;

Свойства 2.3.2. Если i Q, то ri < xi (r) выполняется xi(r) > xi (ri, r-i ) ;

Свойство 2.3.3. Если при некотором r [0, D], ri > 0, то xi (r) > 0.

Лемма 2.3.1. Для механизма распределения ресурса свойство ММ выполнено.

Лемма 2.3.2. Для механизма распределения ресурса свойство НСМ выполнено.

Лемма 2.3.3. Если d = 0 и D > R, то для механизма jI распределения ресурса свойство ОПВ не выполнено. В противном случае ОПВ выполнено.

Лемма 2.3.4. Для механизма распределения ресурса свойство ПО выполнено.

Приведем без доказательств следующие утверждения.

Теорема 2.3.1. Для механизма распределения ресурса, определяемого алгоритмом 1.4.1, не выполнены условия теорем 1.2.6. 1.2.8 и выполнены условия теоремы 1.2.5.

Теорема 2.3.2. Для механизма распределения ресурса, определяемого алгоритмом 1.4.1, выполнены условия теоремы 1.3.1, и такой механизм распределения ресурса достоверно реализуем.

Теорема 2.3.3. Для механизма распределения ресурса, определяемого алгоритмом 1.4.1, выполнены предположение А.2.1.1 и условия теоремы 2.1.1, и такой механизм неманипулируем.

Следует отметить, что теоремы 2.3.2 и 2.3.3 представляют собой один и тот же результат о неманипулируемости механизма распределения ресурса, определяемого алгоритмом 1.4.1. Так же из теоремы 2.3.1 видно, что хотя необходимое условие реализуемости (теорема 1.2.5) выполнено, достаточные условия реализуемости СГВ, определяемого рассматриваемым механизмом распределения ресурса, не выполнены.

Для механизмов активной экспертизы, соответствующие прямые механизмы в литературе [111,112] определяются при истинных мнениях экспертов ri, упорядоченных по возрастанию, то есть на множествах вида {r [d, D]n : r1 < r2 <... < rn}. Удобно их описать в терминах перестановок множества I. Перестановкой множества I называется взаимнооднозначное соответствие t : I I.

Пусть задано множество активных элементов I. Рассмотрим перестановки t множества I 1 2 3... n t = t t2 t3... tn, которые задают некоторые упорядочения активных элементов.

Формально будем писать t : I, где I - исходное множество активных элементов, - упорядоченное множество активных элементов. При этом элементы множества I будем обозначать латинскими буквами, а элементы множества будем обозначать греческими буквами.

Множество всех перестановок t : I обозначим через T. На случай совпадения истинных мнений некоторых экспертов введем разбиения E множества I на множества El, l =1, E. Через обозначим множество E всех разбиений E множества I, а через T множество всех перестановок t T, переводящих разбиение E множества I в разбиение множества такое, что для всех l =1, E, l = t(El ) = {,..., + El }, l l то есть множества l представляют из себя последовательное перечисление элементов множества. Для каждого разбиения El n определим последовательность {il}l =1 активных элементов из El, такую, что l {1,..., E }, il = min t-1( ). Определим для каждого разбиения l E E и t T следующие множества:

tE = {r [d, D]n : l {1,..., E }, j El, rj = ril и ri1 < ri2 <... < rin }.

Рассмотрим некоторое разбиение E из и произвольную E перестановку t T. Определим вектор s( ), следующим образом s = d, = 1,, s( ) = s = D, = (n - ), n,.

t E Обозначим (s1,..., sn ) = (st(1),..., st(n) ) и для заданных E и t T определим последовательности {W t} n =1 и {W t, E} n =1 следующим образом:

t W t = (s( )) и W t, E = min W t.

l E При заданных разбиении E и перестановке t T, для каждого r tE, соответствующий (s) прямой механизм h(r) определим следующим образом h(r) = max min (rt -1( ), W t, E ). (2.3.1) - Очевидно, что для каждого r [d, D]n всегда найдутся единственное разбиение E и единственная, с точностью до E перестановок внутри множеств El разбиения E, перестановка t T E такие, что r t. Последовательность {W t, E} n =0 не меняется при перестановках элементов внутри множеств разбиения E, поэтому механизм h(r) определен для каждого r [d, D]n однозначно. Нам будет удобно обозначить через (r) множество элементов из, на которых достигается max min (rt -1( ), W t, E ) при данном r [d, D]n - (r) = Argmax min (rt-1( ), W t, E ).

- Очевидно, (r), поэтому обозначим через (r) такой номер l, что l = (r).

Свойства введенного механизма описываются следующей леммой.

Лемма 2.3.5. Для любого r [d, D]n, верны следующие утверждения:

1) если ri > h(r), то ~ h(r), h(~i, r-i ) = h(r) и ~ < h(r), ri r ri h(~i, r-i ) < h(r) ;

r 2) если ri < h(r), то ~ h(r), h(~i, r-i ) = h(r) и ~ > h(r), ri r ri h(~, r-i) > h(r).

ri Рассмотрим теперь свойства СГВ, определяемой соответствующим прямым механизмом для механизма активной экспертизы.

Лемма 2.3.6. Для механизма активной экспертизы свойство ММ выполнено.

Лемма 2.3.7. Для механизма активной экспертизы свойство НСМ выполнено.

Лемма 2.3.8. Для механизма активной экспертизы свойство ОПВ выполнено.

Лемма 2.3.9. Для механизма активной экспертизы свойство ПО выполнено.

Приведем без доказательств следующие утверждения.

Теорема 2.3.4. Для механизма активной экспертизы, определяемого (2.3.1), не выполнены условия теорем 1.2.6.-1.2.8 и выполнены условия теоремы 1.2.5.

Теорема 2.3.5. Для механизма активной экспертизы, определяемого (2.3.1), выполнены условия теоремы 1.3.1, и такой механизм распределения ресурса достоверно реализуем.

Теорема 2.3.6. Для механизма активной экспертизы, определяемого (2.1.1), выполнены предположение А.2.1.1 и условия теоремы 2.1.1, и такой механизм неманипулируем.

Сводка результатов лемм 2.3.1-2.3.9 приведена в таблице 2.1.

Использованы следующие обозначения: символ «+» означает, что для данного механизма свойство выполнено;

символ «-» означает, что для данного механизма свойство не выполнено.

Свойство Соответствующий Соответствующий прямой механизм для прямой механизм для МРР МАЭ ММ + + НСМ + + ОПВ - - ПО + + Таблица 2.1. Свойства соответствующих прямых механизмов распределения ресурса и механизмов активной экспертизы Следующая теорема устанавливает связь между результатами работ [89,90] и результатами параграфа 1 настоящей главы.

Теорема 2.3.7. Пусть прямой механизм H = (, h) удовлетворяет условиям условию А.2.1.1 и для него D =D0, тогда для этого механизма выполнены А.1.2.1, А.1.2.2.

Таким образом, условия параграфа 1 главы 2 на структуру множеств диктаторства являются более сильными, чем условия А.1.2.1, А.1.2.2.

Связь между результатами по неманипулируемости механизмов планирования можно отразить следующим образом:

Теорема 2.1. A.2.1.1., D=D Неманипу лируемость [112] А.1.2.1, А.1.2. Теорема 2.3. Таким образом, наиболее слабым условием неманипулируемости является НСМ, а наиболее сильным – условия параграфа 1 главы 2.

Настоящий параграф устанавливает связь между условиями неманипулируемости механизмов планирования работ [54,89,111,112], обсуждавшихся в § 2-5 главы I, и результатами § 1 главы 2. Кроме этого, показана трудоемкость проверки свойств ММ, НСМ и ОПВ (леммы 2.3.1 2.3.9) для механизмов планирования. При этом оказывается, что только НСМ гарантирует неманипулируемость (Т.2.3.2, Т.2.3.5) рассмотренных механизмов планирования. Условия остальных теорем о реализуемости оказываются невыполенными (Т.2.3.1, Т.2.3.3), что указывает на неэффективность использования аппарата теории реализуемости для исследования механизмов планирования.

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

Показана эффективность и наглядность применения метода анализа множеств диктаторства для исследования неманипулируемости прямых механизмов.

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

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

§1. Прямые и непрямые механизмы планирования Пусть механизм g : S не является прямым и для каждого Rn профиля предпочтений SPn мы знаем одно из положений равновесия ) которое зависит только от положения точек пиков s( элементов r Rn. Такие равновесия будем записывать следующим образом: s(r).

Для непрямого механизма g : S построим соответствующий Rn ~ ему прямой механизм. Элементы сообщают информацию ri R1, i I о своих точках пика, центр по ним находит вектор равновесных заявок s(r) для механизма g : S Rn и назначает планы x = g(s(r)).

Получим новый механизм h(r) = g(. Если соответствующий прямой s(r)) механизм h(r) удовлетворяет условиям теоремы 2.1.1, то он неманипулируем и, следовательно, для непрямого механизма g : S Rn существует эквивалентный прямой механизм (см. § 1 главы I) h(r) = g(.

s(r)) В настоящей главе будем рассматривать непрямые механизмы следующего вида. Пусть планы элементам назначаются по заявкам si Si = [0,1] в соответствии с процедурой планирования x = g(s), x = (s1,..., sn) S = [0,1. Будем предполагать, что ]n Rn, s процедура планирования непрерывна в S и частично монотонна, то есть gi (s) не убывает по si при любых s S.

В настоящей главе мы получим условия на механизм g : S Rn, которые достаточны для того, чтобы соответствующий прямой механизм h(r) удовлетворял теореме 2.1.1, которая гарантирует его неманипулируемость.

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

Поэтому в следующем параграфе мы докажем теорему о существовании равновесия Нэша для непрямых механизмов планирования.

§2. Существование равновесия Нэша Рассмотрим непрямой механизм g :[0, 1]n Rn. Пусть для некоторого r существует положение равновесия. При этом Rn s(r) данному r можно сопоставить вектор состояний такой, что gC( )(s(r)) = rC( ), gM ( )(s(r)) < rM ( ), gA( )(s(r)) > rA( ). В силу того, что - равновесие Нэша, элементы i M ( ) будут сообщать заявки s(r) gi(si,si), элементы i A( ), Arg gi(si, si) и s Arg max - i s min i si[0,1] si[0,1] s[0,1], i C(A).

i В силу частичной монотонности {si =1} Arg gi(si, s-i) и max si[0,1] {si = 0} Arg gi(si,s-i). Далее будет доказано, что в равновесии min si[0,1] si = 1, i M (A) ;

si = 0, i A(A) и si [0,1], i C(A).

Найдем положения равновесия для механизма примера 2.1.1.

Пример 3.2.1. Для механизма g1(s) = s1 + 2 s2, g2 (s) = s1 + s2, si [0, 1], i = 1, 2, (r1, r2) R2 найдем одно из возможных равновесий для всех профилей SPn. Очевидно для всех функций полезности с точкой пика r D(m, m) вектор сообщений s = (1, 1) будет равновесием Нэша.

Действительно, пусть r D(m, m), например r = (4, 3). g(s) = (3, 2) и, изменяя свое сообщение, первый АЭ не может получить план больший трех, поскольку при g(s1, s2 ) < 3 для всех si [0, 1]. Поскольку функция полезности строго возрастает до точки пика r1 = 4, то (g1(s)) > (g1(s1, s2)). Аналогично s2 [0, 1], 1 (g2(s)) > (g2(s1, s2)). Тогда s = (1, 1) является равновесием Нэша 2 для всех профилей предпочтений, задаваемых однопиковыми функциями полезности таких, что их точки пика r1 = 4, r2 = 3.

Аналогично, для любого профиля предпочтений SPn, такого, что вектор точек пиков профиля r D(c, m), равновесие Нэша определяется выражением s(r) = (r1 - 2, 1). Например, для профиля с точками пиков r1 = 2,5 и r2 = 2. Положение равновесия s(r) = (0,5;

1).

Действительно, при s1 = 0,5, s2 = 1, g1(s) = 2,5, g2(s) =1,5. Как видим при таком векторе сообщений первый активный элемент получает максимально возможную полезность и меняя своё сообщение s1 [0, 1], (g(s)) > (g(s1, s2)). Аналогично невыгодно менять своё сообщение 1 второму элементу, так как s2 [0, 1) g2(s) > g2(s1, s2). Значит s(r) = (0,5;

1) является равновесием Нэша при r = (2,5;

2).

Приведем выражения для векторов равновесных сообщений, если r D(m, m), s(r) = (1, 1) ;

r D(m, c), s(r) = (1, r2 -1) ;

r D(m, a), s(r) = (1, 0) ;

r D(c, a), s(r) = (r1, 1) ;

r D(a, a), s(r) = (0, 0) ;

r D(a, c), s(r) = (0, r2 ) ;

r D(a, m), s(r) = (0, 1) ;

r D(c, m), s(r) = (r1 - 2, 1).

В записи s-J индекс " -J ", где J - подмножество I, обозначает по аналогии с индексом " -i " все компоненты вектора s, которые не принадлежат J.

Для каждого вектора состояний n определим вектор s-C( ) размерности I \ C( ), с компонентами si, i I \ C( ) :

0, i A( );

si = 1, i M ( ).

Так же, для каждого вектора состояний определим множества S = {s Rn : sM ( ) > sM ( ), sA( ) < sA( ), sC( ) [0, 1]C( ) }, n.

Для случая двух элементов, разбиение {S } изображено на рис. 3.1.

Далее нам потребуется некоторые очевидные из геометрических соображений свойства множеств S, n, доказательства которых приводятся в приложении.

Утверждение 3.2.1. Совокупность множеств {S } n есть разбиение Rn.

Следующим утверждением устанавливается свойство малых окрестностей точек в Rn по отношению к разбиению {S } n : для каждой точки s Rn существует набор s S S S ( m, m ) ( c, m ) ( c, m ) S S S ( a, c ) ( c, c ) ( m, c ) s S ( m, a ) S S ( a, a ) ( c, a ) Рис. 3. множеств разбиения {S } n, определяемый множеством их векторов состояний 0(s) такой, что все достаточно малые окрестности точки s пересекаются только с множествами S, 0(s).

Утверждение 3.2.2. Для любого s Rn существует множество векторов состояний 0 и число > 0 такие, что (0, ), 0, U (s) S и 0, U (s) S.

Пример 3.2.2. Поясним это утверждение на следующем примере (см. рис. 3.2). Рассмотрим точку s R2, s = (0, 0,9) и окрестность радиуса 1,5. Эта окрестность будет пересекаться со всеми множествами разбиения {S } n. Окрестность радиуса 1 будет пересекаться только со множествами S(a, a), S(c, a), S(a, c), S(c, c), S(a, m), S(c, m). Окрестность радиуса 0,5 будет пересекать только множества S(a, c), S(c, c), S(a, m), S(c, m). А все окрестности радиуса меньше 0,1 пересекаются только с двумя множествами S(a, c), S(c, c). Поэтому множество 0 для точки s = (0, 0,9) будет состоять из элементов 0 = {(a, c), (c, c)}.

Далее докажем, что любой отрезок с началом не в S(c,..., c) пересекается с внутренностью некоторого множества S, где {c,..., c}.

s S S S ( m, m ) ( c, m ) (c, m ) s = (0, 0,9) S S S ( a, c ) ( c, c ) ( m, c ) s S ( m, a ) S S ( a, a ) (c, a ) Рис. 3. Утверждение 3.2.3. Пусть s1 s2 Rn. s1 S 1 и s2 S 2 и {c,..., c}, тогда > 0 и : t (0, ) s(t) = s1(1- t) + s2t S и {c,..., c}.

C( ) Определим множества Q = {s Rn : sC ( ) R, s-C ( ) = s-C ( )} и произвольные s1, s2 Rn такие, что они принадлежат разным 1 множествам разбиения {S }, то есть можно указать такие вектора,, 1 что s1 S 1 и s2 S 2.

Рассмотрим отрезок [s1, s2 ] = {s(t) = s1t + s2(1- t), t [0, 1]}. При ~ = {c,..., c}, [s1, s2 ] Q = Rn. Найдем множество всех векторов из ~ n таких, что [s1, s2] Q,. Обозначим (s1, s2) = Argmax I \ C( ).

~ Поясним введенные определения на следующем примере.

Пример 3.2.3. Рассмотрим разбиение {S } n и отрезок [s1, s2 ], где s1 = (-0,3, 1), s1 = (0,5, 1). Множества Q будут следующими (см. рис.

3.3) Q(c, c) = R2 ;

Q(m, m) = (1, 1) ;

s S S( c, m ) S ( m, m) ( c, m ) S S S( m, c ) ( a, c ) ( c, c) s S( m, a ) S( a, a ) S( c, a ) Рис. 3. Q(a, m) = (0, 1) ;

Q(m, a) = (1, 0) ;

Q(a, a) = (0, 0) ;

Q(c, a) = {r R2 : s1 (-, + ), s2 = 0} ;

Q(a, c) = {r R2 : s1 (-, + ), s2 = 1} ;

Q(c, m) = {r R2 : s2 = 0, s2 (-, + )};

Q(m, c) = {r R2 : s1 = 1, s2 = (-, + )}.

Тогда [s1, s2 ] будет принадлежать Q(c, c) и Q(c, m).

~ (s1, s2 ) = {(c, c), (c, m)}. При этом (s1, s2 ) = Argmax I \ C( ) = {(c, m)}.

Утверждение 3.2.4. s1, s2 R2 множество (s1, s2 ) состоит из одного элемента.

Единственный элемент обозначим ~.

Поскольку для каждого s Rn существует единственный n такой, что s S, то однозначным будет следующее доопределение отображения g : S Rn на все Rn. Рассмотрим произвольный s Rn, существует единственный n такой, что s S. В точке s определим функцию G(s) таким образом, что GC( )(s) = gC( )(s-C( ), sC ( )) и G-C( ) (s) = g-C ( )(s-C( ), sC( ) ) + (s-C ( ) - s-C( ) ). Очевидно, если s S = [0, 1]n то G(s) = g(s).

Pages:     || 2 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.