Достаточное условие сбалансированности игры
ных на анализе только положения точек пика целевых функций агентов.
Теорема 8. Если для любого сбалансированного покрытия Z 8тхт (.rT,T) Доказательство. Подставляя в критерий сбалансированности игры (11) значение характеристической функции (111), имеем: (П4) Z ^ZCO^Z/fe)- T^N ieT ieN Заменим местами порядок суммирования так же, как это было сделано при доказательстве леммы 4: Z ЦЗтМУ^^ТМуш) ¦ ieN TieT ieN В этой сумме фигурируют только собственные коалиции. Для любой вогнутой функции fi справедливо свойство [42]. Vxk(k = l..M), VSk > 0: Z<5*: = 1 Z$kf(xk) - /(Z'xk) По определению сбалансированного покрытия (10), Z^r = 1 TieT для любого агента /, то есть для произвольного агента / можно записать: Ц8Т/г(у1Т)< ft( ?ST -ylT). TieT TieT Отсюда следует, что неравенство (115) можно огрубить следующим образом: z Z^j^Z/^Z^r). ieN TieT ieN TieT Если обозначить Yt := ZSTylT , TieT T:=Zi;- = ZZ STyIT, ieN ieNTieT то достаточное условие сбалансированности примет вид: ИМУш)- ieN ieN Заметим, что, по определению ут, Z Угг = хт (гт ¦ ^ ) • т0 есть ieT компоненты этого вектора представляют собой распределение всего ресурса хт(гт,Т) в распоряжении коалиции между ее участниками. 114 Тогда, проводя замену порядка суммирования (аналогично процедуре, описанной в доказательстве леммы 4) в (117), получим Y = X Ц$тУгт = 1А1>гт = Т.8тхт(гт,Т). iGNTiGT TeD isT TeD To есть левая часть неравенства (118) представляет собой, по сути, выигрыш максимальной коалиции N при некотором распределении между ее участниками ресурса в количестве Y. Значит, если Y < R, то, даже если распределение Yt окажется оптимальным распределением ресурса между участниками максимальной коалиции, все равно будет выполняться неравенство X /I ) - X./,'0',v), так как правая часть есть ieN ieN результат оптимального распределения большего количества ресурса R. Поскольку это неравенство - достаточное условие сбалансированности, то сбалансированность игры будет следовать и из условия Y < R, то есть для любого сбалансированного покрытия xT(rT,T) Если это условие не выполняется для некоторого набора {профиля) точек пика гг целевых функций агентов, то найдутся такие вогнутые функции с максимумами в этих точках, что построенная на этих целевых функциях игра будет несбалансированной. Покажем, что для механизма обладающего «свойством нулевой заявки» доказанное достаточное условие является необходимым и достаточным, если производственные функции агентов имеют вид: fx, X, < Г: f1(xi) = \ [Гг Хг^Гг Такие целевые функции представляют собой модель линейного производства с ограничениями на мощность. Здесь оптимальным для агентов является количество ресурса гг. Следствие 4. Если в условиях теоремы 8 производственные функции агентов имеют вид (121), а механизм распределения ресурса обладает «свойством нулевой заявки», то условие (120) является необходимым и достаточным условием сбалансированности игры. Доказательство. Аналогично доказательству теоремы 8 запишем необходимое и достаточное условие непустоты С-ядра (11): E^ECOv^ECOv)- TeD ieT ieN Воспользуемся частным видом производственных функций агентов. ЕЯгЕяг^Е^Д- TeD ieT ieN Как показано при доказательстве теоремы 8, для произвольной коалиции X У я = хт (''г- О • То есть из (123) следует, что ус- ieT ловие сбалансированности принимает вид ^8TxT(rT ,Т) < R . Так TeD как это условие получено последовательностью тождественных преобразований, оно является необходимым и достаточным. • Таким образом, по крайней мере для механизмов, обладающих «свойством нулевой заявки», наихудший с точки зрения обеспечения сбалансированности игры случай реализуется при линейных производственных функциях агентов, представляющих собой предельный случай вогнутых производственных функций. Для вогнутых функций зона сбалансированности будет шире, однако центр, не зная точно параметрического вида производственных функций агентов (то есть не зная функций fi = ft (хг, rt), зависящих от параметра гг) не может гарантировать сбалансированность, если не выполнено условие (120). Использование выражения (120) в качестве условия сбалансированности при отсутствии такой информации можно рассматривать, как применение принципа максимального гарантированного резуль-тата, который рекомендует предполагать наихудший случай при отсутствии информации. К сожалению, большинство используемых на практике механизмов распределения ресурса не гарантирует сбалансированности игры агентов с произвольными профилями точек пика /'=(/',),. у их целевых функций, то есть возможны профили, при которых условие (120) нарушается. Тогда дальнейшее использование принципа МГР для получения гарантий сбалансированности, предполагающее максимизацию левой части неравенства (120) по всем профилям точек пика, приводит к неутешительному выводу: гарантировать при заданных условиях сбалансированность игры невозможно. Выше в разделе 3.1 был приведен пример вида подобной информации. Предполагалось, что центр имеет информацию о том, что вектор точек пика гг принадлежит некоторому множеству L. В частности, L может представлять собой декартово произведение диапазонов Р, возможного изменения индивидуальных точек пика, то есть L = 1\ хР2 х...хРп. Тогда для того, чтобы узнать, может ли центр на основе имеющейся информации о положении точек пика (и в отсутствие информации о виде целевых функций) гарантировать сбалансированность, нужно производить максимизацию левой части неравенства (120) уже по более узкому множеству профилей L. Проверка для каждого профиля сбалансированности игры сводится к задаче линейного программирования, где необходимо максимизировать выбором коэффициентов дт сбалансированного покрытия выражение ^дтхт(гт,Т) при дополнительных о грани- TgD чениях сбалансированности коэффициентов (10). Коэффициенты хт берутся из найденной зависимости (см. рис. 8) количества ресурса от положения точки пика целевой функции коалиции. В ряде случаев эту вычислительную задачу можно заменить алгоритмом проверки ядра «по определению», что сводится к поиску решения системы неравенств. В случае, когда центру известна параметрическая зависимость целевых функций агентов, вместо использования огрубленного достаточного условия (120) можно рекомендовать использование необходимого и достаточного условия в соответствии с теоремой Бондаревой. Выполнение этой процедуры для всех агентов должно выделить подмножество С множества всех профилей точек пика, которое содержит все профили, для которых игра гарантированно сбалансирована. Если множество L допустимых точек пика полностью содержится в этом множестве, значит при любых допустимых профилях центр может рассчитывать на гарантированное образование максимальной коалиции и на все связанные с этим преимущества. Как уже было выяснено ранее, множество всех профилей точек пика целевых функций агентов при которых игра сбалансирована, может быть найдено для фиксированных механизма и количества агентов. Эту процедуру можно проделать один раз и затем пользоваться полученными результатами при оценке сбалансированности игр при различных возникающих в жизни случаев информированности центра. Однако даже однократное вычисление вышеописанных множеств может стать вычислительной задачей большой сложности, не говоря уже о плохой наглядности результатов уже при п>Ъ. Поэтому представляет интерес конкретизация формулы (120), которая позволяла бы получить простые и понятные условия, характеризующие принадлежность некоторых простых информационных множеств L к множеству С (где игра сбалансирована). Рассмотрим подобные ограничения, которые гарантируют сбалансированность игры при попадании профилей точек пика целевых функций агентов в условия нижеописанных следствий. Следствие 5. Если для всех коалиций Т оптимальная точка г коалиций Т и N\T, лежит в области (m, m) (см. рис. 7) то С-ядро игры не пусто. Доказательство. Если точка пика коалиций Т и N\T, лежит в области (m, т), то равновесные заявки всех агентов равны R. Агенты при этом получают ресурс хг = 7Г( (R..... R). Следовательно, условие непустоты С-ядра (120) запишется в виде X8TI1ni(R,...,R) Положим At := яД/С... R), тогда, по лемме 4, 1Х(Д,...,Д)<Д. ieN Но в левой части (125) стоит общее количество распределяемого ресурса R при заявках агентов Sj = R. При этом неравенство обращается в тождество, и С-ядро не пусто. • Условие этого следствия выполняется, например, если все точки пика rt > R/n. При этом /', = [R/n, +оо). Следствие 6. Если есть такой агент к, что для всех коалиций Т, содержащих его, оптимальная точка г целевых функций коалиций Т и N\T лежит в области (m, с) (см. рис. 7), а для остальных коалиций - в области (с, т) то С-ядро не пусто. Доказательство. Разобьем множество D собственных коалиций на два подмножества: А ={Т '¦ (rT,rmT)e(c,m)}, Dn = {Т : (rT,rmT) е (m,с)} По условию следствия, D=D^jDn. На рис. 7 видно, что если некоторая коалиция Т принадлежит Z)/, то коалиция М7- принадлежит Du. Коалиции /е/)/ - диктаторские, то есть получаемое такими коалициями количество ресурса хт совпадает с их точкой пика гт. Следовательно, коалиция М7- получит ресурс в объеме xN\T = R- гт. Условие не пустоты ядра (120) в данном случае запишется так: Z$TrT+ ZST(R~rNXT) Так как rmT = р - rT , то Y^8TrT + Т,8т(К~гют) = Ц8тгт + (R ~ Р + гт) = TeD, TeDu TeD] TeD,, ^$тгт +(R~P) TeD TeD,, По лемме 4 для Ai=rh верно равенство X8тгт = р. По TGD определению теоремы, коалиции T Для класса механизмов распределения, обладающих «свойством нулевой заявки», предположения, необходимые для выполнения условий данного следствия, выглядят так: Р1=[0,Р/п]для1Фк, Pk=[R/n,+оо). Таким образом, сформулированные в виде следствий 5 и 6 результаты позволяют дать центру рекомендации по подбору состава агентов на основании имеющейся о них информации. Как уже отмечалось, сбалансированность игры приводит к максимальной эффективности управления. Поэтому можно рекомендовать центру подбирать состав агентов таким образом, чтобы все агенты имели сравнительно большие потребности в ресурсе, то есть представляли собой «не диктаторов». Заметим, что ограничения на положение точек пика следствия 5 представляют собой ограничения снизу. Как показано в разделе 3.2, наличие такой информации у центра не влияло на эффективность механизма в некооперативной модели. Зато такая информация оказывается чрезвычайно полезной для повышения эффективности управления в кооперативном случае. Также игра сбалансирована, если есть единственный агент, производственные возможности которого значительно превышают производительность остальных агентов (то есть все агенты, кроме него, являются диктаторами). При этом неэффективные агенты «продают» ресурс (то есть меняют ресурс на долю в дележе) эффективному агенту для переработки. Несмотря на некоторую несправедливость такой ситуации с точки зрения эффективного агента, она приводит к максимальной производительности системы, как и всегда при образовании максимальной коалиции. Заметим, что случай произвольно малых эффективностей всех агентов, кроме одного, был наихудшим для эффективности управления при некооперативном рассмотрении. В кооперативном же случае эффективность управления системой таких агентов максимальна и равна 1. На основании вышесказанного можно утверждать, то внесение возможности коалиционных взаимодействий положительно влияет именно на слабые стороны некооперативного распределения ресурса.