Optimization reformulations of the generalized Nash equilibrium problem using regularized indicator Nikaidô–Isoda function

In this paper, we extend the literature by adapting the Nikaidô–Isoda function as an indicator function termed as regularized indicator Nikaidô–Isoda function, and this is demonstrated to guarantee existence of a solution. Using this function, we present two constrained optimization reformulations of the generalized Nash equilibrium problem (GNEP for short). The first reformulation characterizes all the solutions of GNEP as global minima of the optimization problem. Later this approach is modified to obtain the second optimization reformulation whose global minima characterize the normalized Nash equilibria. Some numerical results are also included to illustrate the behaviour of the optimization reformulations.     

On solving generalized Nash equilibrium problems via optimization

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.     

Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems

Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.     

Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems

Using a regularized Nikaido-Isoda function, we present a (nonsmooth) constrained optimization reformulation of the player convex generalized Nash equilibrium problem (GNEP). Further we give an unconstrained reformulation of a large subclass of player convex GNEPs which, in particular, includes the jointly convex GNEPs. Both approaches characterize all solutions of a GNEP as minima of optimization problems. The smoothness properties of these optimization problems are discussed in detail, and it is shown that the corresponding objective functions are continuous and piecewise continuously differentiable under mild assumptions. Some numerical results based on the unconstrained optimization reformulation being applied to player convex GNEPs are also included.     

Computing Nash equilibria through computational intelligence methods

Nash equilibrium constitutes a central solution concept in game theory. The task of detecting the Nash equilibria of a finite strategic game remains a challenging problem up-to-date. This paper investigates the effectiveness of three computational intelligence techniques, namely, covariance matrix adaptation evolution strategies, particle swarm optimization, as well as, differential evolution, to compute Nash equilibria of finite strategic games, as global minima of a real-valued, nonnegative function. An issue of particular interest is to detect more than one Nash equilibria of a game. The performance of the considered computational intelligence methods on this problem is investigated using multistart and deflection.     

Noncooperative Games with Vector Payoffs Under Relative Pseudomonotonicity

We consider the Nash equilibrium problem with vector payoffs in a topological vector space. By employing the recent concept of relative (pseudo) monotonicity, we establish several existence results for vector Nash equilibria and vector equilibria. The results strengthen in a major way existence results for vector equilibrium problems which were based on the usual (generalized) monotonicity concepts.     

求解一类广义Nash均衡问题

Generalized Nash equilibrium problem (GNEP) is an important model that has many applications in practice. However, a GNEP usually has multiple or even infinitely many Nash equilibrium points and it is not easy to choose a favorable solution from those equilibria. This paper considers a class of GNEP with some kind of separability. We first extend the so-called normalized equilibrium concept to the stationarity sense and then, we propose an approach to solve the normalized stationary points by reformulating the GNEP as a single optimization problem. We further demonstrate the proposed approach on a GNEP model in similar product markets.     

Coordinate Transformations and Derivation of Open-Loop Nash Equilibria

Leitmann (Ref. 1) introduced coordinate transformations to derive global optima of a class of dynamic optimization problems. We present applications of this method to derive open-loop Nash equilibria for finite-time horizon differential games. The method of coordinate transformations is especially useful in cases where the original game does not satisfy the global curvature conditions normally imposed in sufficient optimality conditions.     

Mathematical programs with multiobjective generalized Nash equilibrium problems in the constraints

This paper considers a class of mathematical programs that include multiobjective generalized Nash equilibrium problems in the constraints. Little research can be found in the literature although it has some interesting applications. We present a single level reformulation for this kind of problems and show their equivalence in terms of global and local minimizers. We find that the reformulation is a special case of the so-called mathematical program with equilibrium constraints which is extensively studied in the literature.     

On differentiability properties of player convex generalized Nash equilibrium problems

Abstract

This article studies differentiability properties for a reformulation of a player convex generalized Nash equilibrium problem as a constrained and possibly nonsmooth minimization problem. By using several results from parametric optimization we show that, apart from exceptional cases, all locally minimal points of the reformulation are differentiability points of the objective function. This justifies a numerical approach which basically ignores the possible nondifferentiabilities.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

COMPETITION AND COOPERATION IN A DYNAMICAL MODEL OF NATURAL RESOURCES

Abstract In this paper, we propose a model describing the commercial exploitation of a common renewable resource by a population of strategically interacting agents. Players can cooperate or compete; cooperators maximize the payoff of their group while defectors maximize their own profit. The partition of the players into two groups, defectors and cooperators, results from the players' choices, so it is not predetermined. This partition is decided as a Nash equilibrium of a static game. It is shown that different types of players can exist in an equilibrium; more precisely, depending on the parameter values such as resource stock, cost, and so on, there might be equilibria only with defectors, cooperators, or with a combination of cooperators and defectors. In any case the total harvest depends on the renewable resource stock, so it influences agents' positions. It is assumed that at each time period the agents harvest according to Nash equilibrium, which can be combined with a dynamic model describing the evolution of fish population. A complete analysis of the equilibria is presented and their stability is analysed. The effect of the different Nash equilibria on the stability of the fish stock, showing that full cooperation is the most stable case, is examined.     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

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.     

Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic, and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give some numerical example to illustrate the behavior of robust Nash equilibria.     

0-1对策的完全混合Nash均衡的代数求解法

将求解一般0-1策略对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程组的问题.作为一种特殊而重要的情形,利用Pascal矩阵,Newton矩阵(对角元素为Newton二项式系数的对角矩阵)和Pascal-Newton矩阵(Pascal矩阵和Newton矩阵的逆阵的乘积)将求解对称0-1对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程的问题,并给出第二问题的反问题(由完全混合Nash均衡求解对称0-1对策族)的求解方法.同时,给出了一些算例来说明对应问题的算法.     

Nash Equilibria for the Multiobjective Control of Linear Partial Differential Equations

This article is concerned with the numerical solution of multiobjective control problems associated with linear partial differential equations. More precisely, for such problems, we look for the Nash equilibrium, which is the solution to a noncooperative game. First, we study the continuous case. Then, to compute the solution of the problem, we combine finite-difference methods for the time discretization, finite-element methods for the space discretization, and conjugate-gradient algorithms for the iterative solution of the discrete control problems. Finally, we apply the above methodology to the solution of several tests problems.     

可行策略对应的图像拓扑下广义博弈Nash平衡的稳定性

以往关于广义博弈Nash平衡的稳定性的研究,均利用可行策略映射之间的一致度量.现考虑在更弱的度量下,利用可行策略映射图像之间的Hausdorff距离定义度量.在此弱图像拓扑下,证明了广义博弈空间的完备性,以及Nash平衡映射的上半连续性和紧性,进而得到广义博弈Nash平衡的通有稳定性.即在Baire分类的意义下,大多数的广义博弈都是本质的.