Models of Decision Making with Limited Volume o f Processed Information

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 carried 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 Systems

-

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. 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. Germie r [ 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 comple x, infinite-dimensional spaces. The use of such strategies implicitly involved the processing of infinitely large amounts of data.

The theory of hierarchical games considers the problem of information support optimizing 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 solution 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 parametrically, 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 extremely irregular. First, the solution in a typical situation can vary greatly with arbitrarily small changes in the parameters of the model. And secondly, discontinuous functions, 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.

Game-theoretic models are more structured than models of information theory, therefore, it was possible to identify not three, but eight meaningful statements (including 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 expand 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 interests are described by the desire to maximize the values of functions g and h respectively.

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 behavior 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 consideration corresponds to a set of 2n subsets

 X10, X11 , X 20, X 21 ,..., X n0, X n1  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 0 t

Xt1  , Xt0

Xt1  V , t  1,..., n.

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

Xtrt . The first player can and should choose control ur U having ret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 controls ur 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(ur ,v) and h(ur ,v) accordingly, 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)  ur . 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 guaranteed 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) , if the upper bound wV  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. 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 strategies 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 restrictions 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 language, 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 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 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 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 c( )  sup sup... sup sup minsup max min h(ur , v)   , u0U u1U um1U  vV rN inf max max  g(ur ,v)  ,   h(ur ,v) vV rN

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 conjunction) 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 simplified in games with restrictions on information exchanges. In this case, the relationship 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 comple xity 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 information 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 ].

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 appearance of the possibility of obtaining inaccurate information in games without externa l 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" information 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 information about his actions. When the amount of information to be transmitted is limite d , the top-level player can “selectively check” the validity of the transmit ted 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 account 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 management, 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 because 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 receiv e information about uncertain factors but to a limited extent (the amount of information can be defined as in Section 3).

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 includes 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 consistency 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 information”.

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 information 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 system, 1 terabyte of information is used. It is clear that the situation will essentially not change if we increase this volume by 1 megabyte o r 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 continuum 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 ].

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 available 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 agricultural 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 simila r to the one to which Klaus Schwab drew attention [ 19 ]: “Today the situation is fundamentally 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 ).

8. Gorelov , M .A. : Topological Statement of the Information Aggregation Problem in Hierarchical 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 information . Problemy peredachi informatsii 1(1) , 3 - 11 , ( 1965 ).

10. Gorelov , M .A.: M aximal guaranteed result for limited volume of transmitted information . 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 Control 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. Autom. Remote Control 81 ( 1 ) 41 - 52 ( 2020 ).

18. Gorelov , M .A. : On a quantity of information required for efficient control . Large-scale systems control 88 , 41 - 68 ( 2020 ).

19. Klaus Schwab , Thierry M alleret . Covid- 19 : The Great Reset, The World Economic Forum ( 2020 ).