<< Предыдущая

стр. 3
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Можно показать, что R-механизм с выпуклыми функциями
приоритета дает определенное преимущество агентам с высокими
заявками. Более точно, имеет место:
i i
? z k < ? ˜k , i = 1, ( n ? 1)
z
k =1 k =1

б) Линейные функции приоритета. Пусть ? i ( y i ) = y i . В этом
случае
yi R
x i = ? i ( y, R ) = y i min(1; ? ) = , R?Y
Y
и R-механизм полностью аналогичен обычному приоритетному
механизму с линейными функциями приоритета.
16


в) Вогнутые функции приоритета. Пусть ? i ( y i ) = y i и y i

упорядочены по возрастанию и все различны, то есть
y 1 < y 2 <... < y n .
Обозначим:
2
?n ?
i ?1
? ? y j ? , i = 1, n .
? i = yi , Ri = ? y j + ? i B i где B i = ? ?
? j= 1 ?
j=1

Имеем
i
C(R k ) - C(R k-1 )
zi = yi ? ?
Bk
k =1

Обычный приоритетный механизм с теми же функциями
приоритета дает распределение затрат
yi
˜= ? C(Y) , i = 1, n .
zi
B1

В данном случае R-механизм дает преимущество агентам с
меньшими заявками, то есть имеет место
i i

? z k < ? ˜k .
z
k =1 k =1

R-механизм обратных приоритетов. Рассмотрим функции
приоритета ? i ( y i ) = 1 y i . Пусть y i упорядочены по возрастанию и
все различны, то есть y 1 < y 2 < ... < y n .
Обозначим:
?1
?n 1?
k
1
, где Q i = ? ? ? , i = 2, n .
? i = yi , Ri = ? y j + ? i
? k =i y i ?
Qi
j=1

Имеем
i
1
? [C(R k ) - C(R k-1 )] ? Q k ,
zi = C(R o ) = 0 , C(R n ) = C(Y) .
yi k =1
17


Сравнивать R-механизм обратных приоритетов с обычными
приоритетными механизмами в данном случае не удается, так как
приоритетный механизм с убывающими функциями приоритета не
удовлетворяет условию монотонности. Однако, R-механизм
обратных приоритетов дает весьма серьезные преимущества
агентам с меньшими заявками. А именно, такие агенты платят за
одно и то же количество ресурса меньше, чем агенты с более
высокими заявками. Это следует из соотношения
? i ( y, R ) < ? j ( y, R ) , для всех i > j , R < R j .

Конкурсные механизмы распределения ресурсов.
Эти механизмы составляют особый класс приоритетных
механизмов. Агенты упорядочиваются по величине приоритетов.
Агент с наивысшим приоритетом является в определенном смысле
диктатором. Он получает ресурс в первую очередь. Остальные
агенты получают ресурс в порядке убывания приоритетов.
Распределение затрат при этом возможно различными способами.
Однако должно выполняться следующее условие - затраты агента
могут зависеть только от его заявки и от заявок агентов с более
высоким приоритетом.
Ограничимся описанием R-механизма на основе конкурса
при условии анонимности. В этом случае, агенты упорядочиваются
y 1 < y 2 <... < y n .
по возрастанию заявок. Пусть Обозначим
i
Yi = ? y i . В литературе рассмотрены два механизма распределения
j=1

затрат на основе конкурса [1, 4]. В первом затраты агента i
определяются выражением:
z i = C(Yi ) ? C(Yi ?1 ) , Yo = 0, i = 1, n .
( в случае одинаковых заявок затраты также берутся равными).
18


Во втором механизме:
1
[C( n. y i ) ? C( n. y i ?1 )] .
z i = z i ?1 +
n ? i +1
n

? z i = C(Y) .
Очевидно, в обоих случаях:
i =1

Многоэтапные механизмы распределения затрат.
Пусть C(Y) кусочно-линейная выпуклая функция Y с точками
k = 1, l , C(Y) = C(R k-1 ) + ? k (Y - R k-1 ) ,
излома то есть
Rk,
Y ?[R k-1 , R k ], ? k ? ? k ?1 .
В этом случае естественно трактовать ? k как цену ресурса на
отрезке [R k-1 , R k ] .
Рассмотрим механизмы распределения затрат, в основе
которых лежит поэтапная процедура распределения ресурса. На
первом этапе распределяется ресурс в количестве ? 1 = R 1 по цене
? 1 , на втором - ресурс в количестве ? 2 = R 2 - R 1 по цене ? 2 , и т.д.,
до тех пор, пока на очередном этапе не будет желающих получить
ресурс. На каждом этапе агенты дают заявку S i k на ресурс, который

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


предпочтительнее получать ресурс на ранних этапах. Этот факт еще
больше сближает многоэтапную процедуру распределения затрат с
процедурами распределения ограниченного ресурса. Действительно,
обозначим ?ik оптимальное количество ресурса для i-го агента по

цене ?k. Очевидно, что цель i-го агента на каком-то этапе получить
ресурс в количестве ?ik (тогда на последующих этапах ресурс ему
больше не нужен). Таким образом, игровой анализ многоэтапных
процедур, фактически, распадается на поэтапный анализ процедур
распределения ограниченного ресурса.
Интересной представляется модификация многоэтапных
процедур, в которой агенты сразу сообщают совокупность оценок

{S } количеств ресурсов, которое они желают приобрести по цене
ik

? k . Очевидно, что S i1 > S i 2 > ... > S il в силу выпуклости С(Y) и
вогнутости функций эффекта. Эта модификация привлекательна
тем, что она сглаживает (смягчает) отрицательные тенденции
манипулирования данными (завышения или занижения оценок),
которые могут появляться при применении тех или иных процедур
распределения ресурса (подробнее это свойство будет рассмотрено
ниже).
Двухоценочные механизмы с сообщением оценки эффекта или
эффективности распределения затрат.
В тех случаях, когда орган, распределяющий ресурс (далее
будем называть его центром), имеет возможность получить
? i (yi )
информацию о фактическом эффекте агентов от
использования ресурса y i , распределение затрат может проводиться
на основе двух оценок - требуемого ресурса y i и ожидаемой
эффективности его использования ? i , где под эффективностью
20


понимается отношение эффекта ? i ( y i ) к ресурсу y i . Наличие у
Центра информации о фактическом эффекте позволяет ему
применять систему санкций (штрафов и премий) в случае, когда
ожидаемый (или обещанный агентом) эффект ? i ? y i не совпадает с

фактическим.
Так, в случае линейных санкций, целевая функция агента
принимает вид
f i (y i , ? i )=? i ( y i ) - ? ( ? i y i - ? i ( y i )) - z i ,

где ? - коэффициент штрафа (премий).
Зачастую санкции применяются только в виде штрафов в
случае, когда фактический эффект ниже ожидаемого. В этом случае

?? i ( y i ) - z i , если ? i y i ? ? i ( y i )
fi = ?
?? i ( y i ) - ? (? i y i - ? i ( y i )) - z i , если ? i y i > ? i ( y i )

?
Если настолько велико, что превышение ожидаемого
эффекта над фактическим явно невыгодно агенту, то получаем
случай «сильных штрафов». Как правило, механизмы распределения
затрат, использующие оценки эффективности, устроены таким
образом, что агент заинтересован завысить оценку. При сильных
штрафах такое манипулирование данными невыгодно агентам и
? i (y i )
поэтому сообщаемая оценка равна ? i = .
yi
Все описанные выше механизмы распределения затрат
можно применить и в случае двух оценок. Для этого достаточно
?i (? i )
функции приоритета сделать зависящими от оценки

?i ?i (? i )
эффективности (естественно, что возрастающие

функции ? i ). Для двухоценочных механизмов условие анонимности
21


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

Параметрические механизмы.
Параметрическими мы будем называть механизмы
распределения затрат, в которых агенты сообщают параметры
функции эффекта S=(S1 , S 2 ,..., S n ) , на основе которых центр

y i = ? i (S) .
определяет распределение ресурса На основе
распределения ресурса {y i } определяется распределение затрат
z i = ? i ( y) . Применение параметрических механизмов возможно в
тех случаях, когда центр имеет достаточно точное представление о
параметрическом виде функций эффекта агентов (знает эти функции
с точностью до параметров). Параметрическое представление
функций эффекта будем обозначать ? i ( y i , ri ) , где ri - параметр.
Рассмотрим следующий класс механизмов распределения
затрат.
? (Y) ? Y ? C(Y)
? i ( y) = ? (Y) y i ? .
n
Очевидно,
n
? ? i ( y) = C(Y) .
i =1

Целевая функция агента принимает вид
? (Y) ? Y ? C(Y)
f i = ? i ( y i , ri ) ? ? (Y) ? y i +
n
При большом числе агентов достаточно обоснованным
является предположение о слабом влиянии количества ресурса y i

отдельного агента на общие для всех агентов величины ?(Y) , ? и
С(Y) (гипотеза слабого влияния). Смысл этой гипотезы в том, что
максимизируя свою целевую функцию по y i , агент i не учитывает
22


того, что y i входит в Y. В этом случае оптимальное количество
ресурса для i-го агента удовлетворяет условию
? 'i ( y i , ri ) = ? (Y) , i = 1, n
Если теперь в качестве ?(Y) взять C(Y), то при естественных
условиях вогнутости функции ? i ( y i ) и выпуклости С(Y), получим
оптимальное решение задачи максимизации суммарного эффекта

<< Предыдущая

стр. 3
(из 9 стр.)

ОГЛАВЛЕНИЕ

Следующая >>