Автоматика и телемеханика, № 6, 2019

Интеллектуальные системы управления,

анализ данных

Ф.И. ЕРЕШКО, д-р техн. наук (fereshko@yandex.ru)

(Вычислительный центр им. А.А. Дородницына ФИЦ ИУ РАН, Москва)

ИНФОРМИРОВАННОСТЬ И ДЕЦЕНТРАЛИЗАЦИЯ УПРАВЛЕНИЯ

Рассматривается задача управления организационной системой в усло-

виях внешней неопределенности. Исследуется вопрос о целесообразности

децентрализации управления в зависимости от доступного объема инфор-

мации о неопределенных факторах. Изучена качественная структура оп-

тимальных стратегий при централизованном и децентрализованном спо-

собах управления.

Ключевые слова: информационная теория иерархических систем, децен-

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

DOI: 10.1134/S0005231019060096

1. Введение

Проблемы информированности и децентрализации являлись одними из

главных в теории принятия решений и привлекали внимание мыслителей

всех эпох (см., например, [1]). В экономической теории к этим вопросам мож-

но отнести понятие “невидимой руки” рынка Адама Смита [2]. В математиче-

ской экономике, исследовании операций и управлении следует выделить две

фундаментальные работы К. Эрроу.

В модели конкурентного равновесия Эрроу-Дебре [3] отражена идея де-

централизации, поскольку доказана теорема о существовании конкретного

значения неконтролируемого фактора - цены, при которой в системе произ-

водители - потребители существует экономическое равновесие: оптимальный

спрос потребителей не превосходит оптимального предложения производите-

лей. Выбор цен не осуществляется централизованным действием. При этом

оптимальный выбор потребителей представляет собой оптимум Парето при

заданных функциях полезности.

В работе К. Эрроу по теории выбора [4] устанавливается роль диктатора -

высшего авторитета в группе активных участников при выборе ими альтер-

натив: его отсутствие при достаточно естественных предположениях о про-

филях предпочтений участников не приводит к выбору приемлемой для всех

альтернативы, что может рассматриваться как определенная иллюстрация

необходимости централизации в управлении.

156

В теории математического программирования одна из ключевых идей свя-

зана с декомпозицией исходной задачи (алгоритмы Данцига - Вулфа, Кор-

наи - Липтака) [5], особенно при больших размерностях задач, что с точки

зрения исследования операций и теории игр есть процедура децентрализации

в принятии решений, а в терминах экономических интерпретаций - переда-

ча властных полномочий при планировании производственной деятельности

от центрального органа к подчиненным подсистемам. Однако в этих рабо-

тах целевые установки подсистем возникали формально, как следствие фор-

мальных преобразований функций Лагранжа, в то время как цели подсистем

могут быть непосредственно (имманентно) присущи игрокам, и несовпадение

внутренних и внешне задаваемых целей может приводить к дискомфорту иг-

роков. Это несовпадение требует дальнейших исследований.

В играх многих лиц, в которых взаимодействия имели иерархический

характер, к фундаментальным работам следует отнести работы Гермейе-

ра Ю.Б. и его учеников, обзор которых содержится в монографии [6] и в

работах [7-9].

В работах Гермейера Ю.Б., Моисеева Н.Н. [10-13] данная тематика соста-

вила содержание информационной теории иерархических систем, в которой

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

фективного управления системой необходимо обрабатывать слишком боль-

шой объем информации о внешней среде. В этом случае лицо, принимаю-

щее решения, (Центр), может делегировать часть своих полномочий по вы-

бору управлений подчиненным. Разумеется, при этом подчиненные, выбирая

управления, могут (и будут) преследовать свои цели. Был поставлен вопрос:

при каких условиях Центр от такой децентрализации может выиграть?

Отметим также работы [14-17], в которых была развита техника формали-

зации конфликтных взаимодействий в условиях внешней неопределенности.

Рассмотренные там постановки стимулировали дальнейшие исследования в

этом направлении (некоторые результаты и дальнейшие ссылки можно найти

в [8, 9]).

В работах по теории активных систем и теории организационных систем

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

описания реальных процессов принятия решений и выбора различных меха-

низмов управления [18, 19].

Из известных зарубежных работ следует отметить близкие постановки

[20-27]. В них рассматривается взаимодействие выделенного игрока и группы

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

торов. Соответственно ими не используется техника анализа иерархических

игр.

Настоящая работа написана на основе идей Гермейера Ю.Б. и Моисее-

ва Н.Н. [10-13]. В ней исследуется вопрос о целесообразности децентрализа-

ции управления в зависимости от объема доступной оперирующей стороне

информации о “внешней среде”.

Для измерения количества информации используется способ, впервые

предложенный в [28]. Эффективность управления оценивается максималь-

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

157

Для простоты принимаются следующие предположения, обеспечивающие

наличие “веерной структуры” у рассматриваемой системы управления:

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

произведения нескольких более простых множеств;

• предполагается, что в децентрализованном варианте управление осу-

ществляется без обратной связи, т.е. элемент верхнего уровня не имеет

информации об управлениях, выбранных остальными элементами;

• при децентрализации управления считается, что элементы нижнего

уровня имеют полную и, следовательно, одинаковую информацию о

внешних неопределенных факторах.

В этих условиях оказывается, что элементы нижнего уровня принимают ре-

шения в условиях полной информации, и их поведение легко описать. Отказ

от любого из этих предположений приводит к тому, что у элементов нижнего

уровня появляется возможность и необходимость взаимодействовать между

собой. Как следствие возникает целый ряд интересных и важных постановок

задач. Но это уже тема для отдельного исследования.

2. Управляемая система

Рассмотрим простейшую модель принятия решений в условиях неопреде-

ленности. Управление рассматриваемой системой осуществляется путем вы-

бора управления w из множества W . Кроме того, на результат управления

влияет значение неопределенного фактора α, выбор которого не контроли-

руется лицом, принимающим решение. Параметр α может принимать любое

значение из множества A. Целью управления является максимизация значе-

ния g(w, α) функции g : W × A → R (как обычно R - множество действитель-

ных чисел).

Дабы избежать в дальнейшем малоинтересных технических проблем, сде-

лаем следующие стандартные предположения. Будем считать, что множества

W и A наделены топологиями и компактны. Функцию g будем считать непре-

рывной на декартовом произведении W × A.

Чтобы полученные далее результаты были более наглядны, предположим,

что рассматриваемая управляемая система “технологически структурирова-

на”. А именно, множество W может быть представлено, как декартово про-

изведение

W =U×V¹ ×V² ×...×Vⁿ.

Таким образом, любое управление w ∈ W может быть записано в виде w =

= (u, v¹, v², . . . , vⁿ), где u ∈ U, vⁱ ∈ V ⁱ, i = 1, . . . , n. Такую форму записи, ко-

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

3. Модель централизованного управления

Будем считать, что выбор управления w ∈ W осуществляет одно лицо,

принимающее решения, (Центр). При этом Центр может получать достовер-

ную информацию о реализовавшемся значении неопределенного фактора α,

158

но объем информации, которую он способен получить и своевременно обра-

ботать, ограничен. Предположим, Центр способен переработать l бит инфор-

мации. Выбор содержания этой информации - это право Центра. Предпола-

гается, что Центр действует в интересах всей системы, следовательно, g - это

функция выигрыша Центра.

Сделанные предположения могут быть формализованы следующим обра-

зом.

Введем обозначение. Здесь и далее Φ(X, Y ) будет обозначать семейство

всех функций, отображающих множество X в множество Y .

Поскольку Центру доступны l бит информации, эта информация может

быть закодирована словами s = (s₁, . . . , s_l), где каждый символ s_i, i = 1, . . . , l

принадлежит множеству {0, 1}. Таким образом, все сообщения о значении

неопределенного фактора, которые Центр может получить, принадлежат

множеству S = {0, 1}^l (декартовой степени множества {0, 1}).

Выше сделано предположение о том, что содержание информации, зако-

дированной словом s, (семантику сообщения s) выбирает Центр. Это значит,

что для каждого сообщения s Центр может указать некоторое множество

Π(s) ⊂ A так, что, получив сообщение s, Центр может быть уверен, что реа-

лизовавшееся значение α принадлежит множеству Π(s). Удобнее пользовать-

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

каждого значения α ∈ A центр вправе выбрать сообщение P (α) ∈ S, кото-

рое соответствует реализации значения параметра α. Таким образом, Центр

фактически выбирает функцию P ∈ Φ(A, S).

Кроме того, для каждого сообщения s ∈ S Центр вправе выбрать свое

управление w ∈ W , т.е., по сути, Центр выбирает функцию w_∗ ∈ Φ(S, W ).

Подводя итоги, скажем, что стратегиями Центра являются пары (w_∗, P ) из

множества Φ (S, W ) × Φ (A, S). Если Центр выберет такую стратегию (w_∗, P )

и реализуется значение неопределенного фактора α, то выигрыш Центра со-

ставит g(w_∗(P (α)), α).

Если значение неопределенного фактора α Центру заранее не известно, то

выбор стратегии (w_∗, P ) гарантирует ему получение выигрыша, равного

inf

g(w_∗(P (α)), α),

α∈A

а его максимальный гарантированный результат составит

R₀ =

sup

inf

g(w_∗(P (α)), α).

α∈A

(w∗,P )∈Φ(S,W )×Φ(A,S)

В предыдущей формуле присутствуют сразу два функциональных про-

странства. Это делает формулу неэффективной. Но это же обстоятельство

позволяет ее упростить.

Запишем последнюю формулу в виде

R₀ = sup

sup

inf

g(w_∗(P (α)), α).

α∈A

w∗∈Φ(S,W) P∈Φ(A,S)

159

Теперь можно поменять местами супремум и инфимум:

R₀ = sup

inf sup g(w_∗(s), α).

w∗∈Φ(S,W)

α∈A s∈S

Обозначим: m = 2^l. Слово s = (s₁, . . . , s_l) ∈ S можно естественным обра-

зом отождествить с натуральным числом из множества {0, 1, . . . , m - 1}, ко-

торое имеет двоичную запись s₁, . . . , s_l. В дальнейшем такое отождествление

будем делать без особых оговорок.

Обозначим: w_s = w_∗(s). Тогда максимальный гарантированный результат

Центра может быть записан в виде

R₀ =

sup

inf

sup

g(w_s, α).

(w₀,w₁...,wm-1)∈W^m

α∈As=0,1,...,m-1

Теперь стандартные теоремы анализа позволяют убедиться, что верхние

и нижние грани в предыдущей формуле достигаются.

Таким образом, приходим к следующему результату.

Теорема 1. Максимальный гарантированный результат Центра равен

R₀ =

max

min

max

g(w_s, α).

(w₀,w₁...,wm-1)∈W^m

α∈A

s=0,1,...,m-1

Оптимальная стратегия Центра в данной задаче существует. Построить ее

можно следующим образом.

Фиксируем любой набор (w₀, w₁, . . . , wm-1) ∈ W^m, доставляющий макси-

мум выражению

min

max

g(w_s, α),

α∈A

s=0,1,...,m-1

и положим w_∗(s) = w_s, s = 0, 1, . . . , m-1. Для каждого α ∈ A выберем любое

значение s, доставляющее максимум функции g(w_s, α), и положим P (α) =

= s. Тем самым будет определена функция P ∈ Φ (A,S). Стратегия (w_∗,P) -

искомая.

Замечание. Полученный результат показывает, что сложность решае-

мой задачи очень быстро растет с ростом объема информации l. Понятно,

что это объективная трудность, и дальнейшего упрощения формула из тео-

ремы 1 в общем случае не допускает. В самом деле, “большое” количество

управлений w₀, w₁, . . . , wm-1 так или иначе найти нужно, и от этого никуда

не денешься. Возникает соблазн искать эти управления как-нибудь “последо-

вательно”, но и это, вообще говоря, не получается. Из содержательных сооб-

ражений это достаточно ясно. Аналогичный формальный пример приведен

в [28]. Идеи, использованные при его построении, могут быть применены и в

данном, более простом случае.

4. Некоторые технические детали

Центральным моментом в доказательстве теоремы 1 явилось использова-

ние следующего известного факта: если f : X × Y → R, то

sup

inf

f (ϕ(y), y) = inf sup f(x, y)

ϕ∈Φ(Y,X)

y∈Y

y∈Y x∈X

(см., например, [29], с. 36).

160

Этот факт стал, наверное, первым инструментом в теории игр. В каком-

то виде он есть уже в книге [30]. В [31] он играет центральную роль. Он же

составляет, по существу, основу метода динамического программирования.

В терминах рассмотренной выше модели он может быть проинтерпретиро-

ван следующим образом. Если Центр не имеет никакой информации о неопре-

деленном факторе, то его максимальный гарантированный результат равен

max

min g(w, α).

w∈W

α∈A

Если же Центр получает точную информацию о значении неопределенного

фактора, то его максимальный гарантированный результат становится рав-

ным

sup

inf

g(ϕ(α), α) = min

max g(w, α).

ϕ∈Φ(A,W )

α∈A

w∈W

В данной статье рассматриваемый факт тоже будет активно использовать-

ся, но в несколько иной форме.

Пусть функция f определена на множестве X и принимает действи-

тельные значения. Тогда утверждение ∀x f(x) ≤ 0 равносильно неравенству

sup_x∈X f(x) ≤ 0. Аналогично, утверждение ∃x f(x) ≤ 0 эквивалентно усло-

вию inf_x∈X f(x) ≤ 0.

Со строгими неравенствами дело обстоит чуть сложнее. Утверждение

∀x f(x) < 0 превращается в такое условие: sup_x∈X f(x) ≤ 0, если верхняя

грань не достигается, и sup_x∈X f(x) < 0 в противном случае.

В задачах, связанных с иерархическими играми, строгие неравенства есте-

ственным образом появляются. И, если приходится использовать несколько

операторов супремума, подобного рода оговорки “накапливаются”. По этой

причине удобнее использовать кванторы, а не операторы супремума и инфи-

мума, а к болеe привычным терминам переходить уже в самом конце преоб-

разований.

В терминах кванторов обсуждаемый в данном разделе факт принима-

ет такую форму: если f : X × Y → R, то утверждение ∀ϕ ∈ Φ (Y, X) ∃y ∈ Y :

f (ϕ(y), y) ≤ 0 равносильно утверждению ∃y ∈ Y ∀x ∈ X f(x, y) ≤ 0.

Такого рода преобразования будут активно использоваться в дальнейшем.

5. Модель децентрализованного управления

Рассмотрим иную схему управления той же системой.

Предположим, что Центр передоверяет выбор управления vⁱ ∈ Vⁱ некото-

рому агенту, которого в дальнейшем будем называть агентом i (i = 1, . . . , n).

Согласно одному из предположений информационной теории иерархических

систем [10] у такого агента при этом появятся собственные интересы. При-

мем еще одну гипотезу, отражающую технологическую структурированность

управляемой системы. Будем считать, что интересы агента i описываются

стремлением к максимизации функции hⁱ(u, vⁱ, α) (т.е. не зависят от выборов

других агентов).

161

Право выбора управления u ∈ U Центр оставляет за собой. При этом, как

и в предыдущей модели, до окончательного выбора своего управления он мо-

жет рассчитывать на получение l бит информации о неопределенном факторе

и содержание этой информации вправе выбирать он сам.

Таким образом, стратегиями Центра будут пары (u_∗, P ) функций u_∗ ∈

∈ Φ(S,U) и P ∈ Φ(A,S). При этом выигрыши Центра и агентов будут опре-

деляться выражениями g(u_∗(P (α)), v¹, v², . . . , vⁿ, α) и hⁱ(u_∗(P (α)), vⁱ, α), (i =

= 1, . . . , n) соответственно.

Будем считать, что Центр обладает правом первого хода, т.е. он первым

выбирает и сообщает агентам свою стратегию (u_∗, P ) ∈ Φ(S, U) × Φ(A, S).

В таком случае агенту i в момент принятия решения известно значе-

ние неопределенного фактора α и стратегия (u_∗, P ), а значит, и значе-

ние u_∗ (P (α)), т.е. “физическое” управление, которое должен будет выбрать

Центр. Таким образом, для этого агента задача принятия решений превраща-

ется в задачу оптимизации. Считая его рациональным, можно предположить,

что он выберет свое управление из множества

{

}

(

)

(

)

BRi (u_∗,P,α) = vi ∈ V ⁱ : hⁱ

u_∗(P(α)),vⁱ,α

= max

hⁱ

u_∗(P(α)),vⁱ,α

vⁱ∈Vⁱ

Тогда один из основных принципов теории исследования операций предпи-

сывает Центру ориентироваться на максимальный гарантированный резуль-

тат, определяемый следующим образом.

Определение 1. Максимальным гарантированным результатом Цен-

тра в рассматриваемой модели называется число

R₁ =

sup

min

α∈A

v¹∈BR¹(u∗,P,α)

(u∗,P )∈Φ(S,U)×Φ(A,S)

min

g(u_∗ (P (α)) , v¹, . . . , vⁿ, α).

vⁿ∈BRⁿ(u∗,P,α)

Замечание. При сделанных выше топологических предположениях

максимум в определении множества BRⁱ (u_∗, P, α) достигается, а само это

множество компактно. Соответственно, достигаются и минимумы в определе-

нии максимального гарантированного результата. Доказательства этих фак-

тов стандартны, а потому опускаются.

Можно подойти к формализации тех же предположений с другой стороны.

Поскольку до выбора управления агента i стратегия Центра уже известна,

для него все управления разбиваются на два класса: выгодные и невыгодные.

Вполне естественно предположить, что это разделение происходит по поро-

говому принципу: существует такое значение λⁱ, что управления, выбор кото-

рых гарантирует получение выигрыша, большего или равного λⁱ, являются

выгодными, а все прочие - невыгодными. Считая агентов рациональными,

Центр может рассчитывать на то, что каждый из них выберет какое-то вы-

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

приходим к следующему определению.

162

Определение 2. Число γ называется гарантированным результатом

Центра в рассматриваемой модели, если существует стратегия (u_∗,P) и

для любого α ∈ A существуют числа λ¹, . . . , λⁿ такие, что выполняются

условия:

1^◦. для любого i с(ществует упра)ление vi0 ∈ Vi, для которого выполня-

ется неравенство hⁱ

u_∗ (P (α)),vi0,α

≥λⁱ;

(

)

2^◦. для любых

v¹,... ,vⁿ

∈ V 1 ×...×V ⁿ либо g(u_∗(P(α)),v¹,...,vⁿ,α) ≥

(

)

≥ γ, либо существует i = 1,... ,n, для которого hⁱ

u_∗ (P (α)) ,vⁱ,α

<λⁱ.

Точная верхняя грань множества гарантированных результатов называ-

ется максимальным гарантированным результатом Центра.

Временно обозначим максимальный гарантированный результат Центра в

смысле определения 2 через R1′.

Использование двух определений для одного понятия оправдывается сле-

дующим результатом.

Лемма 1. Имеет место равенство R1′ = R₁.

Доказательство леммы приводится в Приложении.

Определение 2 весьма удобно для работы. Перепишем его на языке ис-

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

выполняется условие

(

)

∃ (u_∗, P ) ∈ Φ (S, U ) × Φ (A, S) ∀α ∈ A∃

λ¹,... ,λⁿ

[

(

)

]

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_∗ (P (α)),vi0,α

≥λⁱ

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_∗ (P (α)),v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_∗ (P (α)),vⁱ,α

<λⁱ

Данное условие можно переписать в виде

(

)

∃u_∗ ∈ Φ (S,U)∃P ∈ Φ (A,S) ∀α ∈ A∃

λ¹,... ,λⁿ

[

(

)

]

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_∗ (P (α)),vi0,α

≥λⁱ

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×V² ×...×Vⁿ

(

)

(

)

)]

u_∗ (P (α)),v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_∗ (P (α)),vⁱ,α

<λⁱ

Теперь можно поменять местами кванторы общности и существования,

как это описано в разделе 4:

(

)

∃u_∗ ∈ Φ (S,U) ∀α ∈ A∃s ∈ S∃

λ¹,... ,λⁿ

[

(

)

]

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_∗ (s),vi0,α

≥λⁱ

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_∗ (s),v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_∗ (s) ,vⁱ,α

<λⁱ

163

Чтобы избавится от функции u_∗, поступим так же, как в разделе 3. Поло-

жим u_∗(s) = u_s. Тогда предыдущее условие можно переписать в виде

(

)

∃ (u₀, u₁, . . . , um-1) ∈ U^m∀α ∈ A∃j = 0, 1, . . . , m - 1 ∃

λ¹,... ,λⁿ

[

(

)

]

[

(

)

(1)

∀i∃vi0 ∈ Vⁱ : hⁱ

u_j,vi0,α

≥λⁱ

∀

v¹,v²,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_j,v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_j,vⁱ,α

<λⁱ

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

Теорема 2. Максимальный гарантированный результат Центра в рас-

сматриваемой модели равен точной верхней грани чисел γ, удовлетворяю-

щих условию (1).

Запишем полученный результат в более привычной форме, с оператора-

ми максимумов и минимумов вместо кванторов. Прямому применению идей,

изложенных в разделе 4, мешает операция дизъюнкции в формуле (1). Эта

трудность обходится следующим стандартным приемом.

Введем обозначение

{(

)

}

Λ (u, α, γ) =

v¹,... ,vⁿ

∈ V ¹ × ... × V ⁿ : g(u,v¹,...,vⁿ,α) < γ

Тогда условие (1) равносильно следующему:

(

)

∃ (u₀, u₁, . . . , um-1) ∈ U^m∀α ∈ A∃j = 0, 1, . . . , m - 1 ∃

λ¹,... ,λⁿ

[

(

)

]

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_j,vi0,α

≥λⁱ

[

(

)

(

)

]

∀

v¹,... ,vⁿ

∈ Λ(u_j,α,γ)∃i : hⁱ

u_j,vⁱ,α

<λⁱ

Теперь, заменяя кванторы операторами максимумов и минимумов, полу-

чим следующее утверждение.

Теорема 3. Число γ является гарантированным результатом Центра

в рассматриваемой модели тогда и только тогда, когда либо

{[

]

max

min

max

min

min max(hi(uj , v0i, α) - λi)

(u₁,...,um)∈U^m

α∈A

λ¹,...,λⁿ

j=1,...,m

i=1,...,nvi∈Vi

[

]}

inf

max

(λⁱ - h(u_j , vⁱ, α)

> 0,

(v¹,...,vⁿ)∈Λ(u_j ,α,γ)

i=1,...,n

либо

{[

]

max

min

max

min

min max(hi(uj , v0i, α) - λi)

(u₁,...,um)∈U^m

α∈A

λ¹,...,λⁿ

j=1,...,m

i=1,...,nvi∈Vi

[

]}

inf

max

(λⁱ - h(u_j , vⁱ, α)

= 0,

(v¹,...,vⁿ)∈Λ(u_j ,α,γ)

i=1,...,n

и инфимум в этой формуле не достигается.

164

Тот же результат можно переписать в несколько иной форме. Условие (1)

записывается в чуть более сложной, но эквивалентной форме

(

)

∃ (u₀, u₁, . . . , um-1) ∈ U^m∀α ∈ A∃j = 0, 1, . . . , m - 1 ∃

λ¹,... ,λⁿ

[

(

)

∃

v¹⁰,... ,vn0

∈ V ¹ × ... × V ⁿ∀i :

(

)

(

)

)]

(2)

hⁱ

u_j,vi0,α

≥ λⁱ&g

u_j,v¹⁰,... ,vn0,α

≥γ

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_j,v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_j,vⁱ,α

<λⁱ

Введем обозначения

{(

)

}

Λ (u, α, γ) =

v¹,... ,vⁿ

∈ V ¹ × ... × V ⁿ : g(u,v¹,...,vⁿ,α) ≥ γ

λ^i∗(u,α,γ) = max hⁱ(u,vⁱ,α).

vⁱ∈Λ(u,α,γ)

Чтобы первая часть условия (2) выполнялась, необходимо и достаточно,

чтобы были справедливы неравенства λⁱ ≤ λ^i∗(u, α, γ). А вторую часть усло-

вия (2) выполнить тем проще, чем больше значения λⁱ. Поэтому условие (2)

равносильно следующему:

∃ (u₀, u₁, . . . , um-1) ∈ U^m∀α ∈ A∃j = 0, 1, . . . , m - 1 :

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_j,v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_j,vⁱ,α

< λ^i∗(u_j,α,γ)

Далее, действуя, как и в предыдущем случае, получим следующее утвер-

ждение.

Теорема 4. Число γ является гарантированным результатом Центра

в рассматриваемой модели тогда и только тогда, когда либо

[

]

(

)

max

min

max

inf

max

λ^i∗(u_j, α, γ) - h(u_j, vⁱ, α)

> 0,

(u1,...,um )∈U^m

α∈A

j=1,...,m

(v¹,...,vⁿ)∈Λ(uj ,α,γ)

i=1,...,n

либо

[

]

(

)

max

min

max

inf

max

λ^i∗(u_j, α, γ) - h(u_j, vⁱ, α)

= 0,

(u1,...,um )∈U^m

α∈A

j=1,...,m

(v¹,...,vⁿ)∈Λ(uj ,α,γ)

i=1,...,n

и инфимум в этой формуле не достигается.

Замечание. Трудно сказать, какая из двух последних теорем удобнее

при практических вычислениях. Но в любом случае иметь две формы одного

результата не лишне.

Исходя из полученных результатов нетрудно построить и стратегию Цен-

тра, позволяющую наверняка получить выигрыш γ, если γ - гарантирован-

ный результат.

165

Фиксируем набор (u₀, u₁, . . . , um-1) ∈ U^m, существование которого гаран-

тировано условием (1). Положим u_∗(s) = u_s, s = 0, 1, . . . , m - 1. Пусть за-

дано произвольное α ∈ A. Тогда в силу условия (1) и выбора управлений

(u₀, u₁, . . . , um-1) найдутся значения λ¹, . . . , λⁿ, для которых

[

(

)

]

∃j = 0,1,... ,m - 1 :

∀i∃vi0 ∈ Vⁱ : hⁱ

u_j,vi0,α

≥λⁱ

[

(

)

(3)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_j,v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_j,vⁱ,α

<λⁱ

Фиксируем произвольное j, существование которого предусмотрено этим

условием, и положим P (α) = j. Функция P , а с ней и стратегия (u_∗, P ) будут

определены.

Пусть такая стратегия выбрана Центром и реализовалось некоторое зна-

чение α ∈ A. Тогда каждый из агентов выберет такое управление vi0, что

для соответствующего данному α значению λⁱ будет выполнено неравенство

(

)

hⁱ

u_∗ (P (α)) ,vi0,α

≥ λⁱ. Но тогда в силу последней строки условия (3) будет

справедливо неравенство g(u_∗ (P (α)) , v¹⁰, . . . , vn0, α) ≥ γ. Таким образом, неза-

висимо от значения α Центр получит выигрыш, не меньший γ, т. е. стратегия

(u_∗, P ) - искомая.

6. Явное выражение для максимального гарантированного результата

Обратимся к задаче вычисления максимального гарантированного резуль-

тата. Соответствующие формулы можно было бы вывести из полученных

выше результатов аналогично тому, как это было сделано в [28], но проще

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

подсказки.

При любом выборе стратегии (u_∗, P ) множество значений функции

u_∗ (P (α)) состоит из m точек (некоторые из которых могут совпадать). Фик-

сируем набор (u₀, u₁, . . . , um-1) ∈ U^m. Если Центр выберет управление u_s и

реализуется значение неопределенного фактора α, то агент i может выбрать

любое управление из множества

{

}

Eⁱ(u_s,α) = vⁱ ∈ Vⁱ : hⁱ(u_s,vⁱ,α) = max

hⁱ(u_s,ωⁱ,α)

ωⁱ∈Vⁱ

поэтому Центр вправе рассчитывать на получение результата

min

min g(u_s, v¹, . . . , vⁿ, α).

v¹∈E¹(us,α)

v²∈E²(us,α)

vⁿ∈Eⁿ(us,α)

Разумеется, управление u_s стоит выбирать так, чтобы максимизировать

эту величину, и при наихудшем значении α центр вправе рассчитывать на

результат

min

max

min

min g(u_s, v¹, . . . , vⁿ, α).

α∈A

s=0,1,...,m-1_v1_∈E1(us,α) v²∈E²(us,α)

vⁿ∈Eⁿ(us,α)

Выбор набора (u₀, u₁, . . . , um-1) ∈ U^m - это тоже прерогатива Центра. Та-

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

166

Теорема 5. Максимальный гарантированный результат Центра в рас-

сматриваемой модели равен

R₁ =

sup

min

max

min

min g(u_s, v¹, . . . , vⁿ, α).

α∈A

s=0,1,...,m-1_v1_∈E1(us,α)

(u₀,u₁,...,um-1)∈U^m

vⁿ∈Eⁿ(us,α)

Общая схема доказательства теоремы приведена выше. Несложные техни-

ческие детали опустим.

7. Сравнение двух способов управления

Естественным образом возникает вопрос о сравнении эффективности двух

способов управления. Поскольку исследование проводится в интересах Цен-

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

ный результат. Разумно проводить сравнение при одном и том же значении

объема доступной Центру информации l.

Конечно, ответ существенным образом зависит от того, насколько хорошо

интересы агентов согласованы с интересами Центра.

Начнем рассмотрение со случая, когда интересы Центра и агентов “сов-

∑

падают”, а именно g(u, v¹, . . . , vⁿ, α) =

hⁱ(u,vⁱ,α). В этом случае макси-

i=1

мальный гарантированный результат Центра при децентрализованном спо-

собе управления равен

R₁ =

max

min

max

g(u_s, v¹, . . . , vⁿ, α).

(u₀,u₁,...,um-1)∈U^m

α∈A

s=0,1,...,m-1

(v¹,...,vⁿ)∈V¹×...×Vⁿ

Поэтому R₁ ≥ R₀, причем в нетривиальных случаях неравенство строгое.

Теперь обратимся к случаю, когда интересы агентов и Центра “противо-

∑

положны”, т.е. g(u, v¹, . . . , vⁿ, α) = -

hⁱ(u,vⁱ,α) . В этом случае

i=1

R₁ =

max

min

max

min

g(u_s, v¹, . . . , vⁿ, α).

(u₀,u₁,...,um-1)∈U^m

α∈A

s=0,1,...,m-1

(v¹,...,vⁿ)∈V¹×...×Vⁿ

Следовательно, R₁ ≤ R₀ и опять в типичном случае неравенство будет

строгим.

Эти оценки не зависят от значения l. В промежуточных случаях такая

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

чать максимальные гарантированные результаты Центра при централизован-

ном и децентрализованном способах управления через R₀(l) и R₁(l) соответ-

ственно.

Сразу же можно отметить, что при увеличении l множество стратегий

Центра (в обеих моделях) расширяется. Поэтому обе величины R₀(l) и R₁(l)

с ростом l не убывают.

Сравнение этих величин удобно начать с рассмотрения “предельного” слу-

чая, когда Центр в момент выбора своего управления точно знает значение

167

неопределенного фактора. В этом случае его максимальный гарантирован-

ный результат при централизованном способе управления равен

R₀ (∞) = minmax

max

... max g(u,v¹,...,vⁿ),

α∈A

u∈U

v¹∈V¹

v²∈V²

vⁿ∈Vⁿ

а при децентрализованном составит

R₁ (∞) = minmax

min

min g(u, v¹, . . . , vⁿ).

α∈A

u∈U

v¹∈E¹(u,α)

v²∈E²(u,α)

vⁿ∈Eⁿ(u,α)

Следовательно, R₀ (∞) ≥ R₁ (∞), и опять-таки в общем случае неравен-

ство строгое.

Разумеется, при любом l имеют место неравенства R₀ (l) ≤ R₀ (∞) и

R₁ (l) ≤ R₁ (∞).

Использование термина “предельный” оправдано следующим результатом.

Лемма 2. Имеет место равенство lim

R₀(l) = R₀ (∞).

l→∞

Доказательство леммы приведено в Приложении.

Таким образом, если выполняется неравенство R₀ (∞) > R₁ (∞), то при

достаточно больших l будет справедливо неравенство R₀ (l) > R₁ (l).

Подведем итоги. В нетривиальных случаях картина такова. Если интересы

агентов “плохо согласованы” с интересами Центра, то всегда выгоднее центра-

лизованное управление. Если же интересы Центра и агентов “хорошо согла-

сованы”, то при больших значениях l выгоднее централизация управления, а

при малых значениях l предпочтительнее децентрализованное управление.

Точный результат можно сформулировать так.

Теорема 6. Все управляемые системы можно разбить на два клас-

са. Для игр одного класса для всех от l справедливо неравенство R₀(l) ≥

≥ R₁(l). Для игр второго класса существует такое натуральное L, что для

всех l ≥ L имеет место неравенство R₁(l) > R₀(l). Оба класса не пусты.

8. Заключение

Сформулирована задача о возможной децентрализации управления си-

стемой при наличии неопределенности и приводится ее решение на приме-

ре простой модели. Выводы последнего раздела дают начальные основания

для дальнейшего исследования в области централизации - децентрализации

в предложенной постановке.

Естественно рассмотреть постановки, когда подсистемы, подобно Центру,

недостаточно информированы о неконтролируемых факторах; здесь предпо-

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

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

гласованности интересов Центра и подсистем. На первый взгляд, достаточно

хорошо отражает факт согласованности наличие малой величины меры раз-

ности между функцией цели Центра и линейной свертки с весами системы

критериев подсистем. Однако такой подход должен содержать также гипоте-

зы и механизмы коалиционного решения подсистем, что представляет собой

совсем нетривиальный вопрос.

168

Возможно, удастся продвинуться в дальнейших исследованиях в случае

линейных зависимостей. Линейные задачи удобно рассматривать в стандарт-

ных постановках моделей линейных производственных процессов (Канторо-

вич - Купманс) при разных формах задания неопределенных факторов, опи-

раясь на развитый аппарат множителей и функций Лагранжа и теоремы ти-

па Куна - Таккера. К настоящему времени установлены различные варианты

эффективности процедур децентрализации в линейных случаях и построены

соответствующие примеры.

ПРИЛОЖЕНИЕ

Доказательство леммы 1. Докажем сначала неравенство R1′ ≥ R₁.

Фиксируем произвольное γ < R₁. Тогда существует стратегия Центра (u_∗, P ),

для которой

min

g(u, v¹, . . . , vⁿ, α) ≥ γ

α∈A

v¹∈BR¹(u∗,P,α)

v²∈BR²(u∗,P,α)

vⁿ∈BRⁿ(u∗,P,α)

и для любого α ∈ A выполняется условие

min

g(u, v¹, . . . , vⁿ, α) ≥ γ.

v¹∈BR¹(u∗,P,α)

v²∈BR²(u∗,P,α)

vⁿ∈BRⁿ(u∗,P,α)

(

)

Положим λⁱ = max

hⁱ

u_∗ (P (α)),vⁱ,α

, i = 1,...,n. Тогда для любого vi0

vⁱ∈Vⁱ

(

)

из множества BRⁱ (u_∗, P, α) выполняется условие hⁱ

u_∗ (P (α)) ,vi0,α

≥λⁱ

(для всех i = 1, . . . , n), следовательно, пункт 1^◦ определения 2 выполнен. Бо-

(

)

лее того, если hⁱ

u_∗ (P (α)) ,vⁱ,α

≥ λⁱ, то vⁱ ∈ BRi (u_∗,P,α). Поэтому если

(

)

неравенства hⁱ

u_∗ (P (α)) ,vⁱ,α

≥ λⁱ выполняются при всех i = 1,...,n, то

справедливо неравенство g(u_∗(P (α)), v¹, . . . , vⁿ, α) ≥ γ. Значит, выполняется

и пункт 2^◦ этого определения.

Таким образом, γ - гарантированный результат в смысле определения 2 и

потому R1′ ≥ γ. В силу произвольности γ справедливо нужное неравенство

R1′ ≥ R₁.

Докажем обратное неравенство R₁ ≥ R1′. Пусть γ - гарантированный ре-

зультат в смысле определения 2. Тогда существует такая стратегия (u_∗, P ),

что

(

)

[

(

)

]

∀α ∈ A∃

λ¹,... ,λⁿ

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_∗ (P (α)) ,vi0,α

≥λⁱ

[

(

)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_∗ (P (α)),v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_∗ (P (α)),vⁱ,α

<λⁱ

Фиксируем любую такую стратегию и произвольное α ∈ A. Для некоторых

λ¹,... ,λⁿ будет выполнено условие

[

(

)

]

∀i ∃vi0 ∈ Vⁱ : hⁱ

u_∗ (P (α)) ,vi0,α

≥λⁱ

[

(

)

(Π.1)

∀

v¹,... ,vⁿ

∈V¹ ×...×Vⁿ

(

)

(

)

)]

u_∗ (P (α)) ,v¹,... ,vⁿ,α

≥ γ ∨ ∃i : hⁱ

u_∗ (P (α)) ,vⁱ,α

<λⁱ

169

(

)

(

)

Если hⁱ

u_∗ (P (α)) ,vi0,α

≥λⁱ, то тем более max

hⁱ

u_∗ (P (α)),vⁱ,α

≥λⁱ.

vⁱ∈Vⁱ

Поэтому для любого vⁱ ∈ BRⁱ (u_∗, P, α) выполнено неравенство

(

)

hⁱ

u_∗ (P (α)) ,vⁱ,α

≥λⁱ.

Следовательно, в с (лу условия (Π.1), ес)и v1 ∈ BR1 (u∗, P, α) , . . . , vn ∈

∈ BRn (u_∗,P,α), то g

u_∗ (P (α)),v¹,... ,vⁿ,α

≥ γ. Значит,

min

g(u, v¹, . . . , vⁿ, α) ≥ γ,

v¹∈BR¹(u∗,P,α)

v²∈BR²(u∗,P,α)

vⁿ∈BRⁿ(u∗,P,α)

и в силу произвольности α

min

g(u, v¹, . . . , vⁿ, α) ≥ γ.

α∈A

v¹∈BR¹(u∗,P,α)

v²∈BR²(u∗,P,α)

vⁿ∈BRⁿ(u∗,P,α)

Тем более

R₁ =

sup

min

g(u, v¹, . . . , vⁿ, α) ≥ γ.

α∈A

v¹∈BR¹(u∗,P,α)

vⁿ∈BRⁿ(u∗,P,α)

(u∗,P )∈Φ(S,U)×Φ(A,S)

А поскольку γ - произвольный гарантированный результат, выполняется

неравенство R₁ ≥ R1′.

Лемма доказана.

Доказательство леммы 2. Фиксируем произвольное ε > 0.

Для любого α ∈ A найдется w ∈ W , для которого

g(w, α) > min

maxg(w, α) - ε = R0 (∞) - ε.

α∈A

w∈W

Поэтому открытые множества O (w) = {α ∈ A : g(w, α) > R₀ (∞) - ε} покры-

вают множество A. Но множество A компактно, следовательно, можно вы-

брать конечное число элементов w₀, w₁, . . . , w_p множества W так, что множе-

ства O (w₀) , O (w₁) , . . . , O (w_p) будут по-прежнему покрывать A.

Но тогда

min

max

g(w_s, α) > R₀ (∞) - ε

α∈A

s=0,1,...,p-1

и тем более

max

min

max

g(w_s, α) > R₀ (∞) - ε.

(w₀,w₁,...,wp-1)∈W^p

α∈A

s=0,1,...,p-1

А если l таково, что m = 2^l ≥ p, то

R₀(l) =

max

min

max

g(w_s, α) ≥

(w₀,w₁...,wm-1)∈W^m

α∈A

s=0,1,...,m-1

≥

max

min

max

g(w_s, α) > R₀ (∞) - ε.

(w₀,w₁...,wp-1)∈W^p

α∈A

s=0,1,...,p-1

В силу произвольности ε лемма доказана.

170

СПИСОК ЛИТЕРАТУРЫ

https://en.wikipedia.org/wiki/Decentralization

Блауг М. Путеводитель по “Богатству народов” / Экономическая мысль в ре-

троспективе. М.: Дело, 1994.

Алипрантис К., Браун Д., Беркеншо О. Существование и оптимальность кон-

курентного равновесия. М.: Мир, 1995.

Клима Р., Ходж Дж. Математика выборов. М.: МЦНМО, 2007.

Итеративные методы в теории игр и программировании / Под ред. Беленько-

го В.З. и Волконского В.А. М.: Наука, 1974.

Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976.

Ватель И.А., Ерешко Ф.И. Игры с иерархической структурой / Математиче-

ская энциклопедия. Т.2. М.: Сов. энциклопедия, 1979. С. 477-481.

Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в

эколого-экономических системах. М.: Радио и связь, 1982.

Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ конфликтных ситуаций в

системах управления. М.: Радио и связь, 1991.

10.

Гермейер Ю.Б., Моисеев Н.Н. О некоторых задачах теории иерархических си-

стем / Пробл. прикл. мат. и механики. М.: Наука, 1971.

11.

Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981.

12.

Моисеев Н.Н. Иерархические структуры и теория игр // Изв. АН СССР. Сер.

Техн. кибернетика. 1973. № 6. С. 1-11.

13.

Моисеев Н.Н. Информационная теория иерархических систем // Тр. I Всесоюзн.

конф. по исследованию операций. Минск: 1974. С. 95-99.

14.

Кукушкин Н.С. Об одной игре с неполной информацией // Журн. вычисл. ма-

тем. и матем. физики. 1973. Т. 13. № 1. С. 210-216.

15.

Ерешко Ф.И., Кононенко А.Ф. Решение игры с правом первого хода при неточ-

ной информации о цели партнера // Журн. вычисл. матем. и матем. физики.

1973. Т. 13. № 1. С. 217-221.

16.

Ватель И.А., Кукушкин Н.С. Оптимальное поведение игрока, обладающего

правом первого хода, при неточном знании интересов партнера // Журн. вы-

числ. матем. и матем. физики. 1973. Т. 13, № 2. С. 303-310.

17.

Кононенко А.Ф. Роль информации о функции цели противника в играх двух

лиц с фиксированной последовательностью ходов // Журн. вычисл. матем. и

матем. физики. 1973. Т. 13. № 2. С. 311-317.

18.

Бурков В.Н. Основы математической теории активных систем. М.: Наука, 1977.

19.

Новиков Д.А. Теория управления организационными системами. М.: МПСИ,

2005.

20.

Hurwicz L. On informationally decentralized systems / Decision and organization.

Amsterdam: North-Holland Press, 1972. P. 297-336.

21.

Itoh H. Incentives to help in multi-agent situations // Econometrica. 1991. V. 59.

No. 3. P. 611-636.

22.

Myerson R.B. Optimal coordination mechanisms in generalized principal-agent

problems // J. Mat. Econom. 1982. V. 10. No. 1. P. 67-81.

23.

Poitevin M. Can the Theory of Incentives Explain Decentralization? // Canad. J.

Econom. 2000. V. 33. P. 878-906.

24.

Coase R. The Problem of Social Cost // J. Law Econom. 1960. V. 3. P. 1-44.

25.

Fudenberg D., Tirole J. Game Theory. Cambridge: M.I.T. Press, 1991.

171

26. Melamud N., Mookherjee D., Reichelstein S. Hierarchical Decentralization of Incen-

tive Contracts // Rand J. Econom. 1995. V. 26. P. 654-672.

27. Alonso R., Dessein W., Matouschek N. When Does Coordination Require Centra-

lization? // Amer. Econom. Rev. 2008. V. 98. P. 145-179.

28. Горелов М.А. Максимальный гарантированный результат при ограниченном

объеме передаваемой информации // АиТ. 2011. № 3. С. 124-144.

Gorelov M.A. Maximal Guaranteed Result for Limited Volume of Transmitted

Information // Autom. Remote Control. 2011. V. 72. No. 3. P. 580-599.

29. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1983.

30. Bachet de Meziriac. Problemes plaisants et delectables, qui se font par les nombres.

Lyon, 1612.

31. Цермело Э. О применении теории множеств к теории шахматной игры / Мат-

ричные игры. М.: Наука, 1961. С. 167-172.

Статья представлена к публикации членом редколлегии М.В. Губко.

Поступила в редакцию 04.12.2017

После доработки 09.10.2018

Принята к публикации 08.11.2018

172