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

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

ОГЛАВЛЕНИЕ

Следующая >>

сообщение максимальных заявок. Этот достаточно тривиальный
вывод, кстати, справедлив и для соответствующих систем с
интервальной неопределенностью.
Более интересным представляется случай, когда при различных
значениях R различное число АЭ получает оптимальное количество
ресурса. Однако, этот случай гораздо труднее поддается анализу,
особенно при больших n и m.
Первое, что приходит в голову - использовать классические
результаты исследования механизмов распределения ресурса в
детерминированных активных системах. Например, отыскав
равновесные стратегии АЭ для каждого из значений Rj ? ?, объявить,
что в вероятностной системе равновесной будет стратегия,
получаемая из «детерминированных» усреднением по ?. Или,
например, вычислить ожидаемое значение количества ресурса и
решать дальше детерминированную задачу. Очевидно, что ни один из
этих методов, в общем случае не верен. Но все-таки, использовать
результаты анализа детерминированной задачи можно и нужно,
только более осторожно. Поэтому сделаем небольшое отступление и
обратимся к анализу детерминированной задачи.
Упорядочим все АЭ по возрастанию точек пика:
r1 ? r2 ? r3 ? ... ? rn. (4.6)
Как отмечалось выше, механизмом последовательного
распределения ресурса (затрат) называется такой механизм, в котором
элементы упорядочиваются в порядке возрастания (убывания) заявок
(дохода, затрат, эффективности и т.д.), затем ресурс, равный заявке
первого АЭ, выделяется всем АЭ, далее первый элемент исключается



48
из рассмотрения и оставшийся ресурс распределяется между
остальными элементами и т.д [1, 4].
Для рассматриваемого класса детерминированных механизмов
распределения ресурса справедлив следующий результат (ср. с
характеризацией, приведенной в [4]):
Теорема 4.1. Для любого анонимного механизма распределения
ресурса существует эквивалентный прямой механизм
последовательного распределения ресурса.
Доказательство. Из результатов работы [1] известно, что для
любого механизма из рассматриваемого класса существует
эквивалентный прямой механизм (механизм открытого управления).
Алгоритм построения этого механизма приведен выше. Поэтому
докажем, что для этого механизма существует эквивалентный
механизм последовательного распределения ресурса.
Структура равновесия такова, что все проигравшие элементы
сообщают максимальное количество ресурса. Обозначим P ? I -
множество победителей. Понятно, что в упорядочивании (4.6) при
использовании анонимного механизма элемент, стоящий левее
победителя также является победителем. Тогда если k = k(R) - число
победителей, то P(R) = { 1, 2, ... , k(R) }. Значит, в силу анонимности
механизма (если все АЭ сообщают одинаковые заявки, то все АЭ
получают ресурс в одинаковом количестве):
x? = ri , i = 1, k( R), (4.7)
i

k( R)
? ?
? R ? ? rj ?
? j=1 ?
, i = k( R) + 1, n .
x? = (4.8)
n ? k( R )
i




49
Сконструируем теперь механизм последовательного
распределения, эквивалентный рассмотренному выше. Пусть АЭ
сообщили центру оценки точек пика { ˜ }. Расположим эти оценки в
r i

порядке возрастания:
˜ ? ˜ ? ˜ ? ... ? ˜ . (4.9)
r1 r2 r3 rn
Вычислим n величин
i
w i = ? ˜j + ( n ? 1)˜ , i = 1, n .
r ri
j= 1

Очевидно, wi ? wi+1, причем для любого количества распределяемого
ресурса R либо R < ˜ ? n и победителей нет, либо существует такой
r1

номер q ? 1, n ? 1 , q = q( R) , что wq ? R < wq+1. Возможность q = n

исключается в силу введенной выше гипотезы дефицитности.
Рассмотрим следующий механизм последовательного
распределения ресурса:
?АЭ упорядочиваются в соответствии с (4.9);
?если R ? n ˜ , то всем АЭ выделяется ресурс в количестве ˜ и
r1 r1
первый АЭ исключается из рассмотрения, иначе все получают по R/n
(все АЭ сообщают максимальные заявки и получают строго меньше
оптимального количества) и процедура заканчивается;
?если ( R - n ˜ ) ? (n-1) ( ˜2 - ˜ ), то всем оставшимся АЭ
r1 r r1
добавляется по ( ˜2 - ˜ ) единиц ресурса и второй АЭ исключается из
r r1
рассмотрения, иначе всем добавляется по
R ? nr
˜
1
n?1
и процедура заканчивается;
? и т.д.


50
Число шагов механизма, очевидно, конечно. Более того, он
эквивалентен рассматриваемому выше механизму так как приводит к
распределению ресурса, совпадающему с (4.7)-(4.8), где
?R?? k(R) = q(R).
Отметим, что при использовании анонимных механизмов
существует определенная иерархия элементов - количество ресурса,
получаемое некоторым АЭ, зависит только от предпочтений
элементов, расположенных левее него в упорядочении (4.9), и не
зависит от предпочтений элементов, имеющих большие номера.
Докажем неманипулируемость механизма последовательного
распределения, то есть докажем, что сообщение ˜ = ri , i = 1, n -
ri
равновесие Нэша. Элементы-победители, очевидно, сообщат
достоверную информацию так как они получают абсолютно
оптимальное для себя количество ресурса. Рассмотрим, могут ли
проигравшие ресурс в количестве, меньшем
(получившие
оптимального), поодиночке манипулируя информацией, увеличить
свой выигрыш (значение своей функции предпочтения). В силу
анонимности механизма при сообщении ˜i > ri проигравший АЭ не
r
изменит итогового распределения ресурса. Если же ˜i < ri, то
r
количество выделяемого ему ресурса при той же обстановке может
только уменьшиться. Теорема доказана.
Рассмотрим динамический аналог механизмов
последовательного распределения (см. также [4]). Пусть ? -
количество ресурса, производимое в единицу времени. В каждый
момент времени ресурс делится поровну между всеми АЭ, текущее
количества ресурса которых меньше оптимального. В интервале от
t = 0 до t = t1, где t1 =r1?n/?, все АЭ получают в единицу времени по ?/n.

51
В момент времени t1 количество ресурса, накопленное первым
элементом равно x1(t1)= r1. При t ? (t1, t2] ресурс распределяется
между всеми элементами, кроме первого. При этом
??t n , t ? t 1 ,
?
x 2 ( t) = ?(?t 1 n) + ?( t ? t 1 ) ( n ? 1) , t ? [ t 1 , t 2 ],
?r , t ? t
?2 2

где t2 = t1 + (r2 - r1)?(n - 1)/?, и т.д.
Легко видеть, что время, через которое i-ый АЭ получит
оптимальное для себя количество ресурса, определяется выражением:
wi
ti = , i = 1, n .
?
Ограниченность распределяемого ресурса соответствует в
рассматриваемой динамической модели ограниченности времени.
Если предположить, что t ? T, то за время T успеют получить ресурс в
требуемом количестве первые k(T) элементов, где k определяется из
условия: tk ? T < tk+1, или, что то же самое, wk ? ?T ?wk+1. Обозначая ?T
= R, получаем, что k = q(R).
Отметим конструктивный характер доказательства теоремы 4.2
- для любого анонимного механизма распределения ресурса она
позволяет найти равновесное распределение (k(R) = q(R)) (4.7)-(4.8) и
равновесные заявки:
s? = D, i = k( R), n . (4.10)
i


{s (R)}: ? (s (R), s (R), ... , s ( ( R), D, ... , D) = ri , i = 1, k( R ) .
? ? ? ? (4.11)
k R)
i i 1 2


Следствием теоремы 4.1 является следующий факт:
Теорема 4.2. При фиксированном количестве распределяемого
ресурса все анонимные механизмы эквивалентны.


52
Действительно, окончательное распределение ресурса не
зависит от процедуры ?(?) (от нее, естественно, зависят равновесные
заявки элементов-победителей), а определяется только величинами
(R, {ri}, n). Интересно отметить, что итоговое равновесие не зависит и
от ограничения D (при условии, что механизм удовлетворяет
перечисленным выше свойствам). Это обусловлено тем, что
анонимный механизм характеризуется симметричностью процедуры
планирования и одинаковым для всех АЭ ограничением на заявки.
При изменении (увеличении или уменьшении) величины D итоговое
равновесие не меняется. В механизмах, не удовлетворяющих условию
анонимности, изменение индивидуальных ограничений на заявки
влияет как на равновесные заявки, так и на итоговое распределение
ресурса (даже при симметричной процедуре планирования), то есть в
этом случае выбор ограничений {Di} является одним из возможных
управлений со стороны центра. Целесообразность и эффективность
использования управлений такого рода на сегодняшний день, к
сожалению, малоизученна.
Отдельной задачей, также заслуживающей внимания, является
изучение неманипулируемости анонимных механизмов
распределения ресурса при отказе от гипотезы некооперативного
поведения АЭ. Есть основания предполагать, что эти механизмы
являются коалиционно-неманипулируемыми (ср. с результатами [4]).
Обоснование или опровержение этой гипотезы выходит за рамки
настоящей работы и является задачей будущих исследований.
Зная структуру решения детерминированной задачи для
произвольного (но известного элементам) количества ресурса,




53
вернемся к анализу механизмов распределения ресурса в условиях
неопределенности.
Результат теоремы 4.1 позволяет исключить из рассмотрения
следующий малоинтересный случай (более тонкие оценки приводятся
ниже):
Следствие. Если для некоторого АЭ i ? I ? R ? ? wi > R, то si*
= D.
Приведенное следствие утверждает, что для некоторых АЭ в
случае как интервальной, так и вероятностной неопределенности,
стратегия - сообщать максимальные заявки, может быть доминантной,
независимо от количества распределяемого ресурса. Однако,
наиболее интересные эффекты проявляются в случае, когда
существуют элементы, равновесные заявки которых зависят от
количества распределяемого ресурса.
В случае интервальной неопределенности дело обстоит
достаточно просто:
Теорема 4.3. Если активным элементам известно только
множество возможных будущих значений количества ресурса, то они
сообщат заявки, определяемые в соответствии с (4.10)-(4.11) при R =
R1.
Действительно, наихудшей для i-го АЭ ситуацией (в смысле и
классического принципа гарантированного результата, и
ограниченного принципа гарантированного результата [2, 3]) является
минимальное значение распределяемого количества ресурса, так как с
уменьшением R растут равновесные заявки всех АЭ.
Следствие. Если r1 > R1/n, то в случае интервальной
неопределенности все АЭ сообщат максимальные заявки.


54
Результат следствия вполне соответствует наблюдаемому на
практике явлению: если не исключено, что распределяемое
количество ресурса окажется достаточно маленьким, то все будут
просить по-максимуму.
В случае вероятностной неопределенности структура
равновесия не так проста, как при интервальной неопределенности, и,
интуитивно, должна зависеть от всех элементов множеств ? и ?. На
самом деле, во многих практически важных случаях эта зависимость
несколько проще, чем кажется на первый взгляд:
Теорема 4.4. Если процедура планирования линейна по
количеству распределяемого ресурса, а функции предпочтения
элементов - полиномы, максимальная степень которых не
превосходит l, то равновесные стратегии АЭ зависят только от l
первых моментов распределения ?.
Справедливость утверждения теоремы 4.4 следует из того, что
при вычислении ожидаемой полезности i-го элемента возникают
математические ожидания тех степеней R, коэффициенты при
которых в функции предпочтения отличны от нуля. Следовательно,
если l - максимальная из степеней полиномов {?i}, то в системе (4.5)
фигурируют только первые l моментов.
Результаты теорем 4.2 и 4.4 значительно упрощают задачу
анализа и синтеза реальных анонимных механизмов распределения
ресурса. Так как все анонимные механизмы эквивалентны, то
вряд ли стоит использовать экзотические процедуры планирования -

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

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

ОГЛАВЛЕНИЕ

Следующая >>