Distributed Nash Equilibrium Seeking Strategies Under Quantized Communication

This paper is concerned with distributed Nash equi librium seeking strategies under quantized communication. In the proposed seeking strategy, a projection operator is synthesized with a gradient search method to achieve the optimization o 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 informa tion 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, respec tively. Through Lyapunov stability analysis, it is shown that play ers' actions can be steered to a neighborhood of the Nash equilib rium with logarithmic and uniform quantizers, and the quanti fied convergence error depends on the parameter of the quan tizer for both undirected and directed cases. A numerical exam ple is given to verify the theoretical results.

Nash Equilibrium of a Fixed-Sum Two-Player Game

It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.

Distributed Nash Equilibrium Seeking for General Networked Games With Bounded Disturbances

This paper is concerned with anti-disturbance Nash equilibrium seeking for games with partial information.First,reduced-order disturbance observer-based algorithms are proposed to achieve Nash equilibrium seeking for games with firstorder and second-order players,respectively.In the developed algorithms,the observed disturbance values are included in control signals to eliminate the influence of disturbances,based on which a gradient-like optimization method is implemented for each player.Second,a signum function based distributed algorithm is proposed to attenuate disturbances for games with secondorder integrator-type players.To be more specific,a signum function is involved in the proposed seeking strategy to dominate disturbances,based on which the feedback of the velocity-like states and the gradients of the functions associated with players achieves stabilization of system dynamics and optimization of players'objective functions.Through Lyapunov stability analysis,it is proven that the players'actions can approach a small region around the Nash equilibrium by utilizing disturbance observerbased strategies with appropriate control gains.Moreover,exponential(asymptotic)convergence can be achieved when the signum function based control strategy(with an adaptive control gain)is employed.The performance of the proposed algorithms is tested by utilizing an integrated simulation platform of virtual robot experimentation platform(V-REP)and MATLAB.

Fully Distributed Nash Equilibrium Seeking for High-Order Players With Actuator Limitations

This paper explores the problem of distributed Nash equilibrium seeking in games, where players have limited knowledge on other players' actions. In particular, the involved players are considered to be high-order integrators with their control inputs constrained within a pre-specified region. A linear transformation for players' dynamics is firstly utilized to facilitate the design of bounded control inputs incorporating multiple saturation functions. By introducing consensus protocols with adaptive and time-varying gains, the unknown actions for players are distributively estimated. Then, a fully distributed Nash equilibrium seeking strategy is exploited, showcasing its remarkable properties: (1) ensuring the boundedness of control inputs;(2) avoiding any global information/parameters;and (3) allowing the graph to be directed. Based on Lyapunov stability analysis, it is theoretically proved that the proposed distributed control strategy can lead all the players' actions to the Nash equilibrium. Finally, an illustrative example is given to validate effectiveness of the proposed method.

A Penalty Approach for Generalized Nash Equilibrium Problem

The generalized Nash equilibrium problem （GNEP） is a generalization of the standard Nash equilibrium problem （NEP）, in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players. This problem has been used to model various problems in applications. However, the convergent solution algorithms are extremely scare in the literature. In this paper, we present an incremental penalty method for the GNEP, and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs. We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach.

On the finite horizon Nash equilibrium solution in the differential game approach to formation control

The solvability of the coupled Riccati differential equations appearing in the differential game approach to the formation control problem is vital to the finite horizon Nash equilibrium solution.These equations(if solvable)can be solved numerically by using the terminal value and the backward iteration.To investigate the solvability and solution of these equations the formation control problem as the differential game is replaced by a discrete-time dynamic game.The main contributions of this paper are as follows.First,the existence of Nash equilibrium controls for the discretetime formation control problem is shown.Second,a backward iteration approximate solution to the coupled Riccati differential equations in the continuous-time differential game is developed.An illustrative example is given to justify the models and solution.

Fuzzy Nash equilibrium of fuzzy n-person non-cooperative game

The fuzzy non-cooperative game with fuzzy payoff function is studied. Based on fuzzy set theory with game theory, the fuzzy Nash equilibrium of fuzzy non-cooperative games is proposed. Most of researchers rank fuzzy number by its center of gravity or by the real number with its maximal membership. By reducing fuzzy number into a real number, we lose much fuzzy information that should be kept during the operations between fuzzy numbers. The fuzzy quantities or alternatives are ordered directly by Yuan＇s binary fuzzy ordering relation. In doing so, the existence of fuzzy Nash equilibrium for fuzzy non-cooperative games is shown based on the utility function and the crisp Nash theorem. Finally, an illustrative example in traffic flow patterns of equilibrium is given in order to show the detailed calculation process of fuzzy Nash equilibrium.

Generalized Quantum Games with Nash Equilibrium

We define generalized quantum games by introducing the coherent payoff operators and propose a simple scheme to illustrate it.The scheme is implemented with a single spin qubit system and a two-entangled-qubit system.The Nash Equilibrium Theorem is proved for the models.

A Statistical Analysis of Games with No Certain Nash Equilibrium Make Many Results Doubtful

Some games may have a Nash equilibrium if the parameters (e.g. probabilities for success) take certain values but no equilibrium for other values. So there is a transition from Nash equilibrium to no Nash equilibrium in parameter space. However, in real games in business and economics, the input parameters are not given. They are typically observed in several similar occasions of the past. Therefore they have a distribution and the average is used. Even if the averages are in an area of Nash equilibrium, some values may be outside making the entire result meaningless. As the averages are sometimes just guessed, the distribution cannot be known. The main focus of this article is to show this effect in an example, and to explain the surprising result by topological explanations. We give an example of two players having three strategies each (e.g. player and keeper in penalty shooting) where we demonstrate the effect explicitly. As the transition of Nash equilibrium to no equilibrium is sharp, there may be a special form of chaos which we suggest to call topological chaos.

An Extension of One-Period Nash Equilibrium Model in Non-Life Insurance Markets

This paper deals with an extension of the one-period model in non-life insurance markets (cf. [1]) by using a transition probability matrix depending on some economic factors. We introduce a multi-period model and in each period the solvency constraints will be updated. Moreover, the model has the inactive state including some uninsured population. Similar results on the existence of premium equilibrium and sensitivity analysis for this model are presented and illustrated by numerical results.

Properties of Nash Equilibrium Retail Prices in Contract Model with a Supplier, Multiple Retailers and Price-Dependent Demand

Recently, price contract models between suppliers and retailers, with stochastic demand have been analyzed based on well-known newsvendor problems. In Bernstein and Federgruen [6], they have analyzed a contract model with single supplier and multiples retailers and price dependent demand, where retailers compete on retail prices. Each retailer decides a number of products he procures from the supplier and his retail price to maximize his own profit. This is achieved after giving the wholesale and buy-back prices, which are determined by the supplier as the supplier’s profit is maximized. Bernstein and Federgruen have proved that the retail prices become a unique Nash equilibrium solution under weak conditions on the price dependent distribution of demand. The authors, however, have not mentioned the numerical values and proprieties on these retail prices, the number of products and their individual and overall profits. In this paper, we analyze the model numerically. We first indicate some numerical problems with respect to theorem of Nash equilibrium solutions, which Bernstein and Federgruen proved, and we show their modified results. Then, we compute numerically Nash equilibrium prices, optimal wholesale and buy-back prices for the supplier’s and retailers’ profits, and supply chain optimal retailers’ prices. We also discuss properties on relation between these values and the demand distribution.

Distributed Nash Equilibrium Seeking on Compact Action Sets over Jointly Strongly Connected Switching Networks

This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the actions of all players in their action sets all the time,one has to resort to the projected gradient-based method.Under the assumption that the unique Nash equilibrium is the unique equilibrium of the pseudogradient system,an algorithm is proposed that is able to exponentially find the Nash equilibrium.Further,the authors also consider the distributed Nash equilibrium seeking problem for games whose actions are governed by high-order integrator dynamics and belong to some compact sets.Two examples are used to illustrate the proposed approach.

Nash equilibrium seeking with prescribed performance

In this work,we study a Nash equilibrium(NE)seeking problem for strongly monotone non-cooperative games with prescribed performance.Unlike general NE seeking algorithms,the proposed prescribed-performance NE seeking laws ensure that the convergence error evolves within a predefined region.Thus,the settling time,convergence rate,and maximum overshoot of the algorithm can be guaranteed.First,we develop a second-order Newton-like algorithm that can guarantee prescribed performance and asymptotically converge to the NE of the game.Then,we develop a first-order gradient-based algorithm.To remove some restrictions on this first-order algorithm,we propose two discontinuous dynamical system-based algorithms using tools from non-smooth analysis and adaptive control.We study the special case in optimization problems.Then,we investigate the robustness of the algorithms.It can be proven that the proposed algorithms can guarantee asymptotic convergence to the Nash equilibrium with prescribed performance in the presence of bounded disturbances.Furthermore,we consider a second-order dynamical system solution.The simulation results verify the effectiveness and efficiency of the algorithms,in terms of their convergence rate and disturbance rejection ability.

STOCHASTIC VARIATIONAL INEQUALITY APPROACHES TO THE STOCHASTIC GENERALIZED NASH EQUILIBRIUM WITH SHARED CONSTRAINTS

In this paper,we consider the generalized Nash equilibrium with shared constraints in the stochastic environment,and we call it the stochastic generalized Nash equilibrium.The stochastic variational inequalities are employed to solve this kind of problems,and the expected residual minimization model and the conditional value-at-risk formulations defined by the residual function for the stochastic variational inequalities are discussed.We show the risk for different kinds of solutions for the stochastic generalized Nash equilibrium by the conditional value-at-risk formulations.The properties of the stochastic quadratic generalized Nash equilibrium are shown.The smoothing approximations for the expected residual minimization formulation and the conditional value-at-risk formulation are employed.Moreover,we establish the gradient consistency for the measurable smoothing functions and the integrable functions under some suitable conditions,and we also analyze the properties of the formulations.Numerical results for the applications arising from the electricity market model illustrate that the solutions for the stochastic generalized Nash equilibrium given by the ERM model have good properties,such as robustness,low risk and so on.

Distributed Nash equilibrium seeking with order-reduced dynamics based on consensus exact penalty

In this paper,we consider a networked game with coupled constraints and focus on variational Nash equilibrium seeking.For distributed algorithm design,we eliminate the coupled constraints by employing local Lagrangian functions and construct exact penalty terms to attain multipliers'optimal consensus,which yields a set of equilibrium conditions without any coupled constraint and consensus constraint.Moreover,these conditions are only based on strategy and multiplier variables,without auxiliary variables.Then,we present a distributed order-reduced dynamics that updates the strategy and multiplier variables with guaranteed convergence.Compared with many other distributed algorithms,our algorithm contains no auxiliary variable,and therefore,it can save computation and communication.

A Bayesian Approach with Prior Mixed Strategy Nash Equilibrium for Vehicle Intention Prediction

The state-of-the-art technology in the field of vehicle automation will lead to a mixed traffic environment in the coming years,where connected and automated vehicles have to interact with human-driven vehicles.In this context,it is necessary to have intention prediction models with the capability of forecasting how the traffic scenario is going to evolve with respect to the physical state of vehicles,the possible maneuvers and the interactions between traffic participants within the seconds to come.This article presents a Bayesian approach for vehicle intention forecasting,utilizing a game-theoretic framework in the form of a Mixed Strategy Nash Equilibrium(MSNE)as a prior estimate to model the reciprocal influence between traffic participants.The likelihood is then computed based on the Kullback-Leibler divergence.The game is modeled as a static nonzero-sum polymatrix game with individual preferences,a well known strategic game.Finding the MSNE for these games is in the PPAD∩PLS complexity class,with polynomial-time tractability.The approach shows good results in simulations in the long term horizon(10s),with its computational complexity allowing for online applications.

具有加性耦合效用和连续统参与人博弈中的强Nash均衡

本文将研究具有加性耦合效用和连续统参与人博弈中的强Nash均衡。我们首先证明具有加性耦合效用和有限参与人博弈中强Nash均衡的存在性。进一步,对具有加性耦合效用和连续统参与人的博弈,我们引入弱强Nash均衡的概念,并证明它的存在性定理。本文发展了强Nash均衡的研究。

转移概率部分未知的离散时间Markov跳变系统Nash微分博弈

考虑到转移概率矩阵元素无法完全获悉,如何在转移概率部分未知的情境下研究离散时间Markov跳变系统Nash微分博弈是有待解决的问题之一,这一问题可以为转移概率部分未知的Markov跳变系统Nash微分博弈理论在管理问题上的应用提供理论支撑。基于此,本文首先研究单人博弈情形,即ε-次优控制问题,借助自由连接权矩阵和配方法,得到了ε-次优控制策略存在的充分性条件,并给出了成本函数上界的显式表达;然后延伸至双人博弈进行分析,得到了ε-次优Nash均衡策略存在的条件等价于求解双线性矩阵不等式和矩阵不等式的优化问题,并通过启发式算法求解优化问题得到ε-次优Nash均衡策略;最后通过数值算例证明了主要结论的有效性。

不连续多目标博弈弱Pareto-Nash均衡解的存在性与Hadamard良定性

该文主要考虑不连续多目标博弈问题解的存在性和良定性.首先将不连续条件更优回应保障推广到n人多目标博弈,证明了其弱Pareto-Nash均衡点的存在性定理.更进一步地,研究了此类不连续n人多目标博弈的Hadamard良定性.这些结果推广了P.J.Reny等的研究成果.

A distributed normalized Nash equilibrium seeking algorithm for power allocation among micro-grids

In this paper, a power allocation problem based on the Cournot game and generalized Nash game is proposed. After integrating dynamic average consensus algorithm and distributed projection neural network through singular perturbation systems, a normalized Nash equilibrium seeking algorithm is presented to solve the proposed power allocation problem in a distributed way.Combine Lyapunov stability with the singular perturbation analysis, the convergence of the proposed algorithm is analyzed. A simulation on IEEE 118-bus confirms that the proposed distributed algorithm can adjust the power allocation according to different situations, while keeping the optimal solution within the feasible set.