Collective Behaviour of Automata and the Problems of Stable Local Control of a Large-scale System
Proceedings of the Second International Joint Conference on Artificial Intelligence. Pages 51-57.
© 1971 International Joint Conferences on Artificial Intelligence
Abstract
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
COL.L.:ECTIVE B~HAVIOUR OF AUTOi\lATA AND Tllli PROBL~!JS OF STABLE LOCAL cmrrROL OF A LARGE-SCALE S YST i:!:.\1
V .L.Stefanuk, Institute of Information Transmission Problems, Academy of Sciences of the USSR, Ul. Aviamotornaya 8,a MOSCOW E-24-,
USSR.
The. local choice of individual actions in the collective with antagonistic interaction may in principle lead to unstable, burst-like regimes in this collective. In the mathematical model of such a collective considered below (>lhich is convenient to treat in terms of a collective of radiostations inter fering with each other during their normal performance) the major role in this respect is played by the I\.. n.. region. If a vector of required quali ties .1° satisfies A 0 EJ\.n, then natural local algorithms ot· the local choice of actions give global stability even in case of some delays in the system. On the contrary there is no stability if A 0 ¢.i\n.. The region An is determined with .all the coefficients characterizing the interaction in the collective. For this reason the cohe rently local approach to the control of that system necessarily forces one to look for local criteria of control which could always provide the stable choice of actions (powers) by the radio stati·ons under consideration. It is a matter of control elasticity that leads him further to the elastic local crite rion of power control. This criterion seems to be the most "reasonable" for such a collective, but it is rather complicated in realization. From the formal point of view the analysis of the local criteria is reduced to studying properties of Nash parties in corresponding automata games.
- n - the number of members in the collective, the number of pairs of radiostations;
- Ci - the action of i-th member, the power level of the transmitter of i-th pair;
- t - the time;
- 4-. YL - the useful "effect" received by i-th member of the collective;
- JL, - noise-to-signal ratio on i-th receiver;
- J, - vector of noise-to-signal ratios;
- 7 · .A 0 L - a priori given noise-to-signal ratio;
- vector of given a priori
- ratios of noise-to-signal; the region of obtainable vectors .A.
- aij Cj - the power level on input of the receiver of i-th pair of radiostations due to only the transmitter of j-th pair;
11. ai.j - positive (non-negative for
- l (~t)ll ~,aj. ) values; 12.1 ai.j u - the matrix of the quantin. ties ay ;
- 13.Jl (..t)- the matrix with the diago nal elements equal to .A.i Qii. ,
- n-J.. non-diagonal equal to - ai..j ; 14- · Jl.i ~) -(n- 1 )-th order principal minor of matrix Jln.{ .A) corresponding to i-th diagonal element;
- Cl!i.,d-~.Ji. - fixed positive parameters; 16. ( (1.i, (.ci~)- the local criterion of power control for i-th pair of radiostations;
- cL - vector of fixed positive parameters;
18. cj - the subclass of radiostation collectives;
A number of important problems of control systems construction which because of their complexity we usually consider as belonging to the area of artificial intelligence, leads to the necessity of study of a system with certain character of interaction of its components. Suppose a system consisting of n components. Suppose that the i-th component of the system performs the action C;. (O$:Ci.< 00 ,i.-i, ... ~n) at the moment t and just at the mo ment it knows a value~ which shows what the effectiveness of applying such an P.Ction in that system is. This "effect" is determined by all the actions chosen by all other mem bers of the collective at the same moment of time. The in crease of the C i leads to an in crease of the effect provided that the actions of all other mem bers of the collective are being constant. \'nlile the increase of e ~ ' j :/ t. ' provided that the c, is constant, leads to
its decrease.
In other words the antagonism of aims of different elements of the system and comparatively small infor mation concerning the actions of other elements are main characteristics of the system in question.
Similar interactions are typical of Mathematical Economics. For example one can consider the gain of the firm which is putting into sale Ci units of goods, supposing that other firms independently are supplying the same market with the same goods, their quan tities being equal to ci , .. . I Cn respectively.
'L'he studies on creation of an arti ficial situation oi' a similar kind when identifying people suitable for living in full isolation for a long period of time are .well known (the test for so called psycho-physiological compatibi lity).
Professor Michail Lvovich Tsetlin was the first to draw our attention to the fact that sometimes "behavioral" aspects appear in purely technical problems, which seem to be very far from the problems of behaviour of li ving organisms. One of such problems is that of stable local control of the power levels in the collective of radio stations, which interfere with each other during their normal performance· In this particular problem C;. corresponds to the power level of i-tL transmitter and YL corresponds to the signal-to-noise ratio at the input
of i-th receiver.
It is easy to see that in all examples mentioned above under the condition that the ,.ction Ci. is chosen independenly in each system component on the base of limited, local in:: orma tion related only to the value Yj_ eenerally speaking it is possible to have unstable, burst-like regimes. Indeed, let for ex~ple the i-th compo nent of the system increase its Ci. with the goal to increase the effect
V~ · In that case all other components in their turn can d.o nothing but in crease their actions because their "effects" fall down. As a result the value of the effect in the i-th compo nent may become even lower than the previous one and a further increase of C;. is required, and so on.
Thus in such complicated (large scale) system the necessity of clearing up the possibility of obtaining a stable resime of the local choice of actions begins to play a fundamental role.
'rhough the majority of the paper for:nulations and results seems to be directly applicable to both the Mathe matical !~conomics and the group-psycho logy problems, all the discussions below are related only to the power control problem in a collective of radiostations. (Note that independently such a problem is of interest for one type of communication system, namely for the asynchronous address communication systems.)
The following mathematical model is used. The collective of radiostations consists of ~ pairs of transmitter-receiver. Let CL(t) be the power of the i-th transmitter at the moment t . de suppose that generally speaking all the pairs are interacting and v~ite noisy input power coming from the transmitter of the j-th pair as a£j Cj(t.), where ai.j~O;i is j ;i,j=i ... . .· n. Then, the input noise-to-signal ratio for i-th receiver ~i(t) is equal to
Here ~ is additive noise power at the input of the i-th receiver; ai.L ci.(t.) is the signal power coming from the transmitter of the same (i-th) pair.
It is supposed that all the infor mation concerning the situation in the collective of radiostations at the moment t which is available for i-th transmitter consists of two quantities .l.Jt), CJO (that is, in each pair there is an "ideal" feedback).
When facing such a system one should answer the following questions. Let the positive value .A 0 L be given for the i-th pair, i ·i, ... , n , and let the degree of interaction in the collective be fixed, i.e., the matrix n (n..) u Cli.j is fixed. Then do powers c 1 ., . .. · c, which provide noise-to signal ratios to be equal to respecti vely .1:, · · ·,A.~ exist? If the powers giving ( .1:, ... ,.1°,.,) exist then do algorithms of local choice of power level independently in each transmitter which guarantee .1Jc)-A 0 i. , i.=i, .. . ~n., provided that i-th transcitter knows onlylJi)' ct,(-t.) exist?
Let An. be the set of those And only those positive vectors A (all components of ~ are strictly posi tive) for which all the principal minors of the matrix
are (strictly) positive. It turned out that the values of po:ers pr~viding an a priori given ~ exist (the vector X is obtainable) if and only if .1" e.An, . The algorithm of c power choice which guarantees A.Jt)·Ai., i -= i , . . . , n , if only X E An. , has the following analytical form
(Here 3ei.. is fixed positive parameter of the algorithm).
From the expression (3) it follows that at each moment this algorithm uses only two values: .A-Jt), Ci.(i.). It is convenient to speak about the automaton Ct~ of power control, which has a continuous set of states-actions ci the input .li. and J.~ as a parame ter. Then, the expression (3) describes the joint behaviour of the collective of n. such automata inter acting in accordance with the formula (1).
For the i-th pair of radiostations it is natural from a practical point of view to try to reach an a priori given noise-to-signal ratio because it is this ratio that is responsible for the possibility of normal signal reception. But on the other hand such a criterion of choice of power level has the essential limitation that the ..,o "0 vector a priori given values ""-J., .. . ,.1\.n., may not be obtainable (if j_ 0 ¢.An ). In the latter case in accordance with the power choice algorithm (3) the powers of all the transmitters begin to grow infinitely, i.e., the system
becomes unstable.
Note that the answer of whether liD ~ is obtainable or not may be given only after an analysis of matrix (2). But the problem itself was formu lated so that this information is not available for any member of the col lective.
One way of allowing stability to be reached despite the locality of information in the general case (i.e., the matrix II a.(y)ll is arbitrary one) is to take into account besides the input noise-to-signal ratio the power consumption. To this end we introduce the following formal definition of notion of local criterion of ~ower ca.,ontrol Ct
Assume that the value of CL. is available to the i-th transmitter and its task is to minimize in a definite sense the CL by means of the proper power choice. As it was up to now, we assume that the 1-th transmitter knows only the quanti ties ~JO, Ci.(t) and that CL. can depend only upon them (i.e., c~ may depend upon the powers CJ. , ... , Cn, only via AL, (-t) ) and maybe upon certain parameter 8 pri ori known to the transmitter.
One of the most natural way of synthesis of the local criterion of power control which provides 8 stable choice of powers in an arbitrary col lective of radiostations is to introduce "price" for the transmitter power.
The simplest criterion of such kind has the following form
where eli.> 0 is an a priori chosen fixed positive parameter ("price").
We will study asymptotic (final) behaviour of the collective of automata of power control, c~ being the penalty function for the i-th automaton, i = ! , . . . , n.. · Omitting the formulation of construction of each automaton we will try to prove the existence and uniqueness theorem for certain equili brium points (Nash parties) in corres ponding games. Ai'ter that there will be every reason to hope that automata of simple "gradient" tactics will provide the global stability of power choice by that automata collective. However, the description of the automata picking up the Nash party is beyond the scope of
this paper.
The party of a game (i.e., the set of actions chosen by its participants)
which has the property that for none of the automata is it advantageous to change its action provided that the other automata persist in their actions we will call equilibrium in the sense of Nash party or simply Nash party.
Introducing into formula (4) the expression (1) for noise-to-signal ratio .A.,Jt) in terms of transmitter powers, one can see that for criterion (4) the inequality
is always fulfilled, i.e. cj, is a concave function of the variables Ci For such functions all r;ash parties and only they satisfy the system of equations
Theorem 1. For every positive vector d. = ( al.J , . 0. , ol.tL) there exists e unique equilibrium in sense of Nash vector CJ. , . . . , Cn. and consequently a unique vector .A!, 0 0. , ~n.
(The proofs of all theorems in the paper will be omitted.)
It is interesting to note that an analogous criterion with "logarithmic price" on the power
already doesn't have such a property. One can see that in case of the crite rion (7) the e~uilibrium party exists only for d.. from a certain region, which it~elf depends upon the detailed structure of interactions in the col lective.
Thus criterion (4) provides the solution of the problem of stable local power control in the arbitrary collec tive of rediostations. However, it hes a limitation which forces one to look for a better criterion.
Let all radiostations not interact at all ( a..~,o ' i"'" j; i,j- i , o .. ·"' ), but the automata of power control are ignorant of that feet ( the i-th auto maton knows only .1Jt) , lJi:) ! ). In that case it is principally possible to obtain any e priori given noise-to signal ratio in each pair of radio stations. Unfortunately, the automata performing in accordance with criterion (4) cannot provide in the equilibrium point the a priori given noise-to-sig nal ratio, though it is al·Nays obtain able. Indeed it is seen from expres sion (6) in that case for any fixed
ci~ the noise-to-signal ratio in a Nash party will be defined by the values J(i. '?M~i. n accordance with the formula ,1.= cii.Jii. · But these two L C( " values are unknbWn. to the i-th transmitter (and it is ignorant of the fact that the collective doesn't really exist, for there is no interaction at all) and the equilibrium J.i. is a priori unknown.
However the limitation just mentioned is inherent not only for criterion (4), as a matter of fact it is a property of all criteria of a similar kind.
Consider now an arbitrary col lective of power control automata, cJt) '.A.c: (t) being, respectively, the action and the input of i-th automaton at the moment i. . Let C i. be the penalty function of i-th automaton, provided that C;. depends upon only ~i. , Ct. and maybe upon some parameter oli.. which is a priori chosen individually in each automaton (i.e., transmitter). Then the following theorem is held.
Theorem 2. Criterion C~ which simultaneously has both properties i) and ii) doesn't exist, where the properties are the following: i) In an arbitrary collective charac terized by the matrix Jl a'J' II there exists the unique equilibrium party satisfying the system of equations
ii ) i'ihen there is no interaction at all ( Cl. tj = 0 , i -:1- j ; i, j = 1 , . . . , n. ) , then the equilibrium noise-to-signal ratio is equal to a certain e. priori given value (independent of additive noise power on receiver input).
The reason for the "non-elasticity" lies in the fact that automata can not distinguish the additive noise from the noise cooing from the partners.
Nevertheless using the same local information on the collective available to each trans~tter, one can construct another automata game, the equilibrium party of which doesn't have the form (8). Participants of that new game have the ability to make e distinction between the additive noise and the noise from partners and for that reason the assertion of theorem 2 for the game doesn't hold.
Indeed, applying automaton ct· l providing the choice of an a priori Given noise-to-signal ratio (v1hen it is possible in principal!), one can formulate the game of automata in which the noise-to-signal ratio itself will be the action of i-th automata at the moment i . It can be done by making use of an automaton of so-called "two-levels" construction, where the first level (automaton a, ) is to maintain a certain noise-to-signal ratio, the value of which is chosen by the second, "higher" level.
Then Nash parties will satisfy the equations analogous to (5),(6):
We will study the game automate in which the penalty function of the i-th autoi:laton will be equal to the follo·:; ing elastic local criteria:; of power control
where o,>O is again a fixed numerical parameter a priori chosen in the i-th transmitter. Performing in accordance with this criterion the i-th automa t on decreases the value of the noise-to signal ratio by the way of an increase of its power C;_ until a further negligible decrease of that quantity requires too much increase of the transi:litter power.
It will be shown that this elastic criterion provide sufficient "smooth ness" of the transition from the situation with weak cooponents inter action to the one with high interaction First of all it is desirable to formulate for this criterion a theorem analogous to theorem 2 · Before that we will give an interesting geometrical interpretation of equilibrium point (or points) which follows from (9),(10), (11).
U (n-) u Now suppose that the matrix CLLj 11 is irresoluble. That means that ...(L"'(..t) is irresoluble too. Then it can be proved that the boundary of J\~ region in space of vectors .1. = (.l.1 , .. . , J.n.) may be given by the equation det Ji n.(.A_) .. 0 and the condition that all other prin cipal minors of ....U n,(.t) are strictly positive. This theorem follows from the positive matrix theory.
Resolving the system of equations (1) with respect to {,1 , .. . , Cn, we have
where is the determinant of (rt.-1 )-th order principal minor of the matrix (2) corresponding to the i-th diagonal element.
Now the elastic criterion (11) may be rewritten in the form
'rhen it is easy to see that all points of equilibrium in the sense of Nash (9),(10) and only they are determined by the equation
where 1;.>0 .
Expression (14) leads to a very important conclusion that in the case when the interaction among the radio stations is equal to zero (it means II '"' 1 II that the matrix a.i.J is an upper (lower) triangular one), then the equilibrium J.., i. satisfys J..i. .. fi.. Thus, indeed, the elastic criterion lets us in this case provide an a priori chosen value noise-to-signal ratio.
Fur~her,with the obvious transfor mation the relation (14) can be rewrit ten in the determinant form
Here ( 11 " .. "' is some equilibrium J\IJ,. ' · · · '.A ·~) vector. Now it becomes clear that points with coordinates
lie on the boundary surface of J\~· in the apace of vectors jL
In other words the equilibrium point (points) (~J , .. . , ~ 1\.J correspond ing to a certain choice of the parame ters J~, ... , il'\.. , which determine the criterion (11) in each automaton-trans mitter lies in the A,.. region with its distances from the boundary surface of A""' (measured along coordinate axes j,.l, ... ,.A.., , respectively) being equal to Jj., ... , In. ,. respectively.
The drawing gives an example for ~ · 2. It is seen that exactly one equilibrium point corresponds to each pair of positive it .l'z. · (hyperbolas shown on the drawing are two examples of the location of the boundary surface of A 2 region, for weak and strong interaction of radiostations, respec tively).

The ·proof of the existence theorem for the equilibrium point is complica ted enough in case n.> 2 and it was done previously only for certain natural class of collective of radio stations "where the interaction is not too strong" .
Consider the class ¢ of all possible collectives of radiostations with each element of ~ meeting the following requirement. Any vector ( s,J , . . . , s,II.-J) composed from (ll-1) coordinates of the vector ( J'J. , ... , in-) should be obtainable in the subcollec tive, the indexes of radiostations of which are respectively iJ. , . · · · iiL-J. . L~ 11n-11J: J ~ · e ·, «e-t... ..u.~ 1' Ls , · · · , i n.-i) and all the principal minors of this determi nant are strictly positive (of course the vector ( J' ~ , ... ,J "') shouldn't necessarily be obtainable in the whole collective).
Theorem 3. There is always at least one Nash equilibrium point in the class ¢
The proof of the theorem consists of a number of more or less independent steps justifying in that case the applicability of the fixed point theorem.
Summing up, one can say that in the formulation of the problem of stable (elastic) local power control conside red above, it is the introduction of a "price" on power (or on its increment) that provides global stability. If it were not for questions of the pu rely technical problem, we would say that such a "split" of aim of each participant (besides the natural will to obtain the minimal value of .1 i he wants to guarantee the stability) is analogous to the necessity for an individual to stick to certain moral principles for the sake of stability of society as a whole.
@inproceedings{ijcai1971p5,
title = {Collective Behaviour of Automata and the Problems of Stable Local Control of a Large-scale System},
author = {Stefanuk, Vadim L.},
booktitle = {Proceedings of the Second International Joint Conference on
Artificial Intelligence, {IJCAI-71}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {D.C. Cooper},
pages = {51--57},
year = {1971},
url = {https://ijcai.org/proceedings/1971/5},
}
TY - CPAPER TI - Collective Behaviour of Automata and the Problems of Stable Local Control of a Large-scale System AU - Stefanuk, Vadim L. T2 - Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71 PB - International Joint Conferences on Artificial Intelligence PY - 1971 SP - 51 EP - 57 UR - https://ijcai.org/proceedings/1971/5 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: