On Equilibrium Problems

Summary

In this chapter we give an overview of the theory of scalar equilibrium problems. To emphasize the importance of this problem in nonlinear analysis and in several applied fields we first present its most important particular cases as optimization, Kirszbraun’s problem, saddlepoint (minimax) problems, and variational inequalities. Then, some classical and new results together with their proofs concerning existence of solutions of equilibrium problems are exposed. The existence of approximate solutions via Ekeland’s variational principle – extended to equilibrium problems – is treated within the last part of the chapter.

Work supported by the grant PNII, ID 523/2007

1 Introduction

One of the most important problems in nonlinear analysis is the so-called equilibrium problem, which can be formulated as follows. Let A and B be two nonempty sets and $f : A\times B\to \mathbb{R}$ a given function. The problem consists in finding an element $a\in A$ such that

$$f(a,b) \ge 0 \quad \forall b\in B.$$

((EP))

(EP) has been extensively studied in recent years (e.g. [6, 7, 8, 9, 10, 17, 18, 19, 22] and the references therein). One of the reasons is that it has among its particular cases, optimization problems, saddlepoint (minimax) problems, variational inequalities (monotone or otherwise), Nash equilibrium problems, and other problems of interest in many applications (see [10] for a survey).

As far as we know the term “equilibrium problem” was attributed in [10], but the problem itself has been investigated more than 20 years before a paper of Ky Fan [15] in connection with the so-called intersection theorems (i.e., results stating the nonemptiness of a certain family of sets). Ky Fan considered (EP) in the special case $A = B$ a compact convex subset of a Hausdorff topological vector space and termed it “minimax inequality.” Within short time (in the same year) Brézis, Nirenberg, and Stampacchia [11] improved Ky Fan’s result, extending it to a not necessarily compact set, but assuming instead a so-called coercivity condition, which is automatically satisfied when the set is compact.

Recent result on (EP) emphasizing existence of solutions can be found in [6, 7, 8, 28], and many other papers. New necessary (and in some cases also sufficient) conditions for existence of solutions in infinite dimensional spaces were proposed in [18], and later on simplified and further analyzed in [17].

Looking on the proofs given for existence results, one may detect two fundamental methods: fixed point methods (intersection theorems mostly based on Brouwer’s fixed point theorem) and separation methods (Hahn–Banach type theorems). It is an old conjecture whether Brouwer’s fixed point theorem can be proved using (only) separation results.

The aim of this chapter is to provide an overlook on (EP) by emphasizing its most important particular cases, to expose some classical and recent existence results of it, and to deal with approximate solutions, which, in case the exact solution does not exist, may have an important role.

The chapter is divided into four sections (including Introduction). In Section 2, the most important particular cases of (EP) such as the minimum problem, Kirszbraun’s problem, saddlepoint problem (in connection with game theory, duality in optimization, etc.), and variational inequalities are presented. The next section is devoted to several existence results on (EP). First we focus on results which use fixed point tools and show that these results form an equivalent chain which includes Brouwer’s and Schauder’s fixed point theorems, Knaster–Kuratowski–Mazurkiewitz and Ky Fan’s intersection theorems, Ky Fan’s minimax inequality theorem. Then we expose some recent results on (EP) using separation tools. Finally, in Section 4 (EP) and its more general case, the system of equilibrium problems (abbreviated (SEP)), are discussed in connection with the famous Ekeland’s variational principle. The latter has been established for optimization problems and guarantees the existence of the so-called approximate minimum points. Based on recent results of the author, the extensions of Ekeland’s variational principle for (EP) and (SEP) are given under suitable conditions. These results are useful tools in obtaining new existence results for (EP) and (SEP) without any convexity assumptions on the sets and functions involved.

2 The Equilibrium Problem and Its Important Particular Cases

To underline the importance of (EP) we present in this section some of its various particular cases which have been extensively studied in the literature. The most of them are important models of real-life problems originated from mechanics, economy, biology, etc.

2.1 The Minimum Problem

For $A=B$ and $F: A\to \mathbb{R}$, let $f(a,b):= F(b)-F(a)$. Then each solution of (EP) is a minimum point of F and vice versa.

2.2 The Kirszbraun’s Problem

Let m and n be two positive integers and consider two systems of closed balls in $\mathbb{R}^n: (B_i)$ and $(B^{\prime}_i),\,\, i\in\{1,2,\ldots,m\}$. Denote by $r(B_i)$ and $d(B_i,B_j)$ the radius of B _i and the distance between the centers of B _i and B _j , respectively. The following result is known in the literature as Kirszbraun’s theorem (see [24]).

Theorem 1.

Suppose that

• (a) $\cap_{i=1}^mB_i\neq\emptyset$;

• (b) $r(B_i)=r(B^{\prime}_i)$, for all $i\in \{1,2,\ldots,m\}$;

• (c) $d(B^{\prime}_i,\,B^{\prime}_j)\le d(B_i,\,B_j)$, for all $i,j\in\{1,2,\ldots,m\}$.

Then $\cap_{i=1}^mB^{\prime}_i\neq\emptyset$.

To relate this result to (EP), let $A:= \mathbb{R}^n, B:=\{(x_i,y_i)|\, i\in \{1,2,\ldots,m\}\} \subseteq \mathbb{R}^n\times \mathbb{R}^n$ such that

$$\|y_i-y_j\|\le \|x_i-x_j\| \quad \forall i,j\in \{1,2,\ldots,m\}.$$

((1))

Choose an arbitrary element $x\in \mathbb{R}^n$ and put

$$f(y,b_i):= \|x-x_i\|^2 - \|y-y_i\|^2$$

((2))

for each $y\in \mathbb{R}^n$ and $b_i = (x_i,y_i)\in B$. Then $y\in \mathbb{R}^n$ is a solution of (EP) if and only if

$$\|y-y_i\|\le \|x-x_i\| \quad \forall i\in\{1,2,\ldots,m\}.$$

((3))

It is easy to see by Theorem 1 that the equilibrium problem given by the function f defined in (2) has a solution. Indeed, let $x\in \mathbb{R}^n$ be fixed and put $r_i:= \|x-x_i\|$ for $i:=1,2,\ldots,m.$ Take B _i the closed ball centered at x _i with radius r _i and $B^{\prime}_i$ the closed ball centered at y _i with radius r _i . Obviously, by (1), the assumptions of Theorem 1 are satisfied, hence there exists an element $y\in \mathbb{R}^n$ which satisfies (3).

Observe that, by compactness (i.e., the closed balls in $\mathbb{R}^n$ are compact sets), Theorem 1 of Kirszbraun remains valid for an arbitrary family of balls. More precisely, instead of the finite set $\{1,2,\ldots,m\}$, one can take an arbitrary set I of indices. Using this observation, it is easy to derive the following result concerning the extensibility of an arbitrary nonexpansive function to the whole space. Let $D\subseteq \mathbb{R}^n,\, D\neq \mathbb{R}^n$, and $f:D\to \mathbb{R}^n$ a given nonexpansive fun- ction, i.e.,

$$\|f(x)-f(y)||\le \|x-y||\quad\forall x,y\in D.$$

Then there exists a nonexpansive function $\bar f: \mathbb{R}^n\to \mathbb{R}^n$ such that $\bar f(x)=f(x)$, for each $x\in D$. Indeed, let $z\in \mathbb{R}^n\setminus D$ and take for each $x\in D$ the number $r_x:=\|z-x\|$. Let B _x be the closed ball centered at x with radius r _x and let $B^{\prime}_x$ be the closed ball centered at f(x) with radius r _x . Then we obtain that the set $\cap_{x\in D}B^{\prime}_x$ is nonempty. Now for $\bar f(z)\in \cap_{x\in D}B^{\prime}_x$, the conclusion follows.

2.3 The Saddlepoint (Minimax Theorems)

Next we turn to show a situation where the solution of the equilibrium problem reduces to a of a bifunction. Let X, Y be two nonempty sets and $h:X\times Y\to \mathbb{R}$ be a given function. The pair $(x_0,y_0)\in X\times Y$ is called a saddlepoint of h on the set $X\times Y$ if

$$h(x,y_0)\le h(x_0,y_0)\le h(x_0,y)\quad\forall (x,y)\in X\times Y.$$

((4))

Let $A=B=X\times Y$ and let $f:A\times B\to \mathbb{R}$ defined by

$$f(a,b):=h(x,v)-h(u,y)\quad\forall a=(x,y),\, b=(u,v).$$

((5))

Then each solution of the equilibrium problem (EP) is a saddlepoint of h and vice versa.

The saddlepoint can be characterized as follows. Suppose that for each $x\in X$ there exists $\min_{y\in Y}h(x,y)$ and for each $y\in Y$ there exists $\max_{x\in X}h(x,y)$. Then we have the following result.

Proposition 1.

f admits a saddlepoint on $X\times Y$ if and only if there exist $\max_{x\in X}\min_{y\in Y}f(x,y)$ and $\min_{y\in Y}\max_{x\in X}f(x,y)$ and they are equal.

Proof.

Suppose first that h admits a saddlepoint $(x_0,y_0)\in X\times Y$. Then by relation (4) one obtains

$$\min_{y\in Y}h(x,y) \le h(x,y_0) \le h(x_0,y_0) = \min_{y\in Y}h(x_0,y) \quad \forall x\in X$$

and

$$\max_{x\in X}h(x,y) \ge h(x_0,y) \ge h(x_0,y_0) = \max_{x\in X}h(x,y_0) \quad \forall y\in Y.$$

Therefore,

$$\min_{y\in Y}h(x_0,y) = \max_{x\in X}\min_{y\in Y}h(x,y)$$

and

$$\max_{x\in X}h(x,y_0) = \min_{y\in Y}\max_{x\in X}h(x,y),$$

and both equal to $h(x_0,y_0)$. For the reverse implication take $x_0\in X$ such that

$$\min_{y\in Y}h(x_0,y) = \max_{x\in X}\min_{y\in Y}h(x,y)$$

and $y_0\in Y$ such that

$$\max_{x\in X}h(x,y_0) = \min_{y\in Y}\max_{x\in X}h(x,y).$$

Then by our assumption we obtain

$$\min_{y\in Y}h(x_0,y) = \max_{x\in X}h(x,y_0);$$

therefore, in the obvious relations

$$\min_{y\in Y}h(x_0,y) \le h(x_0,y_0) \le \max_{x\in X}h(x,y_0)$$

one obtains equality in both sides. This completes the proof.

Remark 1.

Observe that, for arbitrary nonempty sets X, Y and function $h: X\times Y\to \mathbb{R}$, the inequality

$$\sup_{x\in X}\inf_{y\in Y}h(x,y) \le \inf_{y\in Y} \sup_{x\in X}h(x,y)$$

always holds. Therefore,

$$\max_{x\in X}\min_{y\in Y}h(x,y) \le \min_{y\in Y}\max_{x\in X}h(x,y)$$

holds either, provided these two values exist.

One of the main issues in minimax theory is to find sufficient and/or necessary conditions for the sets X, Y and function h, such that the reverse inequality in the above relations also holds. Such results are called minimax theorems.

Minimax theorems or, in particular, the existence of a saddlepoint, is important in many applied fields of mathematics. One of them is the game theory.

2.3.1 Two-Player Zero-Sum Games

To introduce a static two-player zero-sum (noncooperative) game (for more details and examples, see [2, 3, 20, 26, 27, 32]) and its relation to a minimax theorem we consider two players called 1 and 2 and assume that the set of pure strategies (also called actions) of player 1 is given by some nonempty set X, while the set of pure strategies of player 2 is given by a nonempty set Y. If player 1 chooses the pure strategy $x\in X$ and player 2 chooses the pure strategy $y\in Y,$ then player 2 has to pay player 1 an amount h(x, y) with $h:A\times B\rightarrow R$ a given function. This function is called the payoff function of player 1. Since the gain of player 1 is the loss of player 2 (this is a so-called zero-sum game) the payoff function of player 2 is $-h$. Clearly player 1 likes to gain as much profit as possible. However, at the moment he does not know how to achieve this and so he first decides to compute a lower bound on his profit. To compute this lower bound player 1 argues as follows: if he decides to choose action $x\in X,$ then it follows that his profit is at least $\inf_{y\mathbf{\in}Y}h(x,y)$, irrespective of the action of player 2. Therefore a lower bound on the profit for player 1 is given by

$$r_{\ast}:=\sup\limits_{x\in X}\inf\limits_{y\in Y}h(x,y).$$

((6))

Similarly player 2 likes to minimize his losses but since he does not know how to achieve this he also decides to compute first an upper bound on his losses. To do so, player 2 argues as follows. If he decides to choose action $y\in Y,$ it follows that he loses at most $\sup_{x\in X}h(x,y)$ and this is independent of the action of player 1. Therefore an upper bound on his losses is given by

$$r^{\ast}:=\inf\limits_{y\in Y}\sup\limits_{x\in X}h(x,y).$$

((7))

Since the profit of player 1 is at least $r_{\ast}$ and the losses of player 2 are at most $r^{\ast}$ and the losses of player 2 are the profits of player 1, it follows directly that $r_{\ast}\leq r^{\ast}$. In general $r_{\ast} <r^{\ast}$, but under some properties on the pure strategy sets and payoff function one can show that $r_{\ast}=r^{\ast}$. If this equality holds and in relations (6) and (7) the suprema and infima are attained, an optimal strategy for both players is obvious. By the interpretation of $r_{\ast}$ for player 1 and the interpretation of $r^{\ast}$ for player 2 and $r^{\ast}=r_{\ast}:=v$ both players will choose an action which achieves the value v and so player 1 will choose that action $x_{0}\in X$ satisfying

$$\inf\limits_{y\in Y}h(x_{0},y)=\max\limits_{x\in X}\inf\limits_{y\in Y}h(x,y).$$

Moreover, player 2 will choose that strategy $y_{0}\in Y$ satisfying

$$\sup\limits_{x\in X}h(x,y_{0})=\min\limits_{y\in Y}\sup\limits_{x\in X}h(x,y).$$

Another field, where the concept of saddlepoint plays an important role, is the so-called duality in optimization.

2.3.2 Duality in Optimization

Let X be a nonempty subset of $\mathbb{R}^n$. A subset K of $\mathbb{R}^m$ is called cone if, for each $y\in K$ and $\lambda > 0$, it follows that $\lambda y\in K$. The set K is called convex cone, if K is a cone and additionally, a convex set. Let $F: \mathbb{R}^n\to \mathbb{R}$ and $G: \mathbb{R}^n\to \mathbb{R}^m$ be given functions. For K, a nonempty convex cone of $\mathbb{R}^m$, define the following optimization problem:

$$v(P):=\inf\{F(x)|\, G(x)\in -K,\, x\in X\}.$$

((8))

This (general) problem has many important particular cases.

The Optimization Problem with Inequality and Equality Constraints. Let $X:=\mathbb{R}^n, K:= \mathbb{R}^p_+\times \{0_{\mathbb{R}^{m-p}}\}$, where $1\le p < m$, and $0_{\mathbb{R}^{m-p}}$ denotes the origin of the space $\mathbb{R}^{m-p}$. Then problem (8) reduces to the classical optimization problem with inequality and equality constraints

$$\inf\{F(x)| G_i(x) \le 0, i=1,2,\ldots,p, G_j(x) = 0, j=p+1,\ldots,m\}.$$

The Linear Programming Problem. Let

$$X:=\mathbb{R}^n_+, \quad K:=\{0_{\mathbb{R}^m}\}, \quad F(x):= c^Tx, \quad G(x):= Ax-b,$$

where A is a matrix with m rows and n columns (with all entries real numbers), $c\in \mathbb{R}^n$ and $b\in\mathbb{R}^m$ are given elements. Then (8) reduces to the following linear programming problem:

$$\inf\{c^Tx| Ax=b, x \ge 0\}.$$

The Conical Programming Problem. Let $K\subseteq \mathbb{R}^n$ be a nonempty convex cone, let $X:= b+L\subseteq \mathbb{R}^n$, where L is a linear subspace of $\mathbb{R}^n$, and let $F(x):=c^Tx,\, G(x):= x$. Then we obtain the so-called conical programming problem

$$\inf\{c^Tx| x\in b+L, x\in -K\}.$$

Denote by ${\cal F}$ the feasible set of problem (8), i.e., the set $\{x\in X|\, G(x)\in -K\}$. The problem

$$v(R):= \inf\{F_R(x)| x\in {\cal F}_R\}$$

is called a relaxation of the initial problem (8), if ${\cal F}\subseteq {\cal F}_R$ and $F_R(x)\le F(x)$ for each $x\in {\cal F}$. It is obvious that $v(R)\le v(P)$. Next we show a natural way to construct a relaxation of problem (8). Let $\lambda\in \mathbb{R}^m$ and consider the problem

$$\inf\{F(x)+\lambda^T G(x)| x\in X\}.$$

Clearly ${\cal F}\subseteq X$ and $F(x)+\lambda^T G(x)\le F(x)$ for each $x\in {\cal F}$ if and only if $\lambda^T G(x)\le 0$ for each $x\in {\cal F}$. Let $K^{\ast}:=\{y\in \mathbb{R}^m|\, y^Tx\ge 0\,\,\,\forall x\in K\}$ be the dual cone of K. Now it is clear that $\lambda\in K^{\ast}$ implies $\lambda^T G(x)\le 0$, for each $x\in{\cal F}$. Define the (Lagrangian) function $L: X\times K^{\ast}\to \mathbb{R}$ by $L(x,\lambda):= F(x)+\lambda^T G(x)$ and consider the problem

$$\theta (\lambda):=\inf\{L(x,\lambda)|\, x\in X\}.$$

((9))

Clearly $\theta(\lambda)\le v(P)$ for each $\lambda\in K^{\ast}$, and therefore we also have

$$\sup_{\lambda\in K^{*}}\theta (\lambda) \le v(P),$$

hence

$$\sup_{\lambda\in K^{\ast}}\inf_{x\in X}L(x,\lambda)\le \inf_{x\in {\cal F}}F(x).$$

((10))

By this relation it follows that the optimal objective value v(D) of the dual problem

$$v(D):=\sup{\theta (\lambda)| \lambda\in K^{*}}$$

approximates from below the optimal objective value v(P) of the primal problem (8). From both theoretical and practical points of view, an important issue is to establish sufficient conditions in order to have equality between the optimal objective values of the primal and dual problems. In this respect, observe that for each $x\in {\cal F}$ one has

$$\sup_{\lambda\in K^{*}}L(x,\lambda) = \sup_{\lambda\in K^{*}}(F(x)+\lambda^T G(x)) = F(x).$$

Therefore,

$$\inf_{x\in {\cal F}}F(x) = \inf_{x\in {\cal F}}\sup_{\lambda\in K^{*}} L(x,\lambda) = \inf_{x\in X}\sup_{\lambda\in K^{*}}L(x,\lambda).$$

Indeed, if $x\in X\setminus {\cal F}$, then $G(x)\notin -K$. By the bipolar theorem [29] we have $K = K^{\ast\ast}$, hence it follows that there exists $\lambda^{\ast}\in K^{\ast}$ such that $\lambda^{\ast T}G(x) > 0$. Since $t\lambda^{\ast}\in K$ for each $t > 0$, then

$$\sup_{\lambda\in K^{*}}L(x,\lambda) = \infty \quad \forall x \in X\setminus {\cal F}.$$

Combining the latter with relation (10) and taking into account that the “supinf” is always less or equal than the “infsup,” one obtains

$$v(D) = \sup_{\lambda\in K^{\ast}}\inf_{x\in X}L(x,\lambda)\le \inf_{x\in X} \sup_{\lambda\in K^{\ast}}L(x,\lambda) = v(P).$$

((11))

Hence we obtain that $v(D) = v(P)$, if a saddlepoint $({\bar x}, {\bar\lambda})$ of the Lagrangian L exists. This situation is called perfect duality. In this case ${\bar x}$ is the optimal solution of the primal, while ${\bar\lambda}$ is the optimal solution of the dual problem.

2.4 Variational Inequalities

Let E be a real topological vector space and $E^{\ast}$ be the dual space of E. Let $K\subseteq E$ be a nonempty convex set and $T:K\to E^{\ast}$ a given operator. For $x\in E$ and $x^{\ast}\in E^{\ast}$, the duality pairing between these two elements will be denoted by $\langle x,\, x^{\ast}\rangle$. If $A = B := K$ and $f(x,y):= \langle T(x),\, y-x\rangle$, for each $x,y\in K$, then each solution of the equilibrium problem (EP) is a solution of the variational inequality

$$\langle T(x),\, y-x\rangle \ge 0\quad\forall y\in K,$$

((12))

and vice versa.

Variational inequalities have shown to be important mathematical models in the study of many real problems, in particular in network equilibrium models ranging from spatial price equilibrium problems and imperfect competitive oligopolistic market equilibrium problems to general financial or traffic equilibrium problems.

An important particular case of the variational inequality (12) is the following. Let $E:= H$ be a real Hilbert space with inner product $\langle\,\,,\,\, \rangle$. It is well known that in this case the dual space $E^{\ast}$ can be identified with H. Consider the bilinear and continuous function $a: H\times H\to \mathbb{R}$, the linear and continuous function $L: H\to \mathbb{R}$, and formulate the problem: find an element $x\in K\subseteq H$ such that

$$a(x,\,y-x)\ge L(y-x)\quad\forall y\in K.$$

((13))

By the hypothesis, for each $x\in H$ the function $a(x,\cdot):H\to \mathbb{R}$ is linear and continuous. Therefore, by the Riesz representation theorem in Hilbert spaces (see, for instance, [30]) there exists a unique element $A(x)\in H$ such that $a(x,\,y) = \langle A(x),\, y\rangle$ for each $y\in H$. It is easy to see that $A: H\to H$ is a linear and continuous operator. Moreover, since L is also linear and continuous, again by the Riesz theorem, there exists a unique element $l\in H$ such that $L(x) = \langle l,\, x\rangle$ for each $x\in H$. Now for $T(x) := A(x) - l$, problem (13) reduces to (12).

In optimization theory, those variational inequalities in which the operator T is a gradient map (i.e., is the gradient of a certain differentiable function) are of special interest since their solutions are (in some cases) the minimum points of the function itself. Suppose that $X\subseteq \mathbb{R}^n$ is an open set, $K\subseteq X$ is a convex set, and the function $F:X\to \mathbb{R}$ is differentiable on X. Then each minimum point of F on the set K is a solution of the variational inequality (12), with $T:= \nabla F$. Indeed, let $x_0\in K$ be a minimum point of F on K and $y\in K$ be an arbitrary element. Then we have

$$F(x_0) \le F(\lambda y + (1-\lambda) x_0) \quad \forall \lambda\in [0,1].$$

Therefore,

$$\frac{1}{\lambda}(F(x_0 + \lambda (y-x_0))-F(x_0)) \ge 0 \quad \forall \lambda\in (0,1].$$

Now letting $\lambda\to 0$ we obtain $\langle \nabla F(x_0),\, y-x_0\rangle \ge 0$, as claimed.

If we suppose further that F is a convex function on the convex set X, then we obtain the reverse implication as well, i.e., each solution of the variational inequality (12), with $T:= \nabla F$, is a minimum point of F on the set K. Indeed, let $x_0\in K$ be a solution of (12) and $y\in K$ be an arbitrary element. Then by convexity

$$F(x_0+\lambda (y-x_0)) \le (1-\lambda)F(x_0)+\lambda F(y) \quad \forall \lambda\in [0,1],$$

which yields

$$\frac{1}{\lambda}(F(x_0+\lambda (y-x_0))-F(x_0)) \le F(y)-F(x_0) \quad \forall \lambda\in (0,1].$$

By letting $\lambda\to 0$ one obtains from the latter that

$$\langle \nabla F(x_0), y-x_0\rangle \le F(y)-F(x_0),$$

which yields the desired implication.

The particular cases presented above shows the importance of the equilibrium problem (EP). Therefore, one of the main issues is to know in advance whether (EP) admits a solution. In the next section we give sufficient conditions for the existence of a solution of this problem.

3 Some Existence Results on Equilibrium Problem

There are many results concerning the existence of solutions of (EP) known in the literature. Usually, regarding their proofs, they can be divided into two classes: results that uses fixed point tools and results using separation tools. There are, however, some results (usually consequences of more general statements) that belong to both classes. The aim of this section is to present two classical results from the first class due to Ky Fan [15] and Brézis, Nirenberg, Stampacchia [11], and a more recent result belonging to the second class due to Kassay and Kolumbán [23].

3.1 Results Based on Fixed Point Theorems

To start, let us first recall the celebrated Brouwer’s fixed point theorem.

Theorem 2.

Let $C\subseteq \mathbb{R}^n$ be a convex, compact set and $h:C\to C$ be a continuous function. Then h admits at least one fixed point.

Since the appearance of this theorem, many different proofs of it have been published. It is still an open question whether there exists an elementary proof of Brouwer’s fixed point theorem in case $n\ge 2$, using separation arguments only.

By Theorem 2 one can prove some of the so-called intersection theorems, which are useful tools regarding existence results for the equilibrium problem. The first important intersection theorem has been published in 1929: the celebrated Knaster–Kuratowski–Mazurkiewicz’s theorem [25] (called in the literature KKM lemma). This result has been extended by Ky Fan [14] in 1961 to infinite dimensional spaces. We will formulate these results later in this section as particular cases of a recent result obtained by Chang and Zhang [12]. In order to present the latter we first need the following definitions. Let E and $E^{\prime}$ be two topological vector spaces and let X be a nonempty subset of E.

Definition 1.

The set-valued mapping $F:X\to 2^E$ is called KKM mapping, if $co\{x_1,\ldots,x_n\}\subseteq \cup_{i=1}^nF(x_i)$ for each finite subset $\{x_1,\ldots,x_n\}$ of X.

A slightly more general concept was introduced by Chang and Zhang [12]:

Definition 2.

The mapping $F:X\to 2^{E^{\prime}}$ is called generalized KKM mapping, if for any finite set $\{x_1,\ldots,x_n\}\subseteq X$, there exists a finite set $\{y_1,\ldots,y_n\}\subseteq E^{\prime}$, such that for any subset $\{y_{i_1},\ldots,y_{i_k}\} \subseteq \{y_1,\ldots,y_n\}$, we have

$$\mathrm{co}\{y_{i_1},\ldots,y_{i_k}\}\subseteq \mathop{\cup}\limits_{j=1}^kF(x_{i_j}).$$

((14))

In case $E=E^{\prime}$ it is clear that every KKM mapping is a generalized KKM mapping too. The converse of this implication is not true, as the following example shows.

Example 1.

(Chang and Zhang [12]). Let $E:=\mathbb{R}, X:= [-2,2]$ and $F:X\to 2^E$ be defined by

$$F(x):= [-(1+x^2/5), 1+x^2/5].$$

Since $\cup_{x\in X}F(x)= [-9/5,9/5]$, we have

$$x \notin F(x) \quad \forall x\in [-2,-9/5)\cup (9/5, 1].$$

This shows that F is not a KKM mapping. On the other hand, for any finite subset $\{x_1,\ldots,x_n\}\subseteq X$, take $\{y_1,\ldots,y_n\}\subseteq [-1, 1]$. Then for any $\{y_{i_1},\ldots,y_{i_k}\} \subseteq \{y_1,\ldots,y_n\}$ we have

$$\mathrm{co}\{y_{i_1},\ldots,y_{i_k}\} \subseteq [-1, 1] = \mathop{\cap}\limits_{x\in X}F(x) \subseteq \mathop{\cup}\limits_{j=1}^kF(x_{i_j}),$$

i.e., F is a generalized KKM mapping.

Theorem 3.

(Chang and Zhang [12]). Suppose that E is a Hausdorff topological vector space, $X\subseteq E$ is nonempty, and $F:X\to 2^E$ is a mapping such that for each $x\in X$ the set F(x) is finitely closed (i.e., for every finite dimensional subspace L of E, $F(x)\cap L$ is closed in the Euclidean topology in L). Then F is a generalized KKM mapping if and only if for every finite subset $I\subseteq X$ the intersection of the subfamily $\{F(x)|\, x\in I\}$ is nonempty.

Proof.

Suppose first that for arbitrary finite set $I = \{x_1,\ldots,x_n\}\subseteq X$ one has

$$\mathop{\cap}\limits_{i=1}^nF(x_i) \ne \emptyset.$$

Take $x_{\ast}\in \cap_{i=1}^nF(x_i)$ and put $y_i:=x_{\ast}$, for each $i\in \{1,\ldots,n\}$. Then for every $\{y_{i_1},\ldots,y_{i_k}\}\subseteq \{y_1,\ldots,y_n\}$ we have

$$\mathrm{co}\{y_{i_1},\ldots,y_{i_k}\} = \{x_{*}\} \subseteq \mathop{\cap}\limits_{i=1}^nF(x_i) \subseteq \mathop{\cap}\limits_{j=1}^kF(x_{i_j}).$$

This implies that F is a generalized KKM mapping.

To show the reverse implication, let $F:X\to 2^E$ be a generalized KKM mapping. Supposing the contrary, there exists some finite set $\{x_1,\ldots,x_n\}\subseteq X$ such that $\cap_{i=1}^nF(x_i^{\prime})=\emptyset$. By the assumption, there exists a set $\{y_1,\ldots,y_n\}\subseteq E$ such that for any $\{y_{i_1},\ldots,y_{i_k}\} \subseteq \{y_1,\ldots,y_n\}$, relation (14) holds. In particular, we have

$$\mathrm{co}\{y_1,\ldots,y_n\} \subseteq \mathop{\cup}\limits_{i=1}^nF(x_i).$$

Let $S:={\rm co}\{y_1,\ldots,y_n\}$ and $L:={\rm span}\{y_1,\ldots,y_n\}$. Since for each $x\in X, F(x)$ is finitely closed, then the sets $F(x_i)\cap L$ are closed. Let d be the Euclidean metric on L. It is easy to verify that

$$d(x,\, F(x_i)\cap L) > 0 \quad {\rm if\,and\,only\,if} \quad x\notin F(x_i)\cap L.$$

((15))

Define now the function $g:S\to \mathbb{R}$ by

$$g(c):=\sum_{i=1}^nd(c, F(x_i)\cap L), \quad c\in S.$$

It follows by (15) and $\cap_{i=1}^nF(x_i)=\emptyset$ that for each $c\in S, g(c) > 0$. Let

$$h(c):=\sum_{i=1}^n\frac{1}{g(c)}d(c, F(x_i)\cap L)y_i.$$

Then h is a continuous function from S to S. By the Brouwer’s fixed point theorem (Theorem 2), there exists an element $c_{\ast}\in S$ such that

$$c_{\ast} = h(c_{\ast}) = \sum_{i=1}^n\frac{1}{g(c_{\ast})}d(c_{\ast},\, F(x_i)\cap L)y_i.$$

((16))

Denote

$$I:= \{i\in \{1,\ldots,n\}|\, d(c_{\ast},\, F(x_i)\cap L) > 0\}.$$

((17))

Then for each $i\in I, c_{\ast}\notin F(x_i)\cap L$. Since $c_{\ast}\in L$, then $c_{\ast}\notin F(x_i)$ for each $i\in I$, or, in other words,

$$c_{\ast}\notin\mathop{\cup}\limits_{i\in I}F(x_i).$$

((18))

By (16) and (17) we have

$$c_{*} = \sum_{i=1}^n\frac{1}{g(c_{*})}d(c_{*}, F(x_i)\cap L)y_i\in \mathrm{co}\{y_i| i\in I\}.$$

Since F is a generalized KKM mapping, this leads to

$$c_{*}\in \mathop{\cup}\limits_{i\in I}F(x_i),$$

which contradicts (18). This completes the proof.

By the above theorem one can easily deduce the following result.

Theorem 4.

(Chang and Zhang [12]) Suppose that $F:X\to 2^E$ is a set-valued mapping such that for each $x\in X$, the set $F(x)$ is closed. If there exists an element $x_0\in X$ such that $F(x_0)$ is compact, then $\cap_{x\in X}F(x)\neq \emptyset$ if and only if F is a generalized KKM mapping.

The proof of this theorem is an easy consequence of Theorem 3.

As we mentioned in the first part of this section, a particular case of Theorem 3 is the intersection theorem due to Ky Fan, known in the literature as Ky Fan’s lemma.

Theorem 5.

(Ky Fan [14]) Let E be a Hausdorff topological vector space, $X\subseteq E$ and for each $x\in X$, let F(x) be a closed subset of E, such that

• (a) there exists $x_0\in X$, such that the set $F(x_0)$ is compact;

• (b) for each $x_1,x_2,\ldots,x_n\in X, \quad {\rm co}\{x_1,x_2,\ldots,x_n\}\subseteq \cup_{i=1}^n F(x_i)$.

Then

$$\mathop{\cap}\limits_{x\in X} F(x) \ne \emptyset.$$

To conclude our presentation concerning intersection theorems, let us mention the famous result of Knaster, Kuratowski, and Mazurkiewitz (known as KKM lemma).

Theorem 6.

(KKM [25]) Let $E_i\subseteq\mathbb{R}^n$ be closed sets and $e_i\in E_i, i=1,\ldots,m$. Suppose that for each $J\subseteq \{1,\ldots,m\}$ we have ${\rm co}\{e_j|\,j\in J\}\subseteq \cup_{j\in J}E_j$. Then

$$\mathop{\cap}\limits_{i=1}^mE_i \ne \emptyset.$$

Now let us turn back to the equilibrium problem (EP). In what follows we need some further definitions.

Definition 3.

Let X be a convex subset of a certain vector space and let $h:X\to \mathbb{R}$ be some function. Then h is said to be quasiconvex if for every $x_1,x_2\in X$ and $0 < \lambda < 1$

$$h(\lambda x_1+(1-\lambda )x_2) \le \max\{h(x_1),h(x_2)\}.$$

We say that h is quasiconcave if $-h$ is quasiconvex.

It is easy to check that h is quasiconvex if and only if the lower level sets $\{x\in X|\, h(x)\le a\}$ are convex for each $a\in \mathbb{R}$. Similarly, h is quasiconcave if and only if the upper level sets $\{x\in X|\, h(x)\ge a\}$ are convex for each $a\in \mathbb{R}$. It is also easy to see that in the statements above, relations $\le (\ge)$ can be replaced with $< (>)$ and the assertions remain valid.

Definition 4.

Let X be a topological space and let $h:X\to \mathbb{R}$ be some function. Then h is said to be lower semicontinuous (lsc in short) on X if the lower level sets $\{x\in X|\, h(x)\le a\}$ are closed for each $a\in \mathbb{R}$. h is said to be upper semicontinuous (usc in short) on X if $-h$ is lsc on X, that is, its upper level sets are all closed.

By means of Ky Fan’s theorem (Theorem 5) one can prove the following existence result for (EP), due also to Ky Fan. This is known in the literature as Ky Fan’s minimax inequality theorem.

Theorem 7.

(Ky Fan [15]) Let A be a nonempty, convex, compact subset of a Hausdorff topological vector space and let $f:A\times A\to \mathbb{R}$, such that

$$\forall b\in A, \quad f(\cdot,b): A\to \mathbb{R}\, {\rm is\, usc},$$

((19))

$$\forall a\in A, \quad f(a,\cdot): A\to \mathbb{R}\, {\rm is\, quasiconvex}$$

((20))

and

$$\forall a\in A, \quad f(a,a)\ge 0.$$

((21))

Then (EP) admits a solution.

Proof.

For each $b\in A$, consider the set $F(b):=\{a\in A|\,f(a,b) \ge 0\}$. By (19), these sets are closed, and since A is compact, they are compact too. It is easy to see that the conclusion of the theorem is equivalent to

$$\mathop{\cap}\limits_{b\in A} F(b)\neq\emptyset.$$

((22))

In order to prove relation (22), let $b_1,b_2,\ldots,b_n\in A$. We shall show that

$$\mathrm{co}\{b_i\vert\, i\in \{1,2,\ldots,n\}\}\subseteq \mathop{\cup}\limits_{i=1}^nF(b_i).$$

((23))

Indeed, suppose by contradiction that there exist $\lambda_1,\lambda_2,\ldots,\lambda_n\ge 0, \sum\limits_{j=1}^n \lambda_j=1$, such that

$$\sum\limits_{j=1}^n\lambda_jb_j \notin\mathop{\cup}\limits_{j=1}^n F(b_j).$$

By definition, the latter means

$$f\left(\sum_{j=1}^n \lambda_jb_j, b_i\right) < 0 \quad \forall i\in \{1,2,\ldots,n\}.$$

By (20) (quasiconvexity), one obtains

$$f\left(\sum\limits_{j=1}^n \lambda_jb_j, \sum_{j=1}^n \lambda_jb_j\right) < 0,$$

which contradicts (21). This shows that (23) holds. Now applying Theorem 5, we obtain (22), which completes the proof.

As we have seen, the basic tool in the proof of Theorem 3 (and 4) of Chang and Zhang was the Brouwer’s fixed point theorem (Theorem 2). Moreover, Ky Fan’s intersection (and consequently his minimax inequality theorems (Theorems 5 and 7)), follow by Theorem 4. On the other hand, as we show next, by Theorem 7 one can easily reobtain the Brouwer’s fixed point theorem, which means that all these mentioned results are equivalent. To do this, we first state the following result.

Theorem 8.

Let E be a normed space, $X\subseteq E$ be a compact convex set, and $g,h:X\to E$ be continuous functions such that

$$\|x-g(x)\|\ge\|x-h(x)\| \quad\forall x\in X.$$

((24))

Then there exists an element $x_0\in X$, such that

$$\|y-g(x_0)|| \ge \|x_0-h(x_0)|| \quad \forall y\in X.$$

Proof.

Let $f :X\times X\to \mathbb{R}$ defined by $f(x,y):=\|y-g(x)\| - \|x-h(x)\|$. It is clear that this function satisfies the hypothesis of Theorem 7; thus there exists an element $x_0\in X$ such that

$$\|x_0-h(x_0)\|\le \|y-g(x_0)\|\quad\forall y\in X.$$

((25))

This completes the proof.

Observe, in case $g(X)\subseteq X$, we can put $y:=g(x_0)$ in (25); in this way we obtain that x ₀ is a fixed point of f. Now it is immediate the well-known Schauder’s fixed point theorem:

Theorem 9.

(Schauder [31]) Let X be a convex compact subset of a real normed space and $h:X\to X$ a continuous function. Then h has a fixed point.

Proof.

Taking $h=g$ in the previous theorem, we obtain this result by (25), with $y:=h(x_0)$.

Clearly, Brouwer’s fixed point theorem (Theorem 2) is a particular case of Theorem 9.

3.2 Results Based on Separation Theorems

As announced at the beginning of this section, we present now some existence results on (EP) which uses separation tools in their proofs.

The result below is a particular case of a theorem due to Kassay and Kolumbán [23].

Theorem 10.

Let A be a nonempty, compact, convex subset of a certain topological vector space, let B be a nonempty convex subset of a certain vector space, and let $f:A\times B\to \mathbb{R}$ be a given function.

Suppose that the following assertions are satisfied:

• (a) f is usc and concave in its first variable;

• (b) f is convex in its second variable;

• (c) $\sup_{a\in A}f(a,b)\ge 0$, for each $b\in B$.

Then the equilibrium problem (EP) has a solution.

Remark 2.

Condition (c) in the previous theorem is satisfied if, for instance, $B\subseteq A$ and $f(a,a)\ge 0$ for each $a\in B$. This condition arises naturally in most of the particular cases presented above.

A similar, but more general existence result for the problem (EP) has been established by Kassay and Kolumbán also in [23], where instead of the convexity (concavity) assumptions upon the function f, certain kind of generalized convexity (concavity) assumptions are supposed.

Theorem 11.

Let A be a compact topological space, let B be a nonempty set, and let $f:A\times B\to \mathbb{R}$ be a given function such that

• (a) for each $b\in B$, the function $f(\cdot, b):A\to\mathbb{R}$ is usc;

• (b) for each $a_1,\ldots,a_m\in A, b_1,\ldots,b_k\in B$, $\lambda _1,\ldots,\lambda _m\ge 0$ with $\sum_{i=1}^m\lambda _i=1$, the inequality

  $$\min_{1 \le j \le k}\sum_{i=1}^m\lambda _if(a_i,b_j) \le \sup_{a\in A} \min_{1 \le j \le k}f(a,b_j)$$

  holds;

• (c) For each $b_1,\ldots,b_k\in B, \mu_1,\ldots,\mu_k\ge 0$ with $\sum_{j=1}^k \mu_j=1$, one has

  $$\sup_{a\in A}\sum_{j=1}^k\mu_jf(a,b_j) \ge 0.$$

Then the equilibrium problem (EP) admits a solution.

Proof.

Suppose by contradiction that (EP) has no solution, i.e., for each $a\in A$ there exists $b\in B$ such that $f(a,b) < 0$ or, equivalently, for each $a\in A$ there exists $b\in B$ and $c > 0$ such that $f(a,b) + c < 0$. Denote by $U_{b,c}$ the set $\{a\in A | \, f (a,b) + c < 0\}$ where $b\in B$ and $c > 0$. By (a) and our assumption, the family of these sets is an open covering of the compact set A. Therefore, one can select a finite subfamily which covers the same set A, i.e., there exist $b_1,\ldots,b_k\in B$ and $c_1,\ldots,c_k > 0$ such that

$$A =\mathop{\cup}\limits_{j=1}^kU_{b_j,c_j}.$$

((26))

Let $c:=\min\{c_1,\ldots,c_k\} > 0$ and define the vector-valued function $H:A\to \mathbb{R}^k$ by

$$H(a):=(f (a,b_1) + c, \ldots,f (a,b_k) + c).$$

We show that

$$\mathrm{co} H(A)\mathop{\cap} \mathrm{int} \mathbb{R}_+^k = \emptyset,$$

((27))

where ${\rm co} H(A)$ denotes the convex hull of the set H(A) and ${\rm int} \mathbb{R}_+^k$ denotes the interior of the positive orthant $\mathbb{R}_+^k$. Indeed, supposing the contrary, there exist $a_1,\ldots,a_m\in A$ and $\lambda_1,\ldots,\lambda_m \ge 0$ with $\sum_{i=1}^m\lambda_i = 1$, such that

$$\sum\limits_{i=1}^m\lambda_iH(a_i)\in \mathrm{int} \mathbb{R}_+^k$$

or, equivalently,

$$\sum\limits_{i=1}^m\lambda_i(f (a_i,\, b_j) + c) > 0\quad\forall j\in\{1,\ldots,k\}.$$

((28))

By (b), (28) implies

$$\sup_{a\in A}\min_{1\le j \le k}f (a,\, b_j) > -c.$$

((29))

Now using (26), for each $a\in A$ there exists $j\in \{1,\ldots,k\}$ such that $f (a,b_j) + c_j < 0$. Thus, for each $a\in A$ we have

$$\min_{1 \le j \le k}f (a,b_j) < -c,$$

which contradicts (29). This shows that relation (27) is true. By the well-known separation theorem of two disjoint convex sets in finite dimensional spaces (see, for instance, [29]), the sets ${\rm co} H(A)$ and ${\rm int} \mathbb{R}_+^k$ can be separated by a hyperplane, i.e., there exist $\mu_1,\ldots,\mu_k \ge 0$ such that $\sum_{j=1}^k\mu_j = 1$ and

$$\sum\limits_{j=1}^k\mu_j(f (a,b_j) + c) \le 0 \quad \forall a\in A,$$

or, equivalently

$$\sum\limits_{j=1}^k\mu_jf(a,b_j) \le -c\quad\forall a\in A.$$

((30))

Observe, the latter relation contradicts assumption (c) of the theorem. Thus the proof is complete.

4 The Equilibrium Problem and the Ekeland’s Principle

Due to its important applications, the problem of solving an equilibrium problem is an important task. However, it often happens, an equilibrium problem may not have solution even in case when the problem arises from practice. Therefore, it is important to find approximate solutions in some sense or to show their existence in case of an equilibrium problem.

The Ekeland’s variational principle (see, for instance, [13]) has been widely used in nonlinear analysis since it entails the existence of approximate solutions of a minimization problem for lower semicontinuous functions on a complete metric space. Since, as we have seen in Section 2, minimization problems are particular cases of equilibrium problems, one is interested in extending Ekeland’s theorem to the setting of an equilibrium problem.

Recently, inspired by the study of systems of vector variational inequalities, Ansari, Schaible, and Yao [1] introduced and investigated systems of equilibrium problems, which are defined as follows. Let m be a positive integer. By a system of equilibrium problems we understand the problem of finding $\bar x = (\bar x_1,\ldots,\bar x_m)\in A$ such that

$$f_i(\bar x,y_i) \ge 0\qquad \forall i\in I, \forall y_i\in A_i,$$

((SEP))

where $f_i:A\times A_i\to\mathbb{R}, A=\prod_1^m A_i,$ with A _i some given sets.

The aim of this section is to present some recent results concerning existence of approximate equilibria for (EP) and (SEP). We find a suitable set of conditions on the functions that do not involve convexity and lead to an Ekeland’s variational principle for equilibrium and system of equilibrium problems. Via the existence of approximate solutions, we are able to show the existence of equilibria on general closed sets. Our setting is an Euclidean space, even if the results could be extended to reflexive Banach spaces, by adapting the assumptions in a standard way.

4.1 The Ekeland’s Principle for (EP) and (SEP)

To start, let us recall the celebrated Ekeland’s variational principle established within the framework of minimization problems for lower semicontinuous functions on complete metric spaces.

Theorem 12.

(Ekeland [13]) Let (X, d) be a complete metric space and $F: X\to \mathbb{R}$ a lower bounded, lower semicontinuous function. Then for every $\varepsilon > 0$ and $x_0\in X$ there exists $\bar x\in X$ such that

$$\begin{cases}\varepsilon d(x_0,\bar x)\le F(x_0)-F(\bar x) \\ F(\bar x) < F(x) + \varepsilon d(\bar x,x)\quad\forall x\in X, \quad x\neq x_0. \end{cases}$$

((31))

Remark 3.

If $X = \mathbb{R}$ with the Euclidean norm, then (31) can be written as

$$\begin{cases} \varepsilon |x_0-\bar x| \le F(x_0)-F(\bar x)\\ F(\bar x) < F(x) + \varepsilon |\bar x-x| \quad \forall x\in X, \quad x \ne x_0, \end{cases}$$

and this relation has a clear geometric interpretation.

Starting from Theorem 12, in a most recent paper [5] the authors established the following general result which we present here in detail.

Theorem 13.

Let A be a closed set of $\mathbb{R}^n$ and $f: A\times A\to\mathbb{R}$. Assume that the following conditions are satisfied:

• (a) $f(x,\cdot)$ is lower bounded and lower semicontinuous, for every $x\in A;$

• (b) $f(t,t)=0$, for every $t\in A;$

• (c) $f(z,x)\le f(z,y)+f(y,x)$, for every $x,y,z\in A.$

Then, for every $\varepsilon >0$ and for every $x_0\in A,$ there exists $\bar x\in A$ such that

$$\begin{cases} f(x_0,\bar x)+\varepsilon \|x_0-\bar x\|\le 0\\ f(\bar x,x)+\varepsilon \|\bar x-x\|>0\quad\forall x\in A, \quad x\neq \bar x. \end{cases}$$

((32))

Proof.

Without loss of generality, we can restrict the proof to the case $\varepsilon =1.$ Denote by ${\cal F}(x)$ the set

$${\cal F}(x):=\{y\in A:f(x,y)+\|y-x|| \le 0\}.$$

By (a), ${\cal F}(x)$ is closed, for every $x\in A;$ by (b), $x\in {\cal F}(x)$, hence ${\cal F}(x)$ is nonempty for every $x\in A$. Assume $y\in {\cal F}(x),$ i.e., $f(x,y)+\|y-x\|\le 0,$ and let $z\in {\cal F}(y)$ (i.e., $f(y,z)+\|y-z\|\le 0$). Adding both sides of the inequalities, we get, by (c),

$$0 \ge f(x,y)+\|y-x||+f(y,z)+\|y-z|| \ge f(x,z)+\|z-x||,$$

that is, $z\in {\cal F}(x).$ Therefore $y\in {\cal F}(x)$ implies ${\cal F}(y)\subseteq {\cal F}(x)$.

Define

$$v(x):=\inf_{z\in {\cal F}(x)}f(x,z).$$

For every $z\in {\cal F}(x),$

$$\|x-z|| \le -f(x,z) \le \sup_{z\in {\cal F}(x)}(-f(x,z))=-\inf_{z\in {\cal F}(x)}f(x,z)=-v(x)$$

that is,

$$\|x-z|| \le -v(x)\qquad \forall z\in {\cal F}(x).$$

In particular, if $x_1,x_2\in {\cal F}(x),$

$$\|x_1-x_2|| \le \|x-x_1||+\|x-x_2|| \le -v(x)-v(x)=-2v(x),$$

implying that

$$\textrm{diam}({\cal F}(x)) \le -2v(x)\qquad \forall x\in A.$$

Fix $x_0\in A; x_1\in {\cal F}(x_0)$ exists such that

$$f(x_0,x_1) \le v(x_0)+2^{-1}.$$

Denote by x ₂ any point in ${\cal F}(x_1)$ such that

$$f(x_1,x_2) \le v(x_1)+2^{-2}.$$

Proceeding in this way, we define a sequence $\{x_n\}$ of points of A such that $x_{n+1}\in {\cal F}(x_n)$ and

$$f(x_{n},x_{n+1}) \le v(x_n)+2^{-(n+1)}.$$

Notice that

$$\begin{gathered} v(x_{n+1})=\inf_{y\in {\cal F}(x_{n+1})}f(x_{n+1},y) \ge \inf_{y\in {\cal F}(x_n)}f(x_{n+1},y)\\ \ge \inf_{y\in {\cal F}(x_n)}(f(x_n,y)-f(x_n,x_{n+1}))\left(\inf_{y\in {\cal F}(x_n)}f(x_n,y)\right)-f(x_n,x_{n+1})\\ =v(x_n)-f(x_n,x_{n+1}). \end{gathered}$$

Therefore,

$$v(x_{n+1}) \ge v(x_n)-f(x_n,x_{n+1})$$

and

$$-v(x_n) \le -f(x_n,x_{n+1})+2^{-(n+1)} \le (v(x_{n+1})-v(x_n))+2^{-(n+1)},$$

that entails

$$0 \le v(x_{n+1})+2^{-(n+1)}.$$

It follows that

$$\textrm{diam}({\cal F}(x_n)) \le -2v(x_n) \le 2\cdot 2^{-n}\to 0, \quad n\to\infty.$$

The sets $\{{\cal F}(x_n)\}$ being closed and ${\cal F}(x_{n+1})\subseteq {\cal F}(x_n),$ we have that

$$\bigcap_n{\cal F}(x_n)={\bar x}.$$

Since $\bar x\in {\cal F}(x_0),$ then

$$f(x_0,\bar x)+||\bar x-x_0|| \le 0.$$

Moreover, $\bar x$ belongs to all ${\cal F}(x_n),$ and, since ${\cal F}(\bar x)\subseteq {\cal F}(x_n),$ for every n, we get that

$${\cal F}(\bar x)={\bar x}.$$

It follows that $x\notin {\cal F}(\bar x)$ whenever $x\neq \bar x,$ implying that

$$f(\bar x,x)+\|x-\bar x||>0.$$

This completes the proof.

Remark 4.

It is easy to see that any function $f(x,y)=g(y)-g(x)$ trivially satisfies (c) (actually with equality). One might wonder whether a bifunction f satisfying all the assumptions of Theorem 13 should be of the form $g(y)-g(x)$, and as such reducing the result above to the classical Ekeland’s principle. It is not the case, as the example below shows: let the function $f:\mathbb{R}^2\to\mathbb{R}$ be defined by

$$f(x,y)=\begin{cases} e^{-\|x-y||}+1+g(y)-g(x)&x \ne y\\ 0&x=y \end{cases},$$

where g is a lower bounded and lower semicontinuous function. Then all the assumptions of Theorem 13 are satisfied, but clearly f cannot be represented in the above-mentioned form.

Next we shall extend the result above for a system of equilibrium problems. Let m be a positive integer and $I = \{1,2,\ldots,m\}$. Consider the functions $f_i:A\times A_i\to \mathbb{R},\, i\in I$, where $A=\prod_{i\in I} A_i,$ and $A_i\subseteq X_i$ is a closed subset of the Euclidean space X _i . An element of the set $A^i=\prod_{j\neq i}A_j$ will be represented by x ⁱ; therefore, $x\in A$ can be written as $x=(x^i,x_i)\in A^i\times A_i.$ If $x\in \prod X_i,$ the symbol $|||x|||$ will denote the Tchebiseff norm of x, i.e., $|||x|||=\max_i ||x_i||_i$ and we shall consider the Euclidean space $\prod X_i$ endowed with this norm.

Theorem 14.

(Bianchi et al. [5]) Assume that

• (a) $f_i(x,\cdot):A_i\to \mathbb{R}$ is lower bounded and lower semicontinuous for every $i\in I$;

• (b) $f_i(x,x_i) =0$ for every $i\in I$ and every $x=(x_1,\ldots,x_m)\in A$;

• (c) $f_i(z,x_i)\le f_i(z,y_i)+f_i(y,x_i)$, for every $x,y,z\in A,$ where $y=(y^i,y_i),$ and for every $i\in I.$

Then for every $\varepsilon > 0$ and for every $x^0 = (x^0_1,\ldots,x^0_m)\in A$ there exists $\bar x =(\bar x_1,\ldots,\bar x_m)\in A$ such that for each $i\in I$ one has

$$f_i(x^0,\bar x_i) + \varepsilon\|x^0_i - \bar x_i\|_i\le 0$$

((33))

and

$$f_i(\bar x, x_i) + \varepsilon \|\bar x_i - x_i\|_i > 0\quad\forall x_i\in D_i, \quad x_i\neq \bar x_i.$$

((34))

Proof.

As before, we restrict the proof to the case $\varepsilon =1$. Let $i\in I$ be arbitrarily fixed. Denote for every $x\in A$

$${\cal F}_i(x):=\{y_i\in A_i: f_i(x,y_i) + \|x_i-y_i\|_i \le 0\}.$$

These sets are closed and nonempty (for every $x=(x_1,\ldots,x_m)\in A$ we have $x_i\in {\cal F}_i(x)$). Define for each $x\in A$

$$v_i(x):= \inf_{z_i\in {\cal F}_i(x)}f_i(x,z_i).$$

In a similar way as in the proof of Theorem 13 one can show that $\textrm{diam}({\cal F}_i(x))\le -2v_i(x)$ for every $x\in A$ and $i\in I$.

Fix now $x^0\in A$ and select for each $i\in I$ an element $x^1_i\in {\cal F}_i(x^0)$ such that

$$f_i(x^0,x^1_i) \le v_i(x^0) + 2^{-1}.$$

Put $x^1:= (x^1_1,\ldots,x^1_m)\in A$ and select for each $i\in I$ an element $x^2_i\in {\cal F}_i(x^1)$ such that

$$f_i(x^1,x^2_i) \le v_i(x^1) + 2^{-2}.$$

Put $x^2:= (x^2_1,\ldots,x^2_m)\in A$. Continuing this process we define a sequence $\{x^n\}$ in A such that $x^{n+1}_i\in {\cal F}_i(x^n)$ for each $i\in I$ and $n\in N$ and

$$f_i(x^n,x^{n+1}_i) \le v_i(x^n) + 2^{-(n+1)}.$$

Using a same argument as in the proof of Theorem 13 one can show that

$${\rm diam}({\cal F}_i(x^n)) \le -2v_i(x^n) \le 2\cdot 2^{-n}\to 0, \quad n\to\infty,$$

for each $i\in I$.

Now define for each $x\in A$ the sets

$${\cal F}(x):= {\cal F}_1(x)\times \cdots\times {\cal F}_m(x) \subseteq A.$$

The sets ${\cal F}(x)$ are closed and using (c) it is immediate to check that for each $y\in {\cal F}(x)$ it follows that ${\cal F}(y)\subseteq {\cal F}(x)$. Therefore, we also have ${\cal F}(x^{n+1})\subseteq {\cal F}(x^n)$ for each $n\in \{0,1,\ldots\}$. On the other hand, for each $y,z\in {\cal F}(x^n)$ we have

$$|||y-z|||=\max_{i\in I}\|y_i-z_i\|_i \le \max_{i\in I}{\rm diam}{\cal F}_i(x^n))\to 0,$$

thus, $\textrm{diam}({\cal F}(x^n))\to 0$ as $n\to\infty$. In conclusion we have

$$\mathop{\cap}\limits_{n=0}^{\infty}{\cal F}(x^n) = {\bar x}, \bar x\in A.$$

Since $\bar x\in {\cal F}(x^0)$, i.e., $\bar x_i\in {\cal F}_i(x^0)$ ($i\in I$) we obtain

$$f_i(x^0,\bar x_i) + \|x^0_i-\bar x_i\|_i \le 0 \quad \forall i\in I,$$

and so, (33) holds. Moreover, $\bar x\in {\cal F}(x^n)$ implies ${\cal F}(\bar x)\subseteq {\cal F}(x^n)$ for all $n=0,1,\ldots$, therefore,

$${\cal F}(\bar x)= {\bar x}$$

implying

$${\cal F}_i(\bar x)= {\bar x_i} \quad \forall i\in I.$$

Now for every $x_i\in A_i$ with $x_i\neq \bar x_i$ we have by the previous relation that $x_i\notin {\cal F}_i(\bar x)$ and so

$$f_i(\bar x, x_i) + ||\bar x_i - x_i\|_i > 0.$$

Thus (34) holds too, and this completes the proof.

4.2 New Existence Results for Equilibria on Compact Sets

As shown by the literature, the existence results of equilibrium problems usually require some convexity (or generalized convexity) assumptions on at least one of the variables of the function involved. In this section, using Theorems 13 and 14, we show the nonemptiness of the solution set of (EP) and (SEP), without any convexity requirement. To this purpose, we recall the definition of approximate equilibrium point, for both cases (see [5, 21]). We start our analysis with (EP).

Definition 5.

Given $f:A\times A\to\mathbb{R}$ and $\varepsilon >0, \bar x\in A$ is said to be an $\varepsilon$-equilibrium point of f if

$$f(\bar x,y)\ge -\varepsilon \|\bar x-y\|\qquad \forall y\in A$$

((35))

The $\varepsilon$-equilibrium point is strict, if in (35) the inequality is strict for all $y\neq \bar x$.

Notice that the second relation of (31) gives the existence of a strict $\varepsilon$-equilibrium point, for every $\varepsilon >0$. Moreover, by (b) and (c) of Theorem 12 it follows by the first relation of (31) that

$$f(\bar x,x_0) \ge \varepsilon ||\bar x-x_0||,$$

“localizing,” in a certain sense, the position of $\bar x.$

Theorem 12 leads to a set of conditions that are sufficient for the nonemptiness of the solution set of (EP).

Proposition 2.

(Bianchi et al. [5]) Let A be a compact (not necessarily convex) subset of an Euclidean space and $f:A\times A\to\mathbb{R}$ be a function satisfying the assumptions:

• (a) $f(x,\cdot)$ is lower bounded and lower semicontinuous, for every $x\in A;$

• (b) $f(t,t)=0$, for every $t\in A;$

• (c) $f(z,x)\le f(z,y)+f(y,x)$, for every $x,y,z\in A;$

• (d) $f(\cdot, y)$ is upper semicontinuous, for every $y\in A.$

Then, the set of solutions of EP is nonempty.

Proof.

For each $n\in \mathbb{N},$ let $x_n\in A$ a 1/n-equilibrium point (such point exists by Theorem 12), i.e.,

$$f(x_n,y) \ge -\frac{1}{n}\|x_n-y||\qquad \forall y\in A.$$

Since A is compact, we can choose a subsequence $\{x_{n_k}\}$ of $\{x_n\}$ such that $x_{n_k}\to \bar x$ as $n\to\infty$. Then, by (d),

$$f(\bar x,y) \ge \limsup_{k\to \infty} \left(f(x_{n_k},y)+\frac{1}{n_k}\|x_{n_k}-y||\right) \qquad \forall y\in A,$$

thereby proving that $\bar x$ is a solution of EP.

Let us now consider the following definition of $\varepsilon$-equilibrium point for systems of equilibrium problems. As before, the index set I consists of the finite set $\{1,2,\ldots,m\}$.

Definition 6.

Let $A_i,\, i\in I$ be subsets of certain Euclidean spaces and put $A=\prod_{i\in I}A_i$. Given $f_i:A\times A_i\to\mathbb{R}, i\in I$, and $\varepsilon >0,$ the point $\bar x\in A$ is said to be an $\varepsilon$-equilibrium point of $\{f_1,f_2,\ldots,f_m\}$ if

$$f_i(\bar x,y_i) \ge -\varepsilon ||\bar x_i-y_i\|_i\qquad \forall y_i\in A_i, \forall i\in I.$$

The following result is an extension of Proposition 2, and it can be proved in a similar way.

Proposition 3.

(Bianchi et al. [5]) Assume that, for every $i\in I, A_i$ is compact and $f_i:A\times A_i\to\mathbb{R}$ is a function satisfying the assumptions:

• (a) $f_i(x,\cdot)$ is lower bounded and lower semicontinuous, for every $x\in A;$

• (b) $f_i(x,x_i)=0$, for every $x=(x^i,x_i)\in A;$

• (c) $f_i(z,x_i)\le f_i(z,y_i)+f_i(y,x_i)$, for every $x,y,z\in A,$ where $y=(y^i,y_i);$

• (d) $f_i(\cdot, y_i)$ is upper semicontinuous, for every $y_i\in A_i.$

Then, the set of solutions of (SEP) is nonempty.

4.3 Equilibria on Noncompact Sets

The study of the existence of solutions of the equilibrium problems on unbounded domains usually involves the same sufficient assumptions as for bounded domains together with a coercivity condition. Bianchi and Pini [7] found coercivity conditions as weak as possible, exploiting the generalized monotonicity properties of the function f defining the equilibrium problem.

Let A be a closed subset of X, not necessarily convex, not necessarily compact, and $f:A\times A\to \mathbb{R}$ be a given function.

Consider the following coercivity condition (see [7]):

$$\exists r > 0: \quad \forall x\in A\setminus K_r, \quad \exists y\in A, \quad \|y\| < \|x\|: \; f(x,y) \le 0,$$

((36))

where $K_r:=\{x\in A:\,\|x\| \le r\}$.

We now show that within the framework of Proposition 2 condition (36) guarantees the existence of solutions of (EP) without supposing compactness of A.

Theorem 15.

(Bianchi et al. [5]) Suppose that

• (a) $f(x,\cdot)$ is lower bounded and lower semicontinuous, for every $x\in A;$

• (b) $f(t,t)=0$, for every $t\in A;$

• (c) $f(z,x)\le f(z,y)+f(y,x)$, for every $x,y,z\in A;$

• (d) $f(\cdot, y)$ is upper semicontinuous, for every $y\in A.$

If (36) holds, then (EP) admits a solution.

Proof.

We may suppose without loss of generality that K _r is nonempty. For each $x\in A$ consider the nonempty set

$$S(x):=\{y\in A: \|y|| \le \|x||: f(x,y) \le 0\}.$$

Observe that for every $x,y\in A, y\in S(x)$ implies $S(y)\subseteq S(x)$. Indeed, for $z\in S(y)$ we have $\|z\|\le \|y\|\le\|x\|$ and by (c) $f(x,z)\le f(x,y)+ f(y,z)\le 0$. On the other hand, since $K_{\|x\|}$ is compact, by (a) we obtain that $S(x)\subseteq K_{\|x\|}$ is a compact set for every $x\in A$. Furthermore, by Proposition 2, there exists an element $x_r\in K_r$ such that

$$f(x_r,y)\ge 0\quad\forall y\in K_r.$$

((37))

Suppose that there exists $x\in A$ with $f(x_r,x) < 0$ and put

$$a:=\min_{y\in S(x)}\|y||$$

(the minimum is taken since S(x) is nonempty, compact and the norm is continuous). We distinguish two cases.

Case 1: $a\le r$. Let $y_0\in S(x)$ such that $\|y_0\|=a\le r$. Then we have $f(x,y_0)\le 0$. Since $f(x_r,x) < 0$, it follows by (c) that

$$f(x_r,y_0) \le f(x_r,x) + f(x,y_0)< 0,$$

contradicting (37).

Case 2: $a > r$. Let again $y_0\in S(x)$ such that $\|y_0\|=a > r$. Then, by (36) we can choose an element $y_1\in A$ with $\|y_1\| < \|y_0\| = a$ such that $f(y_0,y_1)\le 0$. Thus, $y_1\in S(y_0)\subseteq S(x)$ contradicting

$$\|y_1||< a = \min_{y\in S(x)}\|y||.$$

Therefore, there is no $x\in A$ such that $f(x_r,x) < 0$, i.e., x _r is a solution of (EP) (on A). This completes the proof.

Next we consider (SEP) for noncompact setting. Let us consider the following coercivity condition:

$$\exists r > 0: \quad \forall x\in A \;{\rm such\;that}\; \|x_i\|_i>r\;{\rm for\;some}\; i\in I,\nonumber\\ \exists y_i\in A_i,\, \quad \|y_i\|_i < \|x_i\|_i\quad{\rm and} \quad f_i(x,y_i) \le 0.$$

((38))

We conclude this section with the following result which guarantees the existence of solutions for (SEP).

Theorem 16.

(Bianchi et al. [5]) Suppose that, for every $i\in I$,

• (a) $f_i(x,\cdot)$ is lower bounded and lower semicontinuous, for every $x\in A;$

• (b) $f_i(x,x_i)=0$, for every $x=(x^i,x_i)\in A;$

• (c) $f_i(z,x_i)\le f_i(z,y_i)+f_i(y,x_i)$, for every $x,y,z\in A,$ where $y=(y^i,y_i);$

• (d) $f_i(\cdot, y_i)$ is upper semicontinuous, for every $y_i\in A_i.$

If (38) holds, then (SEP) admits a solution.

Proof.

For each $x\in A$ and every $i\in I$ consider the set

$$S_i(x):=\{y_i\in A_i, \|y_i\|_i \le \|x_i\|_i, f_i(x,y_i) \le 0\}.$$

Observe that, by (c), for every x and $y=(y^i,y_i)\in A$, $y_i\in S_i(x)$ implies $S_i(y)\subseteq S_i(x)$. On the other hand, since the set $\{y_i\in A_i:\|y_i\|_i\le r\}=K_i(r)$ is a compact subset of A _i , by (a) we obtain that S _i (x) is a nonempty compact set for every $x\in A$. Furthermore, by Proposition 3, there exists an element $x_r\in \prod_i K_i(r)$ (observe, we may suppose that $K_i(r)\neq\emptyset$ for all $i\in I$) such that

$$f_i(x_r,y_i)\ge 0\quad\forall y_i\in K_i(r),\qquad\forall i\in I.$$

((39))

Suppose that x _r is not a solution of (SEP). In this case, there exists $j\in I$ and $z_j\in A_j$ with $f_j(x_r,z_j) < 0.$ Let $z^j\in A^j$ be arbitrary and put $z=(z^j,z_j)\in A$. Define

$$a_j:=\min_{y_j\in S_j(z)}\|y_j\|_j.$$

We distinguish two cases.

Case 1: $a_j\le r$. Let $\bar y_j(z)\in S_j(z)$ such that $\|\bar y_j(z)\|_j=a_j\le r$. Then we have $f_j(z,\bar y_j(z))\le 0$. Since $f_j(x_r,z_j) < 0$, it follows by (c) that

$$f_j(x_r,\bar y_j(z)) \le f(x_r,z_j) + f(z,\bar y_j(z))< 0,$$

contradicting (39).

Case 1: $a_j > r$. Let again $\bar y_j(z)\in S_j(z)$ such that $\|\bar y_j(z)\|_j=a_j > r$. Let $\bar y^j\in A^j$ be arbitrary and put $\bar y(z) = (\bar y^j, \bar y_j(z))\in A$. Then, by (38) we can choose an element $y_j\in A_j$ with $\|y_j\|_j < \|\bar y_j(z)\|_j = a_j$ such that $f_j(\bar y(z),y_j)\le 0$. Clearly, $y_j\in S_j(\bar y(z))\subseteq S_j(z)$, a contradiction since $\bar y_j(z)$ has minimal norm in $S_j(z).$ This completes the proof.

5 Conclusions

Finally, let us recall the most important issues discussed in this chapter. As emphasized in Introduction, our purpose was to give an overlook on equilibrium problem (abbreviated (EP)) underlining its importance and usefulness from both theoretical and practical points of view.

In the second section we have presented the most important particular cases of (EP). One of them is the optimization problem (minimization/maximization of a real-valued function over a so-called feasible set). As well known, optimization problems appear as mathematical models of many problems of practical interest. Another particular case of (EP) presented here is the so-called Kirszbraun’s problem, which can be successfully applied in extending nonexpansive functions (these functions are important among others, in fixed point theory). The saddlepoint (or minimax) problems have shown to be also particular instances of (EP). We have pointed out the applicability of these problems in game theory on one hand and in duality theory in optimization, on the other hand. We have concluded the presentation of the particular cases of (EP) with variational inequalities, which constitute models of various problems arising from mechanics and economy.

Section 3 has been devoted to the exposition of some classical and recent results concerning existence of solutions of (EP). We have underlined that in general these results can be deduced in two ways: either using fixed point tools or separation (Hahn–Banach) tools. For the reader’s convenience, the most important results of this section have been presented together with their proofs. Moreover, we have tried to keep these proofs as simple as possible.

When dealing with (EP), one frequently encounters the situation when the set of solutions is empty. In these situations it is important to study the existence of approximate solutions in some sense. Since (EP) contains, in particular, optimization problems, and the celebrated Ekeland’s variational principle provides the existence of approximate optimal solutions, it comes natural to investigate whether this principle can be extended to (EP). Based on recent results of the author, we have presented in the last section some of these possible extensions both for (EP) and a more general situation: system of equilibrium problems (SEP).

Throughout this chapter we have limited ourselves to the scalar case, i.e., when the functions involved in (EP) or (SEP) are real-valued. In the last decade the vector-valued case has also been studied (see, for instance, [1, 4, 16]). We think that a possible research for the future could be to investigate whether the results presented here for the scalar case can be extended also for the vector case.