UDC 518.9

MATHEMATICS

S. I. Zukhovitskii, R. A. Polyak, M. E. Primak

TWO METHODS FOR FINDING EQUILIBRIUM POINTS OF CONCAVE \(n\)-PERSON GAMES

(Presented by Academician A. Yu. Ishlinskii, 19 IV 1968)

1. Let there be given continuous functions \(\varphi_i(x_1,\ldots,x_i,\ldots,x_n)\) \((i=1,\ldots,n)\), concave in \(x_i\) for fixed \(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n\), where \(x_i\in E^{m_i}\), and a bounded convex closed domain
\[ \Omega=\{(x_1,\ldots,x_i,\ldots,x_n)\mid h_j(x)=h_j(x_1,\ldots,x_i,\ldots,x_n)\ge 0,\ j=1,\ldots,m\}, \]
where the \(h_j(x)\) are concave functions.

A point \(x^*=(x_1^*,\ldots,x_i^*,\ldots,x_n^*)\in\Omega\) is called an equilibrium point of a concave \(n\)-person game if
\[ \varphi_i(x_1^*,\ldots,x_i^*,\ldots,x_n^*) = \max\{\varphi_i(x_1^*,\ldots,x_i,\ldots,x_n^*)\mid (x_1^*,\ldots,x_i,\ldots,x_n^*)\in\Omega\} \]
\[ (i=1,\ldots,n). \]

The problem of finding equilibrium points with \(\Omega=\Omega_1\times\Omega_2\times\cdots\times\Omega_n\) \((\Omega_i\subset E^{m_i})\) was first studied in \((^1)\).

In \((^2)\), for \(n\)-person games with
\[ \Omega=\{(x_1,\ldots,x_i,\ldots,x_n)\mid h_j(x)\ge 0,\ j=1,\ldots,m\}, \]
an existence and uniqueness theorem was established for the so-called normalized equilibrium point \(x^*\in\Omega\), i.e., an equilibrium point for which
\[ \sum_{i=1}^{n}\varphi_i(x_1^*,\ldots,x_i^*,\ldots,x_n^*) = \max\left\{\sum_{i=1}^{n}\varphi_i(x_1^*,\ldots,x_i,\ldots,x_n^*)\mid (x_1,\ldots,x_i,\ldots,x_n)\in\Omega\right\}, \]
and an algorithm was given for finding such points, close to the gradient projection method \((^3)\)*.

Let \(\nabla_i\varphi_i(x)\) be the vector composed of the partial derivatives of the function \(\varphi_i(x)\) with respect only to the components of the vector \(x_i\), and let
\[ g(x)=(\nabla_1\varphi_1(x),\nabla_2\varphi_2(x),\ldots,\nabla_n\varphi_n(x)). \]
We shall assume that the vector function \(g(x)\) is continuous and satisfies the so-called condition of strict decrease
\[ (g(y)-g(x),\,x-y)>0,\qquad \forall(x,y\in\Omega,\ x\ne y), \]
which ensures the uniqueness of the normalized equilibrium point \((^2)\).

In the present work two algorithms are constructed for finding a normalized equilibrium point.

The first of them is based on the equivalence of the problem of finding a normalized equilibrium point to the problem of finding a saddle point of the function \((g(y),x-y)\) in the domain \(\Omega\times\Omega\).

The second algorithm is a certain generalization of the method of steepest descent \((^4)\). A distinctive feature of the second algorithm consists in a special choice of the descent direction, characteristic of the method for the simultaneous solution of the primal and dual problems of convex programming \((^5)\), in which, along with the maximizing sequence, the Lagrange multipliers appearing in the formulation of the optimality criterion are also found.

The determination of the step size and the “smoothing,” eliminating the possibility of zigzag motion, are carried out with the aid of parameters \(\lambda_k\),

* Obviously, a normalized equilibrium point is also an ordinary equilibrium point, but the converse is not always true.

satisfying the conditions \(\lambda_k > 0,\ \lambda_k \to 0,\ \sum_k \lambda_k = \infty\), characteristic of generalized gradient descent methods \((^6)\).

1. Let us describe the first algorithm for finding a normalized equilibrium point, which, as was already noted above, reduces to finding

\[ \min_{y \in \Omega}\max_{x \in \Omega}(g(y), x-y)=\max_{x \in \Omega}\min_{y \in \Omega}(g(y), x-y). \]

As the initial approximation we choose an arbitrary point \(x^1 \in \Omega\). The new approximation \(x^2\) is found from the condition

\[ (g(x^1), x^2-x^1)=\max_{x \in \Omega}(g(x^1), x-x^1)=\mu_1 \geq 0, \]

i.e., we solve a convex programming problem.

Suppose that the approximations \(x^1, x^2, \ldots, x^k\) have already been found. Then the approximation \(x^{k+1}\) is found from the condition

\[ \min_{1 \leq i \leq k}(g(x^i), x^{k+1}-x^i) = \max_{x \in \Omega}\min_{1 \leq i \leq k}(g(x^i), x-x^i) = \mu_k \geq 0, \]

so that at the general step we again solve a convex programming problem.

In the case when \(\Omega\) is a polyhedron, at each step we solve a linear programming problem. In this case the algorithm described can be applied to solving a convex programming problem consisting in maximizing a concave function \(f(x_1,\ldots,x_n)\) on \(\Omega\). For this, evidently, it suffices to set \(g(x)=\nabla f(x)\) in the preceding algorithm. Such an algorithm is somewhat reminiscent in idea of the centered sections algorithm \((^7)\), but differs in that instead of the centers of gravity of the polyhedra \(\Omega_k=\Omega \cap \{x \mid (g(x^i), x-x^i)\geq 0,\ i=1,\ldots,k\}\), one seeks the Chebyshev centers (points) of the polyhedra \(\{x \mid (g(x^i), x-x^i)\geq 0,\ i=1,\ldots,k\}\) in the domain \(\Omega\).

1. Under the additional assumptions: 1) \(\|g(x)\|>0,\ \forall(x \in \Omega)\), 2) the set \(\Omega\) is strongly convex \((^8)\), convergence of the algorithm is established, as well as the estimates \(\mu_k=O(1/k),\ \|x^k-x^*\|=O(1/k)\).

In the case when at least one of conditions 1), 2) is not satisfied, it was possible only to establish the possibility of extracting from the sequence \(\{x^k\}\) a subsequence converging to \(x^*\). Let us dwell on this in more detail. Introduce the continuous in \(t\) and nondecreasing function

\[ \delta(t)=\min_{\substack{\|x-y\|\geq t\\ x,y \in \Omega}}(g(y)-g(x), x-y), \]

whose positivity for \(t>0\) ensures the condition of strict decrease of \(g(x)\). Let \(x^*\) be an equilibrium point and

\[ \min_{1 \leq i \leq k}\delta(\|x^i-x^*\|)=\delta(\|x^{i_k}-x^*\|). \]

Then

\[ \delta(\|x^{i_k}-x^*\|) \leq (g(x^i)-g(x^*), x^*-x^i) = (g(x^i), x^*-x^i)+(g(x^*), x^i-x^*) \leq (g(x^i), x^*-x^i) \quad (i=1,\ldots,k), \]

so that

\[ \delta(\|x^{i_k}-x^*\|) \leq \min_{1 \leq i \leq k}(g(x^i), x^*-x^i) \leq \mu_k. \]

But, as is not difficult to verify,

\[ \lim_{k \to \infty}\mu_k=0. \]

Therefore \(x^{i_k}\to x^*\). One can indicate a constructive method for extracting the sequence \(\{x^{i_k}\}\).

1. Let us now proceed to the description of the second algorithm. In what follows we shall assume that all functions \(h_j(x)\) are continuously differentiable and that the set \(\Omega\) satisfies Slater’s condition (i.e., has an interior point).

Choose an arbitrary sequence of positive parameters \(\lambda_k\) such that \(\lambda_k \to 0,\ \sum_k \lambda_k=\infty\), and as the initial approximation take some point \(x^0 \in \Omega\). Suppose that \(k\) steps of the algorithm have already been performed and an approximation \(x^k \in \Omega\) has been found. As the value of the smoothing para-

of the parameter \(\delta_{k+1}\) (see, for example, (4)) we take \(\lambda_{k+1}\) and denote by \(J(x^k,\lambda_{k+1})\) the set of indices \(j\) for which \(0 \le h_j(x^k) < \lambda_{k+1}\).

To find the “descent” direction from the point \(x^k\), we solve the following simple quadratic programming problem

\[ \begin{gathered} \min \left\{\left\|v_0 g(x^k)+ \sum_{j\in J(x^k,\lambda_{k+1})} v_j \nabla h_j(x^k)\right\|^2 \,\middle|\, v_0+ \right.\\ \left. +\sum_{j\in J(x^k,\lambda_{k+1})} v_j=1;\; v_0\ge 0,\; v_j\ge 0,\; j\in J(x^k,\lambda_{k+1})\right\}= \\ =\left\|v_0^{k+1} g(x^k)+ \sum_{j\in J(x^k,\lambda_{k+1})} v_j^{k+1}\nabla h_j(x^k)\right\|^2 =\|\xi^{k+1}\|^2 . \end{gathered} \tag{1} \]

As is known (see, for example, (5)), for the vector thus found the inequalities

\[ (g(x^k),\xi^{k+1})\ge \|\xi^{k+1}\|^2;\quad (\nabla h_j(x^k),\xi^{k+1})\ge \|\xi^{k+1}\|^2,\quad j\in J(x^k,\lambda_{k+1}) \tag{2} \]

hold.

If \(\|\xi^{k+1}\|>0\), then we proceed to find the step size \(t_{k+1}\) and the new approximation \(x^{k+1}\). To do this, we find
\(\max\{t\mid x^k+t\xi^{k+1}/\|\xi^{k+1}\|\in\Omega\}=\tau'_{k+1}\), set
\(t_{k+1}=\min\{\tau_{k+1},\lambda_{k+1}\}\), and compute the new approximation \(x^{k+1}\) by the formula
\(x^{k+1}=x^k+t_{k+1}\xi^{k+1}/\|\xi^{k+1}\|\). If, however, \(\|\xi^{k+1}\|=0\), then one should check whether the point \(x^k\) is a normalized equilibrium point. To this end, we solve problem (1), replacing the set
\(J(x^k,\lambda_{k+1})=\{j\mid 0\le h_j(x^k)<\lambda_{k+1}\}\) by the set
\(J(x^k)=\{j\mid h_j(x^k)=0\}\). If in this case too we obtain the zero vector \(\widetilde{\xi}^{\,k+1}\), then \(x^k\) is a normalized equilibrium point. Otherwise we compute a new approximation
\(x^{k+1}=x^k+\widetilde{t}_{k+1}\widetilde{\xi}^{\,k+1}/\|\widetilde{\xi}^{\,k+1}\|\), where \(\widetilde{t}_{k+1}\) is found by the same rules as \(t_{k+1}\).

1. Let us now verify that \(x^*\) is a limit point of the sequence \(\{x^k\}\), and indicate how to select from it a subsequence converging to \(x^*\).

Suppose the contrary. Then, for sufficiently large \(k\), we shall have \(\|\zeta^k\|\ge \gamma>0\), and there exists an \(\varepsilon\)-neighborhood \(S(x^*,\varepsilon)\) of the equilibrium point \(x^*\) containing no point of the sequence \(\{x^k\}\). Choose a point \(\widetilde{x}\in S(x^*,\varepsilon/2)\cap \operatorname{Int}\Omega\) so that

\[ \max\{(g(\widetilde{x}),x-\widetilde{x})\mid x\in\Omega\}\le \tfrac12\delta(\varepsilon/2). \]

For the chosen point \(\widetilde{x}\) we have

\[ 0<\delta(\varepsilon/2)\le \delta(\|x^k-\widetilde{x}\|) \le (g(x^k)-g(\widetilde{x}),\widetilde{x}-x^k)\le \le (g(x^k),\widetilde{x}-x^k)+\tfrac12\delta(\varepsilon/2). \]

Thus, finally,

\[ \alpha'\|g(x^k)\|= \frac{\tfrac12\delta(\varepsilon/2)\|g(x^k)\|}{\max\limits_{x\in\Omega}\|g(x)\|} \le \tfrac12\delta(\varepsilon/2) \le (g(x^k),\widetilde{x}-x^k). \tag{3} \]

Since \(\widetilde{x}\) belongs to \(\Omega\) together with some \(\varepsilon\)-neighborhood of its own, and since the half-spaces of vectors \(x\) for which

\[ 0\le (\nabla h_j(x^k),x-x^k)+\lambda_{k+1},\quad j\in J(x^k,\lambda_{k+1}), \]

contain \(\Omega\), it follows that

\[ \widetilde{\varepsilon}\|\nabla h_j(x^k)\| \le (\nabla h_j(x^k),\widetilde{x}-x^k)+\lambda_{k+1},\quad j\in J(x^k,\lambda_{k+1}). \tag{4} \]

Multiplying (3) by \(v_0^{k+1}\), (4) by \(v_j^{k+1}\), and adding term by term, for sufficiently large \(k\) we obtain

\[ \left(\frac{\xi^{k+1}}{\|\xi^{k+1}\|},\widetilde{x}-x^k\right) \ge \alpha-\frac{1}{\eta}\lambda_{k+1} \ge \frac{\alpha}{2}>0, \tag{5} \]

where \(\alpha=\min\{\varepsilon,\alpha'\}\).

For sufficiently large \(k\), by virtue of (5) we obtain the inequality

\[ \|x^k-\bar{x}\|^2-\|x^{k+1}-\bar{x}\|^2 \geq \frac{\alpha}{2}\,t_{k+1}, \]

which leads to a contradiction, since \(\sum_k t_k=\infty\).

A subsequence of the sequence \(\{x^k\}\) converging to \(x^*\) can be constructed, for example, as follows. As the first term of the subsequence choose \(x^0=x^{k_0}\). As the second term of the subsequence take the approximation \(x^{k_1}\ne x^{k_0}\) with the smallest index for which \(\|\xi^{k_1+1}\|\leq \|\xi^{k_0+1}\|\). As the third term of the subsequence take the point \(x^{k_2}\ne x^{k_1}\) with the smallest index for which \(\|\xi^{k_2+1}\|\leq \|\xi^{k_1+1}\|\), \(k_2>k_1\), and so on. For the subsequence thus constructed, \(\|\xi^{k_i+1}\|\to 0\) and \(x^{k_i}\to x^*\).

The algorithm presented in Sec. 4 can be used to solve a convex programming problem by regarding it as a concave two-person game whose equilibrium point coincides with the saddle point of the Lagrange function. The algorithm for solving a convex programming problem obtained in this way is close in form to the small-step methods \((^9)\) and differs from these methods in the way the step size is computed and in the introduction, at each step, of a smoothing parameter which, generally speaking, accelerates the process.

Moscow Civil Engineering Institute
named after V. V. Kuibyshev

Computing Center of the USSR State Planning Committee

Received
19 V 1968

REFERENCES

\(^1\) J. F. Nash, Proc. Nat. Acad. Sci. U.S.A., 36 (1950).
\(^2\) J. B. Rosen, Econometrica, 33, No. 3 (1965).
\(^3\) J. B. Rosen, J. Soc. Ind. Appl. Math., 9, No. 4 (1961).
\(^4\) S. I. Zukhovitskii, R. A. Polyak, M. E. Primak, DAN, 163, No. 2 (1965).
\(^5\) R. A. Polyak, Economic Cybernetics and Operations Research, 3, 1966.
\(^6\) N. Z. Shor, Dissertation, Kiev, 1964.
\(^7\) A. Yu. Levin, DAN, 160, No. 6 (1965).
\(^8\) E. S. Levitin, B. T. Polyak, Journal of Computational Mathematics and Mathematical Physics, 6, No. 5 (1966).
\(^9\) K. J. Arrow, L. Hurwicz, H. Uzawa, Studies in Linear and Nonlinear Programming, IL, 1962.