Distributed Nash Equilibrium Seeking Strategies Under Quantized Communication

Maojiao Ye,,, Qing-Long Han,,, Lei Ding,,,Shengyuan Xu, and Guobiao Jia

Abstract—This paper is concerned with distributed Nash equilibrium seeking strategies under quantized communication.In the proposed seeking strategy, a projection operator is synthesized with a gradient search method to achieve the optimization of players’ objective functions while restricting their actions within required non-empty, convex and compact domains.In addition, a leader-following consensus protocol, in which quantized information flows are utilized, is employed for information sharing among players.More specifically, logarithmic quantizers and uniform quantizers are investigated under both undirected and connected communication graphs and strongly connected digraphs, respectively.Through Lyapunov stability analysis, it is shown that players’ actions can be steered to a neighborhood of the Nash equilibrium with logarithmic and uniform quantizers, and the quantified convergence error depends on the parameter of the quantizer for both undirected and directed cases.A numerical example is given to verify the theoretical results.

I.INTRODUCTION

FRUITFUL results on distributed control and optimization of networked systems have been reported in the past two decades, see, e.g., [1]–[7], and the references therein.In particular, distributed Nash equilibrium seeking, which deals with partial information games in networked systems,becomes a new thriving research topic in recent years.For instance, based on the framework originated in [8], several consensus-based distributed Nash equilibrium seeking strategies were proposed to accommodate games in systems with fully distributed communication structures [9] and disturbances [10].Besides, gossip-based algorithms were provided to achieve distributed Nash equilibrium seeking [11], [12].Saddle point dynamics were investigated for a class of twonetwork zero-sum games [13].Besides, some attention has also been paid to dealing with the constraints, players’ dynamics, and communication costs, see, e.g., [14], [15].

It is worth mentioning that, as partial information games are taken into account, players need to broadcast some of their local information with others via a communication network.Hence, communication resources play a key role for distributed Nash equilibrium seeking strategies, and communication constraints are important factors to be considered for the design of seeking algorithms.As digital communication channels and digital sensors have limited bandwidth and only receive quantized values, it is necessary to quantize the data before transmission and storage, especially for finite rate links.In addition, to transmit information via digital channels,continuous signals should be coded by using analog-to-digital coders, resulting in non-negligible truncation errors between the continuous signal and its corresponding converted digital signal [16].Inspired by the facts above, some efforts have been made to achieve coordinated control of multi-agent systems with quantized data transmission [17]–[25].For instance,time-varying communication topologies with quantizers were addressed for the distributed iterative averaging problem [18].In [19], quantization effects on the performance of synchronized motion schemes were considered for a team of secondorder mobile agents.Constraints on communication data rates were considered for discrete-time average consensus problems [20].Dithered quantization was adopted to achieve average consensus in bandwidth constrained networks [21].Moreover, leader-following consensus of linear multi-agent systems under quantized, sampled data and Markovian switching communication networks was addressed [22].Based on layered structures, quantized communication was taken into account for distributed computing tasks of unmanned aerial vehicles [23].Bipartite consensus under quantization was investigated in [24], [25].The fault-tolerant consensus control problem for multi-agent systems with quantized data was addressed [26], [27], where data confidentiality was taken into account.Besides, the distributed convex optimization problem with quantized information was also investigated [28].

In addition, quantization effects were considered for discrete-time gradient-based Nash equilibrium seeking algorithms, where the notion of entropy power was adopted to quantify the lower bound on the asymptotic decaying rate of the mean-square error [29].However, it is required that players can communicate with each other via a complete graph,i.e., any two players in the game can communicate and transmit information directly with each other.Obviously, this requirement of complete/centralized communication is highly idealized, and thus can be hardly satisfied in practical implementation, especially for large-scale games.To the best of the authors’ knowledge, however, there have been few results in the literature regarding the effects of quantization on distributed Nash equilibrium seeking algorithms by relaxing this requirement.Therefore, it is of importance and essence to develop distributed Nash equilibrium seeking strategies under data quantization, which motivates the present study.

Based on the observations above, distributed Nash equilibrium seeking under quantization effects is investigated.Compared with existing works [8], [29], the main contributions of this paper are summarized as follows:

1) Distributed Nash equilibrium seeking strategies under quantized communication are established, where both logarithmic and uniform quantizations are taken into account,respectively.Moreover, a projection operator is incorporated into the gradient-based algorithm to deal with action constraints;

2) Based on theoretical analysis, some criteria are derived to ensure that the proposed strategies can converge to a neighborhood of the Nash equilibrium by suitably choosing control gains, where the effects of both logarithmic and uniform quantizations can be characterized explicitly;

3) The proposed distributed quanized Nash equilibrium seeking strategies can accommodate both undirected and directed topology graphs, beneficial for practical implementation.

We structure the rest of this paper as follows.Section II provides the notations and preliminaries.The considered problem is formulated in Section III.Main findings of this manuscript are presented in Section IV.Moreover, numerical studies on the performance of the proposed algorithms are illustrated in Section V.Lastly, Section VI draws conclusions for this paper.

II.NOTATIONS AND PRELIMINARIES

A. Quantizers

B. Algebraic Graph Theory

C. Nonsmooth Analysis

The following preliminaries on nonsmooth analysis are adopted from [31].

Definition 1(Page 14,[31]): Consider

III.PROBLEM FORMULATION

forxi∈Xi, where x-i=[x1,x2,...,xi-1,xi+1,...,xN]T.

Assumption 1: For eachi∈V,fi(x) is a C2function.

Assumption 2: Forx,z ∈RN,

wheremis a positive constant.Moreover, P(x) is globally Lipschitz with constantl.

IV.MAIN RESULTS

In this section, distributed Nash equilibrium seeking algorithms with logarithmic quantizers and uniform quantizers will be investigated under both undirected and directed communication graphs, respectively.

With quantization effects, the distributed Nash equilibrium seeking algorithm can be designed as

Remark 1: In practical implementation, the parameters of quantizers for players might be different due to the specific requirements of communication channels.It should be pointed out that the analysis method used in this paper can completely accommodate heterogeneous quantizer parameters for players.

Remark 2: Compared with [8], [9], this paper considers that players’ actions are subject to non-empty, convex and compact setsXifori∈V.To accommodate the constraints, a projection operator is employed in the seeking strategy.In addition, the quantization effects of communication channels are considered.

AsXiis non-empty, compact and convex, the projection operator has non-expansive property, i.e.,||PXi(γ1)-PXi(γ2)||≤||γ1-γ2||, for all γ1,γ1∈R.Moreover, following Lemma 1 in[33], the subsequent result can be obtained

Lemma 3: Given any x(0)∈X, x(t) generated by (5) is always feasible, i.e.,x(t)∈X,∀t≥0.

As quantization brings non-continuity into the right-hand side of (5), the solution of (5) is considered in the Filippov sense.Hence, forxi(0)∈Xi,i,j∈V, (5) is replaced by

Since the right-hand side of (6) is locally essentially bounded (i.e., bounded on a bounded neighborhood of every point, excluding sets of measure zero), the existence of a local Filippov solution is guaranteed by Lemma 2.In the following,convergence of (6) under undirected and directed communication topologies is shown, successively.

A. Distributed Nash Equilibrium Seeking Under Undirected Graphs With Quantization Effects

In this section, convergence analysis for games under the following communication condition is considered.

Assumption 3: Graph G is undirected and connected.

Theorem 1: Under Assumptions 1-3 and logarithmic quantizers,

Theorem 2: Under Assumptions 1-3 and uniform quantizers,

Remark 4: From Theorem 2, it is observed that the ultimate bound depends on game information, uniform quantizer parameter Φ, control gainκand graph information.Note that the error introduced by logarithmic quantizers is state-dependent, while the error introduced by uniform quantizers is constant.As a result, it can be clearly seen from Theorems 1 and 2 that the ultimate bound under logarithmic quantizers is dependent on the Nash equilibrium point x∗, but the ultimate bound under uniform quantizers is uncorrelated with the Nash equilibrium point x∗.Moreover, when ||x∗|| is small, logarithmic quantizers might result in small convergence errors.

Remark 5: WhenXi=R, the algorithm (5) is reduced to

Withδbeing any positive constant, similar results can be obtained for logarithmic and uniform quantizers, respectively,by following the proofs of Theorems 1 and 2.That is, no restriction is enforced on the choices ofδin (9) when action constraintsXifori∈V are not considered.More specifically,ifXi=R , it is only required that -(x-x∗)T[δ∇i fi(x)]vec≤-ω||x-x∗||2for some positive constantω, which is ensured by Assumption 2 with any positive constantδ.

Remark 6: When the quantization effects are not considered,the algorithm (5) is reduced to

Remark 7: When quantized communication is adopted, it inevitably introduces the quantized errors in the leader-following consensus algorithm (6), implying that distributed Nash equilibrium seeking strategies can achieve only bounded convergence but not asymptotic convergence (see Theorems 1 and 2).

In this section, stability of the equilibrium under undirected and connected communication topologies is investigated.With undirected communication networks, the seeking strategy might take advantages from symmetric information flows among players.In the following, stability properties under directed communication graphs are explored, which would result in asymmetry for the information flows among players.

B. Distributed Nash Equilibrium Seeking Under Directed Graphs

In this section, the problem is considered under directed communication topologies.

Remark 8: Comparing Theorems 1 and 2 with Theorems 3 and 4, respectively, one sees that under directed communication graphs, the ultimate convergence bounds depend on,which is resulted from asymmetric information exchange among players.

Remark 9: In [29], it is assumed that each player can exchange quantized data with any other players, that is the communication graph among players is complete or alternatively there is a central node that can bidirectionally communicate with all players.Under complete communication graphs/With a central node, gradient search method was considered in [29].Different from [29], this paper only requires that the communication graph is connected but not necessarily complete.As players are not able to directly exchange data with other players, gradient method in [29] cannot be utilized as it contains data not available for the players.Hence, (5) further employs a quantized consensus module for action estimation among players.By such a design, the proposed method relaxes the requirement on the communication topologies in[29] and is more suitable for applications of distributed systems.

V.SIMULATION STUDIES

In this section, a connectivity control problem for six omnidirectional mobile vehicles in a 2-dimensional space is considered [34].The positions of vehicles, denoted asxi=[xi1,xi2]T,are their actions.Each vehicle aims to make a tradeoff between its own local objective and global task of getting/keeping close to some of other vehicles, see, e.g., [34].Vehicles’ objective functions are given as

A. Distributed Nash Equilibrium Seeking With Quantization Effects Under Undirected Graphs

Fig.1.The communication graph for vehicles.

Fig.2.The vehicles’ position trajectories under (5), logarithmic quantizers and undirected G.

Fig.3.The vehicles’ position trajectories under (5), uniform quantizers and undirected G.

Fig.4.The trajectories of ||x(t)-x∗|| generated under (5) with logarithmic quantizers (ζ =0.85,0.88,0.9,0.95) and undirected G.

B. Distributed Nash Equilibrium Seeking With Quantization Effects Under Directed Graphs

Fig.5.The trajectories of ||x(t)-x∗|| under (5) with uniform quantizers(Φ=0.01,0.08,0.16,0.32) and undirected G.

Suppose that the players can communicate via a directed circle plotted in Fig.1(b).Wheng0=5, ζ=0.95, δ=0.1,κ=100 (Φ=0.01,δ=0.1,κ=100) and the communication channel is subject to logarithmic quantizers (uniform quantizers), vehicles’ positions generated by the proposed method are given in Fig.6 (Fig.7).From Figs.6 and 7, it can be seen that vehicles’ positions would converge to a small neighborhood of the Nash equilibrium thus verifying the theoretical results.

Fig.6.The vehicles’ position trajectories under (5), logarithmic quantizers and directed G.

Fig.7.The vehicles’ position trajectories under (5), uniform quantizers and directed G.

VI.CONCLUSIONS

This paper considers distributed Nash equilibrium seeking with quantization effects.Logarithmic quantizers and uniform quantizers are considered under both undirected communication topologies and strongly connected digraphs, respectively.It is shown that with both the logarithmic quantizers and uniform quantizers, the proposed seeking strategy can drive players’ actions to a small region around the Nash equilibrium,whose bound is proportional to the quantizer parameter.Future work will concentrate on the data privacy issue of distributed Nash equilibrium seeking algorithms like [26], [27].

APPENDIX

A. Proof of Theorem 1

Define

Then, we have

By Assumption 2, we obtain

inwhich | ∇i fi(x)-∇i fi(z)|2≥0 for eachi∈V.Hence,

and

based on the non-expansive property of the projection operator.Therefore, we have

B. Proof of Theorem 2

Using the functionVin the proof of Theorem 1, we have

With uniform quantizers,

Thus, the conclusion can be obtained.

C. Proof of Theorem 3

Define the Lyapunov candidate function as

Then, following the proof of Theorem 1, we have

Note that

whereql(yij)-yij=∆ijyi j, and

Then, we obtain

Summarizing the above equations, we have

the conclusion can be derived.

D. Proof of Theorem 4

By defining the sameVas that in the proof of Theorem 3,we obtain (19) and (20).Noticing thatwe have

Hence, we obtain

To this end, the conclusion can be easily derived.■