<< Пред. стр.

стр. 4
(общее количество: 15)

ОГЛАВЛЕНИЕ

След. стр. >>

2) g ( E G ( R )) I ( =) f ( R ) .
Другими словами, при всех R I A равновесие существует и в любом
из возможных при данном R равновесии s * ( R ) I EG ( R ) принимаемое
решение g ( s * ( R)) лежит в f (R ) .
Говорят, что прямой механизм H = (A, h) реализует СГВ f : A ® A
достоверно, если "R I A выполнены:
D
1) R I E H (R ) ;

2) h( R) I f ( R) .
Достоверная реализуемость означает, что сообщение достоверной
информации в механизме H является доминантной стратегией, и при
сообщении достоверной информации выбирается допустимая для центра
альтернатива.
Рассмотрим некоторые свойства соответствий группового выбора,
необходимые для исследования реализуемости СГВ.
Рассмотрим бинарное отношение над множеством и
RA A
некоторую альтернативу a I A . Нижним срезом L(a, R A ) отношения R A
по a называется множество X I A , определяемое следующим образом:
X = {b I A : aR A b} . Верхним срезом H (a, R A ) отношения R A по a
X I A , определяемое
называется множество следующим образом:
X = {b I A : bR A a} .
Говорят, что СГВ f : A ® A удовлетворяет условию монотонности
Маскина (ММ) если "{R , R ?} I A, a I f (R ) таких, что a I f (R ) и
"i I I , L(a, Ri ) I L (a, Ri? ) выполняется a I f (R ?) .
Содержательно, ММ означает, что, если при некотором профиле
предпочтений R I A одной из альтернатив, выбираемых по СГВ будет

32
альтернатива a I f (R ) , и профиль предпочтений элементов изменятся на
R ? I A таким образом, что в новом профиле позиция альтернативы a по
отношению к другим альтернативам для всех элементов не ухудшается, т.
е. "i I I , L(a, Ri ) I L(a, Ri? ) , то альтернатива a будет выбираться и при
новом профиле предпочтений a I f (R ?) .
Для однозначных соответствий группового выбора (ОСГВ), то есть
таких, что "R I A ® f ( R ) = 1 , определяется следующее свойство
ОСГВ f : A ® A удовлетворяет независимой слабой монотонности
(НСМ) тогда и только тогда, когда "i I I , "R I A
I H ( f ( Ri? , R-i ), Ri ) .
f ( R) I
R?IA
Содержательно, НСМ означает, что при сообщении
достоверной информации, для всех элементов назначается наилучшая
альтернатива, что является аналогом УСС.
Говорят, что СГВ удовлетворяет свойству отсутствия права вето
"a I A, "i I I , $R I A : "i ? j, "b I A, aR j b
(ОПВ), если выполнено
a I f (R ) . То есть, если есть альтернатива a наилучшая с точки зрения
всех активных элементов кроме некоторого j , то a I f (R ) .
СГВ f : R ® A называется диктаторской, если $i I I такой, что
"R I A, "a I A, a I f ( R) тогда и только тогда, когда "b I A, aRi b . Это
означает, что среди элементов I найдется элемент j такой, что
альтернатива a выбирается по СГВ тогда и только тогда, когда для j - го
элемента нет никакой другой альтернативы, строго лучшей её.
f :A ® A
СГВ называется Парето - оптимальной, если
"R I A, "{a, b} I A если "i I I , aPi b , то b I f (R ) . Парето - оптимальность
означает, что если какая - то альтернатива b для всех элементов строго
хуже альтернативы a , то альтернатива b не может быть выбрана по этой
СГВ.
Еще одним важным свойством СГВ является существенная
монотонность [66].


33
Альтернатива a I X I A называется существенной для активного
элемента i I I во множестве X если существует профиль предпочтений
R I A такой, что a I f (R ) и L(a, Ri ) I X .
Множество всех существенных для элемента i I I во множестве
X I A обозначим Ess (i, X ) .
f :A ® A
СГВ называется существенно монотонным если
"R, R ? I A "a I f (R ) "i I I
и таких, что выполняется
Ess (i, L( x, Ri )) I L( x, Ri? ) ® a I f ( R ?) .
Приведем далее результаты, дающие необходимые и достаточные
условия реализуемости СГВ при использовании понятий равновесия Нэша
и равновесия в доминантных стратегиях. Теоремы 1.3.1-1.3.4 представляют
условия реализуемости при использовании определения равновесия в
доминантных стратегиях, теоремы 1.3.5-1.3.7 являются условиями
реализуемости при использовании определения равновесия Нэша.
f : A ® A было
Теорема 1.3.1. [53,66]. Для того, чтобы ОСГВ
достоверно реализуемо в доминантных стратегиях, необходимо и
достаточно, чтобы оно удовлетворяло НСМ.
f : A ® A достоверно реализуема в
Теорема 1.3.2 [53,66]. СГВ
доминантных стратегиях тогда и только тогда, когда существует ОСГВ
f * , удовлетворяющая НСМ, такая, что для всех R I A , f * (R ) I f (R ) .
Теорема 1.3.3 [53,66]. Пусть A содержит только строгие порядки,
СГВ f : A ® A достоверно реализуема в доминантных стратегиях тогда и
только тогда, когда f является ОСГВ и удовлетворяет НСМ.
Теорема 1.3.4. [53,66]. Предположим, что A включает все возможные
строгие предпочтения над A . Тогда не существует ОСГВ f , множество
значений которой содержит не менее трех различных альтернатив, которая
достоверно реализуема в доминантных стратегиях.
Вместе с теоремой 1.3.2, последний результат утверждает, что ни
одно достаточно сложное СГВ не может быть реализовано в доминантных
стратегиях, если на множество возможных профилей предпочтений не
наложены дополнительные ограничения.

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

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

35
ia * , при a j P j* a * ;
i
g (s) = i
**
ia j , при a R j a j .
i
g ( s) = a k ( s ) ,
s I Sd ,
Правило 1.3.2. Если то где
k ( s ) = max{i I I z i ? z j , "j I I } .
Введенный таким образом механизм назовем механизмом Маскина.
Первое правило определяет действие механизма в случае, когда все
активные элементы, кроме быть может одного, сообщают одинаковые
профили предпочтений R * , одинаковые альтернативы a * I f ( R * ) и не
желают принять участие в лотерее, то есть "i ? j , z i = 0 . В этом случае
считается, что все кроме j -го элемента сообщают достоверный профиль
R * , соответствующий действительному профилю
предпочтений
предпочтений всех элементов, и большинство голосует за альтернативу
a * . При этом из согласованных сообщений остальных АЭ делается
однозначное предположение R * о предпочтениях j -го элемента и
j

выбирается альтернатива, наихудшая для j -го АЭ. Второе правило
определяет так называемую целочисленную игру. Если сообщения
элементов не согласованны, то любой элемент выбором соответствующего
натурального числа может добиться выбора наилучшей для себя
альтернативы. Имеет место следующая
I ?3 и f : A ® A монотонная по
Теорема 1.3.6 [53,66]. Если
Маскину СГВ, удовлетворяющая ОПВ, то механизм Маскина реализует
эту СГВ по Нэшу.
Как видно из определения, в механизме Маскина каждый активный
элемент сообщает профиль предпочтений всех элементов, точное знание
которого не всегда возможно. Множество возможных сообщений было
значительно сужено в работах Сайжо (Saijo) [90] и МакКельви (McCelvey)
[83]. Перейдем к описанию введенного ими механизма.
Определим механизм МакКельви следующим образом. Обозначим
множество элементов через I = {1, ..., n} . Будем считать, что элементы
нумеруются по mod n , то есть номер k I Z соответствует элементу с
36
номером k (mod n) . Каждый элемент i I I = {1, ..., n} посылает в центр
сообщение следующей структуры:
si = (ai , Ai , Bi , ni ) , где ai I A , и $R I A такое, что либо Ai = L(a, Ri ) и
Bi = L(a, Ri +1 ) , Ai = L (a, Ri ) Bi = ? .
либо и Таким образом
Si = A ? 2 A ? 2 A ? N и S = O S i .
iII
sIS j I I , обстановка
Для любых и s- j называется f-

согласованной, если $a I A и $R* I A такие, что
1) a* I f ( R* ) ;
2) ai = a* , "i I I \ { j} ;
3) "i ? j , Ai = L(a* , Ri* ) и Bi = L(a* , Ri*+1 ) .
Процедура принятия решения механизма МакКельви определяется
следующими правилами.
Правило 1.3.3. Пусть число элементов I ? 3 , тогда для любого s I S
если $j I I такой, что a j ? a j -1 и обстановка s- j является f-
согласованной, то
ia j , a j I B j -1 ;
i
g ( s) = i
ia j -1 , a j I B j -1.
i
g (s) = a k ( s) ,
Правило 1.3.4. В противном случае, где

a ni (mod n) .
k ( s) =
iII
Как оказалось, для любой СГВ с количеством активных элементов
больше трех верна следующая
Лемма 1.3.1. [53,83]. Пусть I ? 3 , тогда для любой СГВ f : A ® A и
определенного для неё механизма МакКельви верно
N
"R I A, f ( R ) I g ( EG ( R )) .
Таким образом, любая СГВ, удовлетворяющая условиям леммы
1.3.1, может оказаться нереализуемой лишь в том случае, когда имеются
дополнительные равновесия s * такие, что g ( s * ) I f ( R) .

37
Теорема 1.3.7. [53,83]. Пусть I ? 3 и пусть f : A ® A монотонное по
Маскину СГВ, удовлетворяющее ОПВ, тогда механизм МакКельви
реализует по Нэшу СГВ f .
Принципы построения механизмов Маскина и МакКельви,
используются при простроении «консолидированных» механизмы обмена
для ОС типа цепочка, рассматриваемых в разделе 3.2.
Завершив обзор основных результатов ТАС и микроэкономической
теории, применимых для построения неманипулируемых механизмов
обмена в активных системах, перейдем к формулировке общего метода
построения неманипулируемых механизмов обмена для ОС


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


Обменная схема состоит из n+1 агентов (Центр и n активных
элементов) и m видов ресурсов. Заданы функции полезности АЭ,
f i ( xi , ri ) : R m+1 ® R, ri I W i ,
зависящие от вектора трансфертов ресурсов
i = 1,..., n . Параметр ri – тип элемента, характеризующий некоторым
образом его функцию полезности.
Агенты ОС информированы ассиметрично – центр знает все
параметры схемы, кроме значений типов АЭ – ему известны лишь
множества возможных значений и, быть может, вероятностное
распределение типа на множестве возможных значений.
Информированность АЭ не существенна для общего метода построения
неманипулируемых механизмов обмена.
Данный прием является стандартным для введения внутренней
неопределенности в систему [10-12,18,22,29,45,53,57,59,64,65,81,82,86,91],
и достаточно легко трактуется на качественном уровне – в большинстве
задач ТАС тип активного элемента отражает его ценность с точки зрения
центра – чем выше тип, тем лучше этот элемент для центра (тем большую
полезность центр может получить от взаимодействия с таким элементом).

38
x= p (s ) ,
Задача центра – построить механизм обмена
максимизирующий некий функционал (целевую функцию центра) Ф( s ,x) :
K ( s ) = min F ( s , p ( s )) ® max ,
p (s )
s IW


где s = ( s1 ,..., sn ) - вектор заявок АЭ. АЭ сообщают центру оценки своих
типов, то si I W i , i = 1, n - т.е ищется прямой механизм обмена.
Порядок функционирования механизма обмена стандартен для
механизмов планирования:
Центр объявляет механизм обмена p (s ) ;
АЭ сообщают центру свои заявки s* = ( s1 *,..., sn *) ;
Центр назначает обмен x = p ( s*) .
Механизм обмена ищется в классе прямых неманипулируемых
механизмов – т.е. механизмов, для которых доминантной стратегией
каждого АЭ будет сообщение истинной заявки - s* = (r1 ,..., rn ) .
Введем ограничения, необходимые для общего решения поставленной
задачи. Прежде всего это ограничения на вид функции полезности АЭ.
Нам необходима непрерывность функции полезности, существование и
непрерывность ее частных производных вплоть до второго порядка по
всем переменным. Кроме того частная производная функции полезности
по типу АЭ должна быть монотонна, например
¶f i
( x i , ri ) ? 0, i = 1, n, ri I W i .
(F1)
¶ri
Кроме того, решение поставленной задачи сильно упрощается, если
мы используем условия Спенса-Мирлиса – постоянство знака смешанной
производной ¶ 2 f i / ¶x ij ¶ri [91], например такое: "i, $l (i), такое, что
¶ 2 fi
(F2а) "ri I W i , " xi , ( xi , ri ) > 0 ,
¶xl ¶ri
i



и
¶ 2 fi
(F2b) "i, "j ? l (i ), "ri I Wi , "x , ( xi , ri ) ? 0 .
i

¶xli ¶ri
j




39
Также, необходимо записать условия индивидуальной рациональности
(ИР) для всех АЭ. Без потери общности, можно предложить простейшие
условия – прибыль любого АЭ (значение функции полезности) должна
быть неотрицательна.
Ограничения на ресурсы и возможность взаимодействия между
агентами схемы не уточняются, хотя они безусловно отразятся на
конечном решении задачи для конкретных моделей. Кроме того,
множество возможных вариантов обмена непусто (это следует из
постановки задачи – мы сразу рассматриваем обменную схему).
Прямой неманипулируемый механизм должен отвечать условию
совершенного согласования (УСС)[52]:
fi ( xi , si ) = max f i ( z , si )
zI X i ( s-i )


X i ( s - i ) - Множество возможных трансфертов для i-го АЭ при
фиксированном векторе сообщений остальных АЭ s-i.
Введем функцию зависимости прибыли i-го АЭ от значения
собственного параметра ri, своей заявки si, и заявки остальных участников
обменной схемы s-i:
Vi (ri , s i , s - i ) = f i ( x i ( s i , s - i ), ri ) .
УСС можно проинтерпретировать следующим образом:


i ¶V i
i ¶s (ri , ri , s - i ) = 0
ii
(1) "ri I W i , "s - i I W - i , i 2
i ¶ Vi (r , r , s ) ? 0
i ¶s i 2 i i - i
i
Из первого условия (1а) очевидным образом следует, что
¶f i dx j i
m
(2) a i ( x i (ri , s - i ), ri ) (ri , s - i ) = 0 .
j =1 ¶x dri
j


Лемма 1. Условие (1b) "ri I W i , "s -i I W -i эквивалентно неравенству
¶2 fi dx j i
m
(3) a i (ri , s - i ) ? 0 .
( x i (ri , s - i ), ri )
j =1 ¶x ¶r ds i
j i




40
Доказательство. В развернутом виде, условие (1b) записывается
следующим образом:
¶ 2 fi dx ij dxli
m m

a[a ¶x i ¶x i ( xi (ri , s-i ), ri ) ds (ri , s-i ) ds (ri , s-i ) +
j =1 l =1 j l i i
(4)
¶f i d 2 x ij
+ i ( xi (ri , s-i ), ri ) 2 (ri , s-i )] ? 0.
¶x j dsi
Продифференцировав выражение (2) по ri, получаем:
¶ 2 fi dx ij dxli
m m

a[a ¶x i ¶x i ( xi (ri , s-i ), ri ) ds (ki , s-i ) dr (ri , s-i ) +
j =1 l =1 j l i i


¶ 2 fi dx ij
(5) + i ( xi (ri , s-i ), ri ) (ri , s-i ) +
¶x j ¶ri dsi
¶f i d 2 x ij
+ i ( xi (ri , s-i ), ri ) (ri , s-i )] = 0.
¶x j dsi dri
Очевидно, что
dx ij dx ij
(ri , s - i ) = (ri , s - i ) .
ds i dri
Вычитая из равенства (5) неравенство (4) получим выражение (3).¦
Теорема 1. В рамках введенных предположений следующие условия:

¶f i dx j i
m
1. a i ( x i (ri , s - i ), ri ) (ri , s - i ) = 0 .
j =1 ¶x dri
j


¶2 fi dx j i
m
2. a i (ri , s - i ) ? 0 .
( x i (ri , s - i ), ri )
j =1 ¶x ¶r ds i
j i


3.Все компоненты планов, назначаемых центром каждому АЭ изменяются
монотонно в зависимости от заявки данного АЭ:
dx ij

<< Пред. стр.

стр. 4
(общее количество: 15)

ОГЛАВЛЕНИЕ

След. стр. >>