=Paper=
{{Paper
|id=Vol-2570/paper26
|storemode=property
|title=Information in hierarchical systems
|pdfUrl=https://ceur-ws.org/Vol-2570/paper26.pdf
|volume=Vol-2570
|authors=Michail Gorelov,Felix Ereshko
}}
==Information in hierarchical systems==
https://ceur-ws.org/Vol-2570/paper26.pdf
Information in Hierarchical systems
M.A. Gorelov[0000-0002-0965-5148], F.I. Ereshko[0000-0002-1732-2204]
Federal Research Center “Informatics and Control” of the Russian Academy of Sciences, Vavi-
lova 44-2, 119333, Moscow, Russia
fereshko@yandex.ru
Abstract. The paper discusses the decentralization of the organizational system
control in the presence of external uncertainty factors. The quantity of infor-
mation that he or she can timely receive is assumed to be limited.
Keywords: Decision making under uncertainty. Decentralization of control. In-
formation theory of hierarchical systems.
1 Introduction
Experience shows that, in practice, the control of rather complex organizational sys-
tems is based on the hierarchical principle. Hence, it can be concluded that decentral-
ized control is more efficient. However, it is rather difficult to explain the reason for
the effectiveness of such decentralization. Such explanation was proposed in the early
70s of the last century by Yu.B. Germeyer and N.N. Moiseev [1]. It consists in the
following.
Virtually always, the result of control depends not only on the controls selected by
the operating party, but also on external factors that are beyond the decision maker’s
control. Control will be effective if the decision maker correctly takes into account all
information about the external environment. But this is often impossible due to the
large quantity of such information. If the decision maker delegates some of his or her
decision-making powers to some agents, by joint efforts, they will be able to process
large amounts of information in a timely manner, thereby making the control more
efficient. However, there is another problem. Having the right to choose controls,
agents will have their own interests and choose control pursuing their own goals. This
may reduce the overall system control efficiency. However, if the interests of all
agents are well coordinated, it is still possible to benefit from the decentralization.
Currently, the ability to handle large amounts of information is rapidly increasing;
however, there is no obvious tendency to centralize the control of complex systems.
This is probably due to the simultaneous processes of complicating the ties both be-
tween the individual elements within a controlled system and the system’s ties with
the external environment. Therefore, the quantity of information necessary for effec-
tive control is also increasing. In addition, we need to somehow separate the essential
information from the non-essential one; moreover, the separation method also de-
pends on the quantity of information that can be processed in a timely manner.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0)
ICID-2019 Conference
2
At the verbal level, the above idea set forth by Yu.B. Germeyer and N.N. Moiseev
has been discussed rather widely. However, for a long time, it was not possible to
build formal mathematical models that allow for describing this effect. There are ob-
jective reasons for this.
Obligatory such a model should include:
– the description of several agents (including the operating party);
– the description of each agent’s capabilities and goals;
– the existence of external uncertainty;
– the description of each agent’s attitude towards uncertainty arising both from in-
sufficient information about the external environment and from unknown choices of
partners’ controls;
– a sufficiently detailed description of the agents’ awareness, allowing, among oth-
er things, to estimate the quantity of information processed.
Thus, the desired model shall be very complex.
It is worthwhile to dwell on the last item in this list. The very concept of “infor-
mation” is very complex and ambiguous. In some models of control decentralization,
we can be limited only by the description of the quantity of information; however, it
is not easy to do. There are several approaches to determining the quantity of infor-
mation [2]. This very fact suggests that, in some cases, each of them is not suitable for
modeling reality; therefore, the choice of the desired method is a non-trivial task. In
addition, each of the existing models of the quantity of information is quite complex;
hence, when incorporated it into the general decentralization model, we get a very
difficult object to study.
Probably, a model combining game-theoretic constructions with a quantitative de-
scription of information exchanges was proposed for the first time in [3]. It uses the
approach to determining the quantity of information that A.N. Kolmogorov referred to
as the combinatorial one. The same approach is used below.
This paper accepts the following structural assumptions ensuring the presence of a
“radial structure” in the control system under consideration:
– it is believed that the set of controls can be presented as a Cartesian product of
several simpler sets;
– it is assumed that, in the decentralized version, control is carried out without
feedback, i.e. the top-level element has no information about controls chosen by other
elements;
– with decentralized control, it is believed that the lower-level elements have com-
plete and, therefore, identical information about external uncertainty factor.
The rejection of any of these assumptions leads to the fact that the lower-level ele-
ments can and shall interact with each other. As a result, a number of interesting and
important problem statements have been created; but this is a subject for a separate
research.
3
2 Control System
Let us consider the following controlled system model. The decision maker may
choose any control w at his or her discretion from the set W . In addition to this
choice, the control result is influenced by some uncertainty factor from the set A ,
the value of which is behold the control of the operating party (the decision maker).
The control efficiency is estimated by value g (w, ) of the function g : W A → .
Let us assume that the goal of control is to maximize this value.
Let us make another assumption reflecting the concept of “technological struc-
turedness” of the controlled system under consideration. Let us assume that the set W
can be presented as a Cartesian product W = U V 1 V 2 ... V n . Then, every ele-
ment w W can be recorded as w = (u, v1 , v 2 ,..., v n ) , where u U , vi V i ,
i = 1, 2,..., n . We will use this form of recording where it is convenient, without spe-
cial reservations. In addition, we assume that, on the set A , the probabilistic measure
is given, which is known to the operating party.
We make the following standard assumptions. Let us assume that, on the sets
u U , vi V i , i = 1, 2,..., n and A , topologies are given in which these sets are com-
pact. Let us consider the function g as continuous in the Cartesian product topology
U V 1 V 2 ... V n A . Let us consider the measure as a Borel one.
We assume that the operating party has the opportunity to obtain information about
the realized uncertainty factor value, but the quantity of information that such party is
able to obtain and timely process is limited. Namely, let us assume that the operating
party can use l bits of information, and there are no other restrictions on the use of
such information.
The above can be formalized as follows. Let introduce a notation. Hereinafter,
( X , Y ) will denote the family of all functions maping the set X into the set Y .
The assumption made means that all information about the uncertainty factor, that
is available to the operating party, can be encoded with words s = (s1 , s2 ,..., sl ) from
zeros and ones of the l length. Let us denote the set 0,1 (the Cartesian degree of
l
the set 0,1 ) with the letter S . Since the operating party has no restrictions on ac-
cess to information about the uncertainty factor, the choice of “encoding method”
P : A → S would be its prerogative. In addition, depending on the information ob-
tained s S , the operating party has the right to choose any control w W . That
means, in fact, it can choose the function w* : S → W . If the operating party fixes the
encoding method P ( A, S ) and the control choice rule w* (S,W ) , and the
value of the indefinite factor A is realized, the operating party will receive the
( )
message P ( ) , choose the control w* ( P ( ) ) , and its gain will be g w* ( P ( ) ) , .
We will consider two control schemes of the described system. In the first of them,
the control w is selected centrally. In the second one, the decision maker delegates the
right to choose controls v i to n agents: the agent number i gets the right to choose
4
the control vi V i (i = 1, 2,..., n). The operating party (the Center) reserves the choice
of control u U . We believe that, at the time of decision making, agents know exact-
ly the realized value of the uncertainty factor .
The i agent’s right to influence the situation inevitably entails the appearance of
his or her own goals. The process of forming such goals is complex and insufficiently
studied. In this model, such goals are considered as exogenous. We assume that the
purpose of the agent i is described by the desire to maximize the value of the function
hi ( u, vi , ) . It is significant that this function depends on his or her own control, the
Center’s control, and the uncertainty factor; but it does not depend on choices of other
agents. We will assume that the functions hi are known to the Center. The functions hi
are considered to be continuous.
Let us consider two systems of models differing from each other by the attitude of
the operating party towards uncertainty.
3 Interval Uncertainty
First, let us consider the case where the operating party is careful in relation to uncer-
tainty.
In the case of centralized control, its maximum guaranteed result will be
R0 ( l ) = sup inf g ( w* ( P( )), ) .
( w* , P ) ( S ,W ) ( A, S ) A
For comparison, in the absence of restrictions on the quantity of information obtained,
the maximum guaranteed result is
R0 ( ) = sup inf g ( w# ( ), ).
( w# , P ) ( A,W ) A
Theorem 1. The following equalities are true:
R0 ( l ) = max min max g (ws , ),
( w0 , w1 ..., wm−1 )W m A s = 0,1,..., m −1
R0 ( ) = min max g (w, ).
A wW
In the case of decentralized control, under the assumptions made, the Center can as-
sume that agent i will choose its control from the set
(
BRi ( u* , P, ) = vi V i : hi u* ( P ( ) ) , vi , = max
i i
)
hi u* ( P ( ) ) , vi ,
v V
( )
therefore, the maximum guaranteed result of the Center will be
R1 (l ) = sup min 1 min ... n min g (u* ( P ( ) ) , v1 ,..., v n , ).
( u* , P ) ( S ,U ) ( A, S ) A v BR ( u* , P , ) v BR ( u* , P , )
1 n
5
In the model without restrictions on the quantity of information obtained, similar re-
sult is equal to
R1 () = sup min 1 min ... n min g (u# ( ) , v1 ,..., v n , ),
u# ( A,U ) A v BR ( u# , ) v BR ( u# , )
1 n
where
BRi ( u# , ) = vi V i : hi ( u# ( ) , vi , ) = max
i i
hi (u# ( ) , vi , ) .
v V
Theorem 2. We have the following equalities:
R1 = sup min max min min ... n min g (us , v1 , v 2 ,..., v n , ) ,
( u0 ,u1 ,...,um−1 )U m A s = 0,1,..., m −1 v E ( us , ) v E ( us , ) v E ( us , )
1 1 2 2 n
R1 ( ) = min max 1 min min ... n min g (u , v1 , v 2 ,..., v n ) ,
A 1 uU v E ( u , ) v 2 E 2 ( u , ) n
v E ( u , )
where
E i (us , ) = vi V i : hi (us , vi , ) = max
i i
hi (us , i , ) .
V
For comparison of the two control methods, let us note that the values R0 (l ) and
R1 (l ) do not decrease with increasing l . Of course, for any l , the following inequali-
ties are true: R0 ( l ) R0 ( ) and R1 ( l ) R1 ( ) . Besides, R0 ( ) R1 ( ) , and in
general, the inequality is strict. True is the
Lemma 1. The following equality holds lim R0 (l ) = R0 ( ) .
l →
This simple and seemingly purely technical result is the key to proving the follow-
ing substantive statement.
Theorem 3. All controlled systems can be divided into two classes. For games of
the first class, regardless of l , the following inequality is true: R0 (l ) R1 (l ) . For
games of the second class, there is such natural L that for all l L , there is true the
inequality R1 (l ) R0 (l ) . Both classes are not empty.
4 Stochastic Uncertainty
Now, let us assume that the operating party is risk neutral, that is, it focuses on the
mathematical expectation of its gain.
With centralized control method, the maximum expected result of the operating
party is, by definition, equal to
R2 ( l ) = sup g ( w ( P ( )) , )(d ) .
( w* , P ) ( S ,W ) ( A, S ) A
*
6
A similar result in the model without restrictions on the quantity of information ob-
tained is given by the condition
R2 () = max
w# ( A,W ) g (w ( ) , )(d ).
A
#
Theorem 4. The following equalities are true:
R2 ( l ) = max max g ( w , )(d ) , s
( w0 , w1 ,..., wm−1 )W m A s =0,1,..., m −1
R2 () = max g (w, )(d ).
wW
A
With decentralized control method, the maximum expected result of the Center is
determined by the condition
R3 ( l ) = sup 1
min
(u* , P ) ( S ,U ) ( A, S ) A v BR ( u* , P , )
1
... n min
v BR ( u* , P , )
n
( )
g u* ( P ( ) ) , v1 ,..., v n , ( d ) .
In the model without restrictions on the quantity of information obtained, this result is
equal to
R3 ( ) = sup min( ) ... min( ) g (u ( ) , v ,..., v , )( d ) .
1 n
#
u# ( A,U ) A v1Br1 u# , vn Br n u# ,
Theorem 5. We have the following equalities:
R3 (l ) = max max min ... n min g (us , v1 ,..., v n , )( d ),
(u0 ,u1 ,...,um−1 )U m A s = 01,..., m −1 v1E1 (us , ) n
v E ( us , )
R3 ( ) = max 1 min ... n min g ( u, v1 ,..., v n , )( d ).
1 uU v E ( u , )
n
v E ( u , )
A
It is easy to establish that, for any l, the following inequalities are true:
R2 ( l ) R2 ( ) , R2 ( l ) R2 ( l + 1) , R3 ( l ) R3 ( ) , R3 ( l ) R3 ( l + 1) and
R2 ( ) R3 ( ) .
n
Let assume that g (u, v1 , v 2 ,..., v n , ) = hi (u, vi , ) . Then, one can demonstrate
i =1
that R1(l) R0(l), and in non-trivial cases, the inequality is strict. Similarly, if
n
g (u, v1 , v 2 ,..., v n , ) = − hi (u, vi , ) , then R1 ( l ) R0 ( l ) and, in a typical case, the
i =1
inequality is strict.
The first hypothesis from the previous paragraph can be interpreted as a “very
good” coordination of interests of agents and the system as a whole. The second as-
sumption is interpreted as a “very bad” coordination of interests of the Center and
agents.
7
The analogue of Lemma 1 is as follows.
Lemma 2. We have the equality lim R2 ( l ) = R2 ( ) .
l →
True is the
Theorem 6. With a fixed quantity of available information, both the inequality
R2 ( l ) R3 (l ) and the opposite inequality R3 ( l ) R2 ( l ) can be true. However, with
any 0 , at large enough l , we have the inequality R2 ( l ) R3 (l ) − and, in a typi-
cal case, with large enough l , the inequality R2 ( l ) R3 (l ) is also true.
5 Conclusion
Qualitative conclusions, that can be made based on the study of both systems models,
can be formulated as follows.
In non-trivial cases, the picture is as follows. If the interests of agents are “poorly
coordinated” with those of the Center, a centralized control is always more profitable.
On the contrary, if the interests of the Centers and agents are “well coordinated”, then,
with large values of l , centralization of control is more profitable, and with small
values of l , a decentralized control is preferable.
In general, these conclusions are consistent with substantive ideas. In our opinion,
this suggests that models built reflect correctly the essence of the objects modeled.
Let us note, by the way, that the results of theorems 1,2,4, and 5 allow, at least in
principle, to separate the “essential” information from the “non-essential” one. Surely,
we are still far from getting any quantitative results, but the qualitative picture be-
comes clearer.
It is important to note that all results have been obtained with minimal “geometric”
constraints on the structure of the studied models.
The second of the considered model systems allows for using not the maximum,
but the “average” number of bits in the relevant message to estimate the quantity of
information, that is, for using the Shannon entropy. But the corresponding model has
not yet been studied.
The above gives reason to hope that the suggested approach can serve as a basis for
building models that allow to study issues of the optimal decentralization of the con-
trol basis for building models of complex organizational systems on a quantitative or
qualitative level.
References
1. Germeyer Yu.B., Moiseev N.N.: On some problems of the hierarchical system theory. In:
Problemy prikladnoy matematiki i mekhaniki. Nauka, Moskva, pp. 30–43 (1971).
2. Kolmogorov A.N.: Three approaches to the definition of the concept ‘quantity of infor-
mation’. In: Problemy Peredachi Informatsii, 1(1), 3–11 (1965).
3. Gorelov M.A.: Maximal guaranteed result for limited volume of transmitted information.
Automation and Remote Control. 72(3), 580–599 (2011).