3.3. Построение характеристической функции игры
хт := х( = Xя", - получаемое коалицией количество
геТ геТ
ресурса;
гт := - оптимальное для коалиции количество
гёГ
ресурса;
Z(xT,T) \= {ут (хт) = (ylT) ieT : XУ1Т =хт) ~ множество
геТ
возможных распределений ресурса хт между участниками коалиции.
Для rN будем использовать также обозначение p\=rN .
fT (хт) = max X./, О', у (хт)) ~ целевая функция коали-
yreZ(xr,T)jeT
ции в зависимости от получаемого ею количества ресурса хт.
Коалиция максимизирует суммарную полезность распределением полученного ресурса хт между своими участниками. При этом максимум этой функции достигается при хт = гт, когда все члены суммы (111) одновременно достигают своего максимума. При хт < гт целевая функция монотонно возрастает, при хт> гт - монотонно убывает. Так как все члены суммы в (111) - вогнутые функции, то целевая функция коалиции также вогнута.Таким образом, на первом шаге построения характеристической функции необходимо определить количество ресурса хт, получаемого коалицией Т в равновесии. Агенты имеют полную информацию о целевых функциях друг друга, поэтому, как и при некооперативном рассмотрении, логично рассматривать равновесие Нэша в качестве решения игры. Отличие же
заключается в том, что теперь будет рассматриваться не игра п агентов, а игра коалиций.
Для построения получаемого коалицией количества ресурса хт воспользуемся методом анализа множеств диктаторства [69].
Для упрощения построения будем рассматривать только случай дефицита ресурса. Это не уменьшает общности рассмотрения, так как только при наличии дефицита распределение ресурса нетривиально.
При построении характеристической функции коалиции Т считается, что все остальные агенты объединились в коалицию N\T.
Тогда равновесие Нэша в игре коалиций Т и N\T будет равновесием Нэша игры двух лиц с векторными стратегиями. Перейдем от векторных стратегий коалиций к скалярным, воспользовавшись непрерывностью и монотонностью механизма распределения.Пусть некоторая векторная заявка sT коалиции Т при фиксированной заявке smT их противников дает суммарное значение ресурса коалиции Т
(112) хг = X Xj = IX- (ST , SN\T ) •
г'еГ геГ
Тогда по лемме о непрерывности [49] для коалиции Т существует такая допустимая скалярная заявка Uj{xT), что если все участники коалиции заявят Uj{xT), то коалиция получит столько же, сколько и при исходных заявках, то есть хт Для обоснования этого утверждения положим сначала ит =0. При этом, по свойствам монотонных механизмов, ресурс в распоряжении коалиции Т не больше, чем при произвольной векторной заявке. Затем положим ит = R (при этом ресурс не меньше, чем при произвольной векторной заявке) и заметим, что рост заявки ит от 0 до R приводит к непрерывному росту хт(ит, sN\T).
При таком варьировании заявок коалиции Т коалиция N\T не заинтересована в изменении своих заявок, так как получаемое ее участниками суммарное количество ресурса не изменяется. Аналогично и их заявки можно заменить единой заявкой uN[T. Таким образом, равновесие Нэша для этой игры будет совпадать с равновесием Нэша игры двух лиц со скалярными стратегиями ит, uN\T и целевыми функциями fT и fN[T. На рис. 7 приведены множества диктаторства игры двух коалиций. По осям откладывается ресурс, получаемый коалициями Т и N\T в зависимости от их заявок. Точки х(0, 0), х(0, R), x(R. 0), x(R. R) представляют собой ресурс, получаемый коалициями при их заявках (0, 0), (0, R) и т.д. Так как в условиях дефицита ресурса механизм сбалансирован (то есть ресурс всегда распределяется полностью), эти точки (как и остальные точки отображения множества заявок агентов на множество получаемых ими ресурсов), лежат на прямой хт + xv т = R. Кроме того, из монотонности механизма следует, что точка х(0, R) лежит левее и выше точки х(0, 0), a x(R, 0) - правее и ниже.
Соответственно точка x(R, R) лежит на прямой между точками х(0, R) и x(R,0). На этой же плоскости будем откладывать точки r={rT, fx т) максимума целевых функций коалиций. Так как сумма точек максимума р превышает имеющееся количество ресурса R (дефицит), то эта точка будет лежать правее и выше прямой хг + хлr\f=R. Можно показать [69], что если эта точка лежит в области (a, m), то равновесные заявки агентов будут (0, R), и распределение ресурса будет х(0, R). В области (m, а) наоборот,равновесные заявки будут (R, 0), а распределение ресурса - x(R, 0). Если точка г лежит в области (т, с), то коалиция N 7 будет диктатором и получит ресурс в необходимом ей объеме, тогда как коалиция Т в равновесии будет сообщать максимальную заявку. В области же (с, т) наоборот, коалиция Т будет диктатором, а N Т будет сообщать максимальную заявку. В области (m, m) равновесные заявки обоих коалиций максимальны, и распределение ресурса между ними будет x(R, R).
R
x(R, 0) i / ПГ ..J П X r / IT
i ^s, s 'i? —> 12. Р гт
Рис. 8. Зависимость получаемого в равновесии коалицией Т ресурса хт от ее потребности в ресурсе гТ
Для фиксированного р построим все сочетания оптимальных точек целевых функций агентов. Все они лежат на прямой /'г + /'у г = р. которая проходит последовательно через все описанные зоны (изображена жирной линией на рис. 7). Для любой ее точки известны количества ресурса, получаемые коалициями в равновесии. График зависимости хт, от точки пика гт коалиции приведен на рис. 8. Теперь мы можем пользоваться зависимостью хт = хт (rT, Т) для произвольной коалиции Т.
Подставляя полученную зависимость в (111), получаем характеристическую функцию коалиции Т в зависимости от ее состава и положения оптимальной точки гт ее целевой функции. (113) v(T) = Y.fi (Угт), гДе Ут = arg max ? ft (zlT (xT (rT, T))).
ieT zTGZ(rT,T)iGT
Аналогичный анализ можно провести и для немонотонного, разрывного и несбалансированного механизма, однако при этом процесс построения функции хт(гт) уже нельзя представить наглядно на графике.
Отдельно заметим, что если механизм распределения ресурса обладает «свойством нулевой заявки», то на рис. 8 останутся только зоны I, II и III, а если механизм анонимен, то ISI
x(R. R) = -j^-R ¦ и Рис- 8 будет выглядеть следующим образом:
…