Стимулирование агента зависит только от его действия
Л00 = S -У,)- в (У*,y-i) + ?,¦]-хс,-{Уг,У-г),
ieS ieS
где А - символ Кронекера.
Если остальные коалиции коалиционной структуры выполняют план, то есть _yv Л.
= Л., то при выполнении коалицией S плана y*s она получает выигрыш ?( . Обозначим S' - подмно-i<=S
жество участников коалиции S, отклоняющихся от плана. Тогда выигрыш коалиции S примет вид
fs(y)= +
ze S\S' igS
План у будет реализовываться как равновесие Нэша любой коалиционной структурой, если выигрыш произвольной коалиции S при любом ее действии ys не превышает ее выигрыша при выполнении плана: fs(y*s,y*ms) > fs(ys,y*NXS), то есть для всех коалиций S и всех S}<^S справедливо неравенство
X сг ei + min X сг (yms, ,ys,).
IGS\S' ie S' ys: IGS
Проверка этой системы неравенств сводится к решению большого числа задач математического программирования. Эту систему, однако, можно несколько упростить, поскольку по предположению затраты всех агентов возрастают по каждой из компонент действия у.
В этом случае единственным способом увеличения выигрыша коалиции является выбор нулевого действия некоторыми из участников коалиции. Они при этом не получают стимулирования, но остальные участники коалиции выигрывают за счет уменьшения затрат. Система неравенств (26) приобретает тогда вид:
Z^iyly-,) * + Ec.-Ow,^,) •
ieS\S' ieS' ieS
Несмотря даже на это упрощение, задача проверки реализуемости равновесия Нэша остается технически довольно сложной.
Тем не менее, в частном случае, когда затраты каждого агента зависят только от его собственного действия (система со слабо связанными агентами) можно легко констатировать невыгодность кооперации, так как, отклоняясь от плана, каждый агент продолжает нести неотрицательные затраты, но не получает стимулирования.
Из формулы (27) видно, что увеличение «доплат» ?, повышает «устойчивость» системы стимулирования к коалиционному взаимодействию агентов. Можно сформулировать задачу минимизации суммарных доплат, которые гарантируют реализацию некооперативного равновесия и при коалиционном взаимодействии агентов:
min Xе; при условии выполнения неравенств (27).
ieN
Это задача линейного программирования с довольно большим числом ограничений: для любой коалиции S (из всевозможных 2" -1 коалиций) необходимо проверить выполнение 2 s -1 неравенств, а общее число ограничений равно X 2*V -1, то есть
имеет экспоненциальный по числу агентов порядок.