Distributed Prediction-Correction Algorithms for Time-Varying Nash Equilibrium Tracking

Game theory has been extensively used in numerous applications, including social networks Ghaderi \BBA Srikant (\APACyear2014), sensor networks Stankovic \BOthers. (\APACyear2011) and smart grids Zeng \BOthers. (\APACyear2019). The Nash equilibrium (NE), an important satisfactory solution concept in noncooperative games, emerges to be of both theoretical significance and practical relevance Başar \BBA Olsder (\APACyear1998). Thus, the NE seeking method is becoming a key instrument in solving noncooperative game problems.

Recently, with the penetration of multi-player systems, several distributed approaches to achieve the NE seeking have been proposed Gadjov \BBA Pavel (\APACyear2018); De Persis \BBA Grammatico (\APACyear2019); Zhu \BOthers. (\APACyear2020); Chen \BOthers. (\APACyear2022). Such approaches, however, require time-invariant cost functions and NEs. In fact, in a variety of dynamic real-world situations, such as real-time traffic networks, online auctions, and intermittent renewable generations, the cost functions and NEs are time-varying. As a result, both academia and industry begin to focus on the time-varying NE tracking problem, which is a natural extension of time-invariant NE-related tasks in dynamic environments Lu \BOthers. (\APACyear2020); Su \BOthers. (\APACyear2021).

A natural ideal for solving the NE tracking problem is to treat it as a sequence of static problems and solve them one by one using time-invariant NE seeking methods. However, these time-invariant methods necessitate iterative multiples or even infinite rounds for each static problem, and thus are not suitable for real-time tracking situations. To fix this drawback, a solvable approach is to predict the next NE at the current instant, and use the predicted variables as the initial value when solving the static problem at the next instant. Intuitively, only if the predicted model is properly constructed to bring the predicted variables close to the next NE, it is possible to achieve satisfactory tracking performance. This idea is called the prediction-correction technique, and it has been used in solving centralized time-varying optimization problems Simonetto \BOthers. (\APACyear2017). The concept of changing initial values for iterative algorithms also motivates ADMM techniques in distributed time-varying optimizations Liu \BOthers. (\APACyear2022), which are to approximately solve each static optimization problem and use its output as the initial value for solving the next one. So far, neither prediction-correction techniques nor ADMM techniques have been used in solving distributed NE tracking problems to our knowledge. Another approach to solving NE tracking problems is found in the continuous-time regime Ye \BBA Hu (\APACyear2015); Huang \BOthers. (\APACyear2022), which relies on ODE solutions and may not be implemented using digital computation. In this paper, we focus on discrete-time algorithms.

The objective of this paper is to solve a time-varying NE tracking problem in a distributed manner with a prediction correction algorithm (DPCA). Specifically, a prediction step is proposed to predict the evolution of the NE trajectory using historical information, followed by a correction step to correct predictions by solving a time-invariant NE seeking problem obtained at each time. The contributions are summarized as follows.

1) To the best of our knowledge, our work is the first to study a distributed discrete-time algorithm for a time-varying NE tracking with provable convergence.

2) We prove that the proposed DPCA can track time-varying NEs with a bounded error that is in inverse proportion to the number of correction steps. This result provides a quantitative analysis of the trade-off between tracking accuracy and algorithm iterations. Moreover, our proof demonstrates that the minimum number of correction steps can be one, thereby meeting the requirement of real-time tracking.

3) Furthermore, we prove that with a small enough sampling period, the tracking error can be arbitrarily close to zero. For a time-invariant NE seeking problem, a special case of our formulation, we show that the tracking error linearly converges to zero.

4) A multi-robot surveillance scenario is used to test the performance of our algorithm with only one correction step. In addition, we compare the DPCA to no-predictor algorithms in terms of tracking error. The result verifies the significance of the introduced prediction step in the NE tracking and convergence.

This paper is organized as follows. The distributed NE trajectory tracking problem is presented in Section 2. The detailed algorithm design is proposed in Section 3 and the main results are established in Section 4. The result verification is investigated in Section 5. Finally, concluding remarks are given in Section 6.

Notation: Let $\mathbb{R}^{n}$ be the $n$-dimensional Euclidean space. For a scalar $a\in{\mathbb{R}}$, $\lceil a\rceil$ is the smallest integer not smaller than $a$. For $x\in{\mathbb{R}^{n}}$, denote its European norm by $\|x\|$ and its transpose by $x^{T}$. $[x_{i}]_{i\in{\mathcal{I}}}$ stacks the vector $x_{i}$ as a new column vector in the order of the index set $\mathcal{I}$. For matrices $A$, the Kronecker product is producted by $\otimes$ and the smallest eigenvalue is denoted by $\lambda_{\min}(A)$. Denote by $0_{n},~{}1_{n}\in{\mathbb{R}^{n}}$, and $I_{n}\in{\mathbb{R}^{n\times n}}$ the vectors of all zeros and ones, and the identical matrix, respectively. For a differentiable function $J(x):\mathbb{R}^{n}\!\rightarrow\!\mathbb{R}$, denote $\nabla_{i}J(x)=\frac{\partial J(x)}{\partial x_{i}}$ with respect to $x_{i}$, where $x=[x_{i}]_{i\in\mathcal{I}}$.

The time-varying game under consideration is denoted as $\Gamma^{t}=\{\mathcal{V},J^{t}_{i},x_{i}\}$, where $\mathcal{V}=\{1,\cdots,N\}$ denotes the set of $N$ players and $J_{i}^{t}:\mathbb{R}^{N}\rightarrow\mathbb{R}$ is the private time-varying cost function of player $i$. In the game $\Gamma^{t}$, each player $i$ aims to determine his time-varying strategy $x_{i}(t)$ to track the optimal trajectory shown below.

where $x_{-i}\in{\mathbb{R}^{N-1}}$ represents the joint strategies of all players except player $i$. If for any $t\geq 0$, there is

the time-varying vector $x^{*}(t)=[x_{i}^{*}(t)]_{i\in{\mathcal{V}}}$ is known as the NE trajectory. The NE trajectory tracking problem is a common issue in dynamic environments Huang \BOthers. (\APACyear2022). Take a practical example, consider a target protecting problem in $\mathbb{R}_{+}^{2}$ by $N$ players in order to block $N$ intruders with locations $p_{i}^{t}$ and protect a time-varying target $b_{t}$. To protect the target to the greatest extent possible, it is preferable to keep the weighted center $\sigma(x)\!=\!\sum_{i=1}^{N}x_{i}(t)/N,~{}x\!=\![x_{i}]_{i\in{\mathcal{V}}}$ of all players to track the target $b_{t}$. In this case, each player is constantly adjusting his position to minimize the time varying $J_{i}^{t}\!=\!\|x_{i}\!-p_{i}^{t}\|^{2}+\gamma_{1}\|x_{i}\!-b_{t}\|+\gamma_{2}\|\sigma(x)\!-b_{t}\|^{2}$, and the problem can be cast as a NE trajectory tracking problem (1).

To distributively solve the NE trajectory tracking problem, each player $i$ estimates all other players’ strategies for determining his tracking strategy over a communication graph. Assume that the underlying communication graph $\mathcal{G}(\mathcal{V},A)$ is undirected and connected. The adjacent matrix is defined as $A=[a_{ij}]_{N\times N}$, if the communication link between $i$ and $j$ exists, $a_{ij}>0$; otherwise, $a_{ij}=0$. The corresponding Laplacian matrix is $L=[l_{ij}]_{N\times N}$ with $l_{ij}=-a_{ij}$ if $i\neq j$, and $l_{ij}=\sum_{j\neq i}^{N}a_{ij}$ otherwise. The neighbors set of player $i$ is defined as $\mathcal{N}_{i}=\{j\in\mathcal{V}|a_{ij}>0\}$. For an undirected and connected graph $\mathcal{G}$, all eigenvalues of $L$ are real numbers and can be arranged by an ascending order $0=\lambda_{1}<\cdots\leq\lambda_{N}$.

Some definitions about player $i$’s estimated strategy are provided below. $x^{i}=[x^{i}_{i};x^{i}_{-i}]\in{\mathbb{R}^{N}}$ represents that player $i$’s estimates of all players’ strategies; $x_{i}^{i}\in{\mathbb{R}}$ represents player $i$’s estimate of his strategy, which is indeed his actual strategy, i.e., $x_{i}^{i}=x_{i}$; $x_{-i}^{i}\in{\mathbb{R}^{N-1}}$ represents player $i$’s estimates on all players’ strategies but his own. By the estimated strategy vector $x^{i}$ and the sampling period $h=t_{k+1}-t_{k}$, each player $i$ treat the problem (1) as a sequence of static problems

and then solve them one by one. However, the sampling period $h$ in the real-time tracking is unable to afford the time spent in exactly solving every static problems by using time-invariant NE seeking algorithms in De Persis \BBA Grammatico (\APACyear2019); Zhu \BOthers. (\APACyear2020); Chen \BOthers. (\APACyear2022). Therefore, how to design a dynamic algorithm to ensure good tracking performance with few iterative rounds during $h$ is the problem studied in this paper.

To proceed, we make some standard assumptions, which were also required in relevant game works  Ye \BBA Hu (\APACyear2015); Lu \BOthers. (\APACyear2020).

The augmented preudogradient is further defined as $\bm{F}^{t}(\bm{x})\!\!=\!\![\nabla_{i}J^{t}_{i}(x^{i})]_{i\in{\mathcal{V}}}:\mathbb{R}^{N^{2}}\!\!\rightarrow\!\!\mathbb{R}^{N}$ with $\bm{x}\!=\![x^{i}]_{i\in{\mathcal{V}}}\!\in\!\mathbb{R}^{N^{2}}$. Meanwhile, denote $\theta\!=\!\max_{i\in\mathcal{V}}\{\sqrt{(\theta_{i})^{2}+(\theta_{-i})^{2}}\}$. Under Assumption 2, the $\theta$-Lipschitz continuity of $\bm{F}^{t}(\bm{x})$ is given in Lemma 1, whose proof is similar to that of Lemma 2 in Chen \BOthers. (\APACyear2022) and is thus omitted.

In this section, Algorithm 1 is designed for each player $i,~{}i\!\in\!{\mathcal{V}}$ to generate a sequence $x^{i}_{k},~{}k\!\in\!{\mathbb{N}}$ to track time-varying NEs $x^{*}(t_{k})$. Algorithm 1 involves two steps: prediction and correction, which are depicted below.

The prediction step design: We derive the prediction step (3) by observing the dynamic of time-varying NE. Due to $F^{t}(x^{*}(t))=0_{N}$, the NE trajectory $x^{*}(t)$ satisfies the following nonlinear dynamical system

Then we employ two methods to discretely estimate (5) and generate auxiliary prediction sequences $x_{k+1|k}\in{\mathbb{R}^{N}}$. Meanwhile, the prediction errors $\Delta_{k}=\|x_{k+1|k}-x^{*}(t_{k+1})\|$ of these two methods are compared.

i) The first method is to set the predicted variable as the NE $x^{*}(t_{k})$ at the last time instant $t_{k}$, in other words,

In this case, the prediction error is measured as

ii) The second method involves a $q$-step interpolation method. In other words,

Recalling the dynamic (5), the prediction error $\bar{\Delta}_{k}=\|\bar{x}_{k+1|k}-x^{*}(t_{k+1})\|$ is then computed as follows,

Using the Mean Value Theorem and Assumption 1 yields

where $\xi\in(\tau-(q-r)h,\tau)$. Assumption 1 ensures that

If the sampling period $h$ is small enough, then $\bar{\Delta}_{k}\leq{\Delta}_{k}$, which indicates that the second method outperforms the first. In fact, the sampling period $h\ll 1$ in the dynamic environment. Hence, it motivates the design of prediction in (3), while ensuring that predicted variables $x^{i}_{k+1|k}$ are close to $x^{*}(t_{k+1})$ at the time instant $t_{k+1}$.

The correction step design: We employ a distributed gradient descent (DGD) algorithm (4) to correct errors produced in the prediction. In particular, the predicted variable $x^{i}_{k+1|k}$ that is close to $x^{*}(t_{k+1})$ is harnessed as the correction step’s initial value. It differs from the no-predictor DGD algorithm, which uses any initial state to exact update. In this sense, Algorithm 1 may require fewer iterative rounds $\tau$ and take less computation time to achieve the same tracking performance as the no-predictor DGD algorithm.

This section establishes the convergence of Algorithm 1. We first analyze the prediction error in Lemma 2, and then we examine the tracking error in Lemma 3. Following those, Theorem 1 rigorously characterizes the upper bound of the tracking error. Before we begin, we define stacked variables $\bm{x}_{k+1|k}\!=\![x_{k+1|k}^{i}]_{i\in{\mathcal{V}}}$, $\bm{x}_{k}\!=\![x^{i}_{k}]_{i\in{\mathcal{V}}}$ and $\bm{x}^{*}(t_{k})\!=\!1_{N}\otimes x^{*}(t_{k})$. The proofs of Lemmas 2 and 3 can be found in Appendix.

With Lemmas 2 and 3, we obtain our main theorem.

We prove that there must be a $\gamma_{0}\in(0,1)$ such that (14) holds. Define a decaying function $g(\gamma):\mathbb{R}\rightarrow\mathbb{R}$ related to $\gamma\in(0,+\infty)$ as follows,

By $q>\lceil\frac{2\rho^{\tau}}{1-\rho^{\tau}}\rceil$, we can easily obtain that

Thus, there is a constant $\gamma_{0}\in(0,1)$ satisfying (14).

Next, we prove (16) by starting with the case $k<q$, and then complete the proof for any $k\in{\mathbb{N}}$.

For any $k<q$, there is $\bm{x}_{k+1|k}=\bm{x}_{k}$. According to Lemma 3 and the triangle inequality, we have

The upper bound of the last term of (17) is analyzed. Based on (7), we know that $\|x^{*}(t_{k+1})-x^{*}(t_{k})\|\leq hc_{1}$. By the sequence summation, we rewrite (17) as

By (14) with $\rho^{\tau}<\gamma<1$, we have that for any $k<q$,

At last, we prove (16) for any $k\in{\mathbb{N}}$ via the mathematical induction. Assume that $\|\bm{x}_{k^{\prime}}-\bm{x}^{*}(t_{k^{\prime}})\|\leq C_{1}\gamma^{k^{\prime}}+C_{2}h^{2}$ for any $k^{\prime}\leq k,~{}k\geq q$. We prove $\|\bm{x}_{k^{\prime}+1}-\bm{x}^{*}(t_{k^{\prime}+1})\|\leq C_{1}\gamma^{k^{\prime}+1}+C_{2}h^{2}.$ By inputting (11) into (13), we have

Integrating the initial argument $\|\bm{x}_{k^{\prime}}-\bm{x}^{*}(t_{k^{\prime}})\|\!\leq\!C_{1}\gamma^{k^{\prime}}\!+\!C_{2}h^{2}$ for any $k^{\prime}\leq k,~{}k\geq q$, the definition of $C_{2}$ and the inequality (14) into (18), we obtain that for any $k\geq q$, $\|\bm{x}_{k^{\prime}+1}-\bm{x}^{*}(t_{k^{\prime}+1})\|\leq C_{1}\gamma^{k^{\prime}+1}+C_{2}h^{2}.$ Combining $\|\bm{x}_{k}-\bm{x}^{*}(t_{k})\|\leq C_{1}\gamma^{k}$ for any $k\in[0,q)$, we conclude that for any $k\in{\mathbb{N}}$, the inequality (16) holds. Theorem 1 shows that each sequence $\{x^{i}_{k}\}$ approaches a neighborhood of the NE trajectory $x^{*}(t_{k})$ as time passes. The exponentially convergence of Algorithm 1 is shown in the following corollary.

A robotic surveillance scenario Carnevale \BOthers. (\APACyear2022) is used to validate the effectiveness of Algorithm 1, including a tracking error comparison between Algorithm 1 and the no-predictor algorithm. Consider five robots collaborating to protect a time-varying target from five intruders. Each intruder $i$ moves according to the following rule:

where $p_{i}^{c}=[8+6(i-1);8+6(i-1)],~{}i\in\{1,\cdots,5\}$. The target moves via a similar law with (19), so we set it to be $b_{t}=\sum_{i=1}^{5}p_{i}^{t}/10.$ The dynamic protection strategy of each robot is determined by the following cost function

where $x_{i}(t)\in{\mathbb{R}^{2}}$ denotes the robot’s position, $\gamma_{1}=\gamma_{2}=0.1$ and $\gamma_{3}=0.875$. The aggregative variable $\sigma(x(t))=\sum_{i=1}^{5}x_{i}(t)/5$. The network graph is described by a ring. The parameters for Algorithm 1 are set to $q=400$, $\alpha=0.05$, $\varepsilon=0.01$, $h=0.1$ and $\tau=1$. The element of initial tracking sequences $\{x_{0}^{i}\}\in{\mathbb{R}^{10}}$ is generated at random within an interval $[5+5(i-1),10+5(i-1)]$.

Fig. 1 shows that for any $i\in\{1,\cdots,5\}$, every element of $x^{i}_{k}\in{\mathbb{R}^{10}}$ generated by Algorithm 1 can effectively reach consensus and track every element of the NE trajectory $x^{*}(t)$. Fig. 2 depicts that how the network constructs a smarter formation that protects the time-varying target $b_{t}$ better. As shown in Fig. 3(a), the tracking error $\|\bm{x}_{k}-\bm{x}^{*}(t_{k})\|$ converges to a constant term $7h^{2}=0.07$. Fig. 3 (b) demonstrates the importance of the prediction step in the NE trajectory tracking.

In this paper, we proposed a distributed prediction-correction algorithm (DPCA) to track the NE trajectory. By analyzing the coupling relationship between the prediction and the correction procedures, we rigorously proved that the tracking sequence generated by the DPCA can track the NE trajectory with a bounded error. This bound is proportional to the sampling period and inversely proportional to the number of correction steps. The results filled a gap in the study of NE tracking problems using discrete time algorithms. Moreover, the linear convergence rate for static games with time-invariant cost functions has been included in our results. The Future research of interests includes considering the communication efficient and privacy protected NE tracking algorithm.