<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

i =1 i =1 i =1


¶c i
ri

Где V (r ) = ax (r ) - c( x (ri , r-i ), ri ) + ( x2 (t , r-i ),t )dt .
o
i i i

¶ri
0 2 2
rmin


Следовательно, задачу максимизации ожидаемой прибыли центра
можно представить виде задачи динамического программирования:
¶c i
ri

[ax - c( x , ri ) + ( x2 ,t )dt ]r (ri ) r ?(r-i )dri dr-i , i = 1, n ;
x (ri , r-i ) = arg max o o o
i i i

¶ri
2 2 2
i
x2
W W n -1 rmin


x2 (ri , r-i ) ? Y2 - a x2j (rj , r- j ) , x1i (ri , r-i ) ? Y1 - a x1j (rj , r- j ) , i = 1, n .
i

n/i n/i


Очевидно, что для " i = 1, n функции x2 (ri , r-i ) имеют одинаковый вид.
i



Причем их можно представить в следующем виде - x2 (ri , r-i ) = x2 (ri ) , где
i i



x2 (ri ) является решением задачи динамического программирования:
i




¶c
ri

( x 2 ,t )dt ]r (ri ) r ?(r-i )dri dr-i , i = 1, n ;
[ax2 - c( x2 , ri ) +
x2 (ri ) = arg max o o o ¶ri
x2
W W n -1 rmin


x2 (ri ) ? Y2 - a x2 (rj ) = Y2 (r-i ) , x1 (ri ) ? Y1 - a x1 (rj ) = Y1 (r-i ) , i = 1, n .
n/i n/i

n

aY (r-i ) = Y j , j = 1,2. ¦
При этом i
j
i =1



93
Иными словами, для рассматриваемой модели ОС с веерным типом
взаимодействия агентов задача построения неманипулируемого механизма
обмена эквивалентна задачи для ОС с одним АЭ. Задача построения
эффективного и неманипулируемого механизма обмена разбивается на две
задачи – задача построения эффективного и неманипулируемого
механизма обмена для ОС с одним АЭ и задача оптимального
распределения ресурсных ограничений между АЭ. Поясним
вышесказанное. Эффективный и неманипулируемый механизм обмена
имеет следующий вид - p (r ) = (p (˜ ),..., p (˜ )) . p (r ) = ( x1 (r ), x2 (r )) -
? r1 ? rn ?
эффективный и неманипулируемый механизм обмена для ОС с одним АЭ:

Функция полезности Ц - f 0 ( x1 , x2 ) = H ( x2 ) - x1 ;

Функция полезности АЭ - f ( x1 , x2 ) = x1 - c( x2 , r ) ;

¶c
r

( x2 (t ),t )dt ,
o
x1 (r ) = c( x2 (r ), r ) -
¶r
rmin




x2(r) = arg max Ef0(x1(x2),x2,r).
x2


˜ - назначаемый тип i-ого АЭ, задается следующим образом:
ri
˜ = min[ r , r ] .
?i ?
Критические типы определяются выполнением
ri ri
i

n n

ax ax
(ri ) = Y1 (ri ) = Y2 .
? ?
ресурсных ограничений: или Задача
1 2
i =1 i =1

оптимального распределения ресурсных ограничений между АЭ:
V0 (r ) ® max , r = (r1 ,..., rn ) .
? ?? ?
?
r

Метод построения эффективных и неманипулируемых механизмов
обмена для ОС с веерным типом взаимодействия агентов может быть
проиллюстрирована на примере следующей задачи.
Задача 5. Построить эффективный неманипулируемый механизм
обмена для ОС состоящей из центра и двух АЭ. Функции полезности от
2
x2
i

обмена центра - f 0 ( x1 , x 2 ) = x 2 - x1 , АЭ - f i ( x1i , x 2 , ri ) = x1i - ,
i

2ri

94
ri I? = [rmin,rmax], i = 1,2 . Ограничения x 2 ? Y2 . Центру известно, что
r - rmin
распределение типов АЭ равномерно - F ( r ) = .
rmax - rmin

Механизм ОУ p (r ) = ( x 11 (r1 ), x 1 2 (r1 ), x 2 1 (r2 ), x 2 2 (r2 )) имеет следующий
вид -
p (r ) = (p (˜ ), p (˜ )) ;
? r1 ? r2
iri , "ri I W?, "r-i I W
˜ = imax[r , (r Y - r 2 )1 / 2 ], "r I W / W?, "r I W? , i = 1,2 ;
ri i -i -i
i max 2 i
ir , "r I W / W?, "r I W / W?
i? -i
i


rmaxY2 1 / 2
W? = [rmin , r ] , r = (
?? ).
2
4ri - rmin
2 3
? ?
ri 3

Здесь p (r ) = ( x1 (r ), x 2 (r )) : x i 2 (ri ) = , x i 1 (ri ) =
? .
rmax 6rmax
2




p (r ) = (p (˜ ), p (˜ ))
? r1 ? r2
Утверждение 11. Механизм является
неманипулируемым и оптимальным.
Доказательство. Очевидно, что неманипулируемый механизм обмена
p (r ) = ( x1 (r ), x2 (r )) является оптимальным для ОС с одним АЭ.
?
Задача оптимального распределения ресурсных ограничений имеет
следующий вид:
2(r1 + r2 ) - rmin r12 + r22
3 3
? ? ? ?
3

V0 (r1 , r2 ) = Y2 - ® max , = Y2 .
??
3rmax rmax
2 ??
r ,r
1 2
1

Y2 rmax 1 / 2
Не трудно видеть, что r1 = r2 = (
?? ).
2
Задача оптимального распределения ресурсных ограничений является
частным случаем задачи распределения ресурсов, для которой доказана
оптимальность неманипулируемых механизмов планирования (см. теорема
5.3 [52]).
Используя метод множеств диктаторства [53] можно показать
неманипулируемость предложенного метода определения назначаемых


95
типов ˜ и ˜ . На рисунке 11 решение задачи обмена представлено в
r1 r2
графическом виде.




Рис. 11. Множества диктаторства

Область D1, 2 : p (r ) = (p (r1 ), p (r2 )) - обоим АЭ назначаются планы в
? ?
соответсвии с их заявками. Область D1 : p (r ) = (p (r1 ), p (˜ )) - АЭ 1
? ? r2
является диктатором – назначаемые планы зависят только от его заявки.
Область D2 : p (r ) = (p (˜ ), p (r2 )) - АЭ 2 является диктатором – назначаемые
? r1 ?
планы зависят только от его заявки. Область D : p (r ) = (p (r ), p (r )) - планы
?? ??
обоих АЭ не зависят от их заявок. Поэтому, в соответствии с теоремой
2.1.1 [53] предложенный метод определения назначаемых типов
неманипулируем. Следовательно, неманипулируем и весь предложенный
механизм обмена. ¦ ?
Полученные в данном разделе результаты, вероятно, могут быть
перенесены на более общий вид модели ОС с веерной структурой
взаимодействия агентов. Но это является предметом дальнейших
исследований. Перейдем к рассмотрению ОС со структурой
взаимодействия агентов типа «цепочка»

96
3.2. Неманипулируемые механизмы обмена для обменных схем со
структурой взаимодействия агентов типа «цепочка»
Пример подобной ОС изображен на рисунке 12.




Рис. 12. Многоэлементная ОС со структурой взаимодействия
агентов типа «цепочка»
ОС состоит из центра и двух АЭ. В системе имеются ресурсы трех
типов. В обмен на получаемый от центра ресурс типа 1, АЭ1 передает АЭ2
ресурс типа 2. В свою очередь, АЭ2 в обмен на полученный от АЭ1 ресурс
типа 2 передает центру ресурс типа 3.
Вид функций полезности от обмена:
(122) f 0 ( x1 , x3 ) = x3 - cx1 для Ц,

(123) f1 ( x1 , x2 , r1 ) = r1 x1 - x2 для АЭ1,

(124) f1 ( x2 , x3 , r2 ) = r2 x2 - x3 для АЭ2.

Ресурсные ограничения в терминах трансфертов имеют следующий вид
А={ x1 I [0, Y1 ], x2 ? 0, x3 ? 0 }. Центру известны диапазоны возможных
значений типов АЭ ri I?i = [ r i , ri ]. Задача центра – построить механизм
обмена ОУ, максимизирующий его гарантированную относительную
f 0 (p ( s))
® max , s = ( s1 , s2 ) - вектор сообщений АЭ
прибыль от обмена min det
f 0 ( s) p
s



оценок своих типов.
Лемма 6. Максимальный доход выражается:
97
(125) f 0 (r1 , r2 ) = (r1r2 - c)Y1 .
det




Доказательство. Действительно, руководствуясь принципом
индивидуальной рациональности для активного элемента, получаем из
f 0 (r1 , r2 ) ? (r1r2 - c) x1 и
det
(123) и (124), что r1x1 ? x2 и r2x2 ? x3. Поэтому
достигает максимума при x1 = Y1 . ¦
Рассмотрим различные методы построения неманипулируемого
механизма обмена для предложенной ОС.
Метод «консолидации АЭ».
Центр рассматривает всех АЭ как единый АЭ и решает задачу
нахождения механизма обмена ОУ для полученной базовой ОС (см.
рисунок 13.).




Рис. 13. Метод «консолидации АЭ»
Фактически мы рассмотрим взаимодействие центра с коалицией,
состоящей из двух активных элементов. Пока мы ничего не предполагаем
относительно того, как будут взаимодействовать АЭ между собой (т.е
какой будет дележ). Но очевидно, что для любого положительного
выигрыша данной коалиции найдется такой дележ, когда выигрыши обоих
АЭ будут неотрицательны. Поэтому предположим, что для при любом
плане обмена, предложенном центром, выигрыш коалиции от которого не
отрицательный, оба АЭ не откажутся от участия в обмене. Устанавливать
дележ между собой АЭ могут путем определения количества ресурса типа
y, который АЭ1 передает АЭ2. Таким образом трансферты в цепочке
остаются прежними.

98
Лемма 7. Целевая функция коалиции записывается следующим
образом:
(126) f12 = r1r2x1 – x3.
Доказательство. Рассмотрим некий план (x1,x3), предложенный
центром. Предположим, что АЭ сообщили и или знают истинные значения
обменных коэффициентов друг друга. Из (123) и (124) получим следующее
выражения:
x2 = r1 x1 –f1.
Следовательно
f2 = k2 (k1 x –f1) – z.
Следовательно
(127) f2 + k2f1= k2 k1 x – z.
В левой части выражения (127) стоит суммарный выигрыш обоих АЭ
в размерности ресурса типа z, т.е. суммарный выигрыш коалиции, а правая
часть совпадает с правой частью выражения (126).
Рассмотрим аналогичным способом ситуацию, когда оба АЭ
взаимодействуют между собой на основании некоторых произвольных
заявок s1=[ r 1 ,r1 ] и s2=[ r 2 ,r2 ]. Иными словами АЭ искажают информацию о
своих обменных коэффициентах (очевидно с целью получения
дополнительной прибыли). Тогда по аналогии с (127)
f2? + s2f1?= s2 s1 x1 – x3,
где f1? и f2? “заявленная” прибыль АЭ. Но из (123) и (124)
x2 = r1 x1 –f1;
x3 = r2 x2 –f2.
Где f1 и f2 - полная прибыль каждого из АЭ. Следовательно выражение
(127) будет выполняться для истинных значений прибыли участников
коалиции:
f2 + r2f1= r2 r1 x1 – x3.
Тем самым мы доказали, что целевая функция коалиции записывается
выражением (126).¦
Т.е. мы получили обменную схему состоящую из центра с функцией
полезности (122) и одного АЭ с целевой функцией (126). Центр знает
99
диапазон возможных значений обменного коэффициента АЭ W=[ r 1 r 2 , r1r2 ].
Используя построенный в главе 1 неманипулируемый механизм обмена
для задачи 4, построим механизм открытого управления [х1(s),х3(s)], где
s=s1s2:
m (r1r2 )
(128) x1 ( s) = Y1 ;
m ( s)

1
(129) x3 ( s) = m (r1r2 )( s - c(1 - ))Y1 ;
m ( s)
где
s - c -1
(130) m ( s) = [1 + ln ].
r1 r 2 - c

Функция полезности центра при использовании данного механизма
записывается как
(131) f 0 ( s1 s 2 ) = m (r1 r2 )( s1 s 2 - c)Y1 .

Утверждение 12. Оптимальные заявки для коалиции будет s*=r1r2.
Доказательство. Из (126), (128), (129) и (130) следует, что
s (r r - s s )
¶f 12
= m ( r1 r2 ) -i 1 2 1 2 Y1 , i = 1,2 ;
¶s i s1 s 2 - c
s-i (r1r2 - c)
¶ 2 f12
2

= - m (r1r2 ) Y1 .
¶s1¶s2 s1 s2 - c
Таким образом, видно, что максимум f достигается при s1s2=r1r2 , так
¶f12 ¶ 2 f12
как для si =0, а <0 при si=r1r2/ s-i .¦
¶si ¶s1¶s2

Следовательно, построенный механизм обмена (128) - (130) можно
назвать «механизмом открытого управления для коалиции». Но данный
механизм нельзя назвать полным, т.к. он не определяет размер трансферта
ресурса типа 2. Предполагается, что «коалиция» АЭ сама сумеет поделить
полученный ею выигрыш от обмена.



100
Рассмотрим, каким образом можно ввести в механизм обмена (128) -
(130) зависимость размера трансферта ресурса типа 2 от заявок игроков.
Утверждение 13. Не существует такой функции x2(s1,s2), для которой
выполнялись бы следующие требования:
r1 = arg max f1 ( s1 , s2 ) ;
s1


r2 = arg max f 2 ( s1 , s2 ) .
s2


Доказательство. Для выполнения приведенных в утверждении
требований необходимо, чтобы x2(s1,s2) удовлетворяла следующей паре
¶f1 ¶f

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>