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

центром значения своего стимулирования в точке y0 агент Доказательство. Очевидно, что система стимулирования выберет действие yk, что приносит k-му центру меньший ( ~i ( y), ( y)) реализует точку y0. Действительно, выигрыш -i выигрыш, что следует из того, что ( y) = 0 не являлась его k агента в точках yi ( i {0} N ) остался прежним, во всех же наилучшим ответом в исходной обстановке. Следовательно, прочих точках не увеличился, то есть, по предположению 3, ( ~i ( y), ( y)) является -равновесием Нэша. Х -i действие y0 останется выбором агента. Выигрыши всех центров Иначе говоря, для любого -равновесия Нэша можно найти не изменились, так как значение их функций стимулирования в равновесие, реализующее ту же точку, что и исходное, дающее точке y0 не изменилось. Необходимо теперь доказать, что новый всем центрам те же выигрыши, но в котором функция вектор стратегий будет -равновесием Нэша. Для этого нужно стимулирования каждого центра отлична от нуля не более чем в n показать, что стратегии центров являются наилучшими (с точках.

точностью до ) ответами на новую обстановку.

емма 3. Для произвольного набора чисел y0, Ф1, Е, Фn, такого, Стратегия ( y) центра i была одним из наилучших (с i что существует -равновесие Нэша, реализующее действие y0 и точностью до ) ответов на обстановку ( y) (так как исходный -i дающее i-му центру выигрыш Фi, i N, найдется -равновесие вектор стратегий был -равновесием Нэша). Его выигрыш при Нэша со стратегиями центров вида (34), реализующее действие yиспользовании стратегии (34) не изменился, то есть эта стратегия и дающее i-му центру выигрыш Фi.

является наилучшим с точностью до ответом на ту же Доказательство производится n-кратным применением леммы 2Х обстановку ( y).

-i Необходимость использования -равновесий Нэша в формуРассмотрим теперь произвольный центр с номером k ( k i ).

ировках лемм 2 и 3 обусловлена тем, что функцию ( ) в По следствию 1 при фиксированной обстановке ( y) все значе-k некоторых случаях можно определить так, что множество ния его целевой функции достигаются на множестве его стратеравновесий Нэша (но не множество -равновесий) будет пусто.

гий вида (33), кроме того, одним из его -наилучших ответов Однако справедливо следующее замечание:

является функция P( ( y0 ), y0 ) (так как исходный вектор k Замечание 1. Можно положить = 0 и считать -равновесия, в стратегий является -равновесием Нэша). Поскольку функция которых стратегии центров имеют вид (34) обычными стимулирования (34) i-го центра уменьшилась по сравнению со равновесиями Нэша, дополнительно указывая, что агент при 56 прочих равных условиях должен выбирать действие y0. То есть (40) - c( y ) = f > 0 j {0} N, ij j переход к рассмотрению равновесий Нэша требует введения iN предположения о том, что при прочих равных условиях агент (41) max[Hi ( yi );Gi - f ] Hi ( y0 ) - Hi (y0), i выбирает лопределенное центрами действие y0.

j (42) 0 Hi (y ) - min[Hi (y ); Hi (y0) - ] i, j N j i j i Если равновесные стратегии центров имеют вид (34), то равновесие Нэша можно полностью описать набором n + 1 Левые неравенства в (42) должны выполняться только если действий y0, y1, Е, yn и значениями функций стимулирования всех требуется выполнение предположения 2 запрета блефа.

центров в n точках (всего n2 + n + 1 чисел). Доказательство. Введем обозначения:

Таким образом, если интересоваться (что достаточно для (43) f-j = kj - c(y ) - выигрыш агента в точке y, i j j дальнейшего изложения) только выбираемым агентом действием kN \{i} y0 и выигрышами {Фi}iN всех центров в равновесии, то достаj N {0} при условии, что стимулирование этого действия i-м точно рассматривать только равновесия, в которых все центры центром равно нулю: (y ) = 0.

i j используют стратегии вида (44) f-i = max[ max f-j ;0] - значение целевой функции, которое 0 j i (35) (y) = P(, y0) + P(, y ), jN {0} i i i j jN i-й центр должен обеспечить агенту в некоторой точке y при k i где 0, = 0 i N, k {0} N.

фиксированных стратегиях других центров для того, чтобы агент i i выбрал это действие.

Опишем множество равновесий Нэша, в которых стратегии Набор стратегий ( y) вида (35) будет равновесием Нэша, всех центров имеют вид (35). Введем обозначения:

i (36) Gi := max{Hi ( y) - c( y)}, i N, реализующим (в смысле Замечания 1) точку y0, если стратегия yA каждого центра будет наилучшим ответом на стратегии выигрыш i-го центра, который он может получить в одиночку остальных центров. Для стратегий центров вида (35) неравенство (будем считать, что Gi > 0, i N, то есть у каждого из центров (31) можно записать в виде условий (для каждого центра i N ):

есть допустимая функция стимулирования, при которой агент не (45) = f-i - f-i i отказывается от игры);

- условие наименьших затрат на стимулирование при реализации (37) f := - c( y0) 0, iдействия y0. Это же условие обеспечивает выгодность для агента iN участия в игре.

выигрыш агента в равновесии.

Теорема 1. Все равновесия Нэша (в смысле замечания 1), в (46) Hi (y0) + f-0 Hi (y ) + f-j j N, i j i которых стратегии центров имеют вид (35), можно разбить на два (47) Hi (y0) + f-0 Hi ( y) - c( y) y A типа: равновесия С-типа (лсотрудничество), в которых f = 0 (то i есть центры не переплачивают агенту за выбор нужного им - условия выгодности реализации действия y0 для i-го центра, как действия y0), определяемые условиями:

по сравнению с действиями y (46), так и по сравнению с j (38) = c( y0 ), c( y ) j N, i0 ij j прочими действиями y A (47).

iN iN j (48) 0 Hi (y ) - балансовое ограничение (если требуется i j (39) 0 Hi ( y0) - Gi для каждого центра i N ;

i выполнение предположения 2, то это неравенство должно и равновесия К-типа (лконкуренция), определяемые системой условий 58 j выполняться для всех действий yj, j N {0}, в противном ( j**) < ( j) - = f. Но, так как max ( j) = f, следовательно i** jN случае - только для y0).

j ( j) - < ( j**) = f. Получили противоречие, следовательно, Так как неравенство (47) должно выполняться для всех i** действий y, его можно записать так:

(52) верно.

Из (52) следует, что Hi (y0) - Gi (см. определение Gi, формула (36)).

i j i N, j N {0} f -[ - c(y )] = f - f-j =.

j k j i i Из формул (37), (45) следует, что, так как + f-0 = f, то i i kN \{i} i N f-i = f.

Тогда балансовое ограничение (48) можно записать в виде Рассмотрим сначала случай f = 0 (С-равновесие). Из (45) 0 j (53) Hi (y0 ) - Hi (y ) - i, j N, что в совокупности с i j i следует, что j требованием неотрицательности доказывает условие (42). Так (49) = c( y0 ), то есть доказано условие (38). i iiN i как = 0, можно написать, что Hi (y0) - Hi ( yi ) i N, В i i Условия выгодности реализации действия y0 для i-го центра сочетании с (47) это утверждение доказывает условие (41). Х (46), (47) можно записать в виде Из доказательства теоремы 1 следует, что условия (38)-(42) 0 j (50) 0 Hi ( y0) - Gi, положив при j 0 равными нулю, i i являются необходимым и достаточным условием того, что набор так как они не влияют на выигрыши центров в равновесии, то стратегий вида (35) является равновесием Нэша.

есть доказано (39).

Для исследования кооперации центров в рассматриваемой Пусть теперь f >0 (К- равновесие). Тогда (45) преобразуется к задаче потребуется искать равновесия Нэша игры двух центров.

виду Определим множество равновесий Нэша для этого случая.

(51) i N f = f-i = max f-j = max[ - c( y ) - ]. Равновесия С-типа можно записать следующим образом:

kj j ij i jN jN kN 0 0 (54) c(y0) - H2( y0) + G2 H1(y0 ) - G1, = c(y0) -.

1 2 Из этой формулы следует, что Эта область не пуста при G1 + G2 max[H1(y0) + H2( y0) - c(y0 )].

(52) f = - c( y ) j N {0}, а не только для j = 0, как kj j y0A kN Множество равновесий К-типа задается условиями следует из формулы (37).

0 0 1 (55) + - c( y0) = - c(y1) = - c( y2) = f > 0, 1 2 2 Действительно, обозначим ( j) := - c(y ). Надо доказать, j k j kN (56) max[H1(y1),G1 - f ] H1( y0) - H1( y0), что j N ( j) = f. Предположим, что j* : ( j*) = max ( j) > f. max[H2( y2),G2 - f ] H2(y0) - H2( y0 ), jN i* (57) 0 H1( y2) - c(y2) - f H1( y0) -, Возьмем i* = j*, тогда, так как = 0, выполнено неравен- i* 0 H2(y1) - c(y1) - f H2( y0) -.

j ство max[ ( j) - ] = ( j*) > f. Но, по формуле (51), i* jN Имея эти выражения для множества равновесий Нэша игры j центров, можно переходить к рассмотрению их коалиционного i max[ ( j) - ] = f. Таким образом, max ( j) = f.

i jN jN взаимодействия.

Пусть теперь j** : ( j**) = min ( j) < f. Тогда, из формулы jN (51) для i** = j** следует, что найдется такой j, что 60 Кооперативное взаимодействие центров Для построения характеристической функции необходимо в ОС с распределенным контролем взять одно из равновесий (или несколько, дающих коалиции S одинаковый выигрыш) за основу, то есть предположить, что Для исследования возможностей кооперации центров в центры, присоединяясь к коалиции S и оценивая перспективу соврассматриваемой игре построим характеристическую функцию местных действий, рассчитывают именно на этот результат.

v(S), ставящую в соответствие каждой коалиции суммарный Механизм выбора того или иного равновесия зависит от условий выигрыш, на который могут рассчитывать ее участники, играя решаемой прикладной задачи. Рассмотрим некоторые возможные совместно. Будем считать, что характеристическая функция варианты.

определяется как равновесный по Нэшу выигрыш коалиции S в Одним из общепринятых методов оценки выигрыша является игре с коалицией N\S, состоящей из всех остальных центров.

принцип максимального гарантированного результата [19], Тогда задача исследования игры состоит в том, чтобы определить, когда в качестве оценки берется наихудший из возможных какие коалиции будут образованы, и каким образом доход коалиисходов.

ций будет распределен между их участниками.

1. Гарантированный результат в игре с разрешенным блефом. В Построение функции v(S) можно разбить на следующие этапы:

игре, где блеф разрешен (то есть не требуется выполнения 1. Определение целевой функции коалиций S и N\S и множеств предположения 2), всегда найдется равновесие К-типа, в котором их стратегий.

выигрыш коалиции S vГ1(S) = max[min HS (y);0]. Это следующее yA 2. Построение множества равновесий Нэша игры коалиций S и N\S.

равновесие:

3. Выбор одного из равновесий в качестве основы для вычисле0 ния характеристической функции.

= HS (y0) - max[min HS ( y);0], = S N \S yA В данной задаче целевая функция коалиции S имеет вид:

= HN \S ( y0) - max[min HN \S ( y);0], (58) ФS (y,( (y))iS ) = Hi (y) - (y) = HS (y) - (y), i i S yA iS iS N \S S (61) = f ( y0) + c(yN \S ), = f ( y0) + c( yS ), где HS (y) = Hi ( y), (y) = (y).

S N \S S i iS iS yS = arg min HS (y), yN \S = arg min H ( y), N \S Соответственно, для коалиции N\S имеем: yA yA (59) ФN \S (y, ( (y))iN \S ) = H (y) - (y).

i N \S N \S y0 = arg max[HS (y0) + H (y0) - c(y0)], N \S yA Для такой игры двух лиц множество равновесий Нэша где f(y0) - выигрыш агента в точке y0.

описывается условиями (54)-(57). Это множество достаточно Иначе говоря, если блеф разрешен, то у каждой коалиции обширно и состоит из равновесий двух типов - C и K. Наличие есть возможность угрозой в точке yS загнать противников в равновесий С-типа может интерпретироваться как возможность точку наименьшего дохода.

совместной работы для центров. Пустота множества равновесий 2. Гарантированный результат в игре с запрещенным блефом. Из С-типа говорит о принципиальной невозможности кооперации (57) следует, что f min[HS (yN \S ) - c(yN \S ); H ( yS ) - c(yS )].

центров. Поскольку нас интересует случай кооперации центров, N \S будем считать, что для произвольной коалиции S выполнено Тогда на основании формулы (56) можно записать условие на ФS:

неравенство ФS max[HS (yS );GS - HS (yN \S ) + c(yN \S );GS - HN \S (yS ) + c(yS )].

(60) GS + GN \S GN Для расчета гарантированного результата необходимо найти и зона равновесий С-типа не пуста. минимум правой части этого выражения по всевозможным равновесиям. Этот минимум достигается при 62 * * * * * переговоров, рассчитывая не на наихудший их исход, а, напри(62) GS = HS (yS ) + H ( yS ) - c(yS ) = H (yS ) - c(yS ), N \S N мер, на среднее значение выигрыша. При непустой области yN \S = arg max[HS (y) - c(y)], C-равновесий и реализации действия (63) среднее значение выигyA * * рыша vСП (S) = 0.5(GS + GN - GN \S ).

и равен vГ 2(S) = max[HS ( yS );0], где yS определяется из Завершая рассмотрение способов построения характеристиуравнения (62).

ческой функции, отметим, что во всех случаях выигрыш максиОчевидно, что vГ 2(S) vГ1(S).

мальной коалиции v(N) = GN.

Другим способом сужения множества равновесий Нэша Для целей управления особенно важны условия, при которых является выделение среди них оптимальных по Парето ситуаций.

возможно объединение всех центров в максимальную коалицию Действительно, выбираемая точка y0 в равновесиях вида (54) N. При этом все они действуют как один игрок с целевой является по сути дела результатом некоторых переговоров функцией между коалициями S и N\S. Результаты же переговоров обычно не (64) ФN (.) = Hi (y) - (y).

доминируются по Парето [53, 80, 81, 85]. То есть эффективны по i iN iN Парето решения, реализующие действие Необходимым и достаточным условием устойчивости (63) yN := Arg max GN (y) = Arg max[HS (y) + HN \S (y) - c(y)].

максимальной коалиции является условие сбалансированности yA yA кооперативной игры (11). Проверка условия сбалансированности 3. Гарантированный результат по равновесиям, оптимальным по произвольной кооперативной игры сводится к задаче линейного Парето. Если область равновесий С-типа не пуста, то есть программирования. Интересным представляется, однако, справедливы неравенства (60), достаточно рассматривать только нахождение просто интерпретируемых достаточных условий равновесия С-типа. Тогда из неравенства (54) следует, что сбалансированности игры (то есть достаточных условий гарантированный результат коалиции S vП1(S) = GS. К этому же устойчивости коалиции из всех центров).

результату приводит и более слабое, чем оптимальность по Парето, ограничение на равновесие, а именно, лусловие взаимной Достаточные условия сбалансированности игры центров благожелательности f = 0.

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