Search of Nash Equilibrium in Quadratic Nonconvex Game with Weighted Potential?

Abstract

We consider an n-player nonconvex continuous game with quadratic payo s, multi-dimensional strategy spaces, and possibly shared constraints on strategies, and investigate conditions when this game admits a weighted potential. Since a potential is generally nonconvex in this case, we propose local and global search procedures for maximizing it over the set of admissible game pro les. The local search uses nonlinear support functions that are constructed through a d.c.-decomposition of the potential. The global search is based on reducing of a certain nonconvex quadratic programming problem to a mixed-integer linear programming problem.

Keywords

• Nash equilibrium mization D
• C decomposition

-

One of the main features of potential games in the sense of computing Nash equilibria is a possibility of reducing the game to an optimization problem. More exactly, in a potential game the set of maxima of a certain function is a subset of the set of Nash equilibria. This function is called potential. Generally a potential is a nonconvex function. In this case the set of local non-global maxima may contain equilibrium points as well. For the games with di erentiable payo s, even a stationary point could be suspected to be an equilibrium. Thus two crucially important questions arise in practice: how to determine the existence of a potential, and how to specify this function. Both of these issues are solved for the di erentiable case of exact potential games with scalar strategies [15]. Weighted potential games generalize exact potential games by introducing a positive weight for every player. The class of weighted potential games turns out to have properties, which are very similar to those of exact potential games.

The class of exact potential games was introduced in [15], along with weighted, ordinal, and generalized ordinal potential games. Later even more general classes were investigated, such as best-response potential games [19], and pseudo-potential games [4]. A common property of all these classes stays the same: they admit an optimization problem statement that noticeably makes easier an analysis of the game. A survey on di erent classes of potential games, on relations between them, as well as examples of applications one can nd in [12, 7, 13] (see also the references therein). In this study we are interested in continuous games, i.e. games with continuous sets of strategies. For games with twice continuously di erentiable payo s and interval strategy sets, a useful characteristic for identifying the existence of a potential was established [15]. Such a characteristic can be easily extended for weighted potential games with interval strategy sets. For ordinal and generalized ordinal potential games with the payo s of the same class and with multi-dimensional strategies, necessary conditions were formulated in [5].

For the cases in which either a game is non-potential or an identi cation whether a potential exists is complicated, there are methods of variety of types that do not exploit potential optimization for computing Nash equilibria. For instance, the methods among them are gradient-type algorithms [17, 21, 1], relaxation algorithms [20, 8], Newton-type method [9, 3], nonlinear support function method [10, 14], KKT-conditions-based method [2], and many others. It is worth to note that convexity-type assumptions usually play signi cant role for the convergence properties of equilibrium computation algorithms. The standard assumption widely used is player-concavity of payo s, i.e. every player's payo function must be concave with respect to this player's strategic variable. Games with this assumption being violated we call nonconvex games, in contrast to convex games [16]. Also there exists a rather general approach to reducing an equilibrium problem to a global optimization problem [10] using the so-called Nikaido-Isoda function [16]. It is noticable that this approach in general does not employ any of convexity presumptions. The underlying method in [10] is based on the concept of nonlinear support function. Later such a technique was applied to quadratic nonconvex non-potential games [14]. As we see further, existence of a weighted potential can also be guaranteed without convexity-type conditions on payo s.

The present paper focuses on n-player nonconvex games with quadratic payo s and convex compact set of game pro les. A strategy of every player is assumed to be a multi-dimensional value. We admit that the strategy set of every player depends on chosen strategies of rival players through shared constraints. These constraints restrain the set of admissible pro les. Recall, the problem of nding Nash equilibrium in non-cooperative game with coupled strategy sets is called generalized Nash equilibrium problem (GNEP). In contrast, if the strategy sets are independent, the problem is referred to as Nash equilibrium problem (NEP); see [17] for details. We discuss a di erentiable characterization of weighted potential games with vector strategies, and provide explicit expression of potential function. Then we formulate these results speci cally for quadratic games. The potential turns out to be nonconvex in this statement. Hence we propose a local search and a global search methods for maximizing a potential function over the set of game pro les. 2

Weighted Potential Games

Consider a non-cooperative n-person game. The set of players is N = f1; 2; : : : ; ng, a strategy of ith player represents mi-dimensional vector, so as the set of admissible game pro les is X Rm, where m = m1 + + mn, and R denotes the set of real numbers. Payo function of ith player is fi : X ! R. We suppose that X is a convex compact set, and fi is twice continuously di erentiable for every i 2 N . The problem is to nd generalized Nash equilibrium (or, shortly, Nash equilibrium) for the given game, i.e. to nd a pro le x 2 X meeting the following conditions: fi(xi; x i) 6 fi(x ) 8xi : (xi; x i) 2 X ; 8i 2 N ; ( 1 ) where (xi; x i) = (x1; : : : ; xi 1; xi; xi+1; : : : ; xn). Let us denote the game by = hN; X; ffigi2N i.

Recall that the game is called a weighted potential game if positive weights w1; : : : ; wn and weighted potential function P : X ! R exist such that for all i 2 N and for all yi; zi; x i: (yi; x i) 2 X, (zi; x i) 2 X the following relation holds [15]: If w1 = w2 = = wn, then is called an exact potential game and P is called an exact potential. In order to specify certain values of weights in ( 2 ) we will say that the game is w-potential game, and P is w-potential, where w = (w1; : : : ; wn). The next useful results are well known for di erentiable games with scalar strategies. Let m1 = m2 = = mn = 1. If payo s are continuously di erentiable on X, then condition ( 2 ) can be replaced by Moreover, if payo s are twice continuously di erentiable then is a weighted potential game if and only if positive numbers v1; : : : ; vn exist such that for all i 2 N , j 2 N (i 6= j), x 2 X:

: = vj P (x) =

Z 1 0 i2N

xi dt :

is a weighted potential game, then a weighted potential function is expressed More exactly, due to de nition ( 2 ) the game is (1=v1; : : : ; 1=vn)-potential in the latter case. Relation ( 3 ) at w1 = w2 = = wn = 1, and relations ( 4 ), ( 5 ) at v1 = v2 = = vn = 1 (for exact potential games) were provided in [15]. Extension of these results for weighted potential games with scalar strategies follows in a straightforward way.

In order to generalize the di erentiable characterization (3{5) for multidimensional strategy spaces, let us introduce a game 0 by replacing ith player in by mi players, each of them maximizing the same function fi with respect to one of scalar variables from mi-dimensional strategy of the ith player of . Then the set of players in 0 is N 0 = f1; : : : ; m1; m1 + 1; : : : ; m1 + m2; : : : ; mg. The rst m1 players try to maximize independently f1 as their payo , whereas the next m2 players treat f2 as a payo , etc. The pro le set in 0 is X, and every player of 0 operates one scalar variable.

Recall a de nition from potential game theory useful for the present study. A path in X [15] with respect to is a sequence of game pro les (p1; p2; : : : ) such that pk 2 X, k = 1; 2; : : : , and for every k > 1 there exists a unique deviating player of , say ith player, such that pk = (xi; pk i) for some xi 6= pik 1, (xi; pk i) 2 X. In the further discussion x(i) denotes the kth component of vector k strategy xi. Besides, w0 2 Rm is a vector of weights, where w1 = w10 = w20 = = wm01 , w2 = wm01+1 = wm01+2 = = wm01+m2 , etc.

The next result holds without continuity assumption on payo s.

Theorem 1. Let there exist a path (p1; p2; : : : ; pK ) in X with respect to 0 connecting the pro les p1 = (yi; x i) and pK = (zi; x i) for every yi, zi, x i such that p1 2 X, pK 2 X, and for every i 2 N . Then the game is a w-potential game if and only if the game 0 is a w0-potential. If and 0 are a w-potential and a w0-potential games respectively, their weighted potentials coincide up to constant.

Proof. If is a w-potential game then ( 2 ) holds for some function P : X ! R. For every i 2 N and for every k 2 f1; 2; : : : ; mig x arbitrarily y(ik) = z(ik) = x(i)k such that there exists a scalar value a(ki) : (a(ki); x(i)k; x i) 2 X. Then the condition ( 2 ) yields

fi yk(i); x(i)k; x i wi P yk(i); x(i)k; x i fi zk(i); x(i)k; x i =

P zk(i); x(i)k; x i : The latter relation provides that 0 is a w0-potential game with potential P .

Conversely, let 0 be a w0-potential game. For every i 2 N choose arbitrary vectors yi, zi, x i such that (yi; x i) 2 X and (zi; x i) 2 X. De ne a nite path (p1; p2; : : : ; pK ) in X with respect to 0 connecting the pro les p1 = (yi; x i) and pK = (zi; x i), where the unique deviators are the mi players of 0 with fi as their payo . In other words, pk = (pik; x i), k = 2; 3; : : : ; K 1. Then due to ( 2 ) the following relations take place: In particular, the assumption in Theorem 1 holds for games with independent strategy sets (for NEP). If this assumption is violated let us de ne an open convex neighborhood of the set X, and suppose that payo s and a potential are de ned on . Replace in and 0 the pro le set X by . Denote the derived games by and 0 respectively. It is obvious that if is a weighted potential game, then is also a weighted potential game with the same potential function, since X . Moreover, the assumption of Theorem 1 holds for a game with the pro le set , as for every x 2 there exists a neighborhood B(x) such that B(x) .

Corollary 1. If 0 is a w0-potential game then the same potential function as in 0 . is a w-potential game with In what follows, we suppose that the assumption of Theorem 1 holds.

With Theorem 1 relations ( 3 ) and ( 4 ) are easily extended for games with vector strategies. Since payo s in are continuously di erentiable, due to Theorem 1 the condition ( 3 ) for multi-dimensional strategies can be replaced by the following one:

rxi fi(x) = wirxi P (x) : Using the assumption that payo s are twice continuously di erentiable, Theorem 1 and ( 4 ) imply that is a weighted potential game if and only if positive numbers v1; : : : ; vn exist such that for all i 2 N , j 2 N (i 6= j), k 2 f1; : : : ; mig, and l 2 f1; : : : ; mj g, and for every feasible x:

Condition (7) is equivalent to If we de ne a multi-valued function

virxi;xj fi(x) = vj [r2xi;xj fj (x)]> : 2 ( 6 ) ( 7 ) gv(x) = (v1rx1 f1(x); : : : ; vnrxn fn(x)) ; then relation ( 7 ) is also equivalent to that the Jacobian Gv(x) of gv(x) is symmetric for every feasible x. Proposition 1. If payo s are twice continuously di erentiable then the game is a weighted potential game if and only if positive numbers v1; : : : ; vn exists such that the Jacobian Gv(x) of the function gv(x) is a symmetric matrix for every x 2 X.

Formula ( 5 ) of a potential function is also adopted for multi-dimensional strategies through Theorem 1.

Proposition 2. If is a (1=v1; : : : ; 1=vn)-potential game then a weighted potential for is given by Note that existence of a continuous potential function implies existence of a Nash equilibrium in the game if the pro le set X is compact. 3

Quadratic Games

Let ith player's payo function in the game be de ned as

fi(x) = xi> Without loss of generality matrices Bi are supposed to be symmetric. For payo s ( 9 ) necessary and su cient condition ( 7 ) for to be a weighted potential game is presented by the following one:

viCij = vj Cj>i for some positive v1; : : : ; vn and for every i 2 N and j 2 N (i 6= j). As playerconcavity of ( 9 ) is not used in the condition ( 10 ), weighted potential quadratic games include nonconvex games. Moreover, even the term in payo , which does not depend on rival players variables, has no impact on the existence of a potential function. Indeed, the equality ( 10 ) plays the role of necessary and su cient condition also for the game with the following payo s: fi(x) = fbi(xi) + j6=i X xi>Cij xj ; j2N where fbi generally is non-quadratic.

Proposition 3. The game with payo s ( 11 ) is a weighted potential game if and only if positive numbers v1; : : : ; vn exist such that for every i 2 N and j 2 N (i 6= j) condition ( 10 ) holds. For instance, consider a 2-player game with payo s ( 11 ) and with scalar strategies: Generally c1 6= c2, therefore existence of an exact potential is not guaranteed. However we can always choose positive numbers v1, v2 such that v1c1 = v2c2 being true, if c1 and c2 are nonzero and have the same sign: In particular, v1 = 1, v2 = c1=c2 would be appropriate. For an n-player game with multi-dimensional strategy sets, in order to ensure existence of a weighted potential in accordance with Proposition 1 we should provide v > 0 such that the Jacobian

0v1r2fb1(x1) v1C1;2 : : : v1C1;n 1 Gv(x) = BB v2C2;1 v2r2fb2(x2) : : : v2C2;n CC @: : : : : : : : : : : : : : : : : : :A

vnCn;1 vnCn;2 : : : vnr2fbn(xn) be symmetric.

If ( 10 ) holds, by Proposition 2 a (1=v1; : : : ; 1=vn)-potential for o s ( 9 ) is given by

P (x) = X vi xi> i2N 12 Bixi + di + 21 Xj6=i xi>Cijxj : j2N The validity of ( 12 ) one can examine directly through the verifying the equality ( 6 ).

Example 1 (quadratic payo s [14]). Consider a 2-player nonconvex game with quadratic payo s and scalar strategies: f1(x) = x12 + x1x2 ; f2(x) = Obviously the game does not admit exact potential. However with v1 = 1, v2 = 2 in ( 12 ) (1; 1=2)-potential is

P (x) = x12 2x22 + x1x2 : There are two Nash equilibria in the game: x0 = (1; 1=4) and x00 = ( 1; 1=4). Both of them provide maximal value to P on X. The vector eld (@f1(x)=@x1; @f2(x)=@x2) and the plot of the weighted potential are presented at Fig. 1. Due to ( 6 ) the vector eld coincides with (@P (x)=@x1; @P (x)=@x2). with pay( 12 ) x2 0.5 1 0 −0.5

0 To illustrate Proposition 3 consider an example with non-quadratic payo s. Example 2 (qubic payo s). De ne a 2-player game with payo s ( 11 ), where fb1(x1) and fb2(x2) are qubic polynoms: As in the previous example, the given game is not an exact potential. Setting v1 = 1, v2 = 2=3 at ( 8 ) we obtain (1; 3=2)-potential function:

The next example shows that locally non-optimal stationary point of a potential may be a Nash equilibrium.

Example 3. Consider an exact potential game with X an interior point of X, and payo s are de ned as follows: R2 such that (0; 0) is

A potential is given by

f1(x) = x2x13 f2(x) = x1x23 x21 + x23x1 + 3x1x2 ; x22 + x13x2 + 3x1x2 : P (x) = x13x2 −1,000 0 −10 −5 x1 0 The pro le x0 = (0; 0) is an equilibrium since f1(x1; 0) = x21 and f2(0; x2) = x22. Besides rP (x0) = 0. However P increases along directions d1 = ( 1; 1) and d2 = (1; 1) from x0. Indeed,

P (x0 + td1) = P (x0 + td2) = 2t4 + t2 > P (x0) for every t > 0 :

Hence x0 is not locally optimal.

Therefore we are interested in maximizing P (x) subject to x 2 X, possibly locally, or at least nding a stationary point of the potential over X. To this end, a local search and a global search procedures will be examined further. 4

Local Search

As we discussed before, equilibria of a potential game should be searched among stationary points of a potential function. Hence it is reasonable to use a local ascending method in addition to a global search technique due to much less computational costs of the former one.

For a weighted potential quadratic game with weights (1=v1; : : : ; 1=vn) de ne a vector dv = (v1d1; : : : ; vndn) and the following matrices: 0v1B1 0 : : : 0 1

0 v2B2 : : : 0 Bw = BB: : : : : : : : : :CC ; @ A 0 0 : : : vnBn

0 0 v1C1;2 : : : v1C1;n1 Cw = BB:v2:C2:;1 : : : : ::: : :v2:C:2;n:CAC ;

0 @ vnCn;1 vnCn;2 : : : 0 and Qv = Bv + Cv, where Qv is symmetric since the game is potential. Then represent the potential ( 12 ) as follows:

x>Qvx + x>dv : Consider the general case when the matrix Qv is inde nite, and represent Qv as follows:

Qv = D1 + D2 ;

D1 = Qv

I ;

D2 =

I ; ( 13 ) where > 0 is the largest eigenvalue of Qv. The matrix D1 is negative semidefinite, whereas the matrix D2 is positive de nite. Using ( 13 ) we represent P as the sum of concave and convex functions ' and respectively: In other words, one can say that P is presented as a di erence of two convex functions. Such a representation is referred to as a d.c. decomposition. De ne an iterative local search process for the problem as follows. Let an initial pro le x0 2 X and the current iteration point xk 2 X be given. Then the next point xk+1 is obtained as a solution of a maximization problem with concave objective: xk+1 2 Arg max (x; xk) j x 2 X ;

k = 0; 1; : : : ; (x; xk) = '(x) + r (xk)>(x xk) + (xk) : The function (x; xk) may be considered as a nonlinear support minorant function for P , since ( 14 ) ( 15 ) ( 16 ) (x; xk) 6 P (x) (xk; xk) = P (xk) 8(x; xk) 2 X 8xk 2 X :

X ; An investigation on the algorithm ( 15 ), ( 16 ), including its convergence properties, one can nd in [18]. It had been shown that the process ( 15 ), ( 16 ) converges to a stationary point of the nonconcave optimization problem ( 14 ). 5

Global Search

It is possible to point out two cases when a using of a global search is essential. The rst one is a veri cation of a stationary point obtained by a local search whether this point is an equilibrium. Such a veri cation consists of n nonconvex programming problems that we need to solve in global sense (see ( 1 )). In order to obtain various stationary points it is supposed to start local ascending from di erent, say randomly chosen, initial points (multistart). Secondly, we need to use a global search method if after the veri cation of considerable number of stationary points we failed to nd an equilibrium. In this case we have to solve globally initial problem of maximizing a potential. In both cases we face a quadratic nonconvex programming problem with a convex feasible set. One of existing methods for solving such a problem consists in its reduction to a mixedinteger linear programming problem [11]. In what follows we recall an approach from [11].

To this moment, we have not yet speci ed the pro le set X. From now we assume that X is de ned by linear constraints:

X = fx 2 Rm j Ax 6 bg ; where A 2 Rs m and b 2 Rs. Write out the KKT conditions for ( 14 ), ( 17 ): rP (x)

s X iai = 0 ; i=1 i(x>ai bi) = 0 ;

1 6 i 6 s ; Ax 6 b ;

> 0 ; rP (x) = Qvx + dv ; where and ai denotes the ith row of the matrix A. The relation ( 21 ) implies From ( 18 ), ( 19 ), and (22) we have x>rP (x) = x>Qvx + x>dv = 2P (x) x>dv : x>rP (x)

s X ix>ai = 2P (x) i=1 x>dv

s X ibi = 0 : i=1 Hence every solution of the system ( 18 ){( 20 ) satis es the equality ( 17 ) ( 18 ) ( 19 ) ( 20 ) ( 21 ) (22) (23) (24) (25) (26) (27) With respect to the sensible assumptions [11] we can suppose that a constant M exists such that < M and y < M . Let us introduce binary variables zi, 1 6 i 6 s. Then complementarity slackness (25) can be replaced by the following equivalent constraints: i

M zi 6 0 ; yi

M (1 For convenience de ne auxiliary variables yi = bi problem ( 14 ), ( 17 ) is equivalent to the following one: x>ai for 1 6 i 6 s. The Thus we derive the mixed-integer linear programming (MILP) problem (23), (24), (26){(28) with binary variables. Although the original quadratic nonconvex problem ( 14 ), ( 17 ) is rather di cult, we believe that the derived MILP one would be more tractable due to highly developed MILP solvers (such as CPLEX, for example).

If we want to verify a stationary point x of the problem ( 14 ), ( 17 ) whether x is an equilibrium, we can maximize the payo s ( 9 ) in accordance with the de nition ( 1 ) by the same way as it was just described. Note that in this case we need to solve n nonconvex quadratic problems of dimensions m1, m2, . . . , mn, in contrast to one large problem ( 14 ), ( 17 ) of the dimension m. Hence it may be reasonable rst to search equilibria through the local ascending, since the large dimension plays crucial role in global search procedures. 6

Conclusion

In this study we generalize the di erentiable characterization for weighted potential games with multi-dimensional strategy spaces, and specify the corresponding conditions for an n-player quadratic nonconvex game with continuous set of game pro les. The set of pro les is de ned by shared constraints. It is shown that the ful lment of these conditions does not depend on convexity-type assumptions on payo s. A weighted potential for the given game turns out to be a nonconcave function. Since every global maximum of a potential is a Nash equilibrium, and moreover even a stationary point may be an equilibrium, we propose a local and a global search procedures for maximizing a potential function of quadratic weighted potential game. The local search process represents the sequence of convex optimization problems, and it converges to a stationary point of a potential. The global search is based on the reduction to an MILP problem.

References

1. Antipin , A.S. : Gradient and Extragradient Approaches in Bilinear Equilibrium Programming . Dorodnitsyn Computing Center RAS , Moscow ( 2002 ), (in Russian)

2. Dreves , A. , Facchinei , F. , Kanzow , C. , Sagratella , S. : On the solution of the KKT conditions of generalized Nash equilibrium problems . SIAM J. Optim . 21 ( 3 ), 1082 { 1108 ( 2011 )

3. Dreves , A. , von Heusinger , A. , Kanzow , C. , Fukushima , M.: A globalized Newton method for the computation of normalized Nash equilibria . J. Glob. Optim . 56 ( 2 ), 327 { 340 ( 2013 )

4. Dubey , P. , Haimanko , O. , Zapechelnyuk , A. : Strategic complements and substitutes, and potential games . Games Econ. Behav . 54 ( 1 ), 77 { 94 ( 2006 )

5. Ewerhart , C. : Ordinal potentials in smooth games . University of Zurich, Department of Economics, Working Paper Series, Working Paper No. 265 ( 2017 )

6. Gonzalez-Sanchez , D. , Hernandez-Lerma , O.: A survey of static and dynamic potential games . Sci. China Math. 59 ( 11 ), 2075 { 2102 ( 2016 )

7. Gonzalez-Sanchez , D. , Hernandez-Lerma , O.: A survey of static and dynamic potential games . Sci. China Math. 59 ( 11 ), 2075 { 2102 ( 2016 )

8. von Heusinger , A. , Kanzow , C. : Relaxation methods for generalized nash equilibrium problems with inexact line search . J. Optim. Theory Appl . 143 , 159 { 183 ( 2009 )

9. von Heusinger , A. , Kanzow , C. , Fukushima , M. : Newton's method for computing a normalized equilibrium in the generalized Nash game through xed point formulation . Math. Program . 132 , 99 { 123 ( 2012 )

10. Khamisov , O. : A global optimization approach to solving equilibrium programming problems . In: Pardalos, P.M. , Tseveendorj , I. , Enkhbat , R . (eds.) Optimization and Optimal Control . pp. 155 { 164 . World Scienti c ( 2003 )

11. Khamisov , O.V. : Numerical Solution for Special Quadratic Nonconvex Programming Problems . Discrete Analysis and Operations Research 12 , 81 { 91 ( 2005 ), (in Russian)

12. L~a, Q.D. , Chew , Y.H. , Soong , B.-H. : Potential Game Theory . Springer, Cham ( 2016 )

13. Mallozzi , L.: An application of optimization theory to the study of equilibria for games: a survey . Cent. Eur. J. Oper. Res . 21 ( 3 ), 523 { 539 ( 2013 )

14. Minarchenko , I. : Search of Nash equilibrium in quadratic n-person game . In: Kochetov, Y. , Khachay , M. , Beresnev , V. , Nurminski , E. , Pardalos , P. (eds.) Discrete Optimization and Operations Research. DOOR 2016. LNCS , vol. 9869 , pp. 509 { 521 . Springer, Cham ( 2016 )

15. Monderer , D. , Shapley , L.S.: Potential games . Games Econ. Behav . 14 ( 1 ), 124 { 143 ( 1996 )

16. Nikaido , H. , Isoda , K. : Note on noncooperative convex games . Pac. J. Math. 5 ( 5 ), 807 - 815 ( 1955 )

17. Rosen , J.B. : Existence and uniqueness of equilibrium points for concave n-person games . Econometrica 33 ( 3 ), 520 { 534 ( 1965 )

18. Strekalovsky , A.S.: On local search in D.C. optimization problems . Applied Mathematics and Computation 255 , 73 { 83 ( 2015 )

19. Voorneveld , M. : Best-response potential games . Econ. Lett . 66 ( 3 ), 289 { 295 ( 2000 )

20. Uryas 'ev, S., Rubinstein , R.Y.: On Relaxation Algorithms in Computation of Noncooperative Equilibria . IEEE Trans. Autom. Control 39 ( 6 ), 1263 { 1267 ( 1994 )

21. Zukhovitskiy , S.I. , Polyak , R.A. , Primak , M.E. : Many-person convex games . Economics and Math. Methods 7 ( 6 ), 888 { 900 ( 1971 ), (in Russian)