About the Links Between Equilibrium Problems and Variational Inequalities

Abstract

In this chapter, we seek to study the interrelation between an equilibrium problem and the variational inequality problem. Under most natural assumption, the equilibrium problem is equivalent to an associated variational inequality. Hence, the existence results for equilibrium problems can be obtained from the existence results for variational inequality problems and vice versa. We study a problem of existence of Nash equilibrium in an oligopolistic market and show that it is equivalent to a variational inequality under the most natural economic assumption. We also study the relation between quasi-equilibrium problem and quasi-variational inequality.

6.1 Introduction and Motivation

In the recent decades, a huge number of papers of the literature of optimization have been dedicated to equilibrium problem. In the community of optimizers, this terminology is used to describe the following problem: given a subset $C \subset \mathbb {R}^n$ and a (bi)function $f : \mathbb {R}^n \times \mathbb {R}^n \rightarrow \mathbb {R}$, the equilibrium problem consists in

$$ EP ( f, C)\qquad \text{ find } x \in C \text{ such } \text{ that } f(x, y ) \ge 0,~~ \text{ for } \text{ all } y \in C. $$

This understanding of the term ‘equilibrium’ seems to be quite far to its usual sense in game theory. It is actually not really the case as we will see in the example described in the forthcoming Sect. 6.4.

It was Oettli who in 1994 [4] first coined the term equilibrium problem during the annual conference of the Indian Mathematical Society and his paper was published in the journal Mathematics Student of the Indian Mathematical Society. It is one of the most cited papers in optimization theory.

The power of this formulation is that it allows to include, in a common framework, a large set of problems. For example, consider $f(x, y) = \varphi (y) - \varphi (x)$ and a subset C of $\mathbb {R}^n$. Then the solution set of the problem EP(f, C) coincides with the set of global minimizers of the function $\varphi$ over C. Now if one consider $f(x, y) = \varphi ( x) - \varphi ( y)$, then, symmetrically, the solutions of the equilibrium problem EP(f, C) are the global maximizers of the function $\varphi$ over C. Thus, the concept of an equilibrium problem seems to unify both minimization and maximization problems.

On the other hand if the objective function $\varphi$ is assumed to be differentiable over a closed convex set C, then it is a well-known fact (and simple to prove) that if $\bar{x}$ is a local minimizer of $\varphi$ over C, then

$$\begin{aligned} \langle \nabla \varphi (\bar{x}), y - \bar{x} \rangle \ge 0, \qquad \forall y \in C. \end{aligned}$$

(6.1)

The above inequality expresses the necessary optimality condition in the so-called variational inequality form $VI(\nabla \varphi , C)$. Of course, if additionally f is convex, then the above expression is both necessary and sufficient for global optimality and thus, in context of convex optimization, a first relationship between equilibrium problem and variational inequality occurs since

$$\begin{aligned} EP(f_\varphi ,C)=\arg \min _C \varphi =VI(\nabla \varphi ,C)\qquad \text{ where } f_\varphi (x,y)= \varphi (y) - \varphi (x), \end{aligned}$$

(6.2)

where the notations EP and VI are both used for the problem itself and its solution set.

Our aim in this short note is to make a synthesis/state of art of the relationships (inclusions, equality) of equilibrium problems and variational inequalities, that is, to give sufficient conditions ensuring that one is included in the other one or that they coincide. Then in Sect. 6.4, we also emphasize through an example that the variational inequality is possibly the most general form of an equilibrium problem arising in applications.

6.2 State of the Art of Relationships

6.2.1 A First Step: VI and EP Generated by an Optimization Problem

Before going further into the relationship between equilibrium problems and variational inequalities, let us continue the reformulation process started above with the reformulation of optimization problems in terms of variational inequalities. Indeed, the link stated in (6.2) still holds true, under slight modifications, even if the objective function $\varphi$ is not differentiable and/or not convex.

If $\varphi$ is a lower semi-continuous proper convex function which is not assume to be differentiable, then one can use both the concepts of (convex) subdifferential and set-valued variational inequality in order to obtain a relation similar to (6.2). Let us recall that the subdifferential of the convex function $\varphi$ at a point is given by $\partial \varphi (x)=\{v\in \mathbb {R}^n~:~\langle v,y-x\rangle \le \varphi (y)- \varphi (x),~\forall \,y\in \mathbb {R}^n\}$ and that the general framework of variational inequalities is the following: given a set-valued map $F:\mathbb {R}^n\rightrightarrows \mathbb {R}^n$ and a subset C of $\mathbb {R}^n$, the (somehow called generalized) variational inequality VI(F, C) consists in:

$$ \text{ find } \bar{x}\in C \text{ such } \text{ that } \text{ there } \text{ exists } \bar{x}^*\in F(\bar{x}) \text{ with } \langle \bar{x}^*, y - \bar{x} \rangle \ge 0, \quad \forall x \in C. $$

Thus taking these notations into account, it is well known that Eq. (6.2) extends in

$$\begin{aligned} EP(f_\varphi ,C)=VI(\partial \varphi ,C)\qquad \text{ where } f_\varphi (x,y)= \varphi (y) - \varphi (x). \end{aligned}$$

(6.3)

Now if $\varphi$ is not assumed to be convex but only quasi-convex, then thanks to some recent developments (see, e.g. [1]), it is nevertheless possible to achieve the perfect reformulation of the minimization of $\varphi$ over a convex set C in terms of a related variational inequality. To be more precise, let us first recall some definitions:

A function $\varphi :X\rightarrow \mathrm {I\!R \cup \{+\infty \}}$ is said to be

• quasi-convex on K if,

  $$ \text{ for } \text{ all } x,~y\in K \text{ and } \text{ all } t\in [0,1], \qquad \varphi (tx+(1-t)y)\le \max \{\varphi (x),\varphi (y)\}, $$

  or equivalently

  $$ \text{ for } \text{ all } \lambda \in \mathbb {R}, \text{ the } \text{ sublevel } \text{ set } S_\lambda =\{x\in X~:~\varphi (x)\le \lambda \} \text{ is } \text{ convex. } $$

• semi-strictly quasi-convex on K if, $\varphi$ is quasi-convex and for any $x,y\in K$,

  $$\varphi (x)<\varphi (y)\Rightarrow \varphi (z)<\varphi (y),\quad \forall \, z\in [x,y[. $$

Clearly, any convex function is semi-strictly quasi-convex while semi-strict quasi-convexity implies quasi-convexity. Roughly speaking, a semi-strictly quasi-convex function is a quasi-convex function that has no ‘full dimensional flat part’ except eventually at $\arg \min$.

Some years ago, a new concept of sublevel set called adjusted sublevel set has been defined in [1]: for any $x\in \mathrm{dom}\, f$, we define

$$S^a_\varphi (x)=S_{\varphi (x)}\cap \overline{B}(S^<_{\varphi (x)},\rho _x), $$

where $S^>_\lambda =\{x\in X~:~\varphi (x)<\lambda \}$ stands for the strict sublevel set of $\varphi$ at point x and moreover $\rho _x=dist(x,S^<_{\varphi (x)})$, if $S^<_{\varphi (x)}\ne \emptyset$

and $S^a_\varphi (x)=S_{\varphi (x)}$ if $S^<_{\varphi (x)}=\emptyset$.

Note that actually $S^{a}_\varphi (x)$ coincides with $S_{\varphi (x)}$ if $\text{ cl }(S^>_{\varphi (x)})=S_{\varphi (x)}$. It is, for example, the case whenever f is semi-strictly quasi-convex.

Based on this concept of sublevel sets, one can naturally define the following set-valued map called adjusted normal operator $N^a_\varphi$ defined by

$$ N^a_\varphi (x) =\{x^*\in \mathbb {R}^n~:~\langle x^*,y-x\rangle \le 0,~~\forall \,y\in S^a_\varphi (x)\}. $$

Now following [2, Prop. 5.1], a necessary and sufficient optimality conditions can be proved for the minimization of a quasi-convex function over a convex set.

Proposition 6.2.1

Let C be a closed convex subset of X, $\bar{x}\in C$ and $\varphi :\mathbb {R}^n\rightarrow \mathbb {R}$ be continuous semi-strictly quasi-convex such that $\text{ int }(S^a_\varphi (\bar{x}))\ne \emptyset$ and $\varphi (\bar{x})>\inf _X \varphi$.

Then the following assertions are equivalent:

• (i) $\varphi (\bar{x})=\min _C \varphi$.

• (ii) $\bar{x}\in VI(N^a_\varphi \setminus \{0\},C)$.

Let us observe that the notation $N^a_f\setminus \{0\}$ means that at any point x, 0 is dropped from the cone $N^a_\varphi (x)$. It is an essential technical point for the above equivalence since it allows to avoid any ‘trivial solution’ of the variational inequality.

As a consequence if C is a closed convex subset of X such that $C\cap \arg \min _{\scriptstyle \mathrm {I\!R}} f=\emptyset$, then one has an analogous of the extremely important equivalence (6.2) and it can be proved in the context of quasi-convex optimization.

$$\begin{aligned} EP(f,C)=\arg \min _C \varphi =VI(N^a_\varphi \setminus \{0\},C)\qquad \text{ where } f(x,y)= \varphi (y) - \varphi (x). \end{aligned}$$

(6.4)

The table below summarizes the interrelations stated above between equilibrium problems and variational inequalities in the very particular case where they are defined through an optimization problem.

Initial problem	EP reformulation	Hypothesis	VI reformulation	Hypothesis
$\min _C\varphi$	$\arg \min _C \varphi =EP(f_\varphi ,C)$	none	$\arg \min _C \varphi =VI(\nabla \varphi ,C)$	$\varphi$ diff. convex
	with			C convex non-empty
	$f_\varphi (x,y)=\varphi (y)-\varphi (x)$
			$\arg \min _C \varphi =VI(\partial \varphi ,C)$	$\varphi$ lsc proper convex
				C convex non-empty
			$\arg \min _C \varphi$ $=VI(N^a_\varphi \setminus \{0\},C)$	$\varphi$ continuous and
				semi-strictly quasi-convex
				C convex non-empty
				$C\cap \arg \min _{\scriptstyle \mathrm {I\!R}^n}f=\emptyset$

6.2.2 The More General Case

Based on the interrelations recalled in the previous subsection, we will now explore the relations that can be stated between equilibrium problem EP(f, C) and variational inequalities whenever the function f is not coming from an optimization problem.

Given a subset C of $\mathbb {R}^n$ and a set-valued map $F:\mathbb {R}^n\rightrightarrows \mathbb {R}^n$ and the associated variational inequality VI(F, C), an immediate link with an equilibrium problem can be stated by simply considering a dedicated bifunction $f_F$:

$$ VI ( F, C) = EP ( f_F, C) \qquad \text{ where } f_F(x, y) = \langle F(x), y - x \rangle . $$

This equality being valid without any hypothesis one can thus consider that variational inequality problem are actually particular cases of the class of equilibrium problems. Let us now explore the reverse question that is under which conditions an equilibrium problem EP(f, C) can be seen as a variational inequality problem.

For an equilibrium problem in the general framework to yield nice results, it is needed to fulfil some assumption on the data. One the most common assumptions in the literature (see, for example [4,5,6,7,8,9,10,11,12,13]) is the following:  

(H1):

$f(x, x) = 0$ for all $x \in \mathbb {R}^n$ (or for just $x \in C$).

(H2):

For any $x \in \mathbb {R}^n$, the function $y \mapsto f(x, y)$ is a convex function.

 

The first condition shows that if $x^*$ is a solution of the equilibrium problem then $x^*$ minimizes the function $f( x^*, y )$ over C. Now assume that f is a differentiable convex function in y and C is non-empty and convex. Then we can write down the necessary and sufficient optimality condition as

$$\begin{aligned} \langle \nabla _y f (x^*, x^* ) , y - x^* \rangle \ge 0 , \qquad \forall y \in C. \end{aligned}$$

This shows that $x^*$ solves the variational inequality $VI ( F_f, C )$ where, for each $x\in \mathbb {R}^n$, $F_f (x) = \nabla _y f(x, x)$. Further if $x^*$ solves $VI ( F_f, C)$ then by (6.1) and the convexity of f in the second variable it is clear that $x^*$ minimizes $f (x^*, .)$ over C and since $f( x^*, x^* ) = 0$ we conclude that $x^*$ solves EP(f, C) . Thus, the solution set of EP(f, C) coincides with the solution set of $VI ( F_f, C)$ once we assume that f is differentiable and convex in the second variable that is

$$ EP ( f, C ) = VI ( F_f(x),C)\qquad \text{ where } F_f(x)=\nabla _y f(x, x). $$

Looking to the developments of Sect. 6.2.1, one can wonder if the above relation (6.2.2) can actually be generalized to the case where f is not differentiable and/or not convex in the second variable. First if, for any $x\in C$, the function $f(x,\cdot )$ is convex lower semi-continuous then, using the same proof as above one obtains

$$ EP ( f, C ) = VI ( F_f(x),C)\qquad \text{ where } F_f(x)=\partial _y f(x, x). $$

Finally if (H1) holds true, C is convex and the function is only assumed to be continuous and semistricly quasi-convex in the second variable then, as previously explained, $x^*$ is a solution of EP(f, C) if and only if $x^*$ minimizes $f ( x^*, .)$ and therefore, using Proposition 6.2.1, one immediately have

$$ EP ( f, C ) = VI ( F_f(x),C)\qquad \text{ where } F_f(x)=N^a_{f(x, \cdot )}(x)\setminus \{0\}. $$

Thus, as a conclusion, even if it is true in a full generality, we often have that an equilibrium problem EP(f, C) can be seen as a variational inequality.

The above stated interrelations are summarize in the table below, where assumption (H1) and (H2) is assumed to hold.

Initial problem	EP reformulation	Hypothesis	VI reformulation	Hypothesis
VI(F, C)	$VI(F,C)=EP(f_F,C)$	none
	with
	$f_F(x,y)=\langle F(x),y-x\rangle$
EP(f, C)			$EP(f,C)=VI(F_f,C)$	f(x, .) diff. convex, $\forall \,x$
			with	C convex non-empty
			$F_f(x)=\nabla _2 f(x,\cdot )(x)$	$f(x,x)=0,~~\forall \,x$
			$EP(f,C)=VI(F_f,C)$	f(x, .) lsc proper convex, $\forall \,x$
			with	C convex non-empty
			$F_f(x)=\partial _2 f(x,\cdot )(x)$	$f(x,x)=0,~~\forall \,x$
			$EP(f,C)=VI(F_f,C)$	f(x, .) continuous
				and semi-strictly quasi-convex, $\forall \,x$
			with $F_f(x)=$	C convex non-empty
			$N^a f(x,\cdot )(x)\setminus \{0\}$	$C\cap \arg \min _{\scriptstyle \mathrm {I\!R}^n}f=\emptyset$

6.3 Existence Results for EP Through VI

Here, we present some existence results for both equilibrium problem and the variational inequality problem which are well established in the literature. We can see that the relation between EP and VI mentioned in the previous table implies the interrelation between the existence results of these two classes of problems.

Theorem 6.3.1

([14, 15]) Let C is a non-empty, convex and compact subset of $\mathbb {R}^n$ and let $F : \mathbb {R}^n \rightarrow \mathbb {R}^n$ be a continuous mapping. Then there exists a solution to the problem VI(F, C) .

Theorem 6.3.2

Let $C \subset \mathbb {R}^n$ be non-empty, convex and compact. Also let that $f : \mathbb {R}^n \times \mathbb {R}^n \rightarrow \mathbb {R}$ is bifunction such that f(x, .) is convex, differentiable and $f(x,x) =0$ for any $x \in X$. Then the solution set of the problem EP(f, C) is non-empty

Keeping in view of the relation between EP and VI as presented in the previous section it is clear that Theorem 6.3.2 follows in a straightforward fashion from Theorem 6.3.1

The following existence result for VI with set-valued function is a particular case of Theorem 3.1 [16].

Theorem 6.3.3

Let C be a non-empty, convex, compact subset of $\mathbb {R}^n$ and $F : \mathbb {R}^n \rightrightarrows \mathbb {R}^n$ be an upper semi-continuous set-valued map with convex, compact values. Then VI(F,C) has a solution.

A similar theorem is present in the literature by Ky Fan [17] for the equilibrium problem.

Theorem 6.3.4

(Theorem 1, [17]) Let C is a non-empty, convex, compact subset of $\mathbb {R}^n$. If a continuous bifunction $f : \mathbb {R}^n \times \mathbb {R}^n \rightarrow \mathbb {R}$ satisfies the following properties:

$\bullet$ $f(x,.) : \mathbb {R}^n \rightarrow \mathbb {R}$ is convex for each $x \in C$.

$\bullet$ $f(x,x)=0$ for any $x \in C$.

Then the equilibrium problem EP(f, C) has a solution.

Again looking at the relationship between EP and the VI with set-valued map as we have presented in the previous section, it is clear that Ky Fan’s result can be deduced from Theorem 6.3.3.

There are some results in the literature about the existence of the solutions of EP(f, C) and VI(F, C) , when C is closed but unbounded. But these results were developed independently. Here we show that the link between EP and VI problems leads to those existence results of EP once we assume the same for the VI.

Theorem 6.3.5

(Prop 2.2.3 [19]) Let $C \subset \mathbb {R}^n$ be closed convex and $F : \mathbb {R}^n \rightarrow \mathbb {R}^n$ be continuous. If there exists $u \in \mathbb {R}^n$ such that the set

$$\begin{aligned} V_{<} := \{ x \in C : \langle F(x), x-u \rangle < 0 \} \end{aligned}$$

is bounded (possibly empty), then VI(F, C) has a solution.

The next theorem is an existential result for the equilibrium problem developed by Iusem et al. (Theorem 4.2 [18]). Here, we show that the same result is obtained using the last theorem which ensures the existence of a solution of a VI problem.

Theorem 6.3.6

Let $C \subset \mathbb {R}^n$ is closed convex and $f : \mathbb {R}^n \times \mathbb {R}^n \rightarrow \mathbb {R}$ is a bifunction such that $f(x,.) : \mathbb {R}^n \rightarrow \mathbb {R}^n$ is differentiable convex and $f(x,x) = 0$ for each $x \in C$. If there exists $u \in C$ such that the set

$$\begin{aligned} L_{>} := \{ x \in C : f(x,u) > 0 \} \end{aligned}$$

is bounded (possibly empty), then EP(f, C) has a solution.

Proof

As f(x, .) is convex and differentiable function for all $x \in C$, we already know that $EP(f,C) = VI(F_f, C)$; where $F_f(x)= \nabla _2 f(x,.)(x)$. Also for any $x \in C$,

$$\begin{aligned} f(x,u) \ge f(x,x) + \langle \nabla _2 f(x,.)(x), u-x \rangle . \end{aligned}$$

By the given hypothesis, we get

$$\begin{aligned} f(x,u) \ge \langle F_f(x), u-x \rangle . \end{aligned}$$

(6.5)

From (6.5), it is clear that $\{ x \in C : \langle F_f(x), x-u \rangle < 0 \} \subseteq \{ x \in C : f(x,u)> 0 \}= L_{>}$. Now the boundedness of $L_{>}$ (possibly empty) implies that $\{ x \in C : \langle F_f(x), x-u \rangle < 0 \}$ is bounded (possibly empty). Then by Theorem 6.3.5, $VI(F_f,C)$ has a solution, implying that EP(f, C) also has solution.

Remark 6.3.1

With the similar assumptions on F and C as Theorem 6.3.5 for VI, if we assume that there exists $u \in C$ and $\zeta \ge 0$ such that

$$\begin{aligned} \liminf \limits _{ \Vert x \Vert \rightarrow \infty } \frac{\langle F(x), x-u \rangle }{ \Vert x \Vert ^{\zeta }} >0, \end{aligned}$$

(6.6)

then VI(F, C) has a solution (Prop. 2.2.7, [19]). Note that the coercivity condition (6.6) implies the boundedness of the set $V_{<}$ in Theorem 6.3.5.

Similar thing happens with the equilibrium problem also. The boundedness condition of $L_{>}$ can be replaced by the coercivity condition of f,

$$\begin{aligned} \liminf \limits _{ \Vert x \Vert \rightarrow \infty } \frac{-f(x,u)}{ \Vert x \Vert ^{\zeta }} >0. \end{aligned}$$

6.4 Examples and Counterexamples

In the previous section, it was shown that under some natural assumptions the solution set of an equilibrium problem coincides with the solution set of an associated variational inequality problem. Given the problem EP(f, C), where C is non-empty and convex, f is differentiable and (H1) holds. We shall call the problem $VI(F_f, C)$, with $F_f(x)= \nabla _y f(x,.)(x)= \nabla _yf(x,x)$ as the variational inequality associated with the equilibrium problem EP(f, C). This is because if $x^*$ is a solution of EP(f, C), then $x^*$ solves $VI(F_f,C)$, though the converse need not be true. Taking a clue from an example taken from Muu et al. [3], we show an equilibrium problem which can not be solved by solving the associated variational inequality.

Example 6.4.1

Consider the following equilibrium problem. Find $x \in C$ such that

$$\begin{aligned} f(x,y) \ge 0 \quad \text{ for } \text{ all } \quad y \in C, \end{aligned}$$

where $f(x,y)=\langle x,y-x \rangle + x^2 -y^2$ and $C=[-1,1]$. Since there does not exist any such $x \in [-1,1]$, this equilibrium problem does not have any solution. Here $f_y(x,y)=x-2y$, which implies that $\nabla f_y(x,x)= -x$. Hence, the variational inequality associated with the above mentioned equilibrium problem is given as follows. Find x such that

$$\begin{aligned} \langle -x, y-x \rangle \ge 0 \quad \text{ for } \text{ all } y \in [-1,1]. \end{aligned}$$

Note $x=0$ satisfies the above inequality for all $y \in [-1,1]$, implying that the associated variational inequality has a solution when the equilibrium problem does not.

The above example shows that in general an equilibrium problem may not be related to its associated variational inequality. The above example might appear artificial. Thus, it is natural to ask if there is an example of an equilibrium problem which is drawn from some application where its solution set does not coincide with the solution of its associated variational inequality. While trying to search for such an example, we came across the work of Muu et al. [3], where they have studied the profit maximization problem in the setting of an oligopolistic market. They showed that the existence of Nash equilibrium in such a market is equivalent to a hemivariational inequality. However, they assumed that cost function which tells us the cost of producing a given amount of a good is concave and increasing. Under this assumption, the Nash equilibrium problem cannot be solved by solving the hemivariational inequality problem. However, this assumption is flawed from the economic point of view. It is common knowledge in microeconomics that the function relating the cost of producing a given good with the quantity to be produced is a strictly( or strongly) convex function. We show below that if we consider the correct economic assumption on the cost function, the problem discussed by Muu et al. [3] is indeed equivalent to a variational inequality. We describe the problem in considerable detail.

Let us begin by considering an oligopolistic market. In an oligopolistic market, there are more than one firm produces the same commodity and compete among themselves. Thus, the unit price of the commodity fixed by one firm does not depend only on its own level of production but depends also on the amount of production achieved by other forms. More precisely, consider that there are n firms and let $x_i$ be the amount of the commodity produced by the ith firm and let $p_i$ be the price of the commodity given by the ith firm. In fact, we should write the price as $p_i( x_1, x_2, \ldots , x_n)$. Let $h_i$ be the cost function associated with the firm and thus for producing the amount $x_i$, the firm i needs to spend $h( x_i )$. Thus, the profit or the pay-off function for the ith firm is a function $f_i : \mathbb {R}^m \rightarrow \mathbb {R}$ is s given as

$$\begin{aligned} f_i ( x)= f_i ( x_1, \ldots x_m) = x_i p_i ( x_1, \ldots , x_n) - h_i(x_i). \end{aligned}$$

In fact, it is natural to assume that the cost function $h_i$ of the ith firm depends only on production level of the ith firm itself. It is also important to note that in an oligopolistic structure, the number of firms is not very large. Further, we assume that each firm i has a strategy set $U_i \subset \mathbb {R}$ and we can safely assume it to be convex. This strategy set allows the firm i to set its production level once it has idea of the production level of other firms. This is quite natural since the number of firms is quite less. Thus, a point $\bar{x} = (\bar{x}_1, \ldots , \bar{x}_n) \in U = U_1 \times U_2 \times \cdots \times U_n$ is a Nash equilibrium if for each $i = 1, \ldots , n$

$$\begin{aligned} f_i ( \bar{x}_1, \bar{x}_2, \ldots , \bar{x}_{i-1}, y_i , \bar{x}_{i+1}, \ldots \bar{x}_n) \le f ( \bar{x}_1, \bar{x}_2, \ldots , \bar{x}_i, \ldots , \bar{x}_n ) , \end{aligned}$$

for all $y_i \in U_i$. In fact, one can express this as a sequence of minimization problem. Let $x^{-i}$ denote the production levels of all the firms except the ith firm. Thus, we can write

$$\begin{aligned} x^{-i} = ( x_1, x_2, \ldots , x_{i-1}, x_{i+1}, \ldots , x_n )^T. \end{aligned}$$

Traditionally in the study of Nash equilibrium, one can write the vector x as $x = ( x_i, x^{-i})$. Let us write the loss function for the ith firm as

$$\begin{aligned} \theta _i ( x_i, x^{-i}) = -f_i ( x_1, \ldots , x_n ) = h_i(x_i) - x_i p_i ( x_1, \ldots , x_n ). \end{aligned}$$

Thus for any given $x^{-i}$, the object of the ith firm is to choose a strategy which solves the problem $P_i ( x^{-i})$ given as

$$\begin{aligned} \min _{ x_i \in U_i} \theta _i ( x_i, x^{-i}). \end{aligned}$$

Let $S ( x^{-i})$ denote the solution set of the problem $P_i ( x^{-i})$. A vector $\bar{x}$ is a Nash equilibrium if $\bar{x}_i \in S ( \bar{x}^{-i} )$ for each $i = 1, \ldots , n$. In order solve the above problem, most economists would like to have at least have that $\theta _i$ is convex in $x_i$. Thus, this means that $h_i(x_i) - x_i p_i ( x_1, \ldots , x_n )$ must be convex in $x_i$. In fact, Muu et al. [3] considers $p( x_1, \ldots , x_n ) = \alpha _i - \beta _i ( x_1 + \cdots + x_n )$ where, $\alpha _i$ and $\beta _i$ are constants with $\beta _i \ge 0$. Note that in this case we have

$$\begin{aligned} x_i p_i ( x_1, \ldots x_n ) = \alpha _i x_i - \beta _i ( x_1 x_i + \cdots + x^2_i + \cdots + x_n x_i ) . \end{aligned}$$

This is in fact concave in $x_i$. Further as per the standard assumptions in economic theory we consider that the cost function $h_i$ is strongly convex and this proves that $\theta _i$ is convex in $x_i$ . In fact, a careful inspection would show that it is actually jointly convex in all the variables. Through the following proposition our aim would be to show that under the above assumptions the Nash equilibrium can be computed by solving a hemivariational inequality through of the non-monotone type.

Proposition 6.4.1

Let us assume that $\bar{x}$ is the Nash equilibrium of the oligopolistic market model discussed above. Let us assume that the cost function $h_i$ of each of the ith firm is strongly convex and the unit price $p_i$ quoted by the ith firm is given as

$$\begin{aligned} p_i( x_1, \ldots , x_n) = \alpha _i - \beta _i ( x_1 + \cdots + x_n), \end{aligned}$$

where $\alpha _i \in \mathbb {R}$ and $\beta _i \ge 0$. Then $\bar{x}$ solves the hemivariational inequality $VI ( F, + \nabla \varphi , U )$, where $F(x) = \tilde{B} x - \alpha$, $\alpha = ( \alpha _1, \ldots , \alpha _n) ^T$ with $\tilde{B}$ is a $n \times n$ matrix whose ith row has the entry 0 at the ith column and all other entries are $\beta _i$ and $\varphi$ is given as

$$\begin{aligned} \varphi (x) = \langle x, Bx \rangle + h(x), \end{aligned}$$

where B is a diagonal matrix given as $B = \text{ diag } ( \beta _1, \ldots \beta _n)$ and $h(x) = \sum _{i=1}^n h_i( x_i)$.

Conversely if $\bar{x}$ is a solution to $VI ( F + \nabla \varphi , U)$ with F and $\varphi$ as given above then $\bar{x}$ is indeed a Nash equilibrium for the oligopolistic market model.

Proof: Let us begin by assuming that $\bar{x}$ is the Nash equilibrium of the oligopolistic market model described above. Thus for each $i = 1, \ldots , n$, we have

$$\begin{aligned} f_i ( \bar{x}_1, \bar{x}_2, \ldots , \bar{x}_{i-1}, y_i , \bar{x}_{i+1}, \ldots \bar{x}_n) \le f ( \bar{x}_1, \bar{x}_2, \ldots , \bar{x}_i, \ldots , \bar{x}_n ) , \end{aligned}$$

for all $y_i \in U_i$. Of course, we know that $U = U_1 \times U_2 \times \cdots \times U_n$. From the above expression, a simple manipulation will show that

$$\begin{aligned} h_i ( y_i ) - y_i \left( \alpha _i - \beta _i \left( y_i + \sum _{j=1, j \ne i}^n \bar{x}_j \right) \right) \ge h_i ( \bar{x}_i ) - \bar{x}_i p_i ( \bar{x}_1, \ldots , \bar{x}_n) . \end{aligned}$$

Further simplification shows that

$$\begin{aligned} h_i ( y_i) - h_i (\bar{x}_i) + ( \beta _i \bar{x}_1 + \cdots + \beta _i \bar{x}_{i-1} + \beta _i x_{i+1} + \cdots + \beta _i \bar{x}_n - \alpha _i) ( y_i - \bar{x}_i) \\ + \beta _i y^2_i - \beta _i \bar{x}^2_i \ge 0, \end{aligned}$$

for all $y_i \in U_i$. Summing over all i from 1 to n we have

$$\begin{aligned} \sum _{i=1}^n h_i ( y_i) - \sum _{i=1}^n h_i ( \bar{x}_i) + \langle \tilde{B} \bar{x} - \alpha , y - \bar{x} \rangle + \langle y, By \rangle - \langle x, Bx \rangle \ge 0 \quad \forall y \in U. \end{aligned}$$

This shows that $\bar{x}$ solves $VI ( F + \nabla \varphi , U )$.

Conversely let $\bar{x}$ solve $VI ( F + \nabla \varphi , U )$ with F and $\varphi$ as described in the statement of the proposition. Thus, we have

$$\begin{aligned} \sum _{i=1}^n h_i ( y_i) - \sum _{i=1}^n h_i ( \bar{x}_i) + \langle \tilde{B} \bar{x} - \alpha , y - \bar{x} \rangle + \langle y, By \rangle - \langle x, Bx \rangle \ge 0 \quad \forall y \in U. \end{aligned}$$

(6.7)

Let us choose $y \in U$ as follows:

$$\begin{aligned} y = ( \bar{x}_1, \bar{x}_2, \ldots , \bar{x}_{i-1}, y_i , \bar{x}_{i+1}, \ldots , \bar{x}_n ) , \end{aligned}$$

where $y_i$ is any element from $U_i$. Plugging this y in (6.7), we get

$$\begin{aligned} h_i ( y_i) - h_i (\bar{x}_i) + ( \beta _i \bar{x}_1 + \cdots + \beta _i \bar{x}_{i-1} + \beta _i x_{i+1} + \cdots + \beta _i \bar{x}_n - \alpha _i) ( y_i - \bar{x}_i) \\ + \beta _i y^2_i - \beta _i \bar{x}^2_i \ge 0, \end{aligned}$$

which implies that $f_i(\bar{x}_1, \ldots , \bar{x}_{i-1},y_i, \bar{x}_{i+1}, \ldots , \bar{x}_n)\le f_i ( \bar{x}_1, \ldots , \bar{x}_n)$. This clearly shows that $\bar{x}$ is the Nash equilibrium of the oligopolistic market model. $\Box$.

As mentioned earlier in Muu et al. [3], it was assumed that $h_i$ is an increasing concave function for each i. Then $\varphi$ becomes a difference convex function, and thus, the $VI ( F + \nabla \varphi , U )$ would truly become an equilibrium problem which cannot be solved by solving a VI. However as we had discussed this issue with several economists, they have clearly told us that concavity assumption on the cost function is fundamentally incorrect since in such a case the graph of the cost function of a firm may always remain below the price curve $x_i p_i ( x_1, \ldots x_n)$ which leads the possibility of arbitrarily large amount of production in principle. However, no firm can make an arbitrarily large amount of commodities. The assumption of a convex curve limits the amount of commodities produced by the firm i and thus makes $U_i$ a compact and convex set. This will make it much easier to handle the problems $( P_i ( x^{-i} ) )$. Thus as we see that under the strong convexity assumption on the cost function of each firm, we have $\varphi$ to be strongly convex and thus $VI ( F + \nabla \varphi , U)$ is same as $VI ( F + 2B + \nabla h, U )$, since the cost functions are assumed to be twice differentiable. Thus, the analysis of the Nash equilibrium of an oligopolistic market under natural assumptions does not lead us to an equilibrium problem different from a VI. To the best of our knowledge, the problem of finding an application which can be modelled as an equilibrium problem that is not equivalent to its associated variational inequality remains to be open.

Thus given assumptions (H1) and (H2), it appears that the most general form of an equilibrium problem is a variational inequality problem. However, a variational inequality problem is more general than an optimization problem. This is what the following example will demonstrate.

Example 6.4.2

Consider the following convex optimization problem (CP):

$$\begin{aligned} \min f(x) \quad \text{ subject } \text{ to }\quad g_i(x) \le 0 , i = 1, \ldots , m , \quad x \in X, \end{aligned}$$

where f and each $g_i$, $i = 1, \ldots , m$ are finite-valued convex functions on X or $\mathbb {R}^n$ and X is a closed convex subset of $\mathbb {R}^n$. Associated with (CP) is the Lagrangian function $L : X \times \mathbb {R}^m_+ \rightarrow \mathbb {R}$ given as

$$\begin{aligned} L(x, \lambda ) = f(x) + \lambda _1 g_1(x) + \cdots + \lambda _m g_m (x). \end{aligned}$$

Assume that the Slater’s condition holds, i.e. there exists $\hat{x} \in \mathbb X$ such that $g_i(\hat{x}) < 0$ for all $i = 1. \ldots , m$. It is a well-known result in convex optimization (see, for example, Dhara and Dutta [20] ) that if Slater condition holds then $\bar{x} \in X$ is a minimizer of (CP) if and only if there exists $\bar{\lambda } \in \mathbb {R}^m_+$ such that

$$\begin{aligned} L( \bar{x}, \lambda ) \le L ( \bar{x} , \bar{\lambda }) \le L ( x, \bar{\lambda }) , \quad \text{ for } \text{ all } \quad x \in X, \lambda \in \mathbb {R}^m_+. \end{aligned}$$

(6.8)

The point $( \bar{x}, \bar{\lambda }) \in X \times \mathbb {R}^m_+$ is called a saddle point of the Lagrangian function. From (6.8), it is clear that

$$\begin{aligned} L ( \bar{x}, \bar{\lambda })= & {} \min _{ x \in X} L ( x, \bar{\lambda })\\ L ( \bar{x} , \bar{\lambda })= & {} \max _{ \lambda \in \mathbb {R}^m_+} L ( \bar{x}, \lambda ). \end{aligned}$$

Now using the standard necessary optimality for convex optimization (see Rockafellar [21]), we conclude that

$$\begin{aligned} - \nabla _x L ( \bar{x}, \bar{\lambda } ) \in N_ X ( \bar{x} ) \end{aligned}$$

and

$$\begin{aligned} \nabla _\lambda L ( \bar{x}, \bar{\lambda }) \in N_{\mathbb {R}^m_+} ( \bar{\lambda }). \end{aligned}$$

Noting that

$$\begin{aligned} N_X ({x}) \times N_{\mathbb {R}^m_+} ( \lambda ) = N_{ X \times \mathbb {R}^m_+} ( x, \lambda ) \end{aligned}$$

we conclude that under the Slater condition $( \bar{x}, \bar{\lambda }) \in X \times \mathbb {R}^m_+$ is a saddle point of the Lagrangian function if and only if $( \bar{x}, \bar{\lambda })$ solves the following variational inequality:

$$\begin{aligned} 0 \in F ( x, \lambda ) + N_{ X \times \mathbb {R}^m_+} ( x, \lambda ) \end{aligned}$$

where $F ( x, \lambda ) = ( \nabla _x L ( x, \lambda ), -\nabla _\lambda L ( x, \lambda ))$. It is clear that $F ( x, \lambda )$ is not the gradient of a convex function and in fact, it is not the gradient of the Lagrangian function jointly in both variable. Thus, we have a variational inequality which is not the optimality condition of convex optimization problem.

For more examples of this type, see Borwein and Dutta [22] and Borwein and Lewis [23].

6.5 Link Between QEP and QVI

A more general version of the variational inequality problem is the quasi-variational inequality (QVI) problem (see [24]) and the quasi-equilibrium problem (QEP) generalizes the standard equilibrium problem with set-valued maps. For more details on quasi-equilibrium problems, see, for example, [25, 26]. In this section, we present the observations about the relation between QEP and QVI, i.e. under which assumptions a QEP is equivalent to a QVI.

Given two set-valued maps $T : \mathbb {R}^n \rightrightarrows \mathbb {R}^n$ and $K: \mathbb {R}^n \rightrightarrows \mathbb {R}^n$, the problem QVI(T, K) is defined as:

$$\text{Find}\,\, x \in K(x) \,\,\text{such that there exists} \,\,x^{*} \in T(x) \,\,\text{with} \,\,\langle x^* , y-x \rangle \ge 0 \,\,\text{for all} \,\,y \in K(x). $$

For a bifunction $f : \mathbb {R}^n \times \mathbb {R}^n \rightarrow \mathbb {R}$ and a set-valued map $K: \mathbb {R}^n \rightrightarrows \mathbb {R}^n$, QEP(f, K) is

$$\text{Find}\,\, x \in K(x) \,\,\text{such that}\,\, f(x,y) \ge 0 \,\,\text{for all}\,\, y \in K(x). $$

The following assumptions have been taken for QEP(f, K) in this chapter which also appear in literature:

$\mathscr {A} 1:$ f(x, .) is convex for each $x \in \mathbb {R}^n$.

$\mathscr {A} 2:$ $f(x,x) = 0$ for each $x \in \mathbb {R}^n$.

$\mathscr {A} 3:$ K(x) is non-empty, convex and closed for all $x \in \mathbb {R}^n$.

If $x^*$ is a solution of QEP(f, K) , by assumption $\mathscr {2}$ we get that $x^* \in K(x^*)$ and

$$\begin{aligned} f(x^*,y) \ge f(x^*,x^*) \quad \forall y \in K(x^*), \end{aligned}$$

which is nothing but a solution of the following minimization problem:

$$\begin{aligned} \min f(x^*,y) \quad \text{ subject } \text{ to } y \in K(x^*). \end{aligned}$$

Additionally if we assume that f(x, .) is lsc, proper for any $x \in \mathbb {R}^n$, by the necessary and sufficient optimality condition for this problem we get that there exists $\xi ^* \in \partial _2 f(x^*,.)(x^*)$ such that

$$\begin{aligned} \langle \xi ^*, y-x \rangle \ge 0 \quad \forall y \in K(x^*). \end{aligned}$$

(6.9)

This implies that $x^*$ is a solution of the $QVI(T_f, K)$, where $T_f(x)= \partial _2 f(x,.)(x)$. Further if $x^*$ solves $QVI(T_f, K)$, (6.9) holds with some $\xi ^* \in \partial _2 f(x^*,.)(x^*)$. This together with $\mathscr {A} 1$ and $\mathscr {A} 2$ implies that $x^*$ is a solution of QEP(f, K) . Hence

$$\begin{aligned} QEP(f,K)= QVI(T_f,K) \quad \text{ where } T_f(x)= \partial _2 f(x,.)(x). \end{aligned}$$

In particular when f(x, .) is differentiable for any $x \in \mathbb {R}^n$, using the gradient for subdifferential we get

$$\begin{aligned} QEP(f,K)= QVI(T_f,K) \quad \text{ where } T_f(x)= \nabla _2 f(x,.)(x). \end{aligned}$$

Finally, if $\mathscr {A} 2$ and $\mathscr {A} 3$ are satisfied and the function f(x, .) is semi-strictly quasi-convex function for each $x \in \mathbb {R}^n$, we still get an equivalence relation between QEP and QVI. If $x^*$ is a solution of QEP(f, K) , we have

$$\begin{aligned} f(x^*, y) \ge 0 \quad \forall y \in K(x^*), \end{aligned}$$

which implies that $x^*$ is a solution of the equilibrium problem $EP(f, K(x^*))$. Then by Proposition 2.1, we can say that $EP( f, K(x^*) ) = VI ( T_f, K(x^*) )$, where $T_f(x) = N_{f(x,.)}^a (x) \backslash \{0\}$, which implies there exists $y^* \in T_f(x^*) = N_{f(x^*,.)}^a (x^*) \backslash \{0\}$ such that

$$\begin{aligned} \langle y^*, y- x^* \rangle \ge 0 \quad \forall y \in K(x^*). \end{aligned}$$

Hence, $x^*$ solves $QVI( T_f, K )$. Again if we assume that $x^*$ is a solution of the $QVI( T_f, K )$, following the previous arguments in reverse way we can easily show that $x^*$ also solves QEP(f, K) .

The above-stated observations are summarized in the following table with the assumption that $\mathscr {A}2$ and $\mathscr {A} 3$ hold:

Initial problem	QEP reformulation	Hypothesis	QVI reformulation	Hypothesis
QVI(T,K)	$QVI(T,K)=QEP(f_T,K)$ with $f_T(x,y) = \sup \limits _{\xi \in T(x)} \langle \xi , y-x \rangle$	T(x) is compact $\forall x \in \mathbb {R}^n$
QEP(f,K)			$QEP(f,K) = QVI(T_f,K)$ with $T_f(x)= \nabla _2 f(x, .)(x)$	f(x, .) diff. convex $\forall x \in \mathbb {R}^n$
			$QEP(f,K) = QVI(T_f,K)$ with $T_f(x)= \partial _2 f(x, .)(x)$	f(x, .) convex, lsc, proper $\forall x \in \mathbb {R}^n$
			$QEP(f,K) = QVI(T_f,K)$ with $T_f(x)= N_{f(x,.)}^a(x) \backslash \{0\}$	f(x,.) continuous and semi-strictly quasi-convex $\forall x \in \mathbb {R}^n$ $K(x)\cap \text{ argmin }_{\mathbb {R}^n}f$ = $\emptyset \quad \forall x \in \mathbb {R}^n$