Книги по разным темам Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 17 |

Если для построения характеристической функции используДействительно, из (54) следует, что при реализации одного ется гарантированный результат с разрешенным блефом, то из равновесий С-типа наихудшее для коалиции равновесие реалиv(S) = max[min Hi ( y);0] для всех коалиций, кроме максималь yA зуется при = HS (y0) - GS. Тогда гарантированный выигрыш iS S ной коалиции N - для нее v(N) = GN.

коалиции S будет равен GS независимо от реализуемого действия y.

Теорема 2. Если независимо от номера i N, min Hi (y) Применимость условия f = 0 (при непустой области С-равyA новесий) обусловлена тем, что для любого равновесия К-типа оддостигается в одной точке ymin := arg min Hi (y), то игра yA на из коалиций или оба сразу могут изменять свою функцию стисбалансирована.

мулирования, не уменьшая своего выигрыша, но увеличивая выигрыш противника, до тех пор, пока не будет реализовано одно из Доказательство. По условию теоремы v(S) = max[ Hi (ymin );0].

iS равновесий С-типа. Поэтому при доброжелательности по отношеИгра сбалансирована, если выполнено условие (11), то есть нию к противникам реализация таких равновесий более вероятна.

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

неравенство Коалиция может более оптимистично оценивать результаты 64 Пусть теперь коалиция рассчитывает на гарантированный (65) (S) max[ Hi ( ymin );0] GN.

SN iS Парето-эффективный выигрыш: v(S) = vГП (S) = GS. Приведем Преобразуем левую часть этого неравенства:

несколько вспомогательных результатов.

(S) max[ Hi (ymin );0] = (S) Hi (ymin ) = Лемма 4. Для любого сбалансированного покрытия и произSN iS SN, iS H ( ymin )>j вольных векторов Ai m, iN, справедливо равенство jS (68) Ai = Ai.

= Hi (ymin ) (S) Hi ( ymin ) (S) = S SN iS iN iN S:iS, iN, S:iS H ( ymin )>0 Hi ( ymin )>j Доказательство. Порядок суммирования в (68) можно изменить, jS суммируя сначала по коалициям, содержащим некоторого игрока max[Hi ( ymin ),0] (S).

i, а затем по всем игрокам из N.

iN S:iS Ai = Ai S.

Ai = Но (S) =1 для всех i, так как (S) - сбалансированное S S SN iS iN S:iT iN S:iS S:iS По определению сбалансированного покрытия, = 1 для всех i.

покрытие, то есть условие (65) выполнено, если справедливо S S:iS неравенство Следовательно, Ai = Ai S = Ai. Х S (66) max[Hi ( ymin ),0] GN.

SN iS iN S:iS iN iN Определение 21: Пусть задана функция p : m 1. Будем Из вида равновесия (61) для данного случая следует, что + (67) S N max[min Hi ( y),0] + max[min Hi ( y),0] GN.

говорить, что функция линейно мажорируема в точке A m, + yA yA iS iN \S если найдется такой вектор B m, что p(A) =< A, B > и для Пусть min Hi ( y) > 0 i N. Тогда из (67) следует, что yA iS любого вектора A' A (неравенство выполнено в отдельности по GN min Hi ( y) + min Hi ( y) Hi (y), и условие (66) min каждой из компонент векторов) верно неравенство yA yA yA iS iN \S iN p(A') < A', B >.верно.

Определение 22: Функция p : m 1 называется супераддиПредположим теперь, что i N : min Hi (y) < 0. Рассмот- + yA iS тивной, если для любой пары векторов A, B m справедливо + рим коалицию S = {i N : Hi (ymin ) > 0}. Формула (67) для такой неравенство p(A) + p(B) p(A + B).коалиции преобразуется к виду Hi ( ymin ) GN, то есть Например, выпуклая и неположительная в нуле функция iS неотрицательной вещественной переменной супераддитивна.

max[Hi (ymin ),0] GN, следовательно, неравенство (66) верно. Х iN Лемма 5. Если функция p : m 1 имеет вид + Если коалиция рассчитывает на средний (среди оптимальных p(A') = q(< A',C >), где C m - вектор с неотрицательными + по Парето равновесий) выигрыш, то есть v(S) = vСП (S), то компонентами, а q(.) - супераддитивная функция действительной кооперативная игра является игрой с постоянной суммой [67], то есть S N v(S) + v(N \ S) = v(N). Такие игры не сбалансиро Угловыми скобками здесь и далее обозначается скалярное произведение ваны [67], если v({i}) v(N), то есть если игра является векторов.

iN Данное понятие не следует путать с супераддитивностью функции множества существенной.

(1).

66 переменной, то p(.) линейно мажорируется в любой точке Игра сбалансирована, если для произвольного сбалансированного покрытия верно неравенство (11):

A m.

+ p( Ai ) p( Ai ). Положим A'= Ai и увеличим левую S Доказательство. Действительно, выберем вектор SN iS iN iS q(< A,C >) часть неравенства по свойству мажорируемой функции:

B = C.

< A,C > p( Ai ) < Ai, B > =< Ai, B >. По лемме S S S SN iS SN iS SN iS Тогда p(A) =< A, B >. Так как q(.) супераддитивна и для Ai = Ai, а значит, верна и оценка S любой точки A' A в силу неотрицательности каждой компоненSN iS iN ты вектора С < A',C >< A,C >, то p( Ai ) < Ai, B >= p( Ai ). Х S q(< A,C >) SN iS iN iN p(A') = q(< A',C >) < A',C >=< A', B >. Х Из леммы 7 следует, что если характеристическая функция < A,C > удовлетворяет условиям лемм 5 или 6, то игра сбалансирована.

емма 6. Если функция p : m 1 сепарабельна, то есть имеет + Лемма 8. Если затраты агента - выпуклая сепарабельная фунm m вид p(A') = q ((A') ), причем q j(.) - супераддитивные функции j j кция, то есть c(y) = c (y ), где функции cj(.) - выпуклые неу j j j=j=действительной переменной, то p(.) линейно мажорируется в бывающие, а доходы центров - линейные неубывающие по всем любой точке A m. компонентам вектора действия функции, то кооперативная игра + центров сбалансирована.

q ((A) ) j j Доказательство. Выберем вектор B = ( ).

Доказательство. Линейные функции дохода центров имеют вид j=1...m (A) j Hi (y) =< y >, то есть представляют собой скалярное произведеi Он удовлетворяет определению линейной мажорируемости, поние вектора действия y на вектор коэффициентов. При этом i m скольку p(A) = q ((A) ) =< A, B > и, в силу супераддитивности для произвольной коалиции S функция GS (y) принимает вид j j j=GS (y) =<, y > -c(y), S функций qj(.), для произвольной точки A' A верно неравенство где - вектор коэффициентов функции дохода коалиции.

S m m q ((A) ) j j p(A') = q ((A') ) (A') =< A' B >. Х Максимум функции GS (y) по действию y достигается при j j j (A) j=1 j=j обращении в ноль всех частных производных этой функции, то Лемма 7. Если v(S) = p( Ai ), где Ai m, i N и p(.) линейно есть при + iS (69) ( ) = c' j ( y) = c'j (y ), j = 1...m.

S j y j мажорируется в точке Ai, то игра сбалансирована.

iN Так как все производные c'j (y ) монотонны, из уравнений j Доказательство. По определению линейно мажорируемой (69) можно явно выразить оптимальное для коалиции действие y функции найдется такой вектор B m, что как вектор-функцию от вектора коэффициентов функции дохода:

p( Ai ) =< Ai, B > и для любого вектора A'm, A' Ai, + y (( ) ) = [c'j ]-1(( ) ). Подставляя это выражение в (62), с j S j S j iN iN iN справедливо неравенство p(A') < A', B >. учетом (69) получим выражение для характеристической функции, как функции от вектора коэффициентов :

S 68 m Тогда для вычисления характеристической функции (70) v(S) = p( ) := [( ) [c'j ]-1(( ) )- c ([c'j ]-1(( ) ))].

S S j S j j S j vГП (S) = v( ) = max G(y, ) := max[<, y > -c(y)] S S S j=yA yA Эта функция сепарабельна по компонентам вектора, в предположении, что максимум достигается во внутренней точке S таким образом, если каждое из слагаемых вида множества А допустимых действий агента, необходимо решить систему уравнений q (( ) ) := ( ) [c'j ]-1(( ) )- cj([c'j ]-1(( ) )) j S j S j S j S j (71) ( ) = c' j ( y), j = 1...m, S y j в (70) представляет собой супераддитивную функцию, то, по лемме 5 характеристическая функция линейно мажорируема, а, из которой определяется зависимость y = y( ) оптимального следовательно, игра сбалансирована.

вектора действия от вектора коэффициентов функции дохода Функция действительного аргумента супераддитивна, если произвольной коалиции.

она неположительная в нуле и выпуклая. Очевидно, что Лемма 9. Если для любого m решение системы (71) единст+ q (0) = -c ([c'j ]-1(0)) 0. Покажем, что qj выпукла.

j j венно и имеет вид y = Bj (<, B >), j = 1...m, где B m, а (.) j + Функцию qj(.) можно записать в виде сложной функции:

- неубывающая функция, то игра с характеристической функцией g (y (.)):= q (( ) )= c'j(y (( ) ))y (( ) )- c (y (( ) )), j j j S j j S j j S j j j S j vГП (S) сбалансирована.

где y ( ) = [c'j ]-1( ).

j Доказательство. Покажем, что характеристическая функция vГП (S) в зависимости от вектора коэффициентов функции ' ' S тогда q'j(( ) )= g'j'(y (( ) ))[y'j(( ) )] + g'j(y (( ) ))y'j(( ) ).

S j j S j S j j S j S j дохода имеет вид Дифференцируя g j(.) по y j, имеем g'j(y )= c'j' ( y )y, (72) vГП (S) = p(<, B >), j j j где p(.) - некоторая супераддитивная функция скалярного g'j' (y ) = c'j''(y )y + c'j' ( y ). Дифференцируя y j(.) по ( )j, имеем S j j j j аргумента.

c'j''(y (( ) )) j S j ' Если характеристическая функция также y'j(( ) )=.

S j S j c'j'(y (( ) )), y'j(( ) )= vГП (S) =<, y( ) > -c(y( )) c'j'(y (( ) )) j S j S S S j S j представима в виде (72), то для любого вектора m верно Подставляя полученные функции в выражение для q'j'(.), + тождество имеем:

G( ) p'(<, B >)Bj, j = 1...m, где G( ) :=<, y( ) > -c(y( )), q'j'(( ) )= {c'j''(y (( ) ))y (( ) )+ c'j'(y (( ) ))}c (y (( ) )) S j j S j j S j j S j '' j j j S j то есть '' c'j''(y (( )) c (y (( ) )) j S j j j S j m - c'j'(y (( ) ))y (( ) )c (y (( )) )) = = yi ( ) ci ( y( )) j S j j S j '' 3 y ( ) + - p'(<, B >)Bj, j = 1...m.

c'j'(y (( ) )) c'j'(y (( ) )) j S j j j S j j S j j i yi i=j ' То есть q (.) выпукла, если c'j(y (( ) )) 0 для всех ( ), j j S j S j Из (71) следует, что второе слагаемое в левой части тождестто есть затраты агента выпуклы, что предполагается условием ва равно нулю, то есть y ( ) p'(<, B >)Bj или, с учетом j леммы. Х условия леммы, (<, B >) p'(<, B >). Таким образом, Если функция затрат агента не сепарабельна - лемма тождество верно.

неприменима.

70 Очевидно, что если функция (.) возрастает, то p(.) выпукла.

где yS = arg max Hi ( y) - c(y). Так как функции дохода Hi(.) iS Кроме того, p(0) = -c(y(0)) 0, то есть p(.) - супераддитивная yA функция. Значит, по леммам 6 и 7, игра супераддитивна. Х гладкие, вогнутые и неубывающие, то для каждой из них сущес~ Таким образом, если условия леммы 9 выполнены, то для твует такой линейный функционал вида Hi (y) = Hi0 + <, y >, i любой пары коалиций их оптимальные планы коллинеарны1. Для ~ m, что Hi (yN ) = Hi (yN ) и для любого действия y верно гладкой функции затрат агента это условие выполняется только в i + ~ частных случаях, однако, если функция p(.) в (72) строго выпукла, неравенство Hi (y) Hi (y).

то игра остается сбалансированной, если для произвольной Рассмотрим игру с характеристической функцией коалиции оптимальное действие y = y( ) агента лежит в ~(S) v = Hi0 + <, yS > -c( yS ).

i некоторой окрестности прямой y = Bt, t [0,+). iS iS Для произвольной коалиции S N имеет место неравенство Следствие 2. Увеличение функции дохода всех центров на ~(S) v(S) v, кроме того, для коалиции N оно превращается в константу не влияет на результат лемм 8, 9.

~(N) Доказательство. Пусть Hi (y) = hi + y. Тогда, как легко видеть, равенство v(N) = v.

i характеристическая функция w(S) полученной игры равна По известному свойству характеристических функций [67] из ~(S) сбалансированности игры следует сбалансированность игры v w(S) = hi + v(S) (где v(S) удовлетворяет условиям лемм).

~(S) iS v(S). Но из следствия 2, а также леммы 8 следует, что игра v Обозначим u(S) = hi, тогда w(S) = u(S) + v(S). По свойствам сбалансирована. Значит, сбалансирована и игра v(S).

iS Для произвольной коалиции S N значение характеристихарактеристических функций [67], если игры u(S) и v(S) сбаланческой функции vГ 2(S) не превышает значения характеристичесированы, то сбалансирована и игра w(S). Но, по лемме 4 для ской функции vГП (S) = GS, так как в случае vГ 2 (S) шире u(S) сбалансирована, по леммам 8, 9 сбалансирована и v(S). Х множество, по которому вычисляется гарантированный результат Теорема 3. Если функции дохода Hi(y) гладкие, вогнутые и (все равновесия Нэша, а не только оптимальные по Парето). Для неубывающие, а функция затрат агента удовлетворяет условиям максимальной же коалиции vГ 2(N) = vГП (N) = GN. Значит, по лемм 8 или 9, то игры с характеристическими функциями vГ1(S), тому же свойству характеристических функций, из сбалансироvГ 2 (S), vГП (S) сбалансированы.

ванности игры vГП (S) следует сбалансированность игры vГ 2 (S).

Доказательство. Для игры vГП (S) характеристическая функция Для vГ1(S) доказательство аналогично.Х имеет вид Следствие 3. Как видно из доказательства, результат теоремы v(S) = Hi ( yS ) - c(yS ), легко обобщить на еще более широкий класс функций дохода iS центров, а именно, на все функции дохода, которые можно так аппроксимировать сверху возрастающими линейными функциТакая ситуация характерна для предприятий химической промышленноями, чтобы данные аппроксимирующие функции касалась фунсти, где из одного вида сырья вырабатываются m видов продукции. При этом кций дохода центров в точке yN (плановое действие для объем производства каждого вида готовой продукции из единицы сырья жестко максимальной коалиции). Х определяется технологическим вектором B. Тогда точка оптимального плана Итак, на основании полученных результатов можно сделать y = Bj (<, B >) определяется эффективностью <, B > использования j вывод, что для образования максимальной коалиции осторожпродукции, произведенной из единицы сырья.

72 ных центров (то есть центров, использующих гарантированный Методов воздействия на функционирование системы у ВР результат для оценки выигрыша) достаточно, чтобы функции их может быть много, но в рамках данной работы рассмотрим лишь доходов удовлетворяли условиям следствия 3, а затраты агента - один из них - внутрифирменное налогообложение, когда условиям леммам 8 или 9. Эти условия выполняются для устанавливается ставка отчислений в пользу ВР с доходов i широкого класса ОС.

Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 17 |    Книги по разным темам