=Paper= {{Paper |id=Vol-3036/paper14 |storemode=property |title=Models of Decision Making with Limited Volume of Processed Information |pdfUrl=https://ceur-ws.org/Vol-3036/paper14.pdf |volume=Vol-3036 |authors=Vladimir I. Budzko,Mihail A. Gorelov,Felix I. Ereshko |dblpUrl=https://dblp.org/rec/conf/rcdl/BudzkoGE21 }} ==Models of Decision Making with Limited Volume of Processed Information== https://ceur-ws.org/Vol-3036/paper14.pdf

Models of Decision Making with Limited Volume of
Processed Information

Vladimir I. Budzko 1 , Mihail A. Gorelov 1 , Felix I. Ereshko 1
1
FRC IC RAS, 44-2 Vavilov St., M oscow, 119333, Russia
fereshko@yandex.ru

Abstract. A new class of game-theoretic models, the common feature of
which is the presence of limited volume of information exchanges between active
players, is considered. This makes it possible to describe more adequately the
actions of the subjects of socio-economic processes. It is shown that considering
such restrictions allows one to significantly expand the class of situations that
can be adequately described using game theory in normal form. Possible ways to
formalize the concept of "amount of information" based on the construction of
Andrey Kolmogorov and a new formalization of the concept of the maximum
guaranteed result are discussed. The theoretical review of the new results is car-
ried out considering the experience of using models and tools for ontological
support in the field of decision making. The influence of the volumes of the initial
data on the decision-making processes has been investigated. The application of
the outlined ideas in the information theory of hierarchical systems, developed at
the FRC IC RAS, is considered. The importance of considering limited amounts
of data in applied decision support systems is emphasized.

Keywords: Information Theory, Limited Amount of Data, Games in Normal
Form, Theory of Hierarchical Games, Information Theory of Hierarchical Sys-
tems.

1 Introduction

The approach and language of game theory [1,2] are widely used in the world when
creating decision support systems.
The three constituent parameters of an active agent's decision-making are as follows:

 goals of the agent, interests, motives, criteria for evaluating the results;
 a set of data, information about the state and actions of other subjects, as well as
about uncertain factors of the external environment, on the basis of which he makes
decisions;
 methods of action, strategies of behavior based on the available data.

The importance of input data in game-theoretic models was already identified in the
first works on game theory (for example, [1]). But in the transition to normal form, all
informational aspects turned out to be “hidden” in the complex structure of strategies.

Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).

187
The strategy began to be presented as “elementary” objects, and information indicators
went into the background.
A certain return to information indicators occurred independently in the theory of
metagames by N. Howard [3] and in the theory of hierarchical games by Yu. B. Germier
[4]. But in these theories, the sets of player controls and indefinite factors, as a rule,
were considered as infinite (most often it was assumed that these are compact subsets
of Euclidean spaces). The sets of strategies of some players were viewed as complex,
infinite-dimensional spaces. The use of such strategies implicitly involved the pro-
cessing of infinitely large amounts of data.
The theory of hierarchical games considers the problem of information support op-
timizing for each player who benefits from having as much information as possible.
However, a satiety effect can occur when increasing awareness beyond a certain limit
does not provide additional benefits. This limit is rarely reached in most cases due to
the large volume.
Data processing requires time and resource costs that the existing classical models
do not consider. The “content” of information in classical models was dete rmined by
the “rules of the game”. Players cannot influence these rules. Costs aside, the best so-
lution is to use all available data.
Therefore, in real conditions, it becomes necessary to explicitly consider the limit a-
tions on the amount of the transmitted data in the models. But this requires solving a
number of problems.

2 Amount of Informati on

Until recently, models that took into account somehow at least the restrictions on the
amount of the transmitted information were investigated only in the works of V. S.
Aliyev and A. F. Kononenko, see for example [5]. The authors considered two ways to
limit the amount of information. In the first, a set of “acceptable” methods was set par-
ametrically, and the optimal one was selected from them. In the seco nd, the amount of
information was characterized by the topological dimension of the possible messages
space.
The problem in the first setting is successfully investigated by standard methods of
analysis of hierarchical games. But the solutions found for su ch a problem are ex-
tremely irregular. First, the solution in a typical situation can vary greatly with arbitrar-
ily small changes in the parameters of the model. And secondly, discontinuous func-
tions, Peano curves and other set-theoretic “monsters” appear in the structure of the
solution itself. This is due to the inadequate way of setting restrictions on the amount
of the transmitted information [6–7].
The problem in the second setting was also solved under very general assumptions
[8] with a very beautiful mathematical result, which we will consider below. But, and
this method does not quite adequately describe the phenomenon under study.
One of the works of A. N. Kolmogorov on information theory [9] was called “Three
approaches to the definition of the concept of “amount of information”. And this work
is still relevant today. Each of the three approaches has limitations and can only be
compared at an informal level.

188
Game-theoretic models are more structured than models of information theory,
therefore, it was possible to identify not three, but eight meaningful statements (includ-
ing those already described). The most studied setting is in which the amount of the
transmitted information is characterized by the power of the possible messages set. It
is easy to find out that the optimal result for a typical case can be obtained for finite
sets of messages, so the amount of information can be measured simply by a natural
number. This allows us to identify a number of interesting qualitative features and ex-
pand the class of models available for research. Let's dwell on some of them.

3 Formalization Method

Let us describe the formalization of the simplest version of a two -person game with
feedback.
Consider a two-person game   U ,V , g , h , where U and V are compact metric
spaces, g and h are continuous functions from U V set of real numbers. Elements
of sets U and V are interpreted as controls of the first and second players. Their in-
terests are described by the desire to maximize the values of functions g and h re-
spectively.
Let us consider the following interaction scheme for players. The first player has the
right to ask his partner n questions about the chosen control v V and get truthful
answers to them. Each of these questions must have “yes” or “no” answer. The answer
“yes” will be coded with one, and the answer "no" with zero. The first player makes the
final choice of his control after receiving answers to his questions. But he pre-selects a
list of questions and a plan of his actions with all possible answers. This information
becomes known to the second player. Under these conditions, the second player can
unambiguously correlate his gain with the choice of his control, and therefore his be-
havior becomes predictable: he will choose controls according to the criterion of the
maximu m of his profit. Uncertainty remains only when there are several maximu m
points. We will assume that the first player is careful with respect to this uncertainty
and seeks to maximize his guaranteed result.
Let us give precise definitions. Each system of n questions of the type under con-
sideration corresponds to a set of 2n subsets

 X , X  ,  X , X  ,...,  X , X 
0
1
1
1
0
2
1
2
0
n
1
n (1)

of space V , paired. The set X t1 includes those and only those controls v V of the
second player when choosing which the question with a number t should be answered
“yes”. The set X t0 contains those controls that correspond to the answer "no" to the
question numbered t . Of course, the conditions must be met

X t0 X t1  , X t0 X t1  V , t  1,..., n. (2)

189
Each Boolean vector r   r1 , r2 ,..., rn  from the set N  0,1 can be associated with
n

n
the set X r  X trt . The first player can and should choose control u r U having re-
t 1

ceived answers to his questions  r1 , r2 ,..., rn  . Thus, the strategy of the first player is
determined by specifying 2n of sets (1) satisfying conditions (2) and m  2n of con-
trols u r U , r  N .
If the first player has fixed his strategy of this kind, and the second player chooses
control v V , then the players will receive the winnings g (u r , v) and h(u r , v) accord-
ingly, where the answer r is uniquely determined by the condition v  X r .
It is convenient to define the function P : V  N by the condition P(v)  r , if
v  X r and such function u* : N  U , that u* (r )  u r . Then the strategy of the first
player can be identified with a pair of functions  u* , P  , and the payoffs of the players
will be determined by the functionals g* ((u* , P), v)  g (u* ( P(v)), v) and
h* ((u* , P), v)  h(u* ( P(v)), v) .
Thus, we obtain a new game in normal form  = U,V,g,h, where U is the set
of all strategies  u* , P  , and functions g and h are defined as described above.
We can work with the game  in the same way as the game , for example, look
for the maximu m guaranteed result of the first player or a Nash equilibrium situation.
But you can get more meaningful res ults, because this game is endowed with a certain
additional structure.
Note that this structure has already taken into account the restrictions on the amount
of information processed by the first player. And the mapping P specifies the “content”
of the information it receives, and this mapping is selected by the first player himself.

4 Maximum Guaranteed Result

The simplest model of interest to us is a game of two persons of the Center-Agent type.
In this case, it is usually assumed that the Center has the right of the first move. And
then the only reasonable principle of optimality is the principle of the maximu m guar-
anteed result. Let us dwell on this simplest case in detail.
Traditionally, the maximu m guaranteed result is defined as follows .
Old definition. We fix a positive number  . Let us set B(u* , P) of rational responses
of the second player to the strategy  u* , P  by the following condition:


 B  u* , P   v V : h(u* ( P(v)), v)  max h(u* ( P( w)), w) ,
wV
 if the upper bound

sup h(u* ( P( w)), w) is reached;
wV



B  u* , P   v V : h(u* ( P(v)), v)  sup h(u* ( P(w)), w)  
wV
 otherwise.

190
The maximu m guaranteed result of the first player R is
R  sup inf g (u* ( P(v)), v),
vB ( u* , P )

where the upper bound is taken over the set of all its strategies  u* , P  .
An alternative definition can be formulated
New definition. The number  is called the guaranteed result of the first player if
there exist the number  and the condition u for which the following two conditions
are satisfied:

 there is such a strategy v  V for which h(u*(P(v)),v) ≥ ;
 for any strategy v  V either g(u(P(v)),v) ≥  or h(u(P(v)),v) < .

The exact upper bound for guaranteed results is called the maximu m guaranteed result.
Simple geometric reasoning shows that these two definitions are equivalent.
The interpretation of the new definition is as follows. The strategy u  allows us to
get the guaranteed result  if the entire set of strategies is split into two parts: the strat-
egies from the first part will not be chosen by the second player because he gets a small
payoff (h(u* (P(v)),v) < ), and for any choice of strategies from the second part, the
first player will receive at least . Of course, the second part must be non-empty, since
the second player must choos e some strategy.
The second point of the old definition is too cumbersome. Since games with re-
strictions on the amount of the transmitted information are much more complicated than
the classical models, it becomes too difficult to work with the old definit ion.
The new definition is noticeably simpler than the old one. This statement can be
given a precise mathematical meaning. If we write both definitions in a formal lan-
guage, for example, the language of predicate calculus, then the new definition will be
half the old one.
The transition to a formal language allows one to obtain quite interesting results us-
ing equivalent transformations of the corresponding formulas.
Some areas of research can be viewed from a unified position with a simple problem
statement. For example, the theory of games with uncertain factors was presented until
recently as a set of very complex problems that are not formally related to each other.
The author guessed the solution each time (and then proved its optimality). Moreover,
the structure of the solution turned out in a number of cases to be so complex that it was
almost impossible to guess it. Thanks to the new definition, this structure is formed
from purely formal calculations. In addition, it becomes possible to systematize t he
admissible formulations of the problem (according to the formulas of the propositional
calculus associated with them) and to assess the possibility of constructively solving a
particular problem.
Let us give an exact formulation of one of the results related to the simplest problem
posed above [10]. For example, if you write both definitions in some formal language,
say, the language of predicate calculus, then the new definition will be half the size of
the old one.
The transition to a formal language also provides a good method for obtaining rather
interesting results using equivalent transformations of the corresponding formulas.
Some areas of research can be viewed from a unified position with a simple problem
statement. For example, the theory of games with uncertain factors was presented until

191
recently as a set of very complex problems that are not formally related to each other.
The author guessed the solution each time (and then proved its optimality). Moreover,
the structure of the solution turned out in a number of cases to be so complex that it was
almost impossible to guess it. Thanks to the new definition, this structure is formed
from purely formal calculations. In addition, it becomes possible to systematize the
admissible formulations of the problem (according to the formulas of the propositional
calculus associated with them) and to assess the possibility of constructively solving a
particular problem.
Let us give an exact formulation of one of the results related to the simplest problem
posed above [10].
Theorem. Let

u 0U u1U u m1U 

c( )  supsup... sup sup min sup max min h(u r , v)   ,
vV rN

vV rN

inf max max  g (u r , v)   ,   h(u r , v) 

The maximu m guaranteed result of the first player in the game  is the smallest
solution to the equation c( )  0 .
This interpretation determines the way of performing the proof of the theorem. First,
it is necessary to carry out fairly obvious transformations of the formula of the predicate
calculus, which describes a new definition of the guaranteed result, and then replace
the quantifiers of existence and generality (and the operation of disjunction and con-
junction) with the operators of maximu m and minimum in the resulting formula with
inequalities. The descriptions of these simple transformations are too long to fit in this
article.
Thus, the optimal strategy of a top-level player, characteristic of hierarchical games,
is as follows: the second player, depending on the choice made, either punishes his
partner or maximizes his own payoff. The punishment can be used in all cases in games
without restrictions on the amount of the transmitted information, except for one. this
“management style” is not always effective in practice. The situation is noticeably sim-
plified in games with restrictions on information exchanges. In this case, the relation-
ship between the “policy of the stick” and the “policy of the carrot” is determined to a
large extent by the complexity of the corresponding tasks (and the concept of complex-
ity can be precisely defined in this context) [10].

5 Some New Problem Statements

If the amount of processed information is not limited, then a simple optimal solution is
to process all available information. If it is possible to estimate the amount of infor-
mation received by the player, then it can be used to estimate the costs of obtaining and
processing it and take them into account in the player's objective function. Models of
this type can be constructed and investigated [11].

192
Until recently, the main focus was on models in which the top -level player receives
only reliable information. This is no coincidence, since it can be shown that the appear-
ance of the possibility of obtaining inaccurate information in games without external
uncertainty does not increase the maximum guaranteed result of the top -level player.
The situation when the reliability of the information received by the player of the
upper level is guaranteed corresponds to the case when he himself "extracts" infor-
mation about the actions of the partner. In practice, it is much more common to find
cases when lower-level players submit reports on their activities upstairs, which may
contain incorrect information.
Information can be corrupted during transmission (undetected integrity violation). If
a “part” of the transmitted information is distorted and the player receiving it does not
know which part turned out to be distorted, then it is not possible to obtain a meaningful
formal description of such a situation if models are used without restrictions on the
amount of the transmitted information.
It is possible to implement both interval and stochastic versions o f the model in the
case of games with limited volumes of transmitted information, [12–13]. The problem
of calculating the maximu m guaranteed result of the operating party can be solved in
both versions. And the obtained results have a fairly reasonable int erpretation.
Another situation is when the player of the lower level deliberately distorts infor-
mation about his actions. When the amount of information to be transmitted is limited ,
the top-level player can “selectively check” the validity of the transmitted messages. In
this case, conditions arise for setting various tasks that provide an effective solution
[14], including the identification of corruption schemes.

6 Information Theory of Hierarchical Systems

Yu. B. Germeier and N.N. Moiseev [15] already noted in one of the first works on the
information theory of hierarchical systems that a hierarchy arises when the amount of
information required for effective management of the system turns out to be too large
to could be processed "in real time". At the same time, it is necessary to take into ac-
count that as soon as some element of the system receives the right to choose controls,
it immediately has its own interests, which do not always coincide with the interests of
the system as a whole. Thus, there are two trends. The possible discrepancy between
the interests of the elements speaks in favor of the advisability of centralizing manage-
ment, and the lack of information leads to the need to decentralize management.
On a qualitative level, this was already clear in the early seventies of the last century.
But it was not possible to construct quantitative models for a long time precisely be-
cause of the lack of a measure of the amount of information.
It is possible to follow the path outlined above. Let us consid er the Center – Agent
system (or Agents) but in the presence of external uncertain factors and suppose that
the agents have accurate information about the realized values of the uncertain factors.
In addition, we will assume that the Center can also receive information about uncertain
factors but to a limited extent (the amount of information can be defined as in Section
3).

193
The two control schemes can be compared. In one, the Center concentrates in its
hands the right to choose all departments. In another, it delegates the right to choose
certain controls to agents.
It turns out that all control systems are divided into two classes. The first class in-
cludes systems for which a centralized management method is more preferable for the
Center, regardless of the amount of information available to it. The existence of such
systems is not surprising. The second class includes systems in which, with large
amounts of information available to the Center, a centralized management method is
beneficial, and with small amounts, a decentralized management method becomes more
preferable.
Analysis of examples shows that the feasibility of decentralization of management
is largely determined by the degree of coordination of interests of the Center and the
Agents. True, today there is no formal definition of the concept of “the degree of con-
sistency of interests”.
Details can be found in [16,17]. In the first of them, the effectiveness is assessed by
the guaranteed result of the Center. In the second, it is assumed that the set of uncertain
factors is endowed with a probabilistic measure, and the control efficiency is estimated
by the mathematical expectation of the Center's payoff relative to this measure.

7 Other Ways to Quantify Information

Let us dwell on two alternative ways of defining the concept of “amount of infor-
mation”.
In Section 3, we assumed that information is encoded by words in the alphabet {0,1}
of the same length. It is also possible to consider the case when words are used, the
length of which does not exceed a given value. This case can easily be reduced to the
one already considered. But it can be assumed that many factors about which infor-
mation is transmitted are endowed with a probabilistic measure. Then, as a measure of
the amount of information, you can us e the mathematical expectation of the length of
the word that the Center will receive. This approach was proposed by K. Shannon at
the dawn of information theory.
With such a definition of the amount of information, all the tasks discussed above
can be set. True, the technique for solving the problem of centralized control from the
previous section has been developed so far [18].
The second way to determine the amount of information has already been mentioned
above. It is largely associated with the huge amounts of information processed in the
management of modern complex systems. Let us suppose that when managing a sys-
tem, 1 terabyte of information is used. It is clear that the situation will essentially not
change if we increase this volume by 1 megabyte or decrease it by 2 kilobytes. From
what has been said, it is clear that with such volumes, ordinary numbers are not very
suitable for measuring the amount of information. We need to look for some kind of
alternative.
We can go the traditional way and replace a large finite set with some kind of con-
tinuum and use the “size” of this continuum as a measure of the amount of information.
It is quite natural, for example, to consider this continuum endowed with topology and
use its dimension as a “size”. One of the models of this kind can be found in [8].

194
8 Conclusions

A new concept of the maximu m guaranteed result is introduced, which allows finding
solutions to problems that are characterized by restrictions on the amount of data avail-
able for decision-making. This concept correlates with the classical one (G. von
Stackelberg and Yu.B. Germeier), but it is simpler and more convenient than the latter.
An example of calculating the maximu m guaranteed result in the simplest problem with
exchanges of finite amounts of data is given. The structure of optimal strategies for this
problem is more similar to the strategies of the players used in practice than to the
strategies in traditional problems of the theory of hierarchical games. Variants of the
model are considered, in which distortions of the transmitted information are possible.
Three versions of such models have been investigated: when information is distorted
uncontrollably, distorted randomly, or distortion occurs as a result of purposeful actions
of one of the players.
The outlined ideas make it possible to build methods for solving applied problems,
including in conditions of high external uncertainty, which is typical for problems in
agricultural production, where, for example, data on weather conditions are important.
The use of game theory in decision-making tasks allows us to consider the need for
coordinating centralization and decentralization in making strategic decisions in agri-
cultural production, where centralized coordination is needed in the processin g of large
amounts of data generated by a large number of small producers. The situation is similar
to the one to which Klaus Schwab drew attention [19]: “Today the situation is funda-
mentally different, over the past decades (in the Western world) the role of the state has
significantly decreased. This situation needs to change because it is difficult to imagine
how an exogenous shock of such magnitude as that caused by COVID 19 can be dealt
with purely market-based solutions.”

Acknowledgement. This work was supported by a grant from the Ministry of Science
and Higher Education of the Russian Federation, internal number 00600/2020/51 89 6,
agreement No. 075-15-2020-914.

References

1. Von Neumann, J., M orgenstern, O.: Theory of games and economic behavior. Princeton
university press, Princeton (1953).
2. Shubik M . Game-Theory Approach to Political Economy. London (1984).
3. Howard, N.: Paradoxes of Rationality: Theory of M etagames and Political Behavior. MIT
Press, Cambridge M ass. (1971).
4. Germeier, Yu. B.: Nonantagonistic games.D. Reidel Publishing Co., Dordrecht (1986).
5. Aliev, V. S., Kononenko, A. F.: Aggregation in dynamic games. Comput. M ath. M ath.
Phys. 35(8), 997–1008 (1995).
6. Gorelov, M .A.: Design of rational data exchange procedures in the hierarchical two-player
game: a parametric formulation. Autom. Remote Control 64(9), 1455–1463 (2003).
7. Gorelov, M .A.: Linear Aggregation of Information in Hierarchical Games. Autom. Remote
Control 65(11), 1808–1816 (2004).

195
8. Gorelov, M .A.: Topological Statement of the Information Aggregation Problem in Hierar-
chical Games. Autom. Remote Control 82(2), 308–323 (2021).
9. Kolmogorov, A.N.: Three approaches to the definition of the concept of the quantity of in-
formation. Problemy peredachi informatsii 1(1), 3–11, (1965).
10. Gorelov, M .A.: M aximal guaranteed result for limited volume of transmitted infor-
mation. Autom. Remote Control, 72(3) 580–599 (2011).
11. Gorelov, M .A.: Games with costly information transfer. Large-scale systems control
49, 37–56 (2014).
12. Gorelov, M .A.: A game with errors in information transmission. Autom. Remote Con-
trol 73(12), 2059–2070 (2012).
13. Gorelov, M .A.: Games with random errors of information transmission. Autom. Remote
Control 76(12) 2201–2215, (2015).
14. Gorelov, M .A.: Hierarchical games with deliberately distorted information. Autom. Remote
Control 77(4), 629–639 (2016).
15. Germeier, Yu.B., M oiseev, N.N.: On some problems in the theory of hierarchical systems.
In Problems of applied mathematics and mechanics, pp. 30–43. Nauka, M oscow (1971).
16. Ereshko F.I., Gorelov, M .A.: Awareness and Control Decentralization. Autom. Remote
Control 80(6), 1109–1122 (2019).
17. Ereshko F.I., Gorelov, M .A.: Awareness and Control Decentralization: Stochastic Case. Au-
tom. Remote Control 81(1) 41–52 (2020).
18. Gorelov, M .A.: On a quantity of information required for efficient control. Large-scale sys-
tems control 88, 41–68 (2020).
19. Klaus Schwab, Thierry M alleret. Covid-19: The Great Reset, The World Economic Forum
(2020).

196