<<

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

СОДЕРЖАНИЕ

>>

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

34
Теорема 1.3.5 [22]. Если СГВ f : ? > A реализуема по Нэшу, то она
удовлетворяет монотонности Маскина.
Для получения достаточных условий реализуемости используют
следующий подход. Для исследуемой СГВ определяют в явном виде
механизм и доказывают, что он реализует данную СГВ, поэтому одни и те
же условия будут фигурировать в различных теоремах, доказывающих
реализуемость различными механизмами.
Следующий механизм, реализующий СГВ, удовлетворяющую
условиям ММ и ОПВ, был получен Е.Маскиным (E.Maskin). Пусть I -
множество активных элементов, профили предпочтений которых
принимают значения из множества ? . Задано СГВ f : ? > A . Каждый
активный элемент сообщает в центр профиль предпочтений всех
элементов из ? , альтернативу из A и натуральное число. Таким образом
для каждого элемента S i = A ? ? ? N и множество возможных сообщений
S = ? S i . Назовем множеством согласованных сообщений множество
i?I

S a = {s ? S ?j ? I , ?R ? ? ?, ?a ? ? f ( R ? ) : ?i ? j , si = (a ? , R ? , 0)} .
Множество несогласованных сообщений определим как дополнение к
множеству Sa :
Sd = {s ? S s ? Sa } .
Таким образом определенные множества Sa и S d являются разбиением
S.
Процедура принятия решения g : S > A определяется двумя
правилами.
Правило 1.3.1. Если s ? Sa , то по определению существуют
j ? I , R ? ? ?, a ? ? f ( R ? ) такие, что ?i ? j , si = (a ? , R ? , 0) . Пусть j - ый
активный элемент сообщает альтернативу a j . В этом случае выбираемая
альтернатива
?a? , при a j Pj?a? ;
?
g (s ) = ? ??
?a j , при a R j a j .
?
s ? Sd , g (s ) = ak ( s ) ,
Правило Если то где
1.3.2.
k (s ) = max{i ? I zi ? z j , ?j ? I } .
Введенный таким образом механизм назовем механизмом
Маскина. Первое правило определяет действие механизма в случае, когда
все активные элементы, кроме быть может одного, сообщают одинаковые

35
профили предпочтений 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 = ? . Таким образом
Si = A ? 2 A ? 2 A ? N и S = ? Si .
i?I
Для любых 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 ) .

36
Процедура принятия решения механизма МакКельви определяется
следующими правилами.
Правило 1.3.3. Пусть число элементов I ? 3 , тогда для любого s ? S
a j ? a j ?1 и обстановка
если ?j ? I такой, что является
s? j f-
согласованной, то
? a j , a j ? B j ?1 ;
?
g (s ) = ?
?a j ?1 , a j ? B j ?1.
?
Правило 1.3.4. В противном случае, g (s ) = ak ( s ) , где k (s ) = ? ni (mod n) .
i?I
Как оказалось, для любой СГВ с количеством активных
элементов больше трех верна следующая
Лемма 1.3.1 [50]. Пусть I ? 3 , тогда для любой СГВ f : ? > A и
определенного для неё механизма МакКельви верно
?R ? ?, f ( R ) ? g ( EG ( R )) .
N

Таким образом, любая СГВ, удовлетворяющая условиям леммы
1.3.1, может оказаться нереализуемой лишь в том случае, когда имеются
дополнительные равновесия s ? такие, что g (s? ) ? f ( R) .
I ? 3 и пусть f : ? > A монотонное по
Теорема 1.3.7 [50]. Пусть
Маскину СГВ, удовлетворяющее ОПВ, тогда механизм МакКельви
реализует по Нэшу СГВ f .
Дальнейшее уменьшение множества возможных сообщений
произведено только для СГВ специального вида. Допустим, что
существует альтернатива a H ? A , называемая "истребление" (holocaust),
aH ? f (?) ?R ? ?
такая, что, и
?a ? A \ {a H }, a ? L(aH , Ri ) и a H ? L(a, Ri ) при всех i ? I .
Множество возможных сообщений механизма с истреблением
определяется следующим образом:
S i = {(ai , Ai , ni ) ai ? A, ni ? N , Џ ?R ? ? : Ai = L(ai , Ri +1 )} , S = ? S i .
i?I
Таким образом, предполагается, что элементы сообщают
альтернативу a ? A , целое число и профиль предпочтения своего соседа.
Пусть I ? 3 , для всех s ? S определим процедуру принятия решения
g : S > A механизма с истреблением тремя правилами:
Правило 1.3.5. Если ?a ? ? A такое, что ?i ? I , ai = a? , то


37
(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? ? a j ,
то
?a j , a j ? A j ?1 \ {aH } или a? = a H ;
?
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], хотя
последние являются альтернативным определением равновесия, а не
усилением); второй путь заключается в том, чтобы расширить класс
используемых для реализации механизмов (совершенная пошаговая


38
реализуемость (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 ? ) Ri g ( si , s?i )
?

и для всех i ? I и всех si ? Si , существует такой профиль s?i ? S? i , что
g (si? , s ?i ) Pi g ( si , s ?i ) ,
где через Pi обозначается строгая компонента отношения Ri .
Как видно, первая часть определения является определением
равновесия Нэша, а вторая часть отбрасывает слабо доминируемые
сообщения. Сообщение s ? ? S является слабо доминируемым, если
найдется активный элемент i ? I и сообщение si ? S i такое, что при всех
обстановках s?i ? S? i для i -го активного элемента
g (si , s?i ) Ri g ( si? , s?i ) .
Верна следующая
Теорема 1.3.10 [42,59]. Пусть ? не содержит профиля, в котором
некоторый активный элемент безразличен между всеми альтернативами
из A , то есть ?R ? ?, ?i ? I , ?{a, b} ? A : aPi b . Если I ? 3 и СГВ
f : ? > A удовлетворяет ОПВ, то f реализуема при использовании
определения недоминируемого равновесия Нэша.
Таким образом, результаты теории реализуемости позволяют
гарантировать реализуемость некоторых функций коллективного выбора,
однако в механизмах, реализующих ФКВ, удовлетворяющие условиям
теорем 1.3.7 - 1.3.9, либо достаточно сложно множество возможных
сообщений АЭ: правила 1-4 вынуждают каждый АЭ сообщать не только
свои предпочтения, но и предпочтения остальных АЭ, либо ограничения
налагаются на предпочтения АЭ, что не позволяется напрямую применить
результаты теории реализуемости для исследования манипулируемости
механизмов планирования.




39
§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 прямым механизмом. Если
оказывается, что в соответствующем прямом механизме сообщение
достоверной информации является равновесием в доминантных
стратегиях, т. е. ?R ? ?, R ? EH ( R ) , то соответствующий G прямой
D

механизм H называется эквивалентным G прямым механизмом [22].
40
Таким образом, одним из способов построения достоверно
реализующего заданное СГВ механизма является поиск реализующего это
СГВ механизма 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).


41
Пусть существует базовая процедура ? 0 ( s ) , которую будем
считать оптимальной при условии, что все элементы сообщают
достоверную информацию. Требуется построить некоторую процедуру
? (s) , наиболее близкую к оптимальной в некоторой метрике:
max ? ( s? (r )) ? ? 0 (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 ) = ? k = 0, n .
?(n ? k ) АЭ – сообщаяют D.
Введем 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.1
неманипулируемость была доказана в работах [80,89] для случая, когда
точки пика АЭ упорядочены. В связи с этим, в разделе 2.3 мы приводим
доказательство результата неманипулируемости этого механизма для
общего случая.
Рассмотрим механизм распределения ресурса (МРР) [80,89].
Пусть центр обладает R единицами ресурса, потребителями которого
являются элементы. Ценность ресурса для i - го элемента определяется
функцией полезности ? i ( xi , ri ) , ri ? [d , D] . Задачей центра является
распределение ресурса с целью максимизации суммарной полезности:

42
?? ? i ( xi , ri ) > max ,
?i?I x?0
?
?? xi = R.
?i?I
Функции полезности элементов являются однопиковыми, с
точками пиков ri . Элементы сообщают оценки si ? [d i , Di ], i = 1, n и
получают ресурс в количестве xi = ? i (s) . Будем считать, что ? i (s) -
непрерывная и монотонная функция si .
Пусть механизм удовлетворяет следующим условиям:
А.1.4.1. Весь ресурс распределяется полностью.
А.1.4.2. Каждый активный элемент, изменяя только свою заявку, имеет
возможность получить любое количество ресурса, меньшее того, которое
он уже получил.
А.1.4.3. Если количество ресурса у центра увеличивается, то элементы
получают не меньшее количество ресурса.
Распределение ресурса в равновесии определяет следующий
результат.
Лемма 1.4.2 [80,89]. Пусть ? i ( s) - монотонна по si , тогда равновесие
имеет следующую структуру:
? xi? > ri > si? = d ; si? = d > xi? ? ri
??
? ? ? ?
? xi < ri > si = D; si = D > xi ? ri
?<< ?
?d i si Di > xi = ri .
?
Алгоритм 1.4.1 [80,89]. Сначала предполагается, что все элементы
r
заинтересованы в максимизации xi . В этом случае xi? = g (D) , где
r
D = ( D, ..., D) . Если xi? ? ri , то i - ый элемент не может увеличить
количество получаемого ресурса. Если на j -ом шаге ( j = 1, 2, ... ) не пусто
следующее множество: Q j = {i ? I : xi? > ri } , то все элементы i ? Q j начнут
уменьшать свои заявки и получат в силу гипотезы 2 требуемое количество
ресурса. Это приведет к переходу от Q j к новому множеству
«приоритетных потребителей» Q j +1 , соответствующему ( j + 1) шагу и т.
д. Такая процедура сойдется к тому, что элементы будут либо получать
xi? = ri , ( i ? Q ), либо сообщать s ? = D ( j ? Q ) и получать x j < r j .
j

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


43
Рассмотрим обобщения задачи существования эквивалентного
прямого механизма. Обозначим через gi (s) произвольную процедуру
планирования, si ? S i , s ? S = ? Si . Планы, назначаемые элементам
i?I
˜
x = ( x1 , ..., xn ) ? X = g ( S ) . Будем считать, что функции полезности
элементов однопиковые. Вектор точек пиков обозначим через
r = (r1 , ..., rn ) [110].
Обозначим
Gi = { j ? I : ?s ? S , g ( s) не убывает по si } ,
H i = { j ? I : ?s ? S , g ( s ) не возрастает по si } .
Введем следующие предположения (утверждения для квазиоднопиковых
функций будут обозначаться " ? " , а результаты для них - приводиться в
круглых скобках).
А.1.4.4. (А.1.4.4’) ?i ? I , S i = [d i , Di ] ? R1 , - ? < d i < 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 U H i = I .
А.1.4.7. (А.1.4.7’) ?i ? I , r ? R n и ˜ ? R1 если
r
gi (s? (˜ , r?i )) ? gi (s? (r )) , то
ri
g j ( s? (ri , r?i )) ? g j ( s? (r )) ,
˜
?j ? Gi
g ( s? ( ˜ , p )) ? g ( s? ( p)) .
?j ? H p ?i
i j i j

А.1.4.8. ?i ? I , ? i ? SP .
˜
А.1.4.9. ?p ? X .
˜
А.1.4.10’. P I X = ? .
А.1.4.11’. Для любого i ? I , для любых s ?i ? S ?i , si1 , si2 ?S i , si1 > si2
если 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 ? R n ( r ? R n ), для любого
i ?I
1(1? ). Если gi (s? (r )) < ri (ri? ) , то si? (r ) = Di ;
2( 2? ). Если gi ( s? ( p)) > pi ( pi+ ) , то si? (r ) = di ;

44
3( 3? ). Если s ? (r ) ? (di , Di ) , то gi (s? (r )) = ri (? [ri? , ri+ ]) .
Следующие леммы определяет свойство соответствующего g (s)
˜
прямого механизма h(r ) , аналогичное бескомпромиссности в [5,40] и §2
главы 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 ? R n ( r ? R n ), для любого
i ?I
1. Если hi (r ) < ri , то ?˜ ? hi (r ) , hi (ri , r?i ) = hi (r ) ;
˜
ri
2. Если hi ( p) > pi , то ?˜ ? hi (r ) , hi (ri , r?i ) = hi (r ) .
˜
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 ? R n ( r ? R n ), для любого
i?I
1. Если hi ( p) < pi , то ?˜ < hi (r ) , hi (ri , r?i ) ? hi (r ) ;
˜
ri
2. Если h (r ) > r , то ?˜ > h (r ) , h (˜, r ) ? h (r ) .
r r ?i
i i i i i i i
Следующая теорема дает достаточные условия существования
эквивалентного прямого механизма.
Теорема 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).
В следующем параграфе мы рассмотрим результаты применения
топологических методов для исследования задач коллективного выбора.


45
§5. Топологические методы в теории коллективного выбора

Исторически, наиболее ранние методы исследования проблем
теории коллективного выбора формулировались в предположении
дискретности (конечности) множества возможных альтернатив A , и
предпочтения АЭ при этом представлялись бинарными отношениями.
Такая формулировка накладывает определенные ограничения на методы
исследования проблем коллективного выбора, связанные с дискретными
методами, описанными в §§ 3-4 настоящей работы. В частности
формализм бинарных отношений предпочтения неудобен при
исследовании механизмов голосования, описанных в § 2 настоящей главы,
а механизмы, используемые в дискретных теориях, являются достаточно
громоздкими.
Однако, наиболее часто, в задачах теории коллективного выбора
множество возможных альтернатив непрерывно, что дает возможность
использовать "топологические методы" исследования задач теории
коллективного выбора. Применение топологических методов позволяет
исследовать не только стандартные проблемы теории коллективного
выбора [13,15-19], но и неманипулируемость правил коллективного
выбора [14,60], а так же исследовать механизмы коллективного выбора с
бесконечным числом АЭ.
Как отмечалось в § 2 главы I результаты о невозможности Эрроу
тесно связаны с проблемой неманипулируемости механизмов
планирования, а так же с ограничениями множеств возможных
предпочтений АЭ, необходимых для того, чтобы в активной системы
существовала возможность построить неманипулируемый механизм
планирования.
Применение топологических методов анализа проблем
коллективного выбора показывает, что существование ФКА,
удовлетворяющей НПАА и ПО эквивалентно существованию
непрерывного симметричного отображения из произведения единичных
сфер на единичную сферу и связано с теоремой Брауэра о неподвижной
точке. Теорема о невозможности в топологической формулировке
выглядит следующим образом.
Обозначим ? - пространство непрерывно дифференцируемых
функций полезности над евклидовым пространством возможных
альтернатив. По аналогии с механизмами голосования § 2 главы 1, ФКА
? : ? n > ? назовем анонимной, если для любого профиля P ? ? n и для
?
любой перестановки множества выполняется
I
?( P , P2 , ..., Pn ) = ?( P 1 , P 2 , ..., P n ) . Единогласной назовем ФКА
? ? ?
1

46
? : ? n > ? , такую, что для любого профиля предпочтений P ? ? n ,
такого, что для любых АЭ i , j ? I Pi = Pj выполняется ?( P ) = Pk для
любого k ? I .
Теорема 1.5.1 [5,63,17]. Не существует ФКА ? : ? n > ? ,
удовлетворяющей условиям непрерывности (в смысле равномерной
метрики), анонимности и единогласности.
Таким образом, при достаточно общих предположениях не
удается построить отличного от диктаторского механизма коллективного
выбора и/или функции коллективного агрегирования, и для того, чтобы
существовал недиктаторский механизм коллективного выбора,
необходимо изменить условия, налагаемые на механизм коллективного
выбора. Как показывалось в § 3 при усложнении множества возможных
сообщений АЭ удается найти механизмы, в которых активные элементы
сообщают достоверную информацию, однако в таких механизмах
потребуется изменение определения неманипулируемости в связи с тем,
что сообщением АЭ уже не будет информация только о своих
предпочтениях.
Другая возможность построения неманипулируемых механизмов
коллективного выбора заключается в изменении множества допустимых
предпочтений. В частности, в § 2 рассмотрены неманипулируемые
механизмы голосования.
В рамках настоящей работы нас будут интересовать результаты
применения топологических методов для исследования
неманипулируемости механизмов коллективного выбора [14].
Пусть n - количество активных элементов, множество
A = R m+ ,
возможных альтернатив предпочтения АЭ заданы
m
однопиковыми функциями полезности вида ? i ( x ) = ? ? a j ( x j ? r j ) 2 , где
j =1

aj > 0 , j = 1, m , i ? I , r?A - точка пика функции полезности.
Множество возможных сообщений каждого АЭ S , определяется либо
как S = R m + , либо S = R m .
Функцию f : R n > R назовем локально постоянной либо
диктаторской (ЛПД) [14], если она непрерывна, и для почти всех r ? R m
существует окрестность U (r ) такая, что для всех r ? U (r ) либо ?
f (r ) = const , либо существует АЭ d , такой, что f (r ) = rd .
? ?



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


Функция f : ( R m )n > R m называется покоординатно ЛПД если
она сепарабельна и для каждого k = 1, m , функция f m удовлетворяет
ЛПД.
Основной результат работы [14] представляется следующей
Теорема 1.5.2 [14]. Механизм g : S n > A неманипулируем тогда и
только тогда, когда он удовлетворяет ЛПД.
Таким образом теорема 1.5.2 утверждает, что любой
неманипулируемый механизм состоит из множеств, в которых
определенные АЭ являются диктаторами, то есть механизм g назначает
наилучший для них результат. При этом, из теоремы 1.5.1 следует, что
любой неманипулируемый механизм вида g : S n > A непрерывен. Таким
образом, результаты работы являются топологической
[14]
интерпретацией результатов работ [14, 53], обсуждавшихся в § 2.
Топологический подход также позволяет рассмотреть вопрос об
устойчивости неманипулируемых механизмов вида g : S n > A . Будем
считать, что множество возможных альтернатив A является кубом I m в
R m , множество возможных сообщений каждого АЭ так же является
кубом I m в R m . Таким образом, все неманипулируемые механизмы вида
g : I mn > I m принадлежат множеству C 0 ( I mn , I m ) непрерывных
отображений из I mn в I m . На множестве C 0 ( I mn , I m ) введем расстояние
между элементами и следующим образом
f g
d ( f , g ) = sup f ( x ) ? g ( x) . Справедлива следующая
x?I mn
Теорема 1.5.3 [14]. Множество манипулируемых механизмов на
ограниченном множестве возможных альтернатив является всюду
плотным множеством в пространстве C 0 ( I mn , I m ) .
Таким образом, малые изменения неманипулируемого механизма
могут оказаться манипулируемыми.
Другой проблемой, которую удается решить применением
топологических методов, является исследование механизмов с
бесконечным количеством элементов [20].



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




49
§6. Постановка задачи исследования манипулируемости механизмов
планирования

В предыдущих параграфах приведены известные условия
неманипулируемости для механизмов планирования и условия
реализуемости СГВ. Также мы рассмотрели механизмы планирования
частного вида, для которых было доказано существование эквивалентного
прямого механизма. Для механизмов планирования общего вида были
проанализированы достаточные условия существования эквивалентных
прямых механизмов, однако эти условия недостаточно конструктивны,
так как требуют поиска равновесия для каждого возможного профиля
предпочтений.
Таким образом, возникает необходимость построения
конструктивных достаточных условий неманипулируемости механизмов
планирования. Далее определим классы активных систем и механизмов
планирования (прямых и непрямых), исследуемых в настоящей работе.
Обозначим I={1,…, n}—множество всех АЭ, xi ? R1 — план i-го
АЭ. Планы АЭ назначаются по сообщениям АЭ si ? Si , i ? I : xi = g i (s) .
Функция полезности i -го активного элемента - ? i (x) называется
сепарабельной, если она зависит только от плана, назначаемого i -му
элементу, то есть ? i ( x ) = ?i ( xi ) . Функция полезности ? i ( xi ) является
обобщенно однопиковой, если существует точка r ? R1 такая, что
? i (r ) > ? i ( xi ) при любых xi ? ri и ? i ( xi ) не убывает по x до точки r и не
возрастает после неё. Точка r называется точкой пика или идеальной
точкой. Класс всех обобщенно однопиковых функций обозначается GSP
и, очевидно, содержит класс однопиковых функций SP .
Всюду ниже, если не оговорено особо, предполагается, что
полезность АЭ не трансферабельна, а АЭ имеют обобщенно однопиковые,
сепарабельные функции полезности.
В дальнейшем, рассматривая прямые механизмы планирования,
будем предполагать, что элементы сообщают не свои предпочтения (то
есть функцию полезности), а только идеальные точки своих функций
полезности. Такие механизмы являются устойчивыми к конкретному виду
функций полезности при условии, что они остаются обобщенно
однопиковыми.
Набор функций полезности всех элементов (?1 , ..., ? n ) обозначим
через ? . Вектор точек пиков всех элементов (r1 , ..., rn ) ? R n обозначим


50
через r . Вектор точек пиков для профиля предпочтений ? ? GSP n будем
записывать как r = peak (? ) .
В прямых механизмах элементы сообщают оценку положения
своих точек пиков из R1 , таким образом, в прямых механизмах
множество возможных сообщений каждого элемента есть R1 . Пусть
элементы посылают в центр сообщения ˜ ? R1 . План i-го элемента
ri
определяется процедурой планирования h (r ) , где ˜ = (˜ , ..., ˜ ) ? R n .
˜ r r r
i 1 n

x = ( x1 , ..., x n ) ? R n . Механизм
Обозначим вектор планов через
планирования будет определяться множеством возможных сообщений
R n и процедурой планирования h : R n > R n .
В непрямых механизмах планирования множества возможных
i?I
сообщений каждого АЭ представляют собой отрезки
действительной оси. Без ограничения общности будем считать, что
Si = [0, 1] . Таким образом, процедура планирования в непрямом
механизме представляет собой отображение g : S > R n .
Как отмечалось ранее, будем рассматривать такие механизмы, в
которых каждый АЭ сообщает только свою точку пика ri ? R1 , и,
следовательно, множество возможных сообщений всех АЭ – все R n , при
этом процедура планирования будет отображением h : R n > R n . Под
достоверной информацией будем понимать реальное положение точек
пиков элементов. Прямой механизм планирования называется
неманипулируемым, если для любых идеальных точек АЭ сообщение
достоверной информации является равновесием в доминантных
стратегиях, то есть ?? ? GSP n , r = peak (? ) и ?i?I, ? ri ? R1 , ?r?i ? R n ?1
выполнено
? i (hi (ri , r-i )) ? ?i (hi (ri , r?i )) .
Таким образом, первой задачей настоящего исследования можно
считать поиск условий на прямые механизмы вида h : R n > R n ,
являющиеся достаточными для его неманипулируемости.
Пусть механизм g : S > R n не является прямым и для каждого
профиля предпочтений ? ? ? ? SP n мы знаем одно из положений
равновесия s? (? ) которое зависит только от положения точек пиков
элементов r ? R n . Такие равновесия будем записывать следующим
образом: s ? (r ) .

51
Для непрямого механизма g : S > R n построим соответствующий
ему прямой механизм следующим образом. Элементы сообщают
информацию ˜ ? R1 , i ? I о своих точках пика, центр по ним находит
ri
вектор равновесных заявок s ? (r ) для механизма g : S > R n и назначает
планы x = g ( s? (r )) . Получим новый механизм h(r ) = g ( s? (r )) . Если
соответствующий прямой механизм h(r ) неманипулируем, то для
непрямого механизма g : S > R n существует эквивалентный прямой
механизм h(r ) = g ( s? (r )) .
Таким образом, второй задачей настоящего исследования
является поиск условий на исходный непрямой механизм G = ( S , g ) ,
являющихся достаточными для того, чтобы положение равновесия
зависело только от точек пика АЭ, и соответствующий прямой механизм
был неманипулируем.
Так как условия существования эквивалентного прямого
механизма накладываются на исходный непрямой механизм, то
появляется возможность исследовать влияние изменений исходного
непрямого механизма на существование эквивалентного прямого
механизма. Поскольку менять процедуру планирования обычно не
представляется возможным, актуальной является третья задача - задача
анализа влияния множества допустимых сообщений на существование
эквивалентного прямого механизма.
Как было показано в обзоре, приведенном в §§ 1-5 настоящей
главы, существует множество подходов к исследованию
неманипулируемости. В то же время, достаточно перспективным, с точки
зрения получения условий неманипулируемости механизмов
планирования, выглядит подход, предложенный в [7,94-96], который
развивается в настоящей работе.
Таким образом, изучение условий неманипулируемости
механизмов планирования можно свести к следующим задачам:
- получение условий неманипулируемости прямых
механизмов;
- получение условий существования эквивалентных прямых
механизмов;
- исследование влияния множества допустимых сообщений на
существование эквивалентного прямого механизма.
Решение этих задач приводится соответственно в главах II и III.



52
Глава II. Условия неманипулируемости прямых механизмов
планирования, сформулированные в терминах множеств
диктаторства

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

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

Рассмотрим прямой механизм h : R n > R n . Пусть для некоторого
˜
сообщения ˜ ? R n выбирается вектор планов x = h(r ) . Так как
r
полезность каждого АЭ определяется однопиковой функцией полезности,
то каждый АЭ может находиться в одном и только одном из трех
возможных состояний: (а) либо hi (˜ ) > ˜ и тогда АЭ будет получать план,
r ri
строго больший желаемого, (б) либо hi (r ) = ˜ и АЭ будет назначаться
˜r
i
оптимальный для него план, (в) либо hi (˜ ) < ˜ и план будет
r ri
недостаточным. Для каждого активного элемента i ? I введем индекс
состояния, принимающий значения из набора {a, c, m}=?, где a
соответствует состоянию (а), с—состоянию (б), а m—(в), и обозначим его
через ?i (символы индекса являются первыми буквами фр. слов
manque—нехватка, contentement—удовлетворенность, abondance—
избыток). Вектор индексов состояния всех АЭ обозначим через ???n.
Введем соответствия M:?n>2I, C:?n>2I, A:?n>2I, значениями
которых для каждого вектора состояний ???n будет подмножество АЭ из
I, таких, что индексы состояний этих элементов равны, соответственно, m,
53
c и a: M(?)={j?I: ?j=m}, C(?)={j?I: ?j=c}, A(?)={j?I: ?j=a}, ???n.
Очевидно, для каждого ? подмножества C ( ? ), A( ? ), M ( ? ) в
совокупности являются разбиением множества всех элементов I .
Определение 2.1.1. Разбиением B пространства R n назовем совокупность
множеств D??Rn, таких, что
D = {˜ ? R n h (˜ ) < ˜ если i ? M ( ? ), h (˜ ) = ˜ если i ? C ( ? )
r rr r r
? i i i i

и hi (˜ ) > ˜ , если i ? A( ? )} , ? ??n .
r ri
Сокращенно неравенства hi (˜ ) < ˜ , при i?M(?) будем записывать
r ri
˜) > ˜ ˜˜
˜ ) > ˜ , при i?A(?) как h
A( ? ) ( r ) > rA( ? ) .
rM ( ? ) , а неравенства hi (r
hM ( ? ) (r ri
Как видно из определения, для каждого множества D? разбиения B
задано множество элементов C (? ) , называемых диктаторами, которые
получают оптимальные планы, остальные элементы при этом получают
некоторые неоптимальные для себя планы. Разбиение B назовем
разбиением на множества диктаторства, а сами множества D? -
множествами диктаторства.
Далее будем предполагать, что в каждом из множеств D?
разбиения B планы, назначаемые всем активным элементам зависят
только от сообщений диктаторов C (? ) в этом множестве и не зависит от
сообщений остальных элементов, если вектор сообщений ˜ находится в
r
этом множестве. То есть, существует функция x ? (˜ (? ) ) , определенная на
rC
˜ ˜
? Proj D , такая, что для всех r ? D выполняется
для всех r C (? ) C(?) ? ?

h(˜ ) = x ? (˜ ( ? ) ) и выполнено предположение
r rC
???n
А.2.1.1. Для всех существует функция
? ˜ ? D выполнено h(r ) = x ? (r
˜ ˜ ).
x : ProjC ( ? ) D? > R , такая, что ?r
n
? C(? )

Содержательно предположение А.2.1.1 означает, что планы,
назначаемые для всех векторов сообщений из одного и того же множества
диктаторства, не зависят от сообщений АЭ, не являющихся диктаторами.
Предположение А.2.1.1 будем считать выполненным, если не оговорено
особо, в ходе всего последующего изложения.
Введенные определения иллюстрируются следующим примером.
Пример 2.1.1. Для механизма g1 (s ) = s1 + 2 ? s2 , g 2 ( s) = s1 + s2 ,
si ? [0, 1], i = 1, 2 , (r1 , r2 ) ? R 2 рассмотрим соответствующий прямой
механизм. Он задается следующими соотношениями:
x ( c, c ) (r1 , r2 ) = (r1 , r2 ) , при
54
(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 ? 2 ? r2 , 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} U {r1 ? (1, 2], r2 < 2 ? r1} ;
x ( a , m ) = (2, 1) , при (r1 , r2 ) ? D( a , m ) = {r1 < 1, r2 > 1} U {r1 ? [1, 2 ), r2 > 2 ? r1 ? 1} ;
x ( a , a ) = (0, 0) , при (r1 , r2 ) ? D( a , a ) = { r1 < 0, r2 < 0 }.
Легко проверить, что U D? = R 2 и ?? 1 ? ? 2 , D? 1 I D? 2 = ? , то есть B
? ??2

есть разбиение R 2 . Множества разбиения изображены на рис. 2.1.l

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

???n.
? ??n
Из определения 2.1.2 очевидно, что для любого
выполнено включение D ? ? D? . Так же очевидно, что если для любого
0

?
вектора сообщений r ? D? выполняется h( ˜ ) = x ( ˜ ( ? ) ) , то для
˜ 0
r rC
любого вектора истинных точек пика r ? D? сообщение достоверной
0

0
информации является наилучшим сообщением из D ? для всех АЭ.
Пример 2.1.2. Для примера 2.1.1 множества совокупности
0
B имеют вид:
D(0a , a ) = {r ? R 2 : r1 < 0, r2 < 0} ;
D(0c , a ) = {r ? R 2 : r1 ?[0, 1], x 2 < x1 } ;
D(0m, a ) = {r ? R 2 : r1 > 1, r2 < 1} ;
D(0m, c ) = {r ? R 2 : r2 ?[1, 2], r1 > 1 ? 2r2 } ;


55
D(0m, m) = {r ? R 2 : r1 > 3, r2 > 2} ;
D(0c , m) = {r ? R 2 : r1 ?[2, 3], r2 > 1 + r2 } ;
D(0a , m) = {r ? R 2 : r1 < 2, r2 > 1} ;
D(0a , c) = {r ? R 2 : r2 ?[0, 1], r1 < 2r2 } ;
D(0c , c ) = D( c , c ) по определению.
0 0 0 0 0
ножества D( a , a ) , D( c , a ) , D( m, a ) , D( m, c ) , D( m, m) изображены на рис.
2.2.l
r


D(c, m) D( m, m)
D(a, m)
2

D( m , c )

1 D( c , c )


D(a, c) D(0m, a )
r
1 2 3
0
D(c, a) D(c, a)


Рис. 2.1. Множества B - разбиения для примера 2.1.1
Свойства множеств из B 0 иллюстрируются следующей леммой.
0
Лемма 2.1.1. Рассмотрим произвольный r? D? , тогда:
a) ?i?M(?) { (˜ , r ) ? D 0 } ? {˜ > x ? (r
r r ) }, (2.1.1)
?i ? C(?)
i i i




56
r


D(0m, m )
D(c, m)
D(a, m)
2

D(0m, c )
1

D(a, c) D(0m, a )
D(0c , a ) r
1 2 3
D(0c , a) 0

Рис. 2.2. Множества совокупности B0 для примера 2.1.2

б) ?i?R(?) {(˜ , r?i ) ? D? } ? {ri < xi? (rC ( ? ) )} . ? 2)
˜
0
ri (2.1.2)
Под записью B=B0 будем подразумевать, что ?? ??n , D? = D? .
0


Теорема 2.1.1. Пусть I - множество активных элементов,
функции полезности которых обобщенно однопиковые. Пусть механизм
h : R n > R n удолетворяет А.2.1.1 и B=B0 , тогда он неманипулируем. ?
Очевидно, условия теоремы 2.1.1 не выполнены в примере 2.1.1.
Механизм примера 2.1.1 оказывается манипулируемым. Возьмем,
например, такой профиль предпочтений, что функции полезности
?1 ( x1 ) = ? x1 , ? 2 ( x 2 ) = ? x2 ? 1 2 имеют точки пика равные
соответственно (0, 1 2) . Сообщая достоверную информацию, элементы
получают планы (1, 1 2) и полезности (1, 0) соответственно. Если же
первый активный элемент сообщит недостоверную информацию: 1 2 , а
второй сохранит своё сообщение 1 2 , то будут назначены планы
(1 2 , 1 2) и полезности элементов в этом случае будут (0, 0) .

Символ “ ? ” после формального утверждения означает, что его
2)

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




58
§2. Коалиционная неманипулируемость прямых механизмов

В §1 настоящей главы были построены достаточные условия
неманипулируемости прямых механизмов планирования. В настоящем
параграфе мы введем понятие коалиционной неманипулируемости и
получим необходимые и достаточные условия коалиционной
неманипулируемости для механизмов, удовлетворяющих предположению
А.2.1.1.
Введем несколько отношений между векторами в R n , которые
будут необходимы нам в дальнейшем. Будем писать, что x < ? > y ,
x, y ? R n если xC ( ? ) = yC ( ? ) , x A( ? ) < y A( ? ) , xM ( ? ) > yM ( ? ) . Используя это
0
обозначение, определение множеств D? , D? можно записать следующим
образом:
D? = {˜ ? R n ˜ < ? > h(˜ )} , ? ??n .
r r r

D? = {˜ ? R n ˜ ( ? ) ? ProjC ( ? ) D? , ˜ < ? > x ? (˜ ( ? ) )} , ? ??n
0
r rC r rC
Кроме отношения < ? > определим отношение < ? > . Будем
записывать x < ? > y , если xC ( ? ) = yC ( ? ) , x A( ? ) ? y A( ? ) , xM ( ? ) ? y M ( ? ) .
Для каждого подмножества активных элементов J ? I и для
каждого вектора состояний ? ??n определим множества D( ? , J ) и
вектора состояний c ( ? , J ) следующим образом:
?˜ ?˜
D 0 ( ? , J ) = {˜ ? R n ˜ ( ? ) ? Proj D? , ˜ = x J (rC ( ? ) ), r? J < ? > x? J (rC ( ? ) )} ,
˜
r rC rJ
C(?)

c ( ? , J ) ??n : cJ ( ? , J ) = ? J и ?i ? I \ J > ci ( ? , J ) =' c' .
В дальнейшем будем исследовать прямые механизмы,
удовлетворяющие следующему условию
A.2.2.1. ?? ??n , ?J ? I > D 0 ( ? , J ) ? Dc ( ? , J ) .
0


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




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

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

Коалиционная неманипулируемость означает, что для любого
профиля предпочтений и для любой коалиции ни какая коалиция АЭ не
может получить выигрыш от создания коалиции либо полезность одиного
из АЭ рассматриваемой коалиции строго убывает при образовании
коалиции.
Верны следующие утверждения
Лемма 2.2.1. Пусть механизм h : R n > R n удовлетворяет
предположениям А.2.1.1, А.2.2.1 и для него D = D 0 , тогда этот механизм
коалиционно неманипулируем. ?
Лемма 2.2.2. Пусть механизм h : R n > R n удовлетворяет А.2.1.1
и коалиционно неманипулируем, тогда D = D 0 . ?
Лемма 2.2.3. Пусть механизм h : R n > R n удовлетворяет А.2.1.1
и коалиционно неманипулируем, тогда выполнено А.2.2.1. ?
Следствием Л.2.2.1-Л.2.2.3 является следующая теорема.
Теорема 2.2.1. Для того, чтобы прямой механизм h : R n > R n
удовлетворяющий А.2.1.1, был коалиционно неманипулируем
необходимо и достаточно, чтобы выполнялись условия А.2.2.1 и
D = D0 . ?
Теорема 2.2.1 дает необходимые и достаточные условия для
коалиционной неманипулируемости прямых механизмов в смысле
определения 2.2.1.
В следующем параграфе мы рассмотрим обобщения результатов
§ 1 настоящей главы на механизмы планирования с векторными планами,
60
что является обобщением результатов работ [7,14] о неманипулируемости
механизмов голосования.




61
§3. Неманипулируемость прямых механизмов планирования с
векторными планами

В §§ 1-2 настоящей главы мы получили достаточные условия
неманипулируемости и необходимые и достаточные условия
коалиционной неманипулируемости в терминах множеств диктаторства.
Эти результаты включают результаты работ [7,14,53] для механизмов
планирования со скалярными планами как частные случаи. В настоящем
параграфе мы обобщим результаты этих работ на механизмы
планирования с векторными планами.
Рассмотрим активную систему с сообщением информации.
Обозначим множество активных элементов через I . Пусть активным
элементам назначаются векторные планы x i ? R J i , где J i - множество
компонент планов для i -го активного элемента. Обозначим через J
множество всех компонент планов всех активных элементов J = U J i .
i?I
Будем считать, что функции полезности ? i ( xi ) активных
элементов являются однопиковыми, т.е. такими, что для каждого
активного элемента i ? I существует единственная точка r i ? R J i такая,
что для любой точки x i ? R J i такой, что xi ? r i выполняется
? i ( xi ) < ? i (?x i + (1 ? ? )r i ) < ? i (r i ) , ? ? (0, 1) . Также будем считать
функции полезности активных элементов сепарабельными, т.е. такими,
что для каждого активного элемента i ? I , для любой компоненты его
плана j ? J и для любых компонент плана xi , x?i ? R1 и x i , ˜ i ? R J i \{i}
x ?j ?j
j j
i

таких, что ? i ( xij , x? j ) ? ? i ( x?ji , x? j ) выполняется ? i ( xij , ˜? j ) ? ? i ( x?ji , ˜? j ) .
i i
xi xi
В такой активной системе введем прямой механизм планирования
h : R > R J . По аналогии с индексом состояния АЭ (§ 1 Главы II),
J

определим индекс состояния ? j для каждой компоненты плана каждого
активного элемента j ? J и каждого вектора точек пика r ? R J
следующим образом ? j = a если x j > h j (r ) , ? j = m если x j < h j (r ) и
? j = c если x j = h j (r ) . Обозначим через ? ??J вектор состояний всех
компонент планов всех активных элементов. Индекс состояния i -го
активного элемента i ? I обозначим через ? i = ? J i .



62
e : R Ji > R Ji , i?I
Механизм планирования назовем
элементарным для i -го АЭ, если для всех компонент плана j ? J i и для
?
всех состояний ? j ? c существуют числа x j j ? R{ j} такие, что для
?j ?j
любого r i ? R J i такого, что r ji < ? j > x j выполняется e j (r ) = x j и для
?
любого r i ? R J i такого, что x a < a > r ji и r ji < ? j > x j j . Элементарный
j

механизм планирования для АЭ с двумерным планом из R 2 приведен на
рис. 2.3.1, в нем x1 = x2 = 0 и x1 = x2 = 1 . Очевидно для любого
a a m m


элементарного механизма выполнено B = B 0 .

r2

D( m, m )
D( c, m) D( c, m)


1



D( c, c)
D( a , c ) D( m, c )



r1
0 1
D( m , a )
D( a , a ) D( c , a )



Рис. 2.3.1


Лемма 2.3.1. Пусть функция полезности активного элемента i ? I
однопиковая и сепарабельная, тогда любой элементарный механизм
e : R J i > R J i неманипулируем. ?
Далее будем считать выполненным следующее условие.
63
А.2.3.1. Для любого вектора состояний множество ProjC ( ? ) D? является
односвязным и существует функция x ? : ProjC ( ? ) D? > R J такая, что для
i?I
любого активного элемента величина
? ?
= x J \ C ( ? ) (rC ( ? ) \ C ( ? J ) ) . Для любого
r ? D? выполняется
xJ \ C ( ?
Ji )
i i Ji i
˜
h(r ) = x ? (rC (? ) ) и для любого ? ??J , ?i ? I , ?J ? J i и ?˜ ? Dc ( ? , J )
r
˜
найдется r ? D? такой, что x c ( ? , J ) (˜ (c ( ? , J )) ) = x ? (rC ( ? ) ) .
rC ˜

Теорема 2.3.1. Пусть функции полезности активных элементов
однопиковые и сепарабельные, прямой механизм h : R J > R J ограничен
и удовлетворяет условию А.2.3.1, тогда механизм h(r ) , r ? R J является
неманипулируемым. ?
Данная теорема является обобщением результатов работ для
механизмов коллективного выбора с векторными альтернативами
[7,14,53] и позволяет исследовать неманипулируемость механизмов
планирования с векторными планами в терминах множеств диктаторства.
В следующем параграфе мы рассмотрим механизм активной экспертизы
(МАЭ) и механизм распределения ресурса (МРР), и исследуем их
свойства с точки зрения теории реализуемости и множеств диктаторства.
Так же будут рассмотрено соотношение результатов работ [110,111] и
результатов § 1 настоящей главы.




64
§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 = ? i ( D, ..., D ) . Множество Q на нулевом шаге
полагаем пустым Q 0 = ? .
На шаге j множество Q j определяем следующим образом
Q j = {i ? I : ( x j ?1 )i ? ri } .
Для АЭ из множества Q j по А.1.4.2 определяем ? j ? ? j такие, что
Q Q

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

Если на некотором шаге k окажется, что Q k = Q k ?1 , то алгоритм
останавливается и полагаем s ? = s k , x* = x k , Q k = Q .?
Результаты этого алгоритма обладают следующими свойствами,
приводимыми здесь без доказательства (см. [113]).
Свойство 2.3.1. Если i ? Q , то ?ri? ? xi? (r ) выполняется
xi? (r ) = xi? (ri?, r?i ) ;
?ri? < xi? (r )
i ?Q ,
Свойства Если то выполняется
2.3.2.
xi? (r ) > xi? (ri?, r?i ) ;


65
ri > 0 , то
r ? [0, D ] ,
Свойство 2.3.3. Если при некотором
xi? (r ) > 0 .
Лемма 2.3.1. Для механизма распределения ресурса свойство ММ
выполнено. ?
Лемма 2.3.2. Для механизма распределения ресурса свойство
НСМ выполнено. ?
Лемма 2.3.3. Если d = 0 и ? D > R , то для механизма
j?I
распределения ресурса свойство ОПВ не выполнено. В противном случае
ОПВ выполнено. ?
Лемма 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 t t ... t ? ,
?
? 1 2 3 n?

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

E ? ? и t ? T E следующие множества:
?tE = {r ? [d , D]n : ?l ?{1, ..., E }, ?j ? El , r j = ril и ri1 < ri2 < ... < rin } .
Рассмотрим некоторое разбиение E из ? и произвольную
перестановку t ? T E . Определим вектор s (? ) , ? ? ? следующим образом
?s ? = d , ? = 1, ? ,
?
s (? ) = ?
?s ? = D, ? = (n ? ? ), n, ? ? ?.
?
Обозначим ? t ( s1 , ..., s n ) = ? (st (1) , ..., st ( n ) ) и для заданных E и t ? T E
определим последовательности {W?t }? =1 и {W?t , E }? =1 следующим образом:
n n


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

При заданных разбиении E и перестановке t ? T E , для каждого r ? ?tE ,
соответствующий ? (s) прямой механизм h(r ) определим следующим
образом
h(r ) = max min (rt ?1 (? ) , W?t ,?E ) . (2.3.1)
1
? ??

Очевидно, что для каждого r ? [d , D]n всегда найдутся
единственное разбиение E ? ? и единственная, с точностью до
перестановок внутри множеств El разбиения E , перестановка t ? T E
67
такие, что r ? ?tE . Последовательность {W?t , E }? = 0 не меняется при
n

перестановках элементов внутри множеств разбиения E , поэтому
механизм h(r ) определен для каждого r ? [d , D]n однозначно. Нам будет
удобно обозначить через ?(r ) множество элементов из ? , на которых
, W?t ,?E ) при данном r ? [d , D]n
достигается max min (r ?1
(? ) 1
? ?? t

?(r ) = Argmax min (rt ?1 (? ) , W?t ,?E ) .
1
???
Очевидно, ?(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(˜ , r?i ) < h(r ) ;
ri
2) если r < h(r ) , то ?˜ ? h(r ) , h(˜ , r ) = h(r ) и ?˜ > h(r ) ,
r r r
?i
i i i i

<<

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

СОДЕРЖАНИЕ

>>