<<

стр. 2
(всего 3)

СОДЕРЖАНИЕ

>>

?? ij y j , i ? I.
(18) fi(y) =
j?I
Без ограничения общности предположим, что множество до-
пустимых действий каждого агента составляет отрезок [0; 1].
Тогда множество доминантных стратегий в игре Г0 есть
(19) E 0 ( ?1 ) = ( y id )i?I, y id = Sign(?ii), i ? I,
d

?1, t > 0
где Sign(t) = ? . Определим
0, t ? 0
?
(20) f?(y) = ? ?? ij y j = ? ? j y j ,
i?I j?I j?I

?? ij . Очевидно, что множество равновесий Парето есть
где ?j =
i?I

(21) E 0p ( ?1 ) = ( y ip )i?I, y ip = Sign(?i), i ? I.
Так как существует РДС, то в силу утверждения 1 линейные
АС неуправляемы в смысле K1(?) (при разыгрывании игры Г1),
поэтому рассмотрим игры типа Г2.
Пусть имеется веерная структура ?2k, в которой k-ый агент
является центром. Стратегией центра является выбор функции
uk(y-k), принимающей значения из [0; 1].
Введем множество
(22) Qk = {i ? I \ {k} | Sign(?ki) ? Sign(?ii)}
таких АЭ, которые в отсутствии управления выбирают невыгод-
ные для центра действия (очевидно, что если Sign(?kj) = Sign(?jj),
то j-ым агентом с точки зрения k-го агента управлять не требуется
[6]).
Определим множества
? +
(23) Qk = {i ? Qk | Sign(?ik) = 0}, Qk = {i ? Qk | Sign(?ik) = 1},
агентов, заинтересованных в соответствующем (равном нулю или
единице – внутренние точки отрезка [0; 1] можно не рассматри-
? +
вать) выборе центра. Очевидно, Qk ? Qk = Qk, k ? I.
Определим множества
(24) Pk? = {i ? Qk | Sign(?ki) = 0}, Pk+ = {i ? Qk | Sign(?ki) = 1}


38
агентов, в соответствующем выборе которых заинтересован
центр. Очевидно, Pk? ? Pk+ = Qk, k ? I.
Введем множество агентов, которые согласятся изменить
свои действия, если центр выберет нулевое действие.
(25) Rk = {i ? Qk ? Pk? | ?ii ? –?ik} ? {i ? Qk ? Pk+ | ?ii ? ?ik}.
? ? ?

Для того, чтобы побудить их к этому, центру достаточно исполь-
зовать стратегию
? i ? Pk? ? Rk yi = 0, ? i ? Pk+ ? Rk y i = 1
? ?
?0,
?
?
(26) u k ( y R ? ) = ? .
?1, ? i ? Pk? ? Rk y i = 1 или ? i ? Pk+ ? Rk y i = 0
? ?
?
k


Аналогичным образом введем множество агентов, которые
согласятся изменить свои действия, если центр выберет единич-
ное действие.
(27) Rk = {i ? Qk ? Pk? | ?ik ? ?ii} ? {i ? Qk ? Pk+ | ?ik ? –?ii}.
+ + +

Для того, чтобы побудить их к этому, центру достаточно исполь-
зовать стратегию
? i ? Pk? ? Rk y i = 0, ? i ? Pk+ ? Rk y i = 1
+ +
?1,
?
+
(28) u k ( y R + ) = ? .
?0, ? i ? Pk? ? Rk yi = 1 или ? i ? Pk+ ? Rk yi = 0
+ +
?
k


Таким образом, у центра имеются три альтернативы:
1) разыграть игру Г0 или игру Г1; 2) разыграть игру Г2, обещая в
соответствии с (26) агентам из множества (25) выбрать нулевое
действие, если соответствующие агенты выберут наиболее вы-
годные для центра действия; 3) разыграть игру Г2, обещая в соот-
ветствии с (28) агентам из множества (27) выбрать единичное
действие, если соответствующие агенты выберут наиболее вы-
годные для центра действия.
Вычислим следующие величины:
?? ki Sign(? ii ) + ?kk Sign(?kk) + ?? ki Sign(? ii ) ,
(29) f kd =
i?I \ (Qk ?{k }) i?Qk

?? ki Sign(? ii ) ?? ki ,
(30) f k? = +
+ ? ?
i?Rk ? Pk+
?
i?( I \ (Qk ?{k }))?Qk ?(Qk \ Rk )

?? ki Sign(? ii ) ?? ki .
(31) f k+ = + ?kk +
? + +
i?Rk ? Pk+
+
i?( I \ (Qk ?{k }))?Qk ?(Qk \ Rk )



39
Утверждение 6. Максимальный выигрыш k-го агента при на-
значении его центром в линейной веерной ОС равен
fk = max { f kd , f k? , f k+ }.
Доказательство утверждения 6 заключается в проверке того,
что выбор рекомендуемых центром действий является равновеси-
ем Нэша игры агентов из соответствующего множества. То, что
центру следует использовать управления вида (26)-(28), а не
управления, определенные на некоторых подмножествах мно-
? +
жеств Rk и Rk , следует из определения (22). Выражения (29)-
(31) исчерпывают множество возможных выигрышей центра при
разыгрывании игр Г0, Г1 и Г2. •
Следствие. В зависимости от соотношения величин (29)-(31)
реализуется одно их следующих множеств действий агентов:
- если максимум достигается на f kd , то все агенты выберут
доминантные стратегии;
- если максимум достигается на f k? , то агенты из множества
+ ? ?
(I\(Qk\{k}))? Qk ?( Qk \ Rk ) выберут доминантные стратегии,
агенты из множества ( Rk ? Pk? )?{k} – нулевые действия (в том
?

числе и центр), а агенты из множества Rk ? Pk+ – единичные
?

действия;
- если максимум достигается на f k+ , то агенты из множества
? + +
(I\(Qk\{k}))? Qk ?( Qk \ Rk ) выберут доминантные стратегии,
агенты из множества Rk ? Pk? – нулевые действия, а агенты из
+

множества ( Rk ? Pk+ )?{k} (в том числе и центр) – единичные
+

действия.
Приведем пример, иллюстрирующий свойства линейных ОС
(см. также пример 1).
Пример 4. Рассмотрим линейную ОС (n = 3), в которой целе-
1 ?2 3
вые функции агентов задаются матрицей ? 3 1 ? 5 . Доми-
?1 4 1
нантной стратегией всех агентов в игре Г0 будет выбор единич-
40
ных действий, то есть в структуре ?1 реализуется вектор
x0 = (1, 1, 1), приводящий к выигрышам: f1d = 2, f 2d = -7,
f 3d = 4.
Пусть k = 1, то есть центром назначен первый агент. Тогда
Q1 = {2}, Q1 = {2}, Q1 = ?; P1? = {2}, P1+ = ?, R1 = {2},
? + ?

+
R1 = ?. Оптимальной является следующая стратегия центра:
?0, y 2 = 0
?
, реализующая вектор действий x1 = (0, 0, 1).
u1 (y2) = ?
? 1, y 2 = 1
При этом f1? = 3 > f1d .
Пусть k = 2, то есть центром назначен второй агент. Тогда
? +
P2? = {1, 3}, P2+ = ?,
Q2 = {1, 3}, Q2 = {1}, Q2 = {3};
? +
R2 = {1}, R2 = {3}. Сравнивая выигрыши центра при побужде-
нии первого и третьего агента к выбору нулевых действий
( f 2? = -5, f 2+ = -2), получаем, что выгоднее побуждать третьего
агента, используя следующую оптимальную стратегию центра:
?0, y 3 = 1
?
, которая реализует вектор действий
u 2 (y3) = ?
1, y 3 = 0
?
x2 = (1, 1, 0).
Пусть k = 3, то есть центром назначен третий агент. Тогда
Q3 = {1}, Q3 = ?, Q3 = {1}; P3? = {1}, P3+ = ?, R3 = ?,
? + ?

+
R3 = {1}. Оптимальной является следующая стратегия центра:
?0, y = 1
+
u3 (y1) = ? 1 которая реализует вектор действий
,
1, y1 = 0
?
x3 = (0, 1, 1). При этом f 3+ = 5 > f 3d .
Отметим, что, варьируя структуру, можно реализовать четы-
ре из восьми возможных состояний системы.
Сводка результатов приведена в таблице 2, содержащей вы-
игрыши агентов при различных назначениях центров, а также
(для сравнения вариантов) – вариант xp = (0; 1; 0), оптимальный
по Парето, и значения суммы целевых функций агентов.

41
?f
f1 f2 f3
0
x 2 -7 4 -1
1
x -5 1
3 -1
2
x -1 3
-2 0
3
x 1 -4 5 2
p
x -2 1 4 3
Табл. 2. Выигрыши агентов в примере 4

Из таблицы 2 видно, что каждому из агентов выгодно быть
центром по сравнению с игрой Г0 и с назначением центром друго-
го агента. •
Полученные результаты свидетельствуют о том, что, во-
первых, далеко не все состояния системы могут быть реализова-
ны изменением структуры линейных ОС, а, во-вторых, что реше-
ние задачи структурного синтеза даже для линейных ОС (являю-
щихся в некотором смысле простейшими) достаточно трудоемко.
Обусловлено это, в частности тем, что, выбирая некоторую стра-
тегию, центр не может одновременно поощрять или наказывать
всех АЭ (см. утверждение 6). Выходом является введение побоч-
ных платежей (см. теоретическое обоснование в [24, 25, 76]).
Поэтому перейдем к исследованию моделей ОС с побочными
платежами.


7. РОЛЬ ПОБОЧНЫХ ПЛАТЕЖЕЙ
Общее решение иерархической игры Г2 в двухуровневой ОС
было получено в [25]. Там же, а также в [24, 45, 51, 76], показано,
что введение побочных платежей существенно упрощает как
структуру оптимального решения, так и процесс его поиска.
Формально, в игре с побочными платежами целевые функ-
ции первого и второго агентов имеют, соответственно, вид:
f1(y1, y2, z) = f1(y1, y2) – z, f2(y1, y2, z) = f2(y1, y2) + z, где в игре Г2
z = ?(y2): A2 > ?1 – побочный платеж.
+
Легко показать, что в играх Г0 и Г1 использование побочных
платежей не имеет смысла: второй агент выберет те же действия,
что и в отсутствии побочных платежей, при этом оптимальный
размер платежа с точки зрения первого агента равен нулю. По-
42
этому в дальнейшем под игрой с побочными платежами будем
понимать игру типа Г2 с соответствующим видом целевых функ-
ций агентов.
Игры с побочными платежами, в которых целевые функции
явным образом зависят только от действий второго агента (то
есть первый агент выбирает только зависимость ?(?) платежа z от
действий второго агента), описывают задачу стимулирования
[76], исследованию которой посвящено множество работ
[47, 71, 73, 75].
Начнем изложение моделей сетевых структур с побочными
платежами с примера, иллюстрирующего роль типа игры и воз-
можные интерпретации различных классических иерархических
игр в терминах задач структурного синтеза.
Пример 5 [38, 75, 76]. Пусть ОС состоит из двух агентов –
«центра» и «АЭ» – так как мы будем рассматривать всевозмож-
ные последовательности ходов и варианты информированности,
то термины «центр» и «АЭ» введены для идентификации агента
по виду его целевой функции: W(z, y) = H(y) – z, w(z, y) = z – c(y),
где y ? 0 – действие АЭ, H(?) и c(?) – непрерывные монотонно
возрастающие положительнозначные функции дохода центра и
затрат АЭ, равные в нуле нулю, а z ? 0 – платеж центра АЭ.
Стратегией центра в задаче стимулирования (являющейся
игрой типа Г2 с побочными платежами и специфическим видом
целевых функций) является выбор положительнозначных функ-
ций z = ?(y) от действий агента, стратегией агента – выбор неот-
рицательных действий. Пусть выполнена гипотеза благожела-
тельности. Рассмотрим последовательно несколько возможных
игр между агентами.
Игра Г0. Рассмотрим «обычную» некооперативную игру, в
которой центр и АЭ выбирают свои действия одновременно и
независимо. Так как центр не имеет возможности наблюдать
реализацию выбора АЭ, то он вынужден ограничиться выбором
неотрицательного числа (а не функции от действия АЭ, как это
имеет место в случае, когда центр делает первый ход и рассчиты-
вает на знание действия АЭ).
Из вида целевых функций центра и агента следует, что в игре
Г0 равновесием Нэша является выбор нулевых значений действий
43
и вознаграждений. Таким образом, равновесные действия (ниж-
ний индекс обозначает тип игры): z0 = 0, y0 = 0, а выигрыши
участников: W0 = 0, w0 = 0.
Игра Г1. Предположим теперь, что центр обладает правом
первого хода, но не может рассчитывать на знание выбора АЭ.
Поэтому он вынужден, как и в игре Г0, ограничиться выбором
неотрицательного числа. Отличие игры Г1 от игры Г0 заключается
в том, что в ней центр выбирает свою стратегию первым и сооб-
щает ее АЭ, а АЭ выбирает свое действие при известной ему
стратегии центра. Легко видеть, что наличие права первого хода у
центра не меняет исхода: при любой стратегии центра АЭ выби-
рает нулевое действие как действие, минимизирующее затраты.
Поэтому оптимальной стратегией центра будет нулевое поощре-
ние, то есть z1 = 0, y1 = 0, W1 = 0, w1 = 0.
Игра Г * . Если изменить имеющую место в игре Г1 последо-
2
вательность выбора стратегий на противоположную (то есть
назначить АЭ центром, а центра – АЭ), то получим игру Г * (в2
соответствии с обозначениями теории иерархических игр [25]
игра, полученная из исходной переменой последовательности
ходов, обозначается звездочкой), в которой АЭ первым выбирает
стратегию и сообщает ее центру (при этом считается, что страте-
гия центра всегда становится известной АЭ; в противном случае
*
получим игру Г 1 , решение которой для рассматриваемого при-
мера совпадает с решением игры Г1). Содержательно центр полу-
чает от АЭ информацию о зависимости действия, выбираемого
АЭ, от вознаграждения, выплачиваемого ему центром.
Обозначим y* = arg max {H(y) – c(y)}, Q = H(y*) – c(y*).
y? A
Предположим, что функция H(?) вогнута, а функция c(?) выпукла.
Тогда действие y* единственно. Оптимальной стратегией АЭ
˜ ( z ) = ? y , z = H ( y ) , побуждающая центр выбрать
* *
будет: y 2 ?
?0, z ? H ( y )
*

поощрение z = H(y*) и приводящая к следующему вектору полез-
* *
ностей: W2 = 0, w2 = Q.

44
Игра Г2, в которой центр делает первый ход и, рассчитывая
на знание действия АЭ, выбирает свою стратегию в виде функции
от выбора АЭ, имеет симметричный игре Г * вид, то есть в ней
2

˜ ( y ) = ? c( y ), y = y ; y2 = y*,
* *
оптимальны стратегии ?
z2 = z 2
y?y *
? 0,
которые приводят к следующему вектору выигрышей: W2 = Q,
w2 = 0. Отметим, что вектора полезностей участников ОС, соот-
ветствующие играм Г2 и Г * , недоминируемы по Парето.
2
*
Игра Г 3 . Если в игре Г2 первый ход делает агент, то получа-
*
ем игру Г3 . Оптимальные стратегии агента и центра:
?*
˜ ( y ) = ? H ( y ), y = y
* *
˜* ( ˜( y )) = ? y , z = z3 ? ˜
*
?
y3 z y ? y * ; z3 = z3 ( y ) ,
? 0,
? 0, z ? ˜3 ( y )
? z
приносят им выигрыши W3* = 0, w3 = Q.
*

Игра Г3, в которой стратегией АЭ является функция от выбо-
ра центра, для рассматриваемого примера эквивалентна (в смысле
равновесных выигрышей участников системы) игре Г2, то есть
W3 = Q, w3 = 0.
В [25] показано, что все иерархические нечетные игры, начи-
ная с третьей, эквивалентны (в смысле гарантированного выиг-
рыша первого агента) игре Г3, а все четные игры, начиная со
второй, эквивалентны игре Г2. Среди первых трех игр игра Г2
характеризуется максимальной эффективностью, далее следует
игра Г3, и, наконец, игра Г1. Поэтому рассматривать игры более
высокого порядка не имеет смысла. Отметим, что из рассматри-
ваемой схемы «выпадает» распределение ролей, когда оба агента
являются центрами и каждый пытается навязать другому игру Г2
с правом собственного первого хода. Определить равновесие в
такой игре, не вводя дополнительных предположений, затрудни-
тельно. Можно считать равновесием ситуацию, в которой один из
агентов соглашается на второй ход. При этом реализуется одна из
описанных выше игр Г2 или Г * .
2


45
Таким образом, в рассматриваемой частной модели мини-
мальными играми, описывающие все разнообразие равновесных
распределений выигрышей, являются игры Г2 и Г * (в играх Г0,
2
*
Г 1 и Г1 выигрыши агентов строго доминируются по Парето
выигрышами в любой из игр второго порядка, а игры третьего и
более высокого порядка приводят к тем же векторам выигрышей).
Можно также заметить, что в играх второго порядка агенты,
фактически, определяют распределение между собой «неделимо-
го» выигрыша Q – агент, сделавший ход первым, забирает этот
выигрыш себе, вынуждая второго согласиться (в рамках гипотезы
благожелательности) на нулевое значение своей целевой функ-
ции. Приведем содержательные интерпретации этого факта.
В экономике труда, в теории контрактов, моделях рекрутин-
га, задачах стимулирования и мотивации (см. обзор и ссылки в
[38, 69]) используется понятие области компромисса. Напомним,
что областью компромисса называется множество дележей z
между центром и АЭ, сумма которых равна Q, при использовании
участниками ОС равновесных в соответствующей метаигре дей-
ствий, то есть следующее множество:
{z ? 0 | W(z, y*) + w(z, y*) = Q}.
Следовательно, при определении ролей (решении задачи
синтеза структуры) в модели стимулирования происходит борьба
участников за первый ход. Если существуют институциональные
ограничения, определяющие последовательность ходов, то роли
распределяются однозначно. Такая ситуация может иметь место,
например, при найме АЭ на работу в организацию, интересы
которой представляет центр.
Если на рынке труда существует значительная конкуренция
(то есть, если имеется несколько претендентов на данную вакан-
сию), то с условиях неопределенности (неполной информирован-
ности центра о целевых функциях агентов) равновесием среди
претендентов является аукционное решение (в случае, когда
имеется много однородных АЭ, в равновесии победитель получа-
ет нулевую или резервную полезность). Если же на рынке труда
имеется единственный претендент (например, высококвалифици-
рованный специалист и т.д.), то он является «диктатором» и ему

46
(а не центру!) выгодно сделать первый ход, вынудив центр согла-
ситься на нулевую полезность.
Помимо трудовых контрактов, содержательным примером
распределения ролей в соответствии с описанной выше схемой
могут служить механизмы обмена [76]. •
Завершив рассмотрение примера и качественное обсуждение
роли побочных платежей в теоретико-игровых моделях управле-
ния организационными системами, перейдем к теоретическому
анализу побочных платежей в сетевых структурах – сначала в
веерных структурах (раздел 8), а затем в двухуровневых (раздел
9) и произвольных иерархических (раздел 10) структурах.


8. ПОБОЧНЫЕ ПЛАТЕЖИ В ВЕЕРНЫХ СТРУКТУРАХ
Рассмотрим n-агентную ОС, в которой при назначении цен-
тром i-го агента (то есть при структуре ?2i) целевые функции
участников имеют вид:
(32) wj(y) = fj(y) + ?j(y-i), j ? I \ {i},
(33) wi(y) = fi(y) – ?? j ( y ?i ) .
j ?i
Отметим, что в рамках (32)-(33) считается, что центр назна-
чает побочный платеж каждому АЭ отдельно.
Если на побочные платежи наложено требование неотрица-
тельности (но не ограниченности сверху), то стратегией наказа-
ния с точки зрения побочных платежей будет нулевой платеж.
Фиксируем вектор планов x ? A’. Рассмотрим класс стратегий
центра вида:
?? j , y j = x j
(34) ?xj(y-i) = ? , j ? I \ {i},
0, y j ? x j
?
y ?i = x ?i
? xi ,

y ?i ? j = x ?i ? j , y j ? x j ,
(35) ui(y-i) = ?uij ,
? произвольное, в остальных случаях
?
н н
где определяется как
uij (y-i) fj( uij (y-i), y-i) = min fj(yi, y-i),
yi ?Ai
j ? I \ {i}. Отметим, что в рамках стратегии (35) центр в общем
47
случае не может одновременно наказать двух АЭ, но для реализа-
ции равновесия Нэша требуется застраховаться только от одно-
сторонних отклонений АЭ (см. (37)). Такое поведение центра
называется блефом [25].
Обозначим
(36) Lj(y-i-j) = max min fj(yi, y-i), j ? I \ {i}.
yi ?Ai
y j ?A j
Запишем условия реализуемости, то есть выгодности для АЭ
выбора действий, совпадающих с планами (условие записывается
для каждого АЭ по отдельности в предположении, что остальные
АЭ выполняют планы):
(37) fj(x) + ?j ? Lj(x-i-j), j ? I \ {i}.
Так как центр заинтересован в минимизации платежей, то из (37)
следует, что ?j = Lj(x-i-j) – fj(x) , j ? I \ {i}.
Утверждение 7. В структуре ?2i с побочными платежами иг-
рой Г2 реализуемы состояния ОС, являющиеся решением сле-
дующей задачи:
(38) ? f i ( x ) – ? L j ( x ?i ? j ) > max .
x?A'
j ?i
i?I
Справедливость утверждения 7 следует из того, что система
неравенств (37) обеспечивает равновесность по Нэшу планов,
назначаемых центром, использующим управления (34)-(35), а
задача (38) является задачей оптимального согласованного пла-
нирования [10, 75].
Задача (37)-(38) является достаточно трудоемкой, поэтому
рассмотрим ее частный случай, в котором центр разыгрывает
игру Г1 по {fj(?)} и игру Г2 по побочным платежам. Будем обозна-
чать эту игру Г1-Г2.
Фиксируем действие центра xi ? Ai. Для того, чтобы исполь-
зование побочных платежей (34) реализовывало вектор x-i ? A-i
как равновесие Нэша игры АЭ необходимо и достаточно, чтобы
выполнялось:
(39) fj(x) + ?j ? Lj(x-j), j ? I \ {i},
где
(40) Lj(x-j) = max fj(yj, x-j), j ? I \ {i}.
y j ?A j



48
Так как центр заинтересован в минимизации выплат АЭ, то
получаем, что ?j = Lj(x-j) – fj(x), j ? I \ {i}. Подставляя эти мини-
мальные платежи в целевую функцию центра, получаем, что
задача оптимального согласованного планирования сводится к:
(41) ? f i ( x ) – ? L j ( x ? j ) > max .
x?A'
j ?i
i?I
Таким образом, мы доказали следующий результат.
Утверждение 8. В структуре ?2i с побочными платежами иг-
рой Г1-Г2 реализуемы состояния ОС, являющиеся решением
задачи (41).
Следствие. Если ? L j ( x ?i ? j ) или ? L j ( x ? j ) не зависит от
j ?i j ?i
i ? I, то состояние ОС при структуре ?2i в соответствующей игре
(Г2 или Г1-Г2) не зависит от i (то есть от назначения центра) и
является оптимальным по Парето.
Приведенное следствие отражает распространенную во мно-
гих практически важных случаях ситуацию, когда гарантирован-
ный результат всех АЭ одинаков и не зависит от их действий и от
обстановки игры.
Задача (41) существенно проще задачи (38), но множество
состояний ОС, реализуемых в веерной структуре игрой Г2 в об-
щем случае включает в себя множество состояний ОС, реализуе-
мых в веерной структуре игрой Г1-Г2. Для совпадения этих мно-
жеств, очевидно, достаточно, чтобы имело место
min ? L j ( x ?i ? j ) = min ? L j ( x ? j ) , i ? I.
x?A' j ?i x?A' j ?i

Условия следствия и совпадения множеств реализуемых дей-
ствий имеют место в задачах стимулирования и др. [71, 75].
Таким образом, в веерных структурах оптимальное решение
задачи структурного синтеза в классе веерных структур зависит
от свойств функционалов (36) и (40). Критерием оптимальности
является минимальность этих величин.




49
9. ПОБОЧНЫЕ ПЛАТЕЖИ В ДВУХУРОВНЕВЫХ
СТРУКТУРАХ
Перейдем от рассмотрения веерных структур к изучению за-
дач структурного синтеза в классе двухуровневых структур.
Веерная структура по определению является двухуровневой,
поэтому в настоящем разделе исследуем двухуровневые ОС с
распределенным контролем (РК), то есть двухуровневые ОС, в
которых имеется несколько центров. Задачи управления ОС РК
описаны в [26, 31, 76]. В упомянутых работах исследовалось
равновесие игры центров (в том числе – кооперативные эффекты)
в системах с заданной структурой. Поэтому рассмотрим задачу
оптимального назначения центров из числа агентов.
Пусть K ? I – множество центров, имеющих целевые функ-
ции (условимся, что моделях настоящего раздела верхний индекс
обозначает центров)
(42) wi(y) = f i(y) – ?? ij (yI\K), i ? K,
j?I \ K
и осуществляющих управление (в смысле игры Г2 с побочными
платежами) АЭ из множества I \ K, имеющими целевые функции
(условимся, что в моделях настоящего раздела нижний индекс
обозначает АЭ)
?? ij (yI\K), i ? I \ K.
(43) wi(y) = fi(y) +
j?K
Как и в веерных ОС с побочными платежами, будем считать,
что стратегией i-го центра в игре типа Г2 с побочными платежами
является выбор функций ? ij : AI\K > ?1 , j ? I \ K, и своего «дей-
+
ствия» yi = ui(yI\K), ui: AI\K > Ai.
Двухуровневую структуру, в которой имеется множество K
центров, будем обозначать ?2K.
Ограничимся рассмотрением класса стратегий центров типа
(34) – свойства этого класса стратегий подробно обсуждаются в
[32, 76], то есть
? ?ij , y j = x j
?
(44) ? jx (yI\K) = ? , i ? K, j ? I \ K.
i
?0, y j ? x j
?

50
Стратегию наказания в рассматриваемой ОС РК введем так-
же, как и в веерной структуре (см. предыдущий раздел). Гаранти-
рованный выигрыш АЭ будет при этом равен
(45) Lj(x-K-j) = max minK fj(yj, yK, x-j-K), j ? I \ K.
y j ?A j y ?A
K


Отметим, что, определяя гарантированный выигрыш j-го
агента в виде (45), мы неявно предполагаем, что центры находят-
ся в режиме сотрудничества [76], то есть могут совместно "нака-
зывать" АЭ.
Условие того, что выбор АЭ действий yI\K, совпадающих с
планами xI\K, является равновесием Нэша их игры при заданных
стратегиях центров, имеет вид:
(46) fj(x) + ? ?ij ? Lj(x-K-j), j ? I \ K.
i?K
Из (46) следует, что, управляя АЭ в одиночку, i-ый центр
может получить гарантированно следующий выигрыш:
(47) Wmax = max min} [fi(xi, xI\K, xK|{i}) + ? f j ( x i , x I \ K , x K \{i} ) –
i
i K \{ i
x
x , xI \ K j?I \ K

? L j ( x? i ? j ) ], i ? K.

j? I \ K
Следовательно, условие того, что размер побочных платежей
и стратегии центров вида (44) обеспечивают индивидуальную
рациональность центров, можно записать в виде:
(48) fi(x) – ? ?ij ? Wmax , i ? K.
i

j?I \ K
Запишем задачу определения минимальных неотрицательных
платежей со стороны центров, побуждающих АЭ выбрать тре-
буемые действия:
(49) ? ? ?ij > min, при ограничениях (46) и (48).
i?K j?I \ K
Так как ограничения (46) и (48) сформулированы для некото-
рого "плана" x ? A', то и решение задачи (49) будет зависеть от
этого плана. Следовательно, можно выделить множество
X(K) ? A' состояний ОС, реализуемых в двухуровневых системах
множеством центров K, то есть множество состояний, для кото-

51
рых существует решение задачи (49). Сформулируем этот резуль-
тат в виде следующего утверждения.
Утверждение 9. В двухуровневых ОС со структурой ?iK реа-
лизуемы состояния ОС, для которых существует решение задачи
(49).
Отметим, что, если отказаться от того, что центры ограниче-
ны классом стратегий (44), то множество реализуемых состояний
системы может расшириться при неизменных выигрышах участ-
ников.
Следовательно, в двухуровневых ОС задачу структурного
синтеза можно записать в виде задачи выбора множества центров,
реализующего наиболее предпочтительное с точки зрения ЛПР
состояние ОС:
(50) min f0(x) > max .
K?2I
x?X ( K )
Отметим, что при определении критерия эффективности (50)
в ОС с веерной структурой (то есть в двухуровневых ОС с одним
центром) использовалась гипотеза благожелательности центра к
ЛПР, то есть вычислялось максимальное значение целевой функ-
ции ЛПР на множестве действий, реализуемых центром (достав-
ляющих максимум его целевой функции). В ОС РК пользоваться
гипотезой благожелательности следует очень осторожно – как
отмечается в [76] при наличии нескольких центров неясно, что
понимать под их благожелательным отношением к ЛПР, а также
неясно что понимать под благожелательным отношением АЭ к
нескольким центрам одновременно. Если ЛПР может управлять
выбором равновесия игры центров, то применение гипотезы
благожелательности корректно, в общем же случае целесообразно
применять гарантированный результат – вычислять минимум по
множеству реализуемых состояний ОС (см. выражение (50)).
Введем следующее предположение, которое выполнено, в
частности, в задачах стимулирования [26, 31, 75, 76]:
(51) ? j ? I, ? x-j ? A-j max fj(yj, x-j) = Lj.
y j ?A j

где {Lj} – некоторые константы.
Из (51) следует, что ? j ? I, ? K ? I, ? x ? A’ имеет место:
j
Lj(x-i-j) = Lj(x-j) = Lj(x-K-j) = Wmax = Lj.

52
Утверждение 10. Если выполнено (51), то для любой струк-
туры ?2K найдется структура ?2i не меньшей эффективности.
Доказательство. Докажем, что ? K ? I выполнено
X(K) ? X* = Arg max ? f i ( x ) .
x?A' i?I
Тогда из min f0(x) ? min f0(x), будет следовать, что, если неко-
*
x?X ( K ) x?X
торая структура (например, ?2i, i ? I, в рамках (51)) реализует
состояния из X* и только их, то ее эффективность не меньше
эффективности структуры ?2K, реализующей состояния из X(K).
Из (46) и (48), с учетом (51), следует, что реализуемыми яв-
ляются состояния, удовлетворяющие
? ?ij ? Lj – fj(x), j ? I \ K, ? ?ij ? fi(x) – Li, i ? K.
j?I |K
i?K
Из данной системы неравенств получаем
X(K) ? {x ? A’ | ? f i ( x ) ? ? Li } ? X*,
i?I i?I
что и требовалось доказать. •
Таким образом, утверждение 10 дает достаточное условие
того, что введение нескольких центров не увеличивает эффектив-
ности, то есть в рамках предположения (51) в двухуровневых
структурах достаточно ограничиться классом ОС с одним цен-
тром. Важным представляется то, что в рамках (51) множество
реализуемых состояний всегда включает множество состояний
ОС, эффективных по Парето.
Следствие. В задаче стимулирования оптимальна веерная
структура.
Справедливость утверждения следствия обосновывается тем,
что в задачах стимулирования выполнено (51) [68, 75].
Следствие. Если выполнено (51), то:
а) состояние ОС при структуре ?2i в соответствующей игре
(Г2 или Г1-Г2) не зависит от i (то есть от назначения центра) и
является оптимальным по Парето;
б) множество состояний ОС, реализуемых в веерной струк-
туре игрой Г2 совпадает с множеством состояний ОС, реализуе-
мых в веерной структуре игрой Г1-Г2

53
Справедливость первого пункта следствия вытекает из (38),
второго пункта – из (36) и (40).
Отметим, что предположение (51) является чрезвычайно
сильным – в его рамках взаимодействие агентов вырождается,
поэтому результаты утверждения 10 и его следствий также явля-
ются вырожденными.
Завершив исследование задач структурного синтеза в классе
двухуровневых структур с побочными платежами, рассмотрим
произвольные (многоуровневые) иерархические структуры с
побочными платежами.


10. ПОБОЧНЫЕ ПЛАТЕЖИ В ИЕРАРХИЧЕСКИХ
СТРУКТУРАХ
До сих пор мы рассматривали задачу структурного синтеза
как задачу распределения агентов по уровням иерархии, где
каждому уровню ставился в соответствие определенный приори-
тет в порядке выбора стратегий. Существенную роль играло то,
что центры (управляющие органы) выбирались из числа агентов,
а эффективность той или иной структуры оценивалась по значе-
ниям критерия, отражающего интересы внешнего по отношению
к ОС лица, принимающего решения.
Анализ задач структурного синтеза, проведенный выше, сви-
детельствует об их высокой сложности в общем случае, и только
в ряде частных случаев удается получить сравнительно простое
содержательно интерпретируемое решение (см. утверждения 1-
10). Поэтому в настоящем и ряде последующих разделов изменим
постановку задачи, то есть будем считать, что все агенты из
множества I являются активными элементами (АЭ) и расположе-
ны на нижнем уровне иерархии. Тогда задача структурного син-
теза будет заключаться в нахождении иерархической (не обяза-
тельно древовидной) структуры – определении оптимального
числа так называемых внешних (по отношению ко множеству
агентов) центров и распределении их по уровням иерархии. При
этом считается, что центры имеют интересы, которые в опреде-
ленном ниже смысле «совпадают» с интересами ЛПР. Другими
словами, центры не имеют собственных интересов, отличных от
интересов ЛПР, то есть лица, решающего совместно с исследова-
54
телем операций задачу синтеза. Отметим, что такой подход явля-
ется типичным для исследования операций.
При изучении задачи структурного синтеза в той постановке,
в которой она формулируется в настоящем разделе, появляется
возможность использования результатов по декомпозиции игры
сильно связанных элементов, полученных в [75, 76], а также
результатов анализа многоуровневых ОС, приведенных в
[53, 69, 73]. Следует отметить, что при назначении центрами
субъектов, внешних по отношению к множеству I агентов, суще-
ственно упрощаются задачи анализа состояний ОС, реализуемых
различными структурами, особенно в случае возможности осуще-
ствления побочных платежей между центрами и АЭ.
Рассмотрим следующую модель.
Предположим, что имеется один центр, интересы которого
совпадают с интересами ЛПР, то есть центр имеет целевую функ-
цию f0(y), и присутствует бюджетное ограничение C на суммар-
ное стимулирование. Такую веерную структуру будем обозначать
?20 (индекс «0» означает, что центр назначен извне, то есть не из
множества I агентов).
Обозначим для фиксированного вектора ?(?)
EC(?) = EN(?) ? {y ? A’ | ?? i ( y) ? C}
i?I
множество равновесных по Нэшу при системе стимулирования
?(?) действий, для которых суммарные выплаты центра по их
реализации не превышают бюджетного ограничения. Тогда зада-
ча оптимального управления в структуре ?20 может быть сформу-
лирована как
(52) min f0(y) > max .
y?E С (? ) ?
Обозначим
(53) L0(x) = ? Li ( x ?i ) ,
i?I
где Li(x-i) = max fi(yi, x-i), i ? I,
yi?Ai

? fi ( y) .
(54) F0(y) =
i?I



55
Отметим, что F0(y) является утилитарной функцией коллек-
тивной полезности, свойства которой подробно исследуются,
например, в [65]. Содержательно функция F0(y) может интерпре-
тироваться как целевая функция «системы» из n агентов. Функ-
ция F0(y) согласована с отношением доминирования по Парето в
следующем смысле: если вектор z Парето-доминирует вектор y,
то F0(z) ? F0(y).
Рассмотрим задачу (52) в отсутствии бюджетного ограниче-
ния (C = +?). Пусть центр использует систему стимулирования
? ?i ( x ) + ? i , yi = xi
(55) ?ix(y) = ? ,
y i ? xi
?0,
где ?i(x) – побочный платеж i-му АЭ от центра в случае выполне-
ния первым плана, ?i > 0 – сколь угодно малая строго положи-
тельная константа. В выражении (55) первый режим соответству-
ет трансферту полезностей, а второй режим – наказанию за
индивидуальные отклонения.
Легко видеть, что если
(56) ?i(x) ? Li(x-i) – fi(x), i ? I,
то E 2 ( ? 20 ) = {x}, то есть x ? A’ является единственным РДС
d

игры АЭ при управлении (55).
Получаем, что реализуемыми (и доставляющими максимум
целевой функции центра с учетом побочных платежей) будут
состояния ОС из множества
(57) X(?20) = Arg max [f0(x) + F0(x) – L0(x)].
x?A'
Перейдем к учету балансового (бюджетного) ограничения
при условии, что на побочные платежи используются «внешние»
(не принадлежащие центру в смысле вхождения в f0(y)) средства.
Если трансферты полезности соответствуют внутреннему, то есть
замкнутому относительно множества АЭ, стимулированию, то
сумма трансфертов должна быть неположительна (с точностью до
сколь угодно малой строго положительной константы ? = ? ? i ).
i?I
Если центр имеет возможность привлечь внешние или использо-
вать собственные средства в размере С ? 0, то балансовое ограни-
чение, то есть условие минимальной (при неравенствах (56),
56
выполняющихся как равенства) внутренней сбалансированности,
примет вид:
(58) ?? ix ( x) = L0(x) – F0(x) ? С.
i?I
Таким образом, в рамках замкнутого набора АЭ (при C = 0)
(58) отражает условие неотрицательности баланса трансфертов.
Понятно, что множество P(C) точек, в которые ОС может
быть переведена управлением с побочными платежами, ограни-
ченными в сумме величиной C, есть
(59) P(C) = {y ? A' | L0(y) – F0(y) ? C}.
Следовательно, рассматриваемое управление в ряде случаев
позволяет сделать эффективное по Парето коллективное решение
устойчивым по Нэшу. Таким образом, справедлив следующий
результат.
Утверждение 11. При заданном бюджетном ограничении лю-
бая точка множества (59) может быть реализована системой
стимулирования (55) как эффективное равновесие Нэша.
Если выполнено предположение (51), то, обозначая
L0 = ? L j , получим, что реализуемы будут действия из множе-
j?I
ства {y ? A' | L0 – С ? F0(y)} – см. свойства множества реализуе-
мых действий в задачах стимулирования [68, 71].
Имея результат утверждения 11, изучим преимущества и не-
достатки введения дополнительного уровня иерархии (выделения
над множеством АЭ метаагента – центра).
Введем следующий механизм функционирования АС. Центр
использует систему стимулирования (55) с x ? P(C). При этом:
вектор x является равновесием Нэша, в котором всем АЭ обеспе-
чивается не меньшая полезность, чем при выборе любого другого
индивидуально рационального равновесия; отпадает необходи-
мость получения и обработки АЭ информации о своих оппонен-
тах; центр получает во внутренне сбалансированном механизме
ненулевую полезность.
Итак, выделение над одноуровневой АС дополнительного
уровня управления с наделением его правом частично устанавли-
вать правила игры АЭ (в рамках концепции их некооперативного
поведения) является взаимовыгодным для центра и для всех АЭ,
57
как с точки зрения снижения на АЭ нагрузки по обработке ин-
формации, так и с "экономической" точки зрения – внешнее
управление центра делает выгодным и индивидуально рацио-
нальным коллективно рациональное (в смысле Парето-
эффективности) взаимосодействие АЭ.
В качестве иллюстрации использования предложенных выше
подходов к описанию и исследованию сбалансированного моти-
вационного управления рассмотрим частный случай линейных
ОС (см. общие результаты выше), в которых
(60) F0(y) = ? ? i yi .
i?I
Парето оптимальное (доставляющее максимум (60)) действие
есть (см. также выше) y iP = Sign (?i), доминантная стратегия –
y id = Sign(?ii), i ? I. Определим следующие величины:
?
(61) ?i(yd, yP) = ?i(yd, yP) = ?ij [Sign(?j) – Sign(?jj)].
j?I
Легко проверить, что в любых линейных ОС выполнено:
? ?i(yd, yP) ? 0. Пусть центр в линейной ОС использует сле-
i?I
дующую систему стимулирования:
(62) ?i(yi) = [?i(yd, yP) + ?i] I(yi = y iP ) + ?ii I(yi ? y iP ),
где I(?) – функция индикатор (отметим, что в точке Парето
«штрафы» равны нулю).
Система стимулирования (62) обеспечивает каждому АЭ ту
же полезность, что и при использовании им доминантной страте-
гии, причем yP является равновесием по Нэшу. Более того, центр
оставляет в собственном распоряжении ненулевую полезность,
равную:
(63) F0 = F0(yP) – F0(yd) = ? ?j [Sign (?j) – Sign (?jj)] ? 0,
j?I
которая может рассматриваться как критерий эффективности
управления.
Величина (63) может интерпретироваться как мера «систем-
ности» набора АЭ: с одной стороны это – доход центра, а с дру-

58
гой – интегральная характеристика рассогласованности предпоч-
тений АЭ. Таким образом, справедлив следующий результат.
Утверждение 12 [53, 73]. Эффективность управления в ли-
нейной ОС определяется выражением (63).
Обозначим ?(x) = ? ? j ( x) = L0(x) - F0(x).
j?I
Рассмотрим пример линейной ОС, иллюстрирующий утвер-
ждение 12.
Пример 6. Пусть в линейной АС целевые функции агентов
равны fi(y) = yi + ? (1 ? y j ) , Ai = [0; 1], i ? I. Тогда L0(x) = 2 n –
j ?i

?xj , ?xj , ?xj .
?(x) = n – Если
(n – 1) F0(x) = n – (n – 2)
j?I j?I j?I
f0(x) = – ( ? x j ) /2?, то множеством оптимальных реализуемых
2

j?I

? x j =?}. •
действий будем X* = Arg max {f0(x)–?(x)} = {x ? A' |
x?A' j?I
Таким образом, выше в настоящем разделе мы исследовали
множество состояний ОС, реализуемых при тех или иных бюд-
жетных ограничениях в структуре ?20. Если f0(y) – целевая функ-
ция ЛПР, выделяющего средства в размере C, то его задача в
рамах гипотезы благожелательности заключается в определении
оптимальной величины суммарных побочных платежей, то есть
трансфертов, максимизирующих эффективность K(C) управле-
ния:
(64) K(C) = max f0(y) – C > max .
C ?0
y?P ( C )
Решение обратной задачи (определения минимальных затрат
на гарантированную реализацию множества X ? A’ состояний
ОС) имеет вид
C(X) = max {L0(y) – F0(y)}.
y? X
Так как множество (59) не зависит от центра (его целевой
функции или каких-либо других характеристик), то получаем, что
справедлив следующий результат.


59
Утверждение 13. В ОС с побочными платежами при назначе-
нии управляющих субъектов извне (не из множества I) оптималь-
на структура ?20.
Содержательно утверждение 13 означает, что, если центры
назначаются извне (или не обладают собственными интересами),
то не следует вводить нескольких центров или несколько уровней
иерархии, так как любое состояние ОС, реализуемое при задан-
ных ограничениях на ресурсы ЛПР, может быть реализовано
единственным центром в рамках структуры ?20.
Интересно, что результат утверждения 13 противоречит су-
ществованию широко распространенных на практике многоуров-
невых ОС или ОС с распределенным контролем. Причина заклю-
чается в следующем – результаты всех приведенных выше
утверждений получены в предположении (иногда неявном), что
отсутствуют ограничения на допустимые структуры. В то же
время, на практике возможности управляющих органов ограни-
чены, что и приводит к необходимости введения нескольких
управляющих субъектов, нескольких уровней управления и т.д. В
[46, 62, 79] введен ряд числовых характеристик графов (струк-
турная избыточность, неравномерность распределения связей,
структурная компактность и др.), которые позволяют учитывать
ограничения на структуры.
Обобщим полученные в настоящем разделе результаты на
случай, когда множество агентов I разбито на непересекающиеся
подмножества, каждое из которых подчинено "своему" центру.
Рассмотрим одно из подмножеств (коалицию) S ? I. Предполо-
жим, что центр, осуществляющий руководство АЭ из коалиции S,
использует управление типа (55), где ?i = ?i(xS), то есть вознагра-
ждение АЭ зависит только от действий АЭ, входящих с ним в
одну коалицию. Тогда для того, чтобы выбор агентами из коали-
ции S вектора xS ? AS действий был равновесием Нэша их игры
(действия агентов из множества I \ S при этом для них выступают
в роли внешних неопределенных факторов) должно выполняться:
? i ? S, ? x-S ? A-S, ? xi ? Ai ?i(xS) + fi(xS, x-S) ? fi(xS|xi, x-S).
Последнее неравенство эквивалентно следующему:
? i ? S, ? x-S ? A-S, ?i(xS) ? Li(x-i) – fi(xS, x-S).

60
Следовательно, для того, чтобы реализовать вектор xS как
равновесие Нэша (и, более того – как РДС) игры АЭ из коалиции
S, соответствующему центру достаточно использовать управле-
ние (55), в котором ?i(xS) = vi(xS, S), где
(65) vi(xS, S) = max {Li(x-i) – fi(xS, x-S)}, i ? I, S ? I.
x? S ?A? S
Очевидно, что при фиксированном векторе планов x ? A'
всех АЭ функция (65) убывает с расширением коалиции S.
Содержательно, в соответствии с (55) и (65), центр должен
гарантированно компенсировать затраты подчиненного ему АЭ в
случае выполнения последним плана, независимо от действий
других АЭ, входящих в ту же коалицию, или не входящих в нее.
Обозначим затраты центра на стимулирование АЭ из коали-
ции S
(66) v(xS, S) = ? vi(xS, S).
i?S
Вычислим введенные выше величины для линейных ОС:
F0(x) = ? ? j x j , L0(x) = ? ( Sign(? jj ) ? x j )? jj + ? ? j x j ,
j?I j?I j?I

? ( Sign(? jj ) ? x j )? jj
?(x) = ? 0, vi(x, S) = ?ii(Sign(?ii) - xi), i ? I.
j?I
В частности, в условиях примера 6 vi(x, S) = 3 – n – xi, i ? I.
Особо следует отметить, что в линейных ОС затраты центра
на стимулирование i-го АЭ vi(x, S) не зависят от той коалиции, в
которую входит данный АЭ. Вообще, данный вывод справедлив
для игр с сепарабельными функциями выигрыша игроков [36].
Исследуем свойства зависимости (66), которая характеризует
минимальные затраты центра, осуществляющего управление
коалицией S (и только ей!), по побуждению элементов этой коа-
лиции к выбору вектора действий xS ? AS. Будем называть эту
зависимость функционалом затрат на управление.
Фиксируем две произвольные коалиции S1 ? I и S2 ? I, такие,
что S1 ? S2 ? I, и два произвольных вектора xS1 ? AS1 и xS2 ? AS2
вектора действий членов этих коалиций. Рассмотрим коалицию
S = S1 ? S2, полученную в результате объединения двух исходных
коалиций, и вектор xS = (xS1, xS2) действий ее членов.

61
Оценим затраты на управление i-ым АЭ, входящим, напри-
мер, в коалицию S1:
vi(xS, S) = max {Li(x-i) – fi(x)} ?
x? S ?A? S
? {Li(x-i) – fi(x)} = vi(xS1,S1), i ? S1.
max
x ? S 1 ? A? S 1
Из данной системы неравенств и (66) следует, что
v(xS, S) ? v(xS1,S1) + v(xS2,S2).
Функционал затрат на управление будем называть субадди-
тивным, если он удовлетворяет следующему условию: при объе-
динении двух произвольных коалиций в одну и побуждении АЭ к
выбору тех же действий, что и ранее, затраты на управление не
выше чем сумма затрат на управление двумя коалициями по
отдельности. Таким образом, мы доказали следующий результат.
Утверждение 14. Функционал затрат на управление субадди-
тивен.
Качественно этот факт объясняется тем, что для меньшей
коалиции неопределенность относительно поведения АЭ, не
вошедших в ее состав, выше, следовательно центру приходится
гарантировать компенсацию больших затрат.
Утверждение 14 позволяет сформулировать задачу структур-
ного синтеза в терминах затрат на управление. Если не наложить
ограничений на значения затраты на управления, то в соответст-
вии с утверждением 13 максимальной эффективностью будет
обладать двухуровневая веерная структура. Действительно, мак-
симум эффективности будет определяться как
K* = max {f0(y) – v(y, I)}.
y?A'
В силу субаддитивности функционала затрат на управление
введение дополнительных центров, и даже разделение между
ними ресурса v(y, I), приведет к снижению эффективности. Необ-
ходимость введения нескольких внешних центров возникает, если
ни один из них не имеет возможности в рамках существующих
ограничений управлять сразу всем множеством агентов. Детали-
зируем задачу синтеза оптимальной двухуровневой структуры
(переход от двухуровневой к трехуровневой структуре и т.д.
осуществляется аналогично) с учетом ограничений на возможно-
сти центров по управлению.
62
Пусть для произвольной коалиции S ? I и для произвольного
вектора xS ? AS действий ее членов задан функционал (66) затрат
на управление. Пусть также имеются k центров, для каждого из
которых известны ограничения ci, i ? K = {1, 2, ..., k} максималь-
ных затрат на управление, которые он может нести13. Обозначим
? ? 2I – произвольное разбиение множества агентов на коалиции.
Тогда задача структурного синтеза будет заключаться в нахожде-
нии такого вектора x* ? A' действий всех АЭ, такого разбиения ?
множества агентов I, |?| ? k, и такого назначения центров, для
которых функция f0(x*) принимала бы максимальное значение и
затраты каждого центра на управление подчиненными ему АЭ не
превышали бы имеющегося у него ресурса, то есть v( x * , S) ? cS,
S
S ? ?.
Отметим, что сформулированная задача достаточно просто
решается для линейных ОС (сводится к транспортной задаче), так
как для них выше было показано, что затраты на управление
каждым АЭ не зависят от той коалиции, в которую он включен. В
общем случае задача структурного синтеза принадлежит к классу
сложных задач системной оптимизации и не может быть непо-
средственно сведена ни к одной из известных задач математиче-
ского программирования или исследования операций. Поэтому
рассмотрим эвристический метод ее решения.
Обозначим x* = arg max f0(y), то есть фиксируем вектор дей-
y?A'
ствий, доставляющий максимум критерию ЛПР, и рассмотрим
возможности по его реализации при заданных ограничениях.
Обозначим v(S) = v(ProjS x*, S), S ? I. Получили субаддитив-
ную функцию множеств, характеризующую минимальные затра-
ты на гарантированную реализацию соответствующей коалицией
оптимального с точки зрения ЛПР вектора действий. В этом
случае под задачей структурного синтеза можно понимать задачу,

13
Содержательно величина ci является индивидуальной характеристи-
кой i-го центра, отражающей его максимальные возможности по
управлению АЭ (квалификационные, информационные, ресурсные и др.
ограничения, сформулированные в величинах, имеющих ту же размер-
ность, что и затраты на управление).
63
заключающуюся в проверке существования, во-первых, разбие-
ния множества I не более чем на k непересекающихся14 подмно-
жеств и, во-вторых, назначения центров, удовлетворяющего
ресурсным ограничениям v( x * , S) ? cS, S ? ?. В случае если таких
S
разбиений и/или назначений несколько, можно выбирать, напри-
мер, то из них, которое максимизирует суммарный остающийся в
распоряжении центров ресурс ?(?) = ? (c S ? v ( S )) .
S ??
В заключение настоящего раздела рассмотрим частный слу-
чай однородных ОС (то есть ОС, в которых все АЭ одинаковы).
Обозначим vi(x*, S) = g(s), где g(s) – убывающая функция числа
s = |S| членов коалиции S ? I, i ? I. Очевидно, для однородных
ОС выполнено v(S) = s g(s), S ? I.
Обозначим w(s) = v(S), S ? I. Тогда задачу структурного син-
теза можно формулировать как нахождение: числа m ? k коали-
ций, их размеров {si}, и назначения15 qij ? {0; 1}, i = 1, m , j = 1, k
внешних центров по коалициям, таких, что:
(67) ? w( si ) qij > min
i, j

? qij ? 1, j = 1, k ,
(68)
i

? qij
(69) = 1, i = 1, m ,
j

(70) w(si) xij ? cj, i = 1, m , j = 1, k ,
m
? si
(71) = n.
i =1


14
Отметим, что до сих пор мы рассматривали задачу разбиения мно-
жества агентов на непересекающиеся подмножества, то есть каж-
дый АЭ может (и должен) быть подчинен одному и только одному
центру. Если вектор действий всех АЭ фиксирован, то можно искать
разбиения множества I и на пересекающиеся подмножества, удовле-
творяющие ресурсным ограничениям центров.
15
Положим, что xij = 1, если i-я коалиция подчинена j-му центру, и
qij = 0 в противном случае.
64
Содержательно задача структурного синтеза заключается в
распределении АЭ по коалициям (для однородных ОС это экви-
валентно определению числа и размеров коалиций), число кото-
рых не должно превосходить число внешних центров, и опреде-
лении кого из центров поставить во главе той или иной коалиции
с тем чтобы: затраты на управление были минимальны (см. (67)),
каждый центр был поставлен во главе не более одной коалиции
(условие (68)), во главе каждой коалиции был поставлен один и
только один центр (условие (69)), ресурсы каждого центра были
не меньше, чем затраты на управление подчиненной ему коали-
ции (условие (70)), и каждый АЭ вошел в точности в одну коали-
цию (условие (71)).
В общем случае (67)-(71) принадлежит классу сложных ком-
бинаторных задач. Для ее решения в случае большого числа АЭ и
больших ресурсов центров (оценка: w(1) << min {cj}) может
j =1,k
быть предложен следующий эвристический (не дающий в общем
случае оптимального решения!) алгоритм: упорядочить центры
по убыванию ресурсов и последовательно (до тех пор, пока не
"исчерпается" ресурс очередного центра – после этого переходить
к следующему центру в заданном их упорядочении) назначать АЭ
центрам, пока не будут распределены все АЭ, или пока не будет
использован весь имеющийся у центров ресурс. Другими слова-
ми, в первую очередь следует задействовать (и задействовать
максимально) центры, обладающие максимальным ресурсом
управления.


11. МОДЕЛИ ОГРАНИЧЕННОЙ РАЦИОНАЛЬНОСТИ
Рациональное поведение экономических агентов традиционно
моделируется их стремлением к увеличению значения некоторой
функции (функции полезности, выигрыша, целевой функции и
т.д.) [60, 91, 101, 104], определенной на множестве альтернатив,
которые может выбирать агент, и обстановок (внешних условий
его деятельности) [36]. При этом вводятся две гипотезы – гипотеза
детерминизма, заключающаяся в том, что агент стремится устра-
нить с учетом всей имеющейся у него информации существую-
щую неопределенность (относительно состояния природы или
65
параметров, выбираемых другими агентами), и гипотеза рацио-
нального поведения, заключающаяся в том, что агент (с учетом
всей имеющейся у него информации) выбирает действия, которые
приводят к наиболее предпочтительным результатам деятельности
[36, 77].
Рассмотрим одного агента (в одноэлементных моделях ин-
декс, обозначающий номер агента, будет опускаться), интересы
которого отражены его целевой функцией f(y), определенной на
множестве возможных действий: y ? A, f: A > ?1. Тогда множе-
ством рационального выбора будет множество действий, достав-
ляющих максимум целевой функции:
(72) P0(f(?), A) = Arg max f(y).
y?A
Например, в экономико-математических моделях в качестве
функции полезности (целевой функции фирмы) во многих случа-
ях выступает прибыль фирмы.
Принцип (72) принятия решений соответствует так называе-
мой классической рациональности. В работах Г. Саймона было
предложено рассматривать так называемые модели ограниченной
рациональности (ОР), то есть отказаться от предположения о
стремлении агента к достижению абсолютного максимума, заме-
нив его предположением о стремлении к достижению определен-
ного уровня полезности, быть может, зависящего от величины
оптимума [88, 112, 113].
В настоящем разделе описывается ряд моделей ограниченной
рациональности и обсуждается влияние предположений о рацио-
нальном поведении агентов на решения задач управления ОС и, в
частности – на решение задачи структурного синтеза.
Введем следующее предположение о целевой функции и до-
пустимом множестве: пусть f(?) непрерывна и вогнута, а множест-
во A выпукло и компактно. Очевидно, что в рамках этих предпо-
ложений множество P0(f(?), A) непусто.
Обозначим y* = arg max f(y). Для простоты будем считать,
y?A
что f(y*) ? 0.
Введем в рассмотрения три типа ограниченной рационально-
сти.

66
Первый тип ОР. Предположим, что агент стремится к обес-
печению некоторого минимального уровня индивидуальной
полезности U , то есть множеством рационального выбора можно
считать
(73) P1(f(?), A, U ) = {y ? A | f(y) ? U }.
Второй тип ОР. Предположим, что агент готов смириться с
потерями фиксированной величины ? ? 0 по сравнению с абсо-
лютным максимумом, то есть множеством рационального выбора
можно считать
(74) P2(f(?), A, ?) = {y ? A | f(y) ? f(y*) – ?}.
Отметим, что этот способ учета «нечувствительности» и по-
рогов различения агентов наиболее распространен в теоретико-
игровых моделях и при использовании в построении обобщенных
решений позволяет регуляризовать критерии оптимальности и
добиться устойчивости решения по параметрам модели
[25, 65, 71, 110]. Кроме того, данный тип представления рацио-
нального поведения согласован с моделями ОС, учитывающими
неопределенность [71, 72], в том числе – неопределенность целей
агента.
Третий тип ОР. Предположим, что агент готов смириться с
потерями, составляющими не более, чем фиксированную часть
? ? (0; 1] от максимального выигрыша, то есть множеством ра-
ционального выбора можно считать
(75) P3(f(?), A, ?) = {y ? A | f(y) ? (1 – ?) f(y*)}.
Неравенство в (75) можно записать в эквивалентном виде:
f(y*) – f(y) ? ? f(y*).
Введенные три типа ограниченной рациональности охваты-
вают большинство встречающихся на практике задач управления
ОС. Исследуем свойства множеств (73)-(75).
Очевидно, что в рамках введенных предположений ? U ? 0,
? ? 0, ? ? (0; 1] имеет место:
- P1, P2 и P3 – выпуклые компактные множества;
- P0 ? P1, P0 ? P2, P0 ? P3;
- ? U ' ? U , ?’ ? ?, ?’ ? ? выполнено
P1(f(?), A, U ) ? P1(f(?), A, U ' ), P2(f(?), A, ?) ? P2(f(?), A, ?’),
P3(f(?), A, ?) ? P3(f(?), A, ?’);
67
- P1(f(?), A, 0) = P2(f(?), A, 0) = P3(f(?), A, 0) = P0(f(?), A);
- для любого допустимого значения любого параметра
(U ? 0, ? ? 0, ? ? (0; 1]) существуют значения двух других пара-
метров, при которых множества (73)-(75) совпадают.
Содержательные интерпретации приведенных свойств оче-
видны и опускаются.
Последнее свойство позволяет говорить об эквивалентности
в определенном смысле трех типов ОР, однако, использование в
моделях определенного типа ОР должно быть обусловлено спе-
цификой конкретной модели (например, для первого типа, в
отличие от второго и третьего, не требуется знания абсолютного
максимума и т.д.).
Отметим, что существует целое семейство целевых функций,
имеющих одно и то же множество максимумов (72). Так, из тео-
рии полезности известно [91, 104], что целевая функция опреде-
лена с точностью до положительного линейного преобразования,
то есть для любого числа a и любого положительного числа b
функции f(?) и
g(y) = a + b f(y)
имеют одинаковые множества максимумов:
P0(f(?), A) = P0(g(?), A).
В то же время, не все типы ограниченной рациональности
обладают свойством инвариантности множества выбора относи-
тельно положительных линейных преобразований. Так, для пер-
вого типа ОР множество (73), определенное для функции f(?), не
изменится, если в определении этого множества для функции g(?)
изменить U на a + b U . Для второго типа ОР достаточно изме-
нить ? на b ?. Для третьего типа ОР найти подобной замены обще-
го вида не удается.
Рассмотрим как изменится определение равновесия Нэша (2),
сформулированное для классической рациональности, в рамках
того или иного типа ограниченной рациональности.
Напомним, что равновесие Нэша в предположении классиче-
ской рациональности определяется следующим образом. Для
каждого агента вычисляется его наилучший ответ на ту или иную
игровую обстановку: BRi(y-i) = Arg max fi(yi, y-i), y-i ? A-i, i ? I.
yi?Ai

68
Совокупность этих наилучших ответов определяет отображение
BR(y) = (BR1(y-1), …, BRn(y-n)), y ? A’. Равновесием Нэша называ-
ется точка x ? A’, удовлетворяющая уравнению x = BR(x). Следо-
вательно, E 0 ( ?1 ) = {x ? A’ | x = BR(x)}.
N

Определим для заданного уровня индивидуальной полезно-
сти U i множества Bi( U i ) = {y ? A’ | fi(y) ? U i }, BRi(y-i, U i )
= {yi ? Ai | fi(yi, y-i) ? U i }, i ? I, BR(y, U ) = (BR1(y-1, U1 ), …, BRn(y-
U n )), где U = ( U i )i ? I. Равновесием Нэша в рамках ОР1 можно
n,

считать x = BR(x, U ), то есть
(76) 1 E 0 ( ?1 , U ) = I Bi (U i ) = { x ? A’ | ? i ? I fi(x) ? U i },
N

i?I
то есть множество векторов действий агентов, каждый из которых
гарантирует каждому из агентов соответствующий уровень по-
лезности.
В рамках второго типа ограниченной рациональности опре-
деление равновесия Нэша (2) переходит в определение ?-
равновесия Нэша [107]:
(77) 2 E 0 ( ?1 , ? ) = {y ? A’ | ? i ? I, ? yi ? Ai
N

fi(yiN, y-iN) ? fi(yi, y-iN) – ?i},
где ? = (?1, ?2, …, ?n).
Аналогично определяется равновесие Нэша и в рамках
третьего типа ОР:
(78) 3 E 0 ( ?1 , ? ) = {y ? A’ | ? i ? I, ? yi ? Ai
N

fi(yiN, y-iN) ? (1 – ?i) fi(yi, y-iN)},
где ? = (?1, ?2, …, ?n).
Очевидно, что множества (77) и (78) содержат в себе «клас-
сическое» множество равновесий Нэша (2).
Определим оптимальные стратегии центра в игре типа Г2 с
побочными платежами, предполагая, что поведение АЭ описыва-
ется в рамках того или иного типа ОР.
Рассмотрим задачу синтеза оптимальной веерной структуры.
Если центр, которым назначен i-ый агент, имеет целевую функ-
цию (33), и использует управления (34), (35) по отношению к АЭ,
имеющим целевые функции (32), то по аналогии с тем, как это

69
делалось выше, можно доказать справедливость следующего
утверждения.
Утверждение 15. В структуре ?2i с побочными платежами иг-
рой Г2 реализуемы состояния ОС, являющиеся решением сле-
дующей задачи:
а) в рамках ОР1:
(79) ? f i ( x ) ? ?U i ;
i?I i?I
б) в рамках ОР2:
(80) ? ( f i ( x ) + ? i ) – ? L j ( x ?i ? j ) ?
j ?i
i?I

? max { ? f i ( y ) – ? L j ( y?i ? j ) };
y?A' i?I j ?i
в) в рамках ОР3:
(81) ? f i ( x ) – ? (1 ? ? j ) L j ( x ?i ? j ) ?
j ?i
i?I
? (1 – ?i) max { ? f i ( y ) – ? (1 ? ? j ) L j ( y ?i ? j ) }.
y?A' j ?i
i?I
Утверждение 15 включает утверждение 7 как частный случай
(при ? = ? = 0) и доказывается аналогично.
Отметим, что множество (79) имеет очень простую структуру
и, более того, можно сделать вывод, что реализуемое состояние
ОС в рамках ОР1 не зависит от того, кого из агентов назначить
центром.
Следствие. Если поведение агентов описывается первым ти-
пом ОР, то:
- реализуемыми в веерной структуре являются элементы сле-
дующего множества
(82) ? i ? I 1 E 2 ( ? 2i , U ) = {x ? A’ | ? f i ( x ) ? ?U i };
N

i?I i?I

- имеет место 1 E 0 ( ?1 , U ) ? 1 E 2 ( ? 2i , U
N N
) , то есть множество
состояний, реализуемых в веерной структуре, шире множества
равновесий в одноуровневой структуре;
- увеличение числа центров или уровней иерархии не изменя-
ет множества реализуемых состояний.

70
Таким образом, в ряде случаев введение гипотез (обоснован-
ность которых, естественно, следует проверять в каждом кон-
кретном случае) об ограниченной рациональности агентов позво-
ляет существенно упростить решение задачи структурного
синтеза. Например, в системах, поведение агентов которых опи-
сывается ОР1, достаточно ограничиться классом веерных струк-
тур, причем назначение центра может быть осуществлено произ-
вольно.


12. МЕХАНИЗМЫ УПРАВЛЕНИЯ В СЕТЕВЫХ
СТРУКТУРАХ

В предыдущих разделах задача структурного синтеза иссле-
довалась в рамках модели, в которой предпочтения агентов опи-
сывались "абстрактными" целевыми функциями, а структуре
соответствовало разделение агентов на множества, упорядочен-
ные в соответствии с последовательностью выбора стратегий.
В то же время, в теории активных систем и близких к ней на-
правлениях теории управления социально-экономическими сис-
темами разработано множество механизмов управления, ориен-
тированных на те или иные прикладные задачи и ситуации и
характеризуемых частным видом целевых функций, специфич-
ными информированностью и порядком функционирования.
Поэтому значительный интерес представляет рассмотрение меха-
низмов управления в сетевых структурах, под которыми будем
понимать задачи синтеза структур совместно с механизмами
управления из определенного класса.
Отметим, что имеющийся на сегодняшний день опыт анализа
специфики того или иного механизма управления в различных
организационных структурах ограничивается задачами идеально-
го агрегирования [3, 4, 7, 8, 73] и произвольной децентрализации
[70, 73] механизмов управления фиксированным набором АЭ при
условии, что объединение АЭ в группы и управление этими
группами производится внешними центрами (назначаемыми "со
стороны" (см. выше), то есть не из числа агентов). В то же время,
в задачах структурного синтеза (по крайней мере, в том их виде, в
котором они рассматривались выше) назначение управляющих
71
органов предполагается производить из числа агентов. Формули-
ровка и методы решения при этом могут быть использованы
аналогичные реализованным выше для задач структурного синте-
за.
Рассмотрим пример, иллюстрирующий приведенные выше
общие рассуждения о механизмах управления в сетевых структу-
рах.
Пример 7 (Модель внутренних цен). Пусть имеются n аген-
тов со следующими целевыми функциями: fi(?, yi, ri) = ? yi –
ci(yi, ri), i ? I, где ? – внутрифирменная цена единицы продукции,
выпускаемой агентами, yi – объем производства (выпуска) i-го
агента, ri – эффективность его деятельности, то есть параметр его
функции затрат ci(yi, ri), i ? I.
Содержательно, объединение агентов должно обеспечить
суммарный объем выпуска R, который может интерпретироваться
как внешний заказ. Пусть агенты имеют затраты типа Кобба-
Дугласа: ci(yi, ri) = ri ?(yi/ri), где ?(?) – монотонная выпуклая
функция. В случае, если назначается внешний центр, то миними-
зации суммарных затрат агентов соответствует назначение цены,
равной R / H, где H = ? ri (см. описание механизмов внутренних
i?I
цен в [68, 73]). Будем считать, что H ? R – в противном случае
управления не требуется.
Выберем для простоты ?(t) = t2/2 и рассмотрим задачу синте-
за оптимальной веерной структуры, в которой агент, назначенный
центром, обязан обеспечить реализацию заказа и выбирает опти-
мальную (с его точки зрения) цену (так называемую внутрифир-
менную цену), являющуюся единой для него и для его подчинен-
ных. Содержательно, центр в этом случае выступает в роли
посредника, а выигрыш каждого участника системы (агентов и
центра) определяется разностью между внутрифирменной стои-
мостью произведенной им продукции и его затратами. Обозначим
fik(?) – целевую функцию i-го агента при назначении центром k-го
агента, Y-k = ? y i , H-k = ? ri .
i ?k i ?k

<<

стр. 2
(всего 3)

СОДЕРЖАНИЕ

>>