Построение множества равновесий Нэша игры центров
Далее значком «°» обозначается стратегия агента, при которой он отказывается от игры. Также для краткости будем
обозначать (<7г (y))ieN => у* тот факт, что вектор стратегий
*
(<7г (>>))feAr реализует действие агента У , то есть, что
ч^(<т) max[ X °г (У) - c(j)] ^
(30) / =
v '' геЫ
max[X<7!(j)-c(>')]<0.
У<=-А ieN
Решением игры центров будем считать набор е-равновесных по Нэшу ситуаций. Напомним, что е-равновесием Нэша называется такой вектор стратегий а = (<7г (>')), v, что для любого центра / и любой стратегии <7г (у)
фг (у), <Т_г (у)D - Фг (Т(<7)) < ? , гда^Су) = (<т,Су))^0 [60,65].
Определение е-равновесия Нэша при е = 0 переходит в определение равновесия Нэша.
Введем обозначение для функций стимулирования, отличных от нуля только в одной точке:
= ^
Лемма 1. Пусть (о,(y))iGN - произвольный вектор стратегий центров. Тогда для центра / существует стратегия (функция стимулирования) вида (32), которая при заданной обстановке о ,(у) = (о . 0')); у ; / дает i-му центру тот же выигрыш, что и
исходная стратегия <7г (у).
Доказательство. Достаточно взять стратегию /-го центра
д1{у) = Р{а1{у),у),
где (<тг (>')), => у*. При таком изменении стимулирования множество действий, доставляющих максимум целевой функции агента может только сузиться и, по предположению 3, агент выберет то же действие, что и при исходном векторе стратегий.
Так как сг( (_у ) = О", (_у ), то выигрыш /-го центра не изменился. • Следствие 1. Для любого центра / при фиксированной обстановке <7_j(y) любое достижимое с помощью произвольной стратегиизначение его целевой функции Ф, достижимо и с помощью стратегии вида (33). •
Лемма 2. Пусть (с,(y))iGN - е-равновесие Нэша игры центров, приводящее к выбору агентом действия у0, и выигрыш центра / в равновесии равен Фг. Тогда центр / может в одиночку изменить свою функцию стимулирования <7г (у) на функцию вида (34) д1(у)=Р(а1(у0),у0)+
jsN\{i}
где \>j находится из условия (д . (у) = 0, <7 , (у)) => у .. и полученный набор стратегий (<т((у). с ,(у)) будет е-равновесием Нэша, реализующим ту же точку у0, причем выигрыши всех центров не изменятся.
Доказательство. Очевидно, что система стимулирования (&г (у), <7_!(>>)) реализует точку у„. Действительно, выигрыш агента в точках у, (i е {0} U А') остался прежним, во всех же прочих точках не увеличился, то есть, по предположению 3, действие уо останется выбором агента. Выигрыши всех центров не изменились, так как значение их функций стимулирования в точке уо не изменилось. Необходимо теперь доказать, что новый вектор стратегий будет е-равновесием Нэша. Для этого нужно показать, что стратегии центров являются наилучшими (с точностью до е) ответами на новую обстановку.
Стратегия сг ( у) центра / была одним из наилучших (с
точностью до е) ответов на обстановку <7_г (у) (так как исходный
вектор стратегий был е-равновесием Нэша). Его выигрыш при использовании стратегии (34) не изменился, то есть эта стратегия является наилучшим с точностью до е ответом на ту же обстановку (у) .
Рассмотрим теперь произвольный центр с номером к (к ^ /). По следствию 1 при фиксированной обстановке о_к (у) все значения его целевой функции достигаются на множестве его стратегий вида (33), кроме того, одним из его е-наилучших ответов является функция Р{ок(у0), у0) (так как исходный вектор
стратегий является е-равновесием Нэша).
Поскольку функция стимулирования (34) /-го центра уменьшилась по сравнению со 56своим исходным значением во всех точках, кроме у. , j е {0} U N ,
а стратегии остальных центров не изменились, то и в новой ситуации центру к выгодна реализация действия у0.
В то же время, в новой ситуации к-й центр не может уменьшить значение своей функции стимулирования в точке у0. Действительно, в исходной ситуации выбор к-м центром стратегии Р(ак,у0), где ак(у0) <ак(у0) приводит к реализации
точки _уд., то есть равнозначен выбору стратегии ок (у) = 0 . В новой ситуации равновесия значение целевой функции агента в точке ук не изменилось (так как не изменилось суммарное стимулирование в этой точке). Значит, при уменьшении к-м центром значения своего стимулирования в точке уо агент выберет действие у^, что приносит к-му центру меньший выигрыш, что следует из того, что ок (у) = 0 не являлась его наилучшим ответом в исходной обстановке. Следовательно, (Si (у). о , (у)) является е-равновесием Нэша. •
Иначе говоря, для любого е-равновесия Нэша можно найти е- равновесие, реализующее ту же точку, что и исходное, дающее всем центрам те же выигрыши, но в котором функция стимулирования каждого центра отлична от нуля не более чем в п точках.
Лемма 3. Для произвольного набора чисел у0, Ф\, ..., Ф„, такого, что существует е-равновесие Нэша, реализующее действие у0 и дающее /-му центру выигрыш Фг, ieN, найдется е-равновесие Нэша со стратегиями центров вида (34), реализующее действие у„ и дающее /-му центру выигрыш Фг .
Доказательство производится «-кратным применением леммы 2» Необходимость использования е-равновесий Нэша в формулировках лемм 2 и 3 обусловлена тем, что функцию *+Ч<7) в некоторых случаях можно определить так, что множество равновесий Нэша (но не множество е-равновесий) будет пусто. Однако справедливо следующее замечание:
Замечание 1. Можно положить е = 0 и считать е-равновесия, в которых стратегии центров имеют вид (34) обычными равновесиями Нэша, дополнительно указывая, что агент при
57
прочих равных условиях должен выбирать действие у0. То есть переход к рассмотрению равновесий Нэша требует введения предположения о том, что при прочих равных условиях агент выбирает «определенное центрами» действие у0.
Если равновесные стратегии центров имеют вид (34), то равновесие Нэша можно полностью описать набором п + 1 действий Jo, Ji, • • •, Уп и значениями функций стимулирования всех центров в п точках (всего п2 + п + 1 чисел).
Таким образом, если интересоваться (что достаточно для дальнейшего изложения) только выбираемым агентом действием jo и выигрышами {Ф(}( v всех центров в равновесии, то достаточно рассматривать только равновесия, в которых все центры используют стратегии вида
ai(y) = P(a?,y0)+ZP(a!,yj),
jeN
где of >0,о/ =0V/e7V,?e{0}UTV.
Опишем множество равновесий Нэша, в которых стратегии всех центров имеют вид (35).
Введем обозначения:Gi := тах{/7г (у) - с(у)}, ieN,
yeA
выигрыш /-го центра, который он может получить «в одиночку» (будем считать, что G, >0, ieN, то есть у каждого из центров есть допустимая функция стимулирования, при которой агент не отказывается от игры);
/:=1>г0-сО,0)>0,
ieN
выигрыш агента в равновесии.
Теорема 1. Все равновесия Нэша (в смысле замечания 1), в которых стратегии центров имеют вид (35), можно разбить на два типа: равновесия С-типа («сотрудничество»), в которых /= 0 (то есть центры не переплачивают агенту за выбор нужного им действия jo), определяемые условиями:
Z ieN ieN 0 < of < Я( (y0) - Gt для каждого центра ieN; и равновесия К-типа («конкуренция»), определяемые системой условий S igN msx\Hi {yi); Gt - f \ < H; (yn) - a" < Hj (yn). 0 < Hj {yj) - aj < min[i/. {yj); (y0) - of ] V/JeTV Левые неравенства в (42) должны выполняться только если требуется выполнение предположения 2 «запрета блефа». Доказательство. Введем обозначения: /¦' = О"/ - с(_у,) - выигрыш агента в точке у .. keN\{i} jeN U {0} при условии, что стимулирование этого действия 7-м центром равно нулю: <7( (у ,) = 0 . / = max[ max / '' :() | - значение целевой функции, которое JGN U{0} i-й центр должен обеспечить агенту в некоторой точке у при фиксированных стратегиях других центров для того, чтобы агент выбрал это действие. Набор стратегий <7,(у) вида (35) будет равновесием Нэша, реализующим (в смысле Замечания 1) точку у0, если стратегия каждого центра будет наилучшим ответом на стратегии остальных центров. Для стратегий центров вида (35) неравенство (31) можно записать в виде условий (для каждого центра ieN): (Т,° =/_,.-/4 условие наименьших затрат на стимулирование при реализации действия у0. Это же условие обеспечивает выгодность для агента участия в игре. Н,(у0) + /°>Н,(у;) + Д VjeN, Hi (у0) + > Hi (у) - с(у) VуеА условия выгодности реализации действия у0 для /-го центра, как по сравнению с действиями у ¦ (46), так и по сравнению с прочими действиями у е А (47). 0 < а/ < Н1(у /) - балансовое ограничение (если требуется выполнение предположения 2, то это неравенство должно выполняться для всех действий / е N U {0} , в противном случае - только для у0). Так как неравенство (47) должно выполняться для всех действий у, его можно записать так: Hi (Jo) ~ °f - Gj (см. определение Gt, формула (36)). Из формул (37), (45) следует, что, так как of +/!]=/, то VieN /_,.=/. Рассмотрим сначала случай /= 0 (С-равновесие). Из (45) следует, что X°f = с(Уо) ¦ т0 есть доказано условие (38). ieN Условия выгодности реализации действия у0 для /-го центра (46), (47) можно записать в виде 0 < of < Я(( уп) -С7(. положив о/ при 0 равными нулю, так как они не влияют на выигрыши центров в равновесии, то есть доказано (39). Пусть теперь/>0 (К- равновесие). Тогда (45) преобразуется к виду V/ е N / = /_,. = max Д = шах[ -с(У].)~о/]. ksN Из этой формулы следует, что / = Y.(Tk~c(yJ ) V/' g TV ^ {0} , а не только для 7 = 0, как keN следует из формулы (37). Действительно, обозначим (p(j):= ~С(У]) ¦ Надо доказать, keN что V/ е N cp(j) = / . Предположим, что 3/": ср( / ) = та\<р( /) > / . jeN Возьмем /'* = f. тогда, так как ог» =0, выполнено неравенство max[ jeN ' V/ тах|ф( /) - о/ | = / . Таким образом, max <р( /) = / . jeN jeN Пусть теперь 3/**: (p{j**) = min (p{j) < f . Тогда, из формулы jeN (51) для /** = следует, что найдется такой j, что 60 (p{j) - <7/«» < (p{j**) = f . Получили противоречие, следовательно, верно. Из (52) следует, что V/e7V,7e7VU{0} /-[ Yo; с(г )| / / о . keN\{i} Тогда балансовое ограничение (48) можно записать в виде Я, (у(|) - of > Я, (у;) - О"/ \/i,j eN, что в совокупности с требованием неотрицательности <7/ доказывает условие (42). Так как <7- = 0, можно написать, что Я( (j0) - of > Я( () V/ е TV, В сочетании с (47) это утверждение доказывает условие (41). • Из доказательства теоремы 1 следует, что условия (38)-(42) являются необходимым и достаточным условием того, что набор стратегий вида (35) является равновесием Нэша. Для исследования кооперации центров в рассматриваемой задаче потребуется искать равновесия Нэша игры двух центров. Определим множество равновесий Нэша для этого случая. Равновесия С-типа можно записать следующим образом: c(y0)-H2(y0) + G2<<7° <^(j0)-G15 o2°=c(j0)-o1°. Эта область не пуста при Gj + G2 < тах|Я, (у0) + Н2 (у0) - с(у0)]. у0еА Множество равновесий К-типа задается условиями Oj° + о2° - с(у0) = а12- с (у,) = о,2 - с{у2) = / > 0 , max[#j (jj), Gj - /] < Я1 (Jo) - о,0 < Я1 (Jo), шах[Я2 (у2 ),G2-f]