Коалиционное взаимодействие в задачах формирования состава

Если центр по тем или иным причинам не занимается оптимизацией состава системы, то сами агенты могут внутренними усилиями «оптимизировать» состав, незаметно для центра исключив из нее неэффективный агент и распределив его план (а также и стимулирование) между собой. При этом все агенты выигрывают, даже исключенный, так как он получает за свой уход выплату. Проигрывает только центр, поскольку он продолжает платить за уже отсутствующего в системе агента.

Для описанной «оптимизации» состава системы требуются совместные действия всех или части агентов, ведь агент не может сам незаметно устраниться - кто-то должен взять на себя выполнение его плана. Поэтому вполне логичным представляется рассмотрение данной задачи с использованием подходов теории кооперативных игр.

Введем следующие обозначения:

Для произвольной коалиции агентов S введем обозначение

Cs (Г) := min X с, (Л ) Для функции наименьших затрат коалиции

Hzi=YieS

ieS

S по реализации этой коалицией некоторого суммарного действия Y. Обозначим Ys = Xj'J ~ план, назначенный центром коалиции

i<=S

S. оs = ~ стимулирование, назначенное центром коалиции S

i<=S

за достижение плана Ys.

Итак, пусть образовалась коалиция S с 7V. Действие коалиции заключается в выборе подмножества своих участников, позволяющего с минимальными затратами реализовать назначенный центром план Ys (чтобы центр не заметил изменения состава, коалиция должны выполнить план).

(93) v(S) = cr5-minC^(75).

K(z.S

Исследуем реализуемость максимальной коалиции агентов в этой игре. Как обычно, будем считать, что максимальная коалиция реализуется в случае сбалансированности (непустоты С-ядра) кооперативной игры.

Необходимое и достаточное условие непустоты С-ядра (11) для данной игры можно записать следующим образом: для любого сбалансированного покрытия д

X min СК (7,) > min CL (YN).

ScN

Обозначим

K(S) = argminC^(75) - «эффективное» подмножество

K(Z.S

коалиции,

(ziS)ieK(s) = arg min Xc',(z,) ~ «эффективное» распреде-

T,zi=YS ieK(S) ieK(S)

ление планов коалицией S между членами ее эффективного подмножества K(S).

Введем также индикатор [1, ieK(S) (9?) a's ~ [0, i й K(S) '

Тогда условие сбалансированности (94) можно преобразовать к виду:

ZSsCk(s)(Ys)>Ck(n)(Yn) .

ScN

Или, изменяя порядок суммирования в левой части,

X Т^мФгы) ¦

ieNSieS ieN

Теорема 4. Если есть такой агент (с номером /), что его выгодно исключить из любой коалиции, в которую он входит (за исключением, естественно, коалиции {/}), то С-ядро кооперативной игры (93) не пусто. Иначе говоря, С-ядро игры не пусто если

3leN:VS , als = 0. Доказательство. Если выполнено (100), то

X X SsalSct (zlS )= X X Ssct (zlS) + 8{l)c, (у,).

ieNSieS ieN\{l} SieS

Из свойств выпуклых функций [42]

ieN\{l} SieS ieN\{l} SieS

Значит, если верно неравенство

X сг(Х^) + 5{г}сДуг)>

ieN\{l] SieS ieN\{l}

то верно и неравенство (94). Обозначим xi = ^8szis,i е iV\ {/} ,

SieS

тогда

X*i = Z Zfe = Z <5.V Z Z,S = Z ^Z Уг~8щУ1 =

ieN\{l} ieN\{l}SieS S^N ieS\{l} ScW zeS

= Zj, Z Ss-S{l}y, = Z Уг-^щУг =YN-S{l}y,.

ieN SieS ieN

Уменьшим еще левую часть неравенства (101):

Z с,- (*i) + (у,)> min Z с,- (г,-) + S{l}ct (у,) =

ieN\{l} Lzi=rN-d{l}yi ieN\{l}

ieN\(!}

= CN\{l}(YN-S{l}yi)+8{pC1(y1).

Таким образом, необходимо доказать неравенство

"{1}с1 (Уг) - Cn\{1] (YN ) ~ СТЩ (YN

В силу выпуклости Стщ(.) можно увеличить правую часть неравенства следующим образом:

Стщ

' СN\{1}

Значит, теорема верна, если

С1 (У1) + CN\m(YN - Уi) = (^n (Yn) - CN\{1}(YN) = min CK (YN),

а это неравенство очевидно.

Из доказанной теоремы следует, что если некоторого агента выгодно исключить из любой коалиции, то такой агент будет исключен, а оставшиеся агенты перераспределят план так, чтобы минимизировать суммарные затраты всей системы по реализации плана Y .

Если бы центр знал о выгодности исключения этого агента из системы, но не имел возможности изменить суммарный план системы , он именно таким образом перераспределил бы индивидуальные планы между остающимися агентами. Таким образом, максимальная кооперация агентов в данном случае является, несомненно, положительным явлением с точки зрения

центра, если он заинтересован в сокращении затрат, но не считает нужным по тем или иным причинам сам заниматься оптимизацией состава системы.

Исследованная модель коалиционного взаимодействия относится к случаю, когда для выполнения плана достаточно меньшего числа агентов, чем имеется в системе. Рассмотрим обратный случай, когда для выполнения плана агенты, входящие в ОС, могут привлекать других агентов «со стороны».

Итак, имеется центр с целевой функцией Ф(у) = Н{Ъу,)-Цо,(у), и п агентов с целевыми функциями

ieN ieN

/J (у) = <7г (у) - ci (yi). Центр использует систему стимулирования (76)-(77). В этих условиях агенты заинтересованы в выполнении плана ум- Пусть, однако, имеется дополнительный агент с функцией затрат са (уа), о котором центру неизвестно, но известно агентам. Условия выгодности для коалиции агентов S привлечения его к выполнению плана описываются следующим критерием:

min [Cs{Ys-ya) + ca{ya)]Уа> 0

Если выполнено это неравенство, то коалиция S в принципе может выиграть от привлечения дополнительного агента. Однако это же неравенство может быть выполнено, например, и для коалиции N\S, что может привести к конфликту и «перетягиванию» каждой коалицией дополнительного агента «на себя». При исследовании этого конфликта можно провести аналогию с рассмотренной выше в разделе 2.2 моделью с распределенным контролем, где было показано, что в некоторых случаях конфликт может привести к переплатам дополнительному агенту, что порождает нерациональное расходование ресурсов системы «наружу».

Будем считать, что привлечение дополнительного агента выгодно хотя бы для коалиции N, иначе его присутствие не оказывает на поведение агентов никакого влияния. Таким обра-

зом, имеем игру агентов, в которой каждая коалиция может привлекать дополнительного агента для выполнения своего плана. Если коалиции при расчете характеристической функции рассчитывают на гарантированный результат в игре с разрешенным блефом, то для данной игры справедлив следующий результат:

Теорема 5. Кооперативная игра агентов сбалансирована. Доказательство. Для того, чтобы воспользоваться результатами, полученными в разделе 2.2, сведем игру агентов к задаче стимулирования с распределенным контролем, в которой агенты множества N будут выполнять роль центров промежуточного уровня, а дополнительный агент - роль стимулируемого ими агента.

Обозначим Дг ту часть своего плана У, которую /-й «промежуточный центр» передает агенту. Тогда действие агента представляет из себя вектор Д = (Дг)геЛГ. Функции дохода «центров» имеют вид

а затраты агента с(Д) = са (^ Дг).

ieN

Функции дохода «центров» достигают минимума при назначении агенту нулевых планов, то есть модель в целом удовлетворяет условию теоремы 2.

Максимальная коалиция назначает такое действие дополнительному агенту, чтобы суммарные затраты системы с учетом присоединившегося агента были минимальны, то есть это действие совпадает с планом, который назначил бы сам центр, если бы он знал о дополнительном агенте, но не имел возможности изменить назначенный ранее суммарный план YN.

Таким образом, исследование коалиционного взаимодействия в моделях формирования состава ОС показало, что при наличии у агентов возможности привлекать дополнительных сотрудников, они будут действовать сообща, минимизируя суммарные затраты системы. Отличие их поведения от поведения центра заключается только в том, что центр, знай он о

дополнительном агенте, мог бы изменить суммарный план, учитывающий добавление в систему нового агента.

Отметим, что после добавления нового агента в систему агенты могут просить центр увеличить суммарный план к обоюдной выгоде: центр получает возможность реализовать большее действие с меньшими затратами, а агенты - более полно использовать новый состав системы. Действительно, максимум совокупной прибыли системы Я( X Уг + Уа ) - Z Сг (У г )~Са(Уа)

ieN ieN

достигается теперь при суммарном действии, отличном от yN, то есть при изменении плана возникает положительный «бонус», распределение которого уже может являться предметом переговоров центра и агентов. Исследование возможных исходов этих переговоров является перспективной задачей исследований.

Если же агенты имеют возможность незаметного для центра исключения из системы одного или нескольких из них, то единодушие уже возможно не всегда. Тем не менее, выше приведены условия (теорема 4), при которых исключение определенного агента становится «общим делом» всех остальных агентов и в этой ситуации перераспределение между ними плана исключенного агента также оптимально при заданном суммарном плане. Здесь также возможны переговоры между центром и агентами об изменении суммарного плана к всеобщей выгоде.

Подведем итоги второй главы, посвященной исследованию коалиционного взаимодействия участников ОС с полной информацией.

В разделе 2.1 рассмотрена задача стимулирования в веерной ОС. Показано, что в условиях коалиционного взаимодействия важным для выполнения агентами назначенных им центром планов является возможность для центра назначать стимулирование каждому агенту в зависимости не только от его действия, но и от действий других агентов или общего результата деятельности. Если же стимулирование агента может зависеть только от его действия, для выполнения назначенных планов могут потребоваться дополнительные доплаты от центра агентам. Нахождение минимальных доплат сведено к задаче линейного программирования.

В разделе 2.2 для модели стимулирования в ОС с распределенным контролем найдено множество равновесий Нэша игры центров среднего звена управления, предложены несколько способов определения характеристической функции игры центров, были получены достаточные условия реализуемости коалиции всех центров, применимые для широкого класса реальных ОС. Также поставлена и решена задача согласования интересов высшего руководства и среднего звена управления.

В разделе 2.3 показано, что решение задачи формирования состава ОС сводится к решению набора задач стимулирования в веерной ОС. Предложены методы уменьшения вычислительной сложности этой задачи. Также рассмотрено коалиционное взаимодействие агентов при самопроизвольном изменении состава системы. Найдены условия, при которых коалиционное поведение агентов при несанкционированном изменении ими состава системы совпадает с санкционированными центром действиями по оптимизации состава.