Continuous time approximation of Nash equilibria

An elementary example which illustrates this approach may be observed when $X_{1}=X_{2}=[-1,1]$, $X=[-1,1]^{2}$,

$$f_{1}(x_{1},x_{2})=x_{1}x_{2},\;\;\text{and}\;\;f_{2}(x_{1},x_{2})=-x_{1}x_{2}.$$

It is not hard to check that the origin $(0,0)$ is the unique Nash equilibrium of $f_{1},f_{2}$ and that $f_{1},f_{2}$ satisfy (1.2) (with equality holding) for each $x,y\in[-1,1]^{2}$. We now seek an absolutely continuous path

$$u:[0,\infty)\rightarrow[-1,1]^{2}$$

such that

$$(\dot{u}_{1}(t)+u_{2}(t))(y_{1}-u_{1}(t))+(\dot{u}_{2}(t)-u_{1}(t))(y_{2}-u_{2}(t))\geq 0$$

(1.6)

holds for almost every $t\geq 0$ and each $(y_{1},y_{2})\in[-1,1]$.

It turns out that if

$$u_{1}(0)^{2}+u_{2}(0)^{2}\leq 1,$$

then the unique solution of these differential inequalities is

$$\begin{cases}\displaystyle u_{1}(t)=u_{1}(0)\cos(t)-u_{2}(0)\sin(t)\\ \\ \displaystyle u_{2}(t)=u_{2}(0)\cos(t)+u_{1}(0)\sin(t).\end{cases}$$

This solution simply parametrizes the circle of radius $\sqrt{u_{1}(0)^{2}+u_{2}(0)^{2}}$. In particular,

$$\lim_{t\rightarrow\infty}\frac{1}{t}\int^{t}_{0}u(s)ds=(0,0).$$

For general initial conditions $(u_{1}(0),u_{2}(0))\in[-1,1]^{2}$, it can be shown that $u_{1}(s)^{2}+u_{2}(s)^{2}\leq 1$ in a finite time $s\geq 0$. Refer to Figure 1 for a schematic. It then follows that the same limit above holds for this solution.

The method we present can be extended in certain cases when $X_{1},\dots,X_{N}$ are not compact. For example, suppose $X_{1}=X_{2}=\mathbb{R}$,

$$f_{1}(x_{1},x_{2})=\frac{1}{2}x_{1}^{2}-x_{1}x_{2}-x_{1},\;\;\text{and}\;\;f_{2}(x_{1},x_{2})=\frac{1}{2}x_{2}^{2}+x_{1}x_{2}-2x_{2}.$$

It is easy to check that $f_{1},f_{2}$ satisfy (1.2). Furthermore,

$$\begin{cases}\partial_{x_{1}}f_{1}(x_{1},x_{2})=x_{1}-x_{2}-1=0\\ \\ \partial_{x_{2}}f_{2}(x_{1},x_{2})=x_{2}+x_{1}-2=0\end{cases}$$

provided

$$x_{1}=\frac{3}{2}\quad\text{and}\quad x_{2}=\frac{1}{2}.$$

As a result, this is the unique Nash equilibrium of $f_{1},f_{2}$.

We note that the solution of

$$\begin{cases}\dot{u}_{1}(t)=-(u_{1}(t)-u_{2}(t)-1)\\ \\ \dot{u}_{2}(t)=-(u_{2}(t)+u_{1}(t)-2)\end{cases}$$

is given by

$$\begin{cases}\displaystyle u_{1}(t)=\frac{3}{2}+\left(u_{1}(0)-\frac{3}{2}\right)e^{-t}\cos(t)+\left(u_{2}(0)-\frac{1}{2}\right)e^{-t}\sin(t)\\ \\ \displaystyle u_{2}(t)=\frac{1}{2}+\left(u_{2}(0)-\frac{1}{2}\right)e^{-t}\cos(t)+\left(\frac{3}{2}-u_{1}(0)\right)e^{-t}\sin(t).\end{cases}$$

It is now clear that

$$\lim_{t\rightarrow\infty}(u_{1}(t),u_{2}(t))=\left(\frac{3}{2},\frac{1}{2}\right).$$

In particular, we do not need to employ the Cesàro mean of $u$ in order to approximate the Nash equilibrium of $f_{1},f_{2}$.

It just so happens that our method does not rely on the spaces $X_{1},\dots,X_{N}$ being finite dimensional. Consequently, we will consider the following version of our approximation problem. Let $V$ be a reflexive Banach space over $\mathbb{R}$ with norm $\|\cdot\|$ and continuous dual $V^{*}$. We further suppose

$$X_{1},\dots,X_{N}\subset V\;\text{are closed and convex with nonempty interiors}$$

(1.7)

and consider $N$ functions

$$f_{1},\dots,f_{N}:X\rightarrow\mathbb{R}$$

(1.8)

which satisfy

$$\begin{cases}f_{1},\dots,f_{N}\;\text{are weakly lowersemicontinuous},\\ \\ \displaystyle X\ni y\mapsto\sum^{N}_{j=1}f_{j}(y_{j},x_{-j})\;\text{is convex for each $\displaystyle x\in X$,}\\ \\ X\ni x\mapsto\displaystyle\sum^{N}_{j=1}f_{j}(y_{j},x_{-j})\;\text{is weakly continuous for each $y\in X$, and}\\ \\ \displaystyle\sum^{N}_{j=1}(\partial_{x_{j}}f_{j}(x)-\partial_{x_{j}}f_{j}(y),x_{j}-y_{j})\geq 0\;\;\text{for each $x,y\in X$}.\end{cases}$$

(1.9)

In the last condition listed above, we mean

$$\sum^{N}_{j=1}(p_{j}-q_{j},x_{j}-y_{j})\geq 0$$

for each

$$\displaystyle p_{j}\in\partial_{x_{j}}f_{j}(x):=\left\{\zeta\in V^{*}:f_{j}(z,x_{-j})\geq f_{j}(x)+(\zeta,z-x_{j}),\;z\in X_{j}\right\}$$

and $q_{j}\in\partial_{x_{j}}f_{j}(y)$ for $j=1,\dots,N$.

When $V$ is finite dimensional, we naturally identify $V$ and $V^{*}$ with Euclidean space of the same dimension. Alternatively, when $V$ is infinite dimensional, we will suppose there is a real Hilbert space $H$ for which

$$V\subset H\subset V^{*}$$

and $V\subset H$ is continuously embedded. It is with respect to this space $H$ in which we consider the following initial value problem: for a given $u^{0}\in X$, find an absolutely continuous $u:[0,\infty)\rightarrow H^{N}$ such that

$$\begin{cases}u(0)=u^{0},\;\text{and}\\ \\ \displaystyle\sum^{N}_{j=1}(\dot{u}_{j}(t)+\partial_{x_{j}}f_{j}(u(t)),y_{j}-u_{j}(t))\geq 0\;\text{for a.e. $t\geq 0$ and each $y\in X$.}\end{cases}$$

(1.10)

Our central result involving this initial value problem is as follows. In this statement, we will make use of the set

$${\cal D}=\left\{x\in X:\bigcap^{N}_{j=1}\left(\partial_{x_{j}}f_{j}(x)+n_{X_{j}}(x_{j})\right)\cap H\neq\emptyset\right\}.$$

(1.11)

Here $n_{X_{j}}:V\rightarrow 2^{V^{*}}$ is the normal cone of $X_{j}$ defined as

$$n_{X_{j}}(z):=\{\zeta\in V^{*}:(\zeta,y-z)\leq 0\;\text{all $y\in X_{j}$}\}$$

(1.12)

for $z\in V$ $(j=1,\dots,N)$.

We note that if $X_{1}=\cdots=X_{N}=V$, then $n_{X_{1}}\equiv\cdots\equiv n_{X_{N}}\equiv\{0\}$. In this case

$${\cal D}=\left\{x\in X:\bigcap^{N}_{j=1}\left(\partial_{x_{j}}f_{j}(x)\cap H\right)\neq\emptyset\right\},$$

(1.14)

and the initial value problem reduces to

$$\begin{cases}u(0)=u^{0},\;\text{and}\\ \\ \dot{u}_{j}(t)+\partial_{x_{j}}f_{j}(u(t))\ni 0\;\text{for a.e. $t\geq 0$ and each $j=1,\dots,N$}.\end{cases}$$

(1.15)

We will also explain that if in addition $(\partial_{x_{1}}f_{1},\dots,\partial_{x_{N}}f_{N})$ is single-valued, everywhere-defined, monotone, and hemicontinuous we can obtain the same result as above without assuming (1.9). This follows directly from a theorem of Browder and Minty.

We will phrase our initial value problem (1.10) as the evolution generated by a monotone operator on $H^{N}$ with domain ${\cal D}$. According to pioneering work of Brézis [5], the crucial task will be to verify the maximality of this operator. Regarding the large time behavior of solutions, the convergence to equilibria of maximal monotone operators by the Cesàro means of semigroups they generate originates in the work of Brézis and Baillon [3]. We also refer the reader to Chapter 3 of [2] which gives a detailed discussion of this phenomenon.

Of course, the asymptotic statements we made above are predicated on the existence of a Nash equilibrium. This is only guaranteed to be the case if $X$ is weakly compact or if there is some $\theta>0$ such that

$$\displaystyle\sum^{N}_{j=1}(\partial_{x_{j}}f_{j}(x)-\partial_{x_{j}}f_{j}(y),x_{j}-y_{j})\geq\theta\|x-y\|^{2}$$

(1.16)

for each $x,y\in X$. When such coercivity holds, $f_{1},\dots,f_{N}$ has a unique Nash equilibrium and solutions of the initial value problem (1.10) converge exponentially fast in $H^{N}$ to this equilibrium point.

We will prove Theorem 1.1 in the following section. Then we will apply this result to flows in Euclidean spaces of the form (1.4) in section 3. Finally, we will consider examples in Lebesgue and Sobolev spaces in section 4. A prototypical collection of functionals we will study is

$$f_{j}(v)=\int_{\Omega}\frac{1}{2}|\nabla v_{j}|^{2}+F_{j}(v)dx$$

(1.17)

for $j=1,\dots,N$, where $v=(v_{1},\dots,v_{N})\in H_{0}^{1}(\Omega)^{N}$ and $\Omega\subset\mathbb{R}^{d}$ is a bounded domain. For this particular example, we will argue that if $F_{1},\dots,F_{N}:\mathbb{R}^{N}\rightarrow\mathbb{R}$ satisfy suitable growth and monotonicity conditions, then $f_{1},\dots,f_{N}$ has a unique Nash equilibrium which can be approximated by solutions $u_{1},\dots,u_{N}:\Omega\times[0,\infty)\rightarrow\mathbb{R}$ of the parabolic initial/boundary value problem

$$\begin{cases}\partial_{t}u_{j}=\Delta u_{j}-\partial_{z_{j}}F_{j}(u)\;\;&\text{in}\;\Omega\times(0,\infty)\\ \;\;\;u_{j}=0\;\;&\text{on}\;\partial\Omega\times(0,\infty)\\ \;\;\;u_{j}=u^{0}_{j}\;\;&\text{on}\;\Omega\times\{0\}\end{cases}$$

(1.18)

for appropriately chosen initial conditions $u^{0}_{1},\dots,u^{0}_{N}:\Omega\rightarrow\mathbb{R}$.

We also remark that in finite dimensions, similar results were known to Flåm [15]. In particular, Flåm seems to be the first author to identify the important role of the monotonicity condition (1.2) in approximating Nash equilibrium. However, Rosen appears to be the first to consider using equations such as (1.4) to approximate equilibrium points [26]. In addition, we would like to point out that the finite dimensional variational inequality (1.3) and its relation to Nash equilibrium is studied in depth in the monograph by Facchinei and Pang [13]. In infinite dimensions, there have also been several recent works which discuss discrete time approximations for variational inequalities that correspond to Nash equilibrium [7, 6, 1, 11, 18].

Acknowledgements: This material is based upon work supported by the National Science Foundation under Grants DMS-1440140, DMS-1554130, and HRD-1700236, the National Security Agency under Grant No. H98230-20-1-0015, and the Sloan Foundation under Grant No. G-2020-12602 while the authors participated in a program hosted by the Mathematical Sciences Research Institute in Berkeley, California, during the summer of 2020.

Let $H$ be Hilbert space with inner product $\langle\cdot,\cdot\rangle$ and norm $|\cdot|$. We will denote $2^{H}$ as the power set or collection of all subsets of $H$. We recall that $B:H\rightarrow 2^{H}$ is monotone if

$$\langle p-q,x-y\rangle\geq 0$$

for all $x,y\in H$, $p\in Bx$, and $q\in By$. Moreover, $B$ is maximally monotone if the only monotone $C:H\rightarrow 2^{H}$ such that $Bx\subset Cx$ for all $x\in H$ is $C=B$. Minty’s well known maximality criterion is as follows [22].

Let us now recall a fundamental theorem for the initial value problem

$$\begin{cases}\dot{u}(t)+Bu(t)\ni 0,\;\text{a.e.}\;t\geq 0\\ u(0)=u^{0}.\end{cases}$$

(2.1)

As discussed in Chapter II of [5] and Chapter 3 of [2], the initial value problem is well-posed provided that $B$ is maximally monotone and $u^{0}$ is an element of the domain of $B$

$$D(B)=\{x\in H:Bx\neq\emptyset\}.$$

We also note that the operator $B$ generates a contraction. Let $u$ be a path as described in Brézis’ Theorem, and suppose $v:[0,\infty)\rightarrow H$ is any other Lipschitz continuous path with $v(t)\in D(B)$ for $t\geq 0$ and

$$\dot{v}(t)+Bv(t)\ni 0,\;\text{a.e.}\;t\geq 0.$$

Then

$$|u(t)-v(t)|\leq|u(0)-v(0)|,\quad t\geq 0.$$

(2.3)

If, in addition, there is some $\lambda>0$ such that

$$\langle p-q,x-y\rangle\geq\lambda|x-y|^{2}$$

(2.4)

for all $x,y\in H$, $p\in Bx$, and $q\in By$, then (2.3) can be improved to

$$|u(t)-v(t)|\leq e^{-\lambda t}|u(0)-v(0)|,\quad t\geq 0.$$

(2.5)

Remarkably, it is also possible to use solutions of the initial value problem (as described in Brézis’s Theorem) to approximate equilibria of $B$. These are points $y\in H$ such that

$$By\ni 0.$$

The following theorem was proved in [3].

Let us now suppose the spaces $V$, $X_{1},\dots,X_{N}$, and $H$ are as described in the subsection 1.2 of the introduction. We will further assume $f_{1},\dots,f_{N}:X\rightarrow\mathbb{R}$ are given functions which satisfy (1.9). An elementary but important observation we will use is that a given $y\in H$ induces a linear form in $V^{*}$ by the formula

$$(y,x):=\langle y,x\rangle,\quad(x\in V).$$

That this linear form is continuous is due to the continuity of the embedding $V\subset H$. For convenience, we will use $\|\cdot\|$ to denote both the norm on $V$ and the associated norm on $V^{N}$. Namely, we’ll write

$$\|x\|=\left(\sum^{N}_{j=1}\|x_{j}\|^{2}\right)^{1/2}$$

for $x=(x_{1},\dots,x_{N})\in V^{N}$. We will also use this convention for the inner product $\langle\cdot,\cdot\rangle$ and norm $|\cdot|$ on $H$ and on $H^{N}$ and the induced norm $\|\cdot\|_{*}$ on $V^{*}$ and on $(V^{*})^{N}$.

Let us specify $A:H^{N}\rightarrow 2^{H^{N}}$ via

$$Ax=\begin{cases}\left(\partial_{x_{1}}f_{1}(x)+n_{X_{1}}(x_{1})\right)\cap H\times\dots\times\left(\partial_{x_{N}}f_{N}(x)+n_{X_{N}}(x_{N})\right)\cap H,&x\in{\cal D}\\ \emptyset,&x\not\in{\cal D}\end{cases}$$

(2.6)

for $x\in H^{N}$. Here ${\cal D}$ is defined in (1.11).

In view of Brézis’ Theorem and the Baillon-Brézis Theorem, we can conclude Theorem 1.1 once we verify that $A$ is maximal. To this end, we will verify the hypotheses of Minty’s Lemma.