<<
>>

3. ЗАДАЧА СТРУКТУРНОГО СИНТЕЗА

Выше были введены три типовые структуры: вырожденная, линейная и матричная. Возможны и другие (более или менее детальные классификации): например, в [1] выделяются следую-щие основные виды организационных структур промышленных фирм: иерархическая (которая порождается декомпозицией высшей цели организации на цели, подцели и т.д.), функциональная (декомпозиция производится на основании функций (исследование, производство, маркетинг и т.д.)), дивизиональные (декомпозиция по относительно независимым отделениям, каждое из которых может иметь ту или иную структуру), матричная (наложение «горизонтальной» ответственности руководителей проектов на функциональную структуру).
Существуют «переходные»

17

10 Символ "•" здесь и далее обозначает окончание примера, доказательства и т.д.

(31) fk = ?aiaSign(aii) + akk + ? a

ie( I\(Qk u{k}))uQ-u (Q+ \R+) ieR+knP+

Xi, У-i = х -i

ul, У -«- j = X-i-j, У, * Xj¦¦

произвольное, в остальных случаях

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

Перейдем к рассмотрению формальной (теоретико-игровой) модели структурного синтеза.

Рассмотрим множество I = {1, 2, ..., n} активных агентов (использование термина «агент» обусловлено, во-первых, тем, что в рамках сетевого взаимодействия каждый из субъектов имеет потенциальную возможность выступать как в роли центра, так и в роли АЭ, а, во-вторых, очень условной близостью рас-сматриваемой модели к многоагентным системам (multi-agent or agent-based systems) [99, 108, 109]). Предположим, что каждый агент имеет непрерывную целевую функцию f(y), отражающую зависимость его выигрыша от вектора действий У = (y1, У2, .¦¦' Уп) е A' всех агентов. Будем считать, что действие i- го агента принадлежит выпуклому компактному множеству Ai, и выполнена гипотеза независимого поведения [10, 75] (ГНП), в соответствии с которой A' = ^Ai .

isI

Совокупность {I, (f())ieI, (Ai)ieI} множества агентов, их целе-вых функций и допустимых множеств определяют игру Г0 в нормальной форме [36], в которой все агенты одновременно и независимо (кооперативные эффекты, если не оговорено особо, рассматривать не будем) выбирают свои стратегии [25, 36, 76, 107].

Введем ряд определений.

Выбор действия yid е Ai называется доминантной стратегией i-го агента, если

(1) "y-i е A-i, "yi е A, f(yd, y_) > f(yv y_),

где y-i = (yi, У2, ..., Уг-1, Уг+1, ¦¦¦, Уп) е a., = ^ AJ - обстановка игры

J *i

для i-го агента, i е I. Если каждый агент имеет доминантную стратегию, то их совокупность называется равновесием в доминантных стратегиях (РДС). Множество доминантных стратегий в

игре Г0 обозначим (pi).

В настоящей работе принята следующая система обозначений, отражающая зависимость равновесия от структуры: буква E обозначает равновесие (equilibrium), верхний индекс обозначает тип равновесия: "d" - РДС, "N" - Нэша и т.д., нижний индекс - тип игры: "О" - игра Г0, "1" - Г1, "2" - Г2 и т.д., в скобках указывается структура, для которой определяется равновесие.

Вектор действий У е A' называется равновесием Нэша, если (2) "i е I, "yi е A, f(yN, y/) > f(yv y_f). Множество равновесий Нэша в игре Г0 обозначим EN (p1).

Любое непустое подмножество S множества I, включая и само I, называется коалицией. Понятно, что для игры п лиц возможны 2п-1 коалиций.

Множество всех возможных коалиций обозначим 2I. Обозначим (y-S , yS) е A' ситуацию игры, в которой агенты, не входящие в коалицию S с I, выбирают действия yi (i е I\S), а агенты из S выбирают действия yj (j е S).

С итуация yж называется сильно равновесной по Нэшу, если

для любых коалиций S с I и любых yS е AS = ^ Aj найдется

jeS

SN SN

участник коалиции S (i е S), такой, что f(y ) > f(y-S , yS). Как видно из определения, сильное равновесие Нэша отличается от равновесия Нэша тем, что агенты не только поодиночке не могут увеличить свой выигрыш выходом из равновесия, но и произ-вольная их коалиция не может, отклоняясь от равновесия, увеличить этим одновременно выигрыш всех своих участников. Множество всех сильных равновесий Нэша в игре Г0 обозначим SN

Eo (Р1).

Ситуация yP е A' называется эффективной по Парето, если для любой другой ситуацииy ^У,y е A', найдется агент i е I, для

которого выполнено /(y) < /У). Множество всех эффективных ситуаций в игре Г0 обозначим EЦ (р;).

Довольно просто показать, что выполнены следующие соотношения:

Ed (pi) с E0N (pi), ESN (pi) с E0N (pi), ESN (pi) с E0 (pi). При всех привлекательных чертах сильного равновесия Нэ- ша, его использование ограничено тем, что даже в смешанных стратегиях оно существует не во всех играх, поэтому будем ориентироваться, в основном, на равновесие Нэша, используя РДС и сильное равновесие Нэша только если они существуют.

Введем в рассмотрение pm = (S,)i =1, m - множество упорядоченных разбиений множества I на т непересекающихся непустых подмножеств, объединение которых равно I, то есть

Si е 2 \ {0}, Si п Sj = 0, i, j = 1, т, U Si = I. Элемент pm e pm

i

будем называть структурой ОС или просто структурой (см. содержательные интерпретации ниже).

Число d(m, n) различных размещений n объектов по т «непустым» множествам можно вычислить рекуррентно:

m—1

d(m, n) = mn - ?C'm d(i,n). Следовательно, всего имеется

i=1

n

N(n) = ?d(m,n) вариантов структуры n-агентной системы, то

m =1

есть число вариантов различных структур быстро растет с увеличением числа (см. таблицу 1). Оценка сложности задачи синтеза может быть осуществлена в соответствии с результатами, приведенными в [37]. n 1 2 3 4 5 6 7 8 9 10 N(n) 1 3 13 75 541 4683 47293 545835 7087245 108 n 11 12 13 14 15 16 17 18 19 20 N(n) 109 1010 1011 1013 1014 1015 1017 1018 1020 1021 Табл. i. Число вариантов структуры n-агентной системы

Фиксация pm е задает разбиение множества агентов на m упорядоченных подмножеств, причем Si может интерпретироваться как множество агентов, находящихся на i-ом уровне иерархии, i = 1, m , которые условимся нумеровать сверху вниз, то есть самым высоким является первый уровень иерархии, самым низким - m-ый уровень.

Перейдем от игры Г0, описанной выше, к иерархической игре Г mj , в обозначении которой верхний индекс обозначает число

уровней иерархии в организационной системе (ОС), а нижний индекс j - «глубину рефлексии» в терминах теории иерархических игр [25]. Игра Г1 соответствует случаю, когда агенты, делающие ход раньше, не рассчитывают наблюдать выборы агентов, делающих ходы позже них, то есть игре Штакельберга. Игра Г2 соответствует случаю, когда агенты, делающие ход раньше, рассчитывают наблюдать выборы агентов, делающих ходы позже них, то есть первые могут выбирать свои действия как функции от стратегий последних, и т.д. - см. подробное описание метаигр в [25]. Игры более высоких порядков (j = 3, 4, ...) рассматривать в настоящей работе не будем (см.

сравнение эффективностей мета-игр в [25, 51]).

Установим следующее соответствие между типом игры и структурой ОС: все агенты знают целевые функции и допустимые множества друг друга, кроме того, агенты из множества Si (находящиеся на i-ом уровне иерархии и выбирающие свои стратегии одновременно и независимо) знают выборы всех агентов из

множеств (Sj)) < i, i = 1, m (как отмечалось выше, будем нумеровать Si в порядке убывания уровня иерархии). Таким образом, структура pm порождает m-шаговую иерархическую игру и на-оборот (см. также аналогии в информационных расширениях игр [51, 103]). При этом, в зависимости от конкретной структуры, заданной на одном и том же множестве агентов, каждый из них может выступать как в роли АЭ (находясь на самом нижнем уровне иерархии) или метацентра (находясь на самом высоком уровне иерархии), так и в роли центра промежуточного уровня иерархии.

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

Обозначим Ej(pm) с A' - множество равновесных (по Нэшу, если не оговорено другое) действий агентов в игре Г ™ , J = 1, 2,

разыгрываемой участниками структуры pm, т = 1,п ,f0(y) - критерий эффективности, отражающий предпочтения лица, принимающего решения (ЛПР), на множестве состояний ОС. Под состоянием ОС здесь и далее будем понимать вектор действий ее участников, то есть подмножество множества A'. Иногда, что будет каждый раз оговариваться особо, в состояние будем включать размер побочных платежей между участниками. В последнем случае состояние ОС однозначно определяет выигрыши (значения целевых функций) всех агентов.

Тогда задача структурного синтеза заключается в определении числа уровней иерархии т, правил взаимодействия агентов J, и таком распределении агентов по уровням иерархии (то есть в нахождении такой допустимой структуры ОС pm), которые мак-

симизировали бы критерий эффективности при условии, что агенты выбирают равновесные действия (использование максимума по множеству равновесий соответствует гипотезе благожелательности [36, 68] агентов по отношению к ЛПР):

(3) Kj(pm) = max /o(y) ® max .

y^Ej (pm) pmep,je{0,1,2}

Задача структурного синтеза в виде (3) является чрезвычайно трудоемкой - в ОС с n агентами для ее решения необходимо определить N(n) равновесий для каждого из трех возможных типов игр (j = 0, i, 2). Разработка общих (аналитических и вычислительных) методов ее решения является перспективной задачей будущих исследований. В настоящей работе мы исследуем ряд представляющих интерес как с теоретической, так и с практической, точек зрения частных случаев, допускающих получение простого (аналитического) содержательно интерпретируемого решения.

Обозначим, Sj(pm) - множество агентов, находящихся в структуре pm на j-ом уровне, j = 1, m, Lk(pm) = Ц Sj (pm) -

j=k+1, m

множество агентов, находящихся в структуре pm ниже k-го уровня, Gk(pm) = Ц Sj (pт) - множество агентов, находящихся в

j=й—1

структуре pm выше k-го уровня. Очевидно, что "pm е р,

" k = 1 , m Lk(pm) о1 Sk(pm) LJ Gk(pm) = I. Содержательно, Sk - множество равноправных между собой (в смысле момента выбора стратегий и информированности) агентов, находящихся на k-ом уровне иерархии, Gk - множество их «начальников», Lk - множество их «подчиненных». Рассмотрим три типа игр.

Игра Г о, разыгрываемая множеством агентов I, не зависит от структуры (отношений подчиненности), так как в ней все агенты принимают решения одновременно и независимо.

Игрой типа Г1 назовем игру, в которой стратегией i-го агента, независимо от того, какому уровню иерархии он принадлежит, является безусловный (то есть не зависящий от выборов других агентов, принимающих решения позднее) выбор элемента множества А^, i е I.

Игрой типа Г2 назовем игру, в которой стратегией i-го агента, принадлежащего Sk, то есть k-му уровню иерархии, является выбор функции u,: ^ AJ ® A,, i е I, то есть выбор элемента

JeLk

множества Ai, зависящий от действий, выбираемых агентами из множества Lk.

Определим равновесие в игре типа Г1, в которой, в том числе, агенты из множества Sm, то есть агенты, находящиеся на самом низком уровне иерархии, делают свой выбор, зная стратегии, выбранные агентами из множества Gm = I \ Sm. Будем считать, что они выберут равновесные по Нэшу действия, то есть действия из следующего множества:

(4) NE1(Sm, yGm) = {ySm е ASm | " i е Sm " y, е Ai

f,(yGm, ySm) > f,(yGm, ySm\y,)}, где yGm = (y,)i е Gm е AGm = П Ai - вектор действий агентов из

ieGm

множества Gm, ySm = (y,)i е Sm е ASm = П Ai - вектор действий

ieSm

агентов из множества Sm, ySm\yi - вектор ySm действий агентов из множества Sm, в котором действие i-го агента, i е Sm, заменено на

У,.

В настоящей работе принята следующая система обозначений равновесий в иерархических играх: "NE" обозначает равновесие Нэша (Nash Equilibrium), нижний индекс - тип игры: "О" - игра Г0, "1" - Г1, "2" - Г2 и т.д., в скобках указываются: множество агентов, равновесие игры которых определяется (например, Sm), и стратегии агентов (например, yGm), находящихся на более высоких уровнях иерархии, так как от стратегий последних зависит рассматриваемое равновесие.

Определим соответствие отбора равновесий (СОР) : NE1(L,, уа+1) ® NE^L,, уа+д, однозначно определяющее с точки зрения агентов из множества Si равновесные стратегии агентов из множества L, (при заданных стратегиях агентов из множеств Si и Gi; напомним, что в рамках принятой системы

обозначений Gi+1 = S, и G,), i = 1, m - 1. В качестве СОР может использоваться, например, применяемый агентами индивидуаль-

но принцип максимального гарантированного результата (МГР), или другие принципы - оптимистические оценки и т.д.

Агенты из множества Sm-i, то есть агенты, находящиеся на предпоследнем (снизу) уровне иерархии, делают свой выбор, зная стратегии, выбранные агентами из множества Gm-i, и рассчитывая (в силу знания всех допустимых множеств и целевых функций) на выбор агентами из множества Sm стратегий Ym-i(NEi(Sm, yGm). Таким образом, множество равновесий агентов (m-i)-ro уровня есть

(5) NEi(Sm-i, yGm-i) = {ySm-i е ASm-i l "i е Sm-i "у, е Аг fi^Gm-h ySm -i, Ym-i (NEi(Sm, yGm))) >

>/(yGm-i, ySm-i У i, Ym-i (NEi(Sm, yGm-i, ySm-ilyi))) }, где yGm-i = (y,)i е Gm-i е AGm-i = П Ai - вектор действий агентов

ieGm—1

из множества Gm-i, ySm-i = (y,)i е Sm-i е ASm-i = П Ai - вектор

ieSm—1

действий агентов из множества Sm-i, ySm-i\yi - вектор ySm-i действий агентов из множества Sm-i, в котором действие i-го агента заменено на У,.

Продолжая по аналогии, обозначим

NEi(L,, yGi+i) = { Yi(NEi(Si+i, yG+i)), Y1+i(NEi(S1+2, ya, Y(NEi(S1+h y Gi+i)))), ¦¦, Ym-2( - ), Ym-i(---))} е ^A, - множество равновесных

(с точки зрения агентов i-го уровня) действий агентов более низких уровней в зависимости от стратегий агентов i-го и более

высоких уровней, i = 1, m — 1.

Таким образом, равновесие игры агентов из множества Si можно записать в виде

NEi(S,, уа) = у, е AS, | " j е S, " у е Aj

fj(yGl, У, Y(NEi(Lv yG,+i))) >/(уоъ ys,lyj, Y(NEi(Lv ys\yj, yffl)))},

i = 1, m — 1.

Выбор агентами первого уровня действий из множества

NEi(Si, 0) = {ysi е Asi | " j е Si " yj е Aj

f(ysi, Yi(NEi(Li, ysi))) > /(ysilyj, Yi(NEi(Li, уяу)))}.

индуктивно задает множество Ef ( рm) равновесных состояний

системы со структурой pm: NE1(S2, NE1(S1, 0)) и т.д. Другими словами, игра типа Г1 является обобщение игры Г1 или игры Штакельберга на многоэлементный и многоуровневый случай.

Равновесие в игре типа Г2 строится более сложным образом, чем в игре типа Г1, поэтому исследуем его ниже для частного случая ОС с побочными платежами.

Прежде всего, рассмотрим случаи (классы исходных игр, то есть моделей агентов), в которых введение структуры не изменяет равновесия и, следовательно, не изменяет значения критерия эффективности.

Обозначим р1 - структуру, в которой все n агентов находятся на одном уровне иерархии (очевидно, что структура с m = 1 единственна).

Утверждение 1. Если в игре Г0 множество E^ (Р1) равновесий в доминантных стратегиях не пусто, то " m = 1, n, " pm K-1 (Pm) = max f0(y).

yzEd (ft)

Справедливость утверждения 1 следует из определения (1) РДС. Содержательно это утверждение означает, что, так как каждый агент выбирает свои стратегии независимо от выбора других агентов, то изменение последовательности выбора стратегий не изменит равновесия. Другими словами, системы, в которых существует РДС, неуправляемы в смысле K1().

Отметим, что существенным в утверждении 1 является невозможность выбора агентами действий, являющихся функциями от стратегий других агентов - как показывает приводимый ниже пример 1, в этом случае (качественно соответствующем игре Г2) системы, в которых существует РДС, управляемы в смысле K2().

Поясним последнее утверждение. В определении (1) доминантной стратегии i-го агента фигурирует произвольная, но фиксированная (то есть одинаковая в обеих частях неравенства), обстановка игры для этого агента. В игре типа Г2 на структуре pm, в которой i е Sk, J е Si, l < i, действие J-го агента является функцией от действия i-го агента у,. Поэтому оптимальная стратегия i-

го агента в этой игре может отличаться от стратегии, которая

была оптимальна для него в игре Г0 - может оказаться, что

Arg max /(y_4, y,, yj) n Arg max /(y_4, y,, uj(y,)) = 0.

y^A y^A

yiEA

Рассмотрим следующий пример, иллюстрирующий утверждение 1 в ОС с двумя агентами.

Пример 1 [76]. Пусть ОС включает двух агентов, целевые функции которых имеют вид : / = у, + a (i - y-i), у, е A, = [0; i], i = i, 2. В данной ОС в игре Г0 имеется РДС, в котором оба агента выбирают действия тождественно равные единице и получают единичные выигрыши. Равновесие и выигрыши в игре Г1 такие же.

Рассмотрим игру Г2. Пусть i-ый агент выбрал

При этом в случае, когда a-i > i агент -i выбирает нулевое действие, а при a-i ?i - единичное. Агенту i это выгодно при a >

Следовательно, игра Г2 (без побочных платежей) выгодна обоим агентам при выполнении условия a > i, i = i, 2. В этой игре они получают выигрыши {а}. Если условие a >i, i = i, 2, не выполнено, и побочные платежи запрещены, то каждый из агентов будет использовать доминантную стратегию, гарантирующую единичный выигрыш. Содержательно условие ai > i означает, что "вклад" оппонента в целевую функцию i-го агента не меньше, чем его собственный вклад.

Таким образом, если выполнено условие a > i, i = i, 2, то обоим агентам одинаково выгодно, чтобы кто-либо из них (или они оба) был центром (делал первый ход). Несколько забегая вперед, рассмотрим что произойдет, если допустить возможность осуществления побочных платежей (см. общие результаты об эффективности использования побочных платежей в [24, 25, 76], а также ниже), при которых целевые функции агентов имеют вид (если i-ый агент является центром) / = y, + a (i - y-i) - z,, /-i = y-

i + a-i (1 - y,) + z, i = 1, 2. Пусть первый агент выбирает единич-

й й fs i, У - i = О

ное действие и использует следующий платеж: z, = < .

[О, У - i * О

Тогда агент -i выберет нулевое действие при s, > 1. Следовательно, использование побочного платежа выгодно i-му агенту, если ai > 1. Область компромисса при этом определяется величиной Qi = a, -1. Таким образом, при выполнении следующего условия: max {a, а-г} > 1, которое является более слабым, чем условие a, > 1, i = 1, 2, хотя бы одному агенту выгодно быть центром и получить выигрыш a,. Агент, не являющийся центром, получает единичный выигрыш.

Если выполнено условие a, > 1, i = 1, 2, и разрешены побочные платежи, то возможна ситуация, в которой обоим агентам выгодно быть центром. При этом они начнут конкурировать за право быть центром. Победителем в этой конкуренции (диктатором) станет агент, имеющий большее значение параметра a,. Легко видеть, что конкуренция невыгодна диктатору, поэтому в случае a, > 1, i = 1, 2, использование побочных платежей нецелесообразно.

Мы рассмотрели два случая. В первом управление заключалось в выборе агентом, делающим первый ход, своего действия в виде функции от действия второго агента. Во втором случае от действия второго агента зависел размер побочного платежа, но действие первого агента было фиксировано. В общем случае первый агент может выбирать зависящим от действия второго агента и свое действие, и размер платежа [24, 25]. «1О

Итак, в настоящем разделе сформулирована в общем виде задача структурного синтеза. Приведенное выше построение равновесия в игре Гm свидетельствует о высокой вычислительной сложности этого класса задач. Поэтому рассмотрим ряд частных случаев задачи структурного синтеза, а именно - веерные структуры, линейные системы, системы с побочными платежами и др.

<< | >>
Источник: Новиков Д.А.. Сетевые структуры и орга-низационные системы. М.: ИПУ РАН (научное издание),2003. - 102 С.. 2003

Еще по теме 3. ЗАДАЧА СТРУКТУРНОГО СИНТЕЗА:

  1. 2.1 Организационное проектирование на основании использования типовых структурных схем
  2. 1. ВВЕДЕНИЕ
  3. 2. СЕТЕВОЕ ВЗАИМОДЕЙСТВИЕ: КАЧЕСТВЕННЫЙ АНАЛИЗ
  4. 3. ЗАДАЧА СТРУКТУРНОГО СИНТЕЗА
  5. 4. ВЕЕРНЫЕ СТРУКТУРЫ
  6. 8. ПОБОЧНЫЕ ПЛАТЕЖИ В ВЕЕРНЫХ СТРУКТУРАХ
  7. 9. ПОБОЧНЫЕ ПЛАТЕЖИ В ДВУХУРОВНЕВЫХ СТРУКТУРАХ
  8. 10. ПОБОЧНЫЕ ПЛАТЕЖИ В ИЕРАРХИЧЕСКИХ СТРУКТУРАХ
  9. 12. МЕХАНИЗМЫ УПРАВЛЕНИЯ В СЕТЕВЫХ СТРУКТУРАХ
  10. 13. ЗАДАЧА ПОСЛЕДОВАТЕЛЬНОГО СИНТЕЗА СТРУКТУРЫ СИСТЕМЫ
  11. 14. СТРУКТУРНЫЙ СИНТЕЗ И УПРАВЛЕНИЕ ПРОЕКТАМИ
  12. 15. ЗАКЛЮЧЕНИЕ
  13. 3. Особенности неоклассического синтеза
  14.   § 6*. ПОСТАНОВКА ПРИКЛАДНЫХ ЗАДАЧ ТЕОРИИ ИГР
  15. Конкурентная стратегия как синтез экономических инструментов
  16. КАК ВЫРАЖЕНИЕ СТРУКТУРНОЙ ОРГАНИЗАЦИИ ФОРМЫ СОБСТВЕННОСТИ
  17. ТЕСТЫ И ЗАДАЧИ ПО МАКРОЭКОНОМИКЕ
  18. Структурные цели