Достаточные условия сбалансированности игры центров
v(iS') = max[min ^ЯД;у);0] для всех коалиций, кроме максимальней iGS
ной коалиции TV- для нее v(N) = Gx .
Теорема 2.
Если независимо от номера ieN, min Я( (у)yGA
достигается в одной точке утт := arg min Я( ( у), то игра
yGA
сбалансирована.
Доказательство. По условию теоремы v(S) = тах[^Яг (^тт);0].
iGS
Игра сбалансирована, если выполнено условие (11), то есть если для произвольного сбалансированного покрытия д верно неравенство
ZS(S)-max[ZHi{y^y,0] Преобразуем левую часть этого неравенства: Z 8(S) ¦ тах[?Яг(jmm);0] = ? S(S) ¦ ^Нг{утт) = S^N ieS S^N, ieS E Hj(ymm)>0 jzs = ЦЩутт) ZW< Z Нг{Утт) ^8{S) = ieN SieS, ieN, SieS T. Hj(ymm)>0 ff,Omm)>0 jeS Zтах[Яг(ymm),0] ZW- ieN SieS Ho Z <5= 1 Для всех /, так как 8(S) - сбалансированное SieS покрытие, то есть условие (65) выполнено, если справедливо неравенство Zmax^(Jmin),0] Из вида равновесия (61) для данного случая следует, что VS с N max[min Z #г (j),0] + max[min Z НГ (j),0] < GN . УеА ieS ieN\S Пусть min Ztf, (>') >0 V/ e N . Тогда из (67) следует, что y<=-A ieS GN >minZ^(j) + min Zmin#iOO, и условие (66) УеА ieS УеА ieN\S ieN УеА верно. Предположим теперь, что 3/ е N: min Z^; 00 < 0 • РаССМОТ- ^Л ieS рим коалицию S = {/' е N: Я( (утт) > 0} . Формула (67) для такой коалиции преобразуется к виду Z-^г O-Vn) - GN, то есть ieS Хтах|Я( 0'|Т1||1 ^ Gn, следовательно, неравенство (66) верно. • ieN Если коалиция рассчитывает на средний (среди оптимальных по Парето равновесий) выигрыш, то есть v(.V) = vcn (5"), то кооперативная игра является игрой с постоянной суммой [67], то есть \/S с N v'(.S') + v(N \S) = v(N) . ieN существенной. 66 Пусть теперь коалиция рассчитывает на гарантированный Парето-эффективный выигрыш: v(,V) = vrn(S) = Gs . Приведем несколько вспомогательных результатов. Лемма 4. Для любого сбалансированного покрытия д и произвольных векторов Д е 91™ , i е N. справедливо равенство (68) Е^Е4 = Е4- ScN ieS ieN Доказательство. Порядок суммирования в (68) можно изменить, суммируя сначала по коалициям, содержащим некоторого игрока /, а затем по всем игрокам из N. E^E4 = EEM, = E4EV ScN ieS ieNSieT ieN SieS По определению сбалансированного покрытия, E^.s- = 1 для всех / . SieS Следовательно, Е ^ЕД = ЕД HSs = Е4 • ' ScN ieS ieN SieS ieN Определение 21: Пусть задана функция р:91™ ^911 . Будем говорить, что функция линейно мажорируема в точке А е 91™, если найдется такой вектор В е V.H'". что р(Л) =< А. В > и для любого вектора А'< А (неравенство выполнено в отдельности по каждой из компонент векторов) верно неравенство р(А')<<А\В> } Определение 22: Функция р : 91™ —> 911 называется суперадди-тивной, если для любой пары векторов A,Be 91™ справедливо неравенство р(А) + р(В) < р(А + В) 2 Например, выпуклая и неположительная в нуле функция неотрицательной вещественной переменной супераддитивна. Лемма 5. Если функция р: 91™ —> 911 имеет вид р(А') = q(< А' ,С >), где С е 91™ - вектор с неотрицательными компонентами, a q(.) - супераддитивная функция действительной Угловыми скобками здесь и далее обозначается скалярное произведение векторов. Данное понятие не следует путать с супераддитивностью функции множества (1). переменной, то р(.) линейно мажорируется в любой точке АеМ". Доказательство. Действительно, выберем вектор в = д(< А,С>)с <А,С> Тогда р(А) =< А, В > . Так как q(.) супераддитивна и для любой точки А< А в силу неотрицательности каждой компоненты вектора С < А,С ><< А,С >, то р(А) = q(< А,С >) < < А' С >=< А',В >. < А, С > Лемма 6. Если функция р : 91™ —> 911 сепарабелъна, то есть имеет т вид р{А) = Y.4j((A)j), причем - супераддитивные функции У=1 действительной переменной, то р(.) линейно мажорируется в любой точке А е 91™. Доказательство. Выберем вектор В = т. (A)j Он удовлетворяет определению линейной мажорируемости, по- т скольку р{А) = Z<7j((A).) =< А.В > и, в силу супераддитивности J=1 функций qj{), для произвольной точки А'< А верно неравенство у, 4j((A)j) /]/ ~ 2-, / V" 'J p(A) = ^ Z , '3 (Л), =< А В >. Лемма 7. Если v(S) = />(Z4) > гДе 4 е > 7 е N и р(.) линейно i<=S мажорируется в точке Z4 >т0 игРа сбалансирована. ieN Доказательство. По определению линейно мажорируемой функции найдется такой вектор Be 91™, что /•(Z4) =< Z4>5 > и Л-™ любого вектора А'е 91™, Z4 , г'еЛГ г'еЛГ г'еЛГ справедливо неравенство )<< А,В> . Игра сбалансирована, если для произвольного сбалансированного покрытия верно неравенство (11): X Л) - /КХД)- Положим А'= и увеличим левую SaN iGS iGN iGS часть неравенства по свойству мажорируемой функции: X SsPiZA)^ X Ss ScN iGS ScN iGS ScN iGS X 5, X -Д = X Д • a значит, верна и оценка ScN iGS iGN E SsP(ZA)^ ScN iGS iGN iGN Из леммы 7 следует, что если характеристическая функция удовлетворяет условиям лемм 5 или 6, то игра сбалансирована. Лемма 8. Если затраты агента - выпуклая сепарабельная фун- т кция, то есть с(у) = X0';) • где функции cL(.) - выпуклые неу- J=1 бывающие, а доходы центров - линейные неубывающие по всем компонентам вектора действия функции, то кооперативная игра центров сбалансирована. Доказательство. Линейные функции дохода центров имеют вид Hi (у) =< Ку > 5 т0 есть представляют собой скалярное произведение вектора действия у на вектор коэффициентов Аг. При этом для произвольной коалиции S функция Gs (у) принимает вид Gs{y) = где Ал. Максимум функции Gs(y) по действию у достигается при обращении в ноль всех частных производных этой функции, то есть при (69) (Xs)]=cyj(y) = c](y]), j = \...т . Так как все производные с . (у .) монотонны, из уравнений (69) можно явно выразить оптимальное для коалиции действие у как вектор-функцию от вектора коэффициентов функции дохода: yj({Xs)j) = [с -]-1 ¦). Подставляя это выражение в (62), с учетом (69) получим выражение для характеристической функции, как функции от вектора коэффициентов As.: (70) v(S) = P(XS) := Е^Я^Дс;.]"1^),.)-^.^;.]-1^),.))]. y=i Эта функция сепарабельна по компонентам вектора Я5, таким образом, если каждое из слагаемых вида в (70) представляет собой супераддитивную функцию, то, по лемме 5 характеристическая функция линейно мажорируема, а, следовательно, игра сбалансирована. Функция действительного аргумента супераддитивна, если она неположительная в нуле и выпуклая. Очевидно, что q ¦(0) = с (|с | '(О))- 0 . Покажем, что qj выпукла. Функцию qj(.) можно записать в виде сложной функции: (г (.)): где ^(Я) = [С;]-1(Я). тогда Дифференцируя g}Q по у h имеем g}(у}.) = с}( у}) у} Ё](УJ) = C"I(УJ)YJ +С](У})- Дифференцируя у;(.) по (Я5);, имеем 1 , \ с о ((Я.) )) О' ((Я, ) также ( ц, ^((Я5);)- V; Подставляя полученные функции в выражение для q -(.). имеем: ,/ ((/,» ) (г ((Я,. ))г ((Я,. ) г (г ((Я,, ft ^ ( riv (о ) X (а л \^ ('• » )) (у (йу) )) 1 То есть qj(.) выпукла, если с .(у .((Я5) ¦))> 0 для всех (Av) ,. то есть затраты агента выпуклы, что предполагается условием леммы. • Если функция затрат агента не сепарабельна - лемма 8 неприменима. 70 Тогда для вычисления характеристической функции vrn(S) = v(A5) = max G(y, Xs) := max[< Xs, у > -c(yj\ yeA yeA в предположении, что максимум достигается во внутренней точке множества А допустимых действий агента, необходимо решить систему уравнений (АД=cyj(y), j = \...т, из которой определяется зависимость у = у(А) оптимального вектора действия от вектора коэффициентов А функции дохода произвольной коалиции. Лемма 9. Если для любого А е 91™ решение системы (71) единственно и имеет вид у. = В-у(< А,В >), j = \...т, где В е 91™, а у(.) - неубывающая функция, то игра с характеристической функцией vrn(S) сбалансирована. Доказательство. Покажем, что характеристическая функция vrn(S) в зависимости от вектора коэффициентов As. функции дохода имеет вид vrn{S) = p{ где р(.) - некоторая супераддитивная функция скалярного аргумента. Если характеристическая функция vrn(S) = представима в виде (72), то для любого вектора А е 91™ верно тождество / = 1...™, где G(A):= dAj то есть СКА))' А -- -У(<А,5>)5, , j = \...m. С>Уг Из (71) следует, что второе слагаемое в левой части тождества равно нулю, то есть у . (А) = р' (< А, В >)/i, или, с учетом условия леммы, /(< А, В >) = р'(< А, В >). Таким образом, тождество верно. Очевидно, что если функция у(.) возрастает, то р(.) выпукла. Кроме того, />(0) = -c(j(0)) < 0, то есть р{.) - супераддитивная функция. Значит, по леммам 6 и 7, игра супераддитивна. • Таким образом, если условия леммы 9 выполнены, то для любой пары коалиций их оптимальные планы коллинеарны . Для гладкой функции затрат агента это условие выполняется только в частных случаях, однако, если функция р(.) в (72) строго выпукла, то игра остается сбалансированной, если для произвольной коалиции оптимальное действие у = у(Л) агента лежит в некоторой окрестности прямой у = Bt, t е [0,+со). Следствие 2. Увеличение функции дохода всех центров на константу не влияет на результат лемм 8, 9. Доказательство. Пусть Н^у) = /?( + A, v . Тогда, как легко видеть, характеристическая функция w(iS') полученной игры равна w^S1) = Х^г + (ГДС v'(.V) удовлетворяет условиям лемм). i<=S Обозначим u(S) = ^ht, тогда w(S) = u(S) + v(S). По свойствам iGS характеристических функций [67], если игры u(S) и v(.V) сбалансированы, то сбалансирована и игра w(iS') . Но, по лемме 4 для u(S) сбалансирована, по леммам 8, 9 сбалансирована и v(.V). • Теорема 3. Если функции дохода Ht(y) гладкие, вогнутые и неубывающие, а функция затрат агента удовлетворяет условиям лемм 8 или 9, то игры с характеристическими функциями vri (5"), vr2(S), vril(S) сбалансированы. Доказательство. Для игры vrn(S) характеристическая функция имеет вид v(S) = TlHl(ys)-c(ys), IGS . Так как функции дохода Яг(.) где ys = arg max ?Яг (у) - с(у) уеА гладкие, вогнутые и неубывающие, то для каждой из них существует такой линейный функционал вида ЯДу) =Hj0+ <Аг,у > , Аг е91+, что Нt(yN) = Нt(yN) и для любого действия у верно неравенство Я, (у) > Яг (у) . Рассмотрим игру с характеристической функцией v(S) = ?#,.„+ < > ~c(ys) • iGS iGS Для произвольной коалиции S с TV имеет место неравенство v'(.S') < v(S). кроме того, для коалиции N оно превращается в равенство v(N) = v (N). По известному свойству характеристических функций [67] из сбалансированности игры v (S) следует сбалансированность игры v'(,V). Но из следствия 2, а также леммы 8 следует, что игра v(S) сбалансирована. Значит, сбалансирована и игра v(S). Для произвольной коалиции S с 7V значение характеристической функции vr2 (S) не превышает значения характеристической функции vrn (S) = Gs , так как в случае vr2 (S) шире множество, по которому вычисляется гарантированный результат (все равновесия Нэша, а не только оптимальные по Парето). Для максимальной же коалиции vr2 (N) = vrn (N) = GN . Значит, по тому же свойству характеристических функций, из сбалансиро-ванности игры vrn (S) следует сбалансированность игры vr2 (S). Для vri(S) доказательство аналогично.» Следствие 3. Как видно из доказательства, результат теоремы 3 легко обобщить на еще более широкий класс функций дохода центров, а именно, на все функции дохода, которые можно так аппроксимировать сверху возрастающими линейными функциями, чтобы данные аппроксимирующие функции касалась функций дохода центров в точке yN (плановое действие для максимальной коалиции). • Итак, на основании полученных результатов можно сделать вывод, что для образования максимальной коалиции осторож- ных центров (то есть центров, использующих гарантированный результат для оценки выигрыша) достаточно, чтобы функции их доходов удовлетворяли условиям следствия 3, а затраты агента - условиям леммам 8 или 9. Эти условия выполняются для широкого класса ОС. Если же центры промежуточного уровня более оптимистично настроены на результат переговоров (v(S) = vcn (S)), то кооперация им не нужна, так как переговоры между коалициями дают им то же значение выигрыша, что и переговорный процесс внутри коалиции N, состоящей из всех центров.