стр. 1
(всего 5)

СОДЕРЖАНИЕ

>>

РОССИЙСКАЯ АКАДЕМИЯ НАУК
ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА




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

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




ПРЕПРИНТ




Москва 2001
УДК.65.012.

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




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




Рецензент:


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


Утверждено к печати Редакционным советом Института
Содержание

Содержание …………………………………………………………….. 3
Введение ………………………………………………………………... 4
Глава I. Механизмы функционирования активных систем с
сообщением информации
§1. Описание модели активной системы с сообщением информации 9
§2. Неманипулируемость механизмов планирования ..….…………... 15
§3. Реализуемость соответствий группового выбора .……………….. 32
§4. Достоверная реализуемость соответствий группового выбора … 40
§5. Топологические методы в теории коллективного выбора .……… 46
§6. Постановка задачи исследования манипулируемости
механизмов планирования ...…………………………………………... 50
Глава II. Условия неманипулируемости прямых механизмов
планирования, сформулированные в терминах множеств
диктаторства
§1. Множества диктаторства и неманипулируемость прямых 53
механизмов ……………………………………………………………...
§2. Коалиционная неманипулируемость прямых механизмов ……... 59
§3. Неманипулируемость и реализуемость механизмов активной
экспертизы и распределения ресурса ………………………………… 62
§4. Неманипулируемость прямых механизмов планирования с
векторными планами …………………………………...……………... 65
Глава III. Существование эквивалентных прямых механизмов
§1. Прямые и непрямые механизмы планирования …………………. 71
§2. Существование равновесия Нэша ………………………………... 73
§3. Существование эквивалентного прямого механизма …………… 81
§4. Существование эквивалентного прямого механизма для
дифференцируемых процедур планирования и линейных процедур
планирования …………………………………………………………... 87
§ 5. Влияние множества возможных сообщений на существование
эквивалентного прямого механизма ………………………………….. 90
Заключение ……………………………………………………………... 93
Литература ……………………………………………………………… 96
Приложение …………………………………………………………….. 104




3
Введение

В социально-экономических системах (активных системах),
функционирующих в условиях изменяющейся внутренней и внешней
среды наряду с социально-экономическими факторами, действие которых
учитывается управляющим органом (Центром), существуют факторы,
предсказать возникновение и воздействие которых достаточно сложно для
управляющего органа в силу ограниченности возможностей цента по
сбору и переработке информации. Обычно, остальные участники
активной системы (активные элекменты) осведомлены о неизвестных
центру параметрах гораздо лучше центра.
Для более обоснованного принятия решений логичным
представляется организация обмена информацией между центром и
активными элементами (АЭ) и использование при принятии решений
информации, предоставляемой активными элементами. Однако при
обмене информацией АЭ могут сообщать недостоверную информацию,
которая влияет на качество (эффективность) принимаемых решений.
Необходимость получения достоверной информации для
принятия эффективных решений требует разработки методов создания
механизмов функционирования систем с сообщением информации,
поощряющих сообщение достоверной информации.
Исследование неманипулируемости механизмов
функционирования систем с сообщением информации ведется в нашей
стране и за рубежом в рамках различных научных направлений. К ним, в
частности, относятся: теория игр с непротивоположными интересами,
теория коллективного выбора (в т.ч. теория реализуемости), теория
активных систем - см. ссылки ниже. Несмотря на большой интерес к
манипулируемости механизмов функционирования систем с сообщением
информации, следует отметить, что в работах, посвященных этой теме,
конструктивные условия неманипулируемости получены лишь для
достаточно частных случаев. Необходимость построения универсальных
и удобных в использовании методов изучения неманипулируемости
механизмов планирования определяет актуальность настоящего
исследования.
Объектом настоящего исследования являются механизмы
функционирования активных систем с сообщением информации.
Предметом исследования является неманипулируемость механизмов
планирования1 в активных системах с сообщением информации.

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


остальных участников системы, называются механизмами планирования.
Если сообщение достоверной информации не является равновесием Нэша,
для механизма планирования строится соответствующий прямой
механизм следующим образом: для каждого возможного набора
предпочтений участников активной системы определяется равновесие
Нэша и в качестве информации от участников принимаются сообщения об
их предпочтениях, по которым на основании известного равновесия Нэша
определяют планы. При этом, если сообщение достоверной информации о
предпочтениях является равновесием Нэша, соответствующий прямой
механизм называется эквивалентным исходному прямым механизмом.
2)
Множество возможных предпочтений в механизмах планирования
можно разбить на подмножества, в каждом из которых определенной
группе АЭ будут назначаться оптимальные планы. Такие множества
называются множествами диктаторства.
5
механизмов планирования общего вида; достаточные условия
неманипулируемости механизмов планирования с векторными планами;
достаточные условия существования эквивалентных прямых механизмов;
конструктивные достаточные условия существования эквивалентных
прямых механизмов для случаев дифференцируемых и линейных
механизмов планирования в терминах свойств матрицы Якоби процедуры
планирования; в рамках выбранного метода исследовано влияние
множества возможных сообщений на существование эквивалентного
прямого механизма.
Результаты работы позволяют значительно расширить множество
прямых механизмов планирования, для которых доказана их
неманипулируемость. Также расширен класс непрямых механизмов, для
которых доказано существование эквивалентных прямых механизмов.
Конструктивные условия существования эквивалентных прямых
механизмов позволяют строить эффективные (с точки зрения критерия
управления) неманипулируемые механизмы планирования, для активных
систем, в которых существуют удовлетворительные (с той же точки
зрения) непрямые механизмы планирования.
Во введении обосновывается актуальность проблемы,
формулируется цель и задачи работы, приводится краткое изложение
основного содержания работы.
Изложение материала имеет следующую структуру. Первая глава
посвящена общей постановке задачи и обзору результатов исследований
активных систем с сообщением информации, полученных в
отечественных и зарубежных работах. В §1 дается общая постановка
задачи: определяются состав, информированность и порядок
функционирования системы с сообщением информации, а также
описываются предпочтения элементов системы, определяются механизм
функционирования системы с сообщением информации и модели
поведения элементов системы. В §§ 2-3 приводится обзор существующих
на настоящий момент работ, посвященных неманипулируемости
механизмов планирования и реализуемости соответствий группового
выбора. В §4 приводится обзор результатов работ, посвященных условиям
существования эквивалентных прямых механизмов для непрямых
механизмов планирования. В §5 конкретизируется постановка задачи
настоящего исследования.
Вторая и третья главы посвящены изложению оригинальных
результатов3) по неманипулируемости и условиям существования

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




литературу, доказательства оригинальных результатов вынесено в
приложение.
7
Неманипулируемость Неманипулируемость
CW – функции выбора механизмов вида
[53] (раздел 1.2
c : (R ) > R
mn m
настоящей работы)
[7] (раздел 1.2)




Неманипулируемость Неманипулируемость Неманипулируемость
прямого механизма прямого механизма прямого механизма,
активной экспертизы распределения ресурса удовлетворяющего
А.1.2.1, 1.2.2. [111,112]
[87,89] (раздел 1.4) [87,89] (раздел 1.4)
(раздел 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 : (R ) > R
mn m

Достаточные условия
существования
эквивалентного прямого
механизма (Т.3.3.1,
раздел 3.3)




Достаточные условия Достаточные условия Достаточные условия
существования существования существования
эквивалентного прямого эквивалентного прямого эквивалентного прямого
механизма для линейных дифференцируемого дифференцируемого
процедур планирования двухэлементного многоэлементного
(Т.3.4.1, раздел 3.4) механизма механизма
планирования (Т.3.4.2, планирования (Т.3.4.3,
раздел 3.4) раздел 3.4)


Рис. 0.1. Структура теоретических результатов настоящей работы



8
Глава 1. Механизмы функционирования активных систем с
сообщением информации

§1. Описание модели активной системы с сообщением информации

Будем рассматривать организационные (активные) системы (АС)
с двухуровневой структурой. Такая организация состоит из управляющего
органа — центра и конечного числа подчиненных ему активных
элементов (АЭ). Множество АЭ обозначим I = {1, ..., n} . Задачей центра
является выбор некоторого множества альтернатив X из заранее
определенного множества возможных альтернатив A . Предпочтения
элементов и центра [104,119,122] на множестве A задаются бинарными
отношениями, определяющими в общем случае нестрогий порядок над
A . Элемент i ? I характеризуется отношением предпочтения Ri .
Множество возможных предпочтений i - го элемента обозначим ? i .
Строгую компоненту отношения Ri ? ? будем обозначать Pi . Вектор
отношений предпочтения всех элементов R = ( R1 , ..., Rn ) называется
профилем предпочтений. Множество всех возможных профилей
предпочтений обозначим через ? , ? = ? ? i . Предпочтения центра
i?I
также будем задавать бинарным отношением и обозначать
R P ( R1 , ...., R n ) , отношение предпочтения центра является нестрогим
порядком над 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].

9
Примем следующий порядок функционирования системы.
Поскольку профиль предпочтений неизвестен центру, он запрашивает от
элементов информацию, и те посылают в центр сообщения si .
Множество возможных сообщений i - го участника обозначим Si .
Совокупность сообщений участников назовем вектором сообщений и
обозначим s = (s1 , ..., s n ) . Множество всех возможных векторов
сообщений обозначим через S , S = ? S i . Получив сообщения, центр по
i?I
процедуре принятия решения g : S > A выбирает единственную
альтернативу g (s ) ? A , которая считается решением. Совокупность
множества возможных сообщений S и заданной на нем процедуры
называется механизмом принятия решений, G = ( S , g ) .
Моделью поведения активного элемента служит понятие
равновесия [89,96,104,106,115]. В настоящей работе используются два
типа равновесия: равновесие Нэша и равновесие в доминантных
стратегиях.
Допустим, задан профиль предпочтений элементов R ? ? и
механизм ( S , g ) . Вектор сообщений s ? называется равновесием Нэша
при данном R ? ? , если для любого активного элемента i ? I и любого
его сообщения si ? S i выполняется
g (s ? ) Ri g ( si , s?i ) ,
?

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


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

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

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

В этом примере функции полезности ? i ( x, r ) представляют
отношения предпочтения Ri , поскольку все функции полезности
r
параметризованы параметром r можно считать предпочтения заданными,
r
когда задано значение r .
Поскольку скважина строится сообща, у администраций городов
просят сообщить положения идеальных точек. Администрация каждого
города направляет в комиссию по строительству скважины оценку
r r
положения идеальной точки si = ( s1 , si2 ) , где si ? [0, 1] ? [0, 1] . Координаты
i
скважины находятся по этим оценкам следующим образом
r r r r
x = g (s1 , ..., s n ) = 1 ? si .
n i?I
Здесь в качестве сообщений выступают оценки положений
r
идеальных точек si , а множеством возможных векторов сообщений будет
r r r
S = ? [0, 1]2 . Процедурой принятия решения будет g (s1 , ..., s n ) = 1 ? si .
n i?I
i?I
Пара ( S , g ) составляет механизм принятия решений.
r
Допустим n = 2 и идеальная точка первого города r1 = (0.8, 0.4) ,
r
а второго r2 = (0.9, 0.2) . Если города сообщат достоверную информацию,
r
то скважина будет построена в точке x = (0.85, 0.3) . Затраты городов ? i
будут равны ?1 = 0.0125 и ? 2 = 0.0125 . Если первый город сообщит
r
оценку s1 = (0.7, 0.6) , а второй город по-прежнему будет сообщать
достоверную информацию, скважина будет пробурена в точке

12
r
x = (0.8, 0.4) и затраты городов на транспортировку воды будут равны
соответственно 0 и 0.05. Если комиссия поставит условия, что скважина
будет пробурена только после того, как оценки стабилизируются, то
получим многошаговый процесс, во время которого каждый город будет
изменять свое сообщение, пытаясь максимизировать свою функцию
полезности.
Если администрации городов не обмениваются информацией,
оценки стабилизируются только тогда, когда изменять своё сообщение
каждому городу при неизменном сообщении другого города будет
r
невыгодно. В нашем примере такими сообщениями будут s1? = (0,6; 0,8) и
r?
s 2 = (1; 0) . Затраты городов при этом будут равны соответственно
(0, 0.05) . Очевидно, меняя своё сообщение, второй город не может
приблизить место бурения к своей оптимальной точке. Скважина будет
пробурена точно в точке, оптимальной для первого города.
r
Таким образом, ситуация, когда сообщение первого города s1? , а
r? r r
второго s2 будет при заданных r1 и r2 равновесием Нэша (но не будет
равновесием в доминантных стратегиях).
Как видим, если комиссия не имеет информации о
местоположении идеальных точек городов, место бурения, определенное
при помощи механизма принятия решения ( S , g ) , не будет равным
r
x = (0.85, 0.3) , т.е. не будет оптимальным с точки зрения минимизации
экологической опасности проекта. Однако, суммарные затраты городов на
транспортировку воды от места бурения, определенного при помощи
механизма ( S , g ) , будут составлять 0,05, а от точки, оптимальной для
центра – 0,025. Так как центр готов допустить отклонение значения
целевой функции от максимального значения на 50%, построенный
механизм можно считать удовлетворительным.? 1)
Рассмотренный пример в общих чертах качественно отражает
введенные определения и проблемы, возникающие при исследовании
механизмов функционирования систем с сообщением информации.
Таким образом, при изучении системы с сообщением
информации необходимо выделить элементы системы, определить их
предпочтения, информированность и порядок функционирования
системы, а также модели поведения АЭ. На основании предпочтений
центра строится СГВ, отражающее представления центра об
эффективности функционирования системы. В настоящей работе будем

1)
Знак “?” здесь и далее обозначает окончание примера
13
предполагать, что элементы системы, предпочтения, информированность
и порядок функционирования системы определены и фиксированы.
Допустимое для центра СГВ определяется из соображений
оптимальности его для центра. Выбору оптимальных для центра
альтернатив посвящено большое количество работ по исследованию
операций [77,95,102,103,121]. Поскольку в круг наших интересов будет
входить в основном анализ механизмов функционирования, мы будем
полагать, что допустимое для центра СГВ определено.
Как видно из примера 1.1.1, каждый из АЭ стремится
максимизировать собственную полезность, вследствие чего может
сообщать недостоверную информацию. В тоже время, сообщение
недостоверной информации может быть нежелательным для центра.
Таким образом, одной из задач центра может быть построение
неманипулируемого механизма функционирования АС, в котором АЭ
выгодно сообщать достоверную информацию.
С другой точки зрения, манипулируемый механизм, построенный
в примере 1.1.1, может считаться центром удовлетворительным (так как
обеспечивает не более 50% потерь). Таким образом, в задачи центра также
может входить построение удовлетворительных с его точки зрения
механизмов функционирования АС, то есть механизма
функционирования, реализующего заданное СГВ (см. раздел 1.2).
Качественно, из литературы известно, что при достаточно
богатых множествах возможных предпочтений АЭ механизмы с
сообщением информации оказываются диктаторскими (в теоремах о
невозможности [3,7,22,32] существует единственный АЭ – диктатор). В
настоящей работе мы рассматриваем более “узкий” класс предпочтений
(сепарабельные, обобщенно однопиковые), что приводит к появлению
групп диктаторов, различных для разных подмножеств множества
возможных предпочтений.
В следующих двух параграфах приведем результаты работ, посвященных
задачам построения неманипулируемых механизмов, а также
реализуемости СГВ.




14
§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) .
Прямые механизмы, в которых сообщение достоверной
информации является равновесием в доминантных стратегиях
R ? E H (R ) , называются неманипулируемыми. Формальное определение
D

неманипулируемого механизма следующее. Пусть H = (?, h) – прямой
механизм. Механизм H неманипулируем, если и только если
?R ? ?, R ? E H ( R ) ,
D
либо одно и тоже)
(что
?i ? I , ?Ri ? ? i , ?Ri? ? ? i , ?R?i ? ? ?i выполняется
h( Ri , R?i ) Ri h( Ri?, R?i ) .
Интересен тот факт, что определение неманипулируемого
механизма можно строить, используя определение равновесия по Нэшу
N
E H (R ) , что устанавливается следующей теоремой.
Теорема 1. 2.1 [22]. В прямом механизме H = (?, h) для любого R ? ? ,
R ? E H (R ) тогда и только тогда, когда ?R ? ?, R ? E H ( R) .
N D

Парадоксальный на первый взгляд результат о том, что если
сообщение достоверной информации является равновесием Нэша, то оно
15
удовлетворяет более сильным условиям равновесия в доминантных
стратегиях объясняется тем, если сообщение достоверной информации
является равновесием Нэша при любом профиле предпочтений, то
сообщение достоверной информации является наилучшим сообщением
для каждого АЭ при любых сообщениях других АЭ, поскольку множество
возможных профилей сообщений совпадает с множеством возможных
сообщений.
Одной из основных проблем в теории коллективного выбора
является существование набора так называемых результатов о
невозможности существования функций коллективного выбора,
удовлетворяющих тем или иным условиям (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 a1P a2 выполняется a1?( P)a2 .
1 i
Говорят, что ФКА ? : (?( A) )n > S ( A) удовлетворяет условию
независимости от посторонних альтернатив по Арроу (НПАА) [2,3],
если для любых двух альтернатив a1, a2 и любых двух профилей
предпочтения P, P? таких, что a1 Pi a 2 тогда и только тогда, когда a1Pi?a2
выполняется a1?( P)a2 тогда и только тогда, когда a1?( P?)a2 .




16
Говорят, что ФКА ? : (?( 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 и для любой альтернативы из
1
( )
множества значений механизма a ? g [?( A)]n , если a ? g (P ) , то g ( P ) Pi a .
Как и для функций коллективного агрегирования справедлив
следующий результат о невозможности.
Теорема 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]. В таких механизмах
множество возможных альтернатив представляет собой подмножество

17
конечномерного Евклидова пространства. При этом, предпочтения АЭ
задаются функциями полезности ? 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 1 называется однопиковой, если
существует точка r ? A , называемая точкой пика функции полезности u ,
такая, что u (x ) строго возрастает при x < r и строго убывает при x > r ,
то есть
?x ? A , таких, что x ? r и для любых ? , таких, что 0 < ? < 1
выполняется
u ( x ) < u (?x + (1 ? ? )r ) < u (r ) .
Множество всех однопиковых функций полезности обозначим
через SP . Поскольку функция полезности задает на A некоторое
отношение предпочтения, в дальнейшем под профилем предпочтений
будем понимать совокупность функций полезности всех элементов.


18
Введем следующие ограничения на класс допустимых
механизмов функционирования. Пусть задано множество активных
элементов I = {1, ..., n} , однопиковой функцией выбора (в обзоре мы будем
в основном придерживаться оригинальных названий и обозначений,
введенных авторами в соответствующих работах, в наших определениях
функция выбора соответствует механизму функционирования) назовем
отображение S : SP n ? B > A , ставящее в соответствие каждому профилю
предпочтений u = (u1, ..., u n ) ? SP n и любому подынтервалу B ? B
альтернативу S (u, B ) из B . В настоящем разделе будем предполагать,
что выполнены следующие условия:
i) анонимность: S симметрична по отношению к переменным
u1 , ..., u n ;
ii) эффективность: для всех u , B и для всех y ? B таких, что
x = S (u , B ) ui ( x) ? ui ( y ) ,
?i ? I ,
и выполняется
?i ? I , u i ( x ) = u i ( y ) ;
iii) непрерывность по отношению к подынтервалам:
S (u , B) непрерывна по отношению к B ? B .
Однопиковая функция выбора S , определенная для множества
элементов I , обладает свойством независимости от посторонних
альтернатив по Нэшу (NIIA) [53], если для всех u ? SP n и для всех
B, B? ? B n выполняется:
если B? ? B и S (u, B) ? B ? то S (u, B ?) = S (u , B ) .
Если для всех u , u? ? SP n и для всех B ? B выполняется:
i?I x, y ? B
для всех и всех таких, что
? ?
ui ( x) ? ui ( y ) ? ui ( x ) ? ui ( y ) верно
S (u, B ) = S (u ?, B ) ,
то однопиковая функция выбора обладает свойством независимости от
посторонних альтернатив по Эрроу (AIIA) [3,53].
Свяжем с каждым профилем предпочтений ? = (?1, ..., ? n ) ? SP n
профиль пиков ( r - профиль) r = (r1, ..., rn ) , где ri - пик ui . Далее мы
будем рассматривать только такие функции выбора, которые зависят
только от профиля r .




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

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

где (r1, ..., rn ) – r - профиль u и piB ( ? iB ) обозначает проекцию ri ,
соответственно ? i на B . Здесь, под проекцией некоторого элемента на
множество понимается ближайший к этому элементу элемент множества.
Множество всех CW - функций {? S }? ?R n?1 обозначим через CW .
Определенная таким образом функция выбора удовлетворяет
анонимности, эффективности и непрерывности по отношению к
подынтервалам.
Известны следующие свойства CW - функций.
Теорема 1.2.4 [53]. ?S ? CW :
i) S неманипулируема;
(n ? 1) ? k = S (u k , A) ,
определяется альтернативами
ii) S
- профиль, такой, что ri = 1, i = 1, k
1 ? k ? n ? 1 , где u k и
ri = 0, i = k + 1, n .
iii) S - бескомпромиссные, то есть ?u ? SP n , 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) существует ? = (?1 , ..., ? n ) ? An такой, что S =? S .
Класс CW - функций характеризуется следующими свойствами.

20
Теорема 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 параметрами. Эти параметры для
полезности определяется
2
? = (? ?µ ) ,
I = {1, ..., n} выбираются следующим образом: где
0 ? ? , µ ? n и ? + µ ? n ; при этом 0 ? ? ? , µ ? 1 и ? ? 0 = 1 при 1 ? ? ? n ,
? 0 µ = 0 при 1 ? µ ? n . Предположим так же, что для ? ?µ выполнено
следующее свойство монотонности:
? ?µ ? ? ? +1, µ , когда ? + µ ? n ? 1 и ? ? n ? 1 ;
? ?µ ? ? ? , µ +1 , когда ? + µ ? n ? 1 и µ ? n ? 1 .
Для заданного множества активных элементов и набора (? ?µ ) ,
удовлетворяющего введенным выше условиям, поставим каждому
профилю ? из FP n две конечные цепочки в [ 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 .



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

µ = { ?i?n p }
+
? qt .
1
t i

Наконец ? - обобщенную CW функцию ? S определим на FP n как
?
?
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]. Зафиксируем r1+ , fp 2 , ..., fpn и для всех x таких, что

0 ? x ? r1+ обозначим ? ( x)=? ? ( fp1 ( x ), fp2 , ..., fpn ) , где fp1 ( x ) = ( x, r1+ ) .
Тогда могут возникнуть лишь два следующих случая:
r1+ ? ? (0) и ? ( x) = ? (0) для всех x : 0 ? x ? r1+ ;
случай i)
? (0) ? ? (r1+ ) ? r1+ и ? ( x) = ? (0) , если 0 ? x ? ? (0) ,
случай ii)
? ( x) = x , если ? (0) ? x ? ? (r1+ ) ,
? ( x ) = ? (r1+ ) , если ? (r1+ ) ? x ? r1+ .
Если меняется y = p1 при постоянных r1? , fp2 , ..., fpn , то возможны лишь
+

следующие случаи
? ?(1) ? r1? и ? ?( y ) = ? ?(1) для всех y : r1? ? y ? 1 ;
случай i ? )
r1? ? ? ?(r1? ) ? ? ?(1) и ? ?( x ) = ? ?(0) , если r1? ? y ? ? ?(r1? ) ,
случай ii')
?
? ?( x) = x , если ? ?( p1 ) ? y ? ? ?(1) ,

22
? ?( x ) = ? ?(r1+ ) , если ? ?(1) ? y ? 1 .
Следствие 1 из Л.1.2.1 [53]. Для всех наборов ? , удовлетворяющих
?
? непрерывно по fp , не
ограничениям (1.6.1), (1.6.2), отображение
убывает и липшицево по каждой из переменных pi+ , pi? , i = 1, ..., n . Кроме
этого ? ? бескомпромиссно в следующем смысле. Возьмем произвольный
˜
fp - профиль и положим ? ? ( fp) = z . Для всех i и всех плато fpi в
˜
каждом из следующих случаев имеем ? ? ( fp)=? ? ( f pi , fp?i ) :
˜
i) { z < ri ? и z ? ri ? }
ii) { pi+ < z и ˜i+ ? z}
p
iii) { pi? < z < pi+ и ˜i? ? z ? ˜i+ }
p p
iv) {z = pi? = ˜i? для некоторого ? ?{+, ?} .
p
Характеристические свойства обобщенных CW функций на множестве
одноплатовых функций полезности определяет следующая
Теорема 1.2.7 [53]. Пусть задано множество I = {1, ..., n} . Функция выбора
на множестве одноплатовых профилей FP n удовлетворяет 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 не существует функций выбора на
QC n , удовлетворяющих NIIA и AIIA одновременно.
Итак, мы рассмотрели неманипулируемые механизмы в случае,
когда функции полезности элементов являются однопиковыми либо
одноплатовыми при множестве возможных альтернатив, состоящем из
отрезка [ 0, 1] действительной оси. Далее мы рассмотрим обобщения этих
результатов на случай, когда множество возможных альтернатив
представляет собой m - мерное пространство векторов. В частности,



23
следующая модель является обобщением предыдущей и допускает, что
альтернатива является вектором в R m [7].
Пусть множество альтернатив является m -мерным евклидовым
пространством R m . Предпочтения на R m задаются полными,
рефлексивными, транзитивными бинарными отношениями.
?
Антисимметричная часть отношения предпочтения G обозначается G и
˜
симметричная часть – G . Отношение предпочтения называется звездным
(аналог однопиковой функции полезности над m -мерным евклидовым
пространством R m ), если существует точка r ? R m , называемая
идеальной точкой отношения предпочтения, такая, что для всякой точки
? ?
r? ? R m : r? ? r и для всех 0 < ? < 1 выполняется rG[?r ? + (1 ? ? )r ]Gr? .
Такая точка единственна. I (G) обозначает идеальную точку отношения
предпочтения G .
Отношение предпочтения G называется сепарабельным, если для
каждого j ?{0, 1, ..., m} и ?x j , x ?j , ?k ? j , ?xk , ˜k выполняется
x
( x1 , ..., x j ?1 , x j , x j +1 , ..., xm )G( x1 , ..., x j ?1 , x ?j , x j +1 , ..., x m ) ?
? ( ˜ , ..., ˜ , x , ˜ , ..., ˜ )G ( ˜ , ..., ˜ , x? , ˜ , ..., ˜ ) .
x x x x x x x x
j ?1 j +1 j ?1 j +1
1 j m 1 j m
Обозначим множество всех звездных сепарабельных отношений
предпочтения на R m через S m . Отношение предпочтения называется
квадратичным, если оно может быть представлено функцией полезности
вида
n
? aij ( xi ? pi )( x j ? p j ) ,
?
i, j =1

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

24
Профиль предпочтений АЭ будем обозначать < G i > . Для любого
D ? Sm функция выбора будет отображением C : D n > R m .
Функция выбора C : D n > R m называется единогласной (respects
unanimity) если для любого профиля предпочтений такого, что
?i, I (G i ) = r выполняется C (< Gi >) = r .
Пусть функция выбора C задана на множестве профилей
предпочтений Q n и является отображением C : Q n > R . Если можно
определить функцию c : R n > R (поскольку разным профилям
предпочтений может соответствовать одна точка пика) так, что
c (< r i >) = C (< G i >) , где для всех i и G i ? Q , r i = I (G i ) , то такую
функцию назовем механизмом голосования, соответствующим C .
Механизм голосования c : R n > R называется бескомпромисным
если ?r ? R n , x = c (r ) , если ?i ? I такой, что x < ri ( ri < x ), то
?ri? ? R 1 : x ? ri? (ri? ? x) выполняется x = S (ri?, r?i ) .
Результаты работы [7] по неманипулируемости механизмов
голосования вида c : ( R m ) n > R m базируются на свойствах механизмов
c : R n > R1 , поэтому рассмотрим некоторые их свойства.
C : Q n > R1 соответствует механизм
Лемма 1.2.2 [7]. Пусть СГВ
голосования c : R n > R1 . Если механизм голосования c является
бескомпромиссным, то СГВ C неманипулируема.
Лемма 1.2.3 [7]. Предположим, что СГВ C : Q n > 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 : R n > I U P
e(< r i >) = {k ? I : c(< r i >) = r k } U {n + j ? P : c (< r i >) = r n + j } .

25
Таким образом, e ставит в соответствие каждому профилю множество
элементов и фантомных голосов, идеальные точки которых выбираются
при этом профиле. Говорят, что график e замкнут, если для каждого
k ? I U P , множество профилей предпочтений, соответствующих этому
k - {< r i >? R n : k ? e(< r i >)} замкнуто.
Лемма 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 {mini?S {r i } ? CS } .
Для многомерного случая верны следующие теоремы.
Теорема 1.2.10 [7]. Функция выбора C : (Qm )n > R m неманипулируема и
единогласна тогда и только тогда, когда существуют механизмы
голосования c1 , ..., cm : R n > R , которые неманипулируемы и допускают
единогласие и такие, что
C (< G i >) = (c1 (< I1 (G i ) >), ..., c m (< I m (G i ) >)) ,
где I j (G i ) обозначает j - ю координату идеальной точки i - го
активного элемента.
Теорема 1.2.11 [7]. Функция выбора C : ( Sm )n > R m неманипулируема и
единогласна тогда и только тогда, когда существуют механизмы
? ?
голосования c1 , ..., cm : R n > R , которые неманипулируемы и допускают
единогласие и такие, что
C (< G i >) = ( c ? ( < I1 (G i ) >), ..., cm (< I m (G i ) > )) ,
?
j

для всех < G i >? (Sm )n .
Попытка распространить этот результат на более широкий класс
квадратичных предпочтений, не обязательно сепарабельных, приводит к
следующему результату.
Обозначим через множество всех квадратичных
Qm
предпочтений. Для каждого ? > 0 обозначим

26
Q? = {( A, p) ? Qm : aij < ? aii , если i ? j} ,

где ( A, p) соответствует функции полезности ? ( x ? r )T A( x ? r ) .
Теорема 1.2.12 [7]. Пусть ? > 0 и предположим, что C : Q? > R m , m ? 2
n

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




27
Следует отметить, что механизмы экспертизы, обсуждавшиеся
выше, являются частными случаями механизмов планирования.
Действительно, в механизмах экспертизы можно считать, что всем АЭ
назначаются одинаковые планы.
Рассмотрим систему, состоящую из центра и n активных
элементов. Интересы элементов и центра выражаются их целевыми
функциями f i ( 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 = ? ? i , X = ? Xi -
i?I i?I
xi = ? i (s )
множество допустимых планов, назначает планы
элементам, i = 1, n .
3. Этап выбора состояния. Получив плановые задания, элементы
выбирают свои состояния yi ?Ai - множества допустимых состояний.
В предположении рационального поведения элементов, при
фиксированных планах выбираемые действия yi? будут максимизировать
соответствующие целевые функции, то есть:
yi? ? Pi ( xi , ri ) = Argmax fi ( xi , yi , ri ) .
yi ? Ai

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


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

28
Таким образом, можно говорить о функции предпочтения (полезности)
элемента ? i ( xi , ri ) = f i ( xi , yi? ( xi , ri ), ri ) .
Зададим для каждого элемента множества X i( s?i ) ? X i и
рассмотрим следующую процедуру планирования:
?? ( x, s ) > max
? (1.2.1)
x? X
?? ( x , s ) = max ? ( z , s ).
(1.2.2)
? i i i z? X ( s ) i i
? i ?i

Условие (1.2.2) обеспечивает назначение элементу плана,
максимизирующего его функцию полезности и называется условием
совершенного согласования (УСС). Как оказалось, условие совершенного
согласования эквивалентно условию независимой субъективной
монотонности для транзитивных бинарных отношений предпочтения.
Условие (1.2.1) в неявном виде задает процедуру планирования
максимизирующую целевую функцию центра. Механизм,
удовлетворяющий (1.2.1), (1.2.2) называется механизмом открытого
управления (ОУ).
Теорема 1.2.13 [82]. Необходимым и достаточным условием сообщения
достоверной информации как доминантной стратегии при любых r ? ?
является существование множеств X i(s? i ) , для которых выполнено
условие совершенного согласования.
Рассмотрим механизм с сильными штрафами за отклонение от
плана Для такого механизма выполнено
[80, 82].
?ri ? ?i , ?i ? I , ?? i ? Ai (ri ) , f i (? i , ? i ) = ? i (? i , ri ) . Пусть множество
допустимых планов представимо в виде:
X i (s?i ) = Ai ( si ) I 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) . В
системах с большим числом элементов влияние оценки отдельного

29
элемента на общее управление мало. Если при сообщении своей оценки
si каждый активный элемент не учитывает ее влияния на ? (s ) , то
считается выполненной гипотеза слабого влияния. При выполнении
гипотезы слабого влияния справедлива следующая
Теорема 1.2.15 [82]. Если выполнена гипотеза слабого влияния и
компоненты x(s) плана удовлетворяют условию совершенного
согласования, то сообщение достоверной информации является
доминантной стратегией.
В работе [107,112] получены более конструктивные условия
неманипулируемости механизмов планирования.
Будем считать, что функции полезности элементов однопиковые.
Вектор точек пиков обозначим через r = (r1, ..., rn ) [111].
Через SP ? обозначим класс действительных функций q(x ) ,
1
определенных на R и удовлетворяющих следующим свойствам:
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 = ?[ri? , ri+ ] назовем идеальным множеством.
i?I
Введем следующие предположения для
(утверждения
квазиоднопиковых функций будут обозначаться " ? " , а результаты для
них - приводиться в круглых скобках).
Теорема 1.2.16. [111,112] Пусть множество АЭ системы I , функции
полезности АЭ однопиковые и для прямого механизма h : R n > R n
выполнены следующие условия:
A.1.2.1. Для любого r ? R n ( r ? R n ), для любого i ? I
1. Если hi (r ) < ri , то ?˜ ? hi (r ) , hi (˜, r?i ) = hi (r ) ;
ri ri
2. Если h (r ) > r , то ?˜ ? h (r ) , h (˜, r ) = h (r ) .
r r ?i
i i i i ii i
A.1.2.2. Для любого r ? R ( p ? R ), для любого i ? I
n n

1. Если hi (r ) < ri , то ?˜ < hi (r ) , hi (˜, r?i ) ? hi (r ) ;
ri ri

30
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
функций.
Попытка расширить множество возможных предпочтений
ограничения, наложенные на функции полезности приводят к тому, что
все возможные неманипулируемые механизмы голосования являются
диктаторскими, то есть зависящими от предпочтений единственного АЭ.
В тоже время, класс неманипулируемых механизмов
планирования общего вида в активных системах с однопиковыми
функциями полезнсти достаточно широк и пока не удалось конструктивно
определить общий вид неманипулируемого механизма планирования.
В следующем параграфе мы рассмотрим основные результаты
исследований механизмов функционирования АС с применением
формализма бинарных отношений.




31
§ 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 ? ? выполнены:
1) R ? EH (R) ;
D

2) h( R) ? f ( R) .
Достоверная реализуемость означает, что сообщение достоверной
информации в механизме H является доминантной стратегией, и при
сообщении достоверной информации выбирается допустимая для центра
альтернатива.
Рассмотрим некоторые свойства соответствий группового
выбора, необходимые для исследования реализуемости СГВ.
Рассмотрим бинарное отношение R A над множеством A и
некоторую альтернативу a ? A . Нижним срезом L(a, R A ) отношения R A
по a называется множество X ? A , определяемое следующим образом:
X = {b ? A : aR A b} . Верхним срезом H (a, RA ) отношения R A по a
32
называется множество X ? A , определяемое следующим образом:
X = {b ? A : bRA a} .
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 ) ? I H ( f ( Ri?, R?i ), Ri ) .
R???
Содержательно, НСМ означает, что при сообщении достоверной
информации, для всех элементов назначается наилучшая альтернатива,
что является аналогом УСС, рассмотренного в разделе 1.2.
Говорят, что СГВ удовлетворяет свойству отсутствия права вето
?a ? A, ?i ? I , ?R ? ? : ?i ? j , ?b ? A, aR jb
(ОПВ), если выполнено
a ? f (R) . То есть, если есть альтернатива a наилучшая с точки зрения
всех активных элементов кроме некоторого j , то a ? f (R) .
СГВ f : R > A называется диктаторской, если ?i ? I такой, что
?R ? ?, ?a ? A, a ? f ( R ) тогда и только тогда, когда ?b ? A, aRi b . Это
означает, что среди элементов I найдется элемент j такой, что
альтернатива a выбирается по СГВ тогда и только тогда, когда для j - го
элемента нет никакой другой альтернативы, строго лучшей её.
СГВ f : ? > A называется Парето - оптимальной, если
?R ? ?, ?{a, b} ? A если ?i ? I , aPi b , b ? f (R ) .
то Парето -
оптимальность означает, что если какая - то альтернатива b для всех
элементов строго хуже альтернативы a , то альтернатива b не может
быть выбрана по этой СГВ.

33
Еще одним важным свойством СГВ является существенная
монотонность [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.4
представляют условия реализуемости при использовании определения
равновесия в доминантных стратегиях, теоремы 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
(всего 5)

СОДЕРЖАНИЕ

>>