Книги по разным темам Pages:     | 1 |   ...   | 13 | 14 | 15 | 16 | 17 |

компоненты этого вектора представляют собой распределение xi xi < ri всего ресурса xT (rT,T ) в распоряжении коалиции между ее (121) fi (xi ) =.

xi ri ri участниками.

114 Такие целевые функции представляют собой модель линей- зависящих от параметра ri) не может гарантировать сбалансироного производства с ограничениями на мощность. Здесь опти- ванность, если не выполнено условие (120). Использование мальным для агентов является количество ресурса ri. выражения (120) в качестве условия сбалансированности при Следствие 4. Если в условиях теоремы 8 производственные отсутствии такой информации можно рассматривать, как функции агентов имеют вид (121), а механизм распределения применение принципа максимального гарантированного резульресурса обладает свойством нулевой заявки, то условие (120) тата, который рекомендует предполагать наихудший случай при является необходимым и достаточным условием сбалансирован- отсутствии информации.

ности игры. К сожалению, большинство используемых на практике Доказательство. Аналогично доказательству теоремы 8 запишем механизмов распределения ресурса не гарантирует сбалансиронеобходимое и достаточное условие непустоты C-ядра (11): ванности игры агентов с произвольными профилями точек пика (122) fi ( yiT ) fi ( yiN ). r=(ri) i N их целевых функций, то есть возможны профили, при T TD iT iN которых условие (120) нарушается.

Воспользуемся частным видом производственных функций Тогда дальнейшее использование принципа МГР для получеагентов. Так как при использовании центром механизма, ния гарантий сбалансированности, предполагающее максимизаобладающего свойством нулевой заявки, произвольная цию левой части неравенства (120) по всем профилям точек пика, коалиция изменением своих заявок может произвольно приводит к неутешительному выводу: гарантировать при уменьшить получаемое ей количество ресурса (см. рис. 8), то заданных условиях сбалансированность игры невозможно. Иначе получаемое коалицией количество ресурса всегда меньше или дело обстоит при наличии у центра дополнительной информации равно чем оптимальное, то есть все yiT ri, и, следовательно, о положении точек пика целевых функций агентов.

можно пользоваться только линейной частью производственной Выше в разделе 3.1 был приведен пример вида подобной функции. Тогда (122) можно записать в виде: информации. Предполагалось, что центр имеет информацию о том, что вектор точек пика ri принадлежит некоторому множеству (123) yiT yiN = R.

T TD iT iN L. В частности, L может представлять собой декартово Как показано при доказательстве теоремы 8, для произвольпроизведение диапазонов Pi возможного изменения индивидуальной коалиции yiT = xT (rT,T ). То есть из (123) следует, что ус ных точек пика, то есть L = P1 P2... Pn.

iT Тогда для того, чтобы узнать, может ли центр на основе ловие сбалансированности принимает вид xT (rT,T ) R. Так T имеющейся информации о положении точек пика (и в отсутствие TD информации о виде целевых функций) гарантировать сбалансирокак это условие получено последовательностью тождественных ванность, нужно производить максимизацию левой части преобразований, оно является необходимым и достаточным. Х неравенства (120) уже по более узкому множеству профилей L.

Таким образом, по крайней мере для механизмов, обладаюПроверка для каждого профиля сбалансированности игры щих свойством нулевой заявки, наихудший с точки зрения сводится к задаче линейного программирования, где необходимо обеспечения сбалансированности игры случай реализуется при максимизировать выбором коэффициентов сбалансированного линейных производственных функциях агентов, представляющих T покрытия выражение xT (rT,T ) при дополнительных огранисобой предельный случай вогнутых производственных функций.

T TD Для вогнутых функций зона сбалансированности будет шире, одчениях сбалансированности коэффициентов (10). Коэффициенты нако центр, не зная точно параметрического вида производственxT берутся из найденной зависимости (см. рис. 8) количества ных функций агентов (то есть не зная функций fi = fi (xi, ri ), ресурса от положения точки пика целевой функции коалиции. В 116 ряде случаев эту вычислительную задачу можно заменить Доказательство. Если точка пика коалиций T и N\T, лежит в алгоритмом проверки ядра по определению, что сводится к области (m, m), то равновесные заявки всех агентов равны R.

поиску решения системы неравенств.

Агенты при этом получают ресурс xi = (R,..., R). Следовательi В случае, когда центру известна параметрическая зависино, условие непустоты C-ядра (120) запишется в виде мость целевых функций агентов, вместо использования (124) (R,..., R) R.

T i огрубленного достаточного условия (120) можно рекомендовать TD iT использование необходимого и достаточного условия в Положим Ai := (R,..., R), тогда, по лемме 4, i соответствии с теоремой Бондаревой.

(125) (R,..., R) R.

i Выполнение этой процедуры для всех агентов должно iN выделить подмножество C множества всех профилей точек пика, Но в левой части (125) стоит общее количество распределяекоторое содержит все профили, для которых игра гарантированно мого ресурса R при заявках агентов si = R. При этом неравенство сбалансирована.

(125) обращается в тождество, и C-ядро не пусто. Х Если множество L допустимых точек пика полностью Условие этого следствия выполняется, например, если все содержится в этом множестве, значит при любых допустимых точки пика ri R / n. При этом Pi = [R/n, +).

профилях центр может рассчитывать на гарантированное образоСледствие 6. Если есть такой агент k, что для всех коалиций T, вание максимальной коалиции и на все связанные с этим содержащих его, оптимальная точка r целевых функций коалиций преимущества.

T и N\T лежит в области (m, c) (см. рис. 7), а для остальных Как уже было выяснено ранее, множество всех профилей коалиций - в области (c, m) то C-ядро не пусто.

точек пика целевых функций агентов при которых игра Доказательство. Разобьем множество D собственных коалиций сбалансирована, может быть найдено для фиксированных на два подмножества:

механизма и количества агентов. Эту процедуру можно проделать DI = {T : (rT, rN \T ) (c, m)}, DII = {T : (rT, rN \T ) (m,c)} один раз и затем пользоваться полученными результатами при По условию следствия, D=DIDII. На рис. 7 видно, что если оценке сбалансированности игр при различных возникающих в некоторая коалиция T принадлежит DI, то коалиция N\T жизни случаев информированности центра. Однако даже принадлежит DII. Коалиции TDI - диктаторские, то есть однократное вычисление вышеописанных множеств может стать получаемое такими коалициями количество ресурса xT совпадает вычислительной задачей большой сложности, не говоря уже о с их точкой пика rT. Следовательно, коалиция N\T получит ресурс плохой наглядности результатов уже при n > 3. Поэтому в объеме xN \T = R - rT.

представляет интерес конкретизация формулы (120), которая Условие непустоты ядра (120) в данном случае запишется позволяла бы получить простые и понятные условия, характеритак:

зующие принадлежность некоторых простых информационных множеств L к множеству C (где игра сбалансирована). (126) T rT + T (R - rN \T ) R.

TDI TDII Рассмотрим подобные ограничения, которые гарантируют Так как rN \T = - rT, то сбалансированность игры при попадании профилей точек пика целевых функций агентов в условия нижеописанных следствий.

rT + (R - rN ) = rT + (R - + rT ) = T T \T T T Следствие 5. Если для всех коалиций T оптимальная точка r TDI TDII TDI TDII.

коалиций T и N\T, лежит в области (m, m) (см. рис. 7) то C-ядро rT + (R - ) T T игры не пусто. TD TDII 118 Заметим, что случай произвольно малых эффективностей По лемме 4 для Ai=ri, верно равенство rT =. По T TD всех агентов, кроме одного, был наихудшим для эффективности определению теоремы, коалиции TDII и только они содержат управления при некооперативном рассмотрении. В кооперативагента k. Тогда условие TDII можно переписать как T: kT. Но, ном же случае эффективность управления системой таких агентов по определению сбалансированного покрытия (10), для любого k максимальна и равна 1.

имеем = 1. Значит, На основании вышесказанного можно утверждать, то внесе T T:kT ние возможности коалиционных взаимодействий положительно (127) rT + (R - ) = + R - = R. Х T T влияет именно на слабые стороны некооперативного распределеTD TDII ния ресурса.

Для класса механизмов распределения, обладающих свойстРаспределение ресурса между тремя агентами вом нулевой заявки, предположения, необходимые для выполнения условий данного следствия, выглядят так:

Проиллюстрируем результаты, полученные для n агентов в Pi = [0, R / n] для i k, Pk = [R / n,+).

случае, если агентов всего трое. Предположим, что механизм анонимен и обладает свойством нулевой заявки, а целевые фунТаким образом, сформулированные в виде следствий 5 и результаты позволяют дать центру рекомендации по подбору xi кции агентов можно записать в виде fi = ri f (обобщенные состава агентов на основании имеющейся о них информации. Как ri уже отмечалось, сбалансированность игры приводит к производственные функции Кобба-Дугласа). Здесь f одинакова максимальной эффективности управления. Поэтому можно для всех агентов и обладает следующими свойствами:

рекомендовать центру подбирать состав агентов таким образом, (128) f (0) = 0, f (1) =1, f '(x) > 0 при x <1, f '(x) < 0 при x >1, f ''(x) < 0.

чтобы все агенты имели сравнительно большие потребности в ресурсе, то есть представляли собой не диктаторов. Заметим, Примером подобной функции является f (x) = 2x - x2.

что ограничения на положение точек пика следствия 0, x = Лемма 12. При игра агентов сбалансирована.

представляют собой ограничения снизу. Как показано в разделе f (x) = 1(x) := 1, x > 3.2, наличие такой информации у центра не влияло на Доказательство. Условие сбалансированности (11) для таких эффективность механизма в некооперативной модели. Зато такая производственных функций агентов имеет вид: rS rN.

информация оказывается чрезвычайно полезной для повышения S SN эффективности управления в кооперативном случае.

Непосредственно применяя лемму 4 для m = 1, получаем резульТакже игра сбалансирована, если есть единственный агент, тат леммы. Х производственные возможности которого значительно превышаФункция f (x) = 1(x) является поточечным пределом послеют производительность остальных агентов (то есть все агенты, довательности производственных функций вида Кобба-Дугласа кроме него, являются диктаторами). При этом неэффективные + агенты продают ресурс (то есть меняют ресурс на долю в (x1/ k). Таким образом, можно утверждать, что для произвольk =дележе) эффективному агенту для переработки. Несмотря на ного вектора точек пика производственных функций существуют некоторую несправедливость такой ситуации с точки зрения такие вогнутые производственные функции агентов, имеющие эффективного агента, она приводит к максимальной производимаксимумы в этих точках, что игра агентов будет сбалансирована, тельности системы, как и всегда при образовании максимальной однако гарантировать сбалансированность для произвольных коалиции.

120 вогнутых производственных функций можно только если вектор Действительно, если вероятность реализации того или иного точек пика удовлетворяет условиям следствий 5 или 6. значения точки пика целевой функции агента представлена Построим зоны сбалансированности и несбалансированности равномерным распределением, отношение площади области сбалансированности C к полной площади симплекса даст игры на симплексе r1 + r2 + r3 = для некоторого значения (см.

вероятность того, что профиль точек пика агентов гарантирует рис. 10).

образование максимальной коалиции. При этом интересным (0,, 0) представляется проследить, хотя бы качественно, как меняется площадь области C при варьировании дефицита в системе (параметр R/ ). Рис. 11 демонстрирует зоны сбалансированности и несбалансированности для разных степеней дефицита в (0, R/3, R/3) ( R/3, R/3, 0) системе. Стрелки показывают рост дефицита, то есть уменьшение параметра R/.

(R/3, -R/3, 0) (0, R/3, -R/3) ( R/3, 0, R/3) (, 0, 0) (0, 0, ) (R/3, R/3, 0) Рис. 10. Зоны сбалансированности и несбалансированности игры На рис. 10 зоны, где в соответствии с результатами следствий 5 и 6 игра гарантированно сбалансирована, изображены светлым тоном, а зоны, где в зависимости от конкретного вида производственных функций агентов игра может быть как сбалансирована, так и нет - темным.

Рис. 11. Динамика зон пустого и непустого C-ядра при росте дефицита Как видно из рис. 10, центральная и угловые зоны симплекса соответствуют сбалансированным играм. Данный рисунок посКак видно из рис. 11, при росте общей потребности в ресурсе троен для некоторого фиксированного значения (равного центральная зона увеличивается в размерах, угловые зоны примерно 1.3R). Если центр знает только общую степень сохраняют свой размер. При больших (относительно имеющегося дефицита в системе, описываемую величиной R/, то сравнение количества ресурса R) потребностях основную площадь занимает площади областей с пустым и непустым C-ядром может помочь центральная зона.

центру в оценке вероятности реализации максимальной коалиции.

Точный расчет зон сбалансированных и несбалансированных игр с помощью вычислительной модели для параболических 122 производственных функций показал, что при росте уровня Механизм постоянных приоритетов дает каждому агенту дефицита зона несбалансированных игр монотонно уменьшается, фиксированное количество ресурса xi вне зависимости от заявок пропадая с некоторого момента. агентов. Коэффициенты Ai соответствуют относительной важности агентов для центра.

3.5. Синтез сбалансированных механизмов распределения Этот механизм представляет собой предельный случай для нестрого монотонных механизмов, в котором промежутков Выше были исследовано коалиционное взаимодействие агенстрогого возрастания количества получаемого ресурса в тов при механизмах распределения ресурса, обладающих зависимости от заявки нет вообще.

свойствами монотонности по заявке агента и непрерывности по Сбалансированность игры для механизма постоянных всем переменным.

приоритетов может быть показана и из других соображений.

Pages:     | 1 |   ...   | 13 | 14 | 15 | 16 | 17 |    Книги по разным темам