Влияние информированности центра на эффективность управления
п
(104) К = ^ .
max Х/;(уг)
i=i
Гарантированная эффективность К0 есть нижняя грань эффективности К по изменению параметров модели - вида производственных функций агентов, в частности, положения точек пика производственных функций.
В классической для теории активных систем постановке задачи распределения ресурса предполагается, что центр не имеет никакой информации о точках пика целевых функций агентов, то есть точки пика, с его точки зрения, могут принимать любое значение от нуля до бесконечности. Очевидно, что дополнительная информация о положении точек пика, если бы она имелась у центра, не может ухудшить эффективности управления. Эта дополнительная информация может, например, иметь вид неравенств гг < гг < гг¦ , ограничивающих точку пика гг в некотором
диапазоне (интервальная неопределенность [34]). Тогда центр может запретить агентам подачу заявок, лежащих вне этого диапазона.
В более общем виде информацию о точках пика целевых функций агентов, которой может обладать центр, можно описать подмножеством L положительного сегмента пространства R" (представляющего собой множество возможных профилей точек пика при отсутствии у центра дополнительной информации). Тогда центр может дополнительно потребовать от агентов сообщения только таких заявок, вектор которых принадлежит L.
Следующие результаты показывают влияние интервальной неопределенности различного вида на эффективность механизма распределения ресурса.
Лемма 11. Для произвольного непрерывного механизма прямых приоритетов гарантированная эффективность
Г0=т1п{хг(Д,...,Д)}/Д,
i
если о целевых функциях агентов известно только, что они вогнутые одно пиковые.
Доказательство.
Наихудший случай реализуется, когда отношение эффективности использования ресурса агентами в реальности и в идеальном случае минимально, то есть производственные функции агентов, получающих ресурс в результате игры, должны быть сколь угодно малы по сравнению с производственными функциями агентов, получающих ресурс при оптимальном распределении. Тогда наихудшей будет ситуация, когда только один из агентов будет иметь относительно большую эффективность переработки ресурса, остальные же - произвольно малую. Тогда в идеале почти весь ресурс должен получить этот высокоэффективный агент, в реальности же он делится на основании заявок, а малоэффективные агенты могут быть чрезвычайно ресурсоемкими. Наихудший случай реализуется, когда они забирают максимум ресурса. Так как рассматривается механизм прямых приоритетов, это соответствует максимальным заявкам «неэффективных» агентов. Тогда эффективность К для набора таких агентов запишется в видеК = — ' ' " , где / - номер «эффектив-
/J(min [rt,R])
ного» агента.
Здесь первый элемент под знаком минимума в числителе соответствует случаю, когда «эффективный» агент является диктатором, а второй - когда он является «не диктатором». Первый случай не интересен при рассмотрении гарантированного результата, так как эффективность управления в этом случае равна 1. То есть мы должны предполагать, что «эффективный» агент - «не диктатор». Тогда по свойствам «не диктаторов» его заявка должна быть равна R. Соответственно, чтобы получить максимальный знаменатель, следует предположить, что точка
пика целевой функции этого агента больше, чем имеющееся количество ресурса R, что является еще более сильным условием чем «недиктаторство».
Тогда выражение для эффективности преобразуется к виду
fMR,...^)])
К = - „ \ * / /
"Ч / / \ \ > R Г X.
Рис. б. Производственная функция «эффективного» агента
Центр же не знает, какой из агентов эффективен, поэтому может оказаться, что это наиболее «дискредитированный» (при не анонимном механизме распределения) агент.
При этомэффективность механизма К = niin( /¦ (хг (R,..., R)) / /,' (II)). Для
i
вогнутых производственных функций минимум этого выражения достигается в линейном случае, то есть для производственных функций вида fjiXj) = а{х{.
Действительно, представим произвольную вогнутую функцию в виде линейной и положительной функции ср, как показано
т)
R
на рис. 6: ft(xt) =
хг+<р(хг ). Тогда эффективность можно
записать в виде
К =
. Так как для строго вогнутой
ftWxJR + fpiXt) _ хг <р(хг)
т) R т)
функции^, <р > 0 для всех точек хг е (0,i?), то минимум этого вы-
ражения достигается при <р= 0, то есть именно в линейном случае. В результате гарантированная эффективность
К0 = тт{хг (i?,...,R)}/R, что в точности равно (105). •
i
Заметим, что гарантированная эффективность максимальна для анонимных механизмов и равна 1 / п .
Теорема 6. Для монотонных механизмов прямых приоритетов наличие у центра информации вида /' < /'. ieN не влияет на
эффективность механизма, определяемую формулой (105), а при наличии у центра дополнительной информации вида rf < /' гарантированная эффективность
(107) К0=тш{хД,...,7„)}/11.
i
Доказательство Для механизмов прямых приоритетов заявки агентов всегда не меньше требуемого им количества ресурса rt, поэтому ограничения снизу не увеличивают реальной информированности центра.
Для ограничений сверху вида rf < /' доказательство повторяет до-казательство леммы 11с учетом ограничений на заявки агентов. • Результат теоремы 6 используется ниже при сравнении влияния информированности центра на эффективность управления в кооперативной и некооперативной моделях.