UDC 518:512.25

MATHEMATICS

N. T. TYNYANSKII

GENERAL CONCAVE-CONVEX GAMES

(Presented by Academician L. V. Kantorovich on 15 V 1968)

Let a game \(G=[U;V;f]\) be given, where the strategy sets \(U\) and \(V\) are arbitrary convex sets lying in the Euclidean spaces \(E^k\) and \(E^l\), respectively, and the kernel of the game \(G\) is a concave-convex function \(f(u;v)\), concave and upper semicontinuous in the variable \(u\) for each fixed \(v\in V\), and convex and lower semicontinuous in the variable \(v\) for each fixed \(u\in U\), satisfying the closedness condition consisting in the fact that every point \((u^0,v^0)\in E^{k+l}\) at which \(\lim\limits_{u\in U,\ u\to u^0} f(u;v)\) for all \(v\in V\) and \(\lim\limits_{v\in V,\ v\to v^0} f(u;v)\) for all \(u\in U\) are finite belongs to the domain of definition \(U\times V\), and
\[ f(u^0,v^0)=\lim_{u\in U,\ u\to u^0} f(u;v^0)=\lim_{v\in V,\ v\to v^0} f(u^0;v). \]

A situation \((u^0,v^0)\) is called an equilibrium situation (\(\varepsilon\)-equilibrium) if \(f(u^0,v)\geq f(u^0,v^0)\geq f(u;v^0)\) \(\bigl(f(u^0,v)+\varepsilon\geq f(u^0,v^0)\geq f(u;v^0)-\varepsilon\bigr)\) for all \((u;v)\in U\times V\).

To the study of the game \(G\) we shall apply the method of constructing dual optimization problems and a dual game, proposed in \((^4)\). For the construction of dual problems it is necessary to represent the function \(f(u;v)\) and its domain of definition \(U\times V\) in the form
\[ f(u;v)=f_1(u;v)+f_2(u;v),\qquad U=U_1\cap U_2,\qquad V=V_1\cap V_2, \]
where \(f_i(u;v)\) is a closed concave-convex function defined on the direct product of the convex sets \(U_i\) and \(V_i\) \((i=1,2)\), lying in \(E^k\) and \(E^l\), respectively.

This can be done in many ways. This makes it possible in each particular case to choose the most suitable representation.

A. Let us introduce the following notation. Let
\[ f_1(u;v)=f_2(u;v)=\tfrac12 f(u;v),\qquad U_1=U_2=U,\qquad V_1=V_2=V. \]
Then

I.
\[ \varphi(\gamma;v)=\varphi_1(\gamma;v)=\varphi_2(\gamma;v) =\sup_{u\in U}\left[\tfrac12 f(u;v)+(\gamma,u)\right] \]
with domain of definition
\[ (\Gamma;V)=(\Gamma_1;V_1)=(\Gamma_2;V_2) =\{(\gamma;v)\in E^{k+l}\mid v\in V,\ \varphi(\gamma;v)<\infty\}; \]
\[ \psi(u;\delta)=\psi_1(u;\delta)=\psi_2(u;\delta) =\inf_{v\in V}\left[\tfrac12 f(u;v)-(\delta,v)\right] \]
with domain of definition
\[ (U;\Delta)=(U_1;\Delta_1)=(U_2;\Delta_2) =\{(u;\delta)\in E^{k+l}\mid u\in U;\ \psi(u;\delta)>-\infty\}. \]

The functions \(\varphi(\gamma;v)\) and \(\psi(u;\delta)\) are conjugate (see \((^5)\)).

II. If the function
\[ g'(\gamma;\delta)=g'_1(\gamma;\delta)=g'_2(\gamma;\delta) =\inf_{v\in V}\sup_{u\in U}\left[\tfrac12 f(u;v)+(\gamma,u)-(\delta,v)\right], \]
having finite values on \(\Gamma\times\Delta\), is lower semicontinuous in \(\gamma\), or the function
\[ g''(\gamma;\delta)=g''_1(\gamma;\delta)=g''_2(\gamma;\delta) =\sup_{u\in U}\inf_{v\in V}\left[\tfrac12 f(u;v)+(\gamma,u)-(\delta,v)\right], \]
also finite on \(\Gamma\times\Delta\), is upper semicontinuous in \(\delta\), then \(g'(\gamma;\delta)=\)

\(= g'(\gamma;\delta) = g(\gamma;\delta)\) is a closed convex-concave function on \(\Gamma \times \Delta\).

If in the defining relations for \(\varphi\), \(\psi\), and \(g\) the signs before the scalar products are changed to the opposite ones, then we obtain new functions with their domains of definition \(\varphi(-\gamma;v)\), \((-\Gamma;V)\), \(\psi(u;-\delta)\), \((U;-\Delta)\), \(g(-\gamma;-\delta)\), \((-\Gamma;-\Delta)\).

B. We now formulate the following optimization problems.

Problem I. Find
\[ \min_{v\in V}\sup_{u\in U} f(u;v). \]

Problem I′. Find
\[ \max_{u\in U}\inf_{v\in V} f(u;v). \]

Problem II. Find
\[ \min_{(\gamma;v)\in(\Gamma;V)\cap(-\Gamma;V)} [\varphi(\gamma;v)+\varphi(-\gamma;v)]. \]

Problem II′. Find
\[ \max_{(u;\delta)\in(U;\Delta)\cap(U;-\Delta)} [\psi(u;\delta)+\psi(u;-\delta)]. \]

Problem III. Find
\[ \min_{\gamma\in\Gamma\cap(-\Gamma)} \sup_{\delta\in\Delta\cap(-\Delta)} [g(\gamma;\delta)+g(-\gamma;-\delta)]. \]

Problem III′. Find
\[ \max_{\delta\in\Delta\cap(-\Delta)} \inf_{\gamma\in\Gamma\cap(-\Gamma)} [g(\gamma;\delta)+g(-\gamma;-\delta)]. \]

A problem in which the optimal value of the objective function is attained is called solvable, and in the case where the optimal value exists but is not attained, weakly solvable.

With respect to the weak solvability of the formulated problems, the following assertions hold.

B₁. If the sets \((\Gamma;V)\cap(-\Gamma;V)\) and \((U;\Delta)\cap(U;-\Delta)\) are nonempty, then all the formulated problems are weakly solvable and their optimal values are equal.

B₂. In order that all the problems be weakly solvable, it is necessary and sufficient that the origin of the coordinates of the space \(E^{k+l}\) belong to the set \(\Gamma\times\Delta\).

Concerning solvability of the problems, we have:

B₃. If Problems II and II′ are solvable, then all the problems are solvable and their optimal values are equal.

B₄. Problems II and II′ are solvable if and only if Problems I and I′ are solvable, and all optimal values are equal.

B₅. If the origin of the coordinates of the space \(E^{k+l}\) is an interior point of the set \(\Gamma\times\Delta\), then all the problems are solvable and their optimal values are equal.

C. We pass to the question of the existence of an equilibrium situation in the game \(G\).

Put \(\widetilde G=[\widetilde\Gamma;\widetilde\Delta;\widetilde g]\), where \(\widetilde\Gamma=\Gamma\cap(-\Gamma)\), \(\widetilde\Delta=\Delta\cap(-\Delta)\), \(\widetilde g(\gamma;\delta)=g(\gamma;\delta)+g(-\gamma;-\delta)\). The game \(\widetilde G\) thus defined is called dual to the game \(G\).

Theorem 1. If the sets \((\Gamma;V)\cap(-\Gamma;V)\) and \((U;\Delta)\cap(U;-\Delta)\) are nonempty, then the games \(G\) and \(\widetilde G\) have \(\varepsilon\)-equilibrium situations for any \(\varepsilon>0\).

Theorem 2. The following conditions are equivalent:

1) The game \(G\) has an \(\varepsilon\)-equilibrium situation for any \(\varepsilon>0\).

2) The game \(G\) has an \(\varepsilon\)-equilibrium situation for a fixed \(\varepsilon>0\).

3) The expressions
\[ \inf_{v\in V}\sup_{u\in U} f(u;v) \quad\text{and}\quad \sup_{u\in U}\inf_{v\in V} f(u;v) \]
exist, i.e., take finite values.

4) There exist \(u^0\in U\) and \(v^0\in V\) such that the expressions \(\inf_{v\in V} f(u^0;v)\) and \(\sup_{u\in U} f(u;v^0)\) have finite values.

5) The sets \((\Gamma;V)\cap(-\Gamma;V)\) and \((U;\Delta)\cap(U;-\Delta)\) are nonempty.

6) The origin of the coordinates of the space \(E^{k+l}\) belongs to the set \(\Gamma\times\Delta\).

Theorem 3. The following assertions hold:

1) If problems II and II′ are solvable, then the games \(G\) and \(\widetilde G\) have an equilibrium situation.

2) Problems II and II′ are solvable if and only if the game \(G\) has an equilibrium situation.

3) The game \(G\) has an equilibrium situation if and only if the expressions
\[ \min_{v\in V}\sup_{u\in U} f(u;v)\quad\text{and}\quad \max_{u\in U}\inf_{v\in V} f(u;v). \]

The games \(G\) and \(\widetilde G\) have an equilibrium situation, and the mathematical programming problems dual to them are solvable in the following cases:

1. The sets \((\Gamma;V)\cap(-\Gamma;V)\) and \((U;\Delta)\cap(U;-\Delta)\) are bounded.

2. The set \((\Gamma;V)\cap(-\Gamma;V)\) \(((U;\Delta)\cap(U;-\Delta))\) is bounded and has a relative interior point.

3. The sets \((\Gamma;V)\cap(-\Gamma;V)\) and \((U;\Delta)\cap(U;-\Delta)\) have interior points.

4. The sets \(U\) and \(V\) are bounded.

5. The origin of the space \(E^{k+l}\) belongs to the set \(\Gamma\times\Delta\) and is a relative interior point of this set.

D. Consider the following convex programming problem. Let continuous concave functions \(p(u), q_1(u),\ldots,q_l(u)\) be given, defined on the closed convex set \(U=\{u\in E^k\mid u\geq 0\}\). Then the problem is posed:

Find \(u^0\in U_q=\{u\in E^k\mid u\geq0,\ q(u)=(q_1(u),\ldots,q_l(u))\geq0\}\), at which the scalar function \(p(u)\) attains its greatest value.

The Lagrange function \(L(u;v)\) of this problem has the form \(L(u;v)=p(u)+(v,q(u))\), with closed domain \(U\times V\), where \(V=\{v\in E^l\mid v\geq0\}\).

By construction, \(L(u;v)\) is a closed concave-convex function, and all the results given above are applicable to it. But in this case another representation also suggests itself, namely:
\[ f_1(u;v)=p(u),\quad f_2(u;v)=(v,q(u)),\quad U_1=U_2=U,\quad V_1=V_2=V. \]

Carrying out constructions analogous to the constructions of points A and B (see also (4)), we obtain two dual convex optimization problems and a dual game. We give the corresponding relations for \(\varphi_i\) and \(\psi_i\) \((i=1,2)\):
\[ \varphi_1(\gamma;v)=\sup_{u\in U_1}[f_1(u;v)+(\gamma,u)] =\sup_{u\in U}[p(u)+(\gamma,u)], \]
\[ (\Gamma_1;V)=\{(\gamma;v)\in E^{k+l}\mid v\geq0,\ \varphi_1(\gamma;v)<\infty\}, \]
\[ \varphi_2(-\gamma;v)=\sup_{u\in U_2}[f_2(u;v)-(\gamma,u)] =\sup_{u\in U}[(v,q(u))-(\gamma,u)], \]
\[ (-\Gamma_2;V)=\{(\gamma;v)\in E^{k+l}\mid v\geq0,\ \varphi_2(-\gamma;v)<\infty\}, \]
\[ \psi_1(u;\delta)=p(u),\quad (U;\Delta_1)=\{(u;\delta)\in E^{k+l}\mid \delta\geq0,\ u\geq0\}, \]
\[ \psi_2(u;\delta)\equiv0, \]
\[ (U;-\Delta_2)=\{(u;\delta)\in E^{k+l}\mid q(u)+\delta\geq0,\ u\geq0\}. \]

Problem II′a. Find
\[ \max_{(u;\delta)\in(U;\Delta_1)\cap(U;-\Delta_2)} [\psi_1(u;\delta)+\psi_2(u;-\delta)]. \]

This problem is equivalent to the original problem.

Problem IIa. Find
\[ \min_{(\gamma;v)\in(\Gamma_1;V)\cap(-\Gamma_2;V)} [\varphi_1(\gamma;v)+\varphi_2(-\gamma;v)]. \]

We shall call problem IIa dual to the original one by virtue of the Lagrange function. The duality of problems II′a and IIa is the duality that arises when conjugate functions are used (see, for example, (¹), Ch. 7).

Theorem 4. The Lagrange function \(L(u; v)\) has a saddle point (equilibrium situation) if and only if the original convex programming problem and the problem dual to it by virtue of the Lagrange function are solvable and have equal optimal values (cf. \((3,6)\)).

A complete proof of the results presented is given in (⁷).

CITED LITERATURE

¹ S. Karlin, Mathematical Methods in Game Theory, Programming, and Economics, Moscow, 1964.
² L. V. Kantorovich, G. P. Akilov, Functional Analysis in Normed Spaces, Moscow, 1959.
³ H. W. Kuhn, A. W. Tucker, Proc. II Berkeley Symposium on Mathematical Statistics and Probability, 1951, p. 481.
⁴ V. N. Lebedev, N. T. Tynianskii, DAN, 174, No. 6 (1967).
⁵ W. Fenshel, Canad. J. Math., 1, 73 (1949).
⁶ I. J. Arrow, A. Hurwicz, H. Uzawa, Studies in Linear and Nonlinear Programming, Moscow, 1962.
⁷ N. T. Tynianskii, Fundamentals of the Theory of Duality of Nonlinear Programming Problems and Differential Games, Moscow, 1968.